[thirdparty/bird.git] / lib / slists.h

/*
 *	BIRD Library -- Safe Linked Lists
 *
 *	(c) 1998 Martin Mares <mj@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#ifndef _BIRD_SLISTS_H_
#define _BIRD_SLISTS_H_

/*
 *  These linked lists work in a way similar to standard lists defined
 *  in lib/lists.h, but in addition to all usual list functions they
 *  provide fast deletion/insertion/everything-safe asynchronous
 *  walking.
 *
 *  Example:
 *		slist l;
 *		siterator i;
 *		snode *n;
 *
 *	       	s_init(&i, &l);		// Initialize iteration
 *		...
 *		n = s_get(&i);		// Some time later, fetch present
 *					// value of the iterator and unlink it
 *					// from the list.
 *		while (n->next) {
 *		     ...
 *		     if (decided_to_stop) {
 *			s_put(&i, n);	// Store current position (maybe even
 *					// that we stay at list end)
 *			return;		// and return
 *		     }
 *		     ...
 *		}
 *		// After finishing, don't link the iterator back
 */

typedef struct snode {
  struct snode *next, *prev;
  struct siterator *readers;
} snode;

typedef struct slist {			/* In fact two overlayed snodes */
  struct snode *head, *null, *tail;
  struct siterator *tail_readers;
} slist;

typedef struct siterator {
  /*
   * Caution: Layout of this structure depends hard on layout of the
   *	      snode. Our `next' must be at position of snode `readers'
   *	      field, our `null' must be at position of `prev' and it must
   *	      contain NULL in order to distinguish between siterator
   *	      and snode (snodes with NULL `prev' field never carry
   *	      iterators). You are not expected to understand this.
   */
  struct siterator *prev, *null, *next;
  /*
   * For recently merged nodes this can be NULL, but then it's NULL
   * for all successors as well. This is done to speed up iterator
   * merging when there are lots of deletions.
   */
  snode *node;
} siterator;

#define SNODE (snode *)
#define SHEAD(list) ((void *)((list).head))
#define STAIL(list) ((void *)((list).tail))
#define SNODE_NEXT(n) ((void *)((SNODE (n))->next))
#define SNODE_VALID(n) ((SNODE (n))->next)

#define WALK_SLIST(n,list) for(n=SHEAD(list); SNODE_VALID(n); n=SNODE_NEXT(n))
#define WALK_SLIST_DELSAFE(n,nxt,list) \
     for(n=SHEAD(list); nxt=SNODE_NEXT(n); n=(void *) nxt)
#define EMPTY_SLIST(list) (!(list).head->next)

void s_add_tail(slist *, snode *);
void s_add_head(slist *, snode *);
void s_rem_node(snode *);
void s_add_tail_list(slist *, slist *);
void s_init_list(slist *);
void s_insert_node(snode *, snode *);

snode *s_get(siterator *);
void s_put(siterator *, snode *n);
static inline void s_init(siterator *i, slist *l) { s_put(i, SHEAD(*l)); }
static inline int s_is_used(siterator *i) { return (i->prev != NULL); }

#endif
Commit	Line	Data
a05406e6 MM	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))
70945cb6 OZ	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))
a05406e6	75	#define WALK_SLIST_DELSAFE(n,nxt,list) \
70945cb6	76	for(n=SHEAD(list); nxt=SNODE_NEXT(n); n=(void *) nxt)
a05406e6 MM	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)); }
02a9eeeb	89	static inline int s_is_used(siterator *i) { return (i->prev != NULL); }
a05406e6 MM	90
a05406e6 MM	91	#endif