include/splay.h

   1 /*
   2  * $Id: splay.h,v 1.29 2005/05/08 22:35:03 hno Exp $
   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
  15 class SplayNode
  16 {
  17
  18 public:
  19     typedef V Value;
  20     typedef int SPLAYCMP(Value const &a, Value const &b);
  21     typedef void SPLAYFREE(Value &);
  22     typedef void SPLAYWALKEE(Value const & nodedata, void *state);
  23     static void DefaultFree (Value &aValue) {delete aValue;}
  24
  25     SplayNode<V> (Value const &);
  26     Value data;
  27     mutable SplayNode<V> *left;
  28     mutable SplayNode<V> *right;
  29     void destroy(SPLAYFREE *);
  30     void walk(SPLAYWALKEE *, void *callerState);
  31     bool empty() const { return this == NULL; }
  32     SplayNode<V> const * start() const;
  33     SplayNode<V> const * finish() const;
  34
  35     SplayNode<V> * remove
  36     (const Value data, SPLAYCMP * compare);
  37
  38     SplayNode<V> * insert(Value data, SPLAYCMP * compare);
  39
  40     template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
  41 };
  42
  43 typedef SplayNode<void *> splayNode;
  44
  45 template <class V>
  46
  47 class SplayConstIterator;
  48
  49 template <class V>
  50
  51 class SplayIterator;
  52
  53 template <class V>
  54
  55 class Splay
  56 {
  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     mutable SplayNode<V> * head;
  67     template <class FindValue> Value const *find (FindValue const &, int( * compare)(FindValue const &a, Value const &b)) const;
  68     void insert(Value const &, SPLAYCMP *compare);
  69
  70     void remove
  71     (Value const &, SPLAYCMP *compare);
  72
  73     void destroy(SPLAYFREE *);
  74
  75     SplayNode<V> const * start() const;
  76
  77     SplayNode<V> const * finish() const;
  78
  79     size_t size() const;
  80
  81     const_iterator begin() const;
  82
  83     const_iterator end() const;
  84
  85     size_t elements;
  86 };
  87
  88
  89 SQUIDCEXTERN int splayLastResult;
  90
  91 SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, splayNode::SPLAYCMP *);
  92
  93 SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, splayNode::SPLAYCMP *);
  94
  95 SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, splayNode::SPLAYCMP *);
  96
  97 SQUIDCEXTERN void splay_destroy(splayNode *, splayNode::SPLAYFREE *);
  98
  99 SQUIDCEXTERN void splay_walk(splayNode *, splayNode::SPLAYWALKEE *, void *callerState);
 100
 101 /* inline methods */
 102 template<class V>
 103 SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(NULL), right (NULL) {}
 104
 105 template<class V>
 106 void
 107 SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
 108 {
 109     if (this == NULL)
 110         return;
 111
 112     if (left)
 113         left->walk(walkee, state);
 114
 115     walkee(data, state);
 116
 117     if (right)
 118         right->walk(walkee, state);
 119 }
 120
 121 template<class V>
 122 SplayNode<V> const *
 123 SplayNode<V>::start() const
 124 {
 125     if (this && left)
 126         return left->start();
 127
 128     return this;
 129 }
 130
 131 template<class V>
 132 SplayNode<V> const *
 133 SplayNode<V>::finish() const
 134 {
 135     if (this && right)
 136         return right->finish();
 137
 138     return this;
 139 }
 140
 141 template<class V>
 142 void
 143 SplayNode<V>::destroy(SPLAYFREE * free_func)
 144 {
 145     if (!this)
 146         return;
 147
 148     if (left)
 149         left->destroy(free_func);
 150
 151     if (right)
 152         right->destroy(free_func);
 153
 154     free_func(data);
 155
 156     delete this;
 157 }
 158
 159 template<class V>
 160 SplayNode<V> *
 161 SplayNode<V>::remove
 162 (Value const dataToRemove, SPLAYCMP * compare)
 163 {
 164     if (this == NULL)
 165         return NULL;
 166
 167     SplayNode<V> *result = splay(dataToRemove, compare);
 168
 169     if (splayLastResult == 0) { /* found it */
 170         SplayNode<V> *newTop;
 171
 172         if (result->left == NULL) {
 173             newTop = result->right;
 174         } else {
 175             newTop = result->left->splay(dataToRemove, compare);
 176             /* temporary */
 177             newTop->right = result->right;
 178             result->right = NULL;
 179         }
 180
 181         delete result;
 182         return newTop;
 183     }
 184
 185     return result;                      /* It wasn't there */
 186 }
 187
 188 template<class V>
 189 SplayNode<V> *
 190 SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
 191 {
 192     /* create node to insert */
 193     SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
 194
 195     if (this == NULL) {
 196         splayLastResult = -1;
 197         newNode->left = newNode->right = NULL;
 198         return newNode;
 199     }
 200
 201     SplayNode<V> *newTop = splay(dataToInsert, compare);
 202
 203     if (splayLastResult < 0) {
 204         newNode->left = newTop->left;
 205         newNode->right = newTop;
 206         newTop->left = NULL;
 207         return newNode;
 208     } else if (splayLastResult > 0) {
 209         newNode->right = newTop->right;
 210         newNode->left = newTop;
 211         newTop->right = NULL;
 212         return newNode;
 213     } else {
 214         /* duplicate entry */
 215         delete newNode;
 216         return newTop;
 217     }
 218 }
 219
 220 template<class V>
 221 template<class FindValue>
 222 SplayNode<V> *
 223 SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
 224 {
 225     if (this == NULL) {
 226         /* can't have compared successfully :} */
 227         splayLastResult = -1;
 228         return NULL;
 229     }
 230
 231     Value temp = Value();
 232     SplayNode<V> N(temp);
 233     SplayNode<V> *l;
 234     SplayNode<V> *r;
 235     SplayNode<V> *y;
 236     N.left = N.right = NULL;
 237     l = r = &N;
 238
 239     SplayNode<V> *top = const_cast<SplayNode<V> *>(this);
 240
 241     for (;;) {
 242         splayLastResult = compare(dataToFind, top->data);
 243
 244         if (splayLastResult < 0) {
 245             if (top->left == NULL)
 246                 break;
 247
 248             if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
 249                 y = top->left;  /* rotate right */
 250                 top->left = y->right;
 251                 y->right = top;
 252                 top = y;
 253
 254                 if (top->left == NULL)
 255                     break;
 256             }
 257
 258             r->left = top;      /* link right */
 259             r = top;
 260             top = top->left;
 261         } else if (splayLastResult > 0) {
 262             if (top->right == NULL)
 263                 break;
 264
 265             if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
 266                 y = top->right; /* rotate left */
 267                 top->right = y->left;
 268                 y->left = top;
 269                 top = y;
 270
 271                 if (top->right == NULL)
 272                     break;
 273             }
 274
 275             l->right = top;     /* link left */
 276             l = top;
 277             top = top->right;
 278         } else {
 279             break;
 280         }
 281     }
 282
 283     l->right = top->left;       /* assemble */
 284     r->left = top->right;
 285     top->left = N.right;
 286     top->right = N.left;
 287     return top;
 288 }
 289
 290 template <class V>
 291 template <class FindValue>
 292 typename Splay<V>::Value const *
 293 Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
 294 {
 295     head = head->splay(value, compare);
 296
 297     if (splayLastResult != 0)
 298         return NULL;
 299
 300     return &head->data;
 301 }
 302
 303 template <class V>
 304 void
 305 Splay<V>::insert(Value const &value, SPLAYCMP *compare)
 306 {
 307     assert (!find (value, compare));
 308     head = head->insert(value, compare);
 309     ++elements;
 310 }
 311
 312 template <class V>
 313 void
 314 Splay<V>::remove
 315 (Value const &value, SPLAYCMP *compare)
 316 {
 317     assert (find (value, compare));
 318
 319     head = head->remove
 320            (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 template <class V>
 379
 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     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     return toVisit.top() == right.toVisit.top();
 409 }
 410
 411 template <class V>
 412 SplayConstIterator<V> &
 413 SplayConstIterator<V>::operator ++ ()
 414 {
 415     advance();
 416     return *this;
 417 }
 418
 419 template <class V>
 420 SplayConstIterator<V>
 421 SplayConstIterator<V>::operator ++ (int dummy)
 422 {
 423     SplayConstIterator<V> result = *this;
 424     advance();
 425     return result;
 426 }
 427
 428 /* advance is simple enough:
 429 * if the stack is empty, we're done.
 430 * otherwise, pop the last visited node
 431 * then, pop the next node to visit
 432 * if that has a right child, add it and it's
 433 * left-to-end path.
 434 * then add the node back.
 435 */
 436 template <class V>
 437 void
 438 SplayConstIterator<V>::advance()
 439 {
 440     if (toVisit.size() == 0)
 441         return;
 442
 443     toVisit.pop();
 444
 445     if (toVisit.size() == 0)
 446         return;
 447
 448     SplayNode<V> *currentNode = toVisit.pop();
 449
 450     addLeftPath(currentNode->right);
 451
 452     toVisit.push_back(currentNode);
 453 }
 454
 455 template <class V>
 456 void
 457 SplayConstIterator<V>::addLeftPath(SplayNode<V> *aNode)
 458 {
 459     if (aNode == NULL)
 460         return;
 461
 462     do {
 463         toVisit.push_back(aNode);
 464         aNode = aNode->left;
 465     } while (aNode != NULL);
 466 }
 467
 468 template <class V>
 469 void
 470 SplayConstIterator<V>::init(SplayNode<V> *head)
 471 {
 472     addLeftPath(head);
 473 }
 474
 475 template <class V>
 476 V const &
 477 SplayConstIterator<V>::operator * () const
 478 {
 479     /* can't dereference when past the end */
 480
 481     if (toVisit.size() == 0)
 482         fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
 483
 484     return toVisit.top()->data;
 485 }
 486
 487 #endif /* cplusplus */
 488
 489 #endif /* SQUID_SPLAY_H */