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 /**
  25  * Data is an allocated block, with potentially unused head and tail:
  26  *
  27  *   "esize" each (or sizeof(void*) if esize = 0)
  28  *  /-\ /-\ /-\ /-\ /-\ /-\
  29  *
  30  * +---------------+-------------------------------+---------------+
  31  * | h | e | a | d | e | l | e | m | e | n | t | s | t | a | i | l |
  32  * +---------------+-------------------------------+---------------+
  33  *
  34  * \--------------/ \-----------------------------/ \-------------/
  35  *      unused                    used                   unused
  36  *      "head"                   "count"                 "tail"
  37  *
  38  */
  39 struct array_t {
  40         /** number of elements currently in array (not counting head/tail) */
  41         u_int32_t count;
  42         /** size of each element, 0 for a pointer based array */
  43         u_int16_t esize;
  44         /** allocated but unused elements at array front */
  45         u_int8_t head;
  46         /** allocated but unused elements at array end */
  47         u_int8_t tail;
  48         /** array elements */
  49         void *data;
  50 };
  51
  52 /** maximum number of unused head/tail elements before cleanup */
  53 #define ARRAY_MAX_UNUSED 32
  54
  55 /**
  56  * Get the actual size of a number of elements
  57  */
  58 static size_t get_size(array_t *array, u_int32_t num)
  59 {
  60         if (array->esize)
  61         {
  62                 return array->esize * num;
  63         }
  64         return sizeof(void*) * num;
  65 }
  66
  67 /**
  68  * Increase allocated but unused tail room to at least "room"
  69  */
  70 static void make_tail_room(array_t *array, u_int8_t room)
  71 {
  72         if (array->tail < room)
  73         {
  74                 array->data = realloc(array->data,
  75                                                 get_size(array, array->count + array->head + room));
  76                 array->tail = room;
  77         }
  78 }
  79
  80 /**
  81  * Increase allocated but unused head room to at least "room"
  82  */
  83 static void make_head_room(array_t *array, u_int8_t room)
  84 {
  85         if (array->head < room)
  86         {
  87                 u_int8_t increase = room - array->head;
  88
  89                 array->data = realloc(array->data,
  90                                                 get_size(array, array->count + array->tail + room));
  91                 memmove(array->data + get_size(array, increase), array->data,
  92                                 get_size(array, array->count + array->tail + array->head));
  93                 array->head = room;
  94         }
  95 }
  96
  97 /**
  98  * Make space for an item at index using tail room
  99  */
 100 static void insert_tail(array_t *array, int idx)
 101 {
 102         make_tail_room(array, 1);
 103         /* move up all elements after idx by one */
 104         memmove(array->data + get_size(array, array->head + idx + 1),
 105                         array->data + get_size(array, array->head + idx),
 106                         get_size(array, array->count - idx));
 107
 108         array->tail--;
 109         array->count++;
 110 }
 111
 112 /**
 113  * Make space for an item at index using head room
 114  */
 115 static void insert_head(array_t *array, int idx)
 116 {
 117         make_head_room(array, 1);
 118         /* move down all elements before idx by one */
 119         memmove(array->data + get_size(array, array->head - 1),
 120                         array->data + get_size(array, array->head),
 121                         get_size(array, idx));
 122
 123         array->head--;
 124         array->count++;
 125 }
 126
 127 /**
 128  * Remove an item, increase tail
 129  */
 130 static void remove_tail(array_t *array, int idx)
 131 {
 132         /* move all items after idx one down */
 133         memmove(array->data + get_size(array, idx + array->head),
 134                         array->data + get_size(array, idx + array->head + 1),
 135                         get_size(array, array->count - idx));
 136         array->count--;
 137         array->tail++;
 138 }
 139
 140 /**
 141  * Remove an item, increase head
 142  */
 143 static void remove_head(array_t *array, int idx)
 144 {
 145         /* move all items before idx one up */
 146         memmove(array->data + get_size(array, array->head + 1),
 147                         array->data + get_size(array, array->head), get_size(array, idx));
 148         array->count--;
 149         array->head++;
 150 }
 151
 152 array_t *array_create(u_int esize, u_int8_t reserve)
 153 {
 154         array_t *array;
 155
 156         INIT(array,
 157                 .esize = esize,
 158                 .tail = reserve,
 159         );
 160         if (array->tail)
 161         {
 162                 array->data = malloc(array->tail * array->esize);
 163         }
 164         return array;
 165 }
 166
 167 int array_count(array_t *array)
 168 {
 169         if (array)
 170         {
 171                 return array->count;
 172         }
 173         return 0;
 174 }
 175
 176 void array_compress(array_t *array)
 177 {
 178         if (array)
 179         {
 180                 u_int32_t tail;
 181
 182                 tail = array->tail;
 183                 if (array->head)
 184                 {
 185                         memmove(array->data, array->data + get_size(array, array->head),
 186                                         get_size(array, array->count + array->tail));
 187                         tail += array->head;
 188                         array->head = 0;
 189                 }
 190                 if (tail)
 191                 {
 192                         array->data = realloc(array->data, get_size(array, array->count));
 193                         array->tail = 0;
 194                 }
 195         }
 196 }
 197
 198 typedef struct {
 199         /** public enumerator interface */
 200         enumerator_t public;
 201         /** enumerated array */
 202         array_t *array;
 203         /** current index +1, initialized at 0 */
 204         int idx;
 205 } array_enumerator_t;
 206
 207 METHOD(enumerator_t, enumerate, bool,
 208         array_enumerator_t *this, void **out)
 209 {
 210         void *pos;
 211
 212         if (this->idx >= this->array->count)
 213         {
 214                 return FALSE;
 215         }
 216
 217         pos = this->array->data +
 218                   get_size(this->array, this->idx + this->array->head);
 219         if (this->array->esize)
 220         {
 221                 /* for element based arrays we return a pointer to the element */
 222                 *out = pos;
 223         }
 224         else
 225         {
 226                 /* for pointer based arrays we return the pointer directly */
 227                 *out = *(void**)pos;
 228         }
 229         this->idx++;
 230         return TRUE;
 231 }
 232
 233 enumerator_t* array_create_enumerator(array_t *array)
 234 {
 235         array_enumerator_t *enumerator;
 236
 237         if (!array)
 238         {
 239                 return enumerator_create_empty();
 240         }
 241
 242         INIT(enumerator,
 243                 .public = {
 244                         .enumerate = (void*)_enumerate,
 245                         .destroy = (void*)free,
 246                 },
 247                 .array = array,
 248         );
 249         return &enumerator->public;
 250 }
 251
 252 void array_remove_at(array_t *array, enumerator_t *public)
 253 {
 254         array_enumerator_t *enumerator = (array_enumerator_t*)public;
 255
 256         if (enumerator->idx)
 257         {
 258                 array_remove(array, --enumerator->idx, NULL);
 259         }
 260 }
 261
 262 void array_insert_create(array_t **array, int idx, void *ptr)
 263 {
 264         if (*array == NULL)
 265         {
 266                 *array = array_create(0, 0);
 267         }
 268         array_insert(*array, idx, ptr);
 269 }
 270
 271 void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
 272 {
 273         void *ptr;
 274
 275         while (enumerator->enumerate(enumerator, &ptr))
 276         {
 277                 array_insert(array, idx, ptr);
 278         }
 279         enumerator->destroy(enumerator);
 280 }
 281
 282 void array_insert(array_t *array, int idx, void *data)
 283 {
 284         if (idx < 0 || idx <= array_count(array))
 285         {
 286                 void *pos;
 287
 288                 if (idx < 0)
 289                 {
 290                         idx = array_count(array);
 291                 }
 292
 293                 if (array->head && !array->tail)
 294                 {
 295                         insert_head(array, idx);
 296                 }
 297                 else if (array->tail && !array->head)
 298                 {
 299                         insert_tail(array, idx);
 300                 }
 301                 else if (idx > array_count(array) / 2)
 302                 {
 303                         insert_tail(array, idx);
 304                 }
 305                 else
 306                 {
 307                         insert_head(array, idx);
 308                 }
 309
 310                 pos = array->data + get_size(array, array->head + idx);
 311                 if (array->esize)
 312                 {
 313                         memcpy(pos, data, get_size(array, 1));
 314                 }
 315                 else
 316                 {
 317                         /* pointer based array, copy pointer value */
 318                         *(void**)pos = data;
 319                 }
 320         }
 321 }
 322
 323 bool array_get(array_t *array, int idx, void *data)
 324 {
 325         if (!array)
 326         {
 327                 return FALSE;
 328         }
 329         if (idx >= 0 && idx >= array_count(array))
 330         {
 331                 return FALSE;
 332         }
 333         if (idx < 0)
 334         {
 335                 if (array_count(array) == 0)
 336                 {
 337                         return FALSE;
 338                 }
 339                 idx = array_count(array) - 1;
 340         }
 341         if (data)
 342         {
 343                 memcpy(data, array->data + get_size(array, array->head + idx),
 344                            get_size(array, 1));
 345         }
 346         return TRUE;
 347 }
 348
 349 bool array_remove(array_t *array, int idx, void *data)
 350 {
 351         if (!array_get(array, idx, data))
 352         {
 353                 return FALSE;
 354         }
 355         if (idx > array_count(array) / 2)
 356         {
 357                 remove_tail(array, idx);
 358         }
 359         else
 360         {
 361                 if (idx < 0)
 362                 {
 363                         idx = array_count(array) - 1;
 364                 }
 365                 remove_head(array, idx);
 366         }
 367         if (array->head + array->tail > ARRAY_MAX_UNUSED)
 368         {
 369                 array_compress(array);
 370         }
 371         return TRUE;
 372 }
 373
 374 typedef struct {
 375         /** the array */
 376         array_t *array;
 377         /** comparison function */
 378         int (*cmp)(const void*,const void*,void*);
 379         /** optional user arg */
 380         void *arg;
 381 } sort_data_t;
 382
 383 #ifdef HAVE_QSORT_R_GNU
 384 static int compare_elements(const void *a, const void *b, void *arg)
 385 #else /* HAVE_QSORT_R_BSD */
 386 static int compare_elements(void *arg, const void *a, const void *b)
 387 #endif
 388 {
 389         sort_data_t *data = (sort_data_t*)arg;
 390
 391         if (data->array->esize)
 392         {
 393                 return data->cmp(a, b, data->arg);
 394         }
 395         return data->cmp(*(void**)a, *(void**)b, data->arg);
 396 }
 397
 398 void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
 399                                 void *user)
 400 {
 401         if (array)
 402         {
 403                 sort_data_t data = {
 404                         .array = array,
 405                         .cmp = cmp,
 406                         .arg = user,
 407                 };
 408                 void *start;
 409
 410                 start = array->data + get_size(array, array->head);
 411
 412 #ifdef HAVE_QSORT_R_GNU
 413                 qsort_r(start, array->count, get_size(array, 1), compare_elements,
 414                                 &data);
 415 #else /* HAVE_QSORT_R_BSD */
 416                 qsort_r(start, array->count, get_size(array, 1), &data,
 417                                 compare_elements);
 418 #endif
 419         }
 420 }
 421
 422 typedef struct {
 423         /** the array */
 424         array_t *array;
 425         /** the key */
 426         const void *key;
 427         /** comparison function */
 428         int (*cmp)(const void*,const void*);
 429 } bsearch_data_t;
 430
 431 static int search_elements(const void *a, const void *b)
 432 {
 433         bsearch_data_t *data = (bsearch_data_t*)a;
 434
 435         if (data->array->esize)
 436         {
 437                 return data->cmp(data->key, b);
 438         }
 439         return data->cmp(data->key, *(void**)b);
 440 }
 441
 442 int array_bsearch(array_t *array, const void *key,
 443                                   int (*cmp)(const void*,const void*), void *out)
 444 {
 445         int idx = -1;
 446
 447         if (array)
 448         {
 449                 bsearch_data_t data = {
 450                         .array = array,
 451                         .key = key,
 452                         .cmp = cmp,
 453                 };
 454                 void *start, *item;
 455
 456                 start = array->data + get_size(array, array->head);
 457
 458                 item = bsearch(&data, start, array->count, get_size(array, 1),
 459                                            search_elements);
 460                 if (item)
 461                 {
 462                         if (out)
 463                         {
 464                                 memcpy(out, item, get_size(array, 1));
 465                         }
 466                         idx = (item - start) / get_size(array, 1);
 467                 }
 468         }
 469         return idx;
 470 }
 471
 472 void array_invoke(array_t *array, array_callback_t cb, void *user)
 473 {
 474         if (array)
 475         {
 476                 void *obj;
 477                 int i;
 478
 479                 for (i = array->head; i < array->count + array->head; i++)
 480                 {
 481                         obj = array->data + get_size(array, i);
 482                         if (!array->esize)
 483                         {
 484                                 /* dereference if we store store pointers */
 485                                 obj = *(void**)obj;
 486                         }
 487                         cb(obj, i - array->head, user);
 488                 }
 489         }
 490 }
 491
 492 void array_invoke_offset(array_t *array, size_t offset)
 493 {
 494         if (array)
 495         {
 496                 void (*method)(void *data);
 497                 void *obj;
 498                 int i;
 499
 500                 for (i = array->head; i < array->count + array->head; i++)
 501                 {
 502                         obj = array->data + get_size(array, i);
 503                         if (!array->esize)
 504                         {
 505                                 /* dereference if we store store pointers */
 506                                 obj = *(void**)obj;
 507                         }
 508                         method = *(void**)(obj + offset);
 509                         method(obj);
 510                 }
 511         }
 512 }
 513
 514 void array_destroy(array_t *array)
 515 {
 516         if (array)
 517         {
 518                 free(array->data);
 519                 free(array);
 520         }
 521 }
 522
 523 void array_destroy_function(array_t *array, array_callback_t cb, void *user)
 524 {
 525         array_invoke(array, cb, user);
 526         array_destroy(array);
 527 }
 528
 529 void array_destroy_offset(array_t *array, size_t offset)
 530 {
 531         array_invoke_offset(array, offset);
 532         array_destroy(array);
 533 }