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

/*
 * $Id: splay.h,v 1.17 2003/03/04 01:40:22 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);
    static void DefaultFree (Value &aValue) {aValue->deleteSelf();}
    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) {
	/* can't have compared successfully :} */
	splayLastResult = -1;
	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	/*
a46d2c0e	2	* $Id: splay.h,v 1.17 2003/03/04 01:40:22 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);
8000a965	36	static void DefaultFree (Value &aValue) {aValue->deleteSelf();}
29b17d63	37	Value data;
	38	mutable SplayNode<V> *left;
	39	mutable SplayNode<V> *right;
	40	void destroy(SPLAYFREE *);
	41	void walk(SPLAYWALKEE , void callerState);
	42	SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
	43	SplayNode<V> * insert(Value data, SPLAYCMP * compare);
	44	SplayNode<V> * splay(const Value &data, SPLAYCMP * compare) const;
b67e2c8c	45	};
b67e2c8c	46
29b17d63	47	typedef SplayNode<void *> splayNode;
	48
	49	template <class V>
	50	class Splay {
	51	public:
	52	typedef V Value;
	53	typedef int SPLAYCMP(Value const &a, Value const &b);
	54	Splay():head(NULL){}
	55	mutable SplayNode<V> * head;
	56	Value const find (Value const &, SPLAYCMP compare) const;
	57	};
b67e2c8c	58
b67e2c8c	59
	60	SQUIDCEXTERN int splayLastResult;
	61
29b17d63	62	SQUIDCEXTERN splayNode splay_insert(void , splayNode , splayNode::SPLAYCMP );
	63	SQUIDCEXTERN splayNode splay_delete(const void , splayNode , splayNode::SPLAYCMP );
	64	SQUIDCEXTERN splayNode splay_splay(const void , splayNode , splayNode::SPLAYCMP *);
	65	SQUIDCEXTERN void splay_destroy(splayNode , splayNode::SPLAYFREE );
	66	SQUIDCEXTERN void splay_walk(splayNode , splayNode::SPLAYWALKEE , void *callerState);
	67
	68	/* inline methods */
	69	template<class V>
	70	void
	71	SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
	72	{
	73	if (this == NULL)
	74	return;
	75	if (left)
	76	left->walk(walkee, state);
	77	walkee(data, state);
	78	if (right)
	79	right->walk(walkee, state);
	80	}
	81
	82	template<class V>
	83	void
	84	SplayNode<V>::destroy(SPLAYFREE * free_func)
	85	{
	86	if (!this)
	87	return;
	88	if (left)
	89	left->destroy(free_func);
	90	if (right)
	91	right->destroy(free_func);
	92	free_func(data);
	93	delete this;
	94	}
	95
	96	template<class V>
	97	SplayNode<V> *
	98	SplayNode<V>::remove(Value const data, SPLAYCMP * compare)
	99	{
	100	if (this == NULL)
	101	return NULL;
	102	SplayNode<V> *result = splay(data, compare);
	103	if (splayLastResult == 0) { /* found it */
	104	SplayNode<V> *newTop;
	105	if (result->left == NULL) {
	106	newTop = result->right;
	107	} else {
	108	newTop = result->left->splay(data, compare);
	109	/* temporary */
	110	newTop->right = result->right;
	111	result->right = NULL;
	112	}
	113	delete result;
	114	return newTop;
	115	}
	116	return result; /* It wasn't there */
	117	}
b67e2c8c	118
29b17d63	119	template<class V>
	120	SplayNode<V> *
	121	SplayNode<V>::insert(Value data, SPLAYCMP * compare)
	122	{
	123	/* create node to insert */
	124	SplayNode<V> *newNode = new SplayNode<V>;
	125	newNode->data = data;
	126	if (this == NULL) {
	127	newNode->left = newNode->right = NULL;
	128	return newNode;
	129	}
	130
	131	SplayNode<V> *newTop = splay(data, compare);
	132	if (splayLastResult < 0) {
	133	newNode->left = newTop->left;
	134	newNode->right = newTop;
	135	newTop->left = NULL;
	136	return newNode;
	137	} else if (splayLastResult > 0) {
	138	newNode->right = newTop->right;
	139	newNode->left = newTop;
	140	newTop->right = NULL;
	141	return newNode;
	142	} else {
	143	/* duplicate entry */
	144	delete newNode;
	145	return newTop;
	146	}
	147	}
	148
	149	template<class V>
	150	SplayNode<V> *
	151	SplayNode<V>::splay(Value const &data, SPLAYCMP * compare) const
	152	{
a46d2c0e	153	if (this == NULL) {
	154	/* can't have compared successfully :} */
	155	splayLastResult = -1;
29b17d63	156	return NULL;
a46d2c0e	157	}
29b17d63	158	SplayNode<V> N;
	159	SplayNode<V> *l;
	160	SplayNode<V> *r;
	161	SplayNode<V> *y;
	162	N.left = N.right = NULL;
	163	l = r = &N;
	164
	165	SplayNode<V> top = const_cast<SplayNode<V> >(this);
	166	for (;;) {
	167	splayLastResult = compare(data, top->data);
	168	if (splayLastResult < 0) {
	169	if (top->left == NULL)
	170	break;
	171	if ((splayLastResult = compare(data, top->left->data)) < 0) {
	172	y = top->left; /* rotate right */
	173	top->left = y->right;
	174	y->right = top;
	175	top = y;
	176	if (top->left == NULL)
	177	break;
	178	}
	179	r->left = top; /* link right */
	180	r = top;
	181	top = top->left;
	182	} else if (splayLastResult > 0) {
	183	if (top->right == NULL)
	184	break;
	185	if ((splayLastResult = compare(data, top->right->data)) > 0) {
	186	y = top->right; /* rotate left */
	187	top->right = y->left;
	188	y->left = top;
	189	top = y;
	190	if (top->right == NULL)
	191	break;
	192	}
	193	l->right = top; /* link left */
	194	l = top;
	195	top = top->right;
	196	} else {
	197	break;
	198	}
	199	}
	200	l->right = top->left; /* assemble */
	201	r->left = top->right;
	202	top->left = N.right;
	203	top->right = N.left;
	204	return top;
	205	}
	206
	207	template <class V>
	208	typename Splay<V>::Value const *
	209	Splay<V>::find (Value const &value, SPLAYCMP *compare) const
	210	{
	211	head = head->splay(value, compare);
	212	if (splayLastResult != 0)
	213	return NULL;
	214	return &head->data;
	215	}
b67e2c8c	216
b67e2c8c	217	#endif
bdffbfa5	218
b5638623	219	#endif /* SQUID_SPLAY_H */