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         if (array == NULL)
  81                 return;
  82
  83         WMEmptyArray(array);
  84         wfree(array->items);
  85         wfree(array);
  86 }
  87
  88 int WMGetArrayItemCount(WMArray * array)
  89 {
  90         if (array == NULL)
  91                 return 0;
  92
  93         return array->itemCount;
  94 }
  95
  96 void WMAppendArray(WMArray * array, WMArray * other)
  97 {
  98         if (array == NULL || other == NULL)
  99                 return;
 100
 101         if (other->itemCount == 0)
 102                 return;
 103
 104         if (array->itemCount + other->itemCount > array->allocSize) {
 105                 array->allocSize += other->allocSize;
 106                 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
 107         }
 108
 109         memcpy(array->items + array->itemCount, other->items, sizeof(void *) * other->itemCount);
 110         array->itemCount += other->itemCount;
 111 }
 112
 113 void WMAddToArray(WMArray * array, void *item)
 114 {
 115         if (array == NULL)
 116                 return;
 117
 118         if (array->itemCount >= array->allocSize) {
 119                 array->allocSize += RESIZE_INCREMENT;
 120                 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
 121         }
 122         array->items[array->itemCount] = item;
 123
 124         array->itemCount++;
 125 }
 126
 127 void WMInsertInArray(WMArray * array, int index, void *item)
 128 {
 129         if (array == NULL)
 130                 return;
 131
 132         wassertr(index >= 0 && index <= array->itemCount);
 133
 134         if (array->itemCount >= array->allocSize) {
 135                 array->allocSize += RESIZE_INCREMENT;
 136                 array->items = wrealloc(array->items, sizeof(void *) * array->allocSize);
 137         }
 138         if (index < array->itemCount) {
 139                 memmove(array->items + index + 1, array->items + index,
 140                         sizeof(void *) * (array->itemCount - index));
 141         }
 142         array->items[index] = item;
 143
 144         array->itemCount++;
 145 }
 146
 147 void *WMReplaceInArray(WMArray * array, int index, void *item)
 148 {
 149         void *old;
 150
 151         if (array == NULL)
 152                 return NULL;
 153
 154         wassertrv(index >= 0 && index <= array->itemCount, NULL);
 155
 156         /* is it really useful to perform append if index == array->itemCount ? -Dan */
 157         if (index == array->itemCount) {
 158                 WMAddToArray(array, item);
 159                 return NULL;
 160         }
 161
 162         old = array->items[index];
 163         array->items[index] = item;
 164
 165         return old;
 166 }
 167
 168 int WMDeleteFromArray(WMArray * array, int index)
 169 {
 170         if (array == NULL)
 171                 return 0;
 172
 173         wassertrv(index >= 0 && index < array->itemCount, 0);
 174
 175         if (array->destructor) {
 176                 array->destructor(array->items[index]);
 177         }
 178
 179         if (index < array->itemCount - 1) {
 180                 memmove(array->items + index, array->items + index + 1,
 181                         sizeof(void *) * (array->itemCount - index - 1));
 182         }
 183
 184         array->itemCount--;
 185
 186         return 1;
 187 }
 188
 189 int WMRemoveFromArrayMatching(WMArray * array, WMMatchDataProc * match, void *cdata)
 190 {
 191         int i;
 192
 193         if (array == NULL)
 194                 return 1;
 195
 196         if (match != NULL) {
 197                 for (i = 0; i < array->itemCount; i++) {
 198                         if ((*match) (array->items[i], cdata)) {
 199                                 WMDeleteFromArray(array, i);
 200                                 return 1;
 201                         }
 202                 }
 203         } else {
 204                 for (i = 0; i < array->itemCount; i++) {
 205                         if (array->items[i] == cdata) {
 206                                 WMDeleteFromArray(array, i);
 207                                 return 1;
 208                         }
 209                 }
 210         }
 211
 212         return 0;
 213 }
 214
 215 void *WMGetFromArray(WMArray * array, int index)
 216 {
 217         if (index < 0 || array == NULL || index >= array->itemCount)
 218                 return NULL;
 219
 220         return array->items[index];
 221 }
 222
 223 void *WMPopFromArray(WMArray * array)
 224 {
 225         if (array == NULL || array->itemCount <= 0)
 226                 return NULL;
 227
 228         array->itemCount--;
 229
 230         return array->items[array->itemCount];
 231 }
 232
 233 int WMFindInArray(WMArray * array, WMMatchDataProc * match, void *cdata)
 234 {
 235         int i;
 236
 237         if (array == NULL)
 238                 return WANotFound;
 239
 240         if (match != NULL) {
 241                 for (i = 0; i < array->itemCount; i++) {
 242                         if ((*match) (array->items[i], cdata))
 243                                 return i;
 244                 }
 245         } else {
 246                 for (i = 0; i < array->itemCount; i++) {
 247                         if (array->items[i] == cdata)
 248                                 return i;
 249                 }
 250         }
 251
 252         return WANotFound;
 253 }
 254
 255 int WMCountInArray(WMArray * array, void *item)
 256 {
 257         int i, count;
 258
 259         if (array == NULL)
 260                 return 0;
 261
 262         for (i = 0, count = 0; i < array->itemCount; i++) {
 263                 if (array->items[i] == item)
 264                         count++;
 265         }
 266
 267         return count;
 268 }
 269
 270 void WMSortArray(WMArray * array, WMCompareDataProc * comparer)
 271 {
 272         if (array == NULL)
 273                 return;
 274
 275         if (array->itemCount > 1) {     /* Don't sort empty or single element arrays */
 276                 qsort(array->items, array->itemCount, sizeof(void *), comparer);
 277         }
 278 }
 279
 280 void WMMapArray(WMArray * array, void (*function) (void *, void *), void *data)
 281 {
 282         int i;
 283
 284         if (array == NULL)
 285                 return;
 286
 287         for (i = 0; i < array->itemCount; i++) {
 288                 (*function) (array->items[i], data);
 289         }
 290 }
 291
 292 WMArray *WMGetSubarrayWithRange(WMArray * array, WMRange aRange)
 293 {
 294         WMArray *newArray;
 295
 296         if (aRange.count <= 0 || array == NULL)
 297                 return WMCreateArray(0);
 298
 299         if (aRange.position < 0)
 300                 aRange.position = 0;
 301         if (aRange.position >= array->itemCount)
 302                 aRange.position = array->itemCount - 1;
 303         if (aRange.position + aRange.count > array->itemCount)
 304                 aRange.count = array->itemCount - aRange.position;
 305
 306         newArray = WMCreateArray(aRange.count);
 307         memcpy(newArray->items, array->items + aRange.position, sizeof(void *) * aRange.count);
 308         newArray->itemCount = aRange.count;
 309
 310         return newArray;
 311 }
 312
 313 void *WMArrayFirst(WMArray * array, WMArrayIterator * iter)
 314 {
 315         if (array == NULL || array->itemCount == 0) {
 316                 *iter = WANotFound;
 317                 return NULL;
 318         } else {
 319                 *iter = 0;
 320                 return array->items[0];
 321         }
 322 }
 323
 324 void *WMArrayLast(WMArray * array, WMArrayIterator * iter)
 325 {
 326         if (array == NULL || array->itemCount == 0) {
 327                 *iter = WANotFound;
 328                 return NULL;
 329         } else {
 330                 *iter = array->itemCount - 1;
 331                 return array->items[*iter];
 332         }
 333 }
 334
 335 void *WMArrayNext(WMArray * array, WMArrayIterator * iter)
 336 {
 337         if (array == NULL) {
 338                 *iter = WANotFound;
 339                 return NULL;
 340         }
 341
 342         if (*iter >= 0 && *iter < array->itemCount - 1) {
 343                 return array->items[++(*iter)];
 344         } else {
 345                 *iter = WANotFound;
 346                 return NULL;
 347         }
 348 }
 349
 350 void *WMArrayPrevious(WMArray * array, WMArrayIterator * iter)
 351 {
 352         if (array == NULL) {
 353                 *iter = WANotFound;
 354                 return NULL;
 355         }
 356
 357         if (*iter > 0 && *iter < array->itemCount) {
 358                 return array->items[--(*iter)];
 359         } else {
 360                 *iter = WANotFound;
 361                 return NULL;
 362         }
 363 }