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 (size_t)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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to array.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / collections