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         if (array->itemCount <= 0)
 202                 return NULL;
 203
 204         array->itemCount--;
 205
 206         return array->items[array->itemCount];
 207 }
 208
 209 int WMFindInArray(WMArray * array, WMMatchDataProc * match, void *cdata)
 210 {
 211         int i;
 212
 213         if (match != NULL) {
 214                 for (i = 0; i < array->itemCount; i++) {
 215                         if ((*match) (array->items[i], cdata))
 216                                 return i;
 217                 }
 218         } else {
 219                 for (i = 0; i < array->itemCount; i++) {
 220                         if (array->items[i] == cdata)
 221                                 return i;
 222                 }
 223         }
 224
 225         return WANotFound;
 226 }
 227
 228 int WMCountInArray(WMArray * array, void *item)
 229 {
 230         int i, count;
 231
 232         for (i = 0, count = 0; i < array->itemCount; i++) {
 233                 if (array->items[i] == item)
 234                         count++;
 235         }
 236
 237         return count;
 238 }
 239
 240 void WMSortArray(WMArray * array, WMCompareDataProc * comparer)
 241 {
 242         if (array->itemCount > 1) {     /* Don't sort empty or single element arrays */
 243                 qsort(array->items, array->itemCount, sizeof(void *), comparer);
 244         }
 245 }
 246
 247 void WMMapArray(WMArray * array, void (*function) (void *, void *), void *data)
 248 {
 249         int i;
 250
 251         for (i = 0; i < array->itemCount; i++) {
 252                 (*function) (array->items[i], data);
 253         }
 254 }
 255
 256 WMArray *WMGetSubarrayWithRange(WMArray * array, WMRange aRange)
 257 {
 258         WMArray *newArray;
 259
 260         if (aRange.count <= 0)
 261                 return WMCreateArray(0);
 262
 263         if (aRange.position < 0)
 264                 aRange.position = 0;
 265         if (aRange.position >= array->itemCount)
 266                 aRange.position = array->itemCount - 1;
 267         if (aRange.position + aRange.count > array->itemCount)
 268                 aRange.count = array->itemCount - aRange.position;
 269
 270         newArray = WMCreateArray(aRange.count);
 271         memcpy(newArray->items, array->items + aRange.position, sizeof(void *) * aRange.count);
 272         newArray->itemCount = aRange.count;
 273
 274         return newArray;
 275 }
 276
 277 void *WMArrayFirst(WMArray * array, WMArrayIterator * iter)
 278 {
 279         if (array->itemCount == 0) {
 280                 *iter = WANotFound;
 281                 return NULL;
 282         } else {
 283                 *iter = 0;
 284                 return array->items[0];
 285         }
 286 }
 287
 288 void *WMArrayLast(WMArray * array, WMArrayIterator * iter)
 289 {
 290         if (array->itemCount == 0) {
 291                 *iter = WANotFound;
 292                 return NULL;
 293         } else {
 294                 *iter = array->itemCount - 1;
 295                 return array->items[*iter];
 296         }
 297 }
 298
 299 void *WMArrayNext(WMArray * array, WMArrayIterator * iter)
 300 {
 301         if (*iter >= 0 && *iter < array->itemCount - 1) {
 302                 return array->items[++(*iter)];
 303         } else {
 304                 *iter = WANotFound;
 305                 return NULL;
 306         }
 307 }
 308
 309 void *WMArrayPrevious(WMArray * array, WMArrayIterator * iter)
 310 {
 311         if (*iter > 0 && *iter < array->itemCount) {
 312                 return array->items[--(*iter)];
 313         } else {
 314                 *iter = WANotFound;
 315                 return NULL;
 316         }
 317 }