include/splay.h

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