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