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