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