]>
Commit | Line | Data |
---|---|---|
b67e2c8c | 1 | /* |
b67e2c8c | 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 | |
4 | */ | |
5 | ||
f7f3304a | 6 | #include "squid.h" |
b67e2c8c | 7 | |
074d6a40 | 8 | #include <cstdlib> |
b67e2c8c | 9 | #if HAVE_UNISTD_H |
10 | #include <unistd.h> | |
11 | #endif | |
12 | ||
e1f7507e | 13 | #if 0 |
42a503bd | 14 | #define assert(X) {if (!(X)) exit (1);} |
b67e2c8c | 15 | #include "splay.h" |
42a503bd | 16 | #undef assert |
e1f7507e AJ |
17 | #else |
18 | #include "splay.h" | |
19 | #endif | |
b67e2c8c | 20 | |
e1f7507e | 21 | #include "util.h" |
42a503bd | 22 | |
23 | class intnode | |
24 | { | |
25 | ||
26 | public: | |
26ac0430 | 27 | intnode() : i(0) {} |
42a503bd | 28 | |
29 | intnode (int anInt) : i (anInt) {} | |
30 | ||
b67e2c8c | 31 | int i; |
42a503bd | 32 | }; |
b67e2c8c | 33 | |
34 | int | |
29b17d63 | 35 | compareintvoid(void * const &a, void * const &n) |
b67e2c8c | 36 | { |
37 | intnode *A = (intnode *)a; | |
38 | intnode *B = (intnode *)n; | |
b67e2c8c | 39 | return A->i - B->i; |
40 | } | |
41 | ||
29b17d63 | 42 | int |
43 | compareint(intnode * const &a, intnode * const &b) | |
44 | { | |
45 | return a->i - b->i; | |
46 | } | |
47 | ||
23087cb8 | 48 | class SplayCheck |
49 | { | |
42a503bd | 50 | |
51 | public: | |
23087cb8 | 52 | static void BeginWalk(); |
53 | static int LastValue; | |
54 | static bool ExpectedFail; | |
55 | static void WalkVoid(void *const &, void *); | |
56 | static void WalkNode(intnode *const &, void *); | |
57 | static void WalkNodeRef(intnode const &, void *); | |
58 | static void CheckNode(intnode const &); | |
59 | }; | |
60 | ||
61 | int SplayCheck::LastValue (0); | |
62 | bool SplayCheck::ExpectedFail (false); | |
63 | ||
b67e2c8c | 64 | void |
23087cb8 | 65 | SplayCheck::BeginWalk() |
b67e2c8c | 66 | { |
23087cb8 | 67 | LastValue = 0; |
b67e2c8c | 68 | } |
69 | ||
29b17d63 | 70 | void |
23087cb8 | 71 | SplayCheck::WalkVoid(void *const &node, void *state) |
29b17d63 | 72 | { |
23087cb8 | 73 | intnode *A = (intnode *)node; |
74 | CheckNode(*A); | |
75 | } | |
76 | ||
77 | void | |
78 | SplayCheck::CheckNode(intnode const &A) | |
79 | { | |
80 | if (LastValue > A.i) { | |
42a503bd | 81 | /* failure */ |
82 | ||
83 | if (!ExpectedFail) | |
84 | exit (1); | |
23087cb8 | 85 | } else |
42a503bd | 86 | /* success */ |
87 | if (ExpectedFail) | |
88 | exit (1); | |
89 | ||
23087cb8 | 90 | LastValue = A.i; |
91 | } | |
92 | ||
93 | void | |
94 | SplayCheck::WalkNode (intnode *const &a, void *state) | |
95 | { | |
96 | CheckNode (*a); | |
97 | } | |
98 | ||
99 | void | |
100 | SplayCheck::WalkNodeRef (intnode const &a, void *state) | |
101 | { | |
102 | CheckNode (a); | |
29b17d63 | 103 | } |
104 | ||
105 | void | |
106 | destintvoid(void * &data) | |
107 | { | |
108 | intnode *i = (intnode *)data; | |
109 | xfree (i); | |
110 | } | |
111 | ||
112 | void | |
113 | destint(intnode * &data) | |
114 | { | |
115 | delete data; | |
116 | } | |
117 | ||
118 | int | |
119 | compareintref(intnode const &a, intnode const &b) | |
120 | { | |
121 | return a.i - b.i; | |
122 | } | |
123 | ||
29b17d63 | 124 | void |
125 | destintref (intnode &) | |
42a503bd | 126 | {} |
29b17d63 | 127 | |
b67e2c8c | 128 | int |
129 | main(int argc, char *argv[]) | |
130 | { | |
42a503bd | 131 | { |
132 | int i; | |
133 | intnode *I; | |
134 | /* test void * splay containers */ | |
135 | splayNode *top = NULL; | |
707075b9 | 136 | squid_srandom(time(NULL)); |
42a503bd | 137 | |
14942edd | 138 | for (i = 0; i < 100; ++i) { |
42a503bd | 139 | I = (intnode *)xcalloc(sizeof(intnode), 1); |
707075b9 | 140 | I->i = squid_random(); |
b001e822 | 141 | top = top->insert(I, compareintvoid); |
42a503bd | 142 | } |
143 | ||
144 | SplayCheck::BeginWalk(); | |
b001e822 | 145 | top->walk(SplayCheck::WalkVoid, NULL); |
42a503bd | 146 | |
147 | SplayCheck::BeginWalk(); | |
148 | top->walk(SplayCheck::WalkVoid, NULL); | |
149 | top->destroy(destintvoid); | |
150 | /* check we don't segfault on NULL splay calls */ | |
151 | top = NULL; | |
b001e822 | 152 | top->splay((void *)NULL, compareintvoid); |
29b17d63 | 153 | } |
42a503bd | 154 | |
29b17d63 | 155 | /* test typesafe splay containers */ |
42a503bd | 156 | { |
157 | /* intnode* */ | |
158 | SplayNode<intnode *> *safeTop = NULL; | |
159 | ||
14942edd | 160 | for ( int i = 0; i < 100; ++i) { |
42a503bd | 161 | intnode *I; |
162 | I = new intnode; | |
707075b9 | 163 | I->i = squid_random(); |
42a503bd | 164 | safeTop = safeTop->insert(I, compareint); |
165 | } | |
166 | ||
167 | SplayCheck::BeginWalk(); | |
168 | safeTop->walk(SplayCheck::WalkNode, NULL); | |
169 | ||
170 | safeTop->destroy(destint); | |
171 | /* check we don't segfault on NULL splay calls */ | |
172 | safeTop = NULL; | |
b001e822 | 173 | safeTop->splay((intnode *)NULL, compareint); |
29b17d63 | 174 | } |
42a503bd | 175 | { |
176 | /* intnode */ | |
177 | SplayNode<intnode> *safeTop = NULL; | |
178 | ||
14942edd | 179 | for (int i = 0; i < 100; ++i) { |
42a503bd | 180 | intnode I; |
707075b9 | 181 | I.i = squid_random(); |
42a503bd | 182 | safeTop = safeTop->insert(I, compareintref); |
183 | } | |
184 | ||
185 | SplayCheck::BeginWalk(); | |
186 | safeTop->walk(SplayCheck::WalkNodeRef, NULL); | |
187 | ||
188 | safeTop->destroy(destintref); | |
189 | /* check we don't segfault on NULL splay calls */ | |
190 | safeTop = NULL; | |
191 | safeTop->splay(intnode(), compareintref); | |
192 | SplayCheck::BeginWalk(); | |
193 | safeTop->walk(SplayCheck::WalkNodeRef, NULL); | |
b67e2c8c | 194 | } |
9dca980d | 195 | |
23087cb8 | 196 | /* check the check routine */ |
9dca980d AJ |
197 | { |
198 | SplayCheck::BeginWalk(); | |
199 | intnode I; | |
200 | I.i = 1; | |
201 | /* check we don't segfault on NULL splay calls */ | |
202 | SplayCheck::WalkNodeRef(I, NULL); | |
203 | I.i = 0; | |
204 | SplayCheck::ExpectedFail = true; | |
205 | SplayCheck::WalkNodeRef(I, NULL); | |
206 | } | |
42a503bd | 207 | |
4c50505b | 208 | { |
42a503bd | 209 | /* check for begin() */ |
210 | SplayNode<intnode> *safeTop = NULL; | |
211 | ||
212 | if (safeTop->start() != NULL) | |
213 | exit (1); | |
214 | ||
ccd33084 | 215 | if (safeTop->finish() != NULL) |
42a503bd | 216 | exit (1); |
217 | ||
14942edd | 218 | for (int i = 0; i < 100; ++i) { |
42a503bd | 219 | intnode I; |
707075b9 | 220 | I.i = squid_random(); |
42a503bd | 221 | |
222 | if (I.i > 50 && I.i < 10000000) | |
223 | safeTop = safeTop->insert(I, compareintref); | |
224 | } | |
225 | ||
226 | { | |
227 | intnode I; | |
228 | I.i = 50; | |
229 | safeTop = safeTop->insert (I, compareintref); | |
230 | I.i = 10000000; | |
231 | safeTop = safeTop->insert (I, compareintref); | |
232 | } | |
233 | ||
234 | if (!safeTop->start()) | |
235 | exit (1); | |
236 | ||
237 | if (safeTop->start()->data.i != 50) | |
238 | exit (1); | |
239 | ||
ccd33084 | 240 | if (!safeTop->finish()) |
42a503bd | 241 | exit (1); |
242 | ||
ccd33084 | 243 | if (safeTop->finish()->data.i != 10000000) |
42a503bd | 244 | exit (1); |
245 | ||
246 | safeTop->destroy(destintref); | |
4c50505b | 247 | } |
42a503bd | 248 | |
4c50505b | 249 | { |
42a503bd | 250 | Splay<intnode *> aSplay; |
251 | ||
252 | if (aSplay.start() != NULL) | |
253 | exit (1); | |
254 | ||
255 | if (aSplay.size() != 0) | |
256 | exit (1); | |
257 | ||
258 | aSplay.insert (new intnode(5), compareint); | |
259 | ||
260 | if (aSplay.start() == NULL) | |
261 | exit (1); | |
262 | ||
263 | if (aSplay.size() != 1) | |
264 | exit (1); | |
265 | ||
266 | aSplay.destroy(destint); | |
267 | ||
268 | if (aSplay.start() != NULL) | |
269 | exit (1); | |
270 | ||
271 | if (aSplay.size() != 0) | |
272 | exit (1); | |
4c50505b | 273 | } |
42a503bd | 274 | |
b67e2c8c | 275 | return 0; |
276 | } |