include/splay.h

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