WINGs/array.c

   1 /*
   2  * Dynamically Resized Array
   3  *
   4  * Authors: Alfredo K. Kojima <kojima@windowmaker.org>
   5  *          Dan Pascu         <dan@windowmaker.org>
   6  *
   7  * This code is released to the Public Domain, but
   8  * proper credit is always appreciated :)
   9  */
  10
  11
  12 #include <stdlib.h>
  13 #include <string.h>
  14
  15 #include "WUtil.h"
  16
  17
  18 #define INITIAL_SIZE 8
  19 #define RESIZE_INCREMENT 8
  20
  21
  22 typedef struct {
  23     void **items;                      /* the array data */
  24     unsigned length;                   /* # of items in array */
  25     unsigned allocSize;                /* allocated size of array */
  26 } W_Array;
  27
  28
  29 WMArray*
  30 WMCreateArray(unsigned initialSize)
  31 {
  32     Array *a;
  33
  34     a = malloc(sizeof(Array));
  35     sassertrv(a!=NULL, NULL);
  36
  37     if (initialSize == 0) {
  38         initialSize = INITIAL_SIZE;
  39     }
  40
  41     a->items = malloc(sizeof(void*)*initialSize);
  42     sassertdo(a->items!=NULL,
  43               free(a);
  44               return NULL;
  45              );
  46     a->length = 0;
  47     a->allocSize = initialSize;
  48
  49     return a;
  50 }
  51
  52
  53 void ArrayFree(Array *array)
  54 {
  55     free(array->items);
  56     free(array);
  57 }
  58
  59
  60 void ArrayClear(Array *array)
  61 {
  62     memset(array->items, 0, array->length*sizeof(void*));
  63     array->length = 0;
  64 }
  65
  66
  67 int ArraySet(Array *array, unsigned index, void *data)
  68 {
  69     sassertrv(index > array->length, 0);
  70
  71     if (index == array->length)
  72         return ArrayAppend(array, data);
  73
  74     array->items[index] = data;
  75
  76     return 1;
  77 }
  78
  79
  80 #if 0
  81 void *ArrayGet(Array *array, unsigned index)
  82 {
  83     return array->items[index];
  84 }
  85 #endif
  86
  87
  88 int ArrayAppend(Array *array, void *data)
  89 {
  90     if (array->length >= array->allocSize) {
  91         array->allocSize += RESIZE_INCREMENT;
  92         array->items = realloc(array->items, sizeof(void*)*array->allocSize);
  93         sassertrv(array->items != NULL, 0);
  94     }
  95     array->items[array->length++] = data;
  96
  97     return 1;
  98 }
  99
 100
 101 int ArrayInsert(Array *array, unsigned index, void *data)
 102 {
 103     sassertrv(index < array->length, 0);
 104
 105     if (array->length >= array->allocSize) {
 106         array->allocSize += RESIZE_INCREMENT;
 107         array->items = realloc(array->items, sizeof(void*)*array->allocSize);
 108         sassertrv(array->items != NULL, 0);
 109     }
 110     if (index < array->length-1)
 111         memmove(array->items+index+1, array->items+index,
 112                 sizeof(void*)*(array->length-index));
 113     array->items[index] = data;
 114
 115     array->length++;
 116
 117     return 1;
 118 }
 119
 120
 121 void ArrayDelete(Array *array, unsigned index)
 122 {
 123     sassertr(index < array->length);
 124
 125     memmove(array->items+index, array->items+index+1,
 126             sizeof(void*)*(array->length-index-1));
 127
 128     array->length--;
 129 }
 130
 131
 132
 133 void *ArrayPop(Array *array)
 134 {
 135     void *d = ArrayGet(array, array->length-1);
 136
 137     ArrayDelete(array, array->length-1);
 138
 139     return d;
 140 }
 141
 142
 143 int ArrayIndex(Array *array, void *data)
 144 {
 145     unsigned i;
 146
 147     for (i = 0; i < array->length; i++)
 148         if (array->items[i] == data)
 149             return i;
 150
 151     return -1;
 152 }