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