1 /*
2 * Copyright (c) 1999-2002, Darren Hiebert
3 *
4 * This source code is released for free distribution under the terms of the
5 * GNU General Public License version 2 or (at your option) any later version.
6 *
7 * This module contains functions managing resizable pointer arrays.
8 */
9
10 /*
11 * INCLUDE FILES
12 */
13 #include "general.h" /* must always come first */
14
15 #include <string.h>
16 #include <stdlib.h>
17
18 #include "debug.h"
19 #include "ptrarray.h"
20 #include "routines.h"
21
22 /*
23 * DATA DECLARATIONS
24 */
25
26 struct sPtrArray {
27 unsigned int max;
28 unsigned int count;
29 void **array;
30 ptrArrayDeleteFunc deleteFunc;
31 };
32
33 /*
34 * FUNCTION DEFINITIONS
35 */
36
ptrArrayNew(ptrArrayDeleteFunc deleteFunc)37 extern ptrArray *ptrArrayNew (ptrArrayDeleteFunc deleteFunc)
38 {
39 ptrArray* const result = xMalloc (1, ptrArray);
40 result->max = 8;
41 result->count = 0;
42 result->array = xMalloc (result->max, void*);
43 result->deleteFunc = deleteFunc;
44 return result;
45 }
46
ptrArrayAdd(ptrArray * const current,void * ptr)47 extern unsigned int ptrArrayAdd (ptrArray *const current, void *ptr)
48 {
49 Assert (current != NULL);
50 if (current->count == current->max)
51 {
52 current->max *= 2;
53 current->array = xRealloc (current->array, current->max, void*);
54 }
55 current->array [current->count] = ptr;
56 return current->count++;
57 }
58
ptrArrayUpdate(ptrArray * const current,unsigned int indx,void * ptr,void * padding)59 extern bool ptrArrayUpdate (ptrArray *const current,
60 unsigned int indx, void *ptr, void *padding)
61 {
62 Assert (current != NULL);
63 if (current->count > indx)
64 {
65 void *r = current->array [indx];
66 if (current->deleteFunc)
67 current->deleteFunc (r);
68 current->array [indx] = ptr;
69 return true;
70 }
71 else
72 {
73 unsigned int c = indx - current->count;
74 for (unsigned int i = 0; i < c; i++)
75 ptrArrayAdd (current, padding);
76 ptrArrayAdd (current, ptr);
77 return false;
78 }
79
80 }
ptrArrayRemoveLast(ptrArray * const current)81 extern void *ptrArrayRemoveLast (ptrArray *const current)
82 {
83 Assert (current != NULL);
84 Assert (current->count > 0);
85 void *r = ptrArrayLast (current);
86 --current->count;
87 return r;
88 }
89
ptrArrayDeleteLastInBatch(ptrArray * const current,unsigned int count)90 extern void ptrArrayDeleteLastInBatch (ptrArray *const current, unsigned int count)
91 {
92 Assert (current != NULL);
93 Assert (current->count >= count);
94 while (count > 0)
95 {
96 void *r = ptrArrayLast (current);
97 if (current->deleteFunc)
98 current->deleteFunc (r);
99 --current->count;
100 --count;
101 }
102 }
103
104 /* Combine array `from' into `current', deleting `from' */
ptrArrayCombine(ptrArray * const current,ptrArray * const from)105 extern void ptrArrayCombine (ptrArray *const current, ptrArray *const from)
106 {
107 unsigned int i;
108 Assert (current != NULL);
109 Assert (from != NULL);
110 for (i = 0 ; i < from->count ; ++i)
111 ptrArrayAdd (current, from->array [i]);
112 from->count = 0;
113 ptrArrayDelete (from);
114 }
115
ptrArrayCount(const ptrArray * const current)116 extern unsigned int ptrArrayCount (const ptrArray *const current)
117 {
118 Assert (current != NULL);
119 return current->count;
120 }
121
ptrArrayItem(const ptrArray * const current,const unsigned int indx)122 extern void* ptrArrayItem (const ptrArray *const current, const unsigned int indx)
123 {
124 Assert (current != NULL);
125 Assert (current->count > indx);
126 return current->array [indx];
127 }
128
ptrArrayItemFromLast(const ptrArray * const current,const unsigned int indx)129 extern void* ptrArrayItemFromLast (const ptrArray *const current, const unsigned int indx)
130 {
131 Assert (current != NULL);
132 Assert (current->count > indx);
133 return current->array [current->count - 1 - indx];
134 }
135
ptrArrayClear(ptrArray * const current)136 extern void ptrArrayClear (ptrArray *const current)
137 {
138 Assert (current != NULL);
139 if (current->deleteFunc)
140 {
141 unsigned int i;
142 for (i = 0 ; i < current->count ; ++i)
143 current->deleteFunc (current->array [i]);
144 }
145 current->count = 0;
146 }
147
ptrArrayDelete(ptrArray * const current)148 extern void ptrArrayDelete (ptrArray *const current)
149 {
150 if (current != NULL)
151 {
152 ptrArrayClear (current);
153 eFree (current->array);
154 eFree (current);
155 }
156 }
157
ptrArrayHasTest(const ptrArray * const current,bool (* test)(const void * ptr,void * userData),void * userData)158 extern bool ptrArrayHasTest (const ptrArray *const current,
159 bool (*test)(const void *ptr, void *userData),
160 void *userData)
161 {
162 bool result = false;
163 unsigned int i;
164 Assert (current != NULL);
165 for (i = 0 ; ! result && i < current->count ; ++i)
166 result = (*test)(current->array [i], userData);
167 return result;
168 }
169
ptrEq(const void * ptr,void * userData)170 static bool ptrEq (const void *ptr, void *userData)
171 {
172 return (ptr == userData);
173 }
174
ptrArrayHas(const ptrArray * const current,void * ptr)175 extern bool ptrArrayHas (const ptrArray *const current, void *ptr)
176 {
177 return ptrArrayHasTest (current, ptrEq, ptr);
178 }
179
ptrArrayReverse(const ptrArray * const current)180 extern void ptrArrayReverse (const ptrArray *const current)
181 {
182 unsigned int i, j;
183 void *tmp;
184
185 Assert (current != NULL);
186 for (i = 0, j = current->count - 1 ; i < (current->count / 2); ++i, --j)
187 {
188 tmp = current->array[i];
189 current->array[i] = current->array[j];
190 current->array[j] = tmp;
191 }
192 }
193
ptrArrayDeleteItem(ptrArray * const current,unsigned int indx)194 extern void ptrArrayDeleteItem (ptrArray* const current, unsigned int indx)
195 {
196 void *ptr = current->array[indx];
197
198 if (current->deleteFunc)
199 current->deleteFunc (ptr);
200
201 memmove (current->array + indx, current->array + indx + 1,
202 (current->count - indx - 1) * sizeof (*current->array));
203 --current->count;
204 }
205
ptrArrayRemoveItem(ptrArray * const current,unsigned int indx)206 extern void*ptrArrayRemoveItem (ptrArray* const current, unsigned int indx)
207 {
208 void *ptr = current->array[indx];
209
210 memmove (current->array + indx, current->array + indx + 1,
211 (current->count - indx - 1) * sizeof (*current->array));
212 --current->count;
213
214 return ptr;
215 }
216
ptrArrayInsertItem(ptrArray * const current,unsigned int indx,void * ptr)217 extern void ptrArrayInsertItem (ptrArray* const current, unsigned int indx, void *ptr)
218 {
219 Assert (current != NULL);
220 if (current->count == current->max)
221 {
222 current->max *= 2;
223 current->array = xRealloc (current->array, current->max, void*);
224 }
225
226 memmove (current->array + indx + 1, current->array + indx,
227 (current->count - indx) * sizeof (*current->array));
228 current->array[indx] = ptr;
229 ++current->count;
230 }
231
232 static int (*ptrArraySortCompareVar)(const void *, const void *);
233
ptrArraySortCompare(const void * a0,const void * b0)234 static int ptrArraySortCompare(const void *a0, const void *b0)
235 {
236 void *const *a = (void *const *)a0;
237 void *const *b = (void *const *)b0;
238
239 return ptrArraySortCompareVar (*a, *b);
240 }
241
ptrArraySort(ptrArray * const current,int (* compare)(const void *,const void *))242 extern void ptrArraySort (ptrArray *const current, int (*compare)(const void *, const void *))
243 {
244 ptrArraySortCompareVar = compare;
245 qsort (current->array, current->count, sizeof (void *), ptrArraySortCompare);
246 }
247