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     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     qsort(array->items, array->itemCount, sizeof(void*), comparer);
 278 }
 279
 280
 281 void
 282 WMMapArray(WMArray *array, void (*function)(void*, void*), void *data)
 283 {
 284     int i;
 285
 286     for (i=0; i<array->itemCount; i++) {
 287         (*function)(array->items[i], data);
 288     }
 289 }
 290
 291
 292 WMArray*
 293 WMGetSubarrayWithRange(WMArray* array, WMRange aRange)
 294 {
 295     WMArray *newArray;
 296
 297     if (aRange.count <= 0)
 298         return WMCreateArray(0);
 299
 300     if (aRange.position < 0)
 301         aRange.position = 0;
 302     if (aRange.position >= array->itemCount)
 303         aRange.position = array->itemCount - 1;
 304     if (aRange.position + aRange.count > array->itemCount)
 305         aRange.count = array->itemCount - aRange.position;
 306
 307     newArray = WMCreateArray(aRange.count);
 308     memcpy(newArray->items, array->items+aRange.position,
 309            sizeof(void*)*aRange.count);
 310     newArray->itemCount = aRange.count;
 311
 312     return newArray;
 313 }
 314
 315
 316 void*
 317 WMArrayFirst(WMArray *array, WMArrayIterator *iter)
 318 {
 319     if (array->itemCount == 0) {
 320         *iter = WANotFound;
 321         return NULL;
 322     } else {
 323         *iter = 0;
 324         return array->items[0];
 325     }
 326 }
 327
 328
 329 void*
 330 WMArrayLast(WMArray *array, WMArrayIterator *iter)
 331 {
 332     if (array->itemCount == 0) {
 333         *iter = WANotFound;
 334         return NULL;
 335     } else {
 336         *iter = array->itemCount-1;
 337         return array->items[*iter];
 338     }
 339 }
 340
 341
 342 void*
 343 WMArrayNext(WMArray *array, WMArrayIterator *iter)
 344 {
 345     if (*iter >= 0 && *iter < array->itemCount-1) {
 346         return array->items[++(*iter)];
 347     } else {
 348         *iter = WANotFound;
 349         return NULL;
 350     }
 351 }
 352
 353
 354 void*
 355 WMArrayPrevious(WMArray *array, WMArrayIterator *iter)
 356 {
 357     if (*iter > 0 && *iter < array->itemCount) {
 358         return array->items[--(*iter)];
 359     } else {
 360         *iter = WANotFound;
 361         return NULL;
 362     }
 363 }
 364
 365
 366