160484Sobrien/* A splay-tree datatype. 2104834Sobrien Copyright 1998, 1999, 2000, 2002 Free Software Foundation, Inc. 360484Sobrien Contributed by Mark Mitchell (mark@markmitchell.com). 460484Sobrien 589857SobrienThis file is part of GCC. 660484Sobrien 789857SobrienGCC is free software; you can redistribute it and/or modify it 860484Sobrienunder the terms of the GNU General Public License as published by 960484Sobrienthe Free Software Foundation; either version 2, or (at your option) 1060484Sobrienany later version. 1160484Sobrien 1289857SobrienGCC is distributed in the hope that it will be useful, but 1360484SobrienWITHOUT ANY WARRANTY; without even the implied warranty of 1460484SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1560484SobrienGeneral Public License for more details. 1660484Sobrien 1760484SobrienYou should have received a copy of the GNU General Public License 1889857Sobrienalong with GCC; see the file COPYING. If not, write to 19218822Sdimthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20218822SdimBoston, MA 02110-1301, USA. */ 2160484Sobrien 2260484Sobrien/* For an easily readable description of splay-trees, see: 2360484Sobrien 2460484Sobrien Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 2560484Sobrien Algorithms. Harper-Collins, Inc. 1991. 2660484Sobrien 2760484Sobrien The major feature of splay trees is that all basic tree operations 2860484Sobrien are amortized O(log n) time for a tree with n nodes. */ 2960484Sobrien 3060484Sobrien#ifndef _SPLAY_TREE_H 3160484Sobrien#define _SPLAY_TREE_H 3260484Sobrien 3360484Sobrien#ifdef __cplusplus 3460484Sobrienextern "C" { 3560484Sobrien#endif /* __cplusplus */ 3660484Sobrien 37104834Sobrien#include "ansidecl.h" 3860484Sobrien 39130561Sobrien#ifndef GTY 40130561Sobrien#define GTY(X) 41130561Sobrien#endif 42130561Sobrien 4360484Sobrien/* Use typedefs for the key and data types to facilitate changing 4460484Sobrien these types, if necessary. These types should be sufficiently wide 4560484Sobrien that any pointer or scalar can be cast to these types, and then 4660484Sobrien cast back, without loss of precision. */ 4760484Sobrientypedef unsigned long int splay_tree_key; 4860484Sobrientypedef unsigned long int splay_tree_value; 4960484Sobrien 5060484Sobrien/* Forward declaration for a node in the tree. */ 5160484Sobrientypedef struct splay_tree_node_s *splay_tree_node; 5260484Sobrien 5360484Sobrien/* The type of a function which compares two splay-tree keys. The 5460484Sobrien function should return values as for qsort. */ 55218822Sdimtypedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); 5660484Sobrien 5760484Sobrien/* The type of a function used to deallocate any resources associated 5860484Sobrien with the key. */ 59218822Sdimtypedef void (*splay_tree_delete_key_fn) (splay_tree_key); 6060484Sobrien 6160484Sobrien/* The type of a function used to deallocate any resources associated 6260484Sobrien with the value. */ 63218822Sdimtypedef void (*splay_tree_delete_value_fn) (splay_tree_value); 6460484Sobrien 6560484Sobrien/* The type of a function used to iterate over the tree. */ 66218822Sdimtypedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); 6760484Sobrien 68104834Sobrien/* The type of a function used to allocate memory for tree root and 69104834Sobrien node structures. The first argument is the number of bytes needed; 70104834Sobrien the second is a data pointer the splay tree functions pass through 71104834Sobrien to the allocator. This function must never return zero. */ 72218822Sdimtypedef void *(*splay_tree_allocate_fn) (int, void *); 73104834Sobrien 74104834Sobrien/* The type of a function used to free memory allocated using the 75104834Sobrien corresponding splay_tree_allocate_fn. The first argument is the 76104834Sobrien memory to be freed; the latter is a data pointer the splay tree 77104834Sobrien functions pass through to the freer. */ 78218822Sdimtypedef void (*splay_tree_deallocate_fn) (void *, void *); 79104834Sobrien 8060484Sobrien/* The nodes in the splay tree. */ 81130561Sobrienstruct splay_tree_node_s GTY(()) 8260484Sobrien{ 8360484Sobrien /* The key. */ 84218822Sdim splay_tree_key GTY ((use_param1)) key; 8560484Sobrien 8660484Sobrien /* The value. */ 87218822Sdim splay_tree_value GTY ((use_param2)) value; 8860484Sobrien 8960484Sobrien /* The left and right children, respectively. */ 90218822Sdim splay_tree_node GTY ((use_params)) left; 91218822Sdim splay_tree_node GTY ((use_params)) right; 9260484Sobrien}; 9360484Sobrien 9460484Sobrien/* The splay tree itself. */ 95130561Sobrienstruct splay_tree_s GTY(()) 9660484Sobrien{ 9760484Sobrien /* The root of the tree. */ 98218822Sdim splay_tree_node GTY ((use_params)) root; 9960484Sobrien 10060484Sobrien /* The comparision function. */ 10160484Sobrien splay_tree_compare_fn comp; 10260484Sobrien 10360484Sobrien /* The deallocate-key function. NULL if no cleanup is necessary. */ 10460484Sobrien splay_tree_delete_key_fn delete_key; 10560484Sobrien 10660484Sobrien /* The deallocate-value function. NULL if no cleanup is necessary. */ 10760484Sobrien splay_tree_delete_value_fn delete_value; 108104834Sobrien 109104834Sobrien /* Allocate/free functions, and a data pointer to pass to them. */ 110104834Sobrien splay_tree_allocate_fn allocate; 111104834Sobrien splay_tree_deallocate_fn deallocate; 112218822Sdim void * GTY((skip)) allocate_data; 113104834Sobrien 114130561Sobrien}; 115130561Sobrientypedef struct splay_tree_s *splay_tree; 11660484Sobrien 117218822Sdimextern splay_tree splay_tree_new (splay_tree_compare_fn, 118218822Sdim splay_tree_delete_key_fn, 119218822Sdim splay_tree_delete_value_fn); 120218822Sdimextern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, 121218822Sdim splay_tree_delete_key_fn, 122104834Sobrien splay_tree_delete_value_fn, 123218822Sdim splay_tree_allocate_fn, 124218822Sdim splay_tree_deallocate_fn, 125218822Sdim void *); 126218822Sdimextern void splay_tree_delete (splay_tree); 127218822Sdimextern splay_tree_node splay_tree_insert (splay_tree, 128218822Sdim splay_tree_key, 129218822Sdim splay_tree_value); 130218822Sdimextern void splay_tree_remove (splay_tree, splay_tree_key); 131218822Sdimextern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key); 132218822Sdimextern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key); 133218822Sdimextern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key); 134218822Sdimextern splay_tree_node splay_tree_max (splay_tree); 135218822Sdimextern splay_tree_node splay_tree_min (splay_tree); 136218822Sdimextern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); 137218822Sdimextern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); 138218822Sdimextern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); 13960484Sobrien 14060484Sobrien#ifdef __cplusplus 14160484Sobrien} 14260484Sobrien#endif /* __cplusplus */ 14360484Sobrien 14460484Sobrien#endif /* _SPLAY_TREE_H */ 145