WINGs/bagarray.c

   1
   2
   3
   4
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 #include "WUtil.h"
   9
  10
  11
  12 typedef struct W_ArrayBag {
  13     void **items;
  14     int size;
  15     int count;
  16 } W_ArrayBag;
  17
  18
  19 static int    getItemCount(WMBag *bag);
  20 static int   appendBag(WMBag *bag, WMBag *appendedBag);
  21 static int   putInBag(WMBag *bag, void *item);
  22 static int   insertInBag(WMBag *bag, int index, void *item);
  23 static int   removeFromBag(WMBag *bag, void *item);
  24 static int   deleteFromBag(WMBag *bag, int index);
  25 static void*  getFromBag(WMBag *bag, int index);
  26 static int    firstInBag(WMBag *bag, void *item);
  27 static int    countInBag(WMBag *bag, void *item);
  28 static void*  replaceInBag(WMBag *bag, int index, void *item);
  29 static void   sortBag(WMBag *bag, int (*comparer)(const void*, const void*));
  30 static void   emptyBag(WMBag *bag);
  31 static void   freeBag(WMBag *bag);
  32 static WMBag* mapBag(WMBag *bag, void *(*function)(void *));
  33 static int findInBag(WMBag *bag, int (*match)(void*));
  34 static void*  first(WMBag *bag, void **ptr);
  35 static void*  last(WMBag *bag, void **ptr);
  36 static void*  next(WMBag *bag, void **ptr);
  37 static void*  previous(WMBag *bag, void **ptr);
  38
  39
  40 static W_BagFunctions arrayFunctions = {
  41     getItemCount,
  42     appendBag,
  43     putInBag,
  44     insertInBag,
  45     removeFromBag,
  46     deleteFromBag,
  47     getFromBag,
  48     firstInBag,
  49     countInBag,
  50     replaceInBag,
  51     sortBag,
  52     emptyBag,
  53     freeBag,
  54     mapBag,
  55     findInBag,
  56     first,
  57     last,
  58     next,
  59     previous
  60 };
  61
  62
  63 #define ARRAY ((W_ArrayBag*)bag->data)
  64
  65
  66 WMBag*
  67 WMCreateArrayBagWithDestructor(int size, void (*destructor)(void*))
  68 {
  69     WMBag *bag;
  70     W_ArrayBag *array;
  71
  72     wassertrv(size > 0, NULL);
  73
  74     bag = wmalloc(sizeof(WMBag));
  75
  76     array = wmalloc(sizeof(W_ArrayBag));
  77
  78     bag->data = array;
  79
  80     array->items = wmalloc(sizeof(void*) * size);
  81     array->size = size;
  82     array->count = 0;
  83
  84     bag->func = arrayFunctions;
  85
  86     bag->destructor = destructor;
  87
  88     return bag;
  89 }
  90
  91
  92 WMBag*
  93 WMCreateArrayBag(int size)
  94 {
  95     return WMCreateArrayBagWithDestructor(size, NULL);
  96 }
  97
  98
  99 static int
 100 getItemCount(WMBag *bag)
 101 {
 102     return ARRAY->count;
 103 }
 104
 105
 106 static int
 107 appendBag(WMBag *bag, WMBag *appendedBag)
 108 {
 109     W_ArrayBag *array1 = ARRAY;
 110     W_ArrayBag *array2 = (W_ArrayBag*)appendedBag->data;
 111
 112     if (array1->count + array2->count >= array1->size) {
 113         array1->items =
 114             wrealloc(array1->items, sizeof(void*) * (array1->size+array2->count));
 115         array1->size += array2->count;
 116     }
 117
 118     memcpy(array1->items + array1->count, array2->items,
 119            sizeof(void*) * array2->count);
 120
 121     array1->count += array2->count;
 122
 123     return 1;
 124 }
 125
 126
 127
 128 static int
 129 putInBag(WMBag *bag, void *item)
 130 {
 131     return insertInBag(bag, ARRAY->count, item);
 132 }
 133
 134
 135
 136 static int
 137 insertInBag(WMBag *bag, int index, void *item)
 138 {
 139     W_ArrayBag *array = ARRAY;
 140
 141     if (array->count == array->size) {
 142         array->size += 16;
 143         array->items = wrealloc(array->items, sizeof(void*) * array->size);
 144     }
 145
 146     if (index >= 0 && index < array->count) {
 147         memmove(&array->items[index+1], &array->items[index],
 148                 (array->count - index) * sizeof(void*));
 149     } else {
 150         /* If index is invalid, place it at end */
 151         index = array->count;
 152     }
 153     array->items[index] = item;
 154     array->count++;
 155
 156     return 1;
 157 }
 158
 159
 160 static int
 161 removeFromBag(WMBag *bag, void *item)
 162 {
 163     int i;
 164     W_ArrayBag *array = ARRAY;
 165
 166     for (i = 0; i < array->count; i++) {
 167         if (array->items[i] == item) {
 168             if (bag->destructor)
 169                 bag->destructor(array->items[i]);
 170
 171             memmove(&array->items[i], &array->items[i + 1],
 172                     (array->count - i - 1) * sizeof(void*));
 173             array->count--;
 174
 175             return 1;
 176         }
 177     }
 178
 179     return 0;
 180 }
 181
 182
 183
 184 static int
 185 deleteFromBag(WMBag *bag, int index)
 186 {
 187     W_ArrayBag *array = ARRAY;
 188
 189     if (index < 0 || index >= array->count)
 190         return 0;
 191
 192     if (index < array->count-1) {
 193         if (bag->destructor)
 194             bag->destructor(array->items[index]);
 195
 196         memmove(&array->items[index], &array->items[index + 1],
 197                 (array->count - index - 1) * sizeof(void*));
 198     }
 199     array->count--;
 200
 201     return 1;
 202 }
 203
 204
 205 static void*
 206 getFromBag(WMBag *bag, int index)
 207 {
 208     if (index < 0 || index >= ARRAY->count)
 209         return NULL;
 210
 211     return ARRAY->items[index];
 212 }
 213
 214
 215
 216 static int
 217 firstInBag(WMBag *bag, void *item)
 218 {
 219     int j;
 220     int count = ARRAY->count;
 221     W_ArrayBag *array = ARRAY;
 222
 223     for (j = 0; j < count; j++) {
 224         if (array->items[j] == item)
 225             return j;
 226     }
 227     return -1;
 228 }
 229
 230
 231
 232
 233 static int
 234 countInBag(WMBag *bag, void *item)
 235 {
 236     int i, j;
 237     int count = ARRAY->count;
 238     W_ArrayBag *array = ARRAY;
 239
 240     for (j = 0, i = 0; j < count; j++) {
 241         if (array->items[j] == item)
 242             i++;
 243     }
 244     return i;
 245 }
 246
 247
 248 static void*
 249 replaceInBag(WMBag *bag, int index, void *item)
 250 {
 251     void *old;
 252
 253     if (index < 0 || index >= ARRAY->count)
 254         return NULL;
 255
 256     old = ARRAY->items[index];
 257
 258     ARRAY->items[index] = item;
 259
 260     return old;
 261 }
 262
 263
 264 static void
 265 sortBag(WMBag *bag, int (*comparer)(const void*, const void*))
 266 {
 267     qsort(ARRAY->items, ARRAY->count, sizeof(void*), comparer);
 268 }
 269
 270
 271
 272 static void
 273 emptyBag(WMBag *bag)
 274 {
 275     W_ArrayBag *array = ARRAY;
 276
 277     if (bag->destructor) {
 278         while (--array->count) {
 279             bag->destructor(array->items[array->count]);
 280         }
 281     }
 282     ARRAY->count=0;
 283 }
 284
 285
 286 static void
 287 freeBag(WMBag *bag)
 288 {
 289     emptyBag(bag);
 290
 291     wfree(ARRAY->items);
 292     wfree(ARRAY);
 293     wfree(bag);
 294 }
 295
 296
 297 static WMBag*
 298 mapBag(WMBag *bag, void *(*function)(void *))
 299 {
 300     int i;
 301     void *data;
 302     WMBag *new = WMCreateArrayBagWithDestructor(ARRAY->size, bag->destructor);
 303
 304     for (i = 0; i < ARRAY->count; i++) {
 305         data = (*function)(ARRAY->items[i]);
 306         if (data)
 307             putInBag(new, data);
 308     }
 309
 310     return new;
 311 }
 312
 313
 314 static int
 315 findInBag(WMBag *bag, int (*match)(void*))
 316 {
 317     int i;
 318
 319     for (i = 0; i < ARRAY->count; i++) {
 320         if ((*match)(ARRAY->items[i]))
 321             return i;
 322     }
 323
 324     return -1;
 325 }
 326
 327
 328 static void*
 329 first(WMBag *bag, void **ptr)
 330 {
 331     *ptr = NULL;
 332
 333     if (ARRAY->count == 0)
 334         return NULL;
 335
 336     *(int**)ptr = 0;
 337     return ARRAY->items[0];
 338 }
 339
 340
 341 static void*
 342 last(WMBag *bag, void **ptr)
 343 {
 344     *ptr = NULL;
 345
 346     if (ARRAY->count == 0)
 347         return NULL;
 348
 349     *(int*)ptr = ARRAY->count-1;
 350
 351     return ARRAY->items[ARRAY->count-1];
 352 }
 353
 354
 355 static void*
 356 next(WMBag *bag, void **ptr)
 357 {
 358     if (!*ptr)
 359         return NULL;
 360
 361     (*(int*)ptr)++;
 362     if (*(int*)ptr >= ARRAY->count) {
 363         *ptr = NULL;
 364         return NULL;
 365     }
 366
 367     return ARRAY->items[*(int*)ptr];
 368 }
 369
 370
 371 static void*
 372 previous(WMBag *bag, void **ptr)
 373 {
 374     if (!*ptr)
 375         return NULL;
 376
 377     (*(int*)ptr)--;
 378     if (*(int*)ptr < 0) {
 379         *ptr = NULL;
 380         return NULL;
 381     }
 382
 383     return ARRAY->items[*(int*)ptr];
 384 }
 385
 386