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
 239 static int
 240 firstInBag(WMBag *bag, void *item)
 241 {
 242     int j;
 243     int count = ARRAY->count;
 244     W_ArrayBag *array = ARRAY;
 245
 246     for (j = 0; j < count; j++) {
 247         if (array->items[j] == item)
 248             return j;
 249     }
 250     return -1;
 251 }
 252
 253
 254
 255
 256 static int
 257 countInBag(WMBag *bag, void *item)
 258 {
 259     int i, j;
 260     int count = ARRAY->count;
 261     W_ArrayBag *array = ARRAY;
 262
 263     for (j = 0, i = 0; j < count; j++) {
 264         if (array->items[j] == item)
 265             i++;
 266     }
 267     return i;
 268 }
 269
 270
 271 static void*
 272 replaceInBag(WMBag *bag, int index, void *item)
 273 {
 274     void *old;
 275
 276     if (index < 0 || index >= ARRAY->count)
 277         return NULL;
 278
 279     old = ARRAY->items[index];
 280
 281     ARRAY->items[index] = item;
 282
 283     return old;
 284 }
 285
 286
 287 static int
 288 sortBag(WMBag *bag, int (*comparer)(const void*, const void*))
 289 {
 290     qsort(ARRAY->items, ARRAY->count, sizeof(void*), comparer);
 291     return 1;
 292 }
 293
 294
 295
 296 static void
 297 emptyBag(WMBag *bag)
 298 {
 299     W_ArrayBag *array = ARRAY;
 300
 301     if (bag->destructor) {
 302         while (--array->count) {
 303             bag->destructor(array->items[array->count]);
 304         }
 305     }
 306     ARRAY->count=0;
 307 }
 308
 309
 310 static void
 311 freeBag(WMBag *bag)
 312 {
 313     emptyBag(bag);
 314
 315     wfree(ARRAY->items);
 316     wfree(ARRAY);
 317     wfree(bag);
 318 }
 319
 320
 321 static void
 322 mapBag(WMBag *bag, void (*function)(void *, void *), void *clientData)
 323 {
 324     int i;
 325
 326     for (i = 0; i < ARRAY->last; i++) {
 327         if (ARRAY->items[i])
 328             (*function)(ARRAY->items[i], clientData);
 329     }
 330 }
 331
 332
 333 static int
 334 findInBag(WMBag *bag, int (*match)(void*))
 335 {
 336     int i;
 337
 338     for (i = 0; i < ARRAY->last; i++) {
 339         if ((*match)(ARRAY->items[i]))
 340             return i;
 341     }
 342
 343     return -1;
 344 }
 345
 346
 347 static void*
 348 first(WMBag *bag, void **ptr)
 349 {
 350     *ptr = NULL;
 351
 352     if (ARRAY->count == 0)
 353         return NULL;
 354
 355     *(int**)ptr = 0;
 356     return ARRAY->items[0];
 357 }
 358
 359
 360 static void*
 361 last(WMBag *bag, void **ptr)
 362 {
 363     *ptr = NULL;
 364
 365     if (ARRAY->count == 0)
 366         return NULL;
 367
 368     *(int*)ptr = ARRAY->count-1;
 369
 370     return ARRAY->items[ARRAY->count-1];
 371 }
 372
 373
 374 static void*
 375 next(WMBag *bag, void **ptr)
 376 {
 377     if (!*ptr)
 378         return NULL;
 379
 380     (*(int*)ptr)++;
 381     if (*(int*)ptr >= ARRAY->count) {
 382         *ptr = NULL;
 383         return NULL;
 384     }
 385
 386     return ARRAY->items[*(int*)ptr];
 387 }
 388
 389
 390 static void*
 391 previous(WMBag *bag, void **ptr)
 392 {
 393     if (!*ptr)
 394         return NULL;
 395
 396     (*(int*)ptr)--;
 397     if (*(int*)ptr < 0) {
 398         *ptr = NULL;
 399         return NULL;
 400     }
 401
 402     return ARRAY->items[*(int*)ptr];
 403 }
 404
 405
 406
 407 static void*
 408 iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr)
 409 {
 410 }
 411
 412
 413 static int
 414 indexForIterator(WMBag *bag, WMBagIterator ptr)
 415 {
 416
 417 }
 418
 419 #endif