Return to slists.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib

bird 1.6.3

    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