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