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 {
  23     void **items;                     /* the array data */
  24     unsigned int length;              /* # of items in array */
  25     unsigned int allocSize;           /* allocated size of array */
  26     void (*destructor)(void *item);   /* the destructor to free elements */
  27 } W_Array;
  28
  29
  30 WMArray*
  31 WMCreateArray(unsigned initialSize)
  32 {
  33     WMCreateArrayWithDestructor(initialSize, NULL);
  34 }
  35
  36
  37 WMArray*
  38 WMCreateArrayWithDestructor(unsigned initialSize, void (*destructor)(void*))
  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->length = 0;
  51     array->allocSize = initialSize;
  52     array->destructor = destructor;
  53
  54     return array;
  55 }
  56
  57
  58 void
  59 WMEmptyArray(WMArray *array)
  60 {
  61     if (array->destructor) {
  62         while (array->length-- > 0) {
  63             array->destructor(array->items[array->length]);
  64         }
  65     }
  66     /*memset(array->items, 0, array->length * sizeof(void*));*/
  67     array->length = 0;
  68 }
  69
  70
  71 void
  72 WMFreeArray(WMArray *array)
  73 {
  74     WMEmptyArray(array);
  75     free(array->items);
  76     free(array);
  77 }
  78
  79
  80 int
  81 WMReplaceInArray(WMArray *array, unsigned int index, void *data)
  82 {
  83     wassertrv(index > array->length, 0);
  84
  85     if (index == array->length)
  86         return WMArrayAppend(array, data);
  87
  88     if (array->destructor) {
  89         array->destructor(array->items[index]);
  90     }
  91     array->items[index] = data;
  92
  93     return 1;
  94 }
  95
  96
  97 void*
  98 WMGetFromArray(WMArray *array, unsigned int index)
  99 {
 100     if (index < 0 || index >= array->length)
 101         return NULL;
 102
 103     return array->items[index];
 104 }
 105
 106
 107 int WMArrayAppend(WMArray *array, void *data)
 108 {
 109     if (array->length >= array->allocSize) {
 110         array->allocSize += RESIZE_INCREMENT;
 111         array->items = realloc(array->items, sizeof(void*)*array->allocSize);
 112         sassertrv(array->items != NULL, 0);
 113     }
 114     array->items[array->length++] = data;
 115
 116     return 1;
 117 }
 118
 119
 120 int WMArrayInsert(WMArray *array, unsigned index, void *data)
 121 {
 122     sassertrv(index < array->length, 0);
 123
 124     if (array->length >= array->allocSize) {
 125         array->allocSize += RESIZE_INCREMENT;
 126         array->items = realloc(array->items, sizeof(void*)*array->allocSize);
 127         sassertrv(array->items != NULL, 0);
 128     }
 129     if (index < array->length-1)
 130         memmove(array->items+index+1, array->items+index,
 131                 sizeof(void*)*(array->length-index));
 132     array->items[index] = data;
 133
 134     array->length++;
 135
 136     return 1;
 137 }
 138
 139
 140 void WMArrayDelete(WMArray *array, unsigned index)
 141 {
 142     sassertr(index < array->length);
 143
 144     memmove(array->items+index, array->items+index+1,
 145             sizeof(void*)*(array->length-index-1));
 146
 147     array->length--;
 148 }
 149
 150
 151
 152 void *WMArrayPop(WMArray *array)
 153 {
 154     void *d = WMArrayGet(array, array->length-1);
 155
 156     WMArrayDelete(array, array->length-1);
 157
 158     return d;
 159 }
 160
 161
 162 int WMArrayIndex(WMArray *array, void *data)
 163 {
 164     unsigned i;
 165
 166     for (i = 0; i < array->length; i++)
 167         if (array->items[i] == data)
 168             return i;
 169
 170     return -1;
 171 }
 172
 173