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