libs/basekit/source/List.c

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docLicense("BSD revised")
   4 */
   5
   6 #define LIST_C
   7 #include "List.h"
   8 #undef LIST_C
   9 #include <stdlib.h>
  10
  11 List *List_new(void)
  12 {
  13         List *self = (List *)io_calloc(1, sizeof(List));
  14         self->size = 0;
  15         self->memSize = sizeof(void *)*LIST_START_SIZE;
  16         self->items = (void **)io_calloc(1, self->memSize);
  17         return self;
  18 }
  19
  20 List *List_clone(const List *self)
  21 {
  22         List *child = List_new();
  23         List_copy_(child, self);
  24         /*
  25          List *child = cpalloc(self, sizeof(List));
  26          child->items = cpalloc(self->items, self->memSize);
  27          */
  28         return child;
  29 }
  30
  31 static size_t indexWrap(long index, size_t size)
  32 {
  33         if (index < 0)
  34         {
  35                 index = size - index;
  36
  37                 if (index < 0)
  38                 {
  39                         index = 0;
  40                 }
  41         }
  42
  43         if (index > (int)size)
  44         {
  45                 index = size;
  46         }
  47
  48         return (size_t)index;
  49 }
  50
  51 void List_sliceInPlace(List* self, long startIndex, long endIndex)
  52 {
  53         size_t i, size = List_size(self);
  54         List *tmp = List_new();
  55         size_t start = indexWrap(startIndex, size);
  56         size_t end   = indexWrap(endIndex, size);
  57
  58         for (i = start; i < size && i < end + 1; i ++)
  59         {
  60                 List_append_(tmp, List_at_(self, i));
  61         }
  62
  63         List_copy_(self, tmp);
  64         List_free(tmp);
  65 }
  66
  67 List *List_cloneSlice(const List *self, long startIndex, long endIndex)
  68 {
  69         List *child = List_clone(self);
  70         List_sliceInPlace(child, startIndex, endIndex);
  71         return child;
  72 }
  73
  74 void List_free(List *self)
  75 {
  76         //printf("List_free(%p)\n", (void *)self);
  77         io_free(self->items);
  78         io_free(self);
  79 }
  80
  81 UArray List_asStackAllocatedUArray(List *self)
  82 {
  83         UArray a = UArray_stackAllocedEmptyUArray();
  84         a.itemType = CTYPE_uintptr_t;
  85         a.itemSize = sizeof(uintptr_t);
  86         a.size = self->size;
  87         a.data = (uint8_t *)(self->items);
  88         return a;
  89 }
  90
  91 size_t List_memorySize(const List *self)
  92 {
  93         return sizeof(List) + (self->size * sizeof(void *));
  94 }
  95
  96 void List_removeAll(List *self)
  97 {
  98         self->size = 0;
  99         List_compactIfNeeded(self);
 100 }
 101
 102 void List_copy_(List *self, const List *otherList)
 103 {
 104         if (self == otherList || (!otherList->size && !self->size))
 105         {
 106                 return;
 107         }
 108
 109         List_preallocateToSize_(self, otherList->size);
 110         memmove(self->items, otherList->items, sizeof(void *) * (otherList->size));
 111         self->size = otherList->size;
 112 }
 113
 114 int List_equals_(const List *self, const List *otherList)
 115 {
 116         return (self->size == otherList->size &&
 117                    memcmp(self->items, otherList->items, sizeof(void *) * self->size) == 0);
 118 }
 119
 120 /* --- sizing ------------------------------------------------ */
 121
 122 void List_setSize_(List *self, size_t index)
 123 {
 124         List_ifNeededSizeTo_(self, index);
 125         self->size = index;
 126 }
 127
 128 void List_preallocateToSize_(List *self, size_t index)
 129 {
 130         size_t s = index * sizeof(void *);
 131
 132         if (s >= self->memSize)
 133         {
 134                 size_t newSize = self->memSize * LIST_RESIZE_FACTOR;
 135
 136                 if (s > newSize)
 137                 {
 138                         newSize = s;
 139                 }
 140
 141                 self->items = (void **)io_realloc(self->items, newSize);
 142                 memset(self->items + self->size, 0, (newSize - (self->size*sizeof(void *))));
 143                 self->memSize = newSize;
 144         }
 145 }
 146
 147 void List_compact(List *self)
 148 {
 149         self->memSize = self->size * sizeof(void *);
 150         self->items = (void **)io_realloc(self->items, self->memSize);
 151 }
 152
 153 // -----------------------------------------------------------
 154
 155 void List_print(const List *self)
 156 {
 157         size_t i;
 158
 159         printf("List <%p> [%i bytes]\n", (void *)self, (int)self->memSize);
 160
 161         for (i = 0; i < self->size; i ++)
 162         {
 163                 printf("%i: %p\n", i, (void *)self->items[i]);
 164         }
 165
 166         printf("\n");
 167 }
 168
 169 // enumeration -----------------------------------------
 170
 171 void List_do_(List *self, ListDoCallback *callback)
 172 {
 173         LIST_FOREACH(self, i, v, if (v) (*callback)(v));
 174 }
 175
 176 void List_do_with_(List *self, ListDoWithCallback *callback, void *arg)
 177 {
 178         LIST_FOREACH(self, i, v, if (v) (*callback)(v, arg));
 179 }
 180
 181 void List_mapInPlace_(List *self, ListCollectCallback *callback)
 182 {
 183         void **items = self->items;
 184         LIST_FOREACH(self, i, v, items[i] = (*callback)(v));
 185 }
 186
 187 List *List_map_(List *self, ListCollectCallback *callback)
 188 {
 189         List *r = List_new();
 190         LIST_FOREACH(self, i, v, List_append_(r, (*callback)(v)););
 191         return r;
 192 }
 193
 194 List *List_select_(List *self, ListSelectCallback *callback)
 195 {
 196         List *r = List_new();
 197         LIST_FOREACH(self, i, v, if ((*callback)(v)) List_append_(r, v));
 198         return r;
 199 }
 200
 201 void *List_detect_(List *self, ListDetectCallback *callback)
 202 {
 203         LIST_FOREACH(self, i, v, if (v && (*callback)(v)) return v; );
 204         return NULL;
 205 }
 206
 207 void *List_anyOne(const List *self)
 208 {
 209         size_t i;
 210
 211         if (self->size == 0)
 212         {
 213                 return (void *)NULL;
 214         }
 215
 216         if (self->size == 1)
 217         {
 218                 return LIST_AT_(self, 0);
 219         }
 220
 221         i = (rand() >> 4) % (self->size); // without the shift, just get a sequence!
 222
 223         return LIST_AT_(self, i);
 224 }
 225
 226 void List_shuffle(List *self)
 227 {
 228         size_t i, j;
 229
 230         for (i = 0; i < self->size - 1; i ++)
 231         {
 232                 j = i + rand() % (self->size - i);
 233                 List_swap_with_(self, i, j);
 234         }
 235 }
 236
 237 void *List_removeLast(List *self)
 238 {
 239         void *item = List_at_(self, self->size - 1);
 240
 241         if (item)
 242         {
 243                 self->size --;
 244                 List_compactIfNeeded(self);
 245         }
 246
 247         return item;
 248 }
 249