[thirdparty/binutils-gdb.git] / include / splay-tree.h

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

   This file is part of GCC.
   
   GCC 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.

   GCC 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 GCC; see the file COPYING.  If not, write to
   the Free Software Foundation, 51 Franklin Street - Fifth Floor,
   Boston, MA 02110-1301, 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.  

   The major feature of splay trees is that all basic tree operations
   are amortized O(log n) time for a tree with n nodes.  */

#ifndef _SPLAY_TREE_H
#define _SPLAY_TREE_H

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */

#include "ansidecl.h"

#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif
#ifdef HAVE_INTTYPES_H
#include <inttypes.h>
#endif

/* Use typedefs for the key and data types to facilitate changing
   these types, if necessary.  These types should be sufficiently wide
   that any pointer or scalar can be cast to these types, and then
   cast back, without loss of precision.  */
typedef uintptr_t splay_tree_key;
typedef uintptr_t splay_tree_value;

/* Forward declaration for a node in the tree.  */
typedef struct splay_tree_node_s *splay_tree_node;

/* The type of a function which compares two splay-tree keys.  The
   function should return values as for qsort.  */
typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key);

/* The type of a function used to deallocate any resources associated
   with the key.  If you provide this function, the splay tree
   will take the ownership of the memory of the splay_tree_key arg
   of splay_tree_insert.  This function is called to release the keys
   present in the tree when calling splay_tree_delete or splay_tree_remove.
   If splay_tree_insert is called with a key equal to a key already
   present in the tree, the old key and old value will be released.  */
typedef void (*splay_tree_delete_key_fn) (splay_tree_key);

/* The type of a function used to deallocate any resources associated
   with the value.  If you provide this function, the memory of the
   splay_tree_value arg of splay_tree_insert is managed similarly to
   the splay_tree_key memory: see splay_tree_delete_key_fn.  */
typedef void (*splay_tree_delete_value_fn) (splay_tree_value);

/* The type of a function used to iterate over the tree.  */
typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*);

/* The type of a function used to allocate memory for tree root and
   node structures.  The first argument is the number of bytes needed;
   the second is a data pointer the splay tree functions pass through
   to the allocator.  This function must never return zero.  */
typedef void *(*splay_tree_allocate_fn) (int, void *);

/* The type of a function used to free memory allocated using the
   corresponding splay_tree_allocate_fn.  The first argument is the
   memory to be freed; the latter is a data pointer the splay tree
   functions pass through to the freer.  */
typedef void (*splay_tree_deallocate_fn) (void *, void *);

/* The nodes in the splay tree.  */
struct splay_tree_node_s {
  /* The key.  */
  splay_tree_key key;

  /* The value.  */
  splay_tree_value value;

  /* The left and right children, respectively.  */
  splay_tree_node left;
  splay_tree_node right;
};

/* The splay tree itself.  */
struct splay_tree_s {
  /* The root of the tree.  */
  splay_tree_node root;

  /* The comparision function.  */
  splay_tree_compare_fn comp;

  /* The deallocate-key function.  NULL if no cleanup is necessary.  */
  splay_tree_delete_key_fn delete_key;

  /* The deallocate-value function.  NULL if no cleanup is necessary.  */
  splay_tree_delete_value_fn delete_value;

  /* Node allocate function.  Takes allocate_data as a parameter. */
  splay_tree_allocate_fn allocate;

  /* Free function for nodes and trees.  Takes allocate_data as a parameter.  */
  splay_tree_deallocate_fn deallocate;

  /* Parameter for allocate/free functions.  */
  void *allocate_data;
};

typedef struct splay_tree_s *splay_tree;

extern splay_tree splay_tree_new (splay_tree_compare_fn,
				  splay_tree_delete_key_fn,
				  splay_tree_delete_value_fn);
extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn,
						 splay_tree_delete_key_fn,
						 splay_tree_delete_value_fn,
						 splay_tree_allocate_fn,
						 splay_tree_deallocate_fn,
						 void *);
extern splay_tree splay_tree_new_typed_alloc (splay_tree_compare_fn,
					      splay_tree_delete_key_fn,
					      splay_tree_delete_value_fn,
					      splay_tree_allocate_fn,
					      splay_tree_allocate_fn,
					      splay_tree_deallocate_fn,
					      void *);
extern void splay_tree_delete (splay_tree);
extern splay_tree_node splay_tree_insert (splay_tree,
					  splay_tree_key,
					  splay_tree_value);
extern void splay_tree_remove	(splay_tree, splay_tree_key);
extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
extern splay_tree_node splay_tree_max (splay_tree);
extern splay_tree_node splay_tree_min (splay_tree);
extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*);
extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key);
extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key);
extern int splay_tree_compare_strings (splay_tree_key, splay_tree_key);
extern void splay_tree_delete_pointers (splay_tree_value);

#ifdef __cplusplus
}
#endif /* __cplusplus */

