array: Allocate initial data properly if esize is 0
[strongswan.git] / src / libstrongswan / collections / array.c
1 /*
2 * Copyright (C) 2014 Tobias Brunner
3 * Hochschule fuer Technik Rapperswil
4 *
5 * Copyright (C) 2013 Martin Willi
6 * Copyright (C) 2013 revosec AG
7 *
8 * This program is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2 of the License, or (at your
11 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 * for more details.
17 */
18
19 #define _GNU_SOURCE /* for qsort_r() */
20 #include <stdlib.h>
21
22 #include "array.h"
23
24 #ifndef HAVE_QSORT_R
25 #include <threading/thread_value.h>
26 #endif
27
28 /**
29 * Data is an allocated block, with potentially unused head and tail:
30 *
31 * "esize" each (or sizeof(void*) if esize = 0)
32 * /-\ /-\ /-\ /-\ /-\ /-\
33 *
34 * +---------------+-------------------------------+---------------+
35 * | h | e | a | d | e | l | e | m | e | n | t | s | t | a | i | l |
36 * +---------------+-------------------------------+---------------+
37 *
38 * \--------------/ \-----------------------------/ \-------------/
39 * unused used unused
40 * "head" "count" "tail"
41 *
42 */
43 struct array_t {
44 /** number of elements currently in array (not counting head/tail) */
45 u_int32_t count;
46 /** size of each element, 0 for a pointer based array */
47 u_int16_t esize;
48 /** allocated but unused elements at array front */
49 u_int8_t head;
50 /** allocated but unused elements at array end */
51 u_int8_t tail;
52 /** array elements */
53 void *data;
54 };
55
56 #ifndef HAVE_QSORT_R
57 /* store data to replicate qsort_r in thread local storage */
58 static thread_value_t *sort_data;
59 #endif
60
61 /** maximum number of unused head/tail elements before cleanup */
62 #define ARRAY_MAX_UNUSED 32
63
64 /**
65 * Get the actual size of a number of elements
66 */
67 static size_t get_size(array_t *array, u_int32_t num)
68 {
69 if (array->esize)
70 {
71 return array->esize * num;
72 }
73 return sizeof(void*) * num;
74 }
75
76 /**
77 * Increase allocated but unused tail room to at least "room"
78 */
79 static void make_tail_room(array_t *array, u_int8_t room)
80 {
81 if (array->tail < room)
82 {
83 array->data = realloc(array->data,
84 get_size(array, array->count + array->head + room));
85 array->tail = room;
86 }
87 }
88
89 /**
90 * Increase allocated but unused head room to at least "room"
91 */
92 static void make_head_room(array_t *array, u_int8_t room)
93 {
94 if (array->head < room)
95 {
96 u_int8_t increase = room - array->head;
97
98 array->data = realloc(array->data,
99 get_size(array, array->count + array->tail + room));
100 memmove(array->data + get_size(array, increase), array->data,
101 get_size(array, array->count + array->tail + array->head));
102 array->head = room;
103 }
104 }
105
106 /**
107 * Make space for an item at index using tail room
108 */
109 static void insert_tail(array_t *array, int idx)
110 {
111 make_tail_room(array, 1);
112 /* move up all elements after idx by one */
113 memmove(array->data + get_size(array, array->head + idx + 1),
114 array->data + get_size(array, array->head + idx),
115 get_size(array, array->count - idx));
116
117 array->tail--;
118 array->count++;
119 }
120
121 /**
122 * Make space for an item at index using head room
123 */
124 static void insert_head(array_t *array, int idx)
125 {
126 make_head_room(array, 1);
127 /* move down all elements before idx by one */
128 memmove(array->data + get_size(array, array->head - 1),
129 array->data + get_size(array, array->head),
130 get_size(array, idx));
131
132 array->head--;
133 array->count++;
134 }
135
136 /**
137 * Remove an item, increase tail
138 */
139 static void remove_tail(array_t *array, int idx)
140 {
141 /* move all items after idx one down */
142 memmove(array->data + get_size(array, idx + array->head),
143 array->data + get_size(array, idx + array->head + 1),
144 get_size(array, array->count - 1 - idx));
145 array->count--;
146 array->tail++;
147 }
148
149 /**
150 * Remove an item, increase head
151 */
152 static void remove_head(array_t *array, int idx)
153 {
154 /* move all items before idx one up */
155 memmove(array->data + get_size(array, array->head + 1),
156 array->data + get_size(array, array->head), get_size(array, idx));
157 array->count--;
158 array->head++;
159 }
160
161 array_t *array_create(u_int esize, u_int8_t reserve)
162 {
163 array_t *array;
164
165 INIT(array,
166 .esize = esize,
167 .tail = reserve,
168 );
169 if (array->tail)
170 {
171 array->data = malloc(get_size(array, array->tail));
172 }
173 return array;
174 }
175
176 int array_count(array_t *array)
177 {
178 if (array)
179 {
180 return array->count;
181 }
182 return 0;
183 }
184
185 void array_compress(array_t *array)
186 {
187 if (array)
188 {
189 u_int32_t tail;
190
191 tail = array->tail;
192 if (array->head)
193 {
194 memmove(array->data, array->data + get_size(array, array->head),
195 get_size(array, array->count + array->tail));
196 tail += array->head;
197 array->head = 0;
198 }
199 if (tail)
200 {
201 array->data = realloc(array->data, get_size(array, array->count));
202 array->tail = 0;
203 }
204 }
205 }
206
207 typedef struct {
208 /** public enumerator interface */
209 enumerator_t public;
210 /** enumerated array */
211 array_t *array;
212 /** current index +1, initialized at 0 */
213 int idx;
214 } array_enumerator_t;
215
216 METHOD(enumerator_t, enumerate, bool,
217 array_enumerator_t *this, void **out)
218 {
219 void *pos;
220
221 if (this->idx >= this->array->count)
222 {
223 return FALSE;
224 }
225
226 pos = this->array->data +
227 get_size(this->array, this->idx + this->array->head);
228 if (this->array->esize)
229 {
230 /* for element based arrays we return a pointer to the element */
231 *out = pos;
232 }
233 else
234 {
235 /* for pointer based arrays we return the pointer directly */
236 *out = *(void**)pos;
237 }
238 this->idx++;
239 return TRUE;
240 }
241
242 enumerator_t* array_create_enumerator(array_t *array)
243 {
244 array_enumerator_t *enumerator;
245
246 if (!array)
247 {
248 return enumerator_create_empty();
249 }
250
251 INIT(enumerator,
252 .public = {
253 .enumerate = (void*)_enumerate,
254 .destroy = (void*)free,
255 },
256 .array = array,
257 );
258 return &enumerator->public;
259 }
260
261 void array_remove_at(array_t *array, enumerator_t *public)
262 {
263 array_enumerator_t *enumerator = (array_enumerator_t*)public;
264
265 if (enumerator->idx)
266 {
267 array_remove(array, --enumerator->idx, NULL);
268 }
269 }
270
271 void array_insert_create(array_t **array, int idx, void *ptr)
272 {
273 if (*array == NULL)
274 {
275 *array = array_create(0, 0);
276 }
277 array_insert(*array, idx, ptr);
278 }
279
280 void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
281 {
282 void *ptr;
283
284 while (enumerator->enumerate(enumerator, &ptr))
285 {
286 array_insert(array, idx, ptr);
287 }
288 enumerator->destroy(enumerator);
289 }
290
291 void array_insert(array_t *array, int idx, void *data)
292 {
293 if (idx < 0 || idx <= array_count(array))
294 {
295 void *pos;
296
297 if (idx < 0)
298 {
299 idx = array_count(array);
300 }
301
302 if (array->head && !array->tail)
303 {
304 insert_head(array, idx);
305 }
306 else if (array->tail && !array->head)
307 {
308 insert_tail(array, idx);
309 }
310 else if (idx > array_count(array) / 2)
311 {
312 insert_tail(array, idx);
313 }
314 else
315 {
316 insert_head(array, idx);
317 }
318
319 pos = array->data + get_size(array, array->head + idx);
320 if (array->esize)
321 {
322 memcpy(pos, data, get_size(array, 1));
323 }
324 else
325 {
326 /* pointer based array, copy pointer value */
327 *(void**)pos = data;
328 }
329 }
330 }
331
332 bool array_get(array_t *array, int idx, void *data)
333 {
334 if (!array)
335 {
336 return FALSE;
337 }
338 if (idx >= 0 && idx >= array_count(array))
339 {
340 return FALSE;
341 }
342 if (idx < 0)
343 {
344 if (array_count(array) == 0)
345 {
346 return FALSE;
347 }
348 idx = array_count(array) - 1;
349 }
350 if (data)
351 {
352 memcpy(data, array->data + get_size(array, array->head + idx),
353 get_size(array, 1));
354 }
355 return TRUE;
356 }
357
358 bool array_remove(array_t *array, int idx, void *data)
359 {
360 if (!array_get(array, idx, data))
361 {
362 return FALSE;
363 }
364 if (idx > array_count(array) / 2)
365 {
366 remove_tail(array, idx);
367 }
368 else
369 {
370 if (idx < 0)
371 {
372 idx = array_count(array) - 1;
373 }
374 remove_head(array, idx);
375 }
376 if (array->head + array->tail > ARRAY_MAX_UNUSED)
377 {
378 array_compress(array);
379 }
380 return TRUE;
381 }
382
383 typedef struct {
384 /** the array */
385 array_t *array;
386 /** comparison function */
387 int (*cmp)(const void*,const void*,void*);
388 /** optional user arg */
389 void *arg;
390 } sort_data_t;
391
392 #ifdef HAVE_QSORT_R_GNU
393 static int compare_elements(const void *a, const void *b, void *arg)
394 #elif defined(HAVE_QSORT_R_BSD)
395 static int compare_elements(void *arg, const void *a, const void *b)
396 #else /* !HAVE_QSORT_R */
397 static int compare_elements(const void *a, const void *b)
398 #endif
399 {
400 #ifdef HAVE_QSORT_R
401 sort_data_t *data = (sort_data_t*)arg;
402 #else
403 sort_data_t *data = sort_data->get(sort_data);
404 #endif
405
406 if (data->array->esize)
407 {
408 return data->cmp(a, b, data->arg);
409 }
410 return data->cmp(*(void**)a, *(void**)b, data->arg);
411 }
412
413 void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
414 void *user)
415 {
416 if (array)
417 {
418 sort_data_t data = {
419 .array = array,
420 .cmp = cmp,
421 .arg = user,
422 };
423 void *start;
424
425 start = array->data + get_size(array, array->head);
426
427 #ifdef HAVE_QSORT_R_GNU
428 qsort_r(start, array->count, get_size(array, 1), compare_elements,
429 &data);
430 #elif defined(HAVE_QSORT_R_BSD)
431 qsort_r(start, array->count, get_size(array, 1), &data,
432 compare_elements);
433 #else /* !HAVE_QSORT_R */
434 sort_data->set(sort_data, &data);
435 qsort(start, array->count, get_size(array, 1), compare_elements);
436 #endif
437 }
438 }
439
440 typedef struct {
441 /** the array */
442 array_t *array;
443 /** the key */
444 const void *key;
445 /** comparison function */
446 int (*cmp)(const void*,const void*);
447 } bsearch_data_t;
448
449 static int search_elements(const void *a, const void *b)
450 {
451 bsearch_data_t *data = (bsearch_data_t*)a;
452
453 if (data->array->esize)
454 {
455 return data->cmp(data->key, b);
456 }
457 return data->cmp(data->key, *(void**)b);
458 }
459
460 int array_bsearch(array_t *array, const void *key,
461 int (*cmp)(const void*,const void*), void *out)
462 {
463 int idx = -1;
464
465 if (array)
466 {
467 bsearch_data_t data = {
468 .array = array,
469 .key = key,
470 .cmp = cmp,
471 };
472 void *start, *item;
473
474 start = array->data + get_size(array, array->head);
475
476 item = bsearch(&data, start, array->count, get_size(array, 1),
477 search_elements);
478 if (item)
479 {
480 if (out)
481 {
482 memcpy(out, item, get_size(array, 1));
483 }
484 idx = (item - start) / get_size(array, 1);
485 }
486 }
487 return idx;
488 }
489
490 void array_invoke(array_t *array, array_callback_t cb, void *user)
491 {
492 if (array)
493 {
494 void *obj;
495 int i;
496
497 for (i = array->head; i < array->count + array->head; i++)
498 {
499 obj = array->data + get_size(array, i);
500 if (!array->esize)
501 {
502 /* dereference if we store store pointers */
503 obj = *(void**)obj;
504 }
505 cb(obj, i - array->head, user);
506 }
507 }
508 }
509
510 void array_invoke_offset(array_t *array, size_t offset)
511 {
512 if (array)
513 {
514 void (*method)(void *data);
515 void *obj;
516 int i;
517
518 for (i = array->head; i < array->count + array->head; i++)
519 {
520 obj = array->data + get_size(array, i);
521 if (!array->esize)
522 {
523 /* dereference if we store store pointers */
524 obj = *(void**)obj;
525 }
526 method = *(void**)(obj + offset);
527 method(obj);
528 }
529 }
530 }
531
532 void array_destroy(array_t *array)
533 {
534 if (array)
535 {
536 free(array->data);
537 free(array);
538 }
539 }
540
541 void array_destroy_function(array_t *array, array_callback_t cb, void *user)
542 {
543 array_invoke(array, cb, user);
544 array_destroy(array);
545 }
546
547 void array_destroy_offset(array_t *array, size_t offset)
548 {
549 array_invoke_offset(array, offset);
550 array_destroy(array);
551 }
552
553 void arrays_init()
554 {
555 #ifndef HAVE_QSORT_R
556 sort_data = thread_value_create(NULL);
557 #endif
558 }
559
560 void arrays_deinit()
561 {
562 #ifndef HAVE_QSORT_R
563 sort_data->destroy(sort_data);
564 #endif
565 }