1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Copyright by The HDF Group. *
* Copyright by the Board of Trustees of the University of Illinois. *
* All rights reserved. *
* *
* This file is part of HDF. The full HDF copyright notice, including *
* terms governing use, modification, and redistribution, is contained in *
* the COPYING file, which can be found at the root of the source code *
* distribution tree, or in https://support.hdfgroup.org/ftp/HDF/releases/. *
* If you do not have access to either file, you may request a copy from *
* help@hdfgroup.org. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*
FILE
tree.c
Test HDF Threaded-Balanced-Binary Tree (tbbt) routines.
*/
#include <time.h>
#include "tproto.h"
#include "tbbt_priv.h"
#define MAX_TEST_SIZE 31 /* maximum number of elements to insert */
#define NUM_TEST_RUNS 100 /* number of times to insert & remove each size */
#define SEED(s) (srand(s))
#define RandInt(a, b) ((rand() % (((b) - (a)) + 1)) + (a))
static void swap_arr(int32 *arr, intn a, intn b);
intn tcompare(void *k1, void *k2, intn cmparg);
static void
swap_arr(int32 *arr, intn a, intn b)
{
int32 t;
if (a != b) {
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
} /* end if */
} /* end swap_arr() */
intn
tcompare(void *k1, void *k2, intn cmparg)
{
(void)cmparg;
return (intn)((*(int32 *)k1) - (*(int32 *)k2));
}
void
test_tbbt(void)
{
intn test_size;
intn i, j;
int32 ins_arr[MAX_TEST_SIZE];
int32 rem_arr[MAX_TEST_SIZE];
intn t;
TBBT_TREE *tree;
void **r;
t = (intn)time(NULL);
SEED((uintn)t);
for (test_size = 3; test_size <= MAX_TEST_SIZE; test_size++) {
MESSAGE(7, printf("\nTesting trees with %d elements\n", test_size););
MESSAGE(8, printf("Testing tree #:"););
for (j = 0; j < NUM_TEST_RUNS; j++) {
MESSAGE(8, printf(" %d", j););
for (i = 0; i < test_size; i++) { /* initialize the arrays */
ins_arr[i] = i;
rem_arr[i] = i;
} /* end for */
for (i = 0; i < test_size; i++) { /* shuffle the arrays */
t = RandInt(i, test_size - 1);
swap_arr(ins_arr, i, t);
t = RandInt(i, test_size - 1);
swap_arr(rem_arr, i, t);
} /* end for */
if (Verbosity > 9) {
printf("ins_arr: \n");
for (i = 0; i < test_size; i++) /* print the arrays */
printf("%d \n", (int)ins_arr[i]);
printf("\nrem_arr: \n");
for (i = 0; i < test_size; i++) /* print the arrays */
printf("%d \n", (int)rem_arr[i]);
printf("\n");
} /* end if */
tree = tbbtdmake(tcompare, sizeof(int32), 0);
for (i = 0; i < test_size; i++) {
MESSAGE(9, printf("inserting %d\n", (int)ins_arr[i]););
tbbtdins(tree, (void *)&ins_arr[i], NULL);
MESSAGE(9, tbbtdump(tree, -1););
}
MESSAGE(9, tbbtdump(tree, -1););
for (i = 0; i < test_size; i++) {
int32 key;
key = rem_arr[i];
r = (void **)tbbtdfind(tree, (void *)&key, NULL);
MESSAGE(9, printf("removing %d\n", (int)key););
tbbtrem((TBBT_NODE **)tree, (TBBT_NODE *)r, NULL);
MESSAGE(9, tbbtdump(tree, -1););
} /* end for */
tbbtdfree(tree, NULL, NULL);
} /* end for */
} /* end for */
} /* end test_tbbt() */
|
