Statistics
| Branch: | Revision:

iof-bird-daemon / lib / slists.c @ 094d2bdb

History | View | Annotate | Download (3.44 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
}
153

    
154
#ifdef TEST
155

    
156
#include "lib/resource.h"
157
#include <stdio.h>
158

    
159
void dump(char *c, slist *a)
160
{
161
  snode *x;
162

    
163
  puts(c);
164
  for(x=SHEAD(*a); x; x=x->next)
165
    {
166
      siterator *i, *j;
167
      printf("%p", x);
168
      j = (siterator *) x;
169
      for(i=x->readers; i; i=i->next)
170
        {
171
          if (i->prev != j)
172
            printf(" ???");
173
          j = i;
174
          printf(" [%p:%p]", i, i->node);
175
        }
176
      putchar('\n');
177
    }
178
  puts("---");
179
}
180

    
181
int main(void)
182
{
183
  slist a, b;
184
  snode *x, *y;
185
  siterator i, j;
186

    
187
  s_init_list(&a);
188
  s_init_list(&b);
189
  x = xmalloc(sizeof(*x));
190
  s_add_tail(&a, x);
191
  x = xmalloc(sizeof(*x));
192
  s_add_tail(&a, x);
193
  x = xmalloc(sizeof(*x));
194
  s_add_tail(&a, x);
195
  dump("1", &a);
196

    
197
  s_init(&i, &a);
198
  s_init(&j, &a);
199
  dump("2", &a);
200

    
201
  x = s_get(&i);
202
  printf("Got %p\n", x);
203
  dump("3", &a);
204

    
205
  s_put(&i, x->next);
206
  dump("4", &a);
207

    
208
  y = s_get(&j);
209
  while (y)
210
    {
211
      s_put(&j, y);
212
      dump("5*", &a);
213
      y = s_get(&j)->next;
214
    }
215

    
216
  dump("5 done", &a);
217

    
218
  s_rem_node(a.head->next);
219
  dump("6 (deletion)", &a);
220

    
221
  s_put(&i, s_get(&i)->next);
222
  dump("6 (relink)", &a);
223

    
224
  x = xmalloc(sizeof(*x));
225
  s_add_tail(&b, x);
226
  dump("7 (second list)", &b);
227

    
228
  s_add_tail_list(&b, &a);
229
  dump("8 (after merge)", &b);
230

    
231
  return 0;
232
}
233

    
234
#endif