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

/*
 * $Id: splay.h,v 1.18 2003/03/06 11:51:55 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), elements (0){}
    mutable SplayNode<V> * head;
    Value const *find (Value const &, SPLAYCMP *compare) const;
    void insert(Value const &, SPLAYCMP *compare);
    void remove(Value const &, SPLAYCMP *compare);
    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>
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) {
	splayLastResult = -1;
	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;
}

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

#endif

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