Mercurial > code
annotate array.c @ 99:d534fdcbb319
Remove #ifdef __cplusplus
author | David Demelier <markand@malikania.fr> |
---|---|
date | Fri, 13 Jan 2012 22:48:08 +0100 |
parents | b1a084c030c8 |
children | 06c968b92090 |
rev | line source |
---|---|
62 | 1 /* |
2 * array.c -- manipulate dynamic arrays | |
3 * | |
98 | 4 * Copyright (c) 2011, 2012, David Demelier <markand@malikania.fr> |
62 | 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 | |
91
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
29 int |
93
9ebea85c7765
Use pointer instead of copying variable in ARRAY_FOREACH, then you can modify it
David Demelier <markand@malikania.fr>
parents:
92
diff
changeset
|
30 array_init(struct array *arr, size_t unit) |
62 | 31 { |
91
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
32 if (unit == 0) |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
33 return -1; |
62 | 34 |
35 arr->unit = unit; | |
36 arr->size = OFFSET(arr->bsize); | |
37 | |
92 | 38 /* Set defaults if needed */ |
39 arr->bsize = (arr->bsize <= 0) ? ARRAY_DEFAULT_BSIZE : arr->bsize; | |
91
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
40 arr->malloc = (arr->malloc == NULL) ? &malloc : arr->malloc; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
41 arr->realloc = (arr->realloc == NULL) ? &realloc : arr->realloc; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
42 |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
43 if ((arr->data = arr->malloc(arr->size)) == NULL) |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
44 return -1; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
45 |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
46 return 0; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
47 } |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
48 |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
49 /* |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
50 * Valid options that can be set for an array : |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
51 * l -> optional array block size of type int |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
52 * m -> malloc function that must matches void * (*malloc)(size_t) |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
53 * r -> realloc function that must matches void * (*realloc)(void *, size_t) |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
54 * t -> type of array of type enum array_type |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
55 */ |
62 | 56 |
91
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
57 void |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
58 array_set(struct array *arr, const char *fmt, ...) |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
59 { |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
60 va_list ap; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
61 const char *p; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
62 |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
63 va_start(ap, fmt); |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
64 for (p = fmt; *p != '\0'; ++p) |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
65 switch (*p) { |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
66 case 'l': |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
67 arr->bsize = va_arg(ap, int); |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
68 break; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
69 case 'm': |
93
9ebea85c7765
Use pointer instead of copying variable in ARRAY_FOREACH, then you can modify it
David Demelier <markand@malikania.fr>
parents:
92
diff
changeset
|
70 arr->malloc = va_arg(ap, void *(*)(size_t)); |
91
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
71 break; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
72 case 'r': |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
73 arr->realloc = va_arg(ap, void *(*)(void *, size_t)); |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
74 break; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
75 case 't': |
99
d534fdcbb319
Remove #ifdef __cplusplus
David Demelier <markand@malikania.fr>
parents:
98
diff
changeset
|
76 arr->type = va_arg(ap, int); |
d534fdcbb319
Remove #ifdef __cplusplus
David Demelier <markand@malikania.fr>
parents:
98
diff
changeset
|
77 break; |
91
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
78 default: |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
79 break; |
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
80 } |
62 | 81 } |
82 | |
83 /* | |
84 * Add to the head of array. NOTE: this may be very slow when adding a lot | |
85 * of object (about 100000). If you need to add a lot of data please consider | |
86 * using linked list instead. | |
87 */ | |
88 | |
89 int | |
90 array_push(struct array *arr, const void *data) | |
91 { | |
92 if (array_grow(arr) < 0) | |
93 return -1; | |
94 | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
95 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
|
96 memcpy((char *)arr->data, data, arr->unit); |
62 | 97 |
98 return 0; | |
99 } | |
100 | |
101 /* | |
102 * Insert the data at the specified index. The function returns -1 on | |
103 * allocation failure or when the index is outof bounds otherwise 0 is returned. | |
104 */ | |
105 | |
106 int | |
107 array_insert(struct array *arr, const void *data, int index) | |
108 { | |
109 if (index > arr->length - 1 || index < 0 || array_grow(arr) < 0) | |
110 return -1; | |
111 | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
112 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
|
113 (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
|
114 memcpy((char *)arr->data + OFFSET(index), data, arr->unit); |
62 | 115 |
116 return 0; | |
117 } | |
118 | |
119 /* | |
120 * Append the data to the end of array. | |
121 */ | |
122 | |
123 int | |
124 array_append(struct array *arr, const void *data) | |
125 { | |
126 if (array_grow(arr) < 0) | |
127 return -1; | |
128 | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
129 memcpy((char *)arr->data + OFFSET(arr->length++), data, arr->unit); |
62 | 130 |
131 return 0; | |
132 } | |
133 | |
134 /* | |
135 * Remove the array's head. | |
136 */ | |
137 | |
138 void | |
139 array_pop(struct array *arr) | |
140 { | |
141 if (arr->length > 0) { | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
142 memmove((char *)arr->data, (char *)arr->data + OFFSET(1), |
62 | 143 OFFSET(--arr->length)); |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
144 memset((char *)arr->data + OFFSET(arr->length), 0, arr->unit); |
62 | 145 } |
146 } | |
147 | |
148 /* | |
149 * Remove the array's tail. | |
150 */ | |
151 | |
152 void | |
153 array_unqueue(struct array *arr) | |
154 { | |
155 if (arr->length > 0) | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
156 memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit); |
62 | 157 } |
158 | |
159 /* | |
160 * Remove the data at the specified index. Bounds are checked. | |
161 */ | |
162 | |
163 void | |
164 array_remove(struct array *arr, int index) | |
165 { | |
166 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
|
167 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
|
168 (char *)arr->data + OFFSET(index + 1), |
62 | 169 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
|
170 memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit); |
62 | 171 } |
172 } | |
173 | |
174 /* | |
175 * Remove the object referenced by the `data' argument. Useful when you | |
176 * don't know the index. | |
177 */ | |
178 | |
179 void | |
180 array_unref(struct array *arr, const void *data) | |
181 { | |
182 void *elm; | |
183 int i; | |
184 | |
185 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
|
186 elm = (char *)arr->data + OFFSET(i); |
62 | 187 |
188 if (memcmp(elm, data, arr->unit) == 0) | |
189 array_remove(arr, i); | |
190 } | |
191 } | |
192 | |
193 /* | |
194 * Swap the two elements referenced by index `i1' and `i2'. This function needs | |
195 * to allocate data to swap elements thus if the functions fails it returns -1 | |
196 * otherwise 0 is returned. | |
197 */ | |
198 | |
199 int | |
200 array_iswap(struct array *arr, int i1, int i2) | |
201 { | |
202 void *tmp; | |
203 | |
204 /* Out of bounds */ | |
205 if (i1 >= arr->length || i1 < 0 || i2 >= arr->length || i2 < 0) | |
206 return -1; | |
207 | |
208 /* | |
209 * Only allocate at this time, the user may do not want to use this | |
210 * function. | |
211 */ | |
212 | |
91
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
213 if ((tmp = arr->malloc(arr->unit)) == NULL) |
62 | 214 return -1; |
215 | |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
216 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
|
217 memcpy((char *)arr->data + OFFSET(i1), (char *)arr->data + OFFSET(i2), |
62 | 218 arr->unit); |
64
9cc5d6d0563e
Add more cast for old gcc and other cc
David Demelier <markand@malikania.fr>
parents:
62
diff
changeset
|
219 memcpy((char *)arr->data + OFFSET(i2), (char *)tmp, arr->unit); |
62 | 220 |
221 /* | |
222 * Clear bytes for safety you probably don't want a password or | |
223 * secure data to be left somewhere in the memory. | |
224 */ | |
225 | |
226 memset(tmp, 0, arr->unit); | |
227 free(tmp); | |
228 | |
229 return 0; | |
230 } | |
231 | |
232 /* | |
233 * Swap the two elements referenced by data `o1' and `o2'. This function | |
234 * may be slow on large arrays since it must travel all the object | |
235 * to find the indexes. | |
236 */ | |
237 | |
238 int | |
239 array_pswap(struct array *arr, const void *o1, const void *o2) | |
240 { | |
241 int found, i1, i2; | |
242 | |
243 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
|
244 found = memcmp((char *)arr->data + OFFSET(i1), o1, arr->unit) == 0; |
62 | 245 |
246 if (!found) | |
247 return -1; | |
248 | |
249 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
|
250 found = memcmp((char *)arr->data + OFFSET(i2), o2, arr->unit) == 0; |
62 | 251 |
252 if (!found) | |
253 return -1; | |
254 | |
255 return array_iswap(arr, --i1, --i2); | |
256 } | |
257 | |
258 /* | |
259 * Apply the function `fn' on each object and give the optional `udata' | |
260 * argument to the function too. | |
261 */ | |
262 | |
263 void | |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
264 array_map(const struct array *arr, array_map_fn fn, void *udata) |
62 | 265 { |
266 int i; | |
267 | |
268 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
|
269 fn((char *)arr->data + OFFSET(i), udata); |
62 | 270 } |
271 | |
272 /* | |
273 * 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
|
274 * 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
|
275 * 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
|
276 * function nevers returns 1, array_find returns -1. |
62 | 277 */ |
278 | |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
279 int |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
280 array_find(const struct array *arr, array_cmp_fn fn, void *data, void *u) |
62 | 281 { |
282 int st, i; | |
283 | |
284 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
|
285 st = fn((char *)arr->data + OFFSET(i), u); |
62 | 286 |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
287 if (st) |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
288 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
|
289 else |
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
290 i = -1; |
62 | 291 |
67
cff6869fbc94
Modified [p]array_find to return the index for a better usage
David Demelier <markand@malikania.fr>
parents:
64
diff
changeset
|
292 return i; |
62 | 293 } |
294 | |
295 /* | |
296 * Erase every bytes and set the length to 0. | |
297 */ | |
298 | |
299 void | |
300 array_clear(struct array *arr) | |
301 { | |
302 memset(arr->data, 0, arr->size); | |
303 arr->length = 0; | |
304 } | |
305 | |
306 /* | |
307 * Same as array_clear except it also free the array object. | |
308 */ | |
309 | |
310 void | |
311 array_free(struct array *arr) | |
312 { | |
313 array_clear(arr); | |
314 | |
315 if (arr->data) | |
316 free(arr->data); | |
317 } | |
318 | |
319 /* | |
320 * Increate the array storage when it is full. If the buffer is fixed size | |
321 * it returns -1 on full buffer otherwise 0 is returned if allocation | |
322 * succeeded. | |
323 */ | |
324 | |
325 static int | |
326 array_grow(struct array *arr) | |
327 { | |
328 if ((arr->size / arr->unit) > (size_t) arr->length) | |
329 return 0; | |
330 | |
331 if (arr->type == ARRAY_AUTO) { | |
91
b3ba5f5df3b9
New style for array.c and array.h, no pointer to these object thus
David Demelier <markand@malikania.fr>
parents:
67
diff
changeset
|
332 if ((arr->data = arr->realloc(arr->data, arr->size + |
62 | 333 OFFSET(arr->bsize))) == NULL) |
334 return -1; | |
335 | |
336 arr->size += OFFSET(arr->bsize); | |
337 } else | |
338 return -1; | |
339 | |
340 return 0; | |
341 } |