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     ! 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: }