lstack: Linked list stack implementation
[ccan] / ccan / lstack / lstack.h
1 /* Licensed under BSD-MIT - see LICENSE file for details */
2 #ifndef CCAN_LSTACK_H
3 #define CCAN_LSTACK_H
4
5 #include <stdbool.h>
6 #include <stdio.h>
7 #include <assert.h>
8
9 #include <ccan/container_of/container_of.h>
10
11 /**
12  * struct lstack_link - a stack link
13  * @down: immedately lower entry in the stack, or NULL if this is the bottom.
14  *
15  * This is used as an entry in a stack.
16  *
17  * Example:
18  *      struct stacker {
19  *              char *name;
20  *              struct lstack_link sl;
21  *      };
22  */
23 struct lstack_link {
24         struct lstack_link *down;
25 };
26
27 /**
28  * struct lstack - a stack
29  * @b: the top of the stack (NULL if empty)
30  */
31 struct lstack {
32         struct lstack_link *top;
33 };
34
35 /**
36  * LSTACK - define and initialize an empty stack
37  * @name: the name of the lstack.
38  *
39  * The LSTACK macro defines an lstack and initializes it to an empty
40  * stack.  It can be prepended by "static" to define a static lstack.
41  *
42  * See also:
43  *      lstack_init()
44  *
45  * Example:
46  *      LSTACK(my_stack);
47  *
48  *      assert(lstack_empty(&my_stack));
49  */
50 #define LSTACK(name) \
51         struct lstack name = { NULL, }
52
53 /**
54  * lstack_init - initialize a stack
55  * @h: the lstack to set to an empty stack
56  *
57  * Example:
58  *      struct lstack *sp = malloc(sizeof(*sp));
59  *      lstack_init(sp);
60  */
61 static inline void lstack_init(struct lstack *s)
62 {
63         s->top = NULL;
64 }
65
66 /**
67  * lstack_empty - is a stack empty?
68  * @s: the stack
69  *
70  * If the stack is empty, returns true.
71  *
72  * Example:
73  *      assert(lstack_empty(sp));
74  */
75 static inline bool lstack_empty(const struct lstack *s)
76 {
77         return (s->top == NULL);
78 }
79
80 /**
81  * lstack_entry - convert an lstack_link back into the structure containing it.
82  * @e: the lstack_link
83  * @type: the type of the entry
84  * @member: the lstack_link member of the type
85  *
86  * Example:
87  *      struct stacker {
88  *              char *name;
89  *              struct lstack_link sl;
90  *      } st;
91  *      assert(lstack_entry(&st.sl, struct stacker, sl) == &st);
92  */
93 #define lstack_entry(n, type, member) container_of_or_null(n, type, member)
94
95 /**
96  * lstack_top - get top entry in a stack
97  * @s: the stack
98  * @type: the type of stack entries
99  * @member: the lstack_link entry
100  *
101  * If the stack is empty, returns NULL.
102  *
103  * Example:
104  *      struct stacker *t;
105  *
106  *      t = lstack_top(sp, struct stacker, sl);
107  *      assert(lstack_pop(sp, struct stacker, sl) == t);
108  */
109 #define lstack_top(s, type, member) \
110         lstack_entry(lstack_top_((s)), type, member)
111 static inline struct lstack_link *lstack_top_(const struct lstack *s)
112 {
113         return s->top;
114 }
115
116 /**
117  * lstack_push - add an entry to the top of the stack
118  * @s: the stack to add the node to
119  * @e: the item to push
120  * @member: the lstack_link field of *e
121  *
122  * The lstack_link does not need to be initialized; it will be overwritten.
123  */
124 #define lstack_push(s, e, member) \
125         lstack_push_((s), &((e)->member))
126 static inline void lstack_push_(struct lstack *s, struct lstack_link *e)
127 {
128         e->down = lstack_top_(s);
129         s->top = e;
130 }
131
132 /**
133  * lstack_pop - remove and return the entry from the top of the stack
134  * @s: the stack
135  * @type: the type of stack entries
136  * @member: the lstack_link field of @type
137  *
138  * Note that this leaves the returned entry's link in an undefined
139  * state; it can be added to another stack, but not deleted again.
140  */
141 #define lstack_pop(s, type, member) \
142         lstack_entry(lstack_pop_((s)), type, member)
143 static inline struct lstack_link *lstack_pop_(struct lstack *s)
144 {
145         struct lstack_link *top;
146
147         if (lstack_empty(s))
148                 return NULL;
149
150         top = lstack_top_(s);
151         s->top = top->down;
152         return top;
153 }
154
155 #endif /* CCAN_LSTACK_H */