lib/slists.c

   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