Subversion Repositories PlanixRsrch.SVN

Rev

Rev 341 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
333 7u83 1 
#include <stdarg.h>
324 7u83 2 
#include <stdio.h>
3 
#include <errno.h>
4 
#include <string.h>
5 
#include <time.h>
6 
 
7 
#include <mutests.h>
8 
 
9 
#include "mavl.h"
10 
 
11 
/* Compare function to compare integers */
12 
static int
13 
cmp(const void *v1, const void *v2)
14 
{
15 
	return *((int *)v1) - *((int *)v2);
16 
}
17 
 
18 
static float
19 
calc_depth(int numvals)
20 
{
21 
	int i;
22 
	unsigned int r=1;
23 
	for (i=0; i<64; i++){
24 
		if (r>(unsigned int)numvals)
25 
			return (float)((double)i*1.44);
26 
		r=r<<1;
27 
	}
28 
	return (float)0.0;
29 
}
30 
 
31 
static int
32 
test_mavl(const char * name,int numvals,int type)
33 
{
34 
	int i;
35 
	int insval;
427 7u83 36 
	int exists,existed;
324 7u83 37 
	struct mavl *t;
38 
	int rc;
39 
	float depth, maxdepth;
40 
 
41 
	(void) printf ("Running insert %s: numvals=%d, type=%d\n"
42 
			,name, numvals,type);
43 
 
44 
 
45 
	/* Create a MAVL object which store object of size of int. */
46 
	t = mavl_create(cmp, NULL, sizeof(int));
47 
	mu_assert (t!=NULL, "mavl_create(%s): %s", name,strerror(errno));
48 
 
49 
	srand((unsigned int)time(NULL));
427 7u83 50 
	existed=0;
324 7u83 51 
	for (i = 0; i < numvals; i++) {
52 
		switch (type) {
53 
		case 0:
54 
			insval = rand();
55 
			break;
56 
		case -1:
57 
			insval = numvals-i;
58 
			break;
59 
		default:
60 
			insval = i;
61 
			break;
62 
 
63 
		};
64 
		(void)mavl_insert(t, &insval, &exists);
427 7u83 65 
		if (exists)
66 
			existed++;
324 7u83 67 
	}
68 
	rc = mavl_verify(t);
69 
	mu_assert(rc,"Verify (%s)",name);
70 
 
427 7u83 71 
	mu_assert(t->count+existed == numvals,
72 
			"%s %d != %d",name,t->count+existed, numvals);
324 7u83 73 
 
74 
	depth = (float)mavl_get_depth(t);
75 
	maxdepth = calc_depth(numvals);
76 
	mu_assert(depth < maxdepth,
77 
			"%s Depth %f >= %f",name,depth,maxdepth);
78 
 
79 
	mavl_destroy(t);
80 
	return 1;
81 
}
82 
 
