]>
git.ipfire.org Git - thirdparty/squid.git/blob - include/splay.h
2 * Copyright (C) 1996-2014 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.
12 #if defined(__cplusplus)
19 // private class of Splay. Do not use directly
26 typedef int SPLAYCMP(Value
const &a
, Value
const &b
);
27 typedef void SPLAYFREE(Value
&);
28 typedef void SPLAYWALKEE(Value
const & nodedata
, void *state
);
29 static void DefaultFree (Value
&aValue
) {delete aValue
;}
31 SplayNode
<V
> (Value
const &);
33 mutable SplayNode
<V
> *left
;
34 mutable SplayNode
<V
> *right
;
35 void destroy(SPLAYFREE
* = DefaultFree
);
36 void walk(SPLAYWALKEE
*, void *callerState
);
37 bool empty() const { return this == NULL
; }
38 SplayNode
<V
> const * start() const;
39 SplayNode
<V
> const * finish() const;
41 SplayNode
<V
> * remove(const Value data
, SPLAYCMP
* compare
);
43 SplayNode
<V
> * insert(Value data
, SPLAYCMP
* compare
);
45 /// look in the splay for data for where compare(data,candidate) == true.
46 /// return NULL if not found, a pointer to the sought data if found.
47 template <class FindValue
> SplayNode
<V
> * splay(const FindValue
&data
, int( * compare
)(FindValue
const &a
, Value
const &b
)) const;
49 /// recursively visit left nodes, this node, and then right nodes
50 template <class Visitor
> void visit(Visitor
&v
) const;
53 typedef SplayNode
<void *> splayNode
;
56 class SplayConstIterator
;
67 typedef int SPLAYCMP(Value
const &a
, Value
const &b
);
68 typedef void SPLAYFREE(Value
&);
69 typedef SplayIterator
<V
> iterator
;
70 typedef const SplayConstIterator
<V
> const_iterator
;
71 Splay():head(NULL
), elements (0) {}
73 mutable SplayNode
<V
> * head
;
74 template <class FindValue
> Value
const *find (FindValue
const &, int( * compare
)(FindValue
const &a
, Value
const &b
)) const;
76 void insert(Value
const &, SPLAYCMP
*compare
);
78 void remove(Value
const &, SPLAYCMP
*compare
);
80 void destroy(SPLAYFREE
* = SplayNode
<V
>::DefaultFree
);
82 SplayNode
<V
> const * start() const;
84 SplayNode
<V
> const * finish() const;
88 bool empty() { return size() == 0; }
90 const_iterator
begin() const;
92 const_iterator
end() const;
94 /// recursively visit all nodes, in left-to-right order
95 template <class Visitor
> void visit(Visitor
&v
) const;
100 SQUIDCEXTERN
int splayLastResult
;
102 SQUIDCEXTERN splayNode
*splay_insert(void *, splayNode
*, splayNode::SPLAYCMP
*);
104 SQUIDCEXTERN splayNode
*splay_delete(const void *, splayNode
*, splayNode::SPLAYCMP
*);
106 SQUIDCEXTERN splayNode
*splay_splay(const void **, splayNode
*, splayNode::SPLAYCMP
*);
108 SQUIDCEXTERN
void splay_destroy(splayNode
*, splayNode::SPLAYFREE
*);
110 SQUIDCEXTERN
void splay_walk(splayNode
*, splayNode::SPLAYWALKEE
*, void *callerState
);
114 SplayNode
<V
>::SplayNode (Value
const &someData
) : data(someData
), left(NULL
), right (NULL
) {}
118 SplayNode
<V
>::walk(SPLAYWALKEE
* walkee
, void *state
)
124 left
->walk(walkee
, state
);
129 right
->walk(walkee
, state
);
134 SplayNode
<V
>::start() const
137 return left
->start();
144 SplayNode
<V
>::finish() const
147 return right
->finish();
154 SplayNode
<V
>::destroy(SPLAYFREE
* free_func
)
160 left
->destroy(free_func
);
163 right
->destroy(free_func
);
172 SplayNode
<V
>::remove(Value
const dataToRemove
, SPLAYCMP
* compare
)
177 SplayNode
<V
> *result
= splay(dataToRemove
, compare
);
179 if (splayLastResult
== 0) { /* found it */
180 SplayNode
<V
> *newTop
;
182 if (result
->left
== NULL
) {
183 newTop
= result
->right
;
185 newTop
= result
->left
->splay(dataToRemove
, compare
);
187 newTop
->right
= result
->right
;
188 result
->right
= NULL
;
195 return result
; /* It wasn't there */
200 SplayNode
<V
>::insert(Value dataToInsert
, SPLAYCMP
* compare
)
202 /* create node to insert */
203 SplayNode
<V
> *newNode
= new SplayNode
<V
>(dataToInsert
);
206 splayLastResult
= -1;
207 newNode
->left
= newNode
->right
= NULL
;
211 SplayNode
<V
> *newTop
= splay(dataToInsert
, compare
);
213 if (splayLastResult
< 0) {
214 newNode
->left
= newTop
->left
;
215 newNode
->right
= newTop
;
218 } else if (splayLastResult
> 0) {
219 newNode
->right
= newTop
->right
;
220 newNode
->left
= newTop
;
221 newTop
->right
= NULL
;
224 /* duplicate entry */
231 template<class FindValue
>
233 SplayNode
<V
>::splay(FindValue
const &dataToFind
, int( * compare
)(FindValue
const &a
, Value
const &b
)) const
236 /* can't have compared successfully :} */
237 splayLastResult
= -1;
241 Value temp
= Value();
242 SplayNode
<V
> N(temp
);
246 N
.left
= N
.right
= NULL
;
249 SplayNode
<V
> *top
= const_cast<SplayNode
<V
> *>(this);
252 splayLastResult
= compare(dataToFind
, top
->data
);
254 if (splayLastResult
< 0) {
255 if (top
->left
== NULL
)
258 if ((splayLastResult
= compare(dataToFind
, top
->left
->data
)) < 0) {
259 y
= top
->left
; /* rotate right */
260 top
->left
= y
->right
;
264 if (top
->left
== NULL
)
268 r
->left
= top
; /* link right */
271 } else if (splayLastResult
> 0) {
272 if (top
->right
== NULL
)
275 if ((splayLastResult
= compare(dataToFind
, top
->right
->data
)) > 0) {
276 y
= top
->right
; /* rotate left */
277 top
->right
= y
->left
;
281 if (top
->right
== NULL
)
285 l
->right
= top
; /* link left */
293 l
->right
= top
->left
; /* assemble */
294 r
->left
= top
->right
;
301 template <class Visitor
>
303 SplayNode
<V
>::visit(Visitor
&visitor
) const
306 left
->visit(visitor
);
309 right
->visit(visitor
);
313 template <class Visitor
>
315 Splay
<V
>::visit(Visitor
&visitor
) const
318 head
->visit(visitor
);
322 template <class FindValue
>
323 typename Splay
<V
>::Value
const *
324 Splay
<V
>::find (FindValue
const &value
, int( * compare
)(FindValue
const &a
, Value
const &b
)) const
326 head
= head
->splay(value
, compare
);
328 if (splayLastResult
!= 0)
336 Splay
<V
>::insert(Value
const &value
, SPLAYCMP
*compare
)
338 assert (!find (value
, compare
));
339 head
= head
->insert(value
, compare
);
345 Splay
<V
>::remove(Value
const &value
, SPLAYCMP
*compare
)
347 assert (find (value
, compare
));
349 head
= head
->remove(value
, compare
);
356 Splay
<V
>:: start() const
359 return head
->start();
366 Splay
<V
>:: finish() const
369 return head
->finish();
376 Splay
<V
>:: destroy(SPLAYFREE
*free_func
)
379 head
->destroy(free_func
);
388 Splay
<V
>::size() const
394 const SplayConstIterator
<V
>
395 Splay
<V
>::begin() const
397 return const_iterator(head
);
401 const SplayConstIterator
<V
>
402 Splay
<V
>::end() const
404 return const_iterator(NULL
);
407 // XXX: This does not seem to iterate the whole thing in some cases.
409 class SplayConstIterator
413 typedef const V value_type
;
414 SplayConstIterator (SplayNode
<V
> *aNode
);
415 bool operator == (SplayConstIterator
const &right
) const;
416 SplayConstIterator
operator ++ (int dummy
);
417 SplayConstIterator
&operator ++ ();
418 V
const & operator * () const;
422 void addLeftPath(SplayNode
<V
> *aNode
);
423 void init(SplayNode
<V
> *);
424 std::stack
<SplayNode
<V
> *> toVisit
;
428 SplayConstIterator
<V
>::SplayConstIterator (SplayNode
<V
> *aNode
)
435 SplayConstIterator
<V
>::operator == (SplayConstIterator
const &right
) const
437 if (toVisit
.empty() && right
.toVisit
.empty())
439 if (!toVisit
.empty() && !right
.toVisit
.empty())
440 return toVisit
.top() == right
.toVisit
.top();
441 // only one of the two is empty
446 SplayConstIterator
<V
> &
447 SplayConstIterator
<V
>::operator ++ ()
454 SplayConstIterator
<V
>
455 SplayConstIterator
<V
>::operator ++ (int dummy
)
457 SplayConstIterator
<V
> result
= *this;
462 /* advance is simple enough:
463 * if the stack is empty, we're done.
464 * otherwise, pop the last visited node
465 * then, pop the next node to visit
466 * if that has a right child, add it and it's
468 * then add the node back.
472 SplayConstIterator
<V
>::advance()
483 SplayNode
<V
> *currentNode
= toVisit
.top();
486 addLeftPath(currentNode
->right
);
488 toVisit
.push(currentNode
);
493 SplayConstIterator
<V
>::addLeftPath(SplayNode
<V
> *aNode
)
501 } while (aNode
!= NULL
);
506 SplayConstIterator
<V
>::init(SplayNode
<V
> *head
)
513 SplayConstIterator
<V
>::operator * () const
515 /* can't dereference when past the end */
517 if (toVisit
.size() == 0)
518 fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
520 return toVisit
.top()->data
;
523 #endif /* cplusplus */
525 #endif /* SQUID_SPLAY_H */