include/splay.h

   1 #ifndef SQUID_SPLAY_H
   2 #define SQUID_SPLAY_H
   3
   4 #if defined(__cplusplus)
   5
   6 #include "fatal.h"
   7
   8 #include <stack>
   9
  10 template <class V>
  11 class SplayNode
  12 {
  13
  14 public:
  15     typedef V Value;
  16     typedef int SPLAYCMP(Value const &a, Value const &b);
  17     typedef void SPLAYFREE(Value &);
  18     typedef void SPLAYWALKEE(Value const & nodedata, void *state);
  19     static void DefaultFree (Value &aValue) {delete aValue;}
  20
  21     SplayNode<V> (Value const &);
  22     Value data;
  23     mutable SplayNode<V> *left;
  24     mutable SplayNode<V> *right;
  25     void destroy(SPLAYFREE *);
  26     void walk(SPLAYWALKEE *, void *callerState);
  27     bool empty() const { return this == NULL; }
  28     SplayNode<V> const * start() const;
  29     SplayNode<V> const * finish() const;
  30
  31     SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
  32
  33     SplayNode<V> * insert(Value data, SPLAYCMP * compare);
  34
  35     template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
  36
  37     /// recursively visit left nodes, this node, and then right nodes
  38     template <class Visitor> void visit(Visitor &v) const;
  39 };
  40
  41 typedef SplayNode<void *> splayNode;
  42
  43 template <class V>
  44 class SplayConstIterator;
  45
  46 template <class V>
  47 class SplayIterator;
  48
  49 template <class V>
  50 class Splay
  51 {
  52
  53 public:
  54     typedef V Value;
  55     typedef int SPLAYCMP(Value const &a, Value const &b);
  56     typedef void SPLAYFREE(Value &);
  57     typedef SplayIterator<V> iterator;
  58     typedef const SplayConstIterator<V> const_iterator;
  59     Splay():head(NULL), elements (0) {}
  60
  61     mutable SplayNode<V> * head;
  62     template <class FindValue> Value const *find (FindValue const &, int( * compare)(FindValue const &a, Value const &b)) const;
  63     void insert(Value const &, SPLAYCMP *compare);
  64
  65     void remove(Value const &, SPLAYCMP *compare);
  66
  67     void destroy(SPLAYFREE *);
  68
  69     SplayNode<V> const * start() const;
  70
  71     SplayNode<V> const * finish() const;
  72
  73     size_t size() const;
  74
  75     const_iterator begin() const;
  76
  77     const_iterator end() const;
  78
  79     /// recursively visit all nodes, in left-to-right order
  80     template <class Visitor> void visit(Visitor &v) const;
  81
  82     size_t elements;
  83 };
  84
  85 SQUIDCEXTERN int splayLastResult;
  86
  87 SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, splayNode::SPLAYCMP *);
  88
  89 SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, splayNode::SPLAYCMP *);
  90
  91 SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, splayNode::SPLAYCMP *);
  92
  93 SQUIDCEXTERN void splay_destroy(splayNode *, splayNode::SPLAYFREE *);
  94
  95 SQUIDCEXTERN void splay_walk(splayNode *, splayNode::SPLAYWALKEE *, void *callerState);
  96
  97 /* inline methods */
  98 template<class V>
  99 SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(NULL), right (NULL) {}
 100
 101 template<class V>
 102 void
 103 SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
 104 {
 105     if (this == NULL)
 106         return;
 107
 108     if (left)
 109         left->walk(walkee, state);
 110
 111     walkee(data, state);
 112
 113     if (right)
 114         right->walk(walkee, state);
 115 }
 116
 117 template<class V>
 118 SplayNode<V> const *
 119 SplayNode<V>::start() const
 120 {
 121     if (this && left)
 122         return left->start();
 123
 124     return this;
 125 }
 126
 127 template<class V>
 128 SplayNode<V> const *
 129 SplayNode<V>::finish() const
 130 {
 131     if (this && right)
 132         return right->finish();
 133
 134     return this;
 135 }
 136
 137 template<class V>
 138 void
 139 SplayNode<V>::destroy(SPLAYFREE * free_func)
 140 {
 141     if (!this)
 142         return;
 143
 144     if (left)
 145         left->destroy(free_func);
 146
 147     if (right)
 148         right->destroy(free_func);
 149
 150     free_func(data);
 151
 152     delete this;
 153 }
 154
 155 template<class V>
 156 SplayNode<V> *
 157 SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare)
 158 {
 159     if (this == NULL)
 160         return NULL;
 161
 162     SplayNode<V> *result = splay(dataToRemove, compare);
 163
 164     if (splayLastResult == 0) { /* found it */
 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;
 178     }
 179
 180     return result;                      /* It wasn't there */
 181 }
 182
 183 template<class V>
 184 SplayNode<V> *
 185 SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
 186 {
 187     /* create node to insert */
 188     SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
 189
 190     if (this == NULL) {
 191         splayLastResult = -1;
 192         newNode->left = newNode->right = NULL;
 193         return newNode;
 194     }
 195
 196     SplayNode<V> *newTop = splay(dataToInsert, compare);
 197
 198     if (splayLastResult < 0) {
 199         newNode->left = newTop->left;
 200         newNode->right = newTop;
 201         newTop->left = NULL;
 202         return newNode;
 203     } else if (splayLastResult > 0) {
 204         newNode->right = newTop->right;
 205         newNode->left = newTop;
 206         newTop->right = NULL;
 207         return newNode;
 208     } else {
 209         /* duplicate entry */
 210         delete newNode;
 211         return newTop;
 212     }
 213 }
 214
 215 template<class V>
 216 template<class FindValue>
 217 SplayNode<V> *
 218 SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
 219 {
 220     if (this == NULL) {
 221         /* can't have compared successfully :} */
 222         splayLastResult = -1;
 223         return NULL;
 224     }
 225
 226     Value temp = Value();
 227     SplayNode<V> N(temp);
 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);
 235
 236     for (;;) {
 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         }
 276     }
 277
 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
 285 template <class V>
 286 template <class Visitor>
 287 void
 288 SplayNode<V>::visit(Visitor &visitor) const {
 289     if (left)
 290         left->visit(visitor);
 291     visitor(data);
 292     if (right)
 293         right->visit(visitor);
 294 }
 295
 296 template <class V>
 297 template <class Visitor>
 298 void
 299 Splay<V>::visit(Visitor &visitor) const {
 300     if (head)
 301         head->visit(visitor);
 302 }
 303
 304 template <class V>
 305 template <class FindValue>
 306 typename Splay<V>::Value const *
 307 Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
 308 {
 309     head = head->splay(value, compare);
 310
 311     if (splayLastResult != 0)
 312         return NULL;
 313
 314     return &head->data;
 315 }
 316
 317 template <class V>
 318 void
 319 Splay<V>::insert(Value const &value, SPLAYCMP *compare)
 320 {
 321     assert (!find (value, compare));
 322     head = head->insert(value, compare);
 323     ++elements;
 324 }
 325
 326 template <class V>
 327 void
 328 Splay<V>::remove(Value const &value, SPLAYCMP *compare)
 329 {
 330     assert (find (value, compare));
 331
 332     head = head->remove(value, compare);
 333
 334     --elements;
 335 }
 336
 337 template <class V>
 338 SplayNode<V> const *
 339 Splay<V>:: start() const
 340 {
 341     if (head)
 342         return head->start();
 343
 344     return NULL;
 345 }
 346
 347 template <class V>
 348 SplayNode<V> const *
 349 Splay<V>:: finish() const
 350 {
 351     if (head)
 352         return head->finish();
 353
 354     return NULL;
 355 }
 356
 357 template <class V>
 358 void
 359 Splay<V>:: destroy(SPLAYFREE *free_func)
 360 {
 361     if (head)
 362         head->destroy(free_func);
 363
 364     head = NULL;
 365
 366     elements = 0;
 367 }
 368
 369 template <class V>
 370 size_t
 371 Splay<V>::size() const
 372 {
 373     return elements;
 374 }
 375
 376 template <class V>
 377 const SplayConstIterator<V>
 378 Splay<V>::begin() const
 379 {
 380     return const_iterator(head);
 381 }
 382
 383 template <class V>
 384 const SplayConstIterator<V>
 385 Splay<V>::end() const
 386 {
 387     return const_iterator(NULL);
 388 }
 389
 390 // XXX: This does not seem to iterate the whole thing in some cases.
 391 template <class V>
 392 class SplayConstIterator
 393 {
 394
 395 public:
 396     typedef const V value_type;
 397     SplayConstIterator (SplayNode<V> *aNode);
 398     bool operator == (SplayConstIterator const &right) const;
 399     SplayConstIterator operator ++ (int dummy);
 400     SplayConstIterator &operator ++ ();
 401     V const & operator * () const;
 402
 403 private:
 404     void advance();
 405     void addLeftPath(SplayNode<V> *aNode);
 406     void init(SplayNode<V> *);
 407     std::stack<SplayNode<V> *> toVisit;
 408 };
 409
 410 template <class V>
 411 SplayConstIterator<V>::SplayConstIterator (SplayNode<V> *aNode)
 412 {
 413     init(aNode);
 414 }
 415
 416 template <class V>
 417 bool
 418 SplayConstIterator<V>::operator == (SplayConstIterator const &right) const
 419 {
 420     if (toVisit.empty() && right.toVisit.empty())
 421         return true;
 422     if (!toVisit.empty() && !right.toVisit.empty())
 423         return toVisit.top() == right.toVisit.top();
 424     // only one of the two is empty
 425     return false;
 426 }
 427
 428 template <class V>
 429 SplayConstIterator<V> &
 430 SplayConstIterator<V>::operator ++ ()
 431 {
 432     advance();
 433     return *this;
 434 }
 435
 436 template <class V>
 437 SplayConstIterator<V>
 438 SplayConstIterator<V>::operator ++ (int dummy)
 439 {
 440     SplayConstIterator<V> result = *this;
 441     advance();
 442     return result;
 443 }
 444
 445 /* advance is simple enough:
 446 * if the stack is empty, we're done.
 447 * otherwise, pop the last visited node
 448 * then, pop the next node to visit
 449 * if that has a right child, add it and it's
 450 * left-to-end path.
 451 * then add the node back.
 452 */
 453 template <class V>
 454 void
 455 SplayConstIterator<V>::advance()
 456 {
 457     if (toVisit.empty())
 458         return;
 459
 460     toVisit.pop();
 461
 462     if (toVisit.empty())
 463         return;
 464
 465     // not empty
 466     SplayNode<V> *currentNode = toVisit.top();
 467     toVisit.pop();
 468
 469     addLeftPath(currentNode->right);
 470
 471     toVisit.push(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(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 */
 507
 508 #endif /* SQUID_SPLAY_H */