]>
Commit | Line | Data |
---|---|---|
2621ff4d | 1 | /* |
132b00ce TB |
2 | * Copyright (C) 2014 Tobias Brunner |
3 | * Hochschule fuer Technik Rapperswil | |
4 | * | |
2621ff4d MW |
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 | ||
132b00ce TB |
19 | #define _GNU_SOURCE /* for qsort_r() */ |
20 | #include <stdlib.h> | |
21 | ||
2621ff4d MW |
22 | #include "array.h" |
23 | ||
b3613c49 TB |
24 | #ifndef HAVE_QSORT_R |
25 | #include <threading/thread_value.h> | |
26 | #endif | |
27 | ||
2621ff4d MW |
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 | ||
b3613c49 TB |
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 | ||
2621ff4d MW |
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 | */ | |
116363e5 | 67 | static size_t get_size(array_t *array, u_int32_t num) |
2621ff4d MW |
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 - 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(array->tail * array->esize); | |
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 | ||
589fab22 | 332 | bool array_get(array_t *array, int idx, void *data) |
2621ff4d MW |
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 | } | |
589fab22 MW |
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 | } | |
2621ff4d MW |
364 | if (idx > array_count(array) / 2) |
365 | { | |
366 | remove_tail(array, idx); | |
367 | } | |
368 | else | |
369 | { | |
589fab22 MW |
370 | if (idx < 0) |
371 | { | |
372 | idx = array_count(array) - 1; | |
373 | } | |
2621ff4d MW |
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 | ||
132b00ce TB |
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) | |
b3613c49 | 394 | #elif HAVE_QSORT_R_BSD |
132b00ce | 395 | static int compare_elements(void *arg, const void *a, const void *b) |
b3613c49 TB |
396 | #else /* !HAVE_QSORT_R */ |
397 | static int compare_elements(const void *a, const void *b) | |
132b00ce TB |
398 | #endif |
399 | { | |
b3613c49 | 400 | #ifdef HAVE_QSORT_R |
132b00ce | 401 | sort_data_t *data = (sort_data_t*)arg; |
b3613c49 TB |
402 | #else |
403 | sort_data_t *data = sort_data->get(sort_data); | |
404 | #endif | |
132b00ce TB |
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); | |
b3613c49 | 430 | #elif HAVE_QSORT_R_BSD |
132b00ce TB |
431 | qsort_r(start, array->count, get_size(array, 1), &data, |
432 | compare_elements); | |
b3613c49 TB |
433 | #else /* !HAVE_QSORT_R */ |
434 | sort_data->set(sort_data, &data); | |
435 | qsort(start, array->count, get_size(array, 1), compare_elements); | |
132b00ce TB |
436 | #endif |
437 | } | |
438 | } | |
439 | ||
79962d9e TB |
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 | ||
2621ff4d MW |
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 | } | |
b3613c49 TB |
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 | } |