include/splay.h

   1 /*
   2  * $Id: splay.h,v 1.16 2003/02/12 06:10:50 robertc Exp $
   3  */
   4
   5 #ifndef SQUID_SPLAY_H
   6 #define SQUID_SPLAY_H
   7
   8 #ifndef __cplusplus
   9 /* legacy C bindings - can be removed when mempool is C++ */
  10 typedef struct _splay_node {
  11     void *data;
  12     struct _splay_node *left;
  13     struct _splay_node *right;
  14 } splayNode;
  15
  16 typedef int SPLAYCMP(const void **a, const void **b);
  17 typedef void SPLAYWALKEE(void **nodedata, void *state);
  18
  19 SQUIDCEXTERN int splayLastResult;
  20
  21 /* MUST match C++ prototypes */
  22 SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, SPLAYCMP *);
  23 SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, SPLAYCMP *);
  24 SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, SPLAYCMP *);
  25 SQUIDCEXTERN void splay_walk(splayNode *, SPLAYWALKEE *, void *);
  26 #else
  27
  28
  29 template <class V>
  30 class SplayNode {
  31   public:
  32     typedef V Value;
  33     typedef int SPLAYCMP(Value const &a, Value const &b);
  34     typedef void SPLAYFREE(Value &);
  35     typedef void SPLAYWALKEE(Value const & nodedata, void *state);
  36     static void DefaultFree (Value &aValue) {aValue->deleteSelf();}
  37     Value data;
  38     mutable SplayNode<V> *left;
  39     mutable SplayNode<V> *right;
  40     void destroy(SPLAYFREE *);
  41     void walk(SPLAYWALKEE *, void *callerState);
  42     SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
  43     SplayNode<V> * insert(Value data, SPLAYCMP * compare);
  44     SplayNode<V> * splay(const Value &data, SPLAYCMP * compare) const;
  45 };
  46
  47 typedef SplayNode<void *> splayNode;
  48
  49 template <class V>
  50 class Splay {
  51   public:
  52     typedef V Value;
  53     typedef int SPLAYCMP(Value const &a, Value const &b);
  54     Splay():head(NULL){}
  55     mutable SplayNode<V> * head;
  56     Value const *find (Value const &, SPLAYCMP *compare) const;
  57 };
  58
  59
  60 SQUIDCEXTERN int splayLastResult;
  61
  62 SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, splayNode::SPLAYCMP *);
  63 SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, splayNode::SPLAYCMP *);
  64 SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, splayNode::SPLAYCMP *);
  65 SQUIDCEXTERN void splay_destroy(splayNode *, splayNode::SPLAYFREE *);
  66 SQUIDCEXTERN void splay_walk(splayNode *, splayNode::SPLAYWALKEE *, void *callerState);
  67
  68 /* inline methods */
  69 template<class V>
  70 void
  71 SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
  72 {
  73     if (this == NULL)
  74         return;
  75     if (left)
  76         left->walk(walkee, state);
  77     walkee(data, state);
  78     if (right)
  79         right->walk(walkee, state);
  80 }
  81
  82 template<class V>
  83 void
  84 SplayNode<V>::destroy(SPLAYFREE * free_func)
  85 {
  86     if (!this)
  87         return;
  88     if (left)
  89         left->destroy(free_func);
  90     if (right)
  91         right->destroy(free_func);
  92     free_func(data);
  93     delete this;
  94 }
  95
  96 template<class V>
  97 SplayNode<V> *
  98 SplayNode<V>::remove(Value const data, SPLAYCMP * compare)
  99 {
 100     if (this == NULL)
 101         return NULL;
 102     SplayNode<V> *result = splay(data, compare);
 103     if (splayLastResult == 0) { /* found it */
 104         SplayNode<V> *newTop;
 105         if (result->left == NULL) {
 106             newTop = result->right;
 107         } else {
 108             newTop = result->left->splay(data, compare);
 109             /* temporary */
 110             newTop->right = result->right;
 111             result->right = NULL;
 112         }
 113         delete result;
 114         return newTop;
 115     }
 116     return result;                      /* It wasn't there */
 117 }
 118
 119 template<class V>
 120 SplayNode<V> *
 121 SplayNode<V>::insert(Value data, SPLAYCMP * compare)
 122 {
 123     /* create node to insert */
 124     SplayNode<V> *newNode = new SplayNode<V>;
 125     newNode->data = data;
 126     if (this == NULL) {
 127         newNode->left = newNode->right = NULL;
 128         return newNode;
 129     }
 130
 131     SplayNode<V> *newTop = splay(data, compare);
 132     if (splayLastResult < 0) {
 133         newNode->left = newTop->left;
 134         newNode->right = newTop;
 135         newTop->left = NULL;
 136         return newNode;
 137     } else if (splayLastResult > 0) {
 138         newNode->right = newTop->right;
 139         newNode->left = newTop;
 140         newTop->right = NULL;
 141         return newNode;
 142     } else {
 143         /* duplicate entry */
 144         delete newNode;
 145         return newTop;
 146     }
 147 }
 148
 149 template<class V>
 150 SplayNode<V> *
 151 SplayNode<V>::splay(Value const &data, SPLAYCMP * compare) const
 152 {
 153     if (this == NULL)
 154         return NULL;
 155     SplayNode<V> N;
 156     SplayNode<V> *l;
 157     SplayNode<V> *r;
 158     SplayNode<V> *y;
 159     N.left = N.right = NULL;
 160     l = r = &N;
 161
 162     SplayNode<V> *top = const_cast<SplayNode<V> *>(this);
 163     for (;;) {
 164         splayLastResult = compare(data, top->data);
 165         if (splayLastResult < 0) {
 166             if (top->left == NULL)
 167                 break;
 168             if ((splayLastResult = compare(data, top->left->data)) < 0) {
 169                 y = top->left;  /* rotate right */
 170                 top->left = y->right;
 171                 y->right = top;
 172                 top = y;
 173                 if (top->left == NULL)
 174                     break;
 175             }
 176             r->left = top;      /* link right */
 177             r = top;
 178             top = top->left;
 179         } else if (splayLastResult > 0) {
 180             if (top->right == NULL)
 181                 break;
 182             if ((splayLastResult = compare(data, top->right->data)) > 0) {
 183                 y = top->right; /* rotate left */
 184                 top->right = y->left;
 185                 y->left = top;
 186                 top = y;
 187                 if (top->right == NULL)
 188                     break;
 189             }
 190             l->right = top;     /* link left */
 191             l = top;
 192             top = top->right;
 193         } else {
 194             break;
 195         }
 196     }
 197     l->right = top->left;       /* assemble */
 198     r->left = top->right;
 199     top->left = N.right;
 200     top->right = N.left;
 201     return top;
 202 }
 203
 204 template <class V>
 205 typename Splay<V>::Value const *
 206 Splay<V>::find (Value const &value, SPLAYCMP *compare) const
 207 {
 208     head = head->splay(value, compare);
 209     if (splayLastResult != 0)
 210         return NULL;
 211     return &head->data;
 212 }
 213
 214 #endif
 215
 216 #endif /* SQUID_SPLAY_H */