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