Return to slists.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib

Annotation of embedaddon/bird/lib/slists.h, revision 1.1.1.1

1.1       misho       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