aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/reflist.c73
-rw-r--r--tests/list_check.c9
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;
}