1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1999-2011 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Eclipse Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.eclipse.org/org/documents/epl-v10.html *
11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <glenn.s.fowler@gmail.com> *
18 * *
19 ***********************************************************************/
20 #include "dttest.h"
21
22 Dtdisc_t Disc =
23 { 0, sizeof(long), -1,
24 newint, NIL(Dtfree_f), compare, hashint,
25 NIL(Dtmemory_f), NIL(Dtevent_f)
26 };
27
28 Dtdisc_t Rdisc =
29 { 0, sizeof(long), -1,
30 newint, NIL(Dtfree_f), rcompare, hashint,
31 NIL(Dtmemory_f), NIL(Dtevent_f)
32 };
33
tmain()34 tmain()
35 {
36 Dt_t* dt;
37 Dtlink_t* link;
38 long i, k, count[1000];
39
40 /* testing Dtoset */
41 dt = dtopen(&Disc,Dtoset);
42 if((long)dtinsert(dt,7L) != 7)
43 terror("Insert 7");
44 if((long)dtinsert(dt,1L) != 1)
45 terror("Insert 1");
46 if((long)dtinsert(dt,3L) != 3)
47 terror("Insert 3");
48 if((long)dtinsert(dt,4L) != 4)
49 terror("Insert 4");
50 if((long)dtinsert(dt,2L) != 2)
51 terror("Insert 2");
52 if((long)dtinsert(dt,6L) != 6)
53 terror("Insert 6");
54 if((long)dtinsert(dt,7L) != 7)
55 terror("Insert 7,2");
56
57 if((long)dtatmost(dt, 5L) != 4)
58 terror("Should have found 4");
59 if((long)dtatleast(dt, 5L) != 6)
60 terror("Should have found 6");
61
62 if((long)dtinsert(dt,5L) != 5)
63 terror("Insert 5");
64
65 if((long)dtatmost(dt, 5L) != 5)
66 terror("Should have found 5");
67 if((long)dtatleast(dt, 3L) != 3)
68 terror("Should have found 3");
69
70 for(i = 1; i <= 7; ++i)
71 if((long)dtsearch(dt,i) != i)
72 terror("Dtoset search");
73 for(link = dtflatten(dt), i = 1; link; link = dtlink(dt,link), i += 1)
74 if((long)dtobj(dt,link) != i)
75 terror("Dtoset flatten");
76 for(i = (long)dtlast(dt), k = 7; k >= 1; i = (long)dtprev(dt,i), k -= 1)
77 if(i != k)
78 terror("Dtoset backwalk");
79
80 /* reverse ordering */
81 dtdisc(dt,&Rdisc,0);
82 for(i = 7; i >= 1; --i)
83 if((long)dtsearch(dt,i) != i)
84 terror("Dtoset search 2");
85 for(i = (long)dtlast(dt), k = 1; k <= 7; i = (long)dtprev(dt,i), k += 1)
86 if(i != k)
87 terror("Dtoset backwalk 2");
88 for(link = dtflatten(dt), i = 7; link; link = dtlink(dt,link), i -= 1)
89 if((long)dtobj(dt,link) != i)
90 terror("Dtoset flatten 2");
91
92 if(!(link = dtextract(dt)) )
93 terror("Fail extracting Dtoset");
94 if(!dtrestore(dt,link) )
95 terror("Fail restoring Dtoset");
96 if(dtsize(dt) != 7)
97 terror("Dtoset size after extract");
98 for(link = dtflatten(dt), i = 7; link; link = dtlink(dt,link), i -= 1)
99 if((long)dtobj(dt,link) != i)
100 terror("Dtoset flatten after extract");
101
102 /* change to hashing */
103 dtmethod(dt,Dtset);
104 for(i = 1; i <= 7; ++i)
105 if((long)dtsearch(dt,i) != i)
106 terror("Dtset search");
107 for(i = 0, link = dtflatten(dt); link; link = dtlink(dt,link))
108 i += 1;
109 if(i != 7)
110 terror("Dtset flatten");
111 for(k = 0, i = (long)dtlast(dt); i != 0; i = (long)dtprev(dt,i))
112 k += 1;
113 if(k != 7)
114 terror("Dtset flatten 2");
115
116 if(!(link = dtextract(dt)) )
117 terror("Fail extracting Dtset");
118 if(!dtrestore(dt,link) )
119 terror("Fail restoring Dtset");
120 if(dtsize(dt) != 7)
121 terror("Dtset size after extract");
122 for(i = (long)dtlast(dt), k = 0; i != 0; i = (long)dtprev(dt,i))
123 k += 1;
124 if(k != 7)
125 terror("Dtset flatten after extract");
126
127 dtdisc(dt,&Disc,0);
128 for(i = 1; i <= 7; ++i)
129 if((long)dtsearch(dt,i) != i)
130 terror("Dtset search 2");
131 for(link = dtflatten(dt), i = 0; link; link = dtlink(dt,link))
132 i += 1;
133 if(i != 7)
134 terror("Dtset flatten 2");
135
136 dtclear(dt);
137 if(dtsize(dt) != 0)
138 terror("Dtsize");
139
140 /* testing Dtlist */
141 dtmethod(dt,Dtlist);
142 if((long)dtinsert(dt,1) != 1)
143 terror("Dtlist insert 1.1");
144 if((long)dtinsert(dt,3) != 3)
145 terror("Dtlist insert 3.1");
146 if((long)dtinsert(dt,2) != 2)
147 terror("Dtlist insert 2.1");
148 if((long)dtinsert(dt,3) != 3)
149 terror("Dtlist insert 3.2");
150 if((long)dtinsert(dt,2) != 2)
151 terror("Dtlist insert 2.2");
152 if((long)dtinsert(dt,3) != 3)
153 terror("Dtlist insert 3.3");
154 if((long)dtinsert(dt,1) != 1)
155 terror("Dtlist insert 1.2");
156
157 /* check multiplicities */
158 for(i = 1; i <= 3; ++i)
159 count[i] = 0;
160 for(i = (long)dtlast(dt); i != 0; i = (long)dtprev(dt,i))
161 count[i] += 1;
162 if(count[1] != 2)
163 terror("Dtlist count 1");
164 if(count[2] != 2)
165 terror("Dtlist count 2");
166 if(count[3] != 3)
167 terror("Dtlist count 3");
168
169 dtclear(dt);
170 if(dtsize(dt) != 0)
171 terror("Dtsize");
172
173 /* testing Dtbag */
174 dtmethod(dt,Dtbag);
175 if((long)dtinsert(dt,1) != 1)
176 terror("Dtlist insert 1.1");
177 if((long)dtinsert(dt,3) != 3)
178 terror("Dtlist insert 3.1");
179 if((long)dtinsert(dt,2) != 2)
180 terror("Dtlist insert 2.1");
181 if((long)dtinsert(dt,3) != 3)
182 terror("Dtlist insert 3.2");
183 if((long)dtinsert(dt,2) != 2)
184 terror("Dtlist insert 2.2");
185 if((long)dtinsert(dt,3) != 3)
186 terror("Dtlist insert 3.3");
187 if((long)dtinsert(dt,1) != 1)
188 terror("Dtlist insert 1.2");
189
190 /* check multiplicities */
191 for(i = 1; i <= 3; ++i)
192 count[i] = 0;
193 for(i = (long)dtlast(dt); i != 0; i = (long)dtprev(dt,i))
194 count[i] += 1;
195 if(count[1] != 2)
196 terror("Dtbag count 1");
197 if(count[2] != 2)
198 terror("Dtbag count 2");
199 if(count[3] != 3)
200 terror("Dtbag count 3");
201
202 /* change method to Dtobag */
203 dtmethod(dt,Dtobag);
204
205 /* check multiplicities */
206 for(i = 1; i <= 3; ++i)
207 count[i] = 0;
208 for(i = (long)dtfirst(dt); i != 0; i = (long)dtnext(dt,i))
209 count[i] += 1;
210 if(count[1] != 2)
211 terror("Dtobag count 1");
212 if(count[2] != 2)
213 terror("Dtobag count 2");
214 if(count[3] != 3)
215 terror("Dtobag count 3");
216
217 /* test consecutive 1's */
218 if((long)dtatmost(dt,1) != 1)
219 terror("Dtobag search 1");
220 if((long)dtnext(dt,1) != 1)
221 terror("Dtobag next 1");
222 if((long)dtnext(dt,1) != 2)
223 terror("Dtobag next should be 2");
224
225 /* test consecutive 2's */
226 if((long)dtatmost(dt,2) != 2)
227 terror("Dtobag search 2");
228 if((long)dtnext(dt,2) != 2)
229 terror("Dtobag next 2");
230 if((long)dtnext(dt,2) != 3)
231 terror("Dtobag next should be 3");
232
233 /* test consecutive 3's */
234 if((long)dtatleast(dt,3) != 3)
235 terror("Dtobag search 3");
236 if((long)dtprev(dt,3) != 3)
237 terror("Dtobag prev 3");
238 if((long)dtprev(dt,3) != 3)
239 terror("Dtobag prev 3.2");
240 if((long)dtprev(dt,3) == 3)
241 terror("Dtobag prev not expecting 3");
242
243 /* test large set of values */
244 dtclear(dt);
245 dtmethod(dt,Dtset);
246 for(i = 1; i < 20000; ++i)
247 if((long)dtinsert(dt,i) != i)
248 terror("Can't insert");
249 dtmethod(dt,Dtoset);
250 for(i = 1, k = (long)dtfirst(dt); i < 20000; ++i, k = (long)dtnext(dt,k))
251 if(i != k)
252 terror("Bad value");
253
254 /* test walking Dtrhset */
255 dtclear(dt);
256 dtmethod(dt, Dtrhset);
257 for(i = 1; i < 100; ++i)
258 if((long)dtinsert(dt,i) != i)
259 terror("Can't insert");
260 for(i = 1; i < 100; ++i)
261 if((long)dtsearch(dt,i) != i)
262 terror("Can't find %d", i);
263
264 memset(count, 0, sizeof(count));
265 for(i = 0, k = (long)dtfirst(dt); k != 0; i += 1, k = (long)dtnext(dt,k))
266 count[k] += 1;
267 for(i = 1; i < 100; ++i)
268 if(count[i] != 1)
269 terror("wrong count[%d]=%d", i, count[i]);
270
271 texit(0);
272 }
273