Make lists work

2 files changed, 52 insertions, 30 deletions

diff --git a/src/reflist.c b/src/reflist.c
index f11e3e97..e03376d2 100644
--- a/src/reflist.c
+++ b/src/reflist.c
@@ -12,6 +12,7 @@
 
 #include <stdlib.h>
 #include <assert.h>
+#include <stdio.h>
 
 #include "reflist.h"
 
@@ -316,6 +317,41 @@ Reflection *add_refl(RefList *list, INDICES)
 
 /********************************** Deletion **********************************/
 
+static void lr_delete(Reflection *refl, int side)
+{
+	int other = 1-side;
+	int i;
+	Reflection *pre;
+
+	pre = refl->child[side];
+	while ( pre->child[other] != NULL ) pre = pre->child[other];
+
+	assert(refl->next == NULL); /* Should have been */
+	assert(refl->prev == NULL); /*  caught above. */
+
+	refl->data = pre->data;
+	refl->serial = pre->serial;
+
+	/* If the predecessor node had duplicates, we need to
+	 * fix things up. */
+	assert(pre->prev == NULL);
+	refl->next = pre->next;
+	if ( pre->next != NULL ) {
+		refl->next->prev = refl;
+	}
+
+	for ( i=0; i<2; i++ ) {
+		if ( pre->parent->child[i] == pre ) {
+			pre->parent->child[i] = pre->child[side];
+		}
+	}
+	if ( pre->child[side] != NULL ) {
+		pre->child[side]->parent = pre->parent;
+	}
+	free(pre);
+}
+
+
 void delete_refl(Reflection *refl)
 {
 	int i;
@@ -323,6 +359,7 @@ void delete_refl(Reflection *refl)
 	/* Is this a duplicate, and not the first one? */
 	if ( refl->prev != NULL ) {
 		refl->prev->next = refl->next;
+		if ( refl->next != NULL ) refl->next->prev = refl->prev;
 		free(refl);
 		return;
 	}
@@ -330,13 +367,12 @@ void delete_refl(Reflection *refl)
 	/* Is this the first duplicate of many? */
 	if ( refl->next != NULL ) {
 
-		refl->next->parent = refl->parent;
-		refl->next->child[0] = refl->child[0];
-		refl->next->child[1] = refl->child[1];
 		assert(refl->next->prev == refl);
+		refl->next->parent = refl->parent;
 		refl->next->prev = NULL;
 
 		for ( i=0; i<2; i++ ) {
+			refl->next->child[i] = refl->child[i];
 			if ( refl->parent->child[i] == refl ) {
 				refl->parent->child[i] = refl->next;
 			}
@@ -354,27 +390,11 @@ void delete_refl(Reflection *refl)
 	/* Two child nodes? */
 	if ( (refl->child[0] != NULL) && (refl->child[1] != NULL ) ) {
 
-		//if ( random() > RAND_MAX/2 ) {
-
-			Reflection *pre = refl->child[0];
-			while ( pre->child[1] != NULL ) pre = pre->child[1];
-
-			refl->data = pre->data;
-			refl->serial = pre->serial;
-			if ( refl->next != NULL ) refl->next->prev = refl;
-			delete_refl(pre);
-
-		//} else {
-
-		//	Reflection *pre = refl->child[1];
-		//	while ( pre->child[0] != NULL ) pre = pre->child[0];
-
-		//	refl->data = pre->data;
-		//	refl->serial = pre->serial;
-		//	if ( refl->next != NULL ) refl->next->prev = refl;
-		//	delete_refl(pre);
-
-		//}
+		if ( random() > RAND_MAX/2 ) {
+			lr_delete(refl, 0);
+		} else {
+			lr_delete(refl, 1);
+		}
 
 	} else if ( refl->child[0] != NULL ) {
 
@@ -401,6 +421,11 @@ void delete_refl(Reflection *refl)
 	} else {
 
 		/* Leaf node */
+		for ( i=0; i<2; i++ ) {
+			if ( refl->parent->child[i] == refl ) {
+				refl->parent->child[i] = NULL;
+			}
+		}
 		free(refl);
 
 	}
diff --git a/tests/list_check.c b/tests/list_check.c
index 5e593d0f..1292d114 100644
--- a/tests/list_check.c
+++ b/tests/list_check.c
@@ -53,6 +53,7 @@ static int test_lists(int num_items)
 
 		int j;
 		int duplicate = 0;
+		Reflection *refl;
 
 		if ( random() > RAND_MAX/2 ) {
 			h = RANDOM_INDEX;
@@ -78,7 +79,7 @@ static int test_lists(int num_items)
 			}
 		}
 
-		add_refl(list, h, k, l);
+		refl = add_refl(list, h, k, l);
 		check[i].h = h;
 		check[i].k = k;
 		check[i].l = l;
@@ -86,10 +87,6 @@ static int test_lists(int num_items)
 		check[i].dup = duplicate;
 		check[i].found = 0;
 
-		if ( (h==-45) && (k==55) && (l==73)) {
-			printf("added, now %i %i\n", check[i].dup, i);
-		}
-
 	}
 
 	/* Iterate over the list and check we find everything */
@@ -232,7 +229,7 @@ int main(int argc, char *argv[])
 	printf("Running list test...");
 	fflush(stdout);
 
-	for ( i=0; i<1; i++ ) {
+	for ( i=0; i<100; i++ ) {
 		if ( test_lists(4096*random()/RAND_MAX) ) return 1;
 	}