libs/basekit/source/List.c

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