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 W_Array {
  23     void **items;                /* the array data */
  24     int itemCount;               /* # of items in array */
  25     int allocSize;               /* allocated size of array */
  26     WMFreeDataProc *destructor;  /* the destructor to free elements */
  27 } W_Array;
  28
  29
  30 WMArray*
  31 WMCreateArray(int initialSize)
  32 {
  33     return WMCreateArrayWithDestructor(initialSize, NULL);
  34 }
  35
  36
  37 WMArray*
  38 WMCreateArrayWithDestructor(int initialSize, WMFreeDataProc *destructor)
  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->itemCount = 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->itemCount > 0) {
  63             array->itemCount--;
  64             array->destructor(array->items[array->itemCount]);
  65         }
  66     }
  67     /*memset(array->items, 0, array->itemCount * sizeof(void*));*/
  68     array->itemCount = 0;
  69 }
  70
  71
  72 void
  73 WMFreeArray(WMArray *array)
  74 {
  75     WMEmptyArray(array);
  76     free(array->items);
  77     free(array);
  78 }
  79
  80
  81 int
  82 WMGetArrayItemCount(WMArray *array)
  83 {
  84     return array->itemCount;
  85 }
  86
  87
  88 int
  89 WMAppendArray(WMArray *array, WMArray *other)
  90 {
  91     if (other->itemCount == 0)
  92         return 1;
  93
  94     if (array->itemCount + other->itemCount > array->allocSize) {
  95         array->allocSize += other->allocSize;
  96         array->items = wrealloc(array->items, sizeof(void*)*array->allocSize);
  97     }
  98
  99     memcpy(array->items+array->itemCount, other->items,
 100            sizeof(void*)*other->itemCount);
 101     array->itemCount += other->itemCount;
 102
 103     return 1;
 104 }
 105
 106
 107 int
 108 WMAddToArray(WMArray *array, void *item)
 109 {
 110     if (array->itemCount >= array->allocSize) {
 111         array->allocSize += RESIZE_INCREMENT;
 112         array->items = wrealloc(array->items, sizeof(void*)*array->allocSize);
 113     }
 114     array->items[array->itemCount] = item;
 115
 116     array->itemCount++;
 117
 118     return 1;
 119 }
 120
 121
 122 int
 123 WMInsertInArray(WMArray *array, int index, void *item)
 124 {
 125     wassertrv(index <= array->itemCount, 0);
 126
 127     if (array->itemCount >= array->allocSize) {
 128         array->allocSize += RESIZE_INCREMENT;
 129         array->items = wrealloc(array->items, sizeof(void*)*array->allocSize);
 130     }
 131     if (index < array->itemCount) {
 132         memmove(array->items+index+1, array->items+index,
 133                 sizeof(void*)*(array->itemCount-index));
 134     }
 135     array->items[index] = item;
 136
 137     array->itemCount++;
 138
 139     return 1;
 140 }
 141
 142
 143 void*
 144 WMReplaceInArray(WMArray *array, int index, void *item)
 145 {
 146     void *old;
 147
 148     wassertrv(index > array->itemCount, 0);
 149
 150     if (index == array->itemCount) {
 151         WMAddToArray(array, item);
 152         return NULL;
 153     }
 154
 155     old = array->items[index];
 156     array->items[index] = item;
 157
 158     return old;
 159 }
 160
 161
 162 int
 163 WMDeleteFromArray(WMArray *array, int index)
 164 {
 165     if (index >= array->itemCount)
 166         return 0;
 167
 168     if (array->destructor) {
 169         array->destructor(array->items[index]);
 170     }
 171
 172     if (index < array->itemCount-1) {
 173         memmove(array->items+index, array->items+index+1,
 174                 sizeof(void*)*(array->itemCount-index-1));
 175     }
 176
 177     array->itemCount--;
 178
 179     return 1;
 180 }
 181
 182
 183 int
 184 WMRemoveFromArray(WMArray *array, void *item)
 185 {
 186     int i;
 187
 188     for (i = 0; i < array->itemCount; i++) {
 189         if (array->items[i] == item) {
 190             return WMDeleteFromArray(array, i);
 191         }
 192     }
 193
 194     return 0;
 195 }
 196
 197
 198 void*
 199 WMGetFromArray(WMArray *array, int index)
 200 {
 201     if (index >= array->itemCount)
 202         return NULL;
 203
 204     return array->items[index];
 205 }
 206
 207
 208 void*
 209 WMPopFromArray(WMArray *array)
 210 {
 211     array->itemCount--;
 212
 213     return array->items[array->itemCount];
 214 }
 215
 216
 217 int
 218 WMFindInArray(WMArray *array, WMMatchDataProc *match, void *cdata)
 219 {
 220     int i;
 221
 222     if (match!=NULL) {
 223         for (i = 0; i < array->itemCount; i++) {
 224             if ((*match)(array->items[i], cdata))
 225                 return i;
 226         }
 227     } else {
 228         for (i = 0; i < array->itemCount; i++) {
 229             if (array->items[i] == cdata)
 230                 return i;
 231         }
 232     }
 233
 234     return WANotFound;
 235 }
 236
 237
 238 int
 239 WMCountInArray(WMArray *array, void *item)
 240 {
 241     int i, count;
 242
 243     for (i=0, count=0; i<array->itemCount; i++) {
 244         if (array->items[i] == item)
 245             count++;
 246     }
 247
 248     return count;
 249 }
 250
 251
 252 int
 253 WMSortArray(WMArray *array, int (*comparer)(const void*, const void*))
 254 {
 255     qsort(array->items, array->itemCount, sizeof(void*), comparer);
 256
 257     return 1;
 258 }
 259
 260
 261 void
 262 WMMapArray(WMArray *array, void (*function)(void*, void*), void *data)
 263 {
 264     int i;
 265
 266     for (i=0; i<array->itemCount; i++) {
 267         (*function)(array->items[i], data);
 268     }
 269 }
 270
 271