This source file includes following definitions.
- gl_array_nx_create_empty
- gl_array_size
- gl_array_indexof
- gl_array_search
- grow
- 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_map.h"
22
23 #include <stdint.h>
24 #include <stdlib.h>
25
26
27 #include "xsize.h"
28
29
30
31 struct pair
32 {
33 const void *key;
34 const void *value;
35 };
36
37
38 struct gl_map_impl
39 {
40 struct gl_map_impl_base base;
41
42
43 struct pair *pairs;
44 size_t count;
45 size_t allocated;
46 };
47
48 static gl_map_t
49 gl_array_nx_create_empty (gl_map_implementation_t implementation,
50 gl_mapkey_equals_fn equals_fn,
51 gl_mapkey_hashcode_fn hashcode_fn,
52 gl_mapkey_dispose_fn kdispose_fn,
53 gl_mapvalue_dispose_fn vdispose_fn)
54 {
55 struct gl_map_impl *map =
56 (struct gl_map_impl *) malloc (sizeof (struct gl_map_impl));
57
58 if (map == NULL)
59 return NULL;
60
61 map->base.vtable = implementation;
62 map->base.equals_fn = equals_fn;
63 map->base.kdispose_fn = kdispose_fn;
64 map->base.vdispose_fn = vdispose_fn;
65 map->pairs = NULL;
66 map->count = 0;
67 map->allocated = 0;
68
69 return map;
70 }
71
72 static size_t
73 gl_array_size (gl_map_t map)
74 {
75 return map->count;
76 }
77
78 static size_t
79 gl_array_indexof (gl_map_t map, const void *key)
80 {
81 size_t count = map->count;
82
83 if (count > 0)
84 {
85 gl_mapkey_equals_fn equals = map->base.equals_fn;
86 if (equals != NULL)
87 {
88 size_t i;
89
90 for (i = 0; i < count; i++)
91 if (equals (map->pairs[i].key, key))
92 return i;
93 }
94 else
95 {
96 size_t i;
97
98 for (i = 0; i < count; i++)
99 if (map->pairs[i].key == key)
100 return i;
101 }
102 }
103 return (size_t)(-1);
104 }
105
106 static bool
107 gl_array_search (gl_map_t map, const void *key, const void **valuep)
108 {
109 size_t index = gl_array_indexof (map, key);
110 if (index != (size_t)(-1))
111 {
112 *valuep = map->pairs[index].value;
113 return true;
114 }
115 else
116 return false;
117 }
118
119
120
121 static int
122 grow (gl_map_t map)
123 {
124 size_t new_allocated;
125 size_t memory_size;
126 struct pair *memory;
127
128 new_allocated = xtimes (map->allocated, 2);
129 new_allocated = xsum (new_allocated, 1);
130 memory_size = xtimes (new_allocated, sizeof (struct pair));
131 if (size_overflow_p (memory_size))
132
133 return -1;
134 memory = (struct pair *) realloc (map->pairs, memory_size);
135 if (memory == NULL)
136
137 return -1;
138 map->pairs = memory;
139 map->allocated = new_allocated;
140 return 0;
141 }
142
143 static int
144 gl_array_nx_getput (gl_map_t map, const void *key, const void *value,
145 const void **oldvaluep)
146 {
147 size_t index = gl_array_indexof (map, key);
148 if (index != (size_t)(-1))
149 {
150 *oldvaluep = map->pairs[index].value;
151 map->pairs[index].value = value;
152 return 0;
153 }
154 else
155 {
156 size_t count = map->count;
157 struct pair *pairs;
158
159 if (count == map->allocated)
160 if (grow (map) < 0)
161 return -1;
162 pairs = map->pairs;
163 pairs[count].key = key;
164 pairs[count].value = value;
165 map->count = count + 1;
166 return 1;
167 }
168 }
169
170
171
172 static void
173 gl_array_remove_at (gl_map_t map, size_t position)
174 {
175 size_t count = map->count;
176 struct pair *pairs;
177 size_t i;
178
179 pairs = map->pairs;
180 if (map->base.kdispose_fn != NULL)
181 map->base.kdispose_fn (pairs[position].key);
182 for (i = position + 1; i < count; i++)
183 pairs[i - 1] = pairs[i];
184 map->count = count - 1;
185 }
186
187 static bool
188 gl_array_getremove (gl_map_t map, const void *key, const void **oldvaluep)
189 {
190 size_t index = gl_array_indexof (map, key);
191 if (index != (size_t)(-1))
192 {
193 *oldvaluep = map->pairs[index].value;
194 gl_array_remove_at (map, index);
195 return true;
196 }
197 else
198 return false;
199 }
200
201 static void
202 gl_array_free (gl_map_t map)
203 {
204 if (map->pairs != NULL)
205 {
206 if (map->base.kdispose_fn != NULL || map->base.vdispose_fn != NULL)
207 {
208 size_t count = map->count;
209
210 if (count > 0)
211 {
212 gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
213 gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
214 struct pair *pairs = map->pairs;
215
216 do
217 {
218 if (vdispose)
219 vdispose (pairs->value);
220 if (kdispose)
221 kdispose (pairs->key);
222 pairs++;
223 }
224 while (--count > 0);
225 }
226 }
227 free (map->pairs);
228 }
229 free (map);
230 }
231
232
233
234 static gl_map_iterator_t
235 gl_array_iterator (gl_map_t map)
236 {
237 gl_map_iterator_t result;
238
239 result.vtable = map->base.vtable;
240 result.map = map;
241 result.count = map->count;
242 result.p = map->pairs + 0;
243 result.q = map->pairs + map->count;
244 #if defined GCC_LINT || defined lint
245 result.i = 0;
246 result.j = 0;
247 #endif
248
249 return result;
250 }
251
252 static bool
253 gl_array_iterator_next (gl_map_iterator_t *iterator,
254 const void **keyp, const void **valuep)
255 {
256 gl_map_t map = iterator->map;
257 if (iterator->count != map->count)
258 {
259 if (iterator->count != map->count + 1)
260
261 abort ();
262
263 iterator->count--;
264 iterator->p = (struct pair *) iterator->p - 1;
265 iterator->q = (struct pair *) iterator->q - 1;
266 }
267 if (iterator->p < iterator->q)
268 {
269 struct pair *p = (struct pair *) iterator->p;
270 *keyp = p->key;
271 *valuep = p->value;
272 iterator->p = p + 1;
273 return true;
274 }
275 else
276 return false;
277 }
278
279 static void
280 gl_array_iterator_free (gl_map_iterator_t *iterator)
281 {
282 }
283
284
285 const struct gl_map_implementation gl_array_map_implementation =
286 {
287 gl_array_nx_create_empty,
288 gl_array_size,
289 gl_array_search,
290 gl_array_nx_getput,
291 gl_array_getremove,
292 gl_array_free,
293 gl_array_iterator,
294 gl_array_iterator_next,
295 gl_array_iterator_free
296 };