splay.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2023 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
16template <class V>
18{
19public:
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);
24 static void DefaultFree (Value &aValue) {delete aValue;}
25
26 SplayNode<V> (Value const &);
31 SplayNode<V> const * start() const;
32 SplayNode<V> const * finish() const;
33
34 SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
35
37
40 template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
41
43 template <class Visitor> void visit(Visitor &v) const;
44};
45
47
48template <class V>
50
51template <class V>
53
54template <class V>
55class Splay
56{
57public:
58 typedef V Value;
59 typedef int SPLAYCMP(Value const &a, Value const &b);
60 typedef void SPLAYFREE(Value &);
63 Splay():head(nullptr), elements (0) {}
64
65 template <class FindValue> Value const *find (FindValue const &, int( * compare)(FindValue const &a, Value const &b)) const;
66
67 void insert(Value const &, SPLAYCMP *compare);
68
69 void remove(Value const &, SPLAYCMP *compare);
70
72
73 SplayNode<V> const * start() const;
74
75 SplayNode<V> const * finish() const;
76
77 size_t size() const;
78
79 bool empty() const { return size() == 0; }
80
82
84
86 template <class Visitor> void visit(Visitor &v) const;
87
88private:
89 mutable SplayNode<V> * head;
90 size_t elements;
91};
92
94
95template<class V>
96SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(nullptr), right (nullptr) {}
97
98template<class V>
99SplayNode<V> const *
101{
102 if (left)
103 return left->start();
104
105 return this;
106}
107
108template<class V>
109SplayNode<V> const *
111{
112 if (right)
113 return right->finish();
114
115 return this;
116}
117
118template<class V>
119void
120SplayNode<V>::destroy(SPLAYFREE * free_func)
121{
122 if (left)
123 left->destroy(free_func);
124
125 if (right)
126 right->destroy(free_func);
127
128 free_func(data);
129
130 delete this;
131}
132
133template<class V>
135SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare)
136{
137 SplayNode<V> *result = splay(dataToRemove, compare);
138
139 if (splayLastResult == 0) { /* found it */
140 SplayNode<V> *newTop;
141
142 if (result->left == nullptr) {
143 newTop = result->right;
144 } else {
145 newTop = result->left->splay(dataToRemove, compare);
146 /* temporary */
147 newTop->right = result->right;
148 result->right = nullptr;
149 }
150
151 delete result;
152 return newTop;
153 }
154
155 return result; /* It wasn't there */
156}
157
158template<class V>
160SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
161{
162 /* create node to insert */
163 SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
164 SplayNode<V> *newTop = splay(dataToInsert, compare);
165
166 if (splayLastResult < 0) {
167 newNode->left = newTop->left;
168 newNode->right = newTop;
169 newTop->left = nullptr;
170 return newNode;
171 } else if (splayLastResult > 0) {
172 newNode->right = newTop->right;
173 newNode->left = newTop;
174 newTop->right = nullptr;
175 return newNode;
176 } else {
177 /* duplicate entry */
178 delete newNode;
179 return newTop;
180 }
181}
182
183template<class V>
184template<class FindValue>
186SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
187{
188 Value temp = Value();
189 SplayNode<V> N(temp);
190 SplayNode<V> *l;
191 SplayNode<V> *r;
192 SplayNode<V> *y;
193 N.left = N.right = nullptr;
194 l = r = &N;
195
196 SplayNode<V> *top = const_cast<SplayNode<V> *>(this);
197
198 for (;;) {
199 splayLastResult = compare(dataToFind, top->data);
200
201 if (splayLastResult < 0) {
202 if (top->left == nullptr)
203 break;
204
205 if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
206 y = top->left; /* rotate right */
207 top->left = y->right;
208 y->right = top;
209 top = y;
210
211 if (top->left == nullptr)
212 break;
213 }
214
215 r->left = top; /* link right */
216 r = top;
217 top = top->left;
218 } else if (splayLastResult > 0) {
219 if (top->right == nullptr)
220 break;
221
222 if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
223 y = top->right; /* rotate left */
224 top->right = y->left;
225 y->left = top;
226 top = y;
227
228 if (top->right == nullptr)
229 break;
230 }
231
232 l->right = top; /* link left */
233 l = top;
234 top = top->right;
235 } else {
236 break;
237 }
238 }
239
240 l->right = top->left; /* assemble */
241 r->left = top->right;
242 top->left = N.right;
243 top->right = N.left;
244 return top;
245}
246
247template <class V>
248template <class Visitor>
249void
250SplayNode<V>::visit(Visitor &visitor) const
251{
252 if (left)
253 left->visit(visitor);
254 visitor(data);
255 if (right)
256 right->visit(visitor);
257}
258
259template <class V>
260template <class Visitor>
261void
262Splay<V>::visit(Visitor &visitor) const
263{
264 if (head)
265 head->visit(visitor);
266}
267
268template <class V>
269template <class FindValue>
270typename Splay<V>::Value const *
271Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
272{
273 if (head == nullptr)
274 return nullptr;
275
276 head = head->splay(value, compare);
277
278 if (splayLastResult != 0)
279 return nullptr;
280
281 return &head->data;
282}
283
284template <class V>
285void
286Splay<V>::insert(Value const &value, SPLAYCMP *compare)
287{
288 if (find(value, compare) != nullptr) // ignore duplicates
289 return;
290
291 if (head == nullptr)
292 head = new SplayNode<V>(value);
293 else
294 head = head->insert(value, compare);
295 ++elements;
296}
297
298template <class V>
299void
300Splay<V>::remove(Value const &value, SPLAYCMP *compare)
301{
302 // also catches the head==NULL case
303 if (find(value, compare) == nullptr)
304 return;
305
306 head = head->remove(value, compare);
307
308 --elements;
309}
310
311template <class V>
312SplayNode<V> const *
314{
315 if (head)
316 return head->start();
317
318 return nullptr;
319}
320
321template <class V>
322SplayNode<V> const *
324{
325 if (head)
326 return head->finish();
327
328 return nullptr;
329}
330
331template <class V>
332void
333Splay<V>:: destroy(SPLAYFREE *free_func)
334{
335 if (head)
336 head->destroy(free_func);
337
338 head = nullptr;
339
340 elements = 0;
341}
342
343template <class V>
344size_t
346{
347 return elements;
348}
349
350template <class V>
353{
354 return const_iterator(head);
355}
356
357template <class V>
360{
361 return const_iterator(nullptr);
362}
363
364// XXX: This does not seem to iterate the whole thing in some cases.
365template <class V>
367{
368
369public:
370 typedef const V value_type;
372 bool operator == (SplayConstIterator const &right) const;
375 V const & operator * () const;
376
377private:
378 void advance();
379 void addLeftPath(SplayNode<V> *aNode);
380 void init(SplayNode<V> *);
381 std::stack<SplayNode<V> *> toVisit;
382};
383
384template <class V>
386{
387 init(aNode);
388}
389
390template <class V>
391bool
393{
394 if (toVisit.empty() && right.toVisit.empty())
395 return true;
396 if (!toVisit.empty() && !right.toVisit.empty())
397 return toVisit.top() == right.toVisit.top();
398 // only one of the two is empty
399 return false;
400}
401
402template <class V>
405{
406 advance();
407 return *this;
408}
409
410template <class V>
413{
414 SplayConstIterator<V> result = *this;
415 advance();
416 return result;
417}
418
419/* advance is simple enough:
420* if the stack is empty, we're done.
421* otherwise, pop the last visited node
422* then, pop the next node to visit
423* if that has a right child, add it and it's
424* left-to-end path.
425* then add the node back.
426*/
427template <class V>
428void
430{
431 if (toVisit.empty())
432 return;
433
434 toVisit.pop();
435
436 if (toVisit.empty())
437 return;
438
439 // not empty
440 SplayNode<V> *currentNode = toVisit.top();
441 toVisit.pop();
442
443 addLeftPath(currentNode->right);
444
445 toVisit.push(currentNode);
446}
447
448template <class V>
449void
451{
452 if (aNode == nullptr)
453 return;
454
455 do {
456 toVisit.push(aNode);
457 aNode = aNode->left;
458 } while (aNode != nullptr);
459}
460
461template <class V>
462void
464{
465 addLeftPath(head);
466}
467
468template <class V>
469V const &
471{
472 /* can't dereference when past the end */
473
474 if (toVisit.size() == 0)
475 fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
476
477 return toVisit.top()->data;
478}
479
480#endif /* SQUID_SPLAY_H */
481
squidaio_request_t * head
Definition: aiops.cc:127
SplayConstIterator(SplayNode< V > *aNode)
Definition: splay.h:385
V const & operator*() const
Definition: splay.h:470
void advance()
Definition: splay.h:429
std::stack< SplayNode< V > * > toVisit
Definition: splay.h:381
const V value_type
Definition: splay.h:370
SplayConstIterator & operator++()
Definition: splay.h:404
void addLeftPath(SplayNode< V > *aNode)
Definition: splay.h:450
bool operator==(SplayConstIterator const &right) const
Definition: splay.h:392
void init(SplayNode< V > *)
Definition: splay.h:463
Value data
Definition: splay.h:27
SplayNode< V > * right
Definition: splay.h:29
void SPLAYWALKEE(Value const &nodedata, void *state)
Definition: splay.h:23
SplayNode< V > * splay(const FindValue &data, int(*compare)(FindValue const &a, Value const &b)) const
Definition: splay.h:186
void visit(Visitor &v) const
recursively visit left nodes, this node, and then right nodes
Definition: splay.h:250
static void DefaultFree(Value &aValue)
Definition: splay.h:24
SplayNode< V > * insert(Value data, SPLAYCMP *compare)
Definition: splay.h:160
SplayNode< V > * left
Definition: splay.h:28
void SPLAYFREE(Value &)
Definition: splay.h:22
SplayNode< V > * remove(const Value data, SPLAYCMP *compare)
Definition: splay.h:135
int SPLAYCMP(Value const &a, Value const &b)
Definition: splay.h:21
SplayNode< V > const * finish() const
Definition: splay.h:110
V Value
Definition: splay.h:20
SplayNode(Value const &)
Definition: splay.h:96
SplayNode< V > const * start() const
Definition: splay.h:100
void destroy(SPLAYFREE *=DefaultFree)
Definition: splay.h:120
Definition: splay.h:56
const_iterator begin() const
Definition: splay.h:352
SplayNode< V > * head
Definition: splay.h:89
size_t elements
Definition: splay.h:90
const SplayConstIterator< V > const_iterator
Definition: splay.h:62
void visit(Visitor &v) const
recursively visit all nodes, in left-to-right order
Definition: splay.h:262
SplayIterator< V > iterator
Definition: splay.h:61
Value const * find(FindValue const &, int(*compare)(FindValue const &a, Value const &b)) const
const_iterator end() const
Definition: splay.h:359
void remove(Value const &, SPLAYCMP *compare)
Definition: splay.h:300
bool empty() const
Definition: splay.h:79
SplayNode< V > const * start() const
Definition: splay.h:313
void insert(Value const &, SPLAYCMP *compare)
Definition: splay.h:286
SplayNode< V > const * finish() const
Definition: splay.h:323
size_t size() const
Definition: splay.h:345
int SPLAYCMP(Value const &a, Value const &b)
Definition: splay.h:59
void destroy(SPLAYFREE *=SplayNode< V >::DefaultFree)
Definition: splay.h:333
void SPLAYFREE(Value &)
Definition: splay.h:60
Splay()
Definition: splay.h:63
V Value
Definition: splay.h:58
void fatal(const char *message)
Definition: fatal.cc:28
SplayNode< void * > splayNode
Definition: splay.h:46
SQUIDCEXTERN int splayLastResult
Definition: splay.h:93
#define SQUIDCEXTERN
Definition: squid.h:21
Comm::AcceptLimiter dummy
Definition: stub_libcomm.cc:16

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors