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 int length;              /* # of items in array */
  25     unsigned int allocSize;           /* allocated size of array */
  26     void (*destructor)(void *item);   /* the destructor to free elements */
  27 } W_Array;
  28
  29
  30 WMArray*
  31 WMCreateArray(unsigned initialSize)
  32 {
  33     WMCreateArrayWithDestructor(initialSize, NULL);
  34 }
  35
  36
  37 WMArray*
  38 WMCreateArrayWithDestructor(unsigned initialSize, void (*destructor)(void*))
  39 {
  40     WMArray *array;
  41
  42     array = wmalloc(sizeof(WMArray));
  43
  44     if (initialSize == 0) {
  45         initialSize = INITIAL_SIZE;
  46     }
  47
  48     array->items = wmalloc(sizeof(void*) * initialSize);
  49
  50     array->length = 0;
  51     array->allocSize = initialSize;
  52     array->destructor = destructor;
  53
  54     return array;
  55 }
  56
  57
  58 void
  59 WMEmptyArray(WMArray *array)
  60 {
  61     if (array->destructor) {
  62         while (array->length-- > 0) {
  63             array->destructor(array->items[array->length]);
  64         }
  65     }
  66     /*memset(array->items, 0, array->length * sizeof(void*));*/
  67     array->length = 0;
  68 }
  69
  70
  71 void
  72 WMFreeArray(WMArray *array)
  73 {
  74     WMEmptyArray(array);
  75     free(array->items);
  76     free(array);
  77 }
  78
  79
  80 void*
  81 WMReplaceInArray(WMArray *array, unsigned int index, void *data)
  82 {
  83     void *old;
  84
  85     wassertrv(index > array->length, 0);
  86
  87     if (index == array->length) {
  88         WMArrayAppend(array, data);
  89         return NULL;
  90     }
  91
  92     old = array->items[index];
  93     array->items[index] = data;
  94
  95     return old;
  96 }
  97
  98
  99 void*
 100 WMGetArrayElement(WMArray *array, unsigned int index)
 101 {
 102     if (index >= array->length)
 103         return NULL;
 104
 105     return array->items[index];
 106 }
 107
 108
 109 #if 0
 110 int
 111 WMAppendToArray(WMArray *array, void *data)
 112 {
 113     if (array->length >= array->allocSize) {
 114         array->allocSize += RESIZE_INCREMENT;
 115         array->items = wrealloc(array->items, sizeof(void*)*array->allocSize);
 116     }
 117     array->items[array->length++] = data;
 118
 119     return 1;
 120 }
 121 #endif
 122
 123
 124 int
 125 WMInsertInArray(WMArray *array, unsigned index, void *data)
 126 {
 127     wassertrv(index <= array->length, 0);
 128
 129     if (array->length >= array->allocSize) {
 130         array->allocSize += RESIZE_INCREMENT;
 131         array->items = wrealloc(array->items, sizeof(void*)*array->allocSize);
 132     }
 133     if (index < array->length)
 134         memmove(array->items+index+1, array->items+index,
 135                 sizeof(void*)*(array->length-index));
 136     array->items[index] = data;
 137
 138     array->length++;
 139
 140     return 1;
 141 }
 142
 143
 144 int
 145 WMAppendToArray(WMArray *array, void *data)
 146 {
 147     return WMInsertInArray(array, array->length, data);
 148 }
 149
 150
 151 static void
 152 removeFromArray(WMArray *array, unsigned index)
 153 {
 154     /*wassertr(index < array->length);*/
 155
 156     memmove(array->items+index, array->items+index+1,
 157             sizeof(void*)*(array->length-index-1));
 158
 159     array->length--;
 160 }
 161
 162
 163 void
 164 WMDeleteFromArray(WMArray *array, unsigned index)
 165 {
 166     wassertr(index < array->length);
 167
 168     if (array->destructor) {
 169         array->destructor(array->items[index]);
 170     }
 171
 172     removeFromArray(array, index);
 173 }
 174
 175
 176 void*
 177 WMArrayPop(WMArray *array)
 178 {
 179     void *last = array->items[length-1];
 180
 181     removeFromArray(array, array->length-1);
 182
 183     return last;
 184 }
 185
 186
 187 int
 188 WMIndexForArrayElement(WMArray *array, void *data)
 189 {
 190     unsigned i;
 191
 192     for (i = 0; i < array->length; i++)
 193         if (array->items[i] == data)
 194             return i;
 195
 196     return -1;
 197 }
 198
 199