]>
git.ipfire.org Git - thirdparty/squid.git/blob - test-suite/splay.cc
2 * based on ftp://ftp.cs.cmu.edu/user/sleator/splaying/top-down-splay.c
3 * http://bobo.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl
19 #define assert(X) {if (!(X)) exit (1);}
34 intnode (int anInt
) : i (anInt
) {}
40 compareintvoid(void * const &a
, void * const &n
)
42 intnode
*A
= (intnode
*)a
;
43 intnode
*B
= (intnode
*)n
;
48 compareint(intnode
* const &a
, intnode
* const &b
)
57 static void BeginWalk();
59 static bool ExpectedFail
;
60 static void WalkVoid(void *const &, void *);
61 static void WalkNode(intnode
*const &, void *);
62 static void WalkNodeRef(intnode
const &, void *);
63 static void CheckNode(intnode
const &);
66 int SplayCheck::LastValue (0);
67 bool SplayCheck::ExpectedFail (false);
70 SplayCheck::BeginWalk()
76 SplayCheck::WalkVoid(void *const &node
, void *state
)
78 intnode
*A
= (intnode
*)node
;
83 SplayCheck::CheckNode(intnode
const &A
)
85 if (LastValue
> A
.i
) {
99 SplayCheck::WalkNode (intnode
*const &a
, void *state
)
105 SplayCheck::WalkNodeRef (intnode
const &a
, void *state
)
111 destintvoid(void * &data
)
113 intnode
*i
= (intnode
*)data
;
118 destint(intnode
* &data
)
124 compareintref(intnode
const &a
, intnode
const &b
)
130 destintref (intnode
&)
134 main(int argc
, char *argv
[])
139 /* test void * splay containers */
140 splayNode
*top
= NULL
;
141 squid_srandom(time(NULL
));
143 for (i
= 0; i
< 100; ++i
) {
144 I
= (intnode
*)xcalloc(sizeof(intnode
), 1);
145 I
->i
= squid_random();
146 top
= top
->insert(I
, compareintvoid
);
149 SplayCheck::BeginWalk();
150 top
->walk(SplayCheck::WalkVoid
, NULL
);
152 SplayCheck::BeginWalk();
153 top
->walk(SplayCheck::WalkVoid
, NULL
);
154 top
->destroy(destintvoid
);
155 /* check we don't segfault on NULL splay calls */
157 top
->splay((void *)NULL
, compareintvoid
);
160 /* test typesafe splay containers */
163 SplayNode
<intnode
*> *safeTop
= NULL
;
165 for ( int i
= 0; i
< 100; ++i
) {
168 I
->i
= squid_random();
169 safeTop
= safeTop
->insert(I
, compareint
);
172 SplayCheck::BeginWalk();
173 safeTop
->walk(SplayCheck::WalkNode
, NULL
);
175 safeTop
->destroy(destint
);
176 /* check we don't segfault on NULL splay calls */
178 safeTop
->splay((intnode
*)NULL
, compareint
);
182 SplayNode
<intnode
> *safeTop
= NULL
;
184 for (int i
= 0; i
< 100; ++i
) {
186 I
.i
= squid_random();
187 safeTop
= safeTop
->insert(I
, compareintref
);
190 SplayCheck::BeginWalk();
191 safeTop
->walk(SplayCheck::WalkNodeRef
, NULL
);
193 safeTop
->destroy(destintref
);
194 /* check we don't segfault on NULL splay calls */
196 safeTop
->splay(intnode(), compareintref
);
197 SplayCheck::BeginWalk();
198 safeTop
->walk(SplayCheck::WalkNodeRef
, NULL
);
200 /* check the check routine */
201 SplayCheck::BeginWalk();
204 /* check we don't segfault on NULL splay calls */
205 SplayCheck::WalkNodeRef(I
, NULL
);
207 SplayCheck::ExpectedFail
= true;
208 SplayCheck::WalkNodeRef(I
, NULL
);
211 /* check for begin() */
212 SplayNode
<intnode
> *safeTop
= NULL
;
214 if (safeTop
->start() != NULL
)
217 if (safeTop
->finish() != NULL
)
220 for (int i
= 0; i
< 100; ++i
) {
222 I
.i
= squid_random();
224 if (I
.i
> 50 && I
.i
< 10000000)
225 safeTop
= safeTop
->insert(I
, compareintref
);
231 safeTop
= safeTop
->insert (I
, compareintref
);
233 safeTop
= safeTop
->insert (I
, compareintref
);
236 if (!safeTop
->start())
239 if (safeTop
->start()->data
.i
!= 50)
242 if (!safeTop
->finish())
245 if (safeTop
->finish()->data
.i
!= 10000000)
248 safeTop
->destroy(destintref
);
252 Splay
<intnode
*> aSplay
;
254 if (aSplay
.start() != NULL
)
257 if (aSplay
.size() != 0)
260 aSplay
.insert (new intnode(5), compareint
);
262 if (aSplay
.start() == NULL
)
265 if (aSplay
.size() != 1)
268 aSplay
.destroy(destint
);
270 if (aSplay
.start() != NULL
)
273 if (aSplay
.size() != 0)