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 #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         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
  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, u_int32_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, 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
 332 bool array_get(array_t *array, int idx, void *data)
 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         }
 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         }
 364         if (idx > array_count(array) / 2)
 365         {
 366                 remove_tail(array, idx);
 367         }
 368         else
 369         {
 370                 if (idx < 0)
 371                 {
 372                         idx = array_count(array) - 1;
 373                 }
 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
 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)
 394 #elif  HAVE_QSORT_R_BSD
 395 static int compare_elements(void *arg, const void *a, const void *b)
 396 #else /* !HAVE_QSORT_R */
 397 static int compare_elements(const void *a, const void *b)
 398 #endif
 399 {
 400 #ifdef HAVE_QSORT_R
 401         sort_data_t *data = (sort_data_t*)arg;
 402 #else
 403         sort_data_t *data = sort_data->get(sort_data);
 404 #endif
 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);
 430 #elif  HAVE_QSORT_R_BSD
 431                 qsort_r(start, array->count, get_size(array, 1), &data,
 432                                 compare_elements);
 433 #else /* !HAVE_QSORT_R */
 434                 sort_data->set(sort_data, &data);
 435                 qsort(start, array->count, get_size(array, 1), compare_elements);
 436 #endif
 437         }
 438 }
 439
 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
 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 }
 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 }