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