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