#ifndef SQUID_SPLAY_H
#define SQUID_SPLAY_H
-#if defined(__cplusplus)
-
#include "fatal.h"
-
#include <stack>
-
// private class of Splay. Do not use directly
template <class V>
class SplayNode
{
-
public:
typedef V Value;
typedef int SPLAYCMP(Value const &a, Value const &b);
template <class V>
class Splay
{
-
public:
typedef V Value;
typedef int SPLAYCMP(Value const &a, Value const &b);
typedef const SplayConstIterator<V> const_iterator;
Splay():head(NULL), elements (0) {}
- mutable SplayNode<V> * head;
template <class FindValue> Value const *find (FindValue const &, int( * compare)(FindValue const &a, Value const &b)) const;
void insert(Value const &, SPLAYCMP *compare);
/// recursively visit all nodes, in left-to-right order
template <class Visitor> void visit(Visitor &v) const;
+private:
+ mutable SplayNode<V> * head;
size_t elements;
};
void
SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
{
- if (this == NULL)
- return;
-
if (left)
left->walk(walkee, state);
SplayNode<V> const *
SplayNode<V>::start() const
{
- if (this && left)
+ if (left)
return left->start();
return this;
SplayNode<V> const *
SplayNode<V>::finish() const
{
- if (this && right)
+ if (right)
return right->finish();
return this;
void
SplayNode<V>::destroy(SPLAYFREE * free_func)
{
- if (!this)
- return;
-
if (left)
left->destroy(free_func);
SplayNode<V> *
SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare)
{
- if (this == NULL)
- return NULL;
-
SplayNode<V> *result = splay(dataToRemove, compare);
if (splayLastResult == 0) { /* found it */
{
/* create node to insert */
SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
-
- if (this == NULL) {
- splayLastResult = -1;
- newNode->left = newNode->right = NULL;
- return newNode;
- }
-
SplayNode<V> *newTop = splay(dataToInsert, compare);
if (splayLastResult < 0) {
SplayNode<V> *
SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
{
- if (this == NULL) {
- /* can't have compared successfully :} */
- splayLastResult = -1;
- return NULL;
- }
-
Value temp = Value();
SplayNode<V> N(temp);
SplayNode<V> *l;
typename Splay<V>::Value const *
Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
{
+ if (head == NULL)
+ return NULL;
+
head = head->splay(value, compare);
if (splayLastResult != 0)
void
Splay<V>::insert(Value const &value, SPLAYCMP *compare)
{
- assert (!find (value, compare));
- head = head->insert(value, compare);
+ assert (find (value, compare) == NULL);
+ if (head == NULL)
+ head = new SplayNode<V>(value);
+ else
+ head = head->insert(value, compare);
++elements;
}
return toVisit.top()->data;
}
-#endif /* cplusplus */
-
#endif /* SQUID_SPLAY_H */