[gcc.git] / libiberty / splay-tree.c

/* A splay-tree datatype.  
   Copyright (C) 1998 Free Software Foundation, Inc.
   Contributed by Mark Mitchell (mark@markmitchell.com).

This file is part of GNU CC.
   
GNU CC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* For an easily readable description of splay-trees, see:

     Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
     Algorithms.  Harper-Collins, Inc.  1991.  */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

#include "libiberty.h"
#include "splay-tree.h"

static void splay_tree_delete_helper    PARAMS((splay_tree, 
						splay_tree_node));
static void splay_tree_splay            PARAMS((splay_tree,
						splay_tree_key));
static splay_tree_node splay_tree_splay_helper     
                                        PARAMS((splay_tree,
						splay_tree_key,
						splay_tree_node*,
						splay_tree_node*,
						splay_tree_node*));
static int splay_tree_foreach_helper    PARAMS((splay_tree,
					        splay_tree_node,
						splay_tree_foreach_fn,
						void*));

/* Deallocate NODE (a member of SP), and all its sub-trees.  */

static void 
splay_tree_delete_helper (sp, node)
     splay_tree sp;
     splay_tree_node node;
{
  if (!node)
    return;

  splay_tree_delete_helper (sp, node->left);
  splay_tree_delete_helper (sp, node->right);

  if (sp->delete_key)
    (*sp->delete_key)(node->key);
  if (sp->delete_value)
    (*sp->delete_value)(node->value);

  free ((char*) node);
}

/* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
   and grandparent, respectively, of NODE.  */

static splay_tree_node
splay_tree_splay_helper (sp, key, node, parent, grandparent)
     splay_tree sp;
     splay_tree_key key;
     splay_tree_node *node;
     splay_tree_node *parent;
     splay_tree_node *grandparent;
{
  splay_tree_node *next;
  splay_tree_node n;
  int comparison;
  
  n = *node;

  if (!n)
    return *parent;

  comparison = (*sp->comp) (key, n->key);

  if (comparison == 0)
    /* We've found the target.  */
    next = 0;
  else if (comparison < 0)
    /* The target is to the left.  */
    next = &n->left;
  else 
    /* The target is to the right.  */
    next = &n->right;

  if (next)
    {
      /* Continue down the tree.  */
      n = splay_tree_splay_helper (sp, key, next, node, parent);

      /* The recursive call will change the place to which NODE
	 points.  */
      if (*node != n)
	return n;
    }

  if (!parent)
    /* NODE is the root.  We are done.  */
    return n;

  /* First, handle the case where there is no grandparent (i.e.,
     *PARENT is the root of the tree.)  */
  if (!grandparent) 
    {
      if (n == (*parent)->left)
	{
	  *node = n->right;
	  n->right = *parent;
	}
      else
	{
	  *node = n->left;
	  n->left = *parent;
	}
      *parent = n;
      return n;
    }

  /* Next handle the cases where both N and *PARENT are left children,
     or where both are right children.  */
  if (n == (*parent)->left && *parent == (*grandparent)->left)
    {
      splay_tree_node p = *parent;

      (*grandparent)->left = p->right;
      p->right = *grandparent;
      p->left = n->right;
      n->right = p;
      *grandparent = n;
      return n; 
    }
  else if  (n == (*parent)->right && *parent == (*grandparent)->right)
    {
      splay_tree_node p = *parent;

      (*grandparent)->right = p->left;
      p->left = *grandparent;
      p->right = n->left;
      n->left = p;
      *grandparent = n;
      return n;
    }

  /* Finally, deal with the case where N is a left child, but *PARENT
     is a right child, or vice versa.  */
  if (n == (*parent)->left) 
    {
      (*parent)->left = n->right;
      n->right = *parent;
      (*grandparent)->right = n->left;
      n->left = *grandparent;
      *grandparent = n;
      return n;
    } 
  else
    {
      (*parent)->right = n->left;
      n->left = *parent;
      (*grandparent)->left = n->right;
      n->right = *grandparent;
      *grandparent = n;
      return n;
    }
}

/* Splay SP around KEY.  */

static void
splay_tree_splay (sp, key)
     splay_tree sp;
     splay_tree_key key;
{
  if (sp->root == 0)
    return;

  splay_tree_splay_helper (sp, key, &sp->root, 
			   /*grandparent=*/0, /*parent=*/0); 
}

/* Call FN, passing it the DATA, for every node below NODE, all of
   which are from SP, following an in-order traversal.  If FN every
   returns a non-zero value, the iteration ceases immediately, and the
   value is returned.  Otherwise, this function returns 0.  */