#endif /* _SPLAY_TREE_H */
Commit	Line	Data
	1	/* A splay-tree datatype.
	2	Copyright (C) 1998-2025 Free Software Foundation, Inc.
	3	Contributed by Mark Mitchell (mark@markmitchell.com).
	4
	5	This file is part of GCC.
	6
	7	GCC 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	GCC 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 GCC; see the file COPYING. If not, write to
	19	the Free Software Foundation, 51 Franklin Street - Fifth Floor,
	20	Boston, MA 02110-1301, USA. */
	21
	22	/* For an easily readable description of splay-trees, see:
	23
	24	Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
	25	Algorithms. Harper-Collins, Inc. 1991.
	26
	27	The major feature of splay trees is that all basic tree operations
	28	are amortized O(log n) time for a tree with n nodes. */
	29
	30	#ifndef _SPLAY_TREE_H
	31	#define _SPLAY_TREE_H
	32
	33	#ifdef __cplusplus
	34	extern "C" {
	35	#endif /* __cplusplus */
	36
	37	#include "ansidecl.h"
	38
	39	#ifdef HAVE_STDINT_H
	40	#include <stdint.h>
	41	#endif
	42	#ifdef HAVE_INTTYPES_H
	43	#include <inttypes.h>
	44	#endif
	45
	46	/* Use typedefs for the key and data types to facilitate changing
	47	these types, if necessary. These types should be sufficiently wide
	48	that any pointer or scalar can be cast to these types, and then
	49	cast back, without loss of precision. */
	50	typedef uintptr_t splay_tree_key;
	51	typedef uintptr_t splay_tree_value;
	52
	53	/* Forward declaration for a node in the tree. */
	54	typedef struct splay_tree_node_s *splay_tree_node;
	55
	56	/* The type of a function which compares two splay-tree keys. The
	57	function should return values as for qsort. */
	58	typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key);
	59
	60	/* The type of a function used to deallocate any resources associated
	61	with the key. If you provide this function, the splay tree
	62	will take the ownership of the memory of the splay_tree_key arg
	63	of splay_tree_insert. This function is called to release the keys
	64	present in the tree when calling splay_tree_delete or splay_tree_remove.
	65	If splay_tree_insert is called with a key equal to a key already
	66	present in the tree, the old key and old value will be released. */
	67	typedef void (*splay_tree_delete_key_fn) (splay_tree_key);
	68
	69	/* The type of a function used to deallocate any resources associated
	70	with the value. If you provide this function, the memory of the
	71	splay_tree_value arg of splay_tree_insert is managed similarly to
	72	the splay_tree_key memory: see splay_tree_delete_key_fn. */
	73	typedef void (*splay_tree_delete_value_fn) (splay_tree_value);
	74
	75	/* The type of a function used to iterate over the tree. */
	76	typedef int (splay_tree_foreach_fn) (splay_tree_node, void);
	77
	78	/* The type of a function used to allocate memory for tree root and
	79	node structures. The first argument is the number of bytes needed;
	80	the second is a data pointer the splay tree functions pass through
	81	to the allocator. This function must never return zero. */
	82	typedef void (splay_tree_allocate_fn) (int, void *);
	83
	84	/* The type of a function used to free memory allocated using the
	85	corresponding splay_tree_allocate_fn. The first argument is the
	86	memory to be freed; the latter is a data pointer the splay tree
	87	functions pass through to the freer. */
	88	typedef void (splay_tree_deallocate_fn) (void , void *);
	89
	90	/* The nodes in the splay tree. */
	91	struct splay_tree_node_s {
	92	/* The key. */
	93	splay_tree_key key;
	94
	95	/* The value. */
	96	splay_tree_value value;
	97
	98	/* The left and right children, respectively. */
	99	splay_tree_node left;
	100	splay_tree_node right;
	101	};
	102
	103	/* The splay tree itself. */
	104	struct splay_tree_s {
	105	/* The root of the tree. */
	106	splay_tree_node root;
	107
	108	/* The comparision function. */
	109	splay_tree_compare_fn comp;
	110
	111	/* The deallocate-key function. NULL if no cleanup is necessary. */
	112	splay_tree_delete_key_fn delete_key;
	113
	114	/* The deallocate-value function. NULL if no cleanup is necessary. */
	115	splay_tree_delete_value_fn delete_value;
	116
	117	/* Node allocate function. Takes allocate_data as a parameter. */
	118	splay_tree_allocate_fn allocate;
	119
	120	/* Free function for nodes and trees. Takes allocate_data as a parameter. */
	121	splay_tree_deallocate_fn deallocate;
	122
	123	/* Parameter for allocate/free functions. */
	124	void *allocate_data;
	125	};
	126
	127	typedef struct splay_tree_s *splay_tree;
	128
	129	extern splay_tree splay_tree_new (splay_tree_compare_fn,
	130	splay_tree_delete_key_fn,
	131	splay_tree_delete_value_fn);
	132	extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn,
	133	splay_tree_delete_key_fn,
	134	splay_tree_delete_value_fn,
	135	splay_tree_allocate_fn,
	136	splay_tree_deallocate_fn,
	137	void *);
	138	extern splay_tree splay_tree_new_typed_alloc (splay_tree_compare_fn,
	139	splay_tree_delete_key_fn,
	140	splay_tree_delete_value_fn,
	141	splay_tree_allocate_fn,
	142	splay_tree_allocate_fn,
	143	splay_tree_deallocate_fn,
	144	void *);
	145	extern void splay_tree_delete (splay_tree);
	146	extern splay_tree_node splay_tree_insert (splay_tree,
	147	splay_tree_key,
	148	splay_tree_value);
	149	extern void splay_tree_remove (splay_tree, splay_tree_key);
	150	extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
	151	extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
	152	extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
	153	extern splay_tree_node splay_tree_max (splay_tree);
	154	extern splay_tree_node splay_tree_min (splay_tree);
	155	extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*);
	156	extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key);
	157	extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key);
	158	extern int splay_tree_compare_strings (splay_tree_key, splay_tree_key);
	159	extern void splay_tree_delete_pointers (splay_tree_value);
	160
	161	#ifdef __cplusplus
	162	}
	163	#endif /* __cplusplus */
	164
	165	#endif /* _SPLAY_TREE_H */