doc/stack.doc

   1 The stack data structure is used to store an ordered list of objects.
   2 It is basically misnamed to call it a stack but it can function that way
   3 and that is what I originally used it for.  Due to the way element
   4 pointers are kept in a malloc()ed array, the most efficient way to use this
   5 structure is to add and delete elements from the end via sk_pop() and
   6 sk_push().  If you wish to do 'lookups' sk_find() is quite efficient since
   7 it will sort the stack (if required) and then do a binary search to lookup
   8 the requested item.  This sorting occurs automatically so just sk_push()
   9 elements on the stack and don't worry about the order.  Do remember that if
  10 you do a sk_find(), the order of the elements will change.
  11
  12 You should never need to 'touch' this structure directly.
  13 typedef struct stack_st
  14         {
  15         unsigned int num;
  16         char **data;
  17         int sorted;
  18
  19         unsigned int num_alloc;
  20         int (*comp)();
  21         } STACK;
  22
  23 'num' holds the number of elements in the stack, 'data' is the array of
  24 elements.  'sorted' is 1 is the list has been sorted, 0 if not.
  25
  26 num_alloc is the number of 'nodes' allocated in 'data'.  When num becomes
  27 larger than num_alloc, data is realloced to a larger size.
  28 If 'comp' is set, it is a function that is used to compare 2 of the items
  29 in the stack.  The function should return -1, 0 or 1, depending on the
  30 ordering.
  31
  32 #define sk_num(sk)      ((sk)->num)
  33 #define sk_value(sk,n)  ((sk)->data[n])
  34
  35 These 2 macros should be used to access the number of elements in the
  36 'stack' and to access a pointer to one of the values.
  37
  38 STACK *sk_new(int (*c)());
  39         This creates a new stack.  If 'c', the comparison function, is not
  40 specified, the various functions that operate on a sorted 'stack' will not
  41 work (sk_find()).  NULL is returned on failure.
  42
  43 void sk_free(STACK *);
  44         This function free()'s a stack structure.  The elements in the
  45 stack will not be freed so one should 'pop' and free all elements from the
  46 stack before calling this function or call sk_pop_free() instead.
  47
  48 void sk_pop_free(STACK *st; void (*func)());
  49         This function calls 'func' for each element on the stack, passing
  50 the element as the argument.  sk_free() is then called to free the 'stack'
  51 structure.
  52
  53 int sk_insert(STACK *sk,char *data,int where);
  54         This function inserts 'data' into stack 'sk' at location 'where'.
  55 If 'where' is larger that the number of elements in the stack, the element
  56 is put at the end.  This function tends to be used by other 'stack'
  57 functions.  Returns 0 on failure, otherwise the number of elements in the
  58 new stack.
  59
  60 char *sk_delete(STACK *st,int loc);
  61         Remove the item a location 'loc' from the stack and returns it.
  62 Returns NULL if the 'loc' is out of range.
  63
  64 char *sk_delete_ptr(STACK *st, char *p);
  65         If the data item pointed to by 'p' is in the stack, it is deleted
  66 from the stack and returned.  NULL is returned if the element is not in the
  67 stack.
  68
  69 int sk_find(STACK *st,char *data);
  70         Returns the location that contains a value that is equal to
  71 the 'data' item.  If the comparison function was not set, this function
  72 does a linear search.  This function actually qsort()s the stack if it is not
  73 in order and then uses bsearch() to do the initial search.  If the
  74 search fails,, -1 is returned.  For mutliple items with the same
  75 value, the index of the first in the array is returned.
  76
  77 int sk_push(STACK *st,char *data);
  78         Append 'data' to the stack.  0 is returned if there is a failure
  79 (due to a malloc failure), else 1.  This is
  80 sk_insert(st,data,sk_num(st));
  81
  82 int sk_unshift(STACK *st,char *data);
  83         Prepend 'data' to the front (location 0) of the stack.  This is
  84 sk_insert(st,data,0);
  85
  86 char *sk_shift(STACK *st);
  87         Return and delete from the stack the first element in the stack.
  88 This is sk_delete(st,0);
  89
  90 char *sk_pop(STACK *st);
  91         Return and delete the last element on the stack.  This is
  92 sk_delete(st,sk_num(sk)-1);
  93
  94 void sk_zero(STACK *st);
  95         Removes all items from the stack.  It does not 'free'
  96 pointers but is a quick way to clear a 'stack of references'.