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

/*
 * $Id: splay.h,v 1.20 2003/06/24 12:30:59 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> const * start() const;
    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);
    SplayNode<V> const * start() 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>
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>
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>;
    newNode->data = 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>
SplayNode<V> *
SplayNode<V>::splay(Value const &dataToFind, 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(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>
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;
}

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

#endif

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