Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / slists.h @ 6b3f1a54

History | View | Annotate | Download (2.67 KB)

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