]>
git.ipfire.org Git - thirdparty/squid.git/blob - test-suite/splay.cc
4 * based on ftp://ftp.cs.cmu.edu/user/sleator/splaying/top-down-splay.c
5 * http://bobo.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl
21 #define assert(X) {if (!(X)) exit (1);}
36 intnode (int anInt
) : i (anInt
) {}
42 compareintvoid(void * const &a
, void * const &n
)
44 intnode
*A
= (intnode
*)a
;
45 intnode
*B
= (intnode
*)n
;
50 compareint(intnode
* const &a
, intnode
* const &b
)
59 static void BeginWalk();
61 static bool ExpectedFail
;
62 static void WalkVoid(void *const &, void *);
63 static void WalkNode(intnode
*const &, void *);
64 static void WalkNodeRef(intnode
const &, void *);
65 static void CheckNode(intnode
const &);
68 int SplayCheck::LastValue (0);
69 bool SplayCheck::ExpectedFail (false);
72 SplayCheck::BeginWalk()
78 SplayCheck::WalkVoid(void *const &node
, void *state
)
80 intnode
*A
= (intnode
*)node
;
85 SplayCheck::CheckNode(intnode
const &A
)
87 if (LastValue
> A
.i
) {
101 SplayCheck::WalkNode (intnode
*const &a
, void *state
)
107 SplayCheck::WalkNodeRef (intnode
const &a
, void *state
)
113 destintvoid(void * &data
)
115 intnode
*i
= (intnode
*)data
;
120 destint(intnode
* &data
)
126 compareintref(intnode
const &a
, intnode
const &b
)
132 destintref (intnode
&)
136 main(int argc
, char *argv
[])
141 /* test void * splay containers */
142 splayNode
*top
= NULL
;
143 squid_srandom(time(NULL
));
145 for (i
= 0; i
< 100; i
++) {
146 I
= (intnode
*)xcalloc(sizeof(intnode
), 1);
147 I
->i
= squid_random();
148 top
= top
->insert(I
, compareintvoid
);
151 SplayCheck::BeginWalk();
152 top
->walk(SplayCheck::WalkVoid
, NULL
);
154 SplayCheck::BeginWalk();
155 top
->walk(SplayCheck::WalkVoid
, NULL
);
156 top
->destroy(destintvoid
);
157 /* check we don't segfault on NULL splay calls */
159 top
->splay((void *)NULL
, compareintvoid
);
162 /* test typesafe splay containers */
165 SplayNode
<intnode
*> *safeTop
= NULL
;
167 for ( int i
= 0; i
< 100; i
++) {
170 I
->i
= squid_random();
171 safeTop
= safeTop
->insert(I
, compareint
);
174 SplayCheck::BeginWalk();
175 safeTop
->walk(SplayCheck::WalkNode
, NULL
);
177 safeTop
->destroy(destint
);
178 /* check we don't segfault on NULL splay calls */
180 safeTop
->splay((intnode
*)NULL
, compareint
);
184 SplayNode
<intnode
> *safeTop
= NULL
;
186 for (int i
= 0; i
< 100; i
++) {
188 I
.i
= squid_random();
189 safeTop
= safeTop
->insert(I
, compareintref
);
192 SplayCheck::BeginWalk();
193 safeTop
->walk(SplayCheck::WalkNodeRef
, NULL
);
195 safeTop
->destroy(destintref
);
196 /* check we don't segfault on NULL splay calls */
198 safeTop
->splay(intnode(), compareintref
);
199 SplayCheck::BeginWalk();
200 safeTop
->walk(SplayCheck::WalkNodeRef
, NULL
);
202 /* check the check routine */
203 SplayCheck::BeginWalk();
206 /* check we don't segfault on NULL splay calls */
207 SplayCheck::WalkNodeRef(I
, NULL
);
209 SplayCheck::ExpectedFail
= true;
210 SplayCheck::WalkNodeRef(I
, NULL
);
213 /* check for begin() */
214 SplayNode
<intnode
> *safeTop
= NULL
;
216 if (safeTop
->start() != NULL
)
219 if (safeTop
->finish() != NULL
)
222 for (int i
= 0; i
< 100; i
++) {
224 I
.i
= squid_random();
226 if (I
.i
> 50 && I
.i
< 10000000)
227 safeTop
= safeTop
->insert(I
, compareintref
);
233 safeTop
= safeTop
->insert (I
, compareintref
);
235 safeTop
= safeTop
->insert (I
, compareintref
);
238 if (!safeTop
->start())
241 if (safeTop
->start()->data
.i
!= 50)
244 if (!safeTop
->finish())
247 if (safeTop
->finish()->data
.i
!= 10000000)
250 safeTop
->destroy(destintref
);
254 Splay
<intnode
*> aSplay
;
256 if (aSplay
.start() != NULL
)
259 if (aSplay
.size() != 0)
262 aSplay
.insert (new intnode(5), compareint
);
264 if (aSplay
.start() == NULL
)
267 if (aSplay
.size() != 1)
270 aSplay
.destroy(destint
);
272 if (aSplay
.start() != NULL
)
275 if (aSplay
.size() != 0)