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