botan: Add support for Ed25519 keys
[strongswan.git] / src / libstrongswan / collections / array.c
1 /*
2 * Copyright (C) 2014 Tobias Brunner
3 * HSR 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 uint32_t count;
46 /** size of each element, 0 for a pointer based array */
47 uint16_t esize;
48 /** allocated but unused elements at array front */
49 uint8_t head;
50 /** allocated but unused elements at array end */
51 uint8_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, uint32_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, uint8_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, uint8_t room)
93 {
94 if (array->head < room)
95 {
96 uint8_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, uint8_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 uint32_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, va_list args)
218 {
219 void *pos, **out;
220
221 VA_ARGS_VGET(args, out);
222
223 if (this->idx >= this->array->count)
224 {
225 return FALSE;
226 }
227
228 pos = this->array->data +
229 get_size(this->array, this->idx + this->array->head);
230 if (this->array->esize)
231 {
232 /* for element based arrays we return a pointer to the element */
233 *out = pos;
234 }
235 else
236 {
237 /* for pointer based arrays we return the pointer directly */
238 *out = *(void**)pos;
239 }
240 this->idx++;
241 return TRUE;
242 }
243
244 enumerator_t* array_create_enumerator(array_t *array)
245 {
246 array_enumerator_t *enumerator;
247
248 if (!array)
249 {
250 return enumerator_create_empty();
251 }
252
253 INIT(enumerator,
254 .public = {
255 .enumerate = enumerator_enumerate_default,
256 .venumerate = _enumerate,
257 .destroy = (void*)free,
258 },
259 .array = array,
260 );
261 return &enumerator->public;
262 }
263
264 void array_remove_at(array_t *array, enumerator_t *public)
265 {
266 array_enumerator_t *enumerator = (array_enumerator_t*)public;
267
268 if (enumerator->idx)
269 {
270 array_remove(array, --enumerator->idx, NULL);
271 }
272 }
273
274 void array_insert_create(array_t **array, int idx, void *ptr)
275 {
276 if (*array == NULL)
277 {
278 *array = array_create(0, 0);
279 }
280 array_insert(*array, idx, ptr);
281 }
282
283 void array_insert_create_value(array_t **array, u_int esize,
284 int idx, void *val)
285 {
286 if (*array == NULL)
287 {
288 *array = array_create(esize, 0);
289 }
290 array_insert(*array, idx, val);
291 }
292
293 void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
294 {
295 void *ptr;
296
297 while (enumerator->enumerate(enumerator, &ptr))
298 {
299 array_insert(array, idx, ptr);
300 }
301 enumerator->destroy(enumerator);
302 }
303
304 void array_insert(array_t *array, int idx, void *data)
305 {
306 if (idx < 0 || idx <= array_count(array))
307 {
308 void *pos;
309
310 if (idx < 0)
311 {
312 idx = array_count(array);
313 }
314
315 if (array->head && !array->tail)
316 {
317 insert_head(array, idx);
318 }
319 else if (array->tail && !array->head)
320 {
321 insert_tail(array, idx);
322 }
323 else if (idx > array_count(array) / 2)
324 {
325 insert_tail(array, idx);
326 }
327 else
328 {
329 insert_head(array, idx);
330 }
331
332 pos = array->data + get_size(array, array->head + idx);
333 if (array->esize)
334 {
335 memcpy(pos, data, get_size(array, 1));
336 }
337 else
338 {
339 /* pointer based array, copy pointer value */
340 *(void**)pos = data;
341 }
342 }
343 }
344
345 bool array_get(array_t *array, int idx, void *data)
346 {
347 if (!array)
348 {
349 return FALSE;
350 }
351 if (idx >= 0 && idx >= array_count(array))
352 {
353 return FALSE;
354 }
355 if (idx < 0)
356 {
357 if (array_count(array) == 0)
358 {
359 return FALSE;
360 }
361 idx = array_count(array) - 1;
362 }
363 if (data)
364 {
365 memcpy(data, array->data + get_size(array, array->head + idx),
366 get_size(array, 1));
367 }
368 return TRUE;
369 }
370
371 bool array_remove(array_t *array, int idx, void *data)
372 {
373 if (!array_get(array, idx, data))
374 {
375 return FALSE;
376 }
377 if (idx < 0)
378 {
379 idx = array_count(array) - 1;
380 }
381 if (idx > array_count(array) / 2)
382 {
383 remove_tail(array, idx);
384 }
385 else
386 {
387 remove_head(array, idx);
388 }
389 if (array->head + array->tail > ARRAY_MAX_UNUSED)
390 {
391 array_compress(array);
392 }
393 return TRUE;
394 }
395
396 typedef struct {
397 /** the array */
398 array_t *array;
399 /** comparison function */
400 int (*cmp)(const void*,const void*,void*);
401 /** optional user arg */
402 void *arg;
403 } sort_data_t;
404
405 #ifdef HAVE_QSORT_R_GNU
406 static int compare_elements(const void *a, const void *b, void *arg)
407 #elif defined(HAVE_QSORT_R_BSD)
408 static int compare_elements(void *arg, const void *a, const void *b)
409 #else /* !HAVE_QSORT_R */
410 static int compare_elements(const void *a, const void *b)
411 #endif
412 {
413 #ifdef HAVE_QSORT_R
414 sort_data_t *data = (sort_data_t*)arg;
415 #else
416 sort_data_t *data = sort_data->get(sort_data);
417 #endif
418
419 if (data->array->esize)
420 {
421 return data->cmp(a, b, data->arg);
422 }
423 return data->cmp(*(void**)a, *(void**)b, data->arg);
424 }
425
426 void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
427 void *user)
428 {
429 if (array)
430 {
431 sort_data_t data = {
432 .array = array,
433 .cmp = cmp,
434 .arg = user,
435 };
436 void *start;
437
438 start = array->data + get_size(array, array->head);
439
440 #ifdef HAVE_QSORT_R_GNU
441 qsort_r(start, array->count, get_size(array, 1), compare_elements,
442 &data);
443 #elif defined(HAVE_QSORT_R_BSD)
444 qsort_r(start, array->count, get_size(array, 1), &data,
445 compare_elements);
446 #else /* !HAVE_QSORT_R */
447 sort_data->set(sort_data, &data);
448 qsort(start, array->count, get_size(array, 1), compare_elements);
449 #endif
450 }
451 }
452
453 typedef struct {
454 /** the array */
455 array_t *array;
456 /** the key */
457 const void *key;
458 /** comparison function */
459 int (*cmp)(const void*,const void*);
460 } bsearch_data_t;
461
462 static int search_elements(const void *a, const void *b)
463 {
464 bsearch_data_t *data = (bsearch_data_t*)a;
465
466 if (data->array->esize)
467 {
468 return data->cmp(data->key, b);
469 }
470 return data->cmp(data->key, *(void**)b);
471 }
472
473 int array_bsearch(array_t *array, const void *key,
474 int (*cmp)(const void*,const void*), void *out)
475 {
476 int idx = -1;
477
478 if (array)
479 {
480 bsearch_data_t data = {
481 .array = array,
482 .key = key,
483 .cmp = cmp,
484 };
485 void *start, *item;
486
487 start = array->data + get_size(array, array->head);
488
489 item = bsearch(&data, start, array->count, get_size(array, 1),
490 search_elements);
491 if (item)
492 {
493 if (out)
494 {
495 memcpy(out, item, get_size(array, 1));
496 }
497 idx = (item - start) / get_size(array, 1);
498 }
499 }
500 return idx;
501 }
502
503 void array_invoke(array_t *array, array_callback_t cb, void *user)
504 {
505 if (array)
506 {
507 void *obj;
508 int i;
509
510 for (i = array->head; i < array->count + array->head; i++)
511 {
512 obj = array->data + get_size(array, i);
513 if (!array->esize)
514 {
515 /* dereference if we store store pointers */
516 obj = *(void**)obj;
517 }
518 cb(obj, i - array->head, user);
519 }
520 }
521 }
522
523 void array_invoke_offset(array_t *array, size_t offset)
524 {
525 if (array)
526 {
527 void (*method)(void *data);
528 void *obj;
529 int i;
530
531 for (i = array->head; i < array->count + array->head; i++)
532 {
533 obj = array->data + get_size(array, i);
534 if (!array->esize)
535 {
536 /* dereference if we store store pointers */
537 obj = *(void**)obj;
538 }
539 method = *(void**)(obj + offset);
540 method(obj);
541 }
542 }
543 }
544
545 void array_destroy(array_t *array)
546 {
547 if (array)
548 {
549 free(array->data);
550 free(array);
551 }
552 }
553
554 void array_destroy_function(array_t *array, array_callback_t cb, void *user)
555 {
556 array_invoke(array, cb, user);
557 array_destroy(array);
558 }
559
560 void array_destroy_offset(array_t *array, size_t offset)
561 {
562 array_invoke_offset(array, offset);
563 array_destroy(array);
564 }
565
566 void arrays_init()
567 {
568 #ifndef HAVE_QSORT_R
569 sort_data = thread_value_create(NULL);
570 #endif
571 }
572
573 void arrays_deinit()
574 {
575 #ifndef HAVE_QSORT_R
576 sort_data->destroy(sort_data);
577 #endif
578 }