diff options
| -rw-r--r-- | src/reflist.c | 73 | ||||
| -rw-r--r-- | tests/list_check.c | 9 |
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; } |