libs/basekit/source/List_inline.h

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docLicense("BSD revised")
   4 docDescription("List is an array of void pointers.
   5 The List is not responsible for io_freeing it's elements.
   6 ")
   7 */
   8
   9 #ifdef LIST_C
  10 #define IO_IN_C_FILE
  11 #endif
  12 #include "Common_inline.h"
  13 #ifdef IO_DECLARE_INLINES
  14
  15 #define LIST_FOREACH(list, index, value, code) \
  16 { \
  17         const List *foreachList = list; \
  18         size_t index, foreachMax = foreachList->size; \
  19         \
  20         for (index = 0; index < foreachMax; index ++) \
  21         { \
  22                 void *value = foreachList->items[index]; \
  23                 code; \
  24         } \
  25 }
  26
  27 #define LIST_SAFEFOREACH(list, index, value, code) \
  28 { \
  29         const List *foreachList = list; \
  30         size_t index; \
  31         \
  32         for (index = 0; index < List_size(foreachList); index ++) \
  33         { \
  34                 void *value = List_at_(foreachList, index); \
  35                 code; \
  36         } \
  37 }
  38
  39 #define LIST_REVERSEFOREACH(list, index, value, code) \
  40 { \
  41         const List *foreachList = list; \
  42         size_t index = List_size(foreachList); \
  43         \
  44         while (index) \
  45         { \
  46                 void *value = List_at_(foreachList, (index --)); \
  47                 code; \
  48         } \
  49 }
  50
  51 #define LIST_SAFEREVERSEFOREACH(list, index, value, code) \
  52 { \
  53         const List *foreachList = list; \
  54         size_t index = List_size(foreachList); \
  55         \
  56         for (index = List_size(foreachList) - 1; index > 0; index --) \
  57         { \
  58                 void *value = List_at_(foreachList, index); \
  59                 code; \
  60                 if (index > List_size(foreachList) - 1) { index = List_size(foreachList) - 1; } \
  61         } \
  62 }
  63
  64 #define LIST_DO_(list, func) \
  65 { \
  66         const List *foreachList = list; \
  67         size_t index, foreachMax = List_size(foreachList); \
  68         \
  69         for (index = 0; index < foreachMax; index ++) \
  70         { \
  71                 func(List_at_(foreachList, index)); \
  72         } \
  73 }
  74
  75 IOINLINE size_t List_size(const List *self)
  76 {
  77         return self->size;
  78 }
  79
  80 IOINLINE void List_ifNeededSizeTo_(List *self, size_t newSize)
  81 {
  82         if (newSize * sizeof(void *) >= self->memSize)
  83         {
  84                 List_preallocateToSize_(self, newSize);
  85         }
  86 }
  87
  88 IOINLINE void *List_rawAt_(List *self, size_t index)
  89 {
  90         return self->items[index];
  91 }
  92
  93
  94 IOINLINE void *List_at_(const List *self, size_t index)
  95 {
  96         if (index < self->size)
  97         {
  98                 return self->items[index];
  99         }
 100
 101         return (void *)NULL;
 102 }
 103
 104 // --------------------------------------------
 105
 106 IOINLINE long List_indexOf_(List *self, void *item)
 107 {
 108         LIST_FOREACH(self, i, v, if(v == item) return i);
 109         return -1;
 110 }
 111
 112 IOINLINE int List_contains_(List *self, void *item)
 113 {
 114         LIST_FOREACH(self, i, v, if(v == item) return 1);
 115         return 0;
 116 }
 117
 118 IOINLINE void *List_append_(List *self, void *item)
 119 {
 120         List_ifNeededSizeTo_(self, self->size + 1);
 121         self->items[self->size] = item;
 122         self->size ++;
 123         return item;
 124 }
 125
 126 IOINLINE void List_appendSeq_(List *self, const List *otherList)
 127 {
 128         LIST_FOREACH(otherList, i, v, List_append_(self, v));
 129 }
 130
 131 IOINLINE void List_compactIfNeeded(List *self)
 132 {
 133         if(self->memSize > 1024 && self->size * sizeof(void *) * 4 < self->memSize)
 134         {
 135                 List_compact(self);
 136         }
 137 }
 138
 139 IOINLINE void List_removeIndex_(List *self, size_t index)
 140 {
 141         if (index >= 0 && index < self->size)
 142         {
 143                 if ( index != self->size - 1)
 144                 {
 145                         memmove(&self->items[index], &self->items[index + 1],
 146                                    (self->size - 1 - index) * sizeof(void *));
 147                 }
 148
 149                 self->size --;
 150
 151                 List_compactIfNeeded(self);
 152         }
 153 }
 154
 155 IOINLINE void List_removeIndex_toIndex_(List *self, size_t index1, size_t index2)
 156 {
 157         long length;
 158
 159         if (index1 < 0)
 160         {
 161                 index1 = 0;
 162         }
 163
 164         if (index1 > self->size - 1)
 165         {
 166                 index1 = self->size - 1;
 167         }
 168
 169         if (index2 < 0)
 170         {
 171                 index2 = 0;
 172         }
 173
 174         if (index2 > self->size - 1)
 175         {
 176                 index2 = self->size - 1;
 177         }
 178
 179         length = index2 - index1;
 180
 181         if (length <= 0)
 182         {
 183                 return;
 184         }
 185
 186         memmove(&self->items[index1], &self->items[index2],
 187                    (self->size - index2) * sizeof(void *));
 188
 189         self->size -= length;
 190
 191         List_compactIfNeeded(self);
 192 }
 193
 194 IOINLINE void List_remove_(List *self, void *item)
 195 {
 196         size_t index;
 197
 198         for (index = 0; index < self->size; index ++)
 199         {
 200                 if (self->items[index] == item)
 201                 {
 202                         List_removeIndex_(self, index);
 203                 }
 204         }
 205 }
 206
 207 IOINLINE int List_removeFirst_(List *self, void *item)
 208 {
 209         int i, max = self->size;
 210
 211         for (i = 0; i < max; i ++)
 212         {
 213                 if (self->items[i] == item)
 214                 {
 215                         List_removeIndex_(self, i);
 216                         return 1;
 217                 }
 218         }
 219
 220         return 0;
 221 }
 222
 223 IOINLINE void List_removeLast_(List *self, void *item)
 224 {
 225         int index = self->size - 1;
 226
 227         for (index = self->size - 1; index > -1; index --)
 228         {
 229                 if (self->items[index] == item)
 230                 {
 231                         List_removeIndex_(self, index);
 232                         break;
 233                 }
 234         }
 235 }
 236
 237 IOINLINE void List_removeItems_(List *self, List *other)
 238 {
 239         LIST_FOREACH(other, i, v, List_remove_(self, v));
 240 }
 241
 242 IOINLINE void List_at_insert_(List *self, size_t index, void *item)
 243 {
 244         if (index < 0)
 245         {
 246                 return;
 247         }
 248
 249         if (index > self->size - 1)
 250         {
 251                 List_preallocateToSize_(self, index + 1);
 252         }
 253         else
 254         {
 255                 List_ifNeededSizeTo_(self, self->size + 1);
 256         }
 257
 258         memmove(&self->items[index + 1], &self->items[index],
 259                    (self->size - index) * sizeof(void *));
 260
 261         self->items[index] = item;
 262         self->size ++;
 263 }
 264
 265 IOINLINE void List_at_put_(List *self, size_t index, void *item)
 266 {
 267         if (index < 0)
 268         {
 269                 return;
 270         }
 271
 272         List_ifNeededSizeTo_(self, index);
 273         self->items[index] = item;
 274
 275         if (index + 1 > self->size)
 276         {
 277                 self->size = index + 1;
 278         }
 279 }
 280
 281 IOINLINE void List_swap_with_(List *self, long index1, long index2)
 282 {
 283         if (index1 < 0 || index2 < 0)
 284         {
 285                 return;
 286         }
 287
 288         if (index1 != index2)
 289         {
 290                 void **items = self->items;
 291                 register void *v1 = items[index1];
 292
 293                 items[index1] = items[index2];
 294                 items[index2] = v1;
 295         }
 296 }
 297
 298 IOINLINE void List_reverse(List *self)
 299 {
 300         register void **i = self->items;
 301         register void **j = i + (self->size - 1);
 302         register void *iv;
 303
 304         while (j > i)
 305         {
 306                 iv = *i;
 307                 *i = *j;
 308                 *j = iv;
 309                 j --;
 310                 i ++;
 311         }
 312 }
 313
 314 // stack --------------------------------------------------
 315
 316 IOINLINE void List_push_(List *self, void *item)
 317 {
 318         List_ifNeededSizeTo_(self, self->size + 1);
 319         self->items[self->size] = item;
 320         self->size ++;
 321 }
 322
 323 IOINLINE void *List_pop(List *self)
 324 {
 325         void *item;
 326
 327         if (!self->size)
 328         {
 329                 return (void *)NULL;
 330         }
 331
 332         self->size --;
 333         item = self->items[self->size];
 334         List_compactIfNeeded(self);
 335         return item;
 336 }
 337
 338 IOINLINE void *List_top(const List *self)
 339 {
 340         if (!self->size)
 341         {
 342                 return (void *)NULL;
 343         }
 344
 345         return self->items[self->size - 1];
 346 }
 347
 348 /* --- perform -------------------------------------------------- */
 349
 350 IOINLINE int List_removeTrueFor_(List *self, ListCollectCallback* callback)
 351 {
 352         size_t getIndex = 0;
 353         size_t putIndex = 0;
 354         size_t count = self->size;
 355         void **items = self->items;
 356
 357         while (getIndex < count)
 358         {
 359                 void *item = items[getIndex];
 360
 361                 if (item && !((*callback)(item)))
 362                 {
 363                         if (getIndex!=putIndex)
 364                         {
 365                                 items[putIndex] = item;
 366                         }
 367
 368                         putIndex ++;
 369                 }
 370
 371                 getIndex ++;
 372         }
 373
 374         self->size = putIndex;
 375
 376         return getIndex - putIndex;
 377 }
 378
 379 IOINLINE void List_qsort(List *self, ListSortCallback *callback)
 380 {
 381         qsort(self->items, self->size, sizeof(void *), *callback);
 382 }
 383
 384 IOINLINE void *List_bsearch(List *self, const void *key, ListSortCallback *callback)
 385 {
 386         return bsearch(key, self->items, self->size, sizeof(void *), callback);
 387 }
 388
 389 IOINLINE void *List_first(const List *self)
 390 {
 391         return List_at_(self, 0);
 392 }
 393
 394 IOINLINE void *List_last(List *self)
 395 {
 396         return List_at_(self, List_size(self) - 1);
 397 }
 398
 399 #undef IO_IN_C_FILE
 400 #endif
 401