src/libstrongswan/collections/array.c

   1 /*
   2  * Copyright (C) 2013 Martin Willi
   3  * Copyright (C) 2013 revosec AG
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; either version 2 of the License, or (at your
   8  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * for more details.
  14  */
  15
  16 #include "array.h"
  17
  18 /**
  19  * Data is an allocated block, with potentially unused head and tail:
  20  *
  21  *   "esize" each (or sizeof(void*) if esize = 0)
  22  *  /-\ /-\ /-\ /-\ /-\ /-\
  23  *
  24  * +---------------+-------------------------------+---------------+
  25  * | h | e | a | d | e | l | e | m | e | n | t | s | t | a | i | l |
  26  * +---------------+-------------------------------+---------------+
  27  *
  28  * \--------------/ \-----------------------------/ \-------------/
  29  *      unused                    used                   unused
  30  *      "head"                   "count"                 "tail"
  31  *
  32  */
  33 struct array_t {
  34         /** number of elements currently in array (not counting head/tail) */
  35         u_int32_t count;
  36         /** size of each element, 0 for a pointer based array */
  37         u_int16_t esize;
  38         /** allocated but unused elements at array front */
  39         u_int8_t head;
  40         /** allocated but unused elements at array end */
  41         u_int8_t tail;
  42         /** array elements */
  43         void *data;
  44 };
  45
  46 /** maximum number of unused head/tail elements before cleanup */
  47 #define ARRAY_MAX_UNUSED 32
  48
  49 /**
  50  * Get the actual size of a number of elements
  51  */
  52 static size_t get_size(array_t *array, int num)
  53 {
  54         if (array->esize)
  55         {
  56                 return array->esize * num;
  57         }
  58         return sizeof(void*) * num;
  59 }
  60
  61 /**
  62  * Increase allocated but unused tail room to at least "room"
  63  */
  64 static void make_tail_room(array_t *array, u_int8_t room)
  65 {
  66         if (array->tail < room)
  67         {
  68                 array->data = realloc(array->data,
  69                                                 get_size(array, array->count + array->head + room));
  70                 array->tail = room;
  71         }
  72 }
  73
  74 /**
  75  * Increase allocated but unused head room to at least "room"
  76  */
  77 static void make_head_room(array_t *array, u_int8_t room)
  78 {
  79         if (array->head < room)
  80         {
  81                 u_int8_t increase = room - array->head;
  82
  83                 array->data = realloc(array->data,
  84                                                 get_size(array, array->count + array->tail + room));
  85                 memmove(array->data + get_size(array, increase), array->data,
  86                                 get_size(array, array->count + array->tail + array->head));
  87                 array->head = room;
  88         }
  89 }
  90
  91 /**
  92  * Make space for an item at index using tail room
  93  */
  94 static void insert_tail(array_t *array, int idx)
  95 {
  96         make_tail_room(array, 1);
  97         /* move up all elements after idx by one */
  98         memmove(array->data + get_size(array, array->head + idx + 1),
  99                         array->data + get_size(array, array->head + idx),
 100                         get_size(array, array->count - idx));
 101
 102         array->tail--;
 103         array->count++;
 104 }
 105
 106 /**
 107  * Make space for an item at index using head room
 108  */
 109 static void insert_head(array_t *array, int idx)
 110 {
 111         make_head_room(array, 1);
 112         /* move down all elements before idx by one */
 113         memmove(array->data + get_size(array, array->head - 1),
 114                         array->data + get_size(array, array->head),
 115                         get_size(array, idx));
 116
 117         array->head--;
 118         array->count++;
 119 }
 120
 121 /**
 122  * Remove an item, increase tail
 123  */
 124 static void remove_tail(array_t *array, int idx)
 125 {
 126         /* move all items after idx one down */
 127         memmove(array->data + get_size(array, idx + array->head),
 128                         array->data + get_size(array, idx + array->head + 1),
 129                         get_size(array, array->count - idx));
 130         array->count--;
 131         array->tail++;
 132 }
 133
 134 /**
 135  * Remove an item, increase head
 136  */
 137 static void remove_head(array_t *array, int idx)
 138 {
 139         /* move all items before idx one up */
 140         memmove(array->data + get_size(array, array->head + 1),
 141                         array->data + get_size(array, array->head), get_size(array, idx));
 142         array->count--;
 143         array->head++;
 144 }
 145
 146 array_t *array_create(u_int esize, u_int8_t reserve)
 147 {
 148         array_t *array;
 149
 150         INIT(array,
 151                 .esize = esize,
 152                 .tail = reserve,
 153         );
 154         if (array->tail)
 155         {
 156                 array->data = malloc(array->tail * array->esize);
 157         }
 158         return array;
 159 }
 160
 161 int array_count(array_t *array)
 162 {
 163         if (array)
 164         {
 165                 return array->count;
 166         }
 167         return 0;
 168 }
 169
 170 void array_compress(array_t *array)
 171 {
 172         if (array)
 173         {
 174                 u_int32_t tail;
 175
 176                 tail = array->tail;
 177                 if (array->head)
 178                 {
 179                         memmove(array->data, array->data + get_size(array, array->head),
 180                                         get_size(array, array->count + array->tail));
 181                         tail += array->head;
 182                         array->head = 0;
 183                 }
 184                 if (tail)
 185                 {
 186                         array->data = realloc(array->data, get_size(array, array->count));
 187                         array->tail = 0;
 188                 }
 189         }
 190 }
 191
 192 typedef struct {
 193         /** public enumerator interface */
 194         enumerator_t public;
 195         /** enumerated array */
 196         array_t *array;
 197         /** current index +1, initialized at 0 */
 198         int idx;
 199 } array_enumerator_t;
 200
 201 METHOD(enumerator_t, enumerate, bool,
 202         array_enumerator_t *this, void **out)
 203 {
 204         void *pos;
 205
 206         if (this->idx >= this->array->count)
 207         {
 208                 return FALSE;
 209         }
 210
 211         pos = this->array->data +
 212                   get_size(this->array, this->idx + this->array->head);
 213         if (this->array->esize)
 214         {
 215                 /* for element based arrays we return a pointer to the element */
 216                 *out = pos;
 217         }
 218         else
 219         {
 220                 /* for pointer based arrays we return the pointer directly */
 221                 *out = *(void**)pos;
 222         }
 223         this->idx++;
 224         return TRUE;
 225 }
 226
 227 enumerator_t* array_create_enumerator(array_t *array)
 228 {
 229         array_enumerator_t *enumerator;
 230
 231         if (!array)
 232         {
 233                 return enumerator_create_empty();
 234         }
 235
 236         INIT(enumerator,
 237                 .public = {
 238                         .enumerate = (void*)_enumerate,
 239                         .destroy = (void*)free,
 240                 },
 241                 .array = array,
 242         );
 243         return &enumerator->public;
 244 }
 245
 246 void array_remove_at(array_t *array, enumerator_t *public)
 247 {
 248         array_enumerator_t *enumerator = (array_enumerator_t*)public;
 249
 250         if (enumerator->idx)
 251         {
 252                 array_remove(array, --enumerator->idx, NULL);
 253         }
 254 }
 255
 256 void array_insert_create(array_t **array, int idx, void *ptr)
 257 {
 258         if (*array == NULL)
 259         {
 260                 *array = array_create(0, 0);
 261         }
 262         array_insert(*array, idx, ptr);
 263 }
 264
 265 void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
 266 {
 267         void *ptr;
 268
 269         while (enumerator->enumerate(enumerator, &ptr))
 270         {
 271                 array_insert(array, idx, ptr);
 272         }
 273         enumerator->destroy(enumerator);
 274 }
 275
 276 void array_insert(array_t *array, int idx, void *data)
 277 {
 278         if (idx < 0 || idx <= array_count(array))
 279         {
 280                 void *pos;
 281
 282                 if (idx < 0)
 283                 {
 284                         idx = array_count(array);
 285                 }
 286
 287                 if (array->head && !array->tail)
 288                 {
 289                         insert_head(array, idx);
 290                 }
 291                 else if (array->tail && !array->head)
 292                 {
 293                         insert_tail(array, idx);
 294                 }
 295                 else if (idx > array_count(array) / 2)
 296                 {
 297                         insert_tail(array, idx);
 298                 }
 299                 else
 300                 {
 301                         insert_head(array, idx);
 302                 }
 303
 304                 pos = array->data + get_size(array, array->head + idx);
 305                 if (array->esize)
 306                 {
 307                         memcpy(pos, data, get_size(array, 1));
 308                 }
 309                 else
 310                 {
 311                         /* pointer based array, copy pointer value */
 312                         *(void**)pos = data;
 313                 }
 314         }
 315 }
 316
 317 bool array_remove(array_t *array, int idx, void *data)
 318 {
 319         if (!array)
 320         {
 321                 return FALSE;
 322         }
 323         if (idx >= 0 && idx >= array_count(array))
 324         {
 325                 return FALSE;
 326         }
 327         if (idx < 0)
 328         {
 329                 if (array_count(array) == 0)
 330                 {
 331                         return FALSE;
 332                 }
 333                 idx = array_count(array) - 1;
 334         }
 335         if (data)
 336         {
 337                 memcpy(data, array->data + get_size(array, array->head + idx),
 338                            get_size(array, 1));
 339         }
 340         if (idx > array_count(array) / 2)
 341         {
 342                 remove_tail(array, idx);
 343         }
 344         else
 345         {
 346                 remove_head(array, idx);
 347         }
 348         if (array->head + array->tail > ARRAY_MAX_UNUSED)
 349         {
 350                 array_compress(array);
 351         }
 352         return TRUE;
 353 }
 354
 355 void array_invoke(array_t *array, array_callback_t cb, void *user)
 356 {
 357         if (array)
 358         {
 359                 void *obj;
 360                 int i;
 361
 362                 for (i = array->head; i < array->count + array->head; i++)
 363                 {
 364                         obj = array->data + get_size(array, i);
 365                         if (!array->esize)
 366                         {
 367                                 /* dereference if we store store pointers */
 368                                 obj = *(void**)obj;
 369                         }
 370                         cb(obj, i - array->head, user);
 371                 }
 372         }
 373 }
 374
 375 void array_invoke_offset(array_t *array, size_t offset)
 376 {
 377         if (array)
 378         {
 379                 void (*method)(void *data);
 380                 void *obj;
 381                 int i;
 382
 383                 for (i = array->head; i < array->count + array->head; i++)
 384                 {
 385                         obj = array->data + get_size(array, i);
 386                         if (!array->esize)
 387                         {
 388                                 /* dereference if we store store pointers */
 389                                 obj = *(void**)obj;
 390                         }
 391                         method = *(void**)(obj + offset);
 392                         method(obj);
 393                 }
 394         }
 395 }
 396
 397 void array_destroy(array_t *array)
 398 {
 399         if (array)
 400         {
 401                 free(array->data);
 402                 free(array);
 403         }
 404 }
 405
 406 void array_destroy_function(array_t *array, array_callback_t cb, void *user)
 407 {
 408         array_invoke(array, cb, user);
 409         array_destroy(array);
 410 }
 411
 412 void array_destroy_offset(array_t *array, size_t offset)
 413 {
 414         array_invoke_offset(array, offset);
 415         array_destroy(array);
 416 }