WINGs/bagarray.c

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