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 this == NULL; }
  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 (this == NULL)
 114         return;
 115
 116     if (left)
 117         left->walk(walkee, state);
 118
 119     walkee(data, state);
 120
 121     if (right)
 122         right->walk(walkee, state);
 123 }
 124
 125 template<class V>
 126 SplayNode<V> const *
 127 SplayNode<V>::start() const
 128 {
 129     if (this && left)
 130         return left->start();
 131
 132     return this;
 133 }
 134
 135 template<class V>
 136 SplayNode<V> const *
 137 SplayNode<V>::finish() const
 138 {
 139     if (this && right)
 140         return right->finish();
 141
 142     return this;
 143 }
 144
 145 template<class V>
 146 void
 147 SplayNode<V>::destroy(SPLAYFREE * free_func)
 148 {
 149     if (!this)
 150         return;
 151
 152     if (left)
 153         left->destroy(free_func);
 154
 155     if (right)
 156         right->destroy(free_func);
 157
 158     free_func(data);
 159
 160     delete this;
 161 }
 162
 163 template<class V>
 164 SplayNode<V> *
 165 SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare)
 166 {
 167     if (this == NULL)
 168         return NULL;
 169
 170     SplayNode<V> *result = splay(dataToRemove, compare);
 171
 172     if (splayLastResult == 0) { /* found it */
 173         SplayNode<V> *newTop;
 174
 175         if (result->left == NULL) {
 176             newTop = result->right;
 177         } else {
 178             newTop = result->left->splay(dataToRemove, compare);
 179             /* temporary */
 180             newTop->right = result->right;
 181             result->right = NULL;
 182         }
 183
 184         delete result;
 185         return newTop;
 186     }
 187
 188     return result;          /* It wasn't there */
 189 }
 190
 191 template<class V>
 192 SplayNode<V> *
 193 SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
 194 {
 195     /* create node to insert */
 196     SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
 197
 198     if (this == NULL) {
 199         splayLastResult = -1;
 200         newNode->left = newNode->right = NULL;
 201         return newNode;
 202     }
 203
 204     SplayNode<V> *newTop = splay(dataToInsert, compare);
 205
 206     if (splayLastResult < 0) {
 207         newNode->left = newTop->left;
 208         newNode->right = newTop;
 209         newTop->left = NULL;
 210         return newNode;
 211     } else if (splayLastResult > 0) {
 212         newNode->right = newTop->right;
 213         newNode->left = newTop;
 214         newTop->right = NULL;
 215         return newNode;
 216     } else {
 217         /* duplicate entry */
 218         delete newNode;
 219         return newTop;
 220     }
 221 }
 222
 223 template<class V>
 224 template<class FindValue>
 225 SplayNode<V> *
 226 SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
 227 {
 228     if (this == NULL) {
 229         /* can't have compared successfully :} */
 230         splayLastResult = -1;
 231         return NULL;
 232     }
 233
 234     Value temp = Value();
 235     SplayNode<V> N(temp);
 236     SplayNode<V> *l;
 237     SplayNode<V> *r;
 238     SplayNode<V> *y;
 239     N.left = N.right = NULL;
 240     l = r = &N;
 241
 242     SplayNode<V> *top = const_cast<SplayNode<V> *>(this);
 243
 244     for (;;) {
 245         splayLastResult = compare(dataToFind, top->data);
 246
 247         if (splayLastResult < 0) {
 248             if (top->left == NULL)
 249                 break;
 250
 251             if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
 252                 y = top->left;  /* rotate right */
 253                 top->left = y->right;
 254                 y->right = top;
 255                 top = y;
 256
 257                 if (top->left == NULL)
 258                     break;
 259             }
 260
 261             r->left = top;  /* link right */
 262             r = top;
 263             top = top->left;
 264         } else if (splayLastResult > 0) {
 265             if (top->right == NULL)
 266                 break;
 267
 268             if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
 269                 y = top->right; /* rotate left */
 270                 top->right = y->left;
 271                 y->left = top;
 272                 top = y;
 273
 274                 if (top->right == NULL)
 275                     break;
 276             }
 277
 278             l->right = top; /* link left */
 279             l = top;
 280             top = top->right;
 281         } else {
 282             break;
 283         }
 284     }
 285
 286     l->right = top->left;   /* assemble */
 287     r->left = top->right;
 288     top->left = N.right;
 289     top->right = N.left;
 290     return top;
 291 }
 292
 293 template <class V>
 294 template <class Visitor>
 295 void
 296 SplayNode<V>::visit(Visitor &visitor) const
 297 {
 298     if (left)
 299         left->visit(visitor);
 300     visitor(data);
 301     if (right)
 302         right->visit(visitor);
 303 }
 304
 305 template <class V>
 306 template <class Visitor>
 307 void
 308 Splay<V>::visit(Visitor &visitor) const
 309 {
 310     if (head)
 311         head->visit(visitor);
 312 }
 313
 314 template <class V>
 315 template <class FindValue>
 316 typename Splay<V>::Value const *
 317 Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
 318 {
 319     head = head->splay(value, compare);
 320
 321     if (splayLastResult != 0)
 322         return NULL;
 323
 324     return &head->data;
 325 }
 326
 327 template <class V>
 328 void
 329 Splay<V>::insert(Value const &value, SPLAYCMP *compare)
 330 {
 331     assert (!find (value, compare));
 332     head = head->insert(value, compare);
 333     ++elements;
 334 }
 335
 336 template <class V>
 337 void
 338 Splay<V>::remove(Value const &value, SPLAYCMP *compare)
 339 {
 340     assert (find (value, compare));
 341
 342     head = head->remove(value, compare);
 343
 344     --elements;
 345 }
 346
 347 template <class V>
 348 SplayNode<V> const *
 349 Splay<V>:: start() const
 350 {
 351     if (head)
 352         return head->start();
 353
 354     return NULL;
 355 }
 356
 357 template <class V>
 358 SplayNode<V> const *
 359 Splay<V>:: finish() const
 360 {
 361     if (head)
 362         return head->finish();
 363
 364     return NULL;
 365 }
 366
 367 template <class V>
 368 void
 369 Splay<V>:: destroy(SPLAYFREE *free_func)
 370 {
 371     if (head)
 372         head->destroy(free_func);
 373
 374     head = NULL;
 375
 376     elements = 0;
 377 }
 378
 379 template <class V>
 380 size_t
 381 Splay<V>::size() const
 382 {
 383     return elements;
 384 }
 385
 386 template <class V>
 387 const SplayConstIterator<V>
 388 Splay<V>::begin() const
 389 {
 390     return const_iterator(head);
 391 }
 392
 393 template <class V>
 394 const SplayConstIterator<V>
 395 Splay<V>::end() const
 396 {
 397     return const_iterator(NULL);
 398 }
 399
 400 // XXX: This does not seem to iterate the whole thing in some cases.
 401 template <class V>
 402 class SplayConstIterator
 403 {
 404
 405 public:
 406     typedef const V value_type;
 407     SplayConstIterator (SplayNode<V> *aNode);
 408     bool operator == (SplayConstIterator const &right) const;
 409     SplayConstIterator operator ++ (int dummy);
 410     SplayConstIterator &operator ++ ();
 411     V const & operator * () const;
 412
 413 private:
 414     void advance();
 415     void addLeftPath(SplayNode<V> *aNode);
 416     void init(SplayNode<V> *);
 417     std::stack<SplayNode<V> *> toVisit;
 418 };
 419
 420 template <class V>
 421 SplayConstIterator<V>::SplayConstIterator (SplayNode<V> *aNode)
 422 {
 423     init(aNode);
 424 }
 425
 426 template <class V>
 427 bool
 428 SplayConstIterator<V>::operator == (SplayConstIterator const &right) const
 429 {
 430     if (toVisit.empty() && right.toVisit.empty())
 431         return true;
 432     if (!toVisit.empty() && !right.toVisit.empty())
 433         return toVisit.top() == right.toVisit.top();
 434     // only one of the two is empty
 435     return false;
 436 }
 437
 438 template <class V>
 439 SplayConstIterator<V> &
 440 SplayConstIterator<V>::operator ++ ()
 441 {
 442     advance();
 443     return *this;
 444 }
 445
 446 template <class V>
 447 SplayConstIterator<V>
 448 SplayConstIterator<V>::operator ++ (int dummy)
 449 {
 450     SplayConstIterator<V> result = *this;
 451     advance();
 452     return result;
 453 }
 454
 455 /* advance is simple enough:
 456 * if the stack is empty, we're done.
 457 * otherwise, pop the last visited node
 458 * then, pop the next node to visit
 459 * if that has a right child, add it and it's
 460 * left-to-end path.
 461 * then add the node back.
 462 */
 463 template <class V>
 464 void
 465 SplayConstIterator<V>::advance()
 466 {
 467     if (toVisit.empty())
 468         return;
 469
 470     toVisit.pop();
 471
 472     if (toVisit.empty())
 473         return;
 474
 475     // not empty
 476     SplayNode<V> *currentNode = toVisit.top();
 477     toVisit.pop();
 478
 479     addLeftPath(currentNode->right);
 480
 481     toVisit.push(currentNode);
 482 }
 483
 484 template <class V>
 485 void
 486 SplayConstIterator<V>::addLeftPath(SplayNode<V> *aNode)
 487 {
 488     if (aNode == NULL)
 489         return;
 490
 491     do {
 492         toVisit.push(aNode);
 493         aNode = aNode->left;
 494     } while (aNode != NULL);
 495 }
 496
 497 template <class V>
 498 void
 499 SplayConstIterator<V>::init(SplayNode<V> *head)
 500 {
 501     addLeftPath(head);
 502 }
 503
 504 template <class V>
 505 V const &
 506 SplayConstIterator<V>::operator * () const
 507 {
 508     /* can't dereference when past the end */
 509
 510     if (toVisit.size() == 0)
 511         fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
 512
 513     return toVisit.top()->data;
 514 }
 515
 516 #endif /* cplusplus */
 517
 518 #endif /* SQUID_SPLAY_H */
 519