]>
git.ipfire.org Git - thirdparty/squid.git/blob - include/splay.h
2 * Copyright (C) 1996-2017 The Squid Software Foundation and contributors
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.
15 // private class of Splay. Do not use directly
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
;}
26 SplayNode
<V
> (Value
const &);
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;
35 SplayNode
<V
> * remove(const Value data
, SPLAYCMP
* compare
);
37 SplayNode
<V
> * insert(Value data
, SPLAYCMP
* compare
);
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;
43 /// recursively visit left nodes, this node, and then right nodes
44 template <class Visitor
> void visit(Visitor
&v
) const;
47 typedef SplayNode
<void *> splayNode
;
50 class SplayConstIterator
;
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
;
64 Splay():head(NULL
), elements (0) {}
66 template <class FindValue
> Value
const *find (FindValue
const &, int( * compare
)(FindValue
const &a
, Value
const &b
)) const;
68 void insert(Value
const &, SPLAYCMP
*compare
);
70 void remove(Value
const &, SPLAYCMP
*compare
);
72 void destroy(SPLAYFREE
* = SplayNode
<V
>::DefaultFree
);
74 SplayNode
<V
> const * start() const;
76 SplayNode
<V
> const * finish() const;
80 bool empty() const { return size() == 0; }
82 const_iterator
begin() const;
84 const_iterator
end() const;
86 /// recursively visit all nodes, in left-to-right order
87 template <class Visitor
> void visit(Visitor
&v
) const;
90 mutable SplayNode
<V
> * head
;
94 SQUIDCEXTERN
int splayLastResult
;
97 SplayNode
<V
>::SplayNode (Value
const &someData
) : data(someData
), left(NULL
), right (NULL
) {}
101 SplayNode
<V
>::walk(SPLAYWALKEE
* walkee
, void *state
)
104 left
->walk(walkee
, state
);
109 right
->walk(walkee
, state
);
114 SplayNode
<V
>::start() const
117 return left
->start();
124 SplayNode
<V
>::finish() const
127 return right
->finish();
134 SplayNode
<V
>::destroy(SPLAYFREE
* free_func
)
137 left
->destroy(free_func
);
140 right
->destroy(free_func
);
149 SplayNode
<V
>::remove(Value
const dataToRemove
, SPLAYCMP
* compare
)
151 SplayNode
<V
> *result
= splay(dataToRemove
, compare
);
153 if (splayLastResult
== 0) { /* found it */
154 SplayNode
<V
> *newTop
;
156 if (result
->left
== NULL
) {
157 newTop
= result
->right
;
159 newTop
= result
->left
->splay(dataToRemove
, compare
);
161 newTop
->right
= result
->right
;
162 result
->right
= NULL
;
169 return result
; /* It wasn't there */
174 SplayNode
<V
>::insert(Value dataToInsert
, SPLAYCMP
* compare
)
176 /* create node to insert */
177 SplayNode
<V
> *newNode
= new SplayNode
<V
>(dataToInsert
);
178 SplayNode
<V
> *newTop
= splay(dataToInsert
, compare
);
180 if (splayLastResult
< 0) {
181 newNode
->left
= newTop
->left
;
182 newNode
->right
= newTop
;
185 } else if (splayLastResult
> 0) {
186 newNode
->right
= newTop
->right
;
187 newNode
->left
= newTop
;
188 newTop
->right
= NULL
;
191 /* duplicate entry */
198 template<class FindValue
>
200 SplayNode
<V
>::splay(FindValue
const &dataToFind
, int( * compare
)(FindValue
const &a
, Value
const &b
)) const
202 Value temp
= Value();
203 SplayNode
<V
> N(temp
);
207 N
.left
= N
.right
= NULL
;
210 SplayNode
<V
> *top
= const_cast<SplayNode
<V
> *>(this);
213 splayLastResult
= compare(dataToFind
, top
->data
);
215 if (splayLastResult
< 0) {
216 if (top
->left
== NULL
)
219 if ((splayLastResult
= compare(dataToFind
, top
->left
->data
)) < 0) {
220 y
= top
->left
; /* rotate right */
221 top
->left
= y
->right
;
225 if (top
->left
== NULL
)
229 r
->left
= top
; /* link right */
232 } else if (splayLastResult
> 0) {
233 if (top
->right
== NULL
)
236 if ((splayLastResult
= compare(dataToFind
, top
->right
->data
)) > 0) {
237 y
= top
->right
; /* rotate left */
238 top
->right
= y
->left
;
242 if (top
->right
== NULL
)
246 l
->right
= top
; /* link left */
254 l
->right
= top
->left
; /* assemble */
255 r
->left
= top
->right
;
262 template <class Visitor
>
264 SplayNode
<V
>::visit(Visitor
&visitor
) const
267 left
->visit(visitor
);
270 right
->visit(visitor
);
274 template <class Visitor
>
276 Splay
<V
>::visit(Visitor
&visitor
) const
279 head
->visit(visitor
);
283 template <class FindValue
>
284 typename Splay
<V
>::Value
const *
285 Splay
<V
>::find (FindValue
const &value
, int( * compare
)(FindValue
const &a
, Value
const &b
)) const
290 head
= head
->splay(value
, compare
);
292 if (splayLastResult
!= 0)
300 Splay
<V
>::insert(Value
const &value
, SPLAYCMP
*compare
)
302 if (find(value
, compare
) != NULL
) // ignore duplicates
306 head
= new SplayNode
<V
>(value
);
308 head
= head
->insert(value
, compare
);
314 Splay
<V
>::remove(Value
const &value
, SPLAYCMP
*compare
)
316 // also catches the head==NULL case
317 if (find(value
, compare
) == NULL
)
320 head
= head
->remove(value
, compare
);
327 Splay
<V
>:: start() const
330 return head
->start();
337 Splay
<V
>:: finish() const
340 return head
->finish();
347 Splay
<V
>:: destroy(SPLAYFREE
*free_func
)
350 head
->destroy(free_func
);
359 Splay
<V
>::size() const
365 const SplayConstIterator
<V
>
366 Splay
<V
>::begin() const
368 return const_iterator(head
);
372 const SplayConstIterator
<V
>
373 Splay
<V
>::end() const
375 return const_iterator(NULL
);
378 // XXX: This does not seem to iterate the whole thing in some cases.
380 class SplayConstIterator
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;
393 void addLeftPath(SplayNode
<V
> *aNode
);
394 void init(SplayNode
<V
> *);
395 std::stack
<SplayNode
<V
> *> toVisit
;
399 SplayConstIterator
<V
>::SplayConstIterator (SplayNode
<V
> *aNode
)
406 SplayConstIterator
<V
>::operator == (SplayConstIterator
const &right
) const
408 if (toVisit
.empty() && right
.toVisit
.empty())
410 if (!toVisit
.empty() && !right
.toVisit
.empty())
411 return toVisit
.top() == right
.toVisit
.top();
412 // only one of the two is empty
417 SplayConstIterator
<V
> &
418 SplayConstIterator
<V
>::operator ++ ()
425 SplayConstIterator
<V
>
426 SplayConstIterator
<V
>::operator ++ (int dummy
)
428 SplayConstIterator
<V
> result
= *this;
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
439 * then add the node back.
443 SplayConstIterator
<V
>::advance()
454 SplayNode
<V
> *currentNode
= toVisit
.top();
457 addLeftPath(currentNode
->right
);
459 toVisit
.push(currentNode
);
464 SplayConstIterator
<V
>::addLeftPath(SplayNode
<V
> *aNode
)
472 } while (aNode
!= NULL
);
477 SplayConstIterator
<V
>::init(SplayNode
<V
> *head
)
484 SplayConstIterator
<V
>::operator * () const
486 /* can't dereference when past the end */
488 if (toVisit
.size() == 0)
489 fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
491 return toVisit
.top()->data
;
494 #endif /* SQUID_SPLAY_H */