329 7u83 83 
static int
84 
test_mavl_del(const char * name,int numvals,int type)
85 
{
86 
	int i;
87 
	int insval,delval;
427 7u83 88 
	int exists,existed;
329 7u83 89 
	struct mavl *t;
90 
	int rc;
91 
	float depth, maxdepth;
92 
	int * vals;
93 
 
94 
	(void) printf ("Running insert and del %s: numvals=%d, type=%d\n"
95 
			,name, numvals,type);
96 
 
97 
	vals = malloc(sizeof(int)*(size_t)numvals);
98 
	mu_assert(vals != NULL,"%s - allocate vals",
99 
			name);
100 
 
101 
	/* Create a MAVL object which store object of size of int. */
102 
	t = mavl_create(cmp, NULL, sizeof(int));
103 
	mu_assert (t!=NULL, "mavl_create(%s): %s", name,strerror(errno));
104 
 
105 
	srand((unsigned int)time(NULL));
427 7u83 106 
	existed=0;
329 7u83 107 
	for (i = 0; i < numvals; i++) {
108 
		switch (type) {
109 
		case 0:
110 
			insval = rand();
111 
			break;
112 
		case -1:
113 
			insval = numvals-i;
114 
			break;
115 
		default:
116 
			insval = i;
117 
			break;
118 
 
119 
		};
120 
		vals[i]=insval;
121 
		(void)mavl_insert(t, &insval, &exists);
427 7u83 122 
		if (exists)
123 
			existed++;
124 
 
329 7u83 125 
	}
126 
	rc = mavl_verify(t);
127 
	mu_assert(rc,"Verify (%s)",name);
128 
 
427 7u83 129 
	mu_assert(t->count+existed == numvals,
130 
			"%s %d != %d",name,t->count+existed, numvals);
329 7u83 131 
 
132 
	depth = (float)mavl_get_depth(t);
133 
	maxdepth = calc_depth(numvals);
134 
	mu_assert(depth < maxdepth,
135 
			"%s Depth %f >= %f",name,depth,maxdepth);
136 
 
331 7u83 137 
/*	{			FILE * outfile;
329 7u83 138 
			int i1;
139 
			outfile = fopen("error.dat","wt");
140 
			for (i1=0; i1<numvals; i1++){
141 
				fprintf(outfile, "%d ",vals[i1]);
142 
			}
143 
			fclose(outfile);
144 
	}
331 7u83 145 
*/	for (i=0; i<numvals; i++){
329 7u83 146 
		int before_count;
147 
 
148 
		delval = vals[i];
149 
		before_count = t->count;
339 7u83 150 
		(void)mavl_del(t,&delval);
329 7u83 151 
 
152 
		mu_assert(before_count != t->count-1,"%s count %d != %d",
153 
				name, before_count,t->count-1);
154 
 
155 
		depth = (float)mavl_get_depth(t);
156 
		maxdepth = calc_depth(t->count);
157 
 
158 
		if (!(depth<=maxdepth)){
159 
		}
160 
 
161 
		mu_assert(depth <= maxdepth,
162 
			"%s Del Depth %f >= %f (N: %d)",name,depth,maxdepth,t->count);
163 
 
164 
	}
165 
	mavl_destroy(t);
341 7u83 166 
	free(vals);
329 7u83 167 
	return 1;
168 
}
169 
 
170 
 
171 
 
172 
 
173 
 
324 7u83 174 
static int test0(void)
175 
{
176 
	const char * name = "test0";
177 
	int type = 0;
329 7u83 178 
	int i;
427 7u83 179 
 
331 7u83 180 
	for (i=0; i<1000; i++){
329 7u83 181 
		(void)test_mavl(name,i+1,type);
182 
	}
427 7u83 183 
 
324 7u83 184 
	(void)test_mavl(name,1024,type);
185 
	(void)test_mavl(name,31871,type);
186 
	(void)test_mavl(name,123456,type);
187 
	(void)test_mavl(name,1000000,type);
188 
	return 1;
189 
}
190 
 
191 
static int test1(void)
192 
{
193 
	const char * name = "test1";
194 
	int type = -1;
195 
	(void)test_mavl(name,1,type);
196 
	(void)test_mavl(name,2,type);
197 
	(void)test_mavl(name,3,type);
198 
	(void)test_mavl(name,10,type);
199 
	(void)test_mavl(name,1024,type);
200 
	(void)test_mavl(name,31871,type);
201 
	(void)test_mavl(name,123456,type);
202 
	(void)test_mavl(name,1000000,type);
203 
	return 1;
204 
}
205 
 
206 
static int test2(void)
207 
{
208 
	const char * name = "test2";
209 
	int type = 1;
210 
	(void)test_mavl(name,1,type);
211 
	(void)test_mavl(name,2,type);
212 
	(void)test_mavl(name,3,type);
213 
	(void)test_mavl(name,10,type);
214 
	(void)test_mavl(name,1024,type);
215 
	(void)test_mavl(name,31871,type);
216 
	(void)test_mavl(name,123456,type);
217 
	(void)test_mavl(name,1000000,type);
218 
	return 1;
219 
}
220 
 
329 7u83 221 
static int test0_del(void)
222 
{
223 
	int i;
224 
	const char * name = "test0_del";
225 
	int type = 0;
331 7u83 226 
	for(i=0; i<1500; i++)
227 
		(void)test_mavl_del(name,i+1,type);
228 
 
334 7u83 229 
	for (i=0; i<2; i++)
230 
		(void)test_mavl_del(name,16300,type);
329 7u83 231 
	return 1;
232 
}
339 7u83 233 
 
234 
 
324 7u83 235 
int
236 
main(void)
237 
{
238 
	mutests tf = {
333 7u83 239 
		test0_del,
331 7u83 240 
		test0,
241 
		test1,
242 
		test2,
324 7u83 243 
		NULL
244 
	};
245 
	return mutests_run(tf);
246 
}