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 #include <stdlib.h>
  12 #include <string.h>
  13
  14 #include "WUtil.h"
  15
  16 #define INITIAL_SIZE 8
  17 #define RESIZE_INCREMENT 8
  18
  19 typedef struct W_Array {
  20         void **items;           /* the array data */
  21         int itemCount;          /* # of items in array */
  22         int allocSize;          /* allocated size of array */
  23         WMFreeDataProc *destructor;     /* the destructor to free elements */
  24 } W_Array;
  25
  26 WMArray *WMCreateArray(int initialSize)
  27 {
  28         return WMCreateArrayWithDestructor(initialSize, NULL);
  29 }
  30
  31 WMArray *WMCreateArrayWithDestructor(int initialSize, WMFreeDataProc * destructor)
  32 {
  33         WMArray *array;
  34
  35         array = wmalloc(sizeof(WMArray));
  36
  37         if (initialSize <= 0) {
  38                 initialSize = INITIAL_SIZE;
  39         }
  40
  41         array->items = wmalloc(sizeof(void *) * initialSize);
  42
  43         array->itemCount = 0;
  44         array->allocSize = initialSize;
  45         array->destructor = destructor;
  46
  47         return array;
  48 }
  49
  50 WMArray *WMCreateArrayWithArray(WMArray * array)
  51 {
  52         WMArray *newArray;
  53
  54         newArray = wmalloc(sizeof(WMArray));
  55
  56         newArray->items = wmalloc(sizeof(void *) * array->allocSize);
  57         memcpy(newArray->items, array->items, sizeof(void *) * array->itemCount);
  58
  59         newArray->itemCount = array->itemCount;
  60         newArray->allocSize = array->allocSize;
  61         newArray->destructor = NULL;
  62
  63         return newArray;
  64 }
  65
  66 void WMEmptyArray(WMArray * array)
  67 {
  68         if (array->destructor) {
  69                 while (array->itemCount > 0) {
  70                         array->itemCount--;
  71                         array->destructor(array->items[array->itemCount]);
  72                 }
  73         }
  74         /*memset(array->items, 0, array->itemCount * sizeof(void*)); */
  75         array->itemCount = 0;
  76 }
  77
  78 void WMFreeArray(WMArray * array)
  79 {
  80         WMEmptyArray(array);
  81         wfree(array->items);
  82         wfree(array);
  83 }
  84
  85 int WMGetArrayItemCount(WMArray * array)
  86 {
  87         return array->itemCount;
  88 }
  89
  90 void WMAppendArray(WMArray * array, WMArray * other)
  91 {
  92         if (other->itemCount == 0)
  93                 return;
  94
  95         if (array->itemCount + other->itemCount > array->allocSize) {
  96                 array->allocSize += other->allocSize;
  97                 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
  98         }
  99
 100         memcpy(array->items + array->itemCount, other->items, sizeof(void *) * other->itemCount);
 101         array->itemCount += other->itemCount;
 102 }
 103
 104 void WMAddToArray(WMArray * array, void *item)
 105 {
 106         if (array->itemCount >= array->allocSize) {
 107                 array->allocSize += RESIZE_INCREMENT;
 108                 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
 109         }
 110         array->items[array->itemCount] = item;
 111
 112         array->itemCount++;
 113 }
 114
 115 void WMInsertInArray(WMArray * array, int index, void *item)
 116 {
 117         wassertr(index >= 0 && index <= array->itemCount);
 118
 119         if (array->itemCount >= array->allocSize) {
 120                 array->allocSize += RESIZE_INCREMENT;
 121                 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
 122         }
 123         if (index < array->itemCount) {
 124                 memmove(array->items + index + 1, array->items + index,
 125                         sizeof(void *) * (array->itemCount - index));
 126         }
 127         array->items[index] = item;
 128
 129         array->itemCount++;
 130 }
 131
 132 void *WMReplaceInArray(WMArray * array, int index, void *item)
 133 {
 134         void *old;
 135
 136         wassertrv(index >= 0 && index <= array->itemCount, NULL);
 137
 138         /* is it really useful to perform append if index == array->itemCount ? -Dan */
 139         if (index == array->itemCount) {
 140                 WMAddToArray(array, item);
 141                 return NULL;
 142         }
 143
 144         old = array->items[index];
 145         array->items[index] = item;
 146
 147         return old;
 148 }
 149
 150 int WMDeleteFromArray(WMArray * array, int index)
 151 {
 152         wassertrv(index >= 0 && index < array->itemCount, 0);
 153
 154         if (array->destructor) {
 155                 array->destructor(array->items[index]);
 156         }
 157
 158         if (index < array->itemCount - 1) {
 159                 memmove(array->items + index, array->items + index + 1,
 160                         sizeof(void *) * (array->itemCount - index - 1));
 161         }
 162
 163         array->itemCount--;
 164
 165         return 1;
 166 }
 167
 168 int WMRemoveFromArrayMatching(WMArray * array, WMMatchDataProc * match, void *cdata)
 169 {
 170         int i;
 171
 172         if (match != NULL) {
 173                 for (i = 0; i < array->itemCount; i++) {
 174                         if ((*match) (array->items[i], cdata)) {
 175                                 WMDeleteFromArray(array, i);
 176                                 return 1;
 177                         }
 178                 }
 179         } else {
 180                 for (i = 0; i < array->itemCount; i++) {
 181                         if (array->items[i] == cdata) {
 182                                 WMDeleteFromArray(array, i);
 183                                 return 1;
 184                         }
 185                 }
 186         }
 187
 188         return 0;
 189 }
 190
 191 void *WMGetFromArray(WMArray * array, int index)
 192 {
 193         if (index < 0 || index >= array->itemCount)
 194                 return NULL;
 195
 196         return array->items[index];
 197 }
 198
 199 void *WMPopFromArray(WMArray * array)
 200 {
 201         array->itemCount--;
 202
 203         return array->items[array->itemCount];
 204 }
 205
 206 int WMFindInArray(WMArray * array, WMMatchDataProc * match, void *cdata)
 207 {
 208         int i;
 209
 210         if (match != NULL) {
 211                 for (i = 0; i < array->itemCount; i++) {
 212                         if ((*match) (array->items[i], cdata))
 213                                 return i;
 214                 }
 215         } else {
 216                 for (i = 0; i < array->itemCount; i++) {
 217                         if (array->items[i] == cdata)
 218                                 return i;
 219                 }
 220         }
 221
 222         return WANotFound;
 223 }
 224
 225 int WMCountInArray(WMArray * array, void *item)
 226 {
 227         int i, count;
 228
 229         for (i = 0, count = 0; i < array->itemCount; i++) {
 230                 if (array->items[i] == item)
 231                         count++;
 232         }
 233
 234         return count;
 235 }
 236
 237 void WMSortArray(WMArray * array, WMCompareDataProc * comparer)
 238 {
 239         if (array->itemCount > 1) {     /* Don't sort empty or single element arrays */
 240                 qsort(array->items, array->itemCount, sizeof(void *), comparer);
 241         }
 242 }
 243
 244 void WMMapArray(WMArray * array, void (*function) (void *, void *), void *data)
 245 {
 246         int i;
 247
 248         for (i = 0; i < array->itemCount; i++) {
 249                 (*function) (array->items[i], data);
 250         }
 251 }
 252
 253 WMArray *WMGetSubarrayWithRange(WMArray * array, WMRange aRange)
 254 {
 255         WMArray *newArray;
 256
 257         if (aRange.count <= 0)
 258                 return WMCreateArray(0);
 259
 260         if (aRange.position < 0)
 261                 aRange.position = 0;
 262         if (aRange.position >= array->itemCount)
 263                 aRange.position = array->itemCount - 1;
 264         if (aRange.position + aRange.count > array->itemCount)
 265                 aRange.count = array->itemCount - aRange.position;
 266
 267         newArray = WMCreateArray(aRange.count);
 268         memcpy(newArray->items, array->items + aRange.position, sizeof(void *) * aRange.count);
 269         newArray->itemCount = aRange.count;
 270
 271         return newArray;
 272 }
 273
 274 void *WMArrayFirst(WMArray * array, WMArrayIterator * iter)
 275 {
 276         if (array->itemCount == 0) {
 277                 *iter = WANotFound;
 278                 return NULL;
 279         } else {
 280                 *iter = 0;
 281                 return array->items[0];
 282         }
 283 }
 284
 285 void *WMArrayLast(WMArray * array, WMArrayIterator * iter)
 286 {
 287         if (array->itemCount == 0) {
 288                 *iter = WANotFound;
 289                 return NULL;
 290         } else {
 291                 *iter = array->itemCount - 1;
 292                 return array->items[*iter];
 293         }
 294 }
 295
 296 void *WMArrayNext(WMArray * array, WMArrayIterator * iter)
 297 {
 298         if (*iter >= 0 && *iter < array->itemCount - 1) {
 299                 return array->items[++(*iter)];
 300         } else {
 301                 *iter = WANotFound;
 302                 return NULL;
 303         }
 304 }
 305
 306 void *WMArrayPrevious(WMArray * array, WMArrayIterator * iter)
 307 {
 308         if (*iter > 0 && *iter < array->itemCount) {
 309                 return array->items[--(*iter)];
 310         } else {
 311                 *iter = WANotFound;
 312                 return NULL;
 313         }
 314 }