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