[thirdparty/squid.git] / include / splay.h

/*
 * 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

#if defined(__cplusplus)

#include "fatal.h"

#include <stack>

template <class V>
class SplayNode
{

public:
    typedef V Value;
    typedef int SPLAYCMP(Value const &a, Value const &b);
    typedef void SPLAYFREE(Value &);
    typedef void SPLAYWALKEE(Value const & nodedata, void *state);
    static void DefaultFree (Value &aValue) {delete aValue;}

    SplayNode<V> (Value const &);
    Value data;
    mutable SplayNode<V> *left;
    mutable SplayNode<V> *right;
    void destroy(SPLAYFREE *);
    void walk(SPLAYWALKEE *, void *callerState);
    bool empty() const { return this == NULL; }
    SplayNode<V> const * start() const;
    SplayNode<V> const * finish() const;

    SplayNode<V> * remove(const Value data, SPLAYCMP * compare);

    SplayNode<V> * insert(Value data, SPLAYCMP * compare);

    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 SplayConstIterator;

template <class V>
class SplayIterator;

template <class V>
class Splay
{

public:
    typedef V Value;
    typedef int SPLAYCMP(Value const &a, Value const &b);
    typedef void SPLAYFREE(Value &);
    typedef SplayIterator<V> iterator;
    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 *);

    SplayNode<V> const * start() const;

    SplayNode<V> const * finish() const;

    size_t size() const;

    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;

    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) {}

template<class V>
void
SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
{
    if (this == NULL)
        return;

    if (left)
        left->walk(walkee, state);

    walkee(data, state);

    if (right)
        right->walk(walkee, state);
}

template<class V>
SplayNode<V> const *
SplayNode<V>::start() const
{
    if (this && left)
        return left->start();

    return this;
}

template<class V>
SplayNode<V> const *
SplayNode<V>::finish() const
{
    if (this && right)
        return right->finish();

    return this;
}

template<class V>
void
SplayNode<V>::destroy(SPLAYFREE * free_func)
{
    if (!this)
        return;

    if (left)
        left->destroy(free_func);

    if (right)
        right->destroy(free_func);

    free_func(data);

    delete this;
}

template<class V>
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 */
        SplayNode<V> *newTop;

        if (result->left == NULL) {
            newTop = result->right;
        } else {
            newTop = result->left->splay(dataToRemove, compare);
            /* temporary */
            newTop->right = result->right;
            result->right = NULL;
        }

        delete result;
        return newTop;
    }

    return result;			/* It wasn't there */
}

template<class V>
SplayNode<V> *
SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
{
    /* 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) {
        newNode->left = newTop->left;
        newNode->right = newTop;
        newTop->left = NULL;
        return newNode;
    } else if (splayLastResult > 0) {
        newNode->right = newTop->right;
        newNode->left = newTop;
        newTop->right = NULL;
        return newNode;
    } else {
        /* duplicate entry */
        delete newNode;
        return newTop;
    }
}

template<class V>
template<class FindValue>
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;
    SplayNode<V> *r;
    SplayNode<V> *y;
    N.left = N.right = NULL;
    l = r = &N;

    SplayNode<V> *top = const_cast<SplayNode<V> *>(this);

    for (;;) {
        splayLastResult = compare(dataToFind, top->data);

        if (splayLastResult < 0) {
            if (top->left == NULL)
                break;

            if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
                y = top->left;	/* rotate right */
                top->left = y->right;
                y->right = top;
                top = y;

                if (top->left == NULL)
                    break;
            }

            r->left = top;	/* link right */
            r = top;
            top = top->left;
        } else if (splayLastResult > 0) {
            if (top->right == NULL)
                break;

            if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
                y = top->right;	/* rotate left */
                top->right = y->left;
                y->left = top;
                top = y;

                if (top->right == NULL)
                    break;
            }

            l->right = top;	/* link left */
            l = top;
            top = top->right;
        } else {
            break;
        }
    }

    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
{
    head = head->splay(value, compare);

    if (splayLastResult != 0)
        return NULL;

    return &head->data;
}

template <class V>
void
Splay<V>::insert(Value const &value, SPLAYCMP *compare)
{
    assert (!find (value, compare));
    head = head->insert(value, compare);
    ++elements;
}

