Return to slists.c CVS log

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

Annotation of embedaddon/bird2/lib/slists.c, revision 1.1.1.1

1.1       misho       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: }