WINGs/array.c

   1 /*
   2  * Dynamically Resized Array
   3  *
   4  * Authors: Alfredo K. Kojima <kojima@windowmaker.info>
   5  *          Dan Pascu         <dan@windowmaker.info>
   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     wfree(array->items);
  95     wfree(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 WMRemoveFromArrayMatching(WMArray *array, WMMatchDataProc *match, void *cdata)
 197 {
 198     int i;
 199
 200     if (match != NULL) {
 201         for (i = 0; i < array->itemCount; i++) {
 202             if ((*match)(array->items[i], cdata)) {
 203                 WMDeleteFromArray(array, i);
 204                 return 1;
 205             }
 206         }
 207     } else {
 208         for (i = 0; i < array->itemCount; i++) {
 209             if (array->items[i] == cdata) {
 210                 WMDeleteFromArray(array, i);
 211                 return 1;
 212             }
 213         }
 214     }
 215
 216     return 0;
 217 }
 218
 219
 220 void*
 221 WMGetFromArray(WMArray *array, int index)
 222 {
 223     if (index < 0 || index >= array->itemCount)
 224         return NULL;
 225
 226     return array->items[index];
 227 }
 228
 229
 230 void*
 231 WMPopFromArray(WMArray *array)
 232 {
 233     array->itemCount--;
 234
 235     return array->items[array->itemCount];
 236 }
 237
 238
 239 int
 240 WMFindInArray(WMArray *array, WMMatchDataProc *match, void *cdata)
 241 {
 242     int i;
 243
 244     if (match!=NULL) {
 245         for (i = 0; i < array->itemCount; i++) {
 246             if ((*match)(array->items[i], cdata))
 247                 return i;
 248         }
 249     } else {
 250         for (i = 0; i < array->itemCount; i++) {
 251             if (array->items[i] == cdata)
 252                 return i;
 253         }
 254     }
 255
 256     return WANotFound;
 257 }
 258
 259
 260 int
 261 WMCountInArray(WMArray *array, void *item)
 262 {
 263     int i, count;
 264
 265     for (i=0, count=0; i<array->itemCount; i++) {
 266         if (array->items[i] == item)
 267             count++;
 268     }
 269
 270     return count;
 271 }
 272
 273
 274 void
 275 WMSortArray(WMArray *array, WMCompareDataProc *comparer)
 276 {
 277     if (array->itemCount > 1) { /* Don't sort empty or single element arrays */
 278         qsort(array->items, array->itemCount, sizeof(void*), comparer);
 279     }
 280 }
 281
 282
 283 void
 284 WMMapArray(WMArray *array, void (*function)(void*, void*), void *data)
 285 {
 286     int i;
 287
 288     for (i=0; i<array->itemCount; i++) {
 289         (*function)(array->items[i], data);
 290     }
 291 }
 292
 293
 294 WMArray*
 295 WMGetSubarrayWithRange(WMArray* array, WMRange aRange)
 296 {
 297     WMArray *newArray;
 298
 299     if (aRange.count <= 0)
 300         return WMCreateArray(0);
 301
 302     if (aRange.position < 0)
 303         aRange.position = 0;
 304     if (aRange.position >= array->itemCount)
 305         aRange.position = array->itemCount - 1;
 306     if (aRange.position + aRange.count > array->itemCount)
 307         aRange.count = array->itemCount - aRange.position;
 308
 309     newArray = WMCreateArray(aRange.count);
 310     memcpy(newArray->items, array->items+aRange.position,
 311            sizeof(void*)*aRange.count);
 312     newArray->itemCount = aRange.count;
 313
 314     return newArray;
 315 }
 316
 317
 318 void*
 319 WMArrayFirst(WMArray *array, WMArrayIterator *iter)
 320 {
 321     if (array->itemCount == 0) {
 322         *iter = WANotFound;
 323         return NULL;
 324     } else {
 325         *iter = 0;
 326         return array->items[0];
 327     }
 328 }
 329
 330
 331 void*
 332 WMArrayLast(WMArray *array, WMArrayIterator *iter)
 333 {
 334     if (array->itemCount == 0) {
 335         *iter = WANotFound;
 336         return NULL;
 337     } else {
 338         *iter = array->itemCount-1;
 339         return array->items[*iter];
 340     }
 341 }
 342
 343
 344 void*
 345 WMArrayNext(WMArray *array, WMArrayIterator *iter)
 346 {
 347     if (*iter >= 0 && *iter < array->itemCount-1) {
 348         return array->items[++(*iter)];
 349     } else {
 350         *iter = WANotFound;
 351         return NULL;
 352     }
 353 }
 354
 355
 356 void*
 357 WMArrayPrevious(WMArray *array, WMArrayIterator *iter)
 358 {
 359     if (*iter > 0 && *iter < array->itemCount) {
 360         return array->items[--(*iter)];
 361     } else {
 362         *iter = WANotFound;
 363         return NULL;
 364     }
 365 }
 366
 367
 368