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 - 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 */