static int
splay_tree_foreach_helper (sp, node, fn, data)
     splay_tree sp;
     splay_tree_node node;
     splay_tree_foreach_fn fn;
     void* data;
{
  int val;

  if (!node)
    return 0;

  val = splay_tree_foreach_helper (sp, node->left, fn, data);
  if (val)
    return val;

  val = (*fn)(node, data);
  if (val)
    return val;

  return splay_tree_foreach_helper (sp, node->right, fn, data);
}

/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
   DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
   values.  */

splay_tree 
splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
     splay_tree_compare_fn compare_fn;
     splay_tree_delete_key_fn delete_key_fn;
     splay_tree_delete_value_fn delete_value_fn;
{
  splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree));
  sp->root = 0;
  sp->comp = compare_fn;
  sp->delete_key = delete_key_fn;
  sp->delete_value = delete_value_fn;

  return sp;
}

/* Deallocate SP.  */

void 
splay_tree_delete (sp)
     splay_tree sp;
{
  splay_tree_delete_helper (sp, sp->root);
  free ((char*) sp);
}

/* Insert a new node (associating KEY with DATA) into SP.  If a
   previous node with the indicated KEY exists, its data is replaced
   with the new value.  */

void 
splay_tree_insert (sp, key, value)
     splay_tree sp;
     splay_tree_key key;
     splay_tree_value value;
{
  int comparison;

  splay_tree_splay (sp, key);

  if (sp->root)
    comparison = (*sp->comp)(sp->root->key, key);

  if (sp->root && comparison == 0)
    {
      /* If the root of the tree already has the indicated KEY, just
	 replace the value with VALUE.  */
      if (sp->delete_value)
	(*sp->delete_value)(sp->root->value);
      sp->root->value = value;
    } 
  else 
    {
      /* Create a new node, and insert it at the root.  */
      splay_tree_node node;
      
      node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node));
      node->key = key;
      node->value = value;
      
      if (!sp->root)
	node->left = node->right = 0;
      else if (comparison < 0)
	{
	  node->left = sp->root;
	  node->right = node->left->right;
	  node->left->right = 0;
	}
      else
	{
	  node->right = sp->root;
	  node->left = node->right->left;
	  node->right->left = 0;
	}

    sp->root = node;
  }
}

/* Lookup KEY in SP, returning VALUE if present, and NULL 
   otherwise.  */

splay_tree_node
splay_tree_lookup (sp, key)
     splay_tree sp;
     splay_tree_key key;
{
  splay_tree_splay (sp, key);

  if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
    return sp->root;
  else
    return 0;
}

/* Call FN, passing it the DATA, for every node in SP, following an
   in-order traversal.  If FN every returns a non-zero value, the
   iteration ceases immediately, and the value is returned.
   Otherwise, this function returns 0.  */

int
splay_tree_foreach (sp, fn, data)
     splay_tree sp;
     splay_tree_foreach_fn fn;
     void *data;
{
  return splay_tree_foreach_helper (sp, sp->root, fn, data);
}

/* Splay-tree comparison function, treating the keys as ints.  */

int
splay_tree_compare_ints (k1, k2)
     splay_tree_key k1;
     splay_tree_key k2;
{
  if ((int) k1 < (int) k2)
    return -1;
  else if ((int) k1 > (int) k2)
    return 1;
  else 
    return 0;
}
Commit	Line	Data
ed87f9c8 MM	1	/* A splay-tree datatype.
	2	Copyright (C) 1998 Free Software Foundation, Inc.
	3	Contributed by Mark Mitchell (mark@markmitchell.com).
	4
28923099	5	This file is part of GNU CC.
ed87f9c8	6
28923099 JL	7	GNU CC is free software; you can redistribute it and/or modify it
	8	under the terms of the GNU General Public License as published by
	9	the Free Software Foundation; either version 2, or (at your option)
	10	any later version.
ed87f9c8	11
28923099 JL	12	GNU CC is distributed in the hope that it will be useful, but
	13	WITHOUT ANY WARRANTY; without even the implied warranty of
	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	15	General Public License for more details.
ed87f9c8	16
28923099 JL	17	You should have received a copy of the GNU General Public License
28923099 JL	18	along with GNU CC; see the file COPYING. If not, write to
0cd43577 JL	19	the Free Software Foundation, 59 Temple Place - Suite 330,
0cd43577 JL	20	Boston, MA 02111-1307, USA. */
ed87f9c8	21
28923099	22	/* For an easily readable description of splay-trees, see:
ed87f9c8 MM	23
	24	Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
	25	Algorithms. Harper-Collins, Inc. 1991. */
	26
