stack.c

   1 #include <stdlib.h>
   2
   3 #include "stack.h"
   4
   5 /* According to some resources, some implementations of malloc are
   6    reluctant to allocate objects with a size larger than half the
   7    range of the maximum size, perhaps due to internal overflows in
   8    pointer comparisons.
   9 */
  10 #ifdef SIZE_MAX
  11 #  define SEGMENT_LIMIT (SIZE_MAX / 2)
  12 #else
  13 #  define SEGMENT_LIMIT (((size_t)(-1)) / 2)
  14 #endif
  15
  16 #define INITIAL_SIZE 16
  17
  18 typedef struct stack_segment {
  19   int *stack_data;
  20   size_t allocated_size;
  21   size_t head_idx;
  22   struct stack_segment *next;
  23 } stack_segment;
  24
  25 stack_segment *head = NULL;
  26
  27 static stack_segment *new_seg(stack_segment * link_target)
  28 {
  29   stack_segment *seg = calloc(1, sizeof (stack_segment));
  30
  31   seg->allocated_size = INITIAL_SIZE;
  32   seg->stack_data = malloc(INITIAL_SIZE * sizeof (int));
  33   seg->head_idx = 0;
  34   seg->next = link_target;
  35   return seg;
  36 }
  37
  38 void stack_init()
  39 {
  40   head = new_seg(NULL);
  41 }
  42
  43 void stack_push(int val)
  44 {
  45   if (head->head_idx >= head->allocated_size) {
  46     if (head->allocated_size * 2 > SEGMENT_LIMIT) {
  47       head = new_seg(head);
  48     } else {
  49       head->allocated_size *= 2;
  50       head->stack_data =
  51           realloc(head->stack_data, head->allocated_size * sizeof (int));
  52     }
  53   }
  54
  55   head->stack_data[head->head_idx++] = val;
  56 }
  57
  58 int stack_pop()
  59 {
  60   stack_segment *new_head;
  61
  62   if (head->head_idx == 0) {
  63     /*
  64      * this behavior is undefined.  Is interpreted as 'exit'
  65      */
  66     if (head->next == NULL)
  67       exit(0);
  68
  69     new_head = head->next;
  70     free(head->stack_data);
  71     free(head);
  72     head = new_head;
  73
  74   }
  75   return head->stack_data[--head->head_idx];
  76 }