]>
Commit | Line | Data |
---|---|---|
5c193dec | 1 | /* |
bf95c10a | 2 | * Copyright (C) 1996-2022 The Squid Software Foundation and contributors |
5c193dec 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 | ||
b5638623 | 9 | #ifndef SQUID_SPLAY_H |
10 | #define SQUID_SPLAY_H | |
3c01c392 | 11 | |
cfb88efb | 12 | #include "fatal.h" |
cfb88efb | 13 | #include <stack> |
29b17d63 | 14 | |
fb3eae94 | 15 | // private class of Splay. Do not use directly |
b67e2c8c | 16 | template <class V> |
42a503bd | 17 | class SplayNode |
18 | { | |
42a503bd | 19 | public: |
b67e2c8c | 20 | typedef V Value; |
29b17d63 | 21 | typedef int SPLAYCMP(Value const &a, Value const &b); |
22 | typedef void SPLAYFREE(Value &); | |
23 | typedef void SPLAYWALKEE(Value const & nodedata, void *state); | |
00d77d6b | 24 | static void DefaultFree (Value &aValue) {delete aValue;} |
42a503bd | 25 | |
2bcafc95 | 26 | SplayNode<V> (Value const &); |
29b17d63 | 27 | Value data; |
28 | mutable SplayNode<V> *left; | |
29 | mutable SplayNode<V> *right; | |
fb3eae94 | 30 | void destroy(SPLAYFREE * = DefaultFree); |
29b17d63 | 31 | void walk(SPLAYWALKEE *, void *callerState); |
4c50505b | 32 | SplayNode<V> const * start() const; |
ccd33084 | 33 | SplayNode<V> const * finish() const; |
42a503bd | 34 | |
6ca34f6f | 35 | SplayNode<V> * remove(const Value data, SPLAYCMP * compare); |
42a503bd | 36 | |
29b17d63 | 37 | SplayNode<V> * insert(Value data, SPLAYCMP * compare); |
42a503bd | 38 | |
fb3eae94 FC |
39 | /// look in the splay for data for where compare(data,candidate) == true. |
40 | /// return NULL if not found, a pointer to the sought data if found. | |
b001e822 | 41 | template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const; |
97754f5a AR |
42 | |
43 | /// recursively visit left nodes, this node, and then right nodes | |
44 | template <class Visitor> void visit(Visitor &v) const; | |
b67e2c8c | 45 | }; |
46 | ||
29b17d63 | 47 | typedef SplayNode<void *> splayNode; |
48 | ||
49 | template <class V> | |
b8bad68c | 50 | class SplayConstIterator; |
51 | ||
52 | template <class V> | |
ccd33084 | 53 | class SplayIterator; |
54 | ||
55 | template <class V> | |
42a503bd | 56 | class Splay |
57 | { | |
42a503bd | 58 | public: |
29b17d63 | 59 | typedef V Value; |
60 | typedef int SPLAYCMP(Value const &a, Value const &b); | |
42a503bd | 61 | typedef void SPLAYFREE(Value &); |
b8bad68c | 62 | typedef SplayIterator<V> iterator; |
63 | typedef const SplayConstIterator<V> const_iterator; | |
aee3523a | 64 | Splay():head(nullptr), elements (0) {} |
42a503bd | 65 | |
b001e822 | 66 | template <class FindValue> Value const *find (FindValue const &, int( * compare)(FindValue const &a, Value const &b)) const; |
fb3eae94 | 67 | |
0353e724 | 68 | void insert(Value const &, SPLAYCMP *compare); |
42a503bd | 69 | |
6ca34f6f | 70 | void remove(Value const &, SPLAYCMP *compare); |
42a503bd | 71 | |
fb3eae94 | 72 | void destroy(SPLAYFREE * = SplayNode<V>::DefaultFree); |
42a503bd | 73 | |
4c50505b | 74 | SplayNode<V> const * start() const; |
42a503bd | 75 | |
ccd33084 | 76 | SplayNode<V> const * finish() const; |
42a503bd | 77 | |
78 | size_t size() const; | |
79 | ||
4a0199ee | 80 | bool empty() const { return size() == 0; } |
fb3eae94 | 81 | |
b8bad68c | 82 | const_iterator begin() const; |
83 | ||
84 | const_iterator end() const; | |
85 | ||
97754f5a AR |
86 | /// recursively visit all nodes, in left-to-right order |
87 | template <class Visitor> void visit(Visitor &v) const; | |
88 | ||
f5dc4237 FC |
89 | private: |
90 | mutable SplayNode<V> * head; | |
e9505c9b | 91 | size_t elements; |
29b17d63 | 92 | }; |
b67e2c8c | 93 | |
b67e2c8c | 94 | SQUIDCEXTERN int splayLastResult; |
95 | ||
29b17d63 | 96 | template<class V> |
aee3523a | 97 | SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(nullptr), right (nullptr) {} |
2bcafc95 | 98 | |
87c692d7 | 99 | template<class V> |
29b17d63 | 100 | void |
101 | SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state) | |
102 | { | |
29b17d63 | 103 | if (left) |
42a503bd | 104 | left->walk(walkee, state); |
105 | ||
29b17d63 | 106 | walkee(data, state); |
42a503bd | 107 | |
29b17d63 | 108 | if (right) |
42a503bd | 109 | right->walk(walkee, state); |
29b17d63 | 110 | } |
111 | ||
4c50505b | 112 | template<class V> |
113 | SplayNode<V> const * | |
114 | SplayNode<V>::start() const | |
115 | { | |
e45bad43 | 116 | if (left) |
42a503bd | 117 | return left->start(); |
118 | ||
119 | return this; | |
120 | } | |
121 | ||
122 | template<class V> | |
123 | SplayNode<V> const * | |
ccd33084 | 124 | SplayNode<V>::finish() const |
42a503bd | 125 | { |
e45bad43 | 126 | if (right) |
ccd33084 | 127 | return right->finish(); |
42a503bd | 128 | |
4c50505b | 129 | return this; |
130 | } | |
131 | ||
29b17d63 | 132 | template<class V> |
133 | void | |
134 | SplayNode<V>::destroy(SPLAYFREE * free_func) | |
135 | { | |
29b17d63 | 136 | if (left) |
42a503bd | 137 | left->destroy(free_func); |
138 | ||
29b17d63 | 139 | if (right) |
42a503bd | 140 | right->destroy(free_func); |
141 | ||
29b17d63 | 142 | free_func(data); |
42a503bd | 143 | |
29b17d63 | 144 | delete this; |
145 | } | |
146 | ||
147 | template<class V> | |
148 | SplayNode<V> * | |
6ca34f6f | 149 | SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare) |
29b17d63 | 150 | { |
626e1f97 | 151 | SplayNode<V> *result = splay(dataToRemove, compare); |
42a503bd | 152 | |
f53969cc | 153 | if (splayLastResult == 0) { /* found it */ |
42a503bd | 154 | SplayNode<V> *newTop; |
155 | ||
aee3523a | 156 | if (result->left == nullptr) { |
42a503bd | 157 | newTop = result->right; |
158 | } else { | |
159 | newTop = result->left->splay(dataToRemove, compare); | |
160 | /* temporary */ | |
161 | newTop->right = result->right; | |
aee3523a | 162 | result->right = nullptr; |
42a503bd | 163 | } |
164 | ||
165 | delete result; | |
166 | return newTop; | |
29b17d63 | 167 | } |
42a503bd | 168 | |
f53969cc | 169 | return result; /* It wasn't there */ |
29b17d63 | 170 | } |
b67e2c8c | 171 | |
29b17d63 | 172 | template<class V> |
173 | SplayNode<V> * | |
626e1f97 | 174 | SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare) |
29b17d63 | 175 | { |
176 | /* create node to insert */ | |
2bcafc95 | 177 | SplayNode<V> *newNode = new SplayNode<V>(dataToInsert); |
626e1f97 | 178 | SplayNode<V> *newTop = splay(dataToInsert, compare); |
42a503bd | 179 | |
29b17d63 | 180 | if (splayLastResult < 0) { |
42a503bd | 181 | newNode->left = newTop->left; |
182 | newNode->right = newTop; | |
aee3523a | 183 | newTop->left = nullptr; |
42a503bd | 184 | return newNode; |
29b17d63 | 185 | } else if (splayLastResult > 0) { |
42a503bd | 186 | newNode->right = newTop->right; |
187 | newNode->left = newTop; | |
aee3523a | 188 | newTop->right = nullptr; |
42a503bd | 189 | return newNode; |
29b17d63 | 190 | } else { |
42a503bd | 191 | /* duplicate entry */ |
192 | delete newNode; | |
193 | return newTop; | |
29b17d63 | 194 | } |
195 | } | |
196 | ||
197 | template<class V> | |
b001e822 | 198 | template<class FindValue> |
29b17d63 | 199 | SplayNode<V> * |
b001e822 | 200 | SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const |
29b17d63 | 201 | { |
b001e822 | 202 | Value temp = Value(); |
203 | SplayNode<V> N(temp); | |
29b17d63 | 204 | SplayNode<V> *l; |
205 | SplayNode<V> *r; | |
206 | SplayNode<V> *y; | |
aee3523a | 207 | N.left = N.right = nullptr; |
29b17d63 | 208 | l = r = &N; |
209 | ||
210 | SplayNode<V> *top = const_cast<SplayNode<V> *>(this); | |
42a503bd | 211 | |
29b17d63 | 212 | for (;;) { |
42a503bd | 213 | splayLastResult = compare(dataToFind, top->data); |
214 | ||
215 | if (splayLastResult < 0) { | |
aee3523a | 216 | if (top->left == nullptr) |
42a503bd | 217 | break; |
218 | ||
219 | if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) { | |
f53969cc | 220 | y = top->left; /* rotate right */ |
42a503bd | 221 | top->left = y->right; |
222 | y->right = top; | |
223 | top = y; | |
224 | ||
aee3523a | 225 | if (top->left == nullptr) |
42a503bd | 226 | break; |
227 | } | |
228 | ||
f53969cc | 229 | r->left = top; /* link right */ |
42a503bd | 230 | r = top; |
231 | top = top->left; | |
232 | } else if (splayLastResult > 0) { | |
aee3523a | 233 | if (top->right == nullptr) |
42a503bd | 234 | break; |
235 | ||
236 | if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) { | |
f53969cc | 237 | y = top->right; /* rotate left */ |
42a503bd | 238 | top->right = y->left; |
239 | y->left = top; | |
240 | top = y; | |
241 | ||
aee3523a | 242 | if (top->right == nullptr) |
42a503bd | 243 | break; |
244 | } | |
245 | ||
f53969cc | 246 | l->right = top; /* link left */ |
42a503bd | 247 | l = top; |
248 | top = top->right; | |
249 | } else { | |
250 | break; | |
251 | } | |
29b17d63 | 252 | } |
42a503bd | 253 | |
f53969cc | 254 | l->right = top->left; /* assemble */ |
29b17d63 | 255 | r->left = top->right; |
256 | top->left = N.right; | |
257 | top->right = N.left; | |
258 | return top; | |
259 | } | |
260 | ||
97754f5a AR |
261 | template <class V> |
262 | template <class Visitor> | |
263 | void | |
2da4bfe6 A |
264 | SplayNode<V>::visit(Visitor &visitor) const |
265 | { | |
97754f5a AR |
266 | if (left) |
267 | left->visit(visitor); | |
268 | visitor(data); | |
269 | if (right) | |
270 | right->visit(visitor); | |
271 | } | |
272 | ||
273 | template <class V> | |
274 | template <class Visitor> | |
275 | void | |
2da4bfe6 A |
276 | Splay<V>::visit(Visitor &visitor) const |
277 | { | |
97754f5a AR |
278 | if (head) |
279 | head->visit(visitor); | |
280 | } | |
281 | ||
29b17d63 | 282 | template <class V> |
b001e822 | 283 | template <class FindValue> |
29b17d63 | 284 | typename Splay<V>::Value const * |
b001e822 | 285 | Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const |
29b17d63 | 286 | { |
aee3523a AR |
287 | if (head == nullptr) |
288 | return nullptr; | |
e45bad43 | 289 | |
29b17d63 | 290 | head = head->splay(value, compare); |
42a503bd | 291 | |
29b17d63 | 292 | if (splayLastResult != 0) |
aee3523a | 293 | return nullptr; |
42a503bd | 294 | |
29b17d63 | 295 | return &head->data; |
296 | } | |
b67e2c8c | 297 | |
0353e724 | 298 | template <class V> |
299 | void | |
300 | Splay<V>::insert(Value const &value, SPLAYCMP *compare) | |
301 | { | |
aee3523a | 302 | if (find(value, compare) != nullptr) // ignore duplicates |
8456681e AJ |
303 | return; |
304 | ||
aee3523a | 305 | if (head == nullptr) |
006b562c FC |
306 | head = new SplayNode<V>(value); |
307 | else | |
308 | head = head->insert(value, compare); | |
0353e724 | 309 | ++elements; |
310 | } | |
311 | ||
312 | template <class V> | |
313 | void | |
6ca34f6f | 314 | Splay<V>::remove(Value const &value, SPLAYCMP *compare) |
0353e724 | 315 | { |
b7cfa5b3 | 316 | // also catches the head==NULL case |
aee3523a | 317 | if (find(value, compare) == nullptr) |
b7cfa5b3 | 318 | return; |
42a503bd | 319 | |
6ca34f6f | 320 | head = head->remove(value, compare); |
42a503bd | 321 | |
0353e724 | 322 | --elements; |
323 | } | |
324 | ||
4c50505b | 325 | template <class V> |
42a503bd | 326 | SplayNode<V> const * |
327 | Splay<V>:: start() const | |
328 | { | |
329 | if (head) | |
330 | return head->start(); | |
331 | ||
aee3523a | 332 | return nullptr; |
42a503bd | 333 | } |
334 | ||
335 | template <class V> | |
336 | SplayNode<V> const * | |
ccd33084 | 337 | Splay<V>:: finish() const |
42a503bd | 338 | { |
4c50505b | 339 | if (head) |
ccd33084 | 340 | return head->finish(); |
42a503bd | 341 | |
aee3523a | 342 | return nullptr; |
4c50505b | 343 | } |
344 | ||
42a503bd | 345 | template <class V> |
346 | void | |
347 | Splay<V>:: destroy(SPLAYFREE *free_func) | |
348 | { | |
349 | if (head) | |
350 | head->destroy(free_func); | |
351 | ||
aee3523a | 352 | head = nullptr; |
42a503bd | 353 | |
354 | elements = 0; | |
355 | } | |
356 | ||
357 | template <class V> | |
358 | size_t | |
359 | Splay<V>::size() const | |
360 | { | |
361 | return elements; | |
362 | } | |
363 | ||
b8bad68c | 364 | template <class V> |
411c6ea3 | 365 | const SplayConstIterator<V> |
b8bad68c | 366 | Splay<V>::begin() const |
367 | { | |
368 | return const_iterator(head); | |
369 | } | |
370 | ||
371 | template <class V> | |
411c6ea3 | 372 | const SplayConstIterator<V> |
b8bad68c | 373 | Splay<V>::end() const |
374 | { | |
aee3523a | 375 | return const_iterator(nullptr); |
b8bad68c | 376 | } |
377 | ||
97754f5a | 378 | // XXX: This does not seem to iterate the whole thing in some cases. |
b8bad68c | 379 | template <class V> |
b8bad68c | 380 | class SplayConstIterator |
381 | { | |
382 | ||
383 | public: | |
384 | typedef const V value_type; | |
385 | SplayConstIterator (SplayNode<V> *aNode); | |
386 | bool operator == (SplayConstIterator const &right) const; | |
387 | SplayConstIterator operator ++ (int dummy); | |
388 | SplayConstIterator &operator ++ (); | |
389 | V const & operator * () const; | |
390 | ||
391 | private: | |
392 | void advance(); | |
393 | void addLeftPath(SplayNode<V> *aNode); | |
394 | void init(SplayNode<V> *); | |
cfb88efb | 395 | std::stack<SplayNode<V> *> toVisit; |
b8bad68c | 396 | }; |
397 | ||
398 | template <class V> | |
399 | SplayConstIterator<V>::SplayConstIterator (SplayNode<V> *aNode) | |
400 | { | |
401 | init(aNode); | |
402 | } | |
403 | ||
404 | template <class V> | |
405 | bool | |
406 | SplayConstIterator<V>::operator == (SplayConstIterator const &right) const | |
407 | { | |
cfb88efb AR |
408 | if (toVisit.empty() && right.toVisit.empty()) |
409 | return true; | |
410 | if (!toVisit.empty() && !right.toVisit.empty()) | |
411 | return toVisit.top() == right.toVisit.top(); | |
412 | // only one of the two is empty | |
413 | return false; | |
b8bad68c | 414 | } |
415 | ||
416 | template <class V> | |
417 | SplayConstIterator<V> & | |
418 | SplayConstIterator<V>::operator ++ () | |
419 | { | |
420 | advance(); | |
421 | return *this; | |
422 | } | |
423 | ||
424 | template <class V> | |
425 | SplayConstIterator<V> | |
8b082ed9 | 426 | SplayConstIterator<V>::operator ++ (int) |
b8bad68c | 427 | { |
428 | SplayConstIterator<V> result = *this; | |
429 | advance(); | |
430 | return result; | |
431 | } | |
432 | ||
433 | /* advance is simple enough: | |
434 | * if the stack is empty, we're done. | |
435 | * otherwise, pop the last visited node | |
436 | * then, pop the next node to visit | |
437 | * if that has a right child, add it and it's | |
438 | * left-to-end path. | |
439 | * then add the node back. | |
440 | */ | |
441 | template <class V> | |
442 | void | |
443 | SplayConstIterator<V>::advance() | |
444 | { | |
cfb88efb | 445 | if (toVisit.empty()) |
b8bad68c | 446 | return; |
447 | ||
448 | toVisit.pop(); | |
449 | ||
cfb88efb | 450 | if (toVisit.empty()) |
b8bad68c | 451 | return; |
452 | ||
cfb88efb AR |
453 | // not empty |
454 | SplayNode<V> *currentNode = toVisit.top(); | |
455 | toVisit.pop(); | |
b8bad68c | 456 | |
457 | addLeftPath(currentNode->right); | |
458 | ||
cfb88efb | 459 | toVisit.push(currentNode); |
b8bad68c | 460 | } |
461 | ||
462 | template <class V> | |
463 | void | |
464 | SplayConstIterator<V>::addLeftPath(SplayNode<V> *aNode) | |
465 | { | |
aee3523a | 466 | if (aNode == nullptr) |
b8bad68c | 467 | return; |
468 | ||
469 | do { | |
cfb88efb | 470 | toVisit.push(aNode); |
b8bad68c | 471 | aNode = aNode->left; |
aee3523a | 472 | } while (aNode != nullptr); |
b8bad68c | 473 | } |
474 | ||
475 | template <class V> | |
476 | void | |
477 | SplayConstIterator<V>::init(SplayNode<V> *head) | |
478 | { | |
479 | addLeftPath(head); | |
480 | } | |
481 | ||
482 | template <class V> | |
483 | V const & | |
484 | SplayConstIterator<V>::operator * () const | |
485 | { | |
486 | /* can't dereference when past the end */ | |
487 | ||
488 | if (toVisit.size() == 0) | |
489 | fatal ("Attempt to dereference SplayConstIterator past-the-end\n"); | |
490 | ||
491 | return toVisit.top()->data; | |
492 | } | |
493 | ||
b5638623 | 494 | #endif /* SQUID_SPLAY_H */ |
f53969cc | 495 |