Mercurial > code

comparison array.c @ 6:25cc379de564

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }