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