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
|
/* Licensed under BSD-MIT - see LICENSE file for details */
#ifndef CCAN_LSTACK_H
#define CCAN_LSTACK_H
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <ccan/container_of/container_of.h>
/**
* struct lstack_link - a stack link
* @down: immedately lower entry in the stack, or NULL if this is the bottom.
*
* This is used as an entry in a stack.
*
* Example:
* struct stacker {
* char *name;
* struct lstack_link sl;
* };
*/
struct lstack_link {
struct lstack_link *down;
};
/**
* struct lstack - a stack
* @b: the top of the stack (NULL if empty)
*/
struct lstack {
struct lstack_link *top;
};
/**
* LSTACK - define and initialize an empty stack
* @name: the name of the lstack.
*
* The LSTACK macro defines an lstack and initializes it to an empty
* stack. It can be prepended by "static" to define a static lstack.
*
* See also:
* lstack_init()
*
* Example:
* LSTACK(my_stack);
*
* assert(lstack_empty(&my_stack));
*/
#define LSTACK(name) \
struct lstack name = { NULL, }
/**
* lstack_init_from_top - initialize a stack with a given top element
* @s: the lstack to initialize
* @e: pointer to the top element of the new stack
* @member: member of the element containing the lstack_link
*
* USE WITH CAUTION: This is for handling unusual cases where you have
* a pointer to an element in a previously constructed stack but can't
* conveniently pass around a normal struct lstack. Usually you
* should use lstack_init().
*
* Example:
* LSTACK(stack1);
* struct lstack stack2;
* struct element {
* int value;
* struct lstack_link link;
* } el;
*
* lstack_push(&stack1, &el, link);
*
* lstack_init_from_top(&stack2,
* lstack_top(&stack1, struct element, link), link);
*/
#define lstack_init_from_top(s, e, member) \
(lstack_init_((s), &(e)->member))
/**
* lstack_init - initialize a stack
* @h: the lstack to set to an empty stack
*
* Example:
* struct lstack *sp = malloc(sizeof(*sp));
* lstack_init(sp);
*/
#define lstack_init(s) \
(lstack_init_((s), NULL))
static inline void lstack_init_(struct lstack *s, struct lstack_link *top)
{
s->top = top;
}
/**
* lstack_empty - is a stack empty?
* @s: the stack
*
* If the stack is empty, returns true.
*
* Example:
* assert(lstack_empty(sp));
*/
static inline bool lstack_empty(const struct lstack *s)
{
return (s->top == NULL);
}
/**
* lstack_entry - convert an lstack_link back into the structure containing it.
* @e: the lstack_link
* @type: the type of the entry
* @member: the lstack_link member of the type
*
* Example:
* struct stacker {
* char *name;
* struct lstack_link sl;
* } st;
* assert(lstack_entry(&st.sl, struct stacker, sl) == &st);
*/
#define lstack_entry(n, type, member) container_of_or_null(n, type, member)
/**
* lstack_top - get top entry in a stack
* @s: the stack
* @type: the type of stack entries
* @member: the lstack_link entry
*
* If the stack is empty, returns NULL.
*
* Example:
* struct stacker *t;
*
* t = lstack_top(sp, struct stacker, sl);
* assert(lstack_pop(sp, struct stacker, sl) == t);
*/
#define lstack_top(s, type, member) \
lstack_entry(lstack_top_((s)), type, member)
static inline struct lstack_link *lstack_top_(const struct lstack *s)
{
return s->top;
}
/**
* lstack_push - add an entry to the top of the stack
* @s: the stack to add the node to
* @e: the item to push
* @member: the lstack_link field of *e
*
* The lstack_link does not need to be initialized; it will be overwritten.
*/
#define lstack_push(s, e, member) \
lstack_push_((s), &((e)->member))
static inline void lstack_push_(struct lstack *s, struct lstack_link *e)
{
e->down = lstack_top_(s);
s->top = e;
}
/**
* lstack_pop - remove and return the entry from the top of the stack
* @s: the stack
* @type: the type of stack entries
* @member: the lstack_link field of @type
*
* Note that this leaves the returned entry's link in an undefined
* state; it can be added to another stack, but not deleted again.
*/
#define lstack_pop(s, type, member) \
lstack_entry(lstack_pop_((s)), type, member)
static inline struct lstack_link *lstack_pop_(struct lstack *s)
{
struct lstack_link *top;
if (lstack_empty(s))
return NULL;
top = lstack_top_(s);
s->top = top->down;
return top;
}
#endif /* CCAN_LSTACK_H */
|
