[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, 675 Mass Ave, Cambridge, MA 02139, 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.  */

#ifndef IN_GCC
#include "libiberty.h"
#endif /* IN_GCC */
#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.  */

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