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