1 /*
2 * Dynamically Resized Array
3 *
4 * Authors: Alfredo K. Kojima <kojima@windowmaker.info>
5 * Dan Pascu <dan@windowmaker.info>
6 *
7 * This code is released to the Public Domain, but
8 * proper credit is always appreciated :)
9 */
10
11 #include <stdlib.h>
12 #include <string.h>
13
14 #include "WUtil.h"
15
16 #define INITIAL_SIZE 8
17 #define RESIZE_INCREMENT 8
18
19 typedef struct W_Array {
20 void **items; /* the array data */
21 int itemCount; /* # of items in array */
22 int allocSize; /* allocated size of array */
23 WMFreeDataProc *destructor; /* the destructor to free elements */
24 } W_Array;
25
WMCreateArray(int initialSize)26 WMArray *WMCreateArray(int initialSize)
27 {
28 return WMCreateArrayWithDestructor(initialSize, NULL);
29 }
30
WMCreateArrayWithDestructor(int initialSize,WMFreeDataProc * destructor)31 WMArray *WMCreateArrayWithDestructor(int initialSize, WMFreeDataProc * destructor)
32 {
33 WMArray *array;
34
35 array = wmalloc(sizeof(WMArray));
36
37 if (initialSize <= 0) {
38 initialSize = INITIAL_SIZE;
39 }
40
41 array->items = wmalloc(sizeof(void *) * initialSize);
42
43 array->itemCount = 0;
44 array->allocSize = initialSize;
45 array->destructor = destructor;
46
47 return array;
48 }
49
WMCreateArrayWithArray(WMArray * array)50 WMArray *WMCreateArrayWithArray(WMArray * array)
51 {
52 WMArray *newArray;
53
54 newArray = wmalloc(sizeof(WMArray));
55
56 newArray->items = wmalloc(sizeof(void *) * array->allocSize);
57 memcpy(newArray->items, array->items, sizeof(void *) * array->itemCount);
58
59 newArray->itemCount = array->itemCount;
60 newArray->allocSize = array->allocSize;
61 newArray->destructor = NULL;
62
63 return newArray;
64 }
65
WMEmptyArray(WMArray * array)66 void WMEmptyArray(WMArray * array)
67 {
68 if (array->destructor) {
69 while (array->itemCount > 0) {
70 array->itemCount--;
71 array->destructor(array->items[array->itemCount]);
72 }
73 }
74 /*memset(array->items, 0, array->itemCount * sizeof(void*)); */
75 array->itemCount = 0;
76 }
77
WMFreeArray(WMArray * array)78 void WMFreeArray(WMArray * array)
79 {
80 if (array == NULL)
81 return;
82
83 WMEmptyArray(array);
84 wfree(array->items);
85 wfree(array);
86 }
87
WMGetArrayItemCount(WMArray * array)88 int WMGetArrayItemCount(WMArray * array)
89 {
90 if (array == NULL)
91 return 0;
92
93 return array->itemCount;
94 }
95
WMAppendArray(WMArray * array,WMArray * other)96 void WMAppendArray(WMArray * array, WMArray * other)
97 {
98 if (array == NULL || other == NULL)
99 return;
100
101 if (other->itemCount == 0)
102 return;
103
104 if (array->itemCount + other->itemCount > array->allocSize) {
105 array->allocSize += other->allocSize;
106 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
107 }
108
109 memcpy(array->items + array->itemCount, other->items, sizeof(void *) * other->itemCount);
110 array->itemCount += other->itemCount;
111 }
112
WMAddToArray(WMArray * array,void * item)113 void WMAddToArray(WMArray * array, void *item)
114 {
115 if (array == NULL)
116 return;
117
118 if (array->itemCount >= array->allocSize) {
119 array->allocSize += RESIZE_INCREMENT;
120 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
121 }
122 array->items[array->itemCount] = item;
123
124 array->itemCount++;
125 }
126
WMInsertInArray(WMArray * array,int index,void * item)127 void WMInsertInArray(WMArray * array, int index, void *item)
128 {
129 if (array == NULL)
130 return;
131
132 wassertr(index >= 0 && index <= array->itemCount);
133
134 if (array->itemCount >= array->allocSize) {
135 array->allocSize += RESIZE_INCREMENT;
136 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
137 }
138 if (index < array->itemCount) {
139 memmove(array->items + index + 1, array->items + index,
140 sizeof(void *) * (array->itemCount - index));
141 }
142 array->items[index] = item;
143
144 array->itemCount++;
145 }
146
WMReplaceInArray(WMArray * array,int index,void * item)147 void *WMReplaceInArray(WMArray * array, int index, void *item)
148 {
149 void *old;
150
151 if (array == NULL)
152 return NULL;
153
154 wassertrv(index >= 0 && index <= array->itemCount, NULL);
155
156 /* is it really useful to perform append if index == array->itemCount ? -Dan */
157 if (index == array->itemCount) {
158 WMAddToArray(array, item);
159 return NULL;
160 }
161
162 old = array->items[index];
163 array->items[index] = item;
164
165 return old;
166 }
167
WMDeleteFromArray(WMArray * array,int index)168 int WMDeleteFromArray(WMArray * array, int index)
169 {
170 if (array == NULL)
171 return 0;
172
173 wassertrv(index >= 0 && index < array->itemCount, 0);
174
175 if (array->destructor) {
176 array->destructor(array->items[index]);
177 }
178
179 if (index < array->itemCount - 1) {
180 memmove(array->items + index, array->items + index + 1,
181 sizeof(void *) * (array->itemCount - index - 1));
182 }
183
184 array->itemCount--;
185
186 return 1;
187 }
188
WMRemoveFromArrayMatching(WMArray * array,WMMatchDataProc * match,void * cdata)189 int WMRemoveFromArrayMatching(WMArray * array, WMMatchDataProc * match, void *cdata)
190 {
191 int i;
192
193 if (array == NULL)
194 return 1;
195
196 if (match != NULL) {
197 for (i = 0; i < array->itemCount; i++) {
198 if ((*match) (array->items[i], cdata)) {
199 WMDeleteFromArray(array, i);
200 return 1;
201 }
202 }
203 } else {
204 for (i = 0; i < array->itemCount; i++) {
205 if (array->items[i] == cdata) {
206 WMDeleteFromArray(array, i);
207 return 1;
208 }
209 }
210 }
211
212 return 0;
213 }
214
WMGetFromArray(WMArray * array,int index)215 void *WMGetFromArray(WMArray * array, int index)
216 {
217 if (index < 0 || array == NULL || index >= array->itemCount)
218 return NULL;
219
220 return array->items[index];
221 }
222
WMPopFromArray(WMArray * array)223 void *WMPopFromArray(WMArray * array)
224 {
225 if (array == NULL || array->itemCount <= 0)
226 return NULL;
227
228 array->itemCount--;
229
230 return array->items[array->itemCount];
231 }
232
WMFindInArray(WMArray * array,WMMatchDataProc * match,void * cdata)233 int WMFindInArray(WMArray * array, WMMatchDataProc * match, void *cdata)
234 {
235 int i;
236
237 if (array == NULL)
238 return WANotFound;
239
240 if (match != NULL) {
241 for (i = 0; i < array->itemCount; i++) {
242 if ((*match) (array->items[i], cdata))
243 return i;
244 }
245 } else {
246 for (i = 0; i < array->itemCount; i++) {
247 if (array->items[i] == cdata)
248 return i;
249 }
250 }
251
252 return WANotFound;
253 }
254
WMCountInArray(WMArray * array,void * item)255 int WMCountInArray(WMArray * array, void *item)
256 {
257 int i, count;
258
259 if (array == NULL)
260 return 0;
261
262 for (i = 0, count = 0; i < array->itemCount; i++) {
263 if (array->items[i] == item)
264 count++;
265 }
266
267 return count;
268 }
269
WMSortArray(WMArray * array,WMCompareDataProc * comparer)270 void WMSortArray(WMArray * array, WMCompareDataProc * comparer)
271 {
272 if (array == NULL)
273 return;
274
275 if (array->itemCount > 1) { /* Don't sort empty or single element arrays */
276 qsort(array->items, array->itemCount, sizeof(void *), comparer);
277 }
278 }
279
WMMapArray(WMArray * array,void (* function)(void *,void *),void * data)280 void WMMapArray(WMArray * array, void (*function) (void *, void *), void *data)
281 {
282 int i;
283
284 if (array == NULL)
285 return;
286
287 for (i = 0; i < array->itemCount; i++) {
288 (*function) (array->items[i], data);
289 }
290 }
291
WMGetSubarrayWithRange(WMArray * array,WMRange aRange)292 WMArray *WMGetSubarrayWithRange(WMArray * array, WMRange aRange)
293 {
294 WMArray *newArray;
295
296 if (aRange.count <= 0 || array == NULL)
297 return WMCreateArray(0);
298
299 if (aRange.position < 0)
300 aRange.position = 0;
301 if (aRange.position >= array->itemCount)
302 aRange.position = array->itemCount - 1;
303 if (aRange.position + aRange.count > array->itemCount)
304 aRange.count = array->itemCount - aRange.position;
305
306 newArray = WMCreateArray(aRange.count);
307 memcpy(newArray->items, array->items + aRange.position, sizeof(void *) * aRange.count);
308 newArray->itemCount = aRange.count;
309
310 return newArray;
311 }
312
WMArrayFirst(WMArray * array,WMArrayIterator * iter)313 void *WMArrayFirst(WMArray * array, WMArrayIterator * iter)
314 {
315 if (array == NULL || array->itemCount == 0) {
316 *iter = WANotFound;
317 return NULL;
318 } else {
319 *iter = 0;
320 return array->items[0];
321 }
322 }
323
WMArrayLast(WMArray * array,WMArrayIterator * iter)324 void *WMArrayLast(WMArray * array, WMArrayIterator * iter)
325 {
326 if (array == NULL || array->itemCount == 0) {
327 *iter = WANotFound;
328 return NULL;
329 } else {
330 *iter = array->itemCount - 1;
331 return array->items[*iter];
332 }
333 }
334
WMArrayNext(WMArray * array,WMArrayIterator * iter)335 void *WMArrayNext(WMArray * array, WMArrayIterator * iter)
336 {
337 if (array == NULL) {
338 *iter = WANotFound;
339 return NULL;
340 }
341
342 if (*iter >= 0 && *iter < array->itemCount - 1) {
343 return array->items[++(*iter)];
344 } else {
345 *iter = WANotFound;
346 return NULL;
347 }
348 }
349
WMArrayPrevious(WMArray * array,WMArrayIterator * iter)350 void *WMArrayPrevious(WMArray * array, WMArrayIterator * iter)
351 {
352 if (array == NULL) {
353 *iter = WANotFound;
354 return NULL;
355 }
356
357 if (*iter > 0 && *iter < array->itemCount) {
358 return array->items[--(*iter)];
359 } else {
360 *iter = WANotFound;
361 return NULL;
362 }
363 }
364