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 WMArray*
  59 WMCreateArrayWithArray(WMArray *array)
  60 {
  61     WMArray *newArray;
  62
  63     newArray = wmalloc(sizeof(WMArray));
  64
  65     newArray->items = wmalloc(sizeof(void*) * array->allocSize);
  66     memcpy(newArray->items, array->items, sizeof(void*)*array->itemCount);
  67
  68     newArray->itemCount = array->itemCount;
  69     newArray->allocSize = array->allocSize;
  70     newArray->destructor = NULL;
  71
  72     return newArray;
  73 }
  74
  75
  76 void
  77 WMEmptyArray(WMArray *array)
  78 {
  79     if (array->destructor) {
  80         while (array->itemCount > 0) {
  81             array->itemCount--;
  82             array->destructor(array->items[array->itemCount]);
  83         }
  84     }
  85     /*memset(array->items, 0, array->itemCount * sizeof(void*));*/
  86     array->itemCount = 0;
  87 }
  88
  89
  90 void
  91 WMFreeArray(WMArray *array)
  92 {
  93     WMEmptyArray(array);
  94     free(array->items);
  95     free(array);
  96 }
  97
  98
  99 int
 100 WMGetArrayItemCount(WMArray *array)
 101 {
 102     return array->itemCount;
 103 }
 104
 105
 106 void
 107 WMAppendArray(WMArray *array, WMArray *other)
 108 {
 109     if (other->itemCount == 0)
 110         return;
 111
 112     if (array->itemCount + other->itemCount > array->allocSize) {
 113         array->allocSize += other->allocSize;
 114         array->items = wrealloc(array->items, sizeof(void*)*array->allocSize);
 115     }
 116
 117     memcpy(array->items+array->itemCount, other->items,
 118            sizeof(void*)*other->itemCount);
 119     array->itemCount += other->itemCount;
 120 }
 121
 122
 123 void
 124 WMAddToArray(WMArray *array, void *item)
 125 {
 126     if (array->itemCount >= array->allocSize) {
 127         array->allocSize += RESIZE_INCREMENT;
 128         array->items = wrealloc(array->items, sizeof(void*)*array->allocSize);
 129     }
 130     array->items[array->itemCount] = item;
 131
 132     array->itemCount++;
 133 }
 134
 135
 136 void
 137 WMInsertInArray(WMArray *array, int index, void *item)
 138 {
 139     wassertr(index >= 0 && index <= array->itemCount);
 140
 141     if (array->itemCount >= array->allocSize) {
 142         array->allocSize += RESIZE_INCREMENT;
 143         array->items = wrealloc(array->items, sizeof(void*)*array->allocSize);
 144     }
 145     if (index < array->itemCount) {
 146         memmove(array->items+index+1, array->items+index,
 147                 sizeof(void*)*(array->itemCount-index));
 148     }
 149     array->items[index] = item;
 150
 151     array->itemCount++;
 152 }
 153
 154
 155 void*
 156 WMReplaceInArray(WMArray *array, int index, void *item)
 157 {
 158     void *old;
 159
 160     wassertrv(index >= 0 && index <= array->itemCount, NULL);
 161
 162     /* is it really useful to perform append if index == array->itemCount ? -Dan */
 163     if (index == array->itemCount) {
 164         WMAddToArray(array, item);
 165         return NULL;
 166     }
 167
 168     old = array->items[index];
 169     array->items[index] = item;
 170
 171     return old;
 172 }
 173
 174
 175 int
 176 WMDeleteFromArray(WMArray *array, int index)
 177 {
 178     wassertrv(index >= 0 && index < array->itemCount, 0);
 179
 180     if (array->destructor) {
 181         array->destructor(array->items[index]);
 182     }
 183
 184     if (index < array->itemCount-1) {
 185         memmove(array->items+index, array->items+index+1,
 186                 sizeof(void*)*(array->itemCount-index-1));
 187     }
 188
 189     array->itemCount--;
 190
 191     return 1;
 192 }
 193
 194
 195 int
 196 WMRemoveFromArray(WMArray *array, void *item)
 197 {
 198     int i;
 199
 200     for (i = 0; i < array->itemCount; i++) {
 201         if (array->items[i] == item) {
 202             WMDeleteFromArray(array, i);
 203             return 1;
 204         }
 205     }
 206
 207     return 0;
 208 }
 209
 210
 211 void*
 212 WMGetFromArray(WMArray *array, int index)
 213 {
 214     if (index < 0 || index >= array->itemCount)
 215         return NULL;
 216
 217     return array->items[index];
 218 }
 219
 220
 221 void*
 222 WMPopFromArray(WMArray *array)
 223 {
 224     array->itemCount--;
 225
 226     return array->items[array->itemCount];
 227 }
 228
 229
 230 int
 231 WMFindInArray(WMArray *array, WMMatchDataProc *match, void *cdata)
 232 {
 233     int i;
 234
 235     if (match!=NULL) {
 236         for (i = 0; i < array->itemCount; i++) {
 237             if ((*match)(array->items[i], cdata))
 238                 return i;
 239         }
 240     } else {
 241         for (i = 0; i < array->itemCount; i++) {
 242             if (array->items[i] == cdata)
 243                 return i;
 244         }
 245     }
 246
 247     return WANotFound;
 248 }
 249
 250
 251 int
 252 WMCountInArray(WMArray *array, void *item)
 253 {
 254     int i, count;
 255
 256     for (i=0, count=0; i<array->itemCount; i++) {
 257         if (array->items[i] == item)
 258             count++;
 259     }
 260
 261     return count;
 262 }
 263
 264
 265 void
 266 WMSortArray(WMArray *array, WMCompareDataProc *comparer)
 267 {
 268     qsort(array->items, array->itemCount, sizeof(void*), comparer);
 269 }
 270
 271
 272 void
 273 WMMapArray(WMArray *array, void (*function)(void*, void*), void *data)
 274 {
 275     int i;
 276
 277     for (i=0; i<array->itemCount; i++) {
 278         (*function)(array->items[i], data);
 279     }
 280 }
 281
 282
 283 WMArray*
 284 WMGetSubarrayWithRange(WMArray* array, WMRange aRange)
 285 {
 286     WMArray *newArray;
 287
 288     if (aRange.count <= 0)
 289         return WMCreateArray(0);
 290
 291     if (aRange.position < 0)
 292         aRange.position = 0;
 293     if (aRange.position >= array->itemCount)
 294         aRange.position = array->itemCount - 1;
 295     if (aRange.position + aRange.count > array->itemCount)
 296         aRange.count = array->itemCount - aRange.position;
 297
 298     newArray = WMCreateArray(aRange.count);
 299     memcpy(newArray->items, array->items+aRange.position,
 300            sizeof(void*)*aRange.count);
 301     newArray->itemCount = aRange.count;
 302
 303     return newArray;
 304 }
 305
 306