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/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_from_top - initialize a stack with a given top element
  55  * @s: the lstack to initialize
  56  * @e: pointer to the top element of the new stack
  57  * @member: member of the element containing the lstack_link
  58  *
  59  * USE WITH CAUTION: This is for handling unusual cases where you have
  60  * a pointer to an element in a previously constructed stack but can't
  61  * conveniently pass around a normal struct lstack.  Usually you
  62  * should use lstack_init().
  63  *
  64  * Example:
  65  *      LSTACK(stack1);
  66  *      struct lstack stack2;
  67  *      struct element {
  68  *              int value;
  69  *              struct lstack_link link;
  70  *      } el;
  71  *
  72  *      lstack_push(&stack1, &el, link);
  73  *
  74  *      lstack_init_from_top(&stack2,
  75  *                           lstack_top(&stack1, struct element, link), link);
  76  */
  77 #define lstack_init_from_top(s, e, member) \
  78         (lstack_init_((s), &(e)->member))
  79
  80 /**
  81  * lstack_init - initialize a stack
  82  * @h: the lstack to set to an empty stack
  83  *
  84  * Example:
  85  *      struct lstack *sp = malloc(sizeof(*sp));
  86  *      lstack_init(sp);
  87  */
  88 #define lstack_init(s) \
  89         (lstack_init_((s), NULL))
  90 static inline void lstack_init_(struct lstack *s, struct lstack_link *top)
  91 {
  92         s->top = top;
  93 }
  94
  95 /**
  96  * lstack_empty - is a stack empty?
  97  * @s: the stack
  98  *
  99  * If the stack is empty, returns true.
 100  *
 101  * Example:
 102  *      assert(lstack_empty(sp));
 103  */
 104 static inline bool lstack_empty(const struct lstack *s)
 105 {
 106         return (s->top == NULL);
 107 }
 108
 109 /**
 110  * lstack_entry - convert an lstack_link back into the structure containing it.
 111  * @e: the lstack_link
 112  * @type: the type of the entry
 113  * @member: the lstack_link member of the type
 114  *
 115  * Example:
 116  *      struct stacker {
 117  *              char *name;
 118  *              struct lstack_link sl;
 119  *      } st;
 120  *      assert(lstack_entry(&st.sl, struct stacker, sl) == &st);
 121  */
 122 #define lstack_entry(n, type, member) container_of_or_null(n, type, member)
 123
 124 /**
 125  * lstack_top - get top entry in a stack
 126  * @s: the stack
 127  * @type: the type of stack entries
 128  * @member: the lstack_link entry
 129  *
 130  * If the stack is empty, returns NULL.
 131  *
 132  * Example:
 133  *      struct stacker *t;
 134  *
 135  *      t = lstack_top(sp, struct stacker, sl);
 136  *      assert(lstack_pop(sp, struct stacker, sl) == t);
 137  */
 138 #define lstack_top(s, type, member) \
 139         lstack_entry(lstack_top_((s)), type, member)
 140 static inline struct lstack_link *lstack_top_(const struct lstack *s)
 141 {
 142         return s->top;
 143 }
 144
 145 /**
 146  * lstack_push - add an entry to the top of the stack
 147  * @s: the stack to add the node to
 148  * @e: the item to push
 149  * @member: the lstack_link field of *e
 150  *
 151  * The lstack_link does not need to be initialized; it will be overwritten.
 152  */
 153 #define lstack_push(s, e, member) \
 154         lstack_push_((s), &((e)->member))
 155 static inline void lstack_push_(struct lstack *s, struct lstack_link *e)
 156 {
 157         e->down = lstack_top_(s);
 158         s->top = e;
 159 }
 160
 161 /**
 162  * lstack_pop - remove and return the entry from the top of the stack
 163  * @s: the stack
 164  * @type: the type of stack entries
 165  * @member: the lstack_link field of @type
 166  *
 167  * Note that this leaves the returned entry's link in an undefined
 168  * state; it can be added to another stack, but not deleted again.
 169  */
 170 #define lstack_pop(s, type, member) \
 171         lstack_entry(lstack_pop_((s)), type, member)
 172 static inline struct lstack_link *lstack_pop_(struct lstack *s)
 173 {
 174         struct lstack_link *top;
 175
 176         if (lstack_empty(s))
 177                 return NULL;
 178
 179         top = lstack_top_(s);
 180         s->top = top->down;
 181         return top;
 182 }
 183
 184 #endif /* CCAN_LSTACK_H */