1 /*
2 * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
3 *
4 * Squid software is distributed under GPLv2+ license and includes
5 * contributions from numerous individuals and organizations.
6 * Please see the COPYING and CONTRIBUTORS files for details.
7 */
8
9 #ifndef SQUID_SPLAY_H
10 #define SQUID_SPLAY_H
11
12 #include "fatal.h"
13 #include <stack>
14
15 // private class of Splay. Do not use directly
16 template <class V>
17 class SplayNode
18 {
19 public:
20 typedef V Value;
21 typedef int SPLAYCMP(Value const &a, Value const &b);
22 typedef void SPLAYFREE(Value &);
23 typedef void SPLAYWALKEE(Value const & nodedata, void *state);
DefaultFree(Value & aValue)24 static void DefaultFree (Value &aValue) {delete aValue;}
25
26 SplayNode<V> (Value const &);
27 Value data;
28 mutable SplayNode<V> *left;
29 mutable SplayNode<V> *right;
30 void destroy(SPLAYFREE * = DefaultFree);
31 void walk(SPLAYWALKEE *, void *callerState);
32 SplayNode<V> const * start() const;
33 SplayNode<V> const * finish() const;
34
35 SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
36
37 SplayNode<V> * insert(Value data, SPLAYCMP * compare);
38
39 /// look in the splay for data for where compare(data,candidate) == true.
40 /// return NULL if not found, a pointer to the sought data if found.
41 template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
42
43 /// recursively visit left nodes, this node, and then right nodes
44 template <class Visitor> void visit(Visitor &v) const;
45 };
46
47 typedef SplayNode<void *> splayNode;
48
49 template <class V>
50 class SplayConstIterator;
51
52 template <class V>
53 class SplayIterator;
54
55 template <class V>
56 class Splay
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;
Splay()64 Splay():head(NULL), elements (0) {}
65
66 template <class FindValue> Value const *find (FindValue const &, int( * compare)(FindValue const &a, Value const &b)) const;
67
68 void insert(Value const &, SPLAYCMP *compare);
69
70 void remove(Value const &, SPLAYCMP *compare);
71
72 void destroy(SPLAYFREE * = SplayNode<V>::DefaultFree);
73
74 SplayNode<V> const * start() const;
75
76 SplayNode<V> const * finish() const;
77
78 size_t size() const;
79
empty()80 bool empty() const { return size() == 0; }
81
82 const_iterator begin() const;
83
84 const_iterator end() const;
85
86 /// recursively visit all nodes, in left-to-right order
87 template <class Visitor> void visit(Visitor &v) const;
88
89 private:
90 mutable SplayNode<V> * head;
91 size_t elements;
92 };
93
94 SQUIDCEXTERN int splayLastResult;
95
96 template<class V>
SplayNode(Value const & someData)97 SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(NULL), right (NULL) {}
98
99 template<class V>
100 void
walk(SPLAYWALKEE * walkee,void * state)101 SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
102 {
103 if (left)
104 left->walk(walkee, state);
105
106 walkee(data, state);
107
108 if (right)
109 right->walk(walkee, state);
110 }
111
112 template<class V>
113 SplayNode<V> const *
start()114 SplayNode<V>::start() const
115 {
116 if (left)
117 return left->start();
118
119 return this;
120 }
121
122 template<class V>
123 SplayNode<V> const *
finish()124 SplayNode<V>::finish() const
125 {
126 if (right)
127 return right->finish();
128
129 return this;
130 }
131
132 template<class V>
133 void
destroy(SPLAYFREE * free_func)134 SplayNode<V>::destroy(SPLAYFREE * free_func)
135 {
136 if (left)
137 left->destroy(free_func);
138
139 if (right)
140 right->destroy(free_func);
141
142 free_func(data);
143
144 delete this;
145 }
146
147 template<class V>
148 SplayNode<V> *
remove(Value const dataToRemove,SPLAYCMP * compare)149 SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare)
150 {
151 SplayNode<V> *result = splay(dataToRemove, compare);
152
153 if (splayLastResult == 0) { /* found it */
154 SplayNode<V> *newTop;
155
156 if (result->left == NULL) {
157 newTop = result->right;
158 } else {
159 newTop = result->left->splay(dataToRemove, compare);
160 /* temporary */
161 newTop->right = result->right;
162 result->right = NULL;
163 }
164
165 delete result;
166 return newTop;
167 }
168
169 return result; /* It wasn't there */
170 }
171
172 template<class V>
173 SplayNode<V> *
insert(Value dataToInsert,SPLAYCMP * compare)174 SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
175 {
176 /* create node to insert */
177 SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
178 SplayNode<V> *newTop = splay(dataToInsert, compare);
179
180 if (splayLastResult < 0) {
181 newNode->left = newTop->left;
182 newNode->right = newTop;
183 newTop->left = NULL;
184 return newNode;
185 } else if (splayLastResult > 0) {
186 newNode->right = newTop->right;
187 newNode->left = newTop;
188 newTop->right = NULL;
189 return newNode;
190 } else {
191 /* duplicate entry */
192 delete newNode;
193 return newTop;
194 }
195 }
196
197 template<class V>
198 template<class FindValue>
199 SplayNode<V> *
splay(FindValue const & dataToFind,int (* compare)(FindValue const & a,Value const & b))200 SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
201 {
202 Value temp = Value();
203 SplayNode<V> N(temp);
204 SplayNode<V> *l;
205 SplayNode<V> *r;
206 SplayNode<V> *y;
207 N.left = N.right = NULL;
208 l = r = &N;
209
210 SplayNode<V> *top = const_cast<SplayNode<V> *>(this);
211
212 for (;;) {
213 splayLastResult = compare(dataToFind, top->data);
214
215 if (splayLastResult < 0) {
216 if (top->left == NULL)
217 break;
218
219 if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
220 y = top->left; /* rotate right */
221 top->left = y->right;
222 y->right = top;
223 top = y;
224
225 if (top->left == NULL)
226 break;
227 }
228
229 r->left = top; /* link right */
230 r = top;
231 top = top->left;
232 } else if (splayLastResult > 0) {
233 if (top->right == NULL)
234 break;
235
236 if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
237 y = top->right; /* rotate left */
238 top->right = y->left;
239 y->left = top;
240 top = y;
241
242 if (top->right == NULL)
243 break;
244 }
245
246 l->right = top; /* link left */
247 l = top;
248 top = top->right;
249 } else {
250 break;
251 }
252 }
253
254 l->right = top->left; /* assemble */
255 r->left = top->right;
256 top->left = N.right;
257 top->right = N.left;
258 return top;
259 }
260
261 template <class V>
262 template <class Visitor>
263 void
visit(Visitor & visitor)264 SplayNode<V>::visit(Visitor &visitor) const
265 {
266 if (left)
267 left->visit(visitor);
268 visitor(data);
269 if (right)
270 right->visit(visitor);
271 }
272
273 template <class V>
274 template <class Visitor>
275 void
visit(Visitor & visitor)276 Splay<V>::visit(Visitor &visitor) const
277 {
278 if (head)
279 head->visit(visitor);
280 }
281
282 template <class V>
283 template <class FindValue>
284 typename Splay<V>::Value const *
find(FindValue const & value,int (* compare)(FindValue const & a,Value const & b))285 Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
286 {
287 if (head == NULL)
288 return NULL;
289
290 head = head->splay(value, compare);
291
292 if (splayLastResult != 0)
293 return NULL;
294
295 return &head->data;
296 }
297
298 template <class V>
299 void
insert(Value const & value,SPLAYCMP * compare)300 Splay<V>::insert(Value const &value, SPLAYCMP *compare)
301 {
302 if (find(value, compare) != NULL) // ignore duplicates
303 return;
304
305 if (head == NULL)
306 head = new SplayNode<V>(value);
307 else
308 head = head->insert(value, compare);
309 ++elements;
310 }
311
312 template <class V>
313 void
remove(Value const & value,SPLAYCMP * compare)314 Splay<V>::remove(Value const &value, SPLAYCMP *compare)
315 {
316 // also catches the head==NULL case
317 if (find(value, compare) == NULL)
318 return;
319
320 head = head->remove(value, compare);
321
322 --elements;
323 }
324
325 template <class V>
326 SplayNode<V> const *
start()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 *
finish()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
destroy(SPLAYFREE * free_func)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
size()359 Splay<V>::size() const
360 {
361 return elements;
362 }
363
364 template <class V>
365 const SplayConstIterator<V>
begin()366 Splay<V>::begin() const
367 {
368 return const_iterator(head);
369 }
370
371 template <class V>
372 const SplayConstIterator<V>
end()373 Splay<V>::end() const
374 {
375 return const_iterator(NULL);
376 }
377
378 // XXX: This does not seem to iterate the whole thing in some cases.
379 template <class V>
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 std::stack<SplayNode<V> *> toVisit;
396 };
397
398 template <class V>
SplayConstIterator(SplayNode<V> * aNode)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 if (toVisit.empty() && right.toVisit.empty())
409 return true;
410 if (!toVisit.empty() && !right.toVisit.empty())
411 return toVisit.top() == right.toVisit.top();
412 // only one of the two is empty
413 return false;
414 }
415
416 template <class V>
417 SplayConstIterator<V> &
418 SplayConstIterator<V>::operator ++ ()
419 {
420 advance();
421 return *this;
422 }
423
424 template <class V>
425 SplayConstIterator<V>
426 SplayConstIterator<V>::operator ++ (int dummy)
427 {
428 SplayConstIterator<V> result = *this;
429 advance();
430 return result;
431 }
432
433 /* advance is simple enough:
434 * if the stack is empty, we're done.
435 * otherwise, pop the last visited node
436 * then, pop the next node to visit
437 * if that has a right child, add it and it's
438 * left-to-end path.
439 * then add the node back.
440 */
441 template <class V>
442 void
advance()443 SplayConstIterator<V>::advance()
444 {
445 if (toVisit.empty())
446 return;
447
448 toVisit.pop();
449
450 if (toVisit.empty())
451 return;
452
453 // not empty
454 SplayNode<V> *currentNode = toVisit.top();
455 toVisit.pop();
456
457 addLeftPath(currentNode->right);
458
459 toVisit.push(currentNode);
460 }
461
462 template <class V>
463 void
addLeftPath(SplayNode<V> * aNode)464 SplayConstIterator<V>::addLeftPath(SplayNode<V> *aNode)
465 {
466 if (aNode == NULL)
467 return;
468
469 do {
470 toVisit.push(aNode);
471 aNode = aNode->left;
472 } while (aNode != NULL);
473 }
474
475 template <class V>
476 void
init(SplayNode<V> * head)477 SplayConstIterator<V>::init(SplayNode<V> *head)
478 {
479 addLeftPath(head);
480 }
481
482 template <class V>
483 V const &
484 SplayConstIterator<V>::operator * () const
485 {
486 /* can't dereference when past the end */
487
488 if (toVisit.size() == 0)
489 fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
490
491 return toVisit.top()->data;
492 }
493
494 #endif /* SQUID_SPLAY_H */
495
496