libs/basekit/source/Stack.c

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docLicense("BSD revised")
   4 docDescription("""
   5 Notes: first element of items is always 0x0.
   6 """)
   7 */
   8
   9 #define STACK_C
  10 #include "Stack.h"
  11 #undef STACK_C
  12 #if !defined(_MSC_VER)
  13 #include <inttypes.h>
  14 #endif
  15
  16 Stack *Stack_new(void)
  17 {
  18     // size is the number of pointers, including the starting NULL.
  19     int size = STACK_START_SIZE;
  20     Stack *self = (Stack *)io_calloc(1, sizeof(Stack));
  21     self->items = (void **)io_calloc(1, size*sizeof(void *));
  22     // memEnd points past the end of the items memory block.
  23     self->memEnd = self->items + size;
  24     self->top = self->items;
  25     //self->lastMark = self->items;
  26     return self;
  27 }
  28
  29 void Stack_free(Stack *self)
  30 {
  31     io_free(self->items);
  32     io_free(self);
  33 }
  34
  35 Stack *Stack_clone(const Stack *self)
  36 {
  37     Stack *s = (Stack *)cpalloc(self, sizeof(Stack));
  38
  39     ptrdiff_t nItems = self->top - self->items;
  40     ptrdiff_t size = nItems + 1;
  41
  42     s->items = (void **)cpalloc(self->items, size*sizeof(void *));
  43     s->memEnd = s->items + size;
  44     s->top = s->items + nItems;
  45     return s;
  46 }
  47
  48 void Stack_copy_(Stack *self, const Stack *other)
  49 {
  50     ptrdiff_t nItems = self->top - self->items;
  51     ptrdiff_t size = nItems + 1;
  52     ptrdiff_t sizeInBytes = size*sizeof(void *);
  53
  54     self->items = (void **)io_realloc(self->items, sizeInBytes);
  55     memcpy(self->items, other->items, sizeInBytes);
  56     self->memEnd = self->items + size;
  57     self->top = self->items + nItems;
  58 }
  59
  60
  61 // stack --------------------------------------------------
  62
  63 size_t Stack_memorySize(const Stack *self)
  64 {
  65     return sizeof(Stack) + (self->memEnd - self->items);
  66 }
  67
  68 void Stack_compact(Stack *self)
  69 {
  70     int oldSize = (1 + self->top - self->items)*sizeof(void *);
  71     self->items = (void **)io_realloc(self->items, oldSize);
  72 }
  73
  74 void Stack_resize(Stack *self)
  75 {
  76     int oldSize = (self->memEnd - self->items)*sizeof(void *);
  77     int newSize = oldSize*STACK_RESIZE_FACTOR;
  78     int i = self->top - self->items;
  79     self->items = (void **)io_realloc(self->items, newSize);
  80     self->top = self->items + i;
  81     self->memEnd = self->items + (newSize/sizeof(void *));
  82 }
  83
  84 // sizing ------------------------------------------------
  85
  86 void Stack_do_on_(const Stack *self, StackDoOnCallback *callback, void *target)
  87 {
  88     Stack *stack = Stack_newCopyWithNullMarks(self);
  89     int i;
  90
  91     for(i = 0; i < Stack_count(stack) - 1; i ++)
  92     {
  93                 void *v = Stack_at_(stack, i);
  94                 if (v) (*callback)(target, v);
  95     }
  96
  97     Stack_free(stack);
  98 }
  99
 100 void Stack_makeMarksNull(Stack *self)
 101 {
 102     ptrdiff_t mark = self->lastMark;
 103
 104     while (mark)
 105     {
 106                 ptrdiff_t nextMark = (ptrdiff_t)self->items[mark];
 107                 self->items[mark] = NULL;
 108                 mark = nextMark;
 109     }
 110 }
 111
 112 Stack *Stack_newCopyWithNullMarks(const Stack *self)
 113 {
 114     Stack *newStack = Stack_clone(self);
 115     Stack_makeMarksNull(newStack);
 116     return newStack;
 117 }
 118
 119 void Stack_popToMark_(Stack *self, intptr_t mark)
 120 {
 121     while (self->lastMark && self->lastMark != mark)
 122     {
 123                 Stack_popMark(self);
 124     }
 125
 126     if (self->lastMark == 0)
 127     {
 128                 printf("Stack error: unable to find mark %p in %p\n", (void *)mark, (void *)self);
 129                 exit(1);
 130     }
 131
 132     Stack_popMark(self);
 133 }
 134
 135 List *Stack_asList(const Stack *self) // slow
 136 {
 137         List *list = List_new();
 138         Stack_do_on_(self, (StackDoOnCallback *)List_append_, list);
 139         return list;
 140 }