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