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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
// stack.h — Generic dynamic stack
//
// Thread safety: Not thread-safe. External synchronization required.
// Memory safety: Double-free and use-after-free protected via NULL reset.
// Empty stack: pop/peek on empty stack returns zero-initialized value.
// Use stack_pop_ok / stack_peek_ok for error detection.
#ifndef STACK_H
#define STACK_H
/* USER-DEFINED (define before including):
* typedef <type> stack_value_t;
*/
#include "type.h"
typedef struct stack {
stack_value_t *data;
u64 size;
u64 capacity;
} stack_t;
void stack_init(stack_t *);
void stack_free(stack_t *);
void stack_from_array(stack_t *, stack_value_t *, u64);
int stack_push(stack_t *, stack_value_t);
stack_value_t stack_pop(stack_t *);
int stack_pop_ok(stack_t *, stack_value_t *);
stack_value_t stack_peek(const stack_t *);
int stack_peek_ok(const stack_t *, stack_value_t *);
int stack_empty(const stack_t *);
void stack_clear(stack_t *);
#endif
#ifdef STACK_IMPLEMENTATION
#ifndef STACK_IMPLEMENTED
#define STACK_IMPLEMENTED
#include <assert.h>
#include <stdlib.h>
#include <string.h>
static stack_value_t const ZERO = {0}; /* Requires stack_value_t to be an aggregate type. For scalar types (double, int, pointer), {0} zero-initializes the entire value. For struct types, C99 guarantees remaining members are zero-initialized. */
// stack_init()
//
// Initialize or reset a stack. If stack->capacity is 0, defaults to 16.
// Frees any existing data buffer before allocating new one.
void stack_init(stack_t *stack) {
if (!stack)
return;
if (stack->data != NULL) {
free(stack->data);
stack->data = NULL;
}
if (stack->capacity == 0) {
stack->capacity = 16;
}
if (stack->capacity > SIZE_MAX / sizeof(stack_value_t)) {
stack->capacity = 0;
stack->size = 0;
stack->data = NULL;
return;
}
stack->size = 0;
stack->data = calloc(stack->capacity, sizeof(stack_value_t));
if (!stack->data)
stack->capacity = 0;
}
// stack_from_array()
//
// Initialize a stack from an existing array. Allocates exact capacity.
void stack_from_array(stack_t *stack, stack_value_t *array, u64 size) {
if (!stack || !array || size == 0)
return;
if (size > SIZE_MAX / sizeof(stack_value_t))
return;
if (stack->data)
free(stack->data);
stack->size = size;
stack->capacity = size;
stack->data = calloc((size_t)size, sizeof(stack_value_t));
if (!stack->data) {
stack->size = 0;
stack->capacity = 0;
stack->data = NULL;
return;
}
memcpy(stack->data, array, sizeof(stack_value_t) * size);
}
// stack_push()
//
// Push a value onto the stack. Automatically doubles capacity if full.
//
// return - 1 on success, 0 on failure
int stack_push(stack_t *stack, stack_value_t x) {
if (!stack || !stack->data)
return 0;
if (stack->size == stack->capacity) {
if (stack->capacity > UINT64_MAX / 2)
return 0;
stack->capacity *= 2;
if (stack->capacity > SIZE_MAX / sizeof(stack_value_t)) {
stack->capacity /= 2;
return 0;
}
void *tmp = realloc(stack->data, sizeof(stack_value_t) * stack->capacity);
if (!tmp) {
stack->capacity /= 2;
return 0;
}
stack->data = tmp;
}
stack->data[stack->size] = x;
stack->size++;
return 1;
}
// stack_pop()
//
// Remove and return the top element. Returns zero-initialized value on
// empty stack — use stack_pop_ok for error detection.
stack_value_t stack_pop(stack_t *stack) {
if (!stack || !stack->data || stack->size == 0) {
return ZERO;
}
stack->size--;
stack_value_t x = stack->data[stack->size];
stack->data[stack->size] = ZERO;
return x;
}
// stack_pop_ok()
//
// Same as stack_pop, but writes result to *out and returns status code.
//
// return - 1 on success, 0 on empty stack or invalid args
int stack_pop_ok(stack_t *stack, stack_value_t *out) {
if (!stack || !stack->data || !out || stack->size == 0) {
return 0;
}
stack->size--;
*out = stack->data[stack->size];
stack->data[stack->size] = ZERO;
return 1;
}
// stack_peek()
//
// Return the top element without removing it. Returns zero on empty stack
// — use stack_peek_ok for error detection.
stack_value_t stack_peek(const stack_t *stack) {
if (!stack || !stack->data || stack->size == 0) {
return ZERO;
}
return stack->data[stack->size - 1];
}
// stack_peek_ok()
//
// Same as stack_peek, but writes result to *out and returns status code.
//
// return - 1 on success, 0 on empty stack or invalid args
int stack_peek_ok(const stack_t *stack, stack_value_t *out) {
if (!stack || !stack->data || !out || stack->size == 0) {
return 0;
}
*out = stack->data[stack->size - 1];
return 1;
}
// stack_empty()
//
// Check if the stack is empty.
//
// return - 1 if empty, 0 otherwise
int stack_empty(const stack_t *stack) {
if (!stack)
return 1;
return stack->size == 0;
}
// stack_clear()
//
// Reset the stack to empty, zeroing all allocated slots
void stack_clear(stack_t *stack) {
if (!stack || !stack->data)
return;
if (stack->capacity > SIZE_MAX / sizeof(stack_value_t))
return;
for (u64 i = 0; i < stack->capacity; i++)
stack->data[i] = ZERO;
stack->size = 0;
}
// stack_free()
//
// Release the stack's data buffer and reset all fields
void stack_free(stack_t *stack) {
if (stack) {
free(stack->data);
stack->data = NULL;
stack->size = 0;
stack->capacity = 0;
}
}
#endif /* STACK_IMPLEMENTED */
#endif /* STACK_IMPLEMENTATION */
|