Mercurial > code

comparison array.c @ 62:d10ab6bc555d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
HG self failure
author David Demelier <markand@malikania.fr>
date Wed, 09 Nov 2011 19:26:09 +0100
parents
children 9cc5d6d0563e
comparison
equal deleted inserted replaced
61:e1f3ed0bf507 62:d10ab6bc555d
1 /*
2 * array.c -- manipulate dynamic arrays
3 *
4 * Copyright (c) 2011, David Demelier <markand@malikania.fr>
5 *
6 * Permission to use, copy, modify, and/or distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <string.h>
22
23 #include "array.h"
24
25 #define OFFSET(x) (arr->unit * (x))
26
27 static int array_grow(struct array *);
28
29 struct array *
30 array_new(enum array_type type, size_t unit, int length)
31 {
32 struct array *arr;
33
34 if (unit == 0 || (arr = malloc(sizeof (struct array))) == NULL)
35 return NULL;
36
37 memset(arr, 0, sizeof (struct array));
38 arr->type = type;
39 arr->bsize = (length == 0) ? ARRAY_DEFAULT_BSIZE : length;
40 arr->unit = unit;
41 arr->size = OFFSET(arr->bsize);
42
43 if ((arr->data = malloc(arr->size)) == NULL) {
44 free(arr);
45 return NULL;
46 }
47
48 return arr;
49 }
50
51 /*
52 * Add to the head of array. NOTE: this may be very slow when adding a lot
53 * of object (about 100000). If you need to add a lot of data please consider
54 * using linked list instead.
55 */
56
57 int
58 array_push(struct array *arr, const void *data)
59 {
60 if (array_grow(arr) < 0)
61 return -1;
62
63 memmove((char *) arr->data + arr->unit, arr->data, OFFSET(arr->length++));
64 memcpy((char *) arr->data, data, arr->unit);
65
66 return 0;
67 }
68
69 /*
70 * Insert the data at the specified index. The function returns -1 on
71 * allocation failure or when the index is outof bounds otherwise 0 is returned.
72 */
73
74 int
75 array_insert(struct array *arr, const void *data, int index)
76 {
77 if (index > arr->length - 1 || index < 0 || array_grow(arr) < 0)
78 return -1;
79
80 memmove((char *) arr->data + OFFSET(index + 1),
81 (char *) arr->data + OFFSET(index), OFFSET(arr->length++ - index));
82 memcpy((char *) arr->data + OFFSET(index), data, arr->unit);
83
84 return 0;
85 }
86
87 /*
88 * Append the data to the end of array.
89 */
90
91 int
92 array_append(struct array *arr, const void *data)
93 {
94 if (array_grow(arr) < 0)
95 return -1;
96
97 memcpy((char *) arr->data + OFFSET(arr->length++), data, arr->unit);
98
99 return 0;
100 }
101
102 /*
103 * Remove the array's head.
104 */
105
106 void
107 array_pop(struct array *arr)
108 {
109 if (arr->length > 0) {
110 memmove((char *) arr->data, (char *) arr->data + OFFSET(1),
111 OFFSET(--arr->length));
112 memset((char *) arr->data + OFFSET(arr->length), 0, arr->unit);
113 }
114 }
115
116 /*
117 * Remove the array's tail.
118 */
119
120 void
121 array_unqueue(struct array *arr)
122 {
123 if (arr->length > 0)
124 memset((char *) arr->data + OFFSET(--arr->length), 0, arr->unit);
125 }
126
127 /*
128 * Remove the data at the specified index. Bounds are checked.
129 */
130
131 void
132 array_remove(struct array *arr, int index)
133 {
134 if (arr->length > 0 && index >= 0 && index < arr->length) {
135 memmove((char *) arr->data + OFFSET(index),
136 (char *) arr->data + OFFSET(index + 1),
137 OFFSET(arr->length - index - 1));
138 memset((char *) arr->data + OFFSET(--arr->length), 0, arr->unit);
139 }
140 }
141
142 /*
143 * Remove the object referenced by the `data' argument. Useful when you
144 * don't know the index.
145 */
146
147 void
148 array_unref(struct array *arr, const void *data)
149 {
150 void *elm;
151 int i;
152
153 for (i = 0; i < arr->length; ++i) {
154 elm = (char *) arr->data + OFFSET(i);
155
156 if (memcmp(elm, data, arr->unit) == 0)
157 array_remove(arr, i);
158 }
159 }
160
161 /*
162 * Swap the two elements referenced by index `i1' and `i2'. This function needs
163 * to allocate data to swap elements thus if the functions fails it returns -1
164 * otherwise 0 is returned.
165 */
166
167 int
168 array_iswap(struct array *arr, int i1, int i2)
169 {
170 void *tmp;
171
172 /* Out of bounds */
173 if (i1 >= arr->length || i1 < 0 || i2 >= arr->length || i2 < 0)
174 return -1;
175
176 /*
177 * Only allocate at this time, the user may do not want to use this
178 * function.
179 */
180
181 if ((tmp = malloc(arr->unit)) == NULL)
182 return -1;
183
184 memcpy((char *) tmp, (char *) arr->data + OFFSET(i1), arr->unit);
185 memcpy((char *) arr->data + OFFSET(i1), (char *) arr->data + OFFSET(i2),
186 arr->unit);
187 memcpy((char *) arr->data + OFFSET(i2), (char *) tmp, arr->unit);
188
189 /*
190 * Clear bytes for safety you probably don't want a password or
191 * secure data to be left somewhere in the memory.
192 */
193
194 memset(tmp, 0, arr->unit);
195 free(tmp);
196
197 return 0;
198 }
199
200 /*
201 * Swap the two elements referenced by data `o1' and `o2'. This function
202 * may be slow on large arrays since it must travel all the object
203 * to find the indexes.
204 */
205
206 int
207 array_pswap(struct array *arr, const void *o1, const void *o2)
208 {
209 int found, i1, i2;
210
211 for (i1 = found = 0; !found && i1 < arr->length; ++i1)
212 found = memcmp(arr->data + OFFSET(i1), o1, arr->unit) == 0;
213
214 if (!found)
215 return -1;
216
217 for (i2 = found = 0; !found && i2 < arr->length; ++i2)
218 found = memcmp(arr->data + OFFSET(i2), o2, arr->unit) == 0;
219
220 if (!found)
221 return -1;
222
223 return array_iswap(arr, --i1, --i2);
224 }
225
226 /*
227 * Apply the function `fn' on each object and give the optional `udata'
228 * argument to the function too.
229 */
230
231 void
232 array_map(const struct array *arr, void (*fn)(void *, void *), void *udata)
233 {
234 int i;
235
236 for (i = 0; i < arr->length; ++i)
237 fn((char *) arr->data + OFFSET(i), udata);
238 }
239
240 /*
241 * Compare each object with the user supplied function. If the `fn' function
242 * returns 1 then the data is returned. Optional idx argument can be set to
243 * indicate the data position. If the data was not found the function returns
244 * NULL.
245 */
246
247 void *
248 array_find(const struct array *arr, int (*fn)(void *, void *), int *ix, void *u)
249 {
250 int st, i;
251 void *data;
252
253 for (i = st = 0; i < arr->length && st != 1; ++i)
254 st = fn((char *) arr->data + OFFSET(i), u);
255
256 if (st) {
257 data = (char *) arr->data + OFFSET(--i);
258 if (ix)
259 *ix = i;
260 } else
261 data = NULL;
262
263 return data;
264 }
265
266 /*
267 * Erase every bytes and set the length to 0.
268 */
269
270 void
271 array_clear(struct array *arr)
272 {
273 memset(arr->data, 0, arr->size);
274 arr->length = 0;
275 }
276
277 /*
278 * Same as array_clear except it also free the array object.
279 */
280
281 void
282 array_free(struct array *arr)
283 {
284 array_clear(arr);
285
286 if (arr->data)
287 free(arr->data);
288
289 free(arr);
290 }
291
292 /*
293 * Increate the array storage when it is full. If the buffer is fixed size
294 * it returns -1 on full buffer otherwise 0 is returned if allocation
295 * succeeded.
296 */
297
298 static int
299 array_grow(struct array *arr)
300 {
301 if ((arr->size / arr->unit) > (size_t) arr->length)
302 return 0;
303
304 if (arr->type == ARRAY_AUTO) {
305 if ((arr->data = realloc(arr->data, arr->size +
306 OFFSET(arr->bsize))) == NULL)
307 return -1;
308
309 arr->size += OFFSET(arr->bsize);
310 } else
311 return -1;
312
313 return 0;
314 }