11a0bb74	27	#ifdef HAVE_CONFIG_H
ad3ef78e MM	28	#include "config.h"
	29	#endif
	30
	31	#ifdef HAVE_STDLIB_H
	32	#include <stdlib.h>
	33	#endif
	34
ed87f9c8	35	#include "libiberty.h"
ed87f9c8 MM	36	#include "splay-tree.h"
	37
	38	static void splay_tree_delete_helper PARAMS((splay_tree,
	39	splay_tree_node));
	40	static void splay_tree_splay PARAMS((splay_tree,
	41	splay_tree_key));
	42	static splay_tree_node splay_tree_splay_helper
	43	PARAMS((splay_tree,
	44	splay_tree_key,
	45	splay_tree_node*,
	46	splay_tree_node*,
	47	splay_tree_node*));
	48	static int splay_tree_foreach_helper PARAMS((splay_tree,
	49	splay_tree_node,
	50	splay_tree_foreach_fn,
	51	void*));
	52
	53	/* Deallocate NODE (a member of SP), and all its sub-trees. */
	54
	55	static void
	56	splay_tree_delete_helper (sp, node)
	57	splay_tree sp;
	58	splay_tree_node node;
	59	{
	60	if (!node)
	61	return;
	62
	63	splay_tree_delete_helper (sp, node->left);
	64	splay_tree_delete_helper (sp, node->right);
	65
	66	if (sp->delete_key)
	67	(*sp->delete_key)(node->key);
	68	if (sp->delete_value)
	69	(*sp->delete_value)(node->value);
	70
	71	free ((char*) node);
	72	}
	73
	74	/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent
	75	and grandparent, respectively, of NODE. */
	76
	77	static splay_tree_node
	78	splay_tree_splay_helper (sp, key, node, parent, grandparent)
	79	splay_tree sp;
	80	splay_tree_key key;
	81	splay_tree_node *node;
	82	splay_tree_node *parent;
	83	splay_tree_node *grandparent;
	84	{
	85	splay_tree_node *next;
	86	splay_tree_node n;
	87	int comparison;
	88
	89	n = *node;
	90
	91	if (!n)
	92	return *parent;
	93
	94	comparison = (*sp->comp) (key, n->key);
	95
	96	if (comparison == 0)
	97	/* We've found the target. */
	98	next = 0;
	99	else if (comparison < 0)
100	/* The target is to the left. */
101	next = &n->left;
102	else
103	/* The target is to the right. */
104	next = &n->right;
105
106	if (next)
107	{
108	/* Continue down the tree. */
109	n = splay_tree_splay_helper (sp, key, next, node, parent);
110
111	/* The recursive call will change the place to which NODE
112	points. */
113	if (*node != n)
114	return n;
115	}
116
117	if (!parent)
118	/* NODE is the root. We are done. */
119	return n;
120
121	/* First, handle the case where there is no grandparent (i.e.,
122	PARENT is the root of the tree.) /
123	if (!grandparent)
124	{
125	if (n == (*parent)->left)
126	{
127	*node = n->right;
128	n->right = *parent;
129	}
130	else
131	{
132	*node = n->left;
133	n->left = *parent;
134	}
135	*parent = n;
136	return n;
137	}
138
139	/* Next handle the cases where both N and *PARENT are left children,
140	or where both are right children. */
141	if (n == (parent)->left && parent == (*grandparent)->left)
142	{
143	splay_tree_node p = *parent;
144
145	(*grandparent)->left = p->right;
146	p->right = *grandparent;
147	p->left = n->right;
148	n->right = p;
149	*grandparent = n;
150	return n;
151	}
152	else if (n == (parent)->right && parent == (*grandparent)->right)
153	{
154	splay_tree_node p = *parent;
155
156	(*grandparent)->right = p->left;
157	p->left = *grandparent;
158	p->right = n->left;
159	n->left = p;
160	*grandparent = n;
161	return n;
162	}
163
164	/* Finally, deal with the case where N is a left child, but *PARENT
165	is a right child, or vice versa. */
166	if (n == (*parent)->left)
167	{
168	(*parent)->left = n->right;
169	n->right = *parent;
170	(*grandparent)->right = n->left;
171	n->left = *grandparent;
172	*grandparent = n;
173	return n;
174	}
175	else
176	{
177	(*parent)->right = n->left;
178	n->left = *parent;
179	(*grandparent)->left = n->right;
180	n->right = *grandparent;
181	*grandparent = n;
182	return n;
183	}
184	}
185
186	/* Splay SP around KEY. */
187
188	static void
189	splay_tree_splay (sp, key)
190	splay_tree sp;
191	splay_tree_key key;
192	{
193	if (sp->root == 0)
194	return;
195
196	splay_tree_splay_helper (sp, key, &sp->root,
197	/grandparent=/0, /parent=/0);
198	}
199
200	/* Call FN, passing it the DATA, for every node below NODE, all of
201	which are from SP, following an in-order traversal. If FN every
202	returns a non-zero value, the iteration ceases immediately, and the
203	value is returned. Otherwise, this function returns 0. */
204
b056ad1c	205	static int
ed87f9c8 MM	206	splay_tree_foreach_helper (sp, node, fn, data)
	207	splay_tree sp;
	208	splay_tree_node node;
	209	splay_tree_foreach_fn fn;
	210	void* data;
	211	{
	212	int val;
	213
	214	if (!node)
	215	return 0;
	216
	217	val = splay_tree_foreach_helper (sp, node->left, fn, data);
	218	if (val)
	219	return val;
	220
	221	val = (*fn)(node, data);
	222	if (val)
	223	return val;
	224
	225	return splay_tree_foreach_helper (sp, node->right, fn, data);
	226	}
	227
	228	/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
	229	DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
	230	values. */
	231
	232	splay_tree
	233	splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
	234	splay_tree_compare_fn compare_fn;
	235	splay_tree_delete_key_fn delete_key_fn;
	236	splay_tree_delete_value_fn delete_value_fn;
	237	{
	238	splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree));
	239	sp->root = 0;
	240	sp->comp = compare_fn;
	241	sp->delete_key = delete_key_fn;
	242	sp->delete_value = delete_value_fn;
	243
	244	return sp;
	245	}
	246
	247	/* Deallocate SP. */
	248
	249	void
	250	splay_tree_delete (sp)
	251	splay_tree sp;
	252	{
	253	splay_tree_delete_helper (sp, sp->root);
	254	free ((char*) sp);
	255	}
	256
	257	/* Insert a new node (associating KEY with DATA) into SP. If a
	258	previous node with the indicated KEY exists, its data is replaced
	259	with the new value. */
	260
	261	void
	262	splay_tree_insert (sp, key, value)
	263	splay_tree sp;
	264	splay_tree_key key;
	265	splay_tree_value value;
	266	{
	267	int comparison;
	268
	269	splay_tree_splay (sp, key);
270
271	if (sp->root)
272	comparison = (*sp->comp)(sp->root->key, key);
273
274	if (sp->root && comparison == 0)
275	{
276	/* If the root of the tree already has the indicated KEY, just
277	replace the value with VALUE. */
278	if (sp->delete_value)
279	(*sp->delete_value)(sp->root->value);
280	sp->root->value = value;
281	}
282	else
283	{
284	/* Create a new node, and insert it at the root. */
285	splay_tree_node node;
286
287	node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node));
288	node->key = key;
289	node->value = value;
290
291	if (!sp->root)
292	node->left = node->right = 0;
293	else if (comparison < 0)
294	{
295	node->left = sp->root;
296	node->right = node->left->right;
297	node->left->right = 0;
298	}
299	else
300	{
301	node->right = sp->root;
302	node->left = node->right->left;
303	node->right->left = 0;
304	}
305
306	sp->root = node;
307	}
308	}
309
310	/* Lookup KEY in SP, returning VALUE if present, and NULL
311	otherwise. */
312
313	splay_tree_node
314	splay_tree_lookup (sp, key)
315	splay_tree sp;
316	splay_tree_key key;
317	{
318	splay_tree_splay (sp, key);
319
320	if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
321	return sp->root;
322	else
323	return 0;
324	}
325
326	/* Call FN, passing it the DATA, for every node in SP, following an
327	in-order traversal. If FN every returns a non-zero value, the
328	iteration ceases immediately, and the value is returned.
329	Otherwise, this function returns 0. */
330
331	int
332	splay_tree_foreach (sp, fn, data)
333	splay_tree sp;
334	splay_tree_foreach_fn fn;
335	void *data;
336	{
337	return splay_tree_foreach_helper (sp, sp->root, fn, data);
338	}
30f72379 MM	339
	340	/* Splay-tree comparison function, treating the keys as ints. */
	341
	342	int
	343	splay_tree_compare_ints (k1, k2)
	344	splay_tree_key k1;
	345	splay_tree_key k2;
	346	{
	347	if ((int) k1 < (int) k2)
	348	return -1;
	349	else if ((int) k1 > (int) k2)
	350	return 1;
	351	else
	352	return 0;
	353	}