List debugging

2 files changed, 54 insertions, 64 deletions

diff --git a/src/reflist.c b/src/reflist.c
index 80179f63..d297c4d0 100644
--- a/src/reflist.c
+++ b/src/reflist.c
@@ -62,15 +62,32 @@ struct _reflist {
 
 #define SERIAL(h, k, l) (((h)+256)*512*512 + ((k)+256)*512 + ((l)+256))
 
+
 /**************************** Creation / deletion *****************************/
 
+static Reflection *new_node(unsigned int serial)
+{
+	Reflection *new;
+
+	new = calloc(1, sizeof(struct _reflection));
+	new->serial = serial;
+	new->next = NULL;
+	new->child[0] = NULL;
+	new->child[1] = NULL;
+
+	return new;
+}
+
+
 /* Create a reflection list */
 RefList *reflist_new()
 {
 	RefList *new;
 
 	new = malloc(sizeof(struct _reflist));
-	new->head = NULL;
+
+	/* Create pseudo-root with invalid indices */
+	new->head = new_node(SERIAL(257, 257, 257));
 
 	return new;
 }
@@ -247,48 +264,34 @@ void set_scalable(Reflection *refl, int scalable)
 
 /********************************* Insertion **********************************/
 
-static int recursive_insert(Reflection *refl, Reflection *new)
+static void insert_node(Reflection *head, Reflection *new)
 {
-	int i;
-
-	if ( refl->serial == new->serial ) {
+	Reflection *refl;
 
-		/* Found a reflection with identical indices */
-		do {
-			refl = refl->next;
-		} while ( refl != NULL );
-		refl->next = new;
-		new->parent = refl;
+	refl = head;
 
-		return 1;
-	}
-
-	for ( i=0; i<2; i++ ) {
+	while ( refl != NULL ) {
 
 		if ( new->serial < refl->serial ) {
 			if ( refl->child[0] != NULL ) {
-				return recursive_insert(refl->child[0], new);
+				refl = refl->child[0];
 			} else {
 				refl->child[0] = new;
 				new->parent = refl;
-				return 1;
+				return;
 			}
-		}
-
-		if ( new->serial >= refl->serial ) {
+		} else {
 			if ( refl->child[1] != NULL ) {
-				return recursive_insert(refl->child[1], new);
+				refl = refl->child[1];
 			} else {
 				refl->child[1] = new;
 				new->parent = refl;
-				return 1;
+				return;
 			}
 		}
 
 
 	}
-
-	return 0;
 }
 
 
@@ -296,18 +299,14 @@ Reflection *add_refl(RefList *list, INDICES)
 {
 	Reflection *new;
 
-	new = calloc(1, sizeof(struct _reflection));
+	new = new_node(SERIAL(h, k, l));
 	new->h = h;  new->k = k,  new->l = l;
-	new->serial = SERIAL(h, k, l);
-	new->next = NULL;
-	new->child[0] = NULL;
-	new->child[1] = NULL;
 
 	if ( list->head == NULL ) {
 		list->head = new;
 		new->parent = NULL;
 	} else {
-		recursive_insert(list->head, new);
+		insert_node(list->head, new);
 	}
 
 	return new;
@@ -336,15 +335,18 @@ void delete_refl(Reflection *refl)
 		if ( random() > RAND_MAX/2 ) {
 
 			*parent_pos = refl->child[0];
+			refl->child[0]->parent = refl->parent;
 
 			/* Now sort out the right child */
-			recursive_insert(refl->child[0], refl->child[1]);
+			insert_node(refl->child[0], refl->child[1]);
+
 		} else {
 
 			*parent_pos = refl->child[1];
+			refl->child[1]->parent = refl->parent;
 
 			/* Now sort out the left child */
-			recursive_insert(refl->child[1], refl->child[0]);
+			insert_node(refl->child[1], refl->child[0]);
 
 		}
 
@@ -352,11 +354,13 @@ void delete_refl(Reflection *refl)
 
 		/* One child, left */
 		*parent_pos = refl->child[0];
+		refl->child[0]->parent = refl->parent;
 
 	} else if (refl->child[1] != NULL ) {
 
 		/* One child, right */
 		*parent_pos = refl->child[1];
+		refl->child[1]->parent = refl->parent;
 
 	} /* else it was just a leaf node */
 
diff --git a/tests/list_check.c b/tests/list_check.c
index be427af0..91d7367d 100644
--- a/tests/list_check.c
+++ b/tests/list_check.c
@@ -38,6 +38,8 @@ static int test_lists(int num_items)
 	RefList *list;
 	int i;
 
+	fprintf(stderr, "Testing with %i items.\n", num_items);
+
 	check = malloc(num_items * sizeof(struct refltemp));
 	list = reflist_new();
 
@@ -47,17 +49,22 @@ static int test_lists(int num_items)
 		int j;
 		int duplicate = 0;
 
-		h = RANDOM_INDEX;
-		k = RANDOM_INDEX;
-		l = RANDOM_INDEX;
+		do {
+			duplicate = 0;
+
+			h = RANDOM_INDEX;
+			k = RANDOM_INDEX;
+			l = RANDOM_INDEX;
 
-		for ( j=0; j<i; j++ ) {
-			if ( (check[j].h == h)
-			  && (check[j].k == k)
-			  && (check[j].l == l) ) {
-				duplicate++;
+			for ( j=0; j<i; j++ ) {
+				if ( (check[j].h == h)
+				  && (check[j].k == k)
+				  && (check[j].l == l) ) {
+					duplicate++;
+				}
 			}
-		}
+
+		} while ( duplicate );
 
 		add_refl(list, h, k, l);
 		check[i].h = h;
@@ -90,28 +97,7 @@ static int test_lists(int num_items)
 
 	}
 
-	for ( i=0; i<num_items/2; i++ ) {
-
-		signed int h, k, l;
-		Reflection *refl;
-
-		h = check[i].h;
-		k = check[i].k;
-		l = check[i].l;
-
-		refl = find_refl(list, h, k, l);
-		if ( refl == NULL ) {
-			fprintf(stderr, "Couldn't find %3i %3i %3i\n", h, k, l);
-			return 1;
-		}
-
-		if ( i<num_items/2 ) {
-			delete_refl(refl);
-			check[i].del = 1;
-		}
-
-	}
-
+	reflist_free(list);
 	free(check);
 
 	return 0;
@@ -122,7 +108,7 @@ int main(int argc, char *argv[])
 	int i;
 
 	for ( i=0; i<100; i++ ) {
-		if ( test_lists(random()) ) return 1;
+		if ( test_lists(4096*random()/RAND_MAX) ) return 1;
 	}
 
 	return 0;