Return to slists.h CVS log

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

bird 1.6.3

    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