This source file includes following definitions.
- gl_array_nx_create_empty
- gl_array_size
- gl_array_indexof
- gl_array_search
- gl_array_search_atleast
- grow
- gl_array_nx_add_at
- gl_array_nx_getput
- gl_array_remove_at
- gl_array_getremove
- gl_array_free
- gl_array_iterator
- gl_array_iterator_next
- gl_array_iterator_free
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #include <config.h>
19
20
21 #include "gl_array_omap.h"
22
23 #include <stdlib.h>
24
25
26 #include "xsize.h"
27
28
29
30 struct pair
31 {
32 const void *key;
33 const void *value;
34 };
35
36
37 struct gl_omap_impl
38 {
39 struct gl_omap_impl_base base;
40
41
42 struct pair *pairs;
43 size_t count;
44 size_t allocated;
45 };
46
47 static gl_omap_t
48 gl_array_nx_create_empty (gl_omap_implementation_t implementation,
49 gl_mapkey_compar_fn compar_fn,
50 gl_mapkey_dispose_fn kdispose_fn,
51 gl_mapvalue_dispose_fn vdispose_fn)
52 {
53 struct gl_omap_impl *map =
54 (struct gl_omap_impl *) malloc (sizeof (struct gl_omap_impl));
55
56 if (map == NULL)
57 return NULL;
58
59 map->base.vtable = implementation;
60 map->base.compar_fn = compar_fn;
61 map->base.kdispose_fn = kdispose_fn;
62 map->base.vdispose_fn = vdispose_fn;
63 map->pairs = NULL;
64 map->count = 0;
65 map->allocated = 0;
66
67 return map;
68 }
69
70 static size_t _GL_ATTRIBUTE_PURE
71 gl_array_size (gl_omap_t map)
72 {
73 return map->count;
74 }
75
76 static size_t _GL_ATTRIBUTE_PURE
77 gl_array_indexof (gl_omap_t map, const void *key)
78 {
79 size_t count = map->count;
80
81 if (count > 0)
82 {
83 gl_mapkey_compar_fn compar = map->base.compar_fn;
84 size_t low = 0;
85 size_t high = count;
86
87
88
89
90
91 do
92 {
93 size_t mid = low + (high - low) / 2;
94 int cmp = (compar != NULL
95 ? compar (map->pairs[mid].key, key)
96 : (map->pairs[mid].key > key ? 1 :
97 map->pairs[mid].key < key ? -1 : 0));
98
99 if (cmp < 0)
100 low = mid + 1;
101 else if (cmp > 0)
102 high = mid;
103 else
104
105 return mid;
106 }
107 while (low < high);
108 }
109 return (size_t)(-1);
110 }
111
112 static bool _GL_ATTRIBUTE_PURE
113 gl_array_search (gl_omap_t map, const void *key, const void **valuep)
114 {
115 size_t index = gl_array_indexof (map, key);
116 if (index != (size_t)(-1))
117 {
118 *valuep = map->pairs[index].value;
119 return true;
120 }
121 else
122 return false;
123 }
124
125 static bool _GL_ATTRIBUTE_PURE
126 gl_array_search_atleast (gl_omap_t map,
127 gl_mapkey_threshold_fn threshold_fn,
128 const void *threshold,
129 const void **keyp, const void **valuep)
130 {
131 size_t count = map->count;
132
133 if (count > 0)
134 {
135 size_t low = 0;
136 size_t high = count;
137
138
139
140
141
142 do
143 {
144 size_t mid = low + (high - low) / 2;
145
146 if (! threshold_fn (map->pairs[mid].key, threshold))
147 low = mid + 1;
148 else
149 {
150
151
152 high = mid;
153
154
155
156
157 while (low < high)
158 {
159 size_t mid2 = low + (high - low) / 2;
160
161 if (! threshold_fn (map->pairs[mid2].key, threshold))
162 low = mid2 + 1;
163 else
164 high = mid2;
165 }
166 *keyp = map->pairs[low].key;
167 *valuep = map->pairs[low].value;
168 return true;
169 }
170 }
171 while (low < high);
172 }
173 return false;
174 }
175
176
177
178 static int
179 grow (gl_omap_t map)
180 {
181 size_t new_allocated;
182 size_t memory_size;
183 struct pair *memory;
184
185 new_allocated = xtimes (map->allocated, 2);
186 new_allocated = xsum (new_allocated, 1);
187 memory_size = xtimes (new_allocated, sizeof (struct pair));
188 if (size_overflow_p (memory_size))
189
190 return -1;
191 memory = (struct pair *) realloc (map->pairs, memory_size);
192 if (memory == NULL)
193
194 return -1;
195 map->pairs = memory;
196 map->allocated = new_allocated;
197 return 0;
198 }
199
200
201
202
203 static int
204 gl_array_nx_add_at (gl_omap_t map, size_t position,
205 const void *key, const void *value)
206 {
207 size_t count = map->count;
208 struct pair *pairs;
209 size_t i;
210
211 if (count == map->allocated)
212 if (grow (map) < 0)
213 return -1;
214 pairs = map->pairs;
215 for (i = count; i > position; i--)
216 pairs[i] = pairs[i - 1];
217 pairs[position].key = key;
218 pairs[position].value = value;
219 map->count = count + 1;
220 return 1;
221 }
222
223 static int
224 gl_array_nx_getput (gl_omap_t map, const void *key, const void *value,
225 const void **oldvaluep)
226 {
227 size_t count = map->count;
228 size_t low = 0;
229
230 if (count > 0)
231 {
232 gl_mapkey_compar_fn compar = map->base.compar_fn;
233 size_t high = count;
234
235
236
237
238
239 do
240 {
241 size_t mid = low + (high - low) / 2;
242 int cmp = (compar != NULL
243 ? compar (map->pairs[mid].key, key)
244 : (map->pairs[mid].key > key ? 1 :
245 map->pairs[mid].key < key ? -1 : 0));
246
247 if (cmp < 0)
248 low = mid + 1;
249 else if (cmp > 0)
250 high = mid;
251 else
252 {
253 *oldvaluep = map->pairs[mid].value;
254 map->pairs[mid].value = value;
255 return 0;
256 }
257 }
258 while (low < high);
259 }
260 return gl_array_nx_add_at (map, low, key, value);
261 }
262
263
264
265 static void
266 gl_array_remove_at (gl_omap_t map, size_t position)
267 {
268 size_t count = map->count;
269 struct pair *pairs;
270 size_t i;
271
272 pairs = map->pairs;
273 if (map->base.kdispose_fn != NULL)
274 map->base.kdispose_fn (pairs[position].key);
275 for (i = position + 1; i < count; i++)
276 pairs[i - 1] = pairs[i];
277 map->count = count - 1;
278 }
279
280 static bool
281 gl_array_getremove (gl_omap_t map, const void *key, const void **oldvaluep)
282 {
283 size_t index = gl_array_indexof (map, key);
284 if (index != (size_t)(-1))
285 {
286 *oldvaluep = map->pairs[index].value;
287 gl_array_remove_at (map, index);
288 return true;
289 }
290 else
291 return false;
292 }
293
294 static void
295 gl_array_free (gl_omap_t map)
296 {
297 if (map->pairs != NULL)
298 {
299 if (map->base.kdispose_fn != NULL || map->base.vdispose_fn != NULL)
300 {
301 size_t count = map->count;
302
303 if (count > 0)
304 {
305 gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
306 gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
307 struct pair *pairs = map->pairs;
308
309 do
310 {
311 if (vdispose)
312 vdispose (pairs->value);
313 if (kdispose)
314 kdispose (pairs->key);
315 pairs++;
316 }
317 while (--count > 0);
318 }
319 }
320 free (map->pairs);
321 }
322 free (map);
323 }
324
325
326
327 static gl_omap_iterator_t _GL_ATTRIBUTE_PURE
328 gl_array_iterator (gl_omap_t map)
329 {
330 gl_omap_iterator_t result;
331
332 result.vtable = map->base.vtable;
333 result.map = map;
334 result.count = map->count;
335 result.p = map->pairs + 0;
336 result.q = map->pairs + map->count;
337 #if defined GCC_LINT || defined lint
338 result.i = 0;
339 result.j = 0;
340 #endif
341
342 return result;
343 }
344
345 static bool
346 gl_array_iterator_next (gl_omap_iterator_t *iterator,
347 const void **keyp, const void **valuep)
348 {
349 gl_omap_t map = iterator->map;
350 if (iterator->count != map->count)
351 {
352 if (iterator->count != map->count + 1)
353
354 abort ();
355
356 iterator->count--;
357 iterator->p = (struct pair *) iterator->p - 1;
358 iterator->q = (struct pair *) iterator->q - 1;
359 }
360 if (iterator->p < iterator->q)
361 {
362 struct pair *p = (struct pair *) iterator->p;
363 *keyp = p->key;
364 *valuep = p->value;
365 iterator->p = p + 1;
366 return true;
367 }
368 else
369 return false;
370 }
371
372 static void
373 gl_array_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_omap_iterator_t *iterator)
374 {
375 }
376
377
378 const struct gl_omap_implementation gl_array_omap_implementation =
379 {
380 gl_array_nx_create_empty,
381 gl_array_size,
382 gl_array_search,
383 gl_array_search_atleast,
384 gl_array_nx_getput,
385 gl_array_getremove,
386 gl_array_free,
387 gl_array_iterator,
388 gl_array_iterator_next,
389 gl_array_iterator_free
390 };