]>
Commit | Line | Data |
---|---|---|
4e0938ef | 1 | /* |
b8ae064d | 2 | * Copyright (C) 1996-2023 The Squid Software Foundation and contributors |
4e0938ef AJ |
3 | * |
4 | * Squid software is distributed under GPLv2+ license and includes | |
5 | * contributions from numerous individuals and organizations. | |
6 | * Please see the COPYING and CONTRIBUTORS files for details. | |
7 | */ | |
8 | ||
b67e2c8c | 9 | /* |
b67e2c8c | 10 | * based on ftp://ftp.cs.cmu.edu/user/sleator/splaying/top-down-splay.c |
11 | * http://bobo.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl | |
12 | */ | |
13 | ||
f7f3304a | 14 | #include "squid.h" |
61bf2627 AJ |
15 | #include "splay.h" |
16 | #include "util.h" | |
b67e2c8c | 17 | |
074d6a40 | 18 | #include <cstdlib> |
0cde91ae | 19 | #include <functional> |
b67e2c8c | 20 | #if HAVE_UNISTD_H |
21 | #include <unistd.h> | |
22 | #endif | |
61bf2627 | 23 | #include <random> |
42a503bd | 24 | |
25 | class intnode | |
26 | { | |
27 | ||
28 | public: | |
26ac0430 | 29 | intnode() : i(0) {} |
42a503bd | 30 | |
31 | intnode (int anInt) : i (anInt) {} | |
32 | ||
b67e2c8c | 33 | int i; |
42a503bd | 34 | }; |
b67e2c8c | 35 | |
8b082ed9 FC |
36 | static int |
37 | compareintvoid(void *const &a, void *const &n) | |
b67e2c8c | 38 | { |
39 | intnode *A = (intnode *)a; | |
40 | intnode *B = (intnode *)n; | |
b67e2c8c | 41 | return A->i - B->i; |
42 | } | |
43 | ||
8b082ed9 FC |
44 | static int |
45 | compareint(intnode *const &a, intnode *const &b) | |
29b17d63 | 46 | { |
47 | return a->i - b->i; | |
48 | } | |
49 | ||
23087cb8 | 50 | class SplayCheck |
51 | { | |
42a503bd | 52 | |
53 | public: | |
23087cb8 | 54 | static void BeginWalk(); |
55 | static int LastValue; | |
56 | static bool ExpectedFail; | |
06ad882f AR |
57 | static void VisitVoid(void *const &); |
58 | static void VisitNode(intnode *const &); | |
59 | static void VisitNodeRef(intnode const &); | |
23087cb8 | 60 | static void CheckNode(intnode const &); |
61 | }; | |
62 | ||
63 | int SplayCheck::LastValue (0); | |
64 | bool SplayCheck::ExpectedFail (false); | |
65 | ||
b67e2c8c | 66 | void |
23087cb8 | 67 | SplayCheck::BeginWalk() |
b67e2c8c | 68 | { |
23087cb8 | 69 | LastValue = 0; |
b67e2c8c | 70 | } |
71 | ||
29b17d63 | 72 | void |
06ad882f | 73 | SplayCheck::VisitVoid(void *const &node) |
29b17d63 | 74 | { |
23087cb8 | 75 | intnode *A = (intnode *)node; |
76 | CheckNode(*A); | |
77 | } | |
78 | ||
79 | void | |
80 | SplayCheck::CheckNode(intnode const &A) | |
81 | { | |
82 | if (LastValue > A.i) { | |
42a503bd | 83 | /* failure */ |
84 | ||
85 | if (!ExpectedFail) | |
24885773 | 86 | exit(EXIT_FAILURE); |
23087cb8 | 87 | } else |
42a503bd | 88 | /* success */ |
89 | if (ExpectedFail) | |
24885773 | 90 | exit(EXIT_FAILURE); |
42a503bd | 91 | |
23087cb8 | 92 | LastValue = A.i; |
93 | } | |
94 | ||
95 | void | |
06ad882f | 96 | SplayCheck::VisitNode(intnode *const &a) |
23087cb8 | 97 | { |
98 | CheckNode (*a); | |
99 | } | |
100 | ||
101 | void | |
06ad882f | 102 | SplayCheck::VisitNodeRef(intnode const &a) |
23087cb8 | 103 | { |
104 | CheckNode (a); | |
29b17d63 | 105 | } |
106 | ||
8b082ed9 FC |
107 | static void |
108 | destintvoid(void *&data) | |
29b17d63 | 109 | { |
110 | intnode *i = (intnode *)data; | |
111 | xfree (i); | |
112 | } | |
113 | ||
8b082ed9 FC |
114 | static void |
115 | destint(intnode *&data) | |
29b17d63 | 116 | { |
117 | delete data; | |
118 | } | |
119 | ||
8b082ed9 | 120 | static int |
29b17d63 | 121 | compareintref(intnode const &a, intnode const &b) |
122 | { | |
123 | return a.i - b.i; | |
124 | } | |
125 | ||
8b082ed9 FC |
126 | static void |
127 | destintref(intnode &) | |
42a503bd | 128 | {} |
29b17d63 | 129 | |
b67e2c8c | 130 | int |
72ed5979 | 131 | main(int, char *[]) |
b67e2c8c | 132 | { |
61bf2627 | 133 | std::mt19937 generator; |
09835feb | 134 | std::uniform_int_distribution<int> distribution; |
61bf2627 AJ |
135 | auto nextRandom = std::bind (distribution, generator); |
136 | ||
42a503bd | 137 | { |
42a503bd | 138 | /* test void * splay containers */ |
d4e7ea7a | 139 | const auto top = new Splay<void *>(); |
42a503bd | 140 | |
61bf2627 AJ |
141 | for (int i = 0; i < 100; ++i) { |
142 | intnode *I = (intnode *)xcalloc(sizeof(intnode), 1); | |
143 | I->i = nextRandom(); | |
d4e7ea7a | 144 | top->insert(I, compareintvoid); |
42a503bd | 145 | } |
146 | ||
147 | SplayCheck::BeginWalk(); | |
06ad882f | 148 | top->visit(SplayCheck::VisitVoid); |
42a503bd | 149 | |
150 | SplayCheck::BeginWalk(); | |
06ad882f | 151 | top->visit(SplayCheck::VisitVoid); |
42a503bd | 152 | top->destroy(destintvoid); |
29b17d63 | 153 | } |
42a503bd | 154 | |
29b17d63 | 155 | /* test typesafe splay containers */ |
42a503bd | 156 | { |
157 | /* intnode* */ | |
d4e7ea7a | 158 | const auto safeTop = new Splay<intnode *>(); |
42a503bd | 159 | |
14942edd | 160 | for ( int i = 0; i < 100; ++i) { |
42a503bd | 161 | intnode *I; |
162 | I = new intnode; | |
61bf2627 | 163 | I->i = nextRandom(); |
d4e7ea7a | 164 | safeTop->insert(I, compareint); |
42a503bd | 165 | } |
166 | ||
167 | SplayCheck::BeginWalk(); | |
06ad882f | 168 | safeTop->visit(SplayCheck::VisitNode); |
42a503bd | 169 | |
170 | safeTop->destroy(destint); | |
29b17d63 | 171 | } |
42a503bd | 172 | { |
173 | /* intnode */ | |
d4e7ea7a | 174 | const auto safeTop = new Splay<intnode>(); |
42a503bd | 175 | |
14942edd | 176 | for (int i = 0; i < 100; ++i) { |
42a503bd | 177 | intnode I; |
61bf2627 | 178 | I.i = nextRandom(); |
d4e7ea7a | 179 | safeTop->insert(I, compareintref); |
42a503bd | 180 | } |
181 | ||
182 | SplayCheck::BeginWalk(); | |
06ad882f | 183 | safeTop->visit(SplayCheck::VisitNodeRef); |
42a503bd | 184 | |
185 | safeTop->destroy(destintref); | |
b67e2c8c | 186 | } |
9dca980d | 187 | |
23087cb8 | 188 | /* check the check routine */ |
9dca980d AJ |
189 | { |
190 | SplayCheck::BeginWalk(); | |
191 | intnode I; | |
192 | I.i = 1; | |
193 | /* check we don't segfault on NULL splay calls */ | |
06ad882f | 194 | SplayCheck::VisitNodeRef(I); |
9dca980d AJ |
195 | I.i = 0; |
196 | SplayCheck::ExpectedFail = true; | |
06ad882f | 197 | SplayCheck::VisitNodeRef(I); |
9dca980d | 198 | } |
42a503bd | 199 | |
4c50505b | 200 | { |
42a503bd | 201 | /* check for begin() */ |
bf0e740b | 202 | Splay<intnode> *safeTop = new Splay<intnode>(); |
42a503bd | 203 | |
aee3523a | 204 | if (safeTop->start() != nullptr) |
24885773 | 205 | exit(EXIT_FAILURE); |
42a503bd | 206 | |
aee3523a | 207 | if (safeTop->finish() != nullptr) |
24885773 | 208 | exit(EXIT_FAILURE); |
42a503bd | 209 | |
14942edd | 210 | for (int i = 0; i < 100; ++i) { |
42a503bd | 211 | intnode I; |
61bf2627 | 212 | I.i = nextRandom(); |
42a503bd | 213 | |
214 | if (I.i > 50 && I.i < 10000000) | |
bf0e740b | 215 | safeTop->insert(I, compareintref); |
42a503bd | 216 | } |
217 | ||
218 | { | |
219 | intnode I; | |
220 | I.i = 50; | |
bf0e740b | 221 | safeTop->insert (I, compareintref); |
42a503bd | 222 | I.i = 10000000; |
bf0e740b | 223 | safeTop->insert (I, compareintref); |
42a503bd | 224 | } |
225 | ||
226 | if (!safeTop->start()) | |
24885773 | 227 | exit(EXIT_FAILURE); |
42a503bd | 228 | |
229 | if (safeTop->start()->data.i != 50) | |
24885773 | 230 | exit(EXIT_FAILURE); |
42a503bd | 231 | |
ccd33084 | 232 | if (!safeTop->finish()) |
24885773 | 233 | exit(EXIT_FAILURE); |
42a503bd | 234 | |
ccd33084 | 235 | if (safeTop->finish()->data.i != 10000000) |
24885773 | 236 | exit(EXIT_FAILURE); |
42a503bd | 237 | |
238 | safeTop->destroy(destintref); | |
4c50505b | 239 | } |
42a503bd | 240 | |
4c50505b | 241 | { |
42a503bd | 242 | Splay<intnode *> aSplay; |
243 | ||
aee3523a | 244 | if (aSplay.start() != nullptr) |
24885773 | 245 | exit(EXIT_FAILURE); |
42a503bd | 246 | |
247 | if (aSplay.size() != 0) | |
24885773 | 248 | exit(EXIT_FAILURE); |
42a503bd | 249 | |
250 | aSplay.insert (new intnode(5), compareint); | |
251 | ||
aee3523a | 252 | if (aSplay.start() == nullptr) |
24885773 | 253 | exit(EXIT_FAILURE); |
42a503bd | 254 | |
255 | if (aSplay.size() != 1) | |
24885773 | 256 | exit(EXIT_FAILURE); |
42a503bd | 257 | |
258 | aSplay.destroy(destint); | |
259 | ||
aee3523a | 260 | if (aSplay.start() != nullptr) |
24885773 | 261 | exit(EXIT_FAILURE); |
42a503bd | 262 | |
263 | if (aSplay.size() != 0) | |
24885773 | 264 | exit(EXIT_FAILURE); |
4c50505b | 265 | } |
42a503bd | 266 | |
cb1e2244 | 267 | /* TODO: also test the other Splay API */ |
bf0e740b | 268 | |
24885773 | 269 | return EXIT_SUCCESS; |
b67e2c8c | 270 | } |
f53969cc | 271 |