splay.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 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 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
38
41 template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
42
44 template <class Visitor> void visit(Visitor &v) const;
45};
46
48
49template <class V>
51
52template <class V>
54
55template <class V>
56class Splay
57{
58public:
59 typedef V Value;
60 typedef int SPLAYCMP(Value const &a, Value const &b);
61 typedef void SPLAYFREE(Value &);
64 Splay():head(nullptr), 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
73
74 SplayNode<V> const * start() const;
75
76 SplayNode<V> const * finish() const;
77
78 size_t size() const;
79
80 bool empty() const { return size() == 0; }
81
83
85
87 template <class Visitor> void visit(Visitor &v) const;
88
89private:
90 mutable SplayNode<V> * head;
91 size_t elements;
92};
93
95
96template<class V>
97SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(nullptr), right (nullptr) {}
98
99template<class V>
100void
101SplayNode<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
112template<class V>
113SplayNode<V> const *
115{
116 if (left)
117 return left->start();
118
119 return this;
120}
121
122template<class V>
123SplayNode<V> const *
125{
126 if (right)
127 return right->finish();
128
129 return this;
130}
131
132template<class V>
133void
134SplayNode<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
147template<class V>
149SplayNode<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 == nullptr) {
157 newTop = result->right;
158 } else {
159 newTop = result->left->splay(dataToRemove, compare);
160 /* temporary */
161 newTop->right = result->right;
162 result->right = nullptr;
163 }
164
165 delete result;
166 return newTop;
167 }
168
169 return result; /* It wasn't there */
170}
171
172template<class V>
174SplayNode<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 = nullptr;
184 return newNode;
185 } else if (splayLastResult > 0) {
186 newNode->right = newTop->right;
187 newNode->left = newTop;
188 newTop->right = nullptr;
189 return newNode;
190 } else {
191 /* duplicate entry */
192 delete newNode;
193 return newTop;
194 }
195}
196
197template<class V>
198template<class FindValue>
200SplayNode<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 = nullptr;
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 == nullptr)
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 == nullptr)
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 == nullptr)
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 == nullptr)
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
261template <class V>
262template <class Visitor>
263void
264SplayNode<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
273template <class V>
274template <class Visitor>
275void
276Splay<V>::visit(Visitor &visitor) const
277{
278 if (head)
279 head->visit(visitor);
280}
281
282template <class V>
283template <class FindValue>
284typename Splay<V>::Value const *
285Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
286{
287 if (head == nullptr)
288 return nullptr;
289
290 head = head->splay(value, compare);
291
292 if (splayLastResult != 0)
293 return nullptr;
294
295 return &head->data;
296}
297
298template <class V>
299void
300Splay<V>::insert(Value const &value, SPLAYCMP *compare)
301{
302 if (find(value, compare) != nullptr) // ignore duplicates
303 return;
304
305 if (head == nullptr)
306 head = new SplayNode<V>(value);
307 else
308 head = head->insert(value, compare);
309 ++elements;
310}
311
312template <class V>
313void
314Splay<V>::remove(Value const &value, SPLAYCMP *compare)
315{
316 // also catches the head==NULL case
317 if (find(value, compare) == nullptr)
318 return;
319
320 head = head->remove(value, compare);
321
322 --elements;
323}
324
325template <class V>
326SplayNode<V> const *
328{
329 if (head)
330 return head->start();
331
332 return nullptr;
333}
334
335template <class V>
336SplayNode<V> const *
338{
339 if (head)
340 return head->finish();
341
342 return nullptr;
343}
344
345template <class V>
346void
347Splay<V>:: destroy(SPLAYFREE *free_func)
348{
349 if (head)
350 head->destroy(free_func);
351
352 head = nullptr;
353
354 elements = 0;
355}
356
357template <class V>
358size_t
360{
361 return elements;
362}
363
364template <class V>
367{
368 return const_iterator(head);
369}
370
371template <class V>
374{
375 return const_iterator(nullptr);
376}
377
378// XXX: This does not seem to iterate the whole thing in some cases.
379template <class V>
381{
382
383public:
384 typedef const V value_type;
386 bool operator == (SplayConstIterator const &right) const;
389 V const & operator * () const;
390
391private:
392 void advance();
393 void addLeftPath(SplayNode<V> *aNode);
394 void init(SplayNode<V> *);
395 std::stack<SplayNode<V> *> toVisit;
396};
397
398template <class V>
400{
401 init(aNode);
402}
403
404template <class V>
405bool
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
416template <class V>
419{
420 advance();
421 return *this;
422}
423
424template <class V>
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*/
441template <class V>
442void
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
462template <class V>
463void
465{
466 if (aNode == nullptr)
467 return;
468
469 do {
470 toVisit.push(aNode);
471 aNode = aNode->left;
472 } while (aNode != nullptr);
473}
474
475template <class V>
476void
478{
479 addLeftPath(head);
480}
481
482template <class V>
483V 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
squidaio_request_t * head
Definition: aiops.cc:126
SplayConstIterator(SplayNode< V > *aNode)
Definition: splay.h:399
V const & operator*() const
Definition: splay.h:484
void advance()
Definition: splay.h:443
std::stack< SplayNode< V > * > toVisit
Definition: splay.h:395
const V value_type
Definition: splay.h:384
SplayConstIterator & operator++()
Definition: splay.h:418
void addLeftPath(SplayNode< V > *aNode)
Definition: splay.h:464
bool operator==(SplayConstIterator const &right) const
Definition: splay.h:406
void init(SplayNode< V > *)
Definition: splay.h:477
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:200
void visit(Visitor &v) const
recursively visit left nodes, this node, and then right nodes
Definition: splay.h:264
static void DefaultFree(Value &aValue)
Definition: splay.h:24
SplayNode< V > * insert(Value data, SPLAYCMP *compare)
Definition: splay.h:174
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:149
int SPLAYCMP(Value const &a, Value const &b)
Definition: splay.h:21
SplayNode< V > const * finish() const
Definition: splay.h:124
void walk(SPLAYWALKEE *, void *callerState)
Definition: splay.h:101
V Value
Definition: splay.h:20
SplayNode(Value const &)
Definition: splay.h:97
SplayNode< V > const * start() const
Definition: splay.h:114
void destroy(SPLAYFREE *=DefaultFree)
Definition: splay.h:134
Definition: splay.h:57
const_iterator begin() const
Definition: splay.h:366
SplayNode< V > * head
Definition: splay.h:90
size_t elements
Definition: splay.h:91
const SplayConstIterator< V > const_iterator
Definition: splay.h:63
void visit(Visitor &v) const
recursively visit all nodes, in left-to-right order
Definition: splay.h:276
SplayIterator< V > iterator
Definition: splay.h:62
Value const * find(FindValue const &, int(*compare)(FindValue const &a, Value const &b)) const
const_iterator end() const
Definition: splay.h:373
void remove(Value const &, SPLAYCMP *compare)
Definition: splay.h:314
bool empty() const
Definition: splay.h:80
SplayNode< V > const * start() const
Definition: splay.h:327
void insert(Value const &, SPLAYCMP *compare)
Definition: splay.h:300
SplayNode< V > const * finish() const
Definition: splay.h:337
size_t size() const
Definition: splay.h:359
int SPLAYCMP(Value const &a, Value const &b)
Definition: splay.h:60
void destroy(SPLAYFREE *=SplayNode< V >::DefaultFree)
Definition: splay.h:347
void SPLAYFREE(Value &)
Definition: splay.h:61
Splay()
Definition: splay.h:64
V Value
Definition: splay.h:59
void fatal(const char *message)
Definition: fatal.cc:28
SplayNode< void * > splayNode
Definition: splay.h:47
SQUIDCEXTERN int splayLastResult
Definition: splay.h:94
#define SQUIDCEXTERN
Definition: squid.h:21
Comm::AcceptLimiter dummy
Definition: stub_libcomm.cc:16

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors