1169695Skan/* A splay-tree datatype. 2169695Skan Copyright 1998, 1999, 2000, 2002 Free Software Foundation, Inc. 3169695Skan Contributed by Mark Mitchell (mark@markmitchell.com). 4169695Skan 5169695SkanThis file is part of GCC. 6169695Skan 7169695SkanGCC is free software; you can redistribute it and/or modify it 8169695Skanunder the terms of the GNU General Public License as published by 9169695Skanthe Free Software Foundation; either version 2, or (at your option) 10169695Skanany later version. 11169695Skan 12169695SkanGCC is distributed in the hope that it will be useful, but 13169695SkanWITHOUT ANY WARRANTY; without even the implied warranty of 14169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15169695SkanGeneral Public License for more details. 16169695Skan 17169695SkanYou should have received a copy of the GNU General Public License 18169695Skanalong with GCC; see the file COPYING. If not, write to 19169695Skanthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20169695SkanBoston, MA 02110-1301, USA. */ 21169695Skan 22169695Skan/* For an easily readable description of splay-trees, see: 23169695Skan 24169695Skan Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 25169695Skan Algorithms. Harper-Collins, Inc. 1991. 26169695Skan 27169695Skan The major feature of splay trees is that all basic tree operations 28169695Skan are amortized O(log n) time for a tree with n nodes. */ 29169695Skan 30169695Skan#ifndef _SPLAY_TREE_H 31169695Skan#define _SPLAY_TREE_H 32169695Skan 33169695Skan#ifdef __cplusplus 34169695Skanextern "C" { 35169695Skan#endif /* __cplusplus */ 36169695Skan 37169695Skan#include "ansidecl.h" 38169695Skan 39169695Skan#ifndef GTY 40169695Skan#define GTY(X) 41169695Skan#endif 42169695Skan 43169695Skan/* Use typedefs for the key and data types to facilitate changing 44169695Skan these types, if necessary. These types should be sufficiently wide 45169695Skan that any pointer or scalar can be cast to these types, and then 46169695Skan cast back, without loss of precision. */ 47169695Skantypedef unsigned long int splay_tree_key; 48169695Skantypedef unsigned long int splay_tree_value; 49169695Skan 50169695Skan/* Forward declaration for a node in the tree. */ 51169695Skantypedef struct splay_tree_node_s *splay_tree_node; 52169695Skan 53169695Skan/* The type of a function which compares two splay-tree keys. The 54169695Skan function should return values as for qsort. */ 55169695Skantypedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); 56169695Skan 57169695Skan/* The type of a function used to deallocate any resources associated 58169695Skan with the key. */ 59169695Skantypedef void (*splay_tree_delete_key_fn) (splay_tree_key); 60169695Skan 61169695Skan/* The type of a function used to deallocate any resources associated 62169695Skan with the value. */ 63169695Skantypedef void (*splay_tree_delete_value_fn) (splay_tree_value); 64169695Skan 65169695Skan/* The type of a function used to iterate over the tree. */ 66169695Skantypedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); 67169695Skan 68169695Skan/* The type of a function used to allocate memory for tree root and 69169695Skan node structures. The first argument is the number of bytes needed; 70169695Skan the second is a data pointer the splay tree functions pass through 71169695Skan to the allocator. This function must never return zero. */ 72169695Skantypedef void *(*splay_tree_allocate_fn) (int, void *); 73169695Skan 74169695Skan/* The type of a function used to free memory allocated using the 75169695Skan corresponding splay_tree_allocate_fn. The first argument is the 76169695Skan memory to be freed; the latter is a data pointer the splay tree 77169695Skan functions pass through to the freer. */ 78169695Skantypedef void (*splay_tree_deallocate_fn) (void *, void *); 79169695Skan 80169695Skan/* The nodes in the splay tree. */ 81169695Skanstruct splay_tree_node_s GTY(()) 82169695Skan{ 83169695Skan /* The key. */ 84169695Skan splay_tree_key GTY ((use_param1)) key; 85169695Skan 86169695Skan /* The value. */ 87169695Skan splay_tree_value GTY ((use_param2)) value; 88169695Skan 89169695Skan /* The left and right children, respectively. */ 90169695Skan splay_tree_node GTY ((use_params)) left; 91169695Skan splay_tree_node GTY ((use_params)) right; 92169695Skan}; 93169695Skan 94169695Skan/* The splay tree itself. */ 95169695Skanstruct splay_tree_s GTY(()) 96169695Skan{ 97169695Skan /* The root of the tree. */ 98169695Skan splay_tree_node GTY ((use_params)) root; 99169695Skan 100169695Skan /* The comparision function. */ 101169695Skan splay_tree_compare_fn comp; 102169695Skan 103169695Skan /* The deallocate-key function. NULL if no cleanup is necessary. */ 104169695Skan splay_tree_delete_key_fn delete_key; 105169695Skan 106169695Skan /* The deallocate-value function. NULL if no cleanup is necessary. */ 107169695Skan splay_tree_delete_value_fn delete_value; 108169695Skan 109169695Skan /* Allocate/free functions, and a data pointer to pass to them. */ 110169695Skan splay_tree_allocate_fn allocate; 111169695Skan splay_tree_deallocate_fn deallocate; 112169695Skan void * GTY((skip)) allocate_data; 113169695Skan 114169695Skan}; 115169695Skantypedef struct splay_tree_s *splay_tree; 116169695Skan 117169695Skanextern splay_tree splay_tree_new (splay_tree_compare_fn, 118169695Skan splay_tree_delete_key_fn, 119169695Skan splay_tree_delete_value_fn); 120169695Skanextern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, 121169695Skan splay_tree_delete_key_fn, 122169695Skan splay_tree_delete_value_fn, 123169695Skan splay_tree_allocate_fn, 124169695Skan splay_tree_deallocate_fn, 125169695Skan void *); 126169695Skanextern void splay_tree_delete (splay_tree); 127169695Skanextern splay_tree_node splay_tree_insert (splay_tree, 128169695Skan splay_tree_key, 129169695Skan splay_tree_value); 130169695Skanextern void splay_tree_remove (splay_tree, splay_tree_key); 131169695Skanextern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key); 132169695Skanextern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key); 133169695Skanextern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key); 134169695Skanextern splay_tree_node splay_tree_max (splay_tree); 135169695Skanextern splay_tree_node splay_tree_min (splay_tree); 136169695Skanextern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); 137169695Skanextern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); 138169695Skanextern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); 139169695Skan 140169695Skan#ifdef __cplusplus 141169695Skan} 142169695Skan#endif /* __cplusplus */ 143169695Skan 144169695Skan#endif /* _SPLAY_TREE_H */ 145