]>
Commit | Line | Data |
---|---|---|
0e2cd867 | 1 | /* |
ccd33084 | 2 | * $Id: splay.h,v 1.25 2003/09/22 03:31:03 robertc Exp $ |
0e2cd867 | 3 | */ |
4 | ||
b5638623 | 5 | #ifndef SQUID_SPLAY_H |
6 | #define SQUID_SPLAY_H | |
3c01c392 | 7 | |
b67e2c8c | 8 | #ifndef __cplusplus |
9 | /* legacy C bindings - can be removed when mempool is C++ */ | |
42a503bd | 10 | |
11 | typedef struct _splay_node | |
12 | { | |
5b220cbf | 13 | void *data; |
42a503bd | 14 | |
5b220cbf | 15 | struct _splay_node *left; |
42a503bd | 16 | |
5b220cbf | 17 | struct _splay_node *right; |
42a503bd | 18 | } |
19 | ||
20 | splayNode; | |
3c01c392 | 21 | |
29b17d63 | 22 | typedef int SPLAYCMP(const void **a, const void **b); |
23 | typedef void SPLAYWALKEE(void **nodedata, void *state); | |
3c01c392 | 24 | |
e6ccf245 | 25 | SQUIDCEXTERN int splayLastResult; |
3c01c392 | 26 | |
29b17d63 | 27 | /* MUST match C++ prototypes */ |
e6ccf245 | 28 | SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, SPLAYCMP *); |
29b17d63 | 29 | SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, SPLAYCMP *); |
e6ccf245 | 30 | SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, SPLAYCMP *); |
e6ccf245 | 31 | SQUIDCEXTERN void splay_walk(splayNode *, SPLAYWALKEE *, void *); |
b67e2c8c | 32 | #else |
33 | ||
29b17d63 | 34 | |
b67e2c8c | 35 | template <class V> |
42a503bd | 36 | |
37 | class SplayNode | |
38 | { | |
39 | ||
40 | public: | |
b67e2c8c | 41 | typedef V Value; |
29b17d63 | 42 | typedef int SPLAYCMP(Value const &a, Value const &b); |
43 | typedef void SPLAYFREE(Value &); | |
44 | typedef void SPLAYWALKEE(Value const & nodedata, void *state); | |
00d77d6b | 45 | static void DefaultFree (Value &aValue) {delete aValue;} |
42a503bd | 46 | |
2bcafc95 | 47 | SplayNode<V> (Value const &); |
29b17d63 | 48 | Value data; |
49 | mutable SplayNode<V> *left; | |
50 | mutable SplayNode<V> *right; | |
51 | void destroy(SPLAYFREE *); | |
52 | void walk(SPLAYWALKEE *, void *callerState); | |
4c50505b | 53 | SplayNode<V> const * start() const; |
ccd33084 | 54 | SplayNode<V> const * finish() const; |
42a503bd | 55 | |
56 | SplayNode<V> * remove | |
57 | (const Value data, SPLAYCMP * compare); | |
58 | ||
29b17d63 | 59 | SplayNode<V> * insert(Value data, SPLAYCMP * compare); |
42a503bd | 60 | |
29b17d63 | 61 | SplayNode<V> * splay(const Value &data, SPLAYCMP * compare) const; |
b67e2c8c | 62 | }; |
63 | ||
29b17d63 | 64 | typedef SplayNode<void *> splayNode; |
65 | ||
66 | template <class V> | |
42a503bd | 67 | |
ccd33084 | 68 | class SplayIterator; |
69 | ||
70 | template <class V> | |
71 | ||
42a503bd | 72 | class Splay |
73 | { | |
74 | ||
75 | public: | |
29b17d63 | 76 | typedef V Value; |
77 | typedef int SPLAYCMP(Value const &a, Value const &b); | |
42a503bd | 78 | typedef void SPLAYFREE(Value &); |
0353e724 | 79 | Splay():head(NULL), elements (0){} |
42a503bd | 80 | |
29b17d63 | 81 | mutable SplayNode<V> * head; |
82 | Value const *find (Value const &, SPLAYCMP *compare) const; | |
0353e724 | 83 | void insert(Value const &, SPLAYCMP *compare); |
42a503bd | 84 | |
85 | void remove | |
86 | (Value const &, SPLAYCMP *compare); | |
87 | ||
88 | void destroy(SPLAYFREE *); | |
89 | ||
4c50505b | 90 | SplayNode<V> const * start() const; |
42a503bd | 91 | |
ccd33084 | 92 | SplayNode<V> const * finish() const; |
42a503bd | 93 | |
94 | size_t size() const; | |
95 | ||
0353e724 | 96 | size_t elements; |
29b17d63 | 97 | }; |
b67e2c8c | 98 | |
b67e2c8c | 99 | |
100 | SQUIDCEXTERN int splayLastResult; | |
101 | ||
29b17d63 | 102 | SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, splayNode::SPLAYCMP *); |
42a503bd | 103 | |
29b17d63 | 104 | SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, splayNode::SPLAYCMP *); |
42a503bd | 105 | |
29b17d63 | 106 | SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, splayNode::SPLAYCMP *); |
42a503bd | 107 | |
29b17d63 | 108 | SQUIDCEXTERN void splay_destroy(splayNode *, splayNode::SPLAYFREE *); |
42a503bd | 109 | |
29b17d63 | 110 | SQUIDCEXTERN void splay_walk(splayNode *, splayNode::SPLAYWALKEE *, void *callerState); |
111 | ||
112 | /* inline methods */ | |
113 | template<class V> | |
2bcafc95 | 114 | SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(NULL), right (NULL) {} |
115 | ||
87c692d7 | 116 | template<class V> |
29b17d63 | 117 | void |
118 | SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state) | |
119 | { | |
120 | if (this == NULL) | |
42a503bd | 121 | return; |
122 | ||
29b17d63 | 123 | if (left) |
42a503bd | 124 | left->walk(walkee, state); |
125 | ||
29b17d63 | 126 | walkee(data, state); |
42a503bd | 127 | |
29b17d63 | 128 | if (right) |
42a503bd | 129 | right->walk(walkee, state); |
29b17d63 | 130 | } |
131 | ||
4c50505b | 132 | template<class V> |
133 | SplayNode<V> const * | |
134 | SplayNode<V>::start() const | |
135 | { | |
136 | if (this && left) | |
42a503bd | 137 | return left->start(); |
138 | ||
139 | return this; | |
140 | } | |
141 | ||
142 | template<class V> | |
143 | SplayNode<V> const * | |
ccd33084 | 144 | SplayNode<V>::finish() const |
42a503bd | 145 | { |
146 | if (this && right) | |
ccd33084 | 147 | return right->finish(); |
42a503bd | 148 | |
4c50505b | 149 | return this; |
150 | } | |
151 | ||
29b17d63 | 152 | template<class V> |
153 | void | |
154 | SplayNode<V>::destroy(SPLAYFREE * free_func) | |
155 | { | |
156 | if (!this) | |
42a503bd | 157 | return; |
158 | ||
29b17d63 | 159 | if (left) |
42a503bd | 160 | left->destroy(free_func); |
161 | ||
29b17d63 | 162 | if (right) |
42a503bd | 163 | right->destroy(free_func); |
164 | ||
29b17d63 | 165 | free_func(data); |
42a503bd | 166 | |
29b17d63 | 167 | delete this; |
168 | } | |
169 | ||
170 | template<class V> | |
171 | SplayNode<V> * | |
42a503bd | 172 | SplayNode<V>::remove |
173 | (Value const dataToRemove, SPLAYCMP * compare) | |
29b17d63 | 174 | { |
175 | if (this == NULL) | |
42a503bd | 176 | return NULL; |
177 | ||
626e1f97 | 178 | SplayNode<V> *result = splay(dataToRemove, compare); |
42a503bd | 179 | |
29b17d63 | 180 | if (splayLastResult == 0) { /* found it */ |
42a503bd | 181 | SplayNode<V> *newTop; |
182 | ||
183 | if (result->left == NULL) { | |
184 | newTop = result->right; | |
185 | } else { | |
186 | newTop = result->left->splay(dataToRemove, compare); | |
187 | /* temporary */ | |
188 | newTop->right = result->right; | |
189 | result->right = NULL; | |
190 | } | |
191 | ||
192 | delete result; | |
193 | return newTop; | |
29b17d63 | 194 | } |
42a503bd | 195 | |
29b17d63 | 196 | return result; /* It wasn't there */ |
197 | } | |
b67e2c8c | 198 | |
29b17d63 | 199 | template<class V> |
200 | SplayNode<V> * | |
626e1f97 | 201 | SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare) |
29b17d63 | 202 | { |
203 | /* create node to insert */ | |
2bcafc95 | 204 | SplayNode<V> *newNode = new SplayNode<V>(dataToInsert); |
42a503bd | 205 | |
29b17d63 | 206 | if (this == NULL) { |
42a503bd | 207 | splayLastResult = -1; |
208 | newNode->left = newNode->right = NULL; | |
209 | return newNode; | |
29b17d63 | 210 | } |
42a503bd | 211 | |
626e1f97 | 212 | SplayNode<V> *newTop = splay(dataToInsert, compare); |
42a503bd | 213 | |
29b17d63 | 214 | if (splayLastResult < 0) { |
42a503bd | 215 | newNode->left = newTop->left; |
216 | newNode->right = newTop; | |
217 | newTop->left = NULL; | |
218 | return newNode; | |
29b17d63 | 219 | } else if (splayLastResult > 0) { |
42a503bd | 220 | newNode->right = newTop->right; |
221 | newNode->left = newTop; | |
222 | newTop->right = NULL; | |
223 | return newNode; | |
29b17d63 | 224 | } else { |
42a503bd | 225 | /* duplicate entry */ |
226 | delete newNode; | |
227 | return newTop; | |
29b17d63 | 228 | } |
229 | } | |
230 | ||
231 | template<class V> | |
232 | SplayNode<V> * | |
626e1f97 | 233 | SplayNode<V>::splay(Value const &dataToFind, SPLAYCMP * compare) const |
29b17d63 | 234 | { |
a46d2c0e | 235 | if (this == NULL) { |
42a503bd | 236 | /* can't have compared successfully :} */ |
237 | splayLastResult = -1; | |
238 | return NULL; | |
a46d2c0e | 239 | } |
42a503bd | 240 | |
2bcafc95 | 241 | SplayNode<V> N(dataToFind); |
29b17d63 | 242 | SplayNode<V> *l; |
243 | SplayNode<V> *r; | |
244 | SplayNode<V> *y; | |
245 | N.left = N.right = NULL; | |
246 | l = r = &N; | |
247 | ||
248 | SplayNode<V> *top = const_cast<SplayNode<V> *>(this); | |
42a503bd | 249 | |
29b17d63 | 250 | for (;;) { |
42a503bd | 251 | splayLastResult = compare(dataToFind, top->data); |
252 | ||
253 | if (splayLastResult < 0) { | |
254 | if (top->left == NULL) | |
255 | break; | |
256 | ||
257 | if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) { | |
258 | y = top->left; /* rotate right */ | |
259 | top->left = y->right; | |
260 | y->right = top; | |
261 | top = y; | |
262 | ||
263 | if (top->left == NULL) | |
264 | break; | |
265 | } | |
266 | ||
267 | r->left = top; /* link right */ | |
268 | r = top; | |
269 | top = top->left; | |
270 | } else if (splayLastResult > 0) { | |
271 | if (top->right == NULL) | |
272 | break; | |
273 | ||
274 | if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) { | |
275 | y = top->right; /* rotate left */ | |
276 | top->right = y->left; | |
277 | y->left = top; | |
278 | top = y; | |
279 | ||
280 | if (top->right == NULL) | |
281 | break; | |
282 | } | |
283 | ||
284 | l->right = top; /* link left */ | |
285 | l = top; | |
286 | top = top->right; | |
287 | } else { | |
288 | break; | |
289 | } | |
29b17d63 | 290 | } |
42a503bd | 291 | |
29b17d63 | 292 | l->right = top->left; /* assemble */ |
293 | r->left = top->right; | |
294 | top->left = N.right; | |
295 | top->right = N.left; | |
296 | return top; | |
297 | } | |
298 | ||
299 | template <class V> | |
300 | typename Splay<V>::Value const * | |
301 | Splay<V>::find (Value const &value, SPLAYCMP *compare) const | |
302 | { | |
303 | head = head->splay(value, compare); | |
42a503bd | 304 | |
29b17d63 | 305 | if (splayLastResult != 0) |
42a503bd | 306 | return NULL; |
307 | ||
29b17d63 | 308 | return &head->data; |
309 | } | |
b67e2c8c | 310 | |
0353e724 | 311 | template <class V> |
312 | void | |
313 | Splay<V>::insert(Value const &value, SPLAYCMP *compare) | |
314 | { | |
315 | assert (!find (value, compare)); | |
316 | head = head->insert(value, compare); | |
317 | ++elements; | |
318 | } | |
319 | ||
320 | template <class V> | |
321 | void | |
42a503bd | 322 | Splay<V>::remove |
323 | (Value const &value, SPLAYCMP *compare) | |
0353e724 | 324 | { |
325 | assert (find (value, compare)); | |
42a503bd | 326 | |
327 | head = head->remove | |
328 | (value, compare); | |
329 | ||
0353e724 | 330 | --elements; |
331 | } | |
332 | ||
4c50505b | 333 | template <class V> |
42a503bd | 334 | SplayNode<V> const * |
335 | Splay<V>:: start() const | |
336 | { | |
337 | if (head) | |
338 | return head->start(); | |
339 | ||
340 | return NULL; | |
341 | } | |
342 | ||
343 | template <class V> | |
344 | SplayNode<V> const * | |
ccd33084 | 345 | Splay<V>:: finish() const |
42a503bd | 346 | { |
4c50505b | 347 | if (head) |
ccd33084 | 348 | return head->finish(); |
42a503bd | 349 | |
4c50505b | 350 | return NULL; |
351 | } | |
352 | ||
42a503bd | 353 | template <class V> |
354 | void | |
355 | Splay<V>:: destroy(SPLAYFREE *free_func) | |
356 | { | |
357 | if (head) | |
358 | head->destroy(free_func); | |
359 | ||
360 | head = NULL; | |
361 | ||
362 | elements = 0; | |
363 | } | |
364 | ||
365 | template <class V> | |
366 | size_t | |
367 | Splay<V>::size() const | |
368 | { | |
369 | return elements; | |
370 | } | |
371 | ||
b67e2c8c | 372 | #endif |
bdffbfa5 | 373 | |
b5638623 | 374 | #endif /* SQUID_SPLAY_H */ |