Annotation of embedaddon/strongswan/src/libstrongswan/collections/array.c, revision 1.1
1.1 ! misho 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