153 lines
2.2 KiB
C
153 lines
2.2 KiB
C
/*
|
|
* BIRD Library -- Safe Linked Lists
|
|
*
|
|
* (c) 1998 Martin Mares <mj@ucw.cz>
|
|
*
|
|
* Can be freely distributed and used under the terms of the GNU GPL.
|
|
*/
|
|
|
|
#define _BIRD_SLISTS_C_
|
|
|
|
#include "nest/bird.h"
|
|
#include "lib/slists.h"
|
|
|
|
static inline void
|
|
s_merge(snode *from, snode *to)
|
|
{
|
|
siterator *f, *g;
|
|
|
|
if (!(f = from->readers))
|
|
return;
|
|
if (!(g = to->readers))
|
|
{
|
|
/* Fast path */
|
|
to->readers = f;
|
|
f->prev = (siterator *) to;
|
|
fixup:
|
|
while (f && f->node)
|
|
{
|
|
f->node = NULL;
|
|
f = f->next;
|
|
}
|
|
return;
|
|
}
|
|
/* Really merging */
|
|
while (g->next)
|
|
g = g->next;
|
|
g->next = f;
|
|
f->prev = g;
|
|
goto fixup;
|
|
}
|
|
|
|
snode *
|
|
s_get(siterator *i)
|
|
{
|
|
siterator *f, *g;
|
|
snode *n;
|
|
|
|
if (!(n = i->node))
|
|
{
|
|
/*
|
|
* No node found. We have to walk the iterator list backwards
|
|
* to find where are we linked.
|
|
*/
|
|
f = i;
|
|
while (!f->null)
|
|
f = f->prev;
|
|
n = (snode *) f;
|
|
}
|
|
f = i->prev; /* Maybe the snode itself */
|
|
g = i->next;
|
|
f->next = g;
|
|
if (g)
|
|
g->prev = f;
|
|
|
|
i->prev = NULL;
|
|
i->next = NULL;
|
|
return n;
|
|
}
|
|
|
|
void
|
|
s_put(siterator *i, snode *n)
|
|
{
|
|
siterator *f;
|
|
|
|
i->node = n;
|
|
if (f = n->readers)
|
|
f->prev = i;
|
|
i->next = f;
|
|
n->readers = i;
|
|
i->prev = (siterator *) n;
|
|
i->null = NULL;
|
|
}
|
|
|
|
void
|
|
s_add_tail(slist *l, snode *n)
|
|
{
|
|
snode *z = l->tail;
|
|
|
|
n->next = (snode *) &l->null;
|
|
n->prev = z;
|
|
z->next = n;
|
|
l->tail = n;
|
|
n->readers = NULL;
|
|
}
|
|
|
|
void
|
|
s_add_head(slist *l, snode *n)
|
|
{
|
|
snode *z = l->head;
|
|
|
|
n->next = z;
|
|
n->prev = (snode *) &l->head;
|
|
z->prev = n;
|
|
l->head = n;
|
|
n->readers = NULL;
|
|
}
|
|
|
|
void
|
|
s_insert_node(snode *n, snode *after)
|
|
{
|
|
snode *z = after->next;
|
|
|
|
n->next = z;
|
|
n->prev = after;
|
|
after->next = n;
|
|
z->prev = n;
|
|
n->readers = NULL;
|
|
}
|
|
|
|
void
|
|
s_rem_node(snode *n)
|
|
{
|
|
snode *z = n->prev;
|
|
snode *x = n->next;
|
|
|
|
z->next = x;
|
|
x->prev = z;
|
|
s_merge(n, x);
|
|
}
|
|
|
|
void
|
|
s_init_list(slist *l)
|
|
{
|
|
l->head = (snode *) &l->null;
|
|
l->null = NULL;
|
|
l->tail = (snode *) &l->head;
|
|
l->tail_readers = NULL;
|
|
}
|
|
|
|
void
|
|
s_add_tail_list(slist *to, slist *l)
|
|
{
|
|
snode *p = to->tail;
|
|
snode *q = l->head;
|
|
|
|
p->next = q;
|
|
q->prev = p;
|
|
q = l->tail;
|
|
q->next = (snode *) &to->null;
|
|
to->tail = q;
|
|
s_merge((snode *) &l->null, (snode *) &to->null);
|
|
}
|