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     ! 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