git.ozlabs.org Git - ccan/blob - 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/tcon/tcon.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 (internal type)
  29  * @b: the top of the stack (NULL if empty)
  30  */
  31 struct lstack_ {
  32         struct lstack_link *top;
  33 };
  34
  35 /**
  36  * LSTACK - declare a stack
  37  * @type: the type of elements in the stack
  38  * @link: the field containing the lstack_link in @type
  39  *
  40  * The LSTACK macro declares an lstack.  It can be prepended by
  41  * "static" to define a static lstack.  The stack begins in undefined
  42  * state, you must either initialize with LSTACK_INIT, or call
  43  * lstack_init() before using it.
  44  *
  45  * See also:
  46  *      lstack_init()
  47  *
  48  * Example:
  49  *      struct element {
  50  *              int value;
  51  *              struct lstack_link link;
  52  *      };
  53  *      LSTACK(struct element, link) my_stack;
  54  */
  55 #define LSTACK(etype, link)                                             \
  56         TCON_WRAP(struct lstack_,                                       \
  57                   TCON_CONTAINER(canary, etype, link))
  58
  59 /**
  60  * LSTACK_INIT - initializer for an empty stack
  61  *
  62  * The LSTACK_INIT macro returns a suitable initializer for a stack
  63  * defined with LSTACK.
  64  *
  65  * Example:
  66  *      struct element {
  67  *              int value;
  68  *              struct lstack_link link;
  69  *      };
  70  *      LSTACK(struct element, link) my_stack = LSTACK_INIT;
  71  *
  72  *      assert(lstack_empty(&my_stack));
  73  */
  74 #define LSTACK_INIT                             \
  75         TCON_WRAP_INIT({ NULL, })
  76
  77 /**
  78  * lstack_entry - convert an lstack_link back into the structure containing it.
  79  * @s: the stack
  80  * @l: the lstack_link
  81  *
  82  * Example:
  83  *      struct element {
  84  *              int value;
  85  *              struct lstack_link link;
  86  *      } e;
  87  *      LSTACK(struct element, link) my_stack;
  88  *      assert(lstack_entry(&my_stack, &e.link) == &e);
  89  */
  90 #define lstack_entry(s_, l_) tcon_container_of((s_), canary, (l_))
  91
  92
  93 /**
  94  * lstack_init_from_top - initialize a stack with a given top element
  95  * @s: the lstack to initialize
  96  * @e: pointer to the top element of the new stack
  97  *
  98  * USE WITH CAUTION: This is for handling unusual cases where you have
  99  * a pointer to an element in a previously constructed stack but can't
 100  * conveniently pass around a normal struct lstack.  Usually you
 101  * should use lstack_init().
 102  *
 103  * Example:
 104  *      struct element {
 105  *              int value;
 106  *              struct lstack_link link;
 107  *      } e;
 108  *      LSTACK(struct element, link) stack1 = LSTACK_INIT;
 109  *      LSTACK(struct element, link) stack2;
 110  *
 111  *      lstack_push(&stack1, &e);
 112  *
 113  *      lstack_init_from_top(&stack2, lstack_top(&stack1));
 114  */
 115 #define lstack_init_from_top(s_, e_)    \
 116         (lstack_init_(tcon_unwrap(s_), tcon_member_of((s_), canary, (e_))))
 117
 118 /**
 119  * lstack_init - initialize a stack
 120  * @h: the lstack to set to an empty stack
 121  *
 122  * Example:
 123  *      struct element {
 124  *              int value;
 125  *              struct lstack_link link;
 126  *      };
 127  *      LSTACK(struct element, link) *sp = malloc(sizeof(*sp));
 128  *      lstack_init(sp);
 129  */
 130 #define lstack_init(s_) \
 131         (lstack_init_(tcon_unwrap(s_), NULL))
 132 static inline void lstack_init_(struct lstack_ *s, struct lstack_link *top)
 133 {
 134         s->top = top;
 135 }
 136
 137 /**
 138  * lstack_empty - is a stack empty?
 139  * @s: the stack
 140  *
 141  * If the stack is empty, returns true.
 142  */
 143 #define lstack_empty(s_) \
 144         lstack_empty_(tcon_unwrap(s_))
 145 static inline bool lstack_empty_(const struct lstack_ *s)
 146 {
 147         return (s->top == NULL);
 148 }
 149
 150 /**
 151  * lstack_top - get top entry in a stack
 152  * @s: the stack
 153  *
 154  * If the stack is empty, returns NULL.
 155  *
 156  * Example:
 157  *      struct element *t;
 158  *
 159  *      t = lstack_top(sp);
 160  *      assert(lstack_pop(sp) == t);
 161  */
 162 #define lstack_top(s_) \
 163         lstack_entry((s_), lstack_top_(tcon_unwrap(s_)))
 164 static inline struct lstack_link *lstack_top_(const struct lstack_ *s)
 165 {
 166         return s->top;
 167 }
 168
 169 /**
 170  * lstack_push - add an entry to the top of the stack
 171  * @s: the stack to add the node to
 172  * @e: the item to push
 173  *
 174  * The lstack_link does not need to be initialized; it will be overwritten.
 175  */
 176 #define lstack_push(s_, e_) \
 177         lstack_push_(tcon_unwrap(s_), tcon_member_of((s_), canary, (e_)))
 178 static inline void lstack_push_(struct lstack_ *s, struct lstack_link *e)
 179 {
 180         e->down = lstack_top_(s);
 181         s->top = e;
 182 }
 183
 184 /**
 185  * lstack_pop - remove and return the entry from the top of the stack
 186  * @s: the stack
 187  *
 188  * Note that this leaves the returned entry's link in an undefined
 189  * state; it can be added to another stack, but not deleted again.
 190  */
 191 #define lstack_pop(s_)                                  \
 192         lstack_entry((s_), lstack_pop_(tcon_unwrap((s_))))
 193 static inline struct lstack_link *lstack_pop_(struct lstack_ *s)
 194 {
 195         struct lstack_link *top;
 196
 197         if (lstack_empty_(s))
 198                 return NULL;
 199
 200         top = lstack_top_(s);
 201         s->top = top->down;
 202         return top;
 203 }
 204
 205 #endif /* CCAN_LSTACK_H */