Mercurial > code
annotate array.c @ 67:cff6869fbc94
Modified [p]array_find to return the index for a better usage
author | David Demelier <markand@malikania.fr> |
---|---|
date | Thu, 10 Nov 2011 18:27:04 +0100 |
parents | 9cc5d6d0563e |
children | b3ba5f5df3b9 |
rev | line source |
---|---|
62 | 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 | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
63 memmove((char *)arr->data + arr->unit, arr->data, OFFSET(arr->length++)); |
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
64 memcpy((char *)arr->data, data, arr->unit); |
62 | 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 | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
80 memmove((char *)arr->data + OFFSET(index + 1), |
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
81 (char *)arr->data + OFFSET(index), OFFSET(arr->length++ - index)); |
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
82 memcpy((char *)arr->data + OFFSET(index), data, arr->unit); |
62 | 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 | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
97 memcpy((char *)arr->data + OFFSET(arr->length++), data, arr->unit); |
62 | 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) { | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
110 memmove((char *)arr->data, (char *)arr->data + OFFSET(1), |
62 | 111 OFFSET(--arr->length)); |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
112 memset((char *)arr->data + OFFSET(arr->length), 0, arr->unit); |
62 | 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) | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
124 memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit); |
62 | 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) { | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
135 memmove((char *)arr->data + OFFSET(index), |
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
136 (char *)arr->data + OFFSET(index + 1), |
62 | 137 OFFSET(arr->length - index - 1)); |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
138 memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit); |
62 | 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) { | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
154 elm = (char *)arr->data + OFFSET(i); |
62 | 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 | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
184 memcpy((char *)tmp, (char *)arr->data + OFFSET(i1), arr->unit); |
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
185 memcpy((char *)arr->data + OFFSET(i1), (char *)arr->data + OFFSET(i2), |
62 | 186 arr->unit); |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
187 memcpy((char *)arr->data + OFFSET(i2), (char *)tmp, arr->unit); |
62 | 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) | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
212 found = memcmp((char *)arr->data + OFFSET(i1), o1, arr->unit) == 0; |
62 | 213 |
214 if (!found) | |
215 return -1; | |
216 | |
217 for (i2 = found = 0; !found && i2 < arr->length; ++i2) | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
218 found = memcmp((char *)arr->data + OFFSET(i2), o2, arr->unit) == 0; |
62 | 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 | |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
232 array_map(const struct array *arr, array_map_fn fn, void *udata) |
62 | 233 { |
234 int i; | |
235 | |
236 for (i = 0; i < arr->length; ++i) | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
237 fn((char *)arr->data + OFFSET(i), udata); |
62 | 238 } |
239 | |
240 /* | |
241 * Compare each object with the user supplied function. If the `fn' function | |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
242 * returns 1 then the index of the data position is returned and the parameter |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
243 * data is filled with the array data at the correct index. If the comparison |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
244 * function nevers returns 1, array_find returns -1. |
62 | 245 */ |
246 | |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
247 int |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
248 array_find(const struct array *arr, array_cmp_fn fn, void *data, void *u) |
62 | 249 { |
250 int st, i; | |
251 | |
252 for (i = st = 0; i < arr->length && st != 1; ++i) | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
253 st = fn((char *)arr->data + OFFSET(i), u); |
62 | 254 |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
255 if (st) |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
256 memcpy(data, (char *)arr->data + OFFSET(--i), arr->unit); |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
257 else |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
258 i = -1; |
62 | 259 |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
260 return i; |
62 | 261 } |
262 | |
263 /* | |
264 * Erase every bytes and set the length to 0. | |
265 */ | |
266 | |
267 void | |
268 array_clear(struct array *arr) | |
269 { | |
270 memset(arr->data, 0, arr->size); | |
271 arr->length = 0; | |
272 } | |
273 | |
274 /* | |
275 * Same as array_clear except it also free the array object. | |
276 */ | |
277 | |
278 void | |
279 array_free(struct array *arr) | |
280 { | |
281 array_clear(arr); | |
282 | |
283 if (arr->data) | |
284 free(arr->data); | |
285 | |
286 free(arr); | |
287 } | |
288 | |
289 /* | |
290 * Increate the array storage when it is full. If the buffer is fixed size | |
291 * it returns -1 on full buffer otherwise 0 is returned if allocation | |
292 * succeeded. | |
293 */ | |
294 | |
295 static int | |
296 array_grow(struct array *arr) | |
297 { | |
298 if ((arr->size / arr->unit) > (size_t) arr->length) | |
299 return 0; | |
300 | |
301 if (arr->type == ARRAY_AUTO) { | |
302 if ((arr->data = realloc(arr->data, arr->size + | |
303 OFFSET(arr->bsize))) == NULL) | |
304 return -1; | |
305 | |
306 arr->size += OFFSET(arr->bsize); | |
307 } else | |
308 return -1; | |
309 | |
310 return 0; | |
311 } |