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