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