stack.c (3706B)
1 #include <assert.h> 2 #include <stdlib.h> // for malloc() and free() 3 #include "stack.h" 4 5 /* node of a doubly-linked list */ 6 struct Node { 7 struct Node *next, *prev; 8 void *data; 9 }; 10 11 /* 12 * stack implemented using a doubly-linked list to allow traversal from the top 13 * or the bottom 14 */ 15 struct Stack { 16 struct Node *top, *bottom; 17 size_t size; 18 }; 19 20 /* node_new: create a new doubly-linked list node */ 21 static struct Node * 22 node_new(void) 23 { 24 struct Node *node = malloc(sizeof *node); 25 if (node == NULL) { 26 return NULL; 27 } 28 node->next = node->prev = node->data = NULL; 29 return node; 30 } 31 32 /* node_free: free a doubly-linked list node */ 33 static void 34 node_free(struct Node *node) 35 { 36 assert(node != NULL); 37 free(node); 38 } 39 40 /* stack_new: create a new empty stack */ 41 struct Stack * 42 stack_new(void) 43 { 44 struct Stack *stack = malloc(sizeof *stack); 45 if (stack == NULL) { 46 return NULL; 47 } 48 stack->top = stack->bottom = NULL; 49 stack->size = 0; 50 return stack; 51 } 52 53 /* 54 * stack_delete: free memory used by the stack and it's nodes. But don't free 55 * any data pointed to by the stack nodes 56 * good for stacks that don't store pointers to dynamically allocated buffers 57 */ 58 void 59 stack_delete(struct Stack *stack) 60 { 61 assert(stack != NULL); 62 for (struct Node *node = stack->top, *next_node; 63 node != NULL; node = next_node) 64 { 65 next_node = node->next; 66 node_free(node); 67 } 68 free(stack); 69 } 70 71 /* 72 * stack_free: free memory used by the stack, it's nodes, and the data stored 73 * inside each node 74 * good for stacks that store pointers to dynamically allocated buffers 75 */ 76 void 77 stack_free(struct Stack *stack, void (*free_data)(void *)) 78 { 79 assert(stack != NULL); 80 assert(free_data != NULL); 81 82 for (struct Node *node = stack->top, *next_node; 83 node != NULL; node = next_node) 84 { 85 next_node = node->next; 86 free_data(node->data); 87 node_free(node); 88 } 89 free(stack); 90 } 91 92 /* push_stack: push a new node of value 'data' to top of 'stack' */ 93 void * 94 stack_push(struct Stack *stack, void *data) 95 { 96 assert(stack != NULL); 97 assert(data != NULL); 98 99 // create a new node with passed 'data' 100 struct Node *newtop; 101 if ((newtop = node_new()) == NULL) { 102 return NULL; 103 } 104 newtop->data = data; 105 106 // push node to stack 107 if (stack->top == NULL) { 108 // first node in stack 109 stack->top = stack->bottom = newtop; 110 } else { 111 // link new top and old top 112 newtop->next = stack->top; 113 stack->top->prev = newtop; 114 // put new node at top of stack 115 stack->top = newtop; 116 } 117 stack->size++; 118 return newtop; 119 } 120 121 /* stack_pop: pop data value of top node of 'stack' */ 122 void * 123 stack_pop(struct Stack *stack) 124 { 125 assert(stack != NULL); 126 struct Node *oldtop = stack->top, 127 *newtop = stack->top->next; 128 void *data = oldtop->data; 129 130 // remove reference to old top and free it 131 newtop->prev = NULL; 132 node_free(oldtop); 133 // set new stack top and size 134 stack->top = newtop; 135 stack->size--; 136 return data; 137 } 138 139 /* stack_size: accessor for size of stack */ 140 size_t 141 stack_size(struct Stack *stack) 142 { 143 assert(stack != NULL); 144 return stack->size; 145 } 146 147 /* 148 * stack_iter: loop over 'stack' nodes from top to bottom, running 'apply' on 149 * each node 150 */ 151 void * 152 stack_iter(struct Stack *stack, void *(*apply)(void *)) 153 { 154 assert(stack != NULL); 155 assert(apply != NULL); 156 for (struct Node *node = stack->top; node != NULL; node = node->next) { 157 if (apply(node->data) == NULL) { 158 return NULL; 159 } 160 } 161 return stack; 162 } 163 164 /* 165 * stack_iter: loop over 'stack' nodes from bottom to top, running 'apply' on 166 * each node 167 */ 168 void * 169 stack_iter_reverse(struct Stack *stack, void *(*apply)(void *)) 170 { 171 assert(stack != NULL); 172 assert(apply != NULL); 173 for (struct Node *node = stack->bottom; node != NULL; node = node->prev) { 174 if (apply(node->data) == NULL) { 175 return NULL; 176 } 177 } 178 return stack; 179 }