include/splay.h

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