Annotation of embedaddon/bird/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: }
! 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
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to slists.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib