Merge branch 'array'
[strongswan.git] / src / libstrongswan / collections / array.c
1 /*
2 * Copyright (C) 2013 Martin Willi
3 * Copyright (C) 2013 revosec AG
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; either version 2 of the License, or (at your
8 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * for more details.
14 */
15
16 #include "array.h"
17
18 /**
19 * Data is an allocated block, with potentially unused head and tail:
20 *
21 * "esize" each (or sizeof(void*) if esize = 0)
22 * /-\ /-\ /-\ /-\ /-\ /-\
23 *
24 * +---------------+-------------------------------+---------------+
25 * | h | e | a | d | e | l | e | m | e | n | t | s | t | a | i | l |
26 * +---------------+-------------------------------+---------------+
27 *
28 * \--------------/ \-----------------------------/ \-------------/
29 * unused used unused
30 * "head" "count" "tail"
31 *
32 */
33 struct array_t {
34 /** number of elements currently in array (not counting head/tail) */
35 u_int32_t count;
36 /** size of each element, 0 for a pointer based array */
37 u_int16_t esize;
38 /** allocated but unused elements at array front */
39 u_int8_t head;
40 /** allocated but unused elements at array end */
41 u_int8_t tail;
42 /** array elements */
43 void *data;
44 };
45
46 /** maximum number of unused head/tail elements before cleanup */
47 #define ARRAY_MAX_UNUSED 32
48
49 /**
50 * Get the actual size of a number of elements
51 */
52 static size_t get_size(array_t *array, int num)
53 {
54 if (array->esize)
55 {
56 return array->esize * num;
57 }
58 return sizeof(void*) * num;
59 }
60
61 /**
62 * Increase allocated but unused tail room to at least "room"
63 */
64 static void make_tail_room(array_t *array, u_int8_t room)
65 {
66 if (array->tail < room)
67 {
68 array->data = realloc(array->data,
69 get_size(array, array->count + array->head + room));
70 array->tail = room;
71 }
72 }
73
74 /**
75 * Increase allocated but unused head room to at least "room"
76 */
77 static void make_head_room(array_t *array, u_int8_t room)
78 {
79 if (array->head < room)
80 {
81 u_int8_t increase = room - array->head;
82
83 array->data = realloc(array->data,
84 get_size(array, array->count + array->tail + room));
85 memmove(array->data + get_size(array, increase), array->data,
86 get_size(array, array->count + array->tail + array->head));
87 array->head = room;
88 }
89 }
90
91 /**
92 * Make space for an item at index using tail room
93 */
94 static void insert_tail(array_t *array, int idx)
95 {
96 make_tail_room(array, 1);
97 /* move up all elements after idx by one */
98 memmove(array->data + get_size(array, array->head + idx + 1),
99 array->data + get_size(array, array->head + idx),
100 get_size(array, array->count - idx));
101
102 array->tail--;
103 array->count++;
104 }
105
106 /**
107 * Make space for an item at index using head room
108 */
109 static void insert_head(array_t *array, int idx)
110 {
111 make_head_room(array, 1);
112 /* move down all elements before idx by one */
113 memmove(array->data + get_size(array, array->head - 1),
114 array->data + get_size(array, array->head),
115 get_size(array, idx));
116
117 array->head--;
118 array->count++;
119 }
120
121 /**
122 * Remove an item, increase tail
123 */
124 static void remove_tail(array_t *array, int idx)
125 {
126 /* move all items after idx one down */
127 memmove(array->data + get_size(array, idx + array->head),
128 array->data + get_size(array, idx + array->head + 1),
129 get_size(array, array->count - idx));
130 array->count--;
131 array->tail++;
132 }
133
134 /**
135 * Remove an item, increase head
136 */
137 static void remove_head(array_t *array, int idx)
138 {
139 /* move all items before idx one up */
140 memmove(array->data + get_size(array, array->head + 1),
141 array->data + get_size(array, array->head), get_size(array, idx));
142 array->count--;
143 array->head++;
144 }
145
146 array_t *array_create(u_int esize, u_int8_t reserve)
147 {
148 array_t *array;
149
150 INIT(array,
151 .esize = esize,
152 .tail = reserve,
153 );
154 if (array->tail)
155 {
156 array->data = malloc(array->tail * array->esize);
157 }
158 return array;
159 }
160
161 int array_count(array_t *array)
162 {
163 if (array)
164 {
165 return array->count;
166 }
167 return 0;
168 }
169
170 void array_compress(array_t *array)
171 {
172 if (array)
173 {
174 u_int32_t tail;
175
176 tail = array->tail;
177 if (array->head)
178 {
179 memmove(array->data, array->data + get_size(array, array->head),
180 get_size(array, array->count + array->tail));
181 tail += array->head;
182 array->head = 0;
183 }
184 if (tail)
185 {
186 array->data = realloc(array->data, get_size(array, array->count));
187 array->tail = 0;
188 }
189 }
190 }
191
192 typedef struct {
193 /** public enumerator interface */
194 enumerator_t public;
195 /** enumerated array */
196 array_t *array;
197 /** current index +1, initialized at 0 */
198 int idx;
199 } array_enumerator_t;
200
201 METHOD(enumerator_t, enumerate, bool,
202 array_enumerator_t *this, void **out)
203 {
204 void *pos;
205
206 if (this->idx >= this->array->count)
207 {
208 return FALSE;
209 }
210
211 pos = this->array->data +
212 get_size(this->array, this->idx + this->array->head);
213 if (this->array->esize)
214 {
215 /* for element based arrays we return a pointer to the element */
216 *out = pos;
217 }
218 else
219 {
220 /* for pointer based arrays we return the pointer directly */
221 *out = *(void**)pos;
222 }
223 this->idx++;
224 return TRUE;
225 }
226
227 enumerator_t* array_create_enumerator(array_t *array)
228 {
229 array_enumerator_t *enumerator;
230
231 if (!array)
232 {
233 return enumerator_create_empty();
234 }
235
236 INIT(enumerator,
237 .public = {
238 .enumerate = (void*)_enumerate,
239 .destroy = (void*)free,
240 },
241 .array = array,
242 );
243 return &enumerator->public;
244 }
245
246 void array_remove_at(array_t *array, enumerator_t *public)
247 {
248 array_enumerator_t *enumerator = (array_enumerator_t*)public;
249
250 if (enumerator->idx)
251 {
252 array_remove(array, --enumerator->idx, NULL);
253 }
254 }
255
256 void array_insert_create(array_t **array, int idx, void *ptr)
257 {
258 if (*array == NULL)
259 {
260 *array = array_create(0, 0);
261 }
262 array_insert(*array, idx, ptr);
263 }
264
265 void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
266 {
267 void *ptr;
268
269 while (enumerator->enumerate(enumerator, &ptr))
270 {
271 array_insert(array, idx, ptr);
272 }
273 enumerator->destroy(enumerator);
274 }
275
276 void array_insert(array_t *array, int idx, void *data)
277 {
278 if (idx < 0 || idx <= array_count(array))
279 {
280 void *pos;
281
282 if (idx < 0)
283 {
284 idx = array_count(array);
285 }
286
287 if (array->head && !array->tail)
288 {
289 insert_head(array, idx);
290 }
291 else if (array->tail && !array->head)
292 {
293 insert_tail(array, idx);
294 }
295 else if (idx > array_count(array) / 2)
296 {
297 insert_tail(array, idx);
298 }
299 else
300 {
301 insert_head(array, idx);
302 }
303
304 pos = array->data + get_size(array, array->head + idx);
305 if (array->esize)
306 {
307 memcpy(pos, data, get_size(array, 1));
308 }
309 else
310 {
311 /* pointer based array, copy pointer value */
312 *(void**)pos = data;
313 }
314 }
315 }
316
317 bool array_remove(array_t *array, int idx, void *data)
318 {
319 if (!array)
320 {
321 return FALSE;
322 }
323 if (idx >= 0 && idx >= array_count(array))
324 {
325 return FALSE;
326 }
327 if (idx < 0)
328 {
329 if (array_count(array) == 0)
330 {
331 return FALSE;
332 }
333 idx = array_count(array) - 1;
334 }
335 if (data)
336 {
337 memcpy(data, array->data + get_size(array, array->head + idx),
338 get_size(array, 1));
339 }
340 if (idx > array_count(array) / 2)
341 {
342 remove_tail(array, idx);
343 }
344 else
345 {
346 remove_head(array, idx);
347 }
348 if (array->head + array->tail > ARRAY_MAX_UNUSED)
349 {
350 array_compress(array);
351 }
352 return TRUE;
353 }
354
355 void array_invoke(array_t *array, array_callback_t cb, void *user)
356 {
357 if (array)
358 {
359 void *obj;
360 int i;
361
362 for (i = array->head; i < array->count + array->head; i++)
363 {
364 obj = array->data + get_size(array, i);
365 if (!array->esize)
366 {
367 /* dereference if we store store pointers */
368 obj = *(void**)obj;
369 }
370 cb(obj, i - array->head, user);
371 }
372 }
373 }
374
375 void array_invoke_offset(array_t *array, size_t offset)
376 {
377 if (array)
378 {
379 void (*method)(void *data);
380 void *obj;
381 int i;
382
383 for (i = array->head; i < array->count + array->head; i++)
384 {
385 obj = array->data + get_size(array, i);
386 if (!array->esize)
387 {
388 /* dereference if we store store pointers */
389 obj = *(void**)obj;
390 }
391 method = *(void**)(obj + offset);
392 method(obj);
393 }
394 }
395 }
396
397 void array_destroy(array_t *array)
398 {
399 if (array)
400 {
401 free(array->data);
402 free(array);
403 }
404 }
405
406 void array_destroy_function(array_t *array, array_callback_t cb, void *user)
407 {
408 array_invoke(array, cb, user);
409 array_destroy(array);
410 }
411
412 void array_destroy_offset(array_t *array, size_t offset)
413 {
414 array_invoke_offset(array, offset);
415 array_destroy(array);
416 }