template <class V>
void
Splay<V>::remove(Value const &value, SPLAYCMP *compare)
{
    assert (find (value, compare));

    head = head->remove(value, compare);

    --elements;
}

template <class V>
SplayNode<V> const *
Splay<V>:: start() const
{
    if (head)
        return head->start();

    return NULL;
}

template <class V>
SplayNode<V> const *
Splay<V>:: finish() const
{
    if (head)
        return head->finish();

    return NULL;
}

template <class V>
void
Splay<V>:: destroy(SPLAYFREE *free_func)
{
    if (head)
        head->destroy(free_func);

    head = NULL;

    elements = 0;
}

template <class V>
size_t
Splay<V>::size() const
{
    return elements;
}

template <class V>
const SplayConstIterator<V>
Splay<V>::begin() const
{
    return const_iterator(head);
}

template <class V>
const SplayConstIterator<V>
Splay<V>::end() const
{
    return const_iterator(NULL);
}

// XXX: This does not seem to iterate the whole thing in some cases.
template <class V>
class SplayConstIterator
{

public:
    typedef const V value_type;
    SplayConstIterator (SplayNode<V> *aNode);
    bool operator == (SplayConstIterator const &right) const;
    SplayConstIterator operator ++ (int dummy);
    SplayConstIterator &operator ++ ();
    V const & operator * () const;

private:
    void advance();
    void addLeftPath(SplayNode<V> *aNode);
    void init(SplayNode<V> *);
    std::stack<SplayNode<V> *> toVisit;
};

template <class V>
SplayConstIterator<V>::SplayConstIterator (SplayNode<V> *aNode)
{
    init(aNode);
}

