bird/lib/slists.h

92 lines
2.7 KiB
C
Raw Permalink Normal View History

/*
* 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))
2014-06-26 17:58:57 +08:00
#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) \
2014-06-26 17:58:57 +08:00
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)); }
2009-01-12 21:40:21 +08:00
static inline int s_is_used(siterator *i) { return (i->prev != NULL); }
#endif