include/splay.h

   1 /*
   2  * Copyright (C) 1996-2023 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_INCLUDE_SPLAY_H
  10 #define SQUID_INCLUDE_SPLAY_H
  11
  12 #include "fatal.h"
  13 #include <cstddef>
  14 #include <stack>
  15
  16 // private class of Splay. Do not use directly
  17 template <class V>
  18 class SplayNode
  19 {
  20 public:
  21     typedef V Value;
  22     typedef int SPLAYCMP(Value const &a, Value const &b);
  23
  24     SplayNode(const Value &);
  25     Value data;
  26     mutable SplayNode<V> *left;
  27     mutable SplayNode<V> *right;
  28     mutable SplayNode<V> *visitThreadUp;
  29
  30     SplayNode<V> const * start() const;
  31     SplayNode<V> const * finish() const;
  32
  33     SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
  34
  35     SplayNode<V> * insert(Value data, SPLAYCMP * compare);
  36
  37     /// look in the splay for data for where compare(data,candidate) == true.
  38     /// return NULL if not found, a pointer to the sought data if found.
  39     template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
  40 };
  41
  42 template <class V>
  43 class SplayConstIterator;
  44
  45 template <class V>
  46 class SplayIterator;
  47
  48 template <class V>
  49 class Splay
  50 {
  51 public:
  52     typedef V Value;
  53     typedef int SPLAYCMP(Value const &a, Value const &b);
  54     typedef void SPLAYFREE(Value &);
  55     typedef SplayIterator<V> iterator;
  56     typedef const SplayConstIterator<V> const_iterator;
  57
  58     static void DefaultFree(Value &v) { delete v; }
  59
  60     Splay():head(nullptr), elements (0) {}
  61
  62     template <class FindValue> Value const *find (FindValue const &, int( * compare)(FindValue const &a, Value const &b)) const;
  63
  64     /// If the given value matches a stored one, returns that matching value.
  65     /// Otherwise, stores the given unique value and returns nil.
  66     const Value *insert(const Value &, SPLAYCMP *);
  67
  68     void remove(Value const &, SPLAYCMP *compare);
  69
  70     void destroy(SPLAYFREE * = DefaultFree);
  71
  72     SplayNode<V> const * start() const;
  73
  74     SplayNode<V> const * finish() const;
  75
  76     size_t size() const;
  77
  78     bool empty() const { return size() == 0; }
  79
  80     const_iterator begin() const;
  81
  82     const_iterator end() const;
  83
  84     /// left-to-right visit of all stored Values
  85     template <typename ValueVisitor> void visit(ValueVisitor &) const;
  86
  87 private:
  88     /// left-to-right walk through all nodes
  89     template <typename NodeVisitor> void visitEach(NodeVisitor &) const;
  90
  91     mutable SplayNode<V> * head;
  92     size_t elements;
  93 };
  94
  95 extern int splayLastResult;
  96
  97 template<class V>
  98 SplayNode<V>::SplayNode(const Value &someData): data(someData), left(nullptr), right(nullptr), visitThreadUp(nullptr) {}
  99
 100 template<class V>
 101 SplayNode<V> const *
 102 SplayNode<V>::start() const
 103 {
 104     auto cur = this;
 105     while (cur->left)
 106         cur = cur->left;
 107     return cur;
 108 }
 109
 110 template<class V>
 111 SplayNode<V> const *
 112 SplayNode<V>::finish() const
 113 {
 114     auto cur = this;
 115     while (cur->right)
 116         cur = cur->right;
 117     return cur;
 118 }
 119
 120 template<class V>
 121 SplayNode<V> *
 122 SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare)
 123 {
 124     SplayNode<V> *result = splay(dataToRemove, compare);
 125
 126     if (splayLastResult == 0) { /* found it */
 127         SplayNode<V> *newTop;
 128
 129         if (result->left == nullptr) {
 130             newTop = result->right;
 131         } else {
 132             newTop = result->left->splay(dataToRemove, compare);
 133             /* temporary */
 134             newTop->right = result->right;
 135             result->right = nullptr;
 136         }
 137
 138         delete result;
 139         return newTop;
 140     }
 141
 142     return result;          /* It wasn't there */
 143 }
 144
 145 template<class V>
 146 SplayNode<V> *
 147 SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
 148 {
 149     /* create node to insert */
 150     SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
 151     SplayNode<V> *newTop = splay(dataToInsert, compare);
 152
 153     if (splayLastResult < 0) {
 154         newNode->left = newTop->left;
 155         newNode->right = newTop;
 156         newTop->left = nullptr;
 157         return newNode;
 158     } else if (splayLastResult > 0) {
 159         newNode->right = newTop->right;
 160         newNode->left = newTop;
 161         newTop->right = nullptr;
 162         return newNode;
 163     } else {
 164         /* duplicate entry */
 165         delete newNode;
 166         return newTop;
 167     }
 168 }
 169
 170 template<class V>
 171 template<class FindValue>
 172 SplayNode<V> *
 173 SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
 174 {
 175     Value temp = Value();
 176     SplayNode<V> N(temp);
 177     SplayNode<V> *l;
 178     SplayNode<V> *r;
 179     SplayNode<V> *y;
 180     N.left = N.right = nullptr;
 181     l = r = &N;
 182
 183     SplayNode<V> *top = const_cast<SplayNode<V> *>(this);
 184
 185     for (;;) {
 186         splayLastResult = compare(dataToFind, top->data);
 187
 188         if (splayLastResult < 0) {
 189             if (top->left == nullptr)
 190                 break;
 191
 192             if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
 193                 y = top->left;  /* rotate right */
 194                 top->left = y->right;
 195                 y->right = top;
 196                 top = y;
 197
 198                 if (top->left == nullptr)
 199                     break;
 200             }
 201
 202             r->left = top;  /* link right */
 203             r = top;
 204             top = top->left;
 205         } else if (splayLastResult > 0) {
 206             if (top->right == nullptr)
 207                 break;
 208
 209             if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
 210                 y = top->right; /* rotate left */
 211                 top->right = y->left;
 212                 y->left = top;
 213                 top = y;
 214
 215                 if (top->right == nullptr)
 216                     break;
 217             }
 218
 219             l->right = top; /* link left */
 220             l = top;
 221             top = top->right;
 222         } else {
 223             break;
 224         }
 225     }
 226
 227     l->right = top->left;   /* assemble */
 228     r->left = top->right;
 229     top->left = N.right;
 230     top->right = N.left;
 231     return top;
 232 }
 233
 234 template <class V>
 235 template <class Visitor>
 236 void
 237 Splay<V>::visitEach(Visitor &visitor) const
 238 {
 239     // In-order walk through tree using modified Morris Traversal: To avoid a
 240     // leftover thread up (and, therefore, a fatal loop in the tree) due to a
 241     // visitor exception, we use an extra pointer visitThreadUp instead of
 242     // manipulating the right child link and interfering with other methods
 243     // that use that link.
 244     // This also helps to distinguish between up and down movements, eliminating
 245     // the need to descent into left subtree a second time after traversing the
 246     // thread to find the loop and remove the temporary thread.
 247
 248     if (!head)
 249         return;
 250
 251     auto cur = head;
 252     auto movedUp = false;
 253     cur->visitThreadUp = nullptr;
 254
 255     while (cur) {
 256         if (!cur->left || movedUp) {
 257             // no (unvisited) left subtree, so handle current node ...
 258             const auto old = cur;
 259             if (cur->right) {
 260                 // ... and descent into right subtree
 261                 cur = cur->right;
 262                 movedUp = false;
 263             }
 264             else if (cur->visitThreadUp) {
 265                 // ... or back up the thread
 266                 cur = cur->visitThreadUp;
 267                 movedUp = true;
 268             } else {
 269                 // end of traversal
 270                 cur = nullptr;
 271             }
 272             visitor(old);
 273             // old may be destroyed here
 274         } else {
 275             // first descent into left subtree
 276
 277             // find right-most child in left tree
 278             auto rmc = cur->left;
 279             while (rmc->right) {
 280                 rmc->visitThreadUp = nullptr; // cleanup old threads on the way
 281                 rmc = rmc->right;
 282             }
 283             // create thread up back to cur
 284             rmc->visitThreadUp = cur;
 285
 286             // finally descent into left subtree
 287             cur = cur->left;
 288             movedUp = false;
 289         }
 290     }
 291 }
 292
 293 template <class V>
 294 template <class Visitor>
 295 void
 296 Splay<V>::visit(Visitor &visitor) const
 297 {
 298     const auto internalVisitor = [&visitor](const SplayNode<V> *node) { visitor(node->data); };
 299     visitEach(internalVisitor);
 300 }
 301
 302 template <class V>
 303 template <class FindValue>
 304 typename Splay<V>::Value const *
 305 Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
 306 {
 307     if (head == nullptr)
 308         return nullptr;
 309
 310     head = head->splay(value, compare);
 311
 312     if (splayLastResult != 0)
 313         return nullptr;
 314
 315     return &head->data;
 316 }
 317
 318 template <class V>
 319 typename Splay<V>::Value const *
 320 Splay<V>::insert(Value const &value, SPLAYCMP *compare)
 321 {
 322     if (const auto similarValue = find(value, compare))
 323         return similarValue; // do not insert duplicates
 324
 325     if (head == nullptr)
 326         head = new SplayNode<V>(value);
 327     else
 328         head = head->insert(value, compare);
 329     ++elements;
 330
 331     return nullptr; // no duplicates found
 332 }
 333
 334 template <class V>
 335 void
 336 Splay<V>::remove(Value const &value, SPLAYCMP *compare)
 337 {
 338     // also catches the head==NULL case
 339     if (find(value, compare) == nullptr)
 340         return;
 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 nullptr;
 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 nullptr;
 365 }
 366
 367 template <class V>
 368 void
 369 Splay<V>:: destroy(SPLAYFREE *free_func)
 370 {
 371     const auto destroyer = [free_func](SplayNode<V> *node) { free_func(node->data); delete node; };
 372     visitEach(destroyer);
 373
 374     head = nullptr;
 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(nullptr);
 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)
 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 == nullptr)
 489         return;
 490
 491     do {
 492         toVisit.push(aNode);
 493         aNode = aNode->left;
 494     } while (aNode != nullptr);
 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 /* SQUID_INCLUDE_SPLAY_H */
 517