splay-tree.h revision 169695
138889Sjdp/* A splay-tree datatype. 238889Sjdp Copyright 1998, 1999, 2000, 2002 Free Software Foundation, Inc. 3218822Sdim Contributed by Mark Mitchell (mark@markmitchell.com). 4218822Sdim 5218822SdimThis file is part of GCC. 6218822Sdim 7218822SdimGCC is free software; you can redistribute it and/or modify it 8218822Sdimunder the terms of the GNU General Public License as published by 938889Sjdpthe Free Software Foundation; either version 2, or (at your option) 1038889Sjdpany later version. 1138889Sjdp 1238889SjdpGCC is distributed in the hope that it will be useful, but 1338889SjdpWITHOUT ANY WARRANTY; without even the implied warranty of 1438889SjdpMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1538889SjdpGeneral Public License for more details. 1638889Sjdp 1738889SjdpYou should have received a copy of the GNU General Public License 1838889Sjdpalong with GCC; see the file COPYING. If not, write to 1938889Sjdpthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 2038889SjdpBoston, MA 02110-1301, USA. */ 2138889Sjdp 2238889Sjdp/* For an easily readable description of splay-trees, see: 23218822Sdim 24218822Sdim Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 2538889Sjdp Algorithms. Harper-Collins, Inc. 1991. 26218822Sdim 27218822Sdim The major feature of splay trees is that all basic tree operations 28218822Sdim are amortized O(log n) time for a tree with n nodes. */ 29218822Sdim 3038889Sjdp#ifndef _SPLAY_TREE_H 31218822Sdim#define _SPLAY_TREE_H 32218822Sdim 33218822Sdim#ifdef __cplusplus 34218822Sdimextern "C" { 35218822Sdim#endif /* __cplusplus */ 36218822Sdim 37218822Sdim#include "ansidecl.h" 38218822Sdim 39218822Sdim#ifndef GTY 40218822Sdim#define GTY(X) 41218822Sdim#endif 42218822Sdim 43218822Sdim/* Use typedefs for the key and data types to facilitate changing 44218822Sdim these types, if necessary. These types should be sufficiently wide 45218822Sdim that any pointer or scalar can be cast to these types, and then 46218822Sdim cast back, without loss of precision. */ 47218822Sdimtypedef unsigned long int splay_tree_key; 48218822Sdimtypedef unsigned long int splay_tree_value; 49218822Sdim 50218822Sdim/* Forward declaration for a node in the tree. */ 51218822Sdimtypedef struct splay_tree_node_s *splay_tree_node; 52218822Sdim 53218822Sdim/* The type of a function which compares two splay-tree keys. The 54218822Sdim function should return values as for qsort. */ 55218822Sdimtypedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); 56218822Sdim 57218822Sdim/* The type of a function used to deallocate any resources associated 58218822Sdim with the key. */ 59218822Sdimtypedef void (*splay_tree_delete_key_fn) (splay_tree_key); 60218822Sdim 61218822Sdim/* The type of a function used to deallocate any resources associated 62218822Sdim with the value. */ 63218822Sdimtypedef void (*splay_tree_delete_value_fn) (splay_tree_value); 64218822Sdim 65218822Sdim/* The type of a function used to iterate over the tree. */ 6638889Sjdptypedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); 6738889Sjdp 68218822Sdim/* The type of a function used to allocate memory for tree root and 6938889Sjdp node structures. The first argument is the number of bytes needed; 7038889Sjdp the second is a data pointer the splay tree functions pass through 7138889Sjdp to the allocator. This function must never return zero. */ 7238889Sjdptypedef void *(*splay_tree_allocate_fn) (int, void *); 73218822Sdim 7438889Sjdp/* The type of a function used to free memory allocated using the 7538889Sjdp corresponding splay_tree_allocate_fn. The first argument is the 76218822Sdim memory to be freed; the latter is a data pointer the splay tree 77218822Sdim functions pass through to the freer. */ 7838889Sjdptypedef void (*splay_tree_deallocate_fn) (void *, void *); 7938889Sjdp 8038889Sjdp/* The nodes in the splay tree. */ 8138889Sjdpstruct splay_tree_node_s GTY(()) 8238889Sjdp{ 8338889Sjdp /* The key. */ 84218822Sdim splay_tree_key GTY ((use_param1)) key; 85218822Sdim 86218822Sdim /* The value. */ 87218822Sdim splay_tree_value GTY ((use_param2)) value; 88218822Sdim 89218822Sdim /* The left and right children, respectively. */ 9038889Sjdp splay_tree_node GTY ((use_params)) left; 9138889Sjdp splay_tree_node GTY ((use_params)) right; 92218822Sdim}; 93218822Sdim 94218822Sdim/* The splay tree itself. */ 95218822Sdimstruct splay_tree_s GTY(()) 96218822Sdim{ 97218822Sdim /* The root of the tree. */ 98218822Sdim splay_tree_node GTY ((use_params)) root; 99218822Sdim 100218822Sdim /* The comparision function. */ 10138889Sjdp splay_tree_compare_fn comp; 10238889Sjdp 10338889Sjdp /* The deallocate-key function. NULL if no cleanup is necessary. */ 10438889Sjdp splay_tree_delete_key_fn delete_key; 10538889Sjdp 10638889Sjdp /* The deallocate-value function. NULL if no cleanup is necessary. */ 10738889Sjdp splay_tree_delete_value_fn delete_value; 108218822Sdim 109218822Sdim /* Allocate/free functions, and a data pointer to pass to them. */ 110218822Sdim splay_tree_allocate_fn allocate; 111218822Sdim splay_tree_deallocate_fn deallocate; 11260484Sobrien void * GTY((skip)) allocate_data; 113218822Sdim 11438889Sjdp}; 115218822Sdimtypedef struct splay_tree_s *splay_tree; 116218822Sdim 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, 122218822Sdim 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); 13938889Sjdp 140218822Sdim#ifdef __cplusplus 141218822Sdim} 142218822Sdim#endif /* __cplusplus */ 14338889Sjdp 144218822Sdim#endif /* _SPLAY_TREE_H */ 145218822Sdim