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

/*
 * $Id: splay.h,v 1.15 2003/02/08 01:45:46 robertc Exp $
 */

#ifndef SQUID_SPLAY_H
#define SQUID_SPLAY_H

#ifndef __cplusplus
/* legacy C bindings - can be removed when mempool is C++ */
typedef struct _splay_node {
    void *data;
    struct _splay_node *left;
    struct _splay_node *right;
} splayNode;

typedef int SPLAYCMP(const void **a, const void **b);
typedef void SPLAYWALKEE(void **nodedata, void *state);

SQUIDCEXTERN int splayLastResult;

/* MUST match C++ prototypes */
SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, SPLAYCMP *);
SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, SPLAYCMP *);
SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, SPLAYCMP *);
SQUIDCEXTERN void splay_walk(splayNode *, SPLAYWALKEE *, void *);
#else


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);
    Value data;
    mutable SplayNode<V> *left;
    mutable SplayNode<V> *right;
    void destroy(SPLAYFREE *);
    void walk(SPLAYWALKEE *, void *callerState);
    SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
    SplayNode<V> * insert(Value data, SPLAYCMP * compare);
    SplayNode<V> * splay(const Value &data, SPLAYCMP * compare) const;
};

typedef SplayNode<void *> splayNode;

template <class V>
class Splay {
  public:
    typedef V Value;
    typedef int SPLAYCMP(Value const &a, Value const &b);
    Splay():head(NULL){}
    mutable SplayNode<V> * head;
    Value const *find (Value const &, SPLAYCMP *compare) const;
};


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>
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>
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 data, SPLAYCMP * compare)
{
    if (this == NULL)
	return NULL;
    SplayNode<V> *result = splay(data, compare);
    if (splayLastResult == 0) {	/* found it */
	SplayNode<V> *newTop;
	if (result->left == NULL) {
	    newTop = result->right;
	} else {
	    newTop = result->left->splay(data, 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 data, SPLAYCMP * compare)
{
    /* create node to insert */
    SplayNode<V> *newNode = new SplayNode<V>;
    newNode->data = data;
    if (this == NULL) {
	newNode->left = newNode->right = NULL;
	return newNode;
    }
    
    SplayNode<V> *newTop = splay(data, 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>
SplayNode<V> *
SplayNode<V>::splay(Value const &data, SPLAYCMP * compare) const
{
    if (this == NULL)
	return NULL;
    SplayNode<V> N;
    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(data, top->data);
	if (splayLastResult < 0) {
	    if (top->left == NULL)
		break;
	    if ((splayLastResult = compare(data, 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(data, 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>
typename Splay<V>::Value const *
Splay<V>::find (Value const &value, SPLAYCMP *compare) const
{
    head = head->splay(value, compare);
    if (splayLastResult != 0)
	return NULL;
    return &head->data;
}

#endif

#endif /* SQUID_SPLAY_H */
Commit	Line	Data
0e2cd867	1	/*
29b17d63	2	* $Id: splay.h,v 1.15 2003/02/08 01:45:46 robertc Exp $
0e2cd867	3	*/
0e2cd867	4
b5638623	5	#ifndef SQUID_SPLAY_H
b5638623	6	#define SQUID_SPLAY_H
3c01c392	7
b67e2c8c	8	#ifndef __cplusplus
b67e2c8c	9	/* legacy C bindings - can be removed when mempool is C++ */
3c01c392	10	typedef struct _splay_node {
5b220cbf	11	void *data;
	12	struct _splay_node *left;
	13	struct _splay_node *right;
3c01c392	14	} splayNode;
3c01c392	15
29b17d63	16	typedef int SPLAYCMP(const void a, const void b);
29b17d63	17	typedef void SPLAYWALKEE(void *nodedata, void state);
3c01c392	18
e6ccf245	19	SQUIDCEXTERN int splayLastResult;
3c01c392	20
29b17d63	21	/* MUST match C++ prototypes */
e6ccf245	22	SQUIDCEXTERN splayNode splay_insert(void , splayNode , SPLAYCMP );
29b17d63	23	SQUIDCEXTERN splayNode splay_splay(const void , splayNode , SPLAYCMP *);
e6ccf245	24	SQUIDCEXTERN splayNode splay_delete(const void , splayNode , SPLAYCMP );
e6ccf245	25	SQUIDCEXTERN void splay_walk(splayNode , SPLAYWALKEE , void *);
b67e2c8c	26	#else
b67e2c8c	27
29b17d63	28
b67e2c8c	29	template <class V>
	30	class SplayNode {
	31	public:
	32	typedef V Value;
29b17d63	33	typedef int SPLAYCMP(Value const &a, Value const &b);
	34	typedef void SPLAYFREE(Value &);
	35	typedef void SPLAYWALKEE(Value const & nodedata, void *state);
	36	Value data;
	37	mutable SplayNode<V> *left;
	38	mutable SplayNode<V> *right;
	39	void destroy(SPLAYFREE *);
	40	void walk(SPLAYWALKEE , void callerState);
	41	SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
	42	SplayNode<V> * insert(Value data, SPLAYCMP * compare);
	43	SplayNode<V> * splay(const Value &data, SPLAYCMP * compare) const;
b67e2c8c	44	};
b67e2c8c	45
29b17d63	46	typedef SplayNode<void *> splayNode;
	47
	48	template <class V>
	49	class Splay {
	50	public:
	51	typedef V Value;
	52	typedef int SPLAYCMP(Value const &a, Value const &b);
	53	Splay():head(NULL){}
	54	mutable SplayNode<V> * head;
	55	Value const find (Value const &, SPLAYCMP compare) const;
	56	};
b67e2c8c	57
b67e2c8c	58
	59	SQUIDCEXTERN int splayLastResult;
	60
29b17d63	61	SQUIDCEXTERN splayNode splay_insert(void , splayNode , splayNode::SPLAYCMP );
	62	SQUIDCEXTERN splayNode splay_delete(const void , splayNode , splayNode::SPLAYCMP );
	63	SQUIDCEXTERN splayNode splay_splay(const void , splayNode , splayNode::SPLAYCMP *);
	64	SQUIDCEXTERN void splay_destroy(splayNode , splayNode::SPLAYFREE );
	65	SQUIDCEXTERN void splay_walk(splayNode , splayNode::SPLAYWALKEE , void *callerState);
	66
	67	/* inline methods */
	68	template<class V>
	69	void
	70	SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
	71	{
	72	if (this == NULL)
	73	return;
	74	if (left)
	75	left->walk(walkee, state);
	76	walkee(data, state);
	77	if (right)
	78	right->walk(walkee, state);
	79	}
	80
	81	template<class V>
	82	void
	83	SplayNode<V>::destroy(SPLAYFREE * free_func)
	84	{
	85	if (!this)
	86	return;
	87	if (left)
	88	left->destroy(free_func);
	89	if (right)
	90	right->destroy(free_func);
	91	free_func(data);
	92	delete this;
	93	}
	94
	95	template<class V>
	96	SplayNode<V> *
	97	SplayNode<V>::remove(Value const data, SPLAYCMP * compare)
	98	{
	99	if (this == NULL)
	100	return NULL;
	101	SplayNode<V> *result = splay(data, compare);
	102	if (splayLastResult == 0) { /* found it */
	103	SplayNode<V> *newTop;
	104	if (result->left == NULL) {
	105	newTop = result->right;
	106	} else {
	107	newTop = result->left->splay(data, compare);
	108	/* temporary */
	109	newTop->right = result->right;
	110	result->right = NULL;
	111	}
	112	delete result;
	113	return newTop;
	114	}
	115	return result; /* It wasn't there */
	116	}
b67e2c8c	117
29b17d63	118	template<class V>
	119	SplayNode<V> *
	120	SplayNode<V>::insert(Value data, SPLAYCMP * compare)
	121	{
	122	/* create node to insert */
	123	SplayNode<V> *newNode = new SplayNode<V>;
	124	newNode->data = data;
	125	if (this == NULL) {
	126	newNode->left = newNode->right = NULL;
	127	return newNode;
	128	}
	129
	130	SplayNode<V> *newTop = splay(data, compare);
	131	if (splayLastResult < 0) {
	132	newNode->left = newTop->left;
	133	newNode->right = newTop;
	134	newTop->left = NULL;
	135	return newNode;
	136	} else if (splayLastResult > 0) {
	137	newNode->right = newTop->right;
	138	newNode->left = newTop;
	139	newTop->right = NULL;
	140	return newNode;
	141	} else {
	142	/* duplicate entry */
	143	delete newNode;
	144	return newTop;
	145	}
	146	}
	147
	148	template<class V>
	149	SplayNode<V> *
	150	SplayNode<V>::splay(Value const &data, SPLAYCMP * compare) const
	151	{
	152	if (this == NULL)
	153	return NULL;
	154	SplayNode<V> N;
	155	SplayNode<V> *l;
	156	SplayNode<V> *r;
	157	SplayNode<V> *y;
	158	N.left = N.right = NULL;
	159	l = r = &N;
	160
	161	SplayNode<V> top = const_cast<SplayNode<V> >(this);
	162	for (;;) {
	163	splayLastResult = compare(data, top->data);
	164	if (splayLastResult < 0) {
	165	if (top->left == NULL)
	166	break;
	167	if ((splayLastResult = compare(data, top->left->data)) < 0) {
	168	y = top->left; /* rotate right */
	169	top->left = y->right;
	170	y->right = top;
	171	top = y;
	172	if (top->left == NULL)
	173	break;
	174	}
	175	r->left = top; /* link right */
	176	r = top;
	177	top = top->left;
	178	} else if (splayLastResult > 0) {
	179	if (top->right == NULL)
	180	break;
	181	if ((splayLastResult = compare(data, top->right->data)) > 0) {
182	y = top->right; /* rotate left */
183	top->right = y->left;
184	y->left = top;
185	top = y;
186	if (top->right == NULL)
187	break;
188	}
189	l->right = top; /* link left */
190	l = top;
191	top = top->right;
192	} else {
193	break;
194	}
195	}
196	l->right = top->left; /* assemble */
197	r->left = top->right;
198	top->left = N.right;
199	top->right = N.left;
200	return top;
201	}
202
203	template <class V>
204	typename Splay<V>::Value const *
205	Splay<V>::find (Value const &value, SPLAYCMP *compare) const
206	{
207	head = head->splay(value, compare);
208	if (splayLastResult != 0)
209	return NULL;
210	return &head->data;
211	}
b67e2c8c	212
b67e2c8c	213	#endif
bdffbfa5	214
b5638623	215	#endif /* SQUID_SPLAY_H */