summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/lists.c61
1 files changed, 61 insertions, 0 deletions
diff --git a/lib/lists.c b/lib/lists.c
index 4a48d3b7..c162a991 100644
--- a/lib/lists.c
+++ b/lib/lists.c
@@ -29,6 +29,42 @@
#include "nest/bird.h"
#include "lib/lists.h"
+LIST_INLINE int
+check_list(list *l, node *n)
+{
+ if (!l)
+ {
+ ASSERT_DIE(n);
+ ASSERT_DIE(n->prev);
+
+ do { n = n->prev; } while (n->prev);
+
+ l = SKIP_BACK(list, head_node, n);
+ }
+
+ int seen = 0;
+
+ ASSERT_DIE(l->null == NULL);
+ ASSERT_DIE(l->head != NULL);
+ ASSERT_DIE(l->tail != NULL);
+
+ node *prev = &l->head_node, *cur = l->head, *next = l->head->next;
+ while (next)
+ {
+ if (cur == n)
+ seen++;
+ ASSERT_DIE(cur->prev == prev);
+ prev = cur;
+ cur = next;
+ next = next->next;
+ }
+
+ ASSERT_DIE(cur == &(l->tail_node));
+ ASSERT_DIE(!n || (seen == 1));
+
+ return 1;
+}
+
/**
* add_tail - append a node to a list
* @l: linked list
@@ -39,6 +75,10 @@
LIST_INLINE void
add_tail(list *l, node *n)
{
+ EXPENSIVE_CHECK(check_list(l, NULL));
+ ASSUME(n->prev == NULL);
+ ASSUME(n->next == NULL);
+
node *z = l->tail;
n->next = &l->tail_node;
@@ -57,6 +97,10 @@ add_tail(list *l, node *n)
LIST_INLINE void
add_head(list *l, node *n)
{
+ EXPENSIVE_CHECK(check_list(l, NULL));
+ ASSUME(n->prev == NULL);
+ ASSUME(n->next == NULL);
+
node *z = l->head;
n->next = z;
@@ -76,6 +120,10 @@ add_head(list *l, node *n)
LIST_INLINE void
insert_node(node *n, node *after)
{
+ EXPENSIVE_CHECK(check_list(l, after));
+ ASSUME(n->prev == NULL);
+ ASSUME(n->next == NULL);
+
node *z = after->next;
n->next = z;
@@ -93,6 +141,8 @@ insert_node(node *n, node *after)
LIST_INLINE void
rem_node(node *n)
{
+ EXPENSIVE_CHECK(check_list(NULL, n));
+
node *z = n->prev;
node *x = n->next;
@@ -116,6 +166,10 @@ rem_node(node *n)
LIST_INLINE void
replace_node(node *old, node *new)
{
+ EXPENSIVE_CHECK(check_list(NULL, old));
+ ASSUME(new->prev == NULL);
+ ASSUME(new->next == NULL);
+
old->next->prev = new;
old->prev->next = new;
@@ -149,6 +203,9 @@ init_list(list *l)
LIST_INLINE void
add_tail_list(list *to, list *l)
{
+ EXPENSIVE_CHECK(check_list(to, NULL));
+ EXPENSIVE_CHECK(check_list(l, NULL));
+
node *p = to->tail;
node *q = l->head;
@@ -157,6 +214,8 @@ add_tail_list(list *to, list *l)
q = l->tail;
q->next = &to->tail_node;
to->tail = q;
+
+ EXPENSIVE_CHECK(check_list(to, NULL));
}
LIST_INLINE uint
@@ -165,6 +224,8 @@ list_length(list *l)
uint len = 0;
node *n;
+ EXPENSIVE_CHECK(check_list(l, NULL));
+
WALK_LIST(n, *l)
len++;