template <class V>
bool
SplayConstIterator<V>::operator == (SplayConstIterator const &right) const
{
    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>
SplayConstIterator<V> &
SplayConstIterator<V>::operator ++ ()
{
    advance();
    return *this;
}

template <class V>
SplayConstIterator<V>
SplayConstIterator<V>::operator ++ (int dummy)
{
    SplayConstIterator<V> result = *this;
    advance();
    return result;
}

/* advance is simple enough:
* if the stack is empty, we're done.
* otherwise, pop the last visited node
* then, pop the next node to visit
* if that has a right child, add it and it's
* left-to-end path.
* then add the node back.
*/
template <class V>
void
SplayConstIterator<V>::advance()
{
    if (toVisit.empty())
        return;

    toVisit.pop();

    if (toVisit.empty())
        return;

    // not empty
    SplayNode<V> *currentNode = toVisit.top();
    toVisit.pop();

    addLeftPath(currentNode->right);

    toVisit.push(currentNode);
}

template <class V>
void
SplayConstIterator<V>::addLeftPath(SplayNode<V> *aNode)
{
    if (aNode == NULL)
        return;

    do {
        toVisit.push(aNode);
        aNode = aNode->left;
    } while (aNode != NULL);
}

template <class V>
void
SplayConstIterator<V>::init(SplayNode<V> *head)
{
    addLeftPath(head);
}

template <class V>
V const &
SplayConstIterator<V>::operator * () const
{
    /* can't dereference when past the end */

    if (toVisit.size() == 0)
        fatal ("Attempt to dereference SplayConstIterator past-the-end\n");

    return toVisit.top()->data;
}

#endif /* cplusplus */

#endif /* SQUID_SPLAY_H */
Commit	Line	Data
	1	/*
	2	* Copyright (C) 1996-2014 The Squid Software Foundation and contributors
	3	*
	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.
	7	*/
	8
	9	#ifndef SQUID_SPLAY_H
	10	#define SQUID_SPLAY_H
	11
	12	#if defined(__cplusplus)
	13
	14	#include "fatal.h"
	15
	16	#include <stack>
	17
	18	template <class V>
	19	class SplayNode
	20	{
	21
	22	public:
	23	typedef V Value;
	24	typedef int SPLAYCMP(Value const &a, Value const &b);
	25	typedef void SPLAYFREE(Value &);
	26	typedef void SPLAYWALKEE(Value const & nodedata, void *state);
	27	static void DefaultFree (Value &aValue) {delete aValue;}
	28
	29	SplayNode<V> (Value const &);
	30	Value data;
	31	mutable SplayNode<V> *left;
	32	mutable SplayNode<V> *right;
	33	void destroy(SPLAYFREE *);
	34	void walk(SPLAYWALKEE , void callerState);
	35	bool empty() const { return this == NULL; }
	36	SplayNode<V> const * start() const;
	37	SplayNode<V> const * finish() const;
	38
	39	SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
	40
	41	SplayNode<V> * insert(Value data, SPLAYCMP * compare);
	42
	43	template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
	44
	45	/// recursively visit left nodes, this node, and then right nodes
	46	template <class Visitor> void visit(Visitor &v) const;
	47	};
	48
	49	typedef SplayNode<void *> splayNode;
	50
	51	template <class V>
	52	class SplayConstIterator;
	53
	54	template <class V>
	55	class SplayIterator;
	56
	57	template <class V>
	58	class Splay
	59	{
	60
	61	public:
	62	typedef V Value;
	63	typedef int SPLAYCMP(Value const &a, Value const &b);
	64	typedef void SPLAYFREE(Value &);
	65	typedef SplayIterator<V> iterator;
	66	typedef const SplayConstIterator<V> const_iterator;
	67	Splay():head(NULL), elements (0) {}
	68
	69	mutable SplayNode<V> * head;
	70	template <class FindValue> Value const find (FindValue const &, int( compare)(FindValue const &a, Value const &b)) const;
	71	void insert(Value const &, SPLAYCMP *compare);
	72
	73	void remove(Value const &, SPLAYCMP *compare);
	74
	75	void destroy(SPLAYFREE *);
	76
	77	SplayNode<V> const * start() const;
	78
	79	SplayNode<V> const * finish() const;
	80
	81	size_t size() const;
	82
	83	const_iterator begin() const;
	84
	85	const_iterator end() const;
	86
	87	/// recursively visit all nodes, in left-to-right order
	88	template <class Visitor> void visit(Visitor &v) const;
	89
	90	size_t elements;
	91	};
	92
	93	SQUIDCEXTERN int splayLastResult;
	94
	95	SQUIDCEXTERN splayNode splay_insert(void , splayNode , splayNode::SPLAYCMP );
	96
	97	SQUIDCEXTERN splayNode splay_delete(const void , splayNode , splayNode::SPLAYCMP );
	98
	99	SQUIDCEXTERN splayNode splay_splay(const void , splayNode , splayNode::SPLAYCMP *);
	100
	101	SQUIDCEXTERN void splay_destroy(splayNode , splayNode::SPLAYFREE );
	102
	103	SQUIDCEXTERN void splay_walk(splayNode , splayNode::SPLAYWALKEE , void *callerState);
	104
	105	/* inline methods */
	106	template<class V>
	107	SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(NULL), right (NULL) {}
	108
	109	template<class V>
	110	void
	111	SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
	112	{
	113	if (this == NULL)
	114	return;
	115
	116	if (left)
	117	left->walk(walkee, state);
	118
	119	walkee(data, state);
	120
	121	if (right)
	122	right->walk(walkee, state);
	123	}
	124
	125	template<class V>
	126	SplayNode<V> const *
	127	SplayNode<V>::start() const
	128	{
	129	if (this && left)
	130	return left->start();
	131
	132	return this;
	133	}
	134
	135	template<class V>
	136	SplayNode<V> const *
	137	SplayNode<V>::finish() const
	138	{
	139	if (this && right)
	140	return right->finish();
	141
	142	return this;
	143	}
	144
	145	template<class V>
	146	void
	147	SplayNode<V>::destroy(SPLAYFREE * free_func)
	148	{
	149	if (!this)
	150	return;
	151
	152	if (left)
	153	left->destroy(free_func);
	154
	155	if (right)
	156	right->destroy(free_func);
	157
	158	free_func(data);
	159
	160	delete this;
	161	}
	162
	163	template<class V>
	164	SplayNode<V> *
	165	SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare)
	166	{
	167	if (this == NULL)
	168	return NULL;
	169
	170	SplayNode<V> *result = splay(dataToRemove, compare);
	171
	172	if (splayLastResult == 0) { /* found it */
	173	SplayNode<V> *newTop;
	174
	175	if (result->left == NULL) {
	176	newTop = result->right;
	177	} else {
	178	newTop = result->left->splay(dataToRemove, compare);
	179	/* temporary */
	180	newTop->right = result->right;
	181	result->right = NULL;
	182	}
	183
	184	delete result;
	185	return newTop;
	186	}
	187
	188	return result; /* It wasn't there */
	189	}
	190
	191	template<class V>
	192	SplayNode<V> *
	193	SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
	194	{
	195	/* create node to insert */
	196	SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
	197
	198	if (this == NULL) {
	199	splayLastResult = -1;
	200	newNode->left = newNode->right = NULL;
	201	return newNode;
	202	}
	203
	204	SplayNode<V> *newTop = splay(dataToInsert, compare);
	205
	206	if (splayLastResult < 0) {
	207	newNode->left = newTop->left;
	208	newNode->right = newTop;
	209	newTop->left = NULL;
	210	return newNode;
	211	} else if (splayLastResult > 0) {
	212	newNode->right = newTop->right;
	213	newNode->left = newTop;
	214	newTop->right = NULL;
	215	return newNode;
	216	} else {
	217	/* duplicate entry */
	218	delete newNode;
	219	return newTop;
	220	}
	221	}
	222
	223	template<class V>
	224	template<class FindValue>
	225	SplayNode<V> *
	226	SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
	227	{
	228	if (this == NULL) {
	229	/* can't have compared successfully :} */
	230	splayLastResult = -1;
	231	return NULL;
	232	}
	233
	234	Value temp = Value();
	235	SplayNode<V> N(temp);
	236	SplayNode<V> *l;
	237	SplayNode<V> *r;
	238	SplayNode<V> *y;
	239	N.left = N.right = NULL;
	240	l = r = &N;
	241
	242	SplayNode<V> top = const_cast<SplayNode<V> >(this);
	243
	244	for (;;) {
	245	splayLastResult = compare(dataToFind, top->data);
	246
	247	if (splayLastResult < 0) {
	248	if (top->left == NULL)
	249	break;
	250
	251	if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
	252	y = top->left; /* rotate right */
	253	top->left = y->right;
	254	y->right = top;
	255	top = y;
	256
	257	if (top->left == NULL)
	258	break;
	259	}
	260
	261	r->left = top; /* link right */
	262	r = top;
	263	top = top->left;
	264	} else if (splayLastResult > 0) {
	265	if (top->right == NULL)
	266	break;
	267
	268	if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
	269	y = top->right; /* rotate left */
	270	top->right = y->left;
	271	y->left = top;
	272	top = y;
	273
	274	if (top->right == NULL)
	275	break;
	276	}
	277
	278	l->right = top; /* link left */
	279	l = top;
	280	top = top->right;
	281	} else {
	282	break;
	283	}
	284	}
	285
	286	l->right = top->left; /* assemble */
	287	r->left = top->right;
	288	top->left = N.right;
	289	top->right = N.left;
	290	return top;
	291	}
	292
	293	template <class V>
	294	template <class Visitor>
	295	void
	296	SplayNode<V>::visit(Visitor &visitor) const
	297	{
	298	if (left)
	299	left->visit(visitor);
	300	visitor(data);
	301	if (right)
	302	right->visit(visitor);
	303	}
	304
	305	template <class V>
	306	template <class Visitor>
	307	void
	308	Splay<V>::visit(Visitor &visitor) const
	309	{
	310	if (head)
	311	head->visit(visitor);
	312	}
	313
	314	template <class V>
	315	template <class FindValue>
	316	typename Splay<V>::Value const *
	317	Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
	318	{
	319	head = head->splay(value, compare);
	320
	321	if (splayLastResult != 0)
	322	return NULL;
	323
	324	return &head->data;
	325	}
	326
	327	template <class V>
	328	void
	329	Splay<V>::insert(Value const &value, SPLAYCMP *compare)
	330	{
	331	assert (!find (value, compare));
	332	head = head->insert(value, compare);
	333	++elements;
	334	}
	335
	336	template <class V>
	337	void
	338	Splay<V>::remove(Value const &value, SPLAYCMP *compare)
	339	{
	340	assert (find (value, compare));
	341
	342	head = head->remove(value, compare);
	343
	344	--elements;
	345	}
	346
	347	template <class V>
	348	SplayNode<V> const *
	349	Splay<V>:: start() const
	350	{
	351	if (head)
	352	return head->start();
	353
	354	return NULL;
	355	}
	356
	357	template <class V>
	358	SplayNode<V> const *
	359	Splay<V>:: finish() const
	360	{
	361	if (head)
	362	return head->finish();
	363
	364	return NULL;
	365	}
	366
	367	template <class V>
	368	void
	369	Splay<V>:: destroy(SPLAYFREE *free_func)
	370	{
	371	if (head)
	372	head->destroy(free_func);
	373
	374	head = NULL;
	375
	376	elements = 0;
	377	}
	378
	379	template <class V>
	380	size_t
	381	Splay<V>::size() const
	382	{
	383	return elements;
	384	}
	385
	386	template <class V>
	387	const SplayConstIterator<V>
	388	Splay<V>::begin() const
	389	{
	390	return const_iterator(head);
	391	}
	392
	393	template <class V>
	394	const SplayConstIterator<V>
	395	Splay<V>::end() const
	396	{
	397	return const_iterator(NULL);
	398	}
	399
	400	// XXX: This does not seem to iterate the whole thing in some cases.
	401	template <class V>
	402	class SplayConstIterator
	403	{
	404
	405	public:
	406	typedef const V value_type;
	407	SplayConstIterator (SplayNode<V> *aNode);
	408	bool operator == (SplayConstIterator const &right) const;
	409	SplayConstIterator operator ++ (int dummy);
	410	SplayConstIterator &operator ++ ();
	411	V const & operator * () const;
	412
	413	private:
	414	void advance();
	415	void addLeftPath(SplayNode<V> *aNode);
	416	void init(SplayNode<V> *);
	417	std::stack<SplayNode<V> *> toVisit;
	418	};
	419
	420	template <class V>
	421	SplayConstIterator<V>::SplayConstIterator (SplayNode<V> *aNode)
	422	{
	423	init(aNode);
	424	}
	425
	426	template <class V>
	427	bool
	428	SplayConstIterator<V>::operator == (SplayConstIterator const &right) const
	429	{
	430	if (toVisit.empty() && right.toVisit.empty())
	431	return true;
	432	if (!toVisit.empty() && !right.toVisit.empty())
	433	return toVisit.top() == right.toVisit.top();
	434	// only one of the two is empty
	435	return false;
	436	}
	437
	438	template <class V>
	439	SplayConstIterator<V> &
	440	SplayConstIterator<V>::operator ++ ()
	441	{
	442	advance();
	443	return *this;
	444	}
	445
	446	template <class V>
	447	SplayConstIterator<V>
	448	SplayConstIterator<V>::operator ++ (int dummy)
	449	{
	450	SplayConstIterator<V> result = *this;
	451	advance();
	452	return result;
	453	}
	454
	455	/* advance is simple enough:
	456	* if the stack is empty, we're done.
	457	* otherwise, pop the last visited node
	458	* then, pop the next node to visit
	459	* if that has a right child, add it and it's
	460	* left-to-end path.
	461	* then add the node back.
	462	*/
	463	template <class V>
	464	void
	465	SplayConstIterator<V>::advance()
	466	{
	467	if (toVisit.empty())
	468	return;
	469
	470	toVisit.pop();
	471
	472	if (toVisit.empty())
	473	return;
	474
	475	// not empty
	476	SplayNode<V> *currentNode = toVisit.top();
	477	toVisit.pop();
	478
	479	addLeftPath(currentNode->right);
	480
	481	toVisit.push(currentNode);
	482	}
	483
	484	template <class V>
	485	void
	486	SplayConstIterator<V>::addLeftPath(SplayNode<V> *aNode)
	487	{
	488	if (aNode == NULL)
	489	return;
	490
	491	do {
	492	toVisit.push(aNode);
	493	aNode = aNode->left;
	494	} while (aNode != NULL);
	495	}
	496
	497	template <class V>
	498	void
	499	SplayConstIterator<V>::init(SplayNode<V> *head)
	500	{
	501	addLeftPath(head);
	502	}
	503
	504	template <class V>
	505	V const &
	506	SplayConstIterator<V>::operator * () const
	507	{
	508	/* can't dereference when past the end */
	509
	510	if (toVisit.size() == 0)
	511	fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
	512
	513	return toVisit.top()->data;
	514	}
	515
	516	#endif /* cplusplus */
	517
	518	#endif /* SQUID_SPLAY_H */