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

/* A splay-tree datatype.  
   Copyright (C) 1998, 1999 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_s));
  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.  Returns the new node.  */

splay_tree_node
splay_tree_insert (sp, key, value)
     splay_tree sp;
     splay_tree_key key;
     splay_tree_value value;
{
  int comparison = 0;

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

  return sp->root;
}

/* Remove KEY from SP.  It is not an error if it did not exist.  */

void
splay_tree_remove (sp, key)
     splay_tree sp;
     splay_tree_key key;
{
  splay_tree_splay (sp, key);

  if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
    {
      splay_tree_node left, right;

      left = sp->root->left;
      right = sp->root->right;

      /* Delete the root node itself.  */
      if (sp->delete_value)
	(*sp->delete_value) (sp->root->value);
      free (sp->root);

      /* One of the children is now the root.  Doesn't matter much
	 which, so long as we preserve the properties of the tree.  */
      if (left)
	{
	  sp->root = left;

	  /* If there was a right child as well, hang it off the 
	     right-most leaf of the left child.  */
	  if (right)
	    {
	      while (left->right)
		left = left->right;
	      left->right = right;
	    }
	}
      else
	sp->root = right;
    }
}

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

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

int
splay_tree_compare_pointers (k1, k2)
     splay_tree_key k1;
     splay_tree_key k2;
{
  if ((char*) k1 < (char*) k2)
    return -1;
  else if ((char*) k1 > (char*) k2)
    return 1;
  else 
    return 0;
}
Commit	Line	Data
ed87f9c8	1	/* A splay-tree datatype.
652374d3	2	Copyright (C) 1998, 1999 Free Software Foundation, Inc.
ed87f9c8 MM	3	Contributed by Mark Mitchell (mark@markmitchell.com).
ed87f9c8 MM	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	{
08230f26	238	splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));
ed87f9c8 MM	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
d080bbfa	259	with the new value. Returns the new node. */
ed87f9c8	260
d080bbfa	261	splay_tree_node
ed87f9c8 MM	262	splay_tree_insert (sp, key, value)
	263	splay_tree sp;
	264	splay_tree_key key;
	265	splay_tree_value value;
	266	{
652374d3	267	int comparison = 0;
ed87f9c8 MM	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
08230f26	287	node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));
ed87f9c8 MM	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	}
d080bbfa MM	308
d080bbfa MM	309	return sp->root;
ed87f9c8 MM	310	}
ed87f9c8 MM	311
dc17cc7b RH	312	/* Remove KEY from SP. It is not an error if it did not exist. */
	313
	314	void
	315	splay_tree_remove (sp, key)
	316	splay_tree sp;
	317	splay_tree_key key;
	318	{
	319	splay_tree_splay (sp, key);
	320
	321	if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
	322	{
	323	splay_tree_node left, right;
	324
	325	left = sp->root->left;
	326	right = sp->root->right;
	327
	328	/* Delete the root node itself. */
	329	if (sp->delete_value)
	330	(*sp->delete_value) (sp->root->value);
	331	free (sp->root);
	332
	333	/* One of the children is now the root. Doesn't matter much
	334	which, so long as we preserve the properties of the tree. */
	335	if (left)
	336	{
	337	sp->root = left;
	338
	339	/* If there was a right child as well, hang it off the
	340	right-most leaf of the left child. */
	341	if (right)
	342	{
	343	while (left->right)
	344	left = left->right;
	345	left->right = right;
	346	}
	347	}
	348	else
	349	sp->root = right;
	350	}
	351	}
	352
ed87f9c8 MM	353	/* Lookup KEY in SP, returning VALUE if present, and NULL
	354	otherwise. */
	355
	356	splay_tree_node
	357	splay_tree_lookup (sp, key)
	358	splay_tree sp;
	359	splay_tree_key key;
	360	{
	361	splay_tree_splay (sp, key);
	362
	363	if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
	364	return sp->root;
	365	else
	366	return 0;
	367	}
	368
	369	/* Call FN, passing it the DATA, for every node in SP, following an
	370	in-order traversal. If FN every returns a non-zero value, the
	371	iteration ceases immediately, and the value is returned.
	372	Otherwise, this function returns 0. */
	373
	374	int
	375	splay_tree_foreach (sp, fn, data)
	376	splay_tree sp;
	377	splay_tree_foreach_fn fn;
	378	void *data;
	379	{
	380	return splay_tree_foreach_helper (sp, sp->root, fn, data);
	381	}
30f72379 MM	382
	383	/* Splay-tree comparison function, treating the keys as ints. */
	384
	385	int
	386	splay_tree_compare_ints (k1, k2)
	387	splay_tree_key k1;
	388	splay_tree_key k2;
	389	{
	390	if ((int) k1 < (int) k2)
	391	return -1;
	392	else if ((int) k1 > (int) k2)
	393	return 1;
	394	else
	395	return 0;
	396	}
ae7f7270 MM	397
	398	/* Splay-tree comparison function, treating the keys as pointers. */
	399
	400	int
	401	splay_tree_compare_pointers (k1, k2)
	402	splay_tree_key k1;
	403	splay_tree_key k2;
	404	{
	405	if ((char) k1 < (char) k2)
	406	return -1;
	407	else if ((char) k1 > (char) k2)
	408	return 1;
	409	else
	410	return 0;
	411	}