include/splay.h

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