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