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.
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;
19         unsigned int num_alloc;
20         int (*comp)();
21         } STACK;
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.
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.
32 #define sk_num(sk)      ((sk)->num)
33 #define sk_value(sk,n)  ((sk)->data[n])
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.
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.
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.
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.
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.
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.
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.
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.
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));
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);
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);
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);
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'.