Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.24 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
#define _BIRD_SLISTS_C_
10

    
11
#include "nest/bird.h"
12
#include "lib/slists.h"
13

    
14
static inline void
15
s_merge(snode *from, snode *to)
16
{
17
  siterator *f, *g;
18

    
19
  if (!(f = from->readers))
20
    return;
21
  if (!(g = to->readers))
22
    {
23
      /* Fast path */
24
      to->readers = f;
25
      f->prev = (siterator *) to;
26
    fixup:
27
      while (f && f->node)
28
        {
29
          f->node = NULL;
30
          f = f->next;
31
        }
32
      return;
33
    }
34
  /* Really merging */
35
  while (g->next)
36
    g = g->next;
37
  g->next = f;
38
  f->prev = g;
39
  goto fixup;
40
}
41

    
42
snode *
43
s_get(siterator *i)
44
{
45
  siterator *f, *g;
46
  snode *n;
47

    
48
  if (!(n = i->node))
49
    {
50
      /*
51
       * No node found. We have to walk the iterator list backwards
52
       * to find where are we linked.
53
       */
54
      f = i;
55
      while (!f->null)
56
        f = f->prev;
57
      n = (snode *) f;
58
    }
59
  f = i->prev;                                /* Maybe the snode itself */
60
  g = i->next;
61
  f->next = g;
62
  if (g)
63
    g->prev = f;
64

    
65
  i->prev = NULL;
66
  i->next = NULL;
67
  return n;
68
}
69

    
70
void
71
s_put(siterator *i, snode *n)
72
{
73
  siterator *f;
74

    
75
  i->node = n;
76
  if (f = n->readers)
77
    f->prev = i;
78
  i->next = f;
79
  n->readers = i;
80
  i->prev = (siterator *) n;
81
  i->null = NULL;
82
}
83

    
84
void
85
s_add_tail(slist *l, snode *n)
86
{
87
  snode *z = l->tail;
88

    
89
  n->next = (snode *) &l->null;
90
  n->prev = z;
91
  z->next = n;
92
  l->tail = n;
93
  n->readers = NULL;
94
}
95

    
96
void
97
s_add_head(slist *l, snode *n)
98
{
99
  snode *z = l->head;
100

    
101
  n->next = z;
102
  n->prev = (snode *) &l->head;
103
  z->prev = n;
104
  l->head = n;
105
  n->readers = NULL;
106
}
107

    
108
void
109
s_insert_node(snode *n, snode *after)
110
{
111
  snode *z = after->next;
112

    
113
  n->next = z;
114
  n->prev = after;
115
  after->next = n;
116
  z->prev = n;
117
  n->readers = NULL;
118
}
119

    
120
void
121
s_rem_node(snode *n)
122
{
123
  snode *z = n->prev;
124
  snode *x = n->next;
125

    
126
  z->next = x;
127
  x->prev = z;
128
  s_merge(n, x);
129
}
130

    
131
void
132
s_init_list(slist *l)
133
{
134
  l->head = (snode *) &l->null;
135
  l->null = NULL;
136
  l->tail = (snode *) &l->head;
137
  l->tail_readers = NULL;
138
}
139

    
140
void
141
s_add_tail_list(slist *to, slist *l)
142
{
143
  snode *p = to->tail;
144
  snode *q = l->head;
145

    
146
  p->next = q;
147
  q->prev = p;
148
  q = l->tail;
149
  q->next = (snode *) &to->null;
150
  to->tail = q;
151
  s_merge((snode *) &l->null, (snode *) &to->null);
152
}