/*
- * $Id$
+ * Copyright (C) 1996-2014 The Squid Software Foundation and contributors
+ *
+ * Squid software is distributed under GPLv2+ license and includes
+ * contributions from numerous individuals and organizations.
+ * Please see the COPYING and CONTRIBUTORS files for details.
*/
#ifndef SQUID_SPLAY_H
#define SQUID_SPLAY_H
-#ifndef __cplusplus
-#else
-
-#include "Stack.h"
+#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);
Value data;
mutable SplayNode<V> *left;
mutable SplayNode<V> *right;
- void destroy(SPLAYFREE *);
+ void destroy(SPLAYFREE * = DefaultFree);
void walk(SPLAYWALKEE *, void *callerState);
- bool empty() const { return this == NULL; }
SplayNode<V> const * start() const;
SplayNode<V> const * finish() const;
SplayNode<V> * insert(Value data, SPLAYCMP * compare);
+ /// look in the splay for data for where compare(data,candidate) == true.
+ /// return NULL if not found, a pointer to the sought data if found.
template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
+
+ /// recursively visit left nodes, this node, and then right nodes
+ template <class Visitor> void visit(Visitor &v) const;
};
typedef SplayNode<void *> splayNode;
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);
void remove(Value const &, SPLAYCMP *compare);
- void destroy(SPLAYFREE *);
+ void destroy(SPLAYFREE * = SplayNode<V>::DefaultFree);
SplayNode<V> const * start() const;
size_t size() const;
+ bool empty() const { return size() == 0; }
+
const_iterator begin() const;
const_iterator end() const;
+ /// 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;
};
-
SQUIDCEXTERN int splayLastResult;
-SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, splayNode::SPLAYCMP *);
-
-SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, splayNode::SPLAYCMP *);
-
-SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, splayNode::SPLAYCMP *);
-
-SQUIDCEXTERN void splay_destroy(splayNode *, splayNode::SPLAYFREE *);
-
-SQUIDCEXTERN void splay_walk(splayNode *, splayNode::SPLAYWALKEE *, void *callerState);
-
-/* inline methods */
template<class V>
SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(NULL), right (NULL) {}
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 */
+ if (splayLastResult == 0) { /* found it */
SplayNode<V> *newTop;
if (result->left == NULL) {
return newTop;
}
- return result; /* It wasn't there */
+ return result; /* It wasn't there */
}
template<class V>
{
/* 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;
break;
if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
- y = top->left; /* rotate right */
+ y = top->left; /* rotate right */
top->left = y->right;
y->right = top;
top = y;
break;
}
- r->left = top; /* link right */
+ r->left = top; /* link right */
r = top;
top = top->left;
} else if (splayLastResult > 0) {
break;
if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
- y = top->right; /* rotate left */
+ y = top->right; /* rotate left */
top->right = y->left;
y->left = top;
top = y;
break;
}
- l->right = top; /* link left */
+ l->right = top; /* link left */
l = top;
top = top->right;
} else {
}
}
- l->right = top->left; /* assemble */
+ l->right = top->left; /* assemble */
r->left = top->right;
top->left = N.right;
top->right = N.left;
return top;
}
+template <class V>
+template <class Visitor>
+void
+SplayNode<V>::visit(Visitor &visitor) const
+{
+ if (left)
+ left->visit(visitor);
+ visitor(data);
+ if (right)
+ right->visit(visitor);
+}
+
+template <class V>
+template <class Visitor>
+void
+Splay<V>::visit(Visitor &visitor) const
+{
+ if (head)
+ head->visit(visitor);
+}
+
template <class V>
template <class FindValue>
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 const_iterator(NULL);
}
+// XXX: This does not seem to iterate the whole thing in some cases.
template <class V>
class SplayConstIterator
{
void advance();
void addLeftPath(SplayNode<V> *aNode);
void init(SplayNode<V> *);
- Stack<SplayNode<V> *> toVisit;
+ std::stack<SplayNode<V> *> toVisit;
};
template <class V>
bool
SplayConstIterator<V>::operator == (SplayConstIterator const &right) const
{
- return toVisit.top() == right.toVisit.top();
+ if (toVisit.empty() && right.toVisit.empty())
+ return true;
+ if (!toVisit.empty() && !right.toVisit.empty())
+ return toVisit.top() == right.toVisit.top();
+ // only one of the two is empty
+ return false;
}
template <class V>
void
SplayConstIterator<V>::advance()
{
- if (toVisit.size() == 0)
+ if (toVisit.empty())
return;
toVisit.pop();
- if (toVisit.size() == 0)
+ if (toVisit.empty())
return;
- SplayNode<V> *currentNode = toVisit.pop();
+ // not empty
+ SplayNode<V> *currentNode = toVisit.top();
+ toVisit.pop();
addLeftPath(currentNode->right);
- toVisit.push_back(currentNode);
+ toVisit.push(currentNode);
}
template <class V>
return;
do {
- toVisit.push_back(aNode);
+ toVisit.push(aNode);
aNode = aNode->left;
} while (aNode != NULL);
}
return toVisit.top()->data;
}
-#endif /* cplusplus */
-
#endif /* SQUID_SPLAY_H */
+
projects / thirdparty / squid.git / blobdiff