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