Mercurial > code
comparison array.c @ 6:25cc379de564
Added array.c and array.h:
Various function to manipulate dynamic array. This let you adding as
much as you want object into the array. You may add object to the head,
end or at a specified index.
author | David Demelier <markand@malikania.fr> |
---|---|
date | Tue, 06 Sep 2011 22:19:18 +0200 |
parents | |
children | e8829146ebc7 |
comparison
equal
deleted
inserted
replaced
5:0ed27735fa87 | 6:25cc379de564 |
---|---|
1 /* | |
2 * array.h -- manipulate dymanic array | |
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 SIZE(x) (sizeof (void *) * (x)) | |
26 | |
27 static int array_grow(struct array *); | |
28 | |
29 struct array * | |
30 array_new(const void *data, size_t bsize, int flags) | |
31 { | |
32 struct array *arr; | |
33 | |
34 if (!(arr = malloc(sizeof (struct array)))) | |
35 return NULL; | |
36 | |
37 memset(arr, 0, sizeof (struct array)); | |
38 arr->bsize = (bsize == 0) ? ARRAY_DEFAULT_BSIZE : bsize; | |
39 arr->size = bsize + 1; | |
40 arr->flags = flags; | |
41 | |
42 if (!(arr->data = calloc(bsize + 1, sizeof (void *)))) { | |
43 free(arr); | |
44 return NULL; | |
45 } | |
46 | |
47 if (data) | |
48 arr->data[arr->length++] = (void *) data; | |
49 | |
50 return arr; | |
51 } | |
52 | |
53 /* | |
54 * Add to the head of array. NOTE: this may be very slow when adding a lot | |
55 * of object (about 100000). If you need to add a lot of data please consider | |
56 * using linked list instead or use array_append and then use reverse foreach | |
57 * functions. | |
58 */ | |
59 | |
60 int | |
61 array_push(struct array *arr, const void *data) | |
62 { | |
63 if (array_grow(arr) < 0) | |
64 return -1; | |
65 | |
66 memmove(arr->data + 1, arr->data, SIZE(arr->length++)); | |
67 arr->data[0] = (void *) data; | |
68 | |
69 return 0; | |
70 } | |
71 | |
72 /* | |
73 * Insert the data to the specified index. The function returns -1 on | |
74 * allocation failure if the array need to grow or when the index is out | |
75 * of bounds otherwise 0 is returned. | |
76 */ | |
77 | |
78 int | |
79 array_insert(struct array *arr, const void *data, int index) | |
80 { | |
81 if (index > arr->length - 1 || index < 0 || array_grow(arr) < 0) | |
82 return -1; | |
83 | |
84 memmove(arr->data + index + 1, arr->data + index, | |
85 SIZE(arr->length++ - index)); | |
86 arr->data[index] = (void *) data; | |
87 | |
88 return 0; | |
89 } | |
90 | |
91 /* | |
92 * Append the data to the end of array. | |
93 */ | |
94 | |
95 int | |
96 array_append(struct array *arr, const void *data) | |
97 { | |
98 if (array_grow(arr) < 0) | |
99 return -1; | |
100 | |
101 arr->data[arr->length++] = (void *) data; | |
102 | |
103 return 0; | |
104 } | |
105 | |
106 /* | |
107 * Remove the array's head and return the object or NULL if | |
108 * the array is empty. | |
109 */ | |
110 | |
111 void * | |
112 array_pop(struct array *arr) | |
113 { | |
114 void *data; | |
115 | |
116 if (arr->length == 0) | |
117 return NULL; | |
118 | |
119 data = arr->data[0]; | |
120 memmove(arr->data, arr->data + 1, SIZE(arr->length)); | |
121 arr->data[--arr->length] = NULL; | |
122 | |
123 return data; | |
124 } | |
125 | |
126 /* | |
127 * Remove the array's queue and return the object or NULL | |
128 * if the array is empty. | |
129 */ | |
130 | |
131 void * | |
132 array_unqueue(struct array *arr) | |
133 { | |
134 void *data; | |
135 | |
136 if (arr->length == 0) | |
137 return NULL; | |
138 | |
139 data = arr->data[--arr->length]; | |
140 arr->data[arr->length] = NULL; | |
141 | |
142 return data; | |
143 } | |
144 | |
145 /* | |
146 * Remove the entry at the specified index and return it. If the index is out of | |
147 * bounds or the list is empty the functions returns NULL. | |
148 */ | |
149 | |
150 void * | |
151 array_remove(struct array *arr, int index) | |
152 { | |
153 void *data; | |
154 | |
155 if (arr->length == 0 || index < 0 || index > arr->length - 1) | |
156 return NULL; | |
157 | |
158 data = arr->data[index]; | |
159 memmove(arr->data + index, arr->data + index + 1, | |
160 SIZE(arr->length - index)); | |
161 arr->data[--arr->length] = NULL; | |
162 | |
163 return data; | |
164 } | |
165 | |
166 /* | |
167 * Apply the function `fn' on each object and give the optional `udata' | |
168 * argument to the function too. | |
169 */ | |
170 | |
171 void | |
172 array_map(struct array *arr, void (*fn)(void *, void *), void *udata) | |
173 { | |
174 size_t i; | |
175 | |
176 for (i = 0; arr->data[i]; ++i) | |
177 fn(arr->data[i], udata); | |
178 } | |
179 | |
180 /* | |
181 * Compare each object with the user supplied function. If the `fn' function | |
182 * returns 1 then the data is returned. Optional idx argument can be set to | |
183 * indicate the data position. If the data was not found the function returns | |
184 * NULL. | |
185 */ | |
186 | |
187 void * | |
188 array_find(struct array *arr, int (*fn)(void *, void *), void *udata, int *idx) | |
189 { | |
190 size_t i; | |
191 int st; | |
192 void *data; | |
193 | |
194 for (i = st = 0; arr->data[i] && !st; ++i) | |
195 st = fn(arr->data[i], udata); | |
196 | |
197 if (st) { | |
198 data = arr->data[--i]; | |
199 if (idx) | |
200 *idx = i; | |
201 } else | |
202 data = NULL; | |
203 | |
204 return data; | |
205 } | |
206 | |
207 /* | |
208 * Reset the array, if the trash argument is set it will free the object | |
209 * too, otherwise the array is just truncated to 0 length. | |
210 */ | |
211 | |
212 void | |
213 array_clear(struct array *arr, int trashit) | |
214 { | |
215 if (trashit) { | |
216 size_t i; | |
217 | |
218 for (i = 0; arr->data[i]; ++i) | |
219 free(arr->data[i]); | |
220 } | |
221 | |
222 memset(arr->data, 0, SIZE(arr->size)); | |
223 arr->length = 0; | |
224 } | |
225 | |
226 /* | |
227 * Same as array_clear except it also free the array object. | |
228 */ | |
229 | |
230 void | |
231 array_free(struct array *arr, int trashit) | |
232 { | |
233 array_clear(arr, trashit); | |
234 | |
235 free(arr->data); | |
236 free(arr); | |
237 } | |
238 | |
239 /* | |
240 * Increate the array storage when it is full. If the buffer is fixed size | |
241 * it returns -1 on full buffer otherwise 0 is returned if allocation | |
242 * succeeded. | |
243 */ | |
244 | |
245 static int | |
246 array_grow(struct array *arr) | |
247 { | |
248 if (arr->size - 1 > arr->length) | |
249 return 0; | |
250 | |
251 if (arr->flags & ARRAY_AUTO) { | |
252 if (!(arr->data = realloc(arr->data, SIZE(arr->size + arr->bsize)))) | |
253 return -1; | |
254 | |
255 arr->size += arr->bsize; | |
256 } else | |
257 return (arr->size - 1 == arr->length) ? -1 : 0; | |
258 | |
259 memset(arr->data + arr->length, 0, SIZE(arr->size - arr->length)); | |
260 | |
261 return 0; | |
262 } |