]>
git.ipfire.org Git - thirdparty/squid.git/blob - include/splay.h
20 typedef int SPLAYCMP(Value
const &a
, Value
const &b
);
21 typedef void SPLAYFREE(Value
&);
22 typedef void SPLAYWALKEE(Value
const & nodedata
, void *state
);
23 static void DefaultFree (Value
&aValue
) {delete aValue
;}
25 SplayNode
<V
> (Value
const &);
27 mutable SplayNode
<V
> *left
;
28 mutable SplayNode
<V
> *right
;
29 void destroy(SPLAYFREE
*);
30 void walk(SPLAYWALKEE
*, void *callerState
);
31 bool empty() const { return this == NULL
; }
32 SplayNode
<V
> const * start() const;
33 SplayNode
<V
> const * finish() const;
36 (const Value data
, SPLAYCMP
* compare
);
38 SplayNode
<V
> * insert(Value data
, SPLAYCMP
* compare
);
40 template <class FindValue
> SplayNode
<V
> * splay(const FindValue
&data
, int( * compare
)(FindValue
const &a
, Value
const &b
)) const;
43 typedef SplayNode
<void *> splayNode
;
47 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 mutable SplayNode
<V
> * head
;
67 template <class FindValue
> Value
const *find (FindValue
const &, int( * compare
)(FindValue
const &a
, Value
const &b
)) const;
68 void insert(Value
const &, SPLAYCMP
*compare
);
71 (Value
const &, SPLAYCMP
*compare
);
73 void destroy(SPLAYFREE
*);
75 SplayNode
<V
> const * start() const;
77 SplayNode
<V
> const * finish() const;
81 const_iterator
begin() const;
83 const_iterator
end() const;
89 SQUIDCEXTERN
int splayLastResult
;
91 SQUIDCEXTERN splayNode
*splay_insert(void *, splayNode
*, splayNode::SPLAYCMP
*);
93 SQUIDCEXTERN splayNode
*splay_delete(const void *, splayNode
*, splayNode::SPLAYCMP
*);
95 SQUIDCEXTERN splayNode
*splay_splay(const void **, splayNode
*, splayNode::SPLAYCMP
*);
97 SQUIDCEXTERN
void splay_destroy(splayNode
*, splayNode::SPLAYFREE
*);
99 SQUIDCEXTERN
void splay_walk(splayNode
*, splayNode::SPLAYWALKEE
*, void *callerState
);
103 SplayNode
<V
>::SplayNode (Value
const &someData
) : data(someData
), left(NULL
), right (NULL
) {}
107 SplayNode
<V
>::walk(SPLAYWALKEE
* walkee
, void *state
)
113 left
->walk(walkee
, state
);
118 right
->walk(walkee
, state
);
123 SplayNode
<V
>::start() const
126 return left
->start();
133 SplayNode
<V
>::finish() const
136 return right
->finish();
143 SplayNode
<V
>::destroy(SPLAYFREE
* free_func
)
149 left
->destroy(free_func
);
152 right
->destroy(free_func
);
162 (Value
const dataToRemove
, SPLAYCMP
* compare
)
167 SplayNode
<V
> *result
= splay(dataToRemove
, compare
);
169 if (splayLastResult
== 0) { /* found it */
170 SplayNode
<V
> *newTop
;
172 if (result
->left
== NULL
) {
173 newTop
= result
->right
;
175 newTop
= result
->left
->splay(dataToRemove
, compare
);
177 newTop
->right
= result
->right
;
178 result
->right
= NULL
;
185 return result
; /* It wasn't there */
190 SplayNode
<V
>::insert(Value dataToInsert
, SPLAYCMP
* compare
)
192 /* create node to insert */
193 SplayNode
<V
> *newNode
= new SplayNode
<V
>(dataToInsert
);
196 splayLastResult
= -1;
197 newNode
->left
= newNode
->right
= NULL
;
201 SplayNode
<V
> *newTop
= splay(dataToInsert
, compare
);
203 if (splayLastResult
< 0) {
204 newNode
->left
= newTop
->left
;
205 newNode
->right
= newTop
;
208 } else if (splayLastResult
> 0) {
209 newNode
->right
= newTop
->right
;
210 newNode
->left
= newTop
;
211 newTop
->right
= NULL
;
214 /* duplicate entry */
221 template<class FindValue
>
223 SplayNode
<V
>::splay(FindValue
const &dataToFind
, int( * compare
)(FindValue
const &a
, Value
const &b
)) const
226 /* can't have compared successfully :} */
227 splayLastResult
= -1;
231 Value temp
= Value();
232 SplayNode
<V
> N(temp
);
236 N
.left
= N
.right
= NULL
;
239 SplayNode
<V
> *top
= const_cast<SplayNode
<V
> *>(this);
242 splayLastResult
= compare(dataToFind
, top
->data
);
244 if (splayLastResult
< 0) {
245 if (top
->left
== NULL
)
248 if ((splayLastResult
= compare(dataToFind
, top
->left
->data
)) < 0) {
249 y
= top
->left
; /* rotate right */
250 top
->left
= y
->right
;
254 if (top
->left
== NULL
)
258 r
->left
= top
; /* link right */
261 } else if (splayLastResult
> 0) {
262 if (top
->right
== NULL
)
265 if ((splayLastResult
= compare(dataToFind
, top
->right
->data
)) > 0) {
266 y
= top
->right
; /* rotate left */
267 top
->right
= y
->left
;
271 if (top
->right
== NULL
)
275 l
->right
= top
; /* link left */
283 l
->right
= top
->left
; /* assemble */
284 r
->left
= top
->right
;
291 template <class FindValue
>
292 typename Splay
<V
>::Value
const *
293 Splay
<V
>::find (FindValue
const &value
, int( * compare
)(FindValue
const &a
, Value
const &b
)) const
295 head
= head
->splay(value
, compare
);
297 if (splayLastResult
!= 0)
305 Splay
<V
>::insert(Value
const &value
, SPLAYCMP
*compare
)
307 assert (!find (value
, compare
));
308 head
= head
->insert(value
, compare
);
315 (Value
const &value
, SPLAYCMP
*compare
)
317 assert (find (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
);
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 Stack
<SplayNode
<V
> *> toVisit
;
399 SplayConstIterator
<V
>::SplayConstIterator (SplayNode
<V
> *aNode
)
406 SplayConstIterator
<V
>::operator == (SplayConstIterator
const &right
) const
408 return toVisit
.top() == right
.toVisit
.top();
412 SplayConstIterator
<V
> &
413 SplayConstIterator
<V
>::operator ++ ()
420 SplayConstIterator
<V
>
421 SplayConstIterator
<V
>::operator ++ (int dummy
)
423 SplayConstIterator
<V
> result
= *this;
428 /* advance is simple enough:
429 * if the stack is empty, we're done.
430 * otherwise, pop the last visited node
431 * then, pop the next node to visit
432 * if that has a right child, add it and it's
434 * then add the node back.
438 SplayConstIterator
<V
>::advance()
440 if (toVisit
.size() == 0)
445 if (toVisit
.size() == 0)
448 SplayNode
<V
> *currentNode
= toVisit
.pop();
450 addLeftPath(currentNode
->right
);
452 toVisit
.push_back(currentNode
);
457 SplayConstIterator
<V
>::addLeftPath(SplayNode
<V
> *aNode
)
463 toVisit
.push_back(aNode
);
465 } while (aNode
!= NULL
);
470 SplayConstIterator
<V
>::init(SplayNode
<V
> *head
)
477 SplayConstIterator
<V
>::operator * () const
479 /* can't dereference when past the end */
481 if (toVisit
.size() == 0)
482 fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
484 return toVisit
.top()->data
;
487 #endif /* cplusplus */
489 #endif /* SQUID_SPLAY_H */