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
|
/* SPDX-License-Identifier: GPL-2.0-or-later */
/* Copyright (C) 2026 Richard Qin */
#ifndef STACK_H
#define STACK_H
/**
* @file stack.h
* @brief LIFO stack primitives backed by a dynamically sized vector.
*
* A stack stores elements by value and uses the last vector element as its
* top. The element size is fixed when the stack is initialized.
*/
#include "vec.h"
/**
* @brief A generic last-in, first-out stack.
*/
typedef struct stack {
/** @brief Contiguous storage for the stack elements. */
vec container;
} stack;
/** @name Initialization */
/** @{ */
/**
* @brief Produces an initializer for an empty stack of the given type.
* @param type The element type.
* @return An initializer for a `stack` object.
*/
#define STACK_INIT(type) { \
.container = VEC_INIT(type), \
}
/**
* @brief Declares and initializes an empty stack.
* @param name The stack variable name.
* @param type The element type.
*/
#define STACK(name, type) \
stack name = STACK_INIT(type)
/**
* @brief Initializes an existing stack for elements of `type`.
* @param s A pointer to the stack.
* @param type The element type.
* @post `s` is empty and its element size is `sizeof(type)`.
*/
#define stack_init(s, type) \
vec_init(&(s)->container, type)
/**
* @brief Destroys a stack and releases its allocated storage.
* @param s A pointer to the stack.
* @pre `s` points to a stack initialized by `STACK` or `stack_init`.
*/
static inline void stack_destroy(stack *s)
{
vec_destroy(&s->container);
}
/** @} */
/** @name Basic properties */
/** @{ */
/**
* @brief Returns the number of elements in the stack.
* @param s A pointer to the stack.
* @return The number of elements in the stack.
* @pre `s` points to an initialized stack.
*/
static inline size_t stack_size(const stack *s)
{
return vec_size(&s->container);
}
/**
* @brief Tests whether the stack is empty.
* @param s A pointer to the stack.
* @return `true` when the stack contains no elements; otherwise `false`.
* @pre `s` points to an initialized stack.
*/
static inline bool stack_empty(const stack *s)
{
return vec_empty(&s->container);
}
/**
* @brief Removes all elements without releasing the allocated capacity.
* @param s A pointer to the stack.
* @post The stack is empty and its allocated capacity is unchanged.
* @pre `s` points to an initialized stack.
*/
static inline void stack_clear(stack *s)
{
vec_clear(&s->container);
}
/**
* @brief Exchanges the contents of two stacks.
* @param a A pointer to the first stack.
* @param b A pointer to the second stack.
* @pre Both stacks are initialized with the same element size.
*/
static inline void stack_swap(stack *a, stack *b)
{
vec_swap(&a->container, &b->container);
}
/** @} */
/** @name Top element */
/** @{ */
/**
* @brief Returns a writable pointer to the top element.
* @param s A pointer to the stack.
* @return A pointer to the top element.
* @pre `s` points to an initialized stack containing at least one element.
*/
static inline void *stack_top(stack *s)
{
return vec_back(&s->container);
}
/**
* @brief Returns a read-only pointer to the top element.
* @param s A pointer to the stack.
* @return A pointer to the top element.
* @pre `s` points to an initialized stack containing at least one element.
*/
static inline const void *stack_top_const(const stack *s)
{
return vec_back_const(&s->container);
}
/** @} */
/** @name Insertion and erasure */
/** @{ */
/**
* @brief Pushes one raw element onto the stack.
* @param s A pointer to the stack.
* @param value A pointer to the element to copy.
* @return `true` on success; `false` for invalid input or allocation failure.
* @pre `s` points to an initialized stack.
*/
static inline bool stack_push(stack *s, const void *value)
{
return vec_push_back(&s->container, value);
}
/**
* @brief Pushes a typed value after checking its size.
* @param s A pointer to the stack.
* @param value The value to copy onto the stack.
* @pre `s` points to an initialized stack whose element type is `typeof(value)`.
*/
#define stack_push_value(s, value) ({ \
typeof(value) __stack_tmp = (value); \
assert(sizeof(__stack_tmp) == \
(s)->container.elem_size); \
stack_push((s), &__stack_tmp); \
})
/**
* @brief Removes the top element, if one exists.
* @param s A pointer to the stack.
*
* Like `std::stack::pop`, this function does not return the removed value.
* @pre `s` points to an initialized stack.
*/
static inline void stack_pop(stack *s)
{
vec_pop_back(&s->container);
}
/**
* @brief Removes the top element and copies it to `out`.
* @param s A pointer to the stack.
* @param out A pointer receiving the removed element.
* @return `true` on success; `false` when the stack is empty or invalid.
* @pre `s` points to an initialized stack.
*/
static inline bool stack_pop_copy(stack *s, void *out)
{
return vec_pop_back_copy(&s->container, out);
}
/** @} */
/** @name Typed access helpers */
/** @{ */
/**
* @brief Returns the top element converted to a writable typed pointer.
* @param s A pointer to the stack.
* @param type The element type.
* @pre `s` points to an initialized, non-empty stack.
*/
#define stack_top_as(s, type) \
((type *)stack_top((s)))
/**
* @brief Returns the top element converted to a read-only typed pointer.
* @param s A pointer to the stack.
* @param type The element type.
* @pre `s` points to an initialized, non-empty stack.
*/
#define stack_top_as_const(s, type) \
((const type *)stack_top_const((s)))
/** @} */
#endif /* STACK_H */
|
