lib/slists.h

   1 /*
   2  *      BIRD Library -- Safe Linked Lists
   3  *
   4  *      (c) 1998 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #ifndef _BIRD_SLISTS_H_
  10 #define _BIRD_SLISTS_H_
  11
  12 /*
  13  *  These linked lists work in a way similar to standard lists defined
  14  *  in lib/lists.h, but in addition to all usual list functions they
  15  *  provide fast deletion/insertion/everything-safe asynchronous
  16  *  walking.
  17  *
  18  *  Example:
  19  *              slist l;
  20  *              siterator i;
  21  *              snode *n;
  22  *
  23  *              s_init(&i, &l);         // Initialize iteration
  24  *              ...
  25  *              n = s_get(&i);          // Some time later, fetch present
  26  *                                      // value of the iterator and unlink it
  27  *                                      // from the list.
  28  *              while (n->next) {
  29  *                   ...
  30  *                   if (decided_to_stop) {
  31  *                      s_put(&i, n);   // Store current position (maybe even
  32  *                                      // that we stay at list end)
  33  *                      return;         // and return
  34  *                   }
  35  *                   ...
  36  *              }
  37  *              // After finishing, don't link the iterator back
  38  */
  39
  40 typedef struct snode {
  41   struct snode *next, *prev;
  42   struct siterator *readers;
  43 } snode;
  44
  45 typedef struct slist {                  /* In fact two overlayed snodes */
  46   struct snode *head, *null, *tail;
  47   struct siterator *tail_readers;
  48 } slist;
  49
  50 typedef struct siterator {
  51   /*
  52    * Caution: Layout of this structure depends hard on layout of the
  53    *          snode. Our `next' must be at position of snode `readers'
  54    *          field, our `null' must be at position of `prev' and it must
  55    *          contain NULL in order to distinguish between siterator
  56    *          and snode (snodes with NULL `prev' field never carry
  57    *          iterators). You are not expected to understand this.
  58    */
  59   struct siterator *prev, *null, *next;
  60   /*
  61    * For recently merged nodes this can be NULL, but then it's NULL
  62    * for all successors as well. This is done to speed up iterator
  63    * merging when there are lots of deletions.
  64    */
  65   snode *node;
  66 } siterator;
  67
  68 #define SNODE (snode *)
  69 #define SHEAD(list) ((void *)((list).head))
  70 #define STAIL(list) ((void *)((list).tail))
  71 #define SNODE_NEXT(n) ((void *)((SNODE (n))->next))
  72 #define SNODE_VALID(n) ((SNODE (n))->next)
  73
  74 #define WALK_SLIST(n,list) for(n=SHEAD(list); SNODE_VALID(n); n=SNODE_NEXT(n))
  75 #define WALK_SLIST_DELSAFE(n,nxt,list) \
  76      for(n=SHEAD(list); nxt=SNODE_NEXT(n); n=(void *) nxt)
  77 #define EMPTY_SLIST(list) (!(list).head->next)
  78
  79 void s_add_tail(slist *, snode *);
  80 void s_add_head(slist *, snode *);
  81 void s_rem_node(snode *);
  82 void s_add_tail_list(slist *, slist *);
  83 void s_init_list(slist *);
  84 void s_insert_node(snode *, snode *);
  85
  86 snode *s_get(siterator *);
  87 void s_put(siterator *, snode *n);
  88 static inline void s_init(siterator *i, slist *l) { s_put(i, SHEAD(*l)); }
  89 static inline int s_is_used(siterator *i) { return (i->prev != NULL); }
  90
  91 #endif