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 >= 0 && 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 >= 0 && index <= array->itemCount, NULL);
 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     wassertrv(index >= 0 && index < array->itemCount, 0);
 166
 167     if (array->destructor) {
 168         array->destructor(array->items[index]);
 169     }
 170
 171     if (index < array->itemCount-1) {
 172         memmove(array->items+index, array->items+index+1,
 173                 sizeof(void*)*(array->itemCount-index-1));
 174     }
 175
 176     array->itemCount--;
 177
 178     return 1;
 179 }
 180
 181
 182 int
 183 WMRemoveFromArray(WMArray *array, void *item)
 184 {
 185     int i;
 186
 187     for (i = 0; i < array->itemCount; i++) {
 188         if (array->items[i] == item) {
 189             return WMDeleteFromArray(array, i);
 190         }
 191     }
 192
 193     return 0;
 194 }
 195
 196
 197 void*
 198 WMGetFromArray(WMArray *array, int index)
 199 {
 200     if (index < 0 || index >= array->itemCount)
 201         return NULL;
 202
 203     return array->items[index];
 204 }
 205
 206
 207 void*
 208 WMPopFromArray(WMArray *array)
 209 {
 210     array->itemCount--;
 211
 212     return array->items[array->itemCount];
 213 }
 214
 215
 216 int
 217 WMFindInArray(WMArray *array, WMMatchDataProc *match, void *cdata)
 218 {
 219     int i;
 220
 221     if (match!=NULL) {
 222         for (i = 0; i < array->itemCount; i++) {
 223             if ((*match)(array->items[i], cdata))
 224                 return i;
 225         }
 226     } else {
 227         for (i = 0; i < array->itemCount; i++) {
 228             if (array->items[i] == cdata)
 229                 return i;
 230         }
 231     }
 232
 233     return WANotFound;
 234 }
 235
 236
 237 int
 238 WMCountInArray(WMArray *array, void *item)
 239 {
 240     int i, count;
 241
 242     for (i=0, count=0; i<array->itemCount; i++) {
 243         if (array->items[i] == item)
 244             count++;
 245     }
 246
 247     return count;
 248 }
 249
 250
 251 void
 252 WMSortArray(WMArray *array, WMCompareDataProc *comparer)
 253 {
 254     qsort(array->items, array->itemCount, sizeof(void*), comparer);
 255 }
 256
 257
 258 void
 259 WMMapArray(WMArray *array, void (*function)(void*, void*), void *data)
 260 {
 261     int i;
 262
 263     for (i=0; i<array->itemCount; i++) {
 264         (*function)(array->items[i], data);
 265     }
 266 }
 267
 268