include/splay.h

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