splay-tree.h revision 302408
1259701Sdim/* A splay-tree datatype. 2259701Sdim Copyright 1998, 1999, 2000, 2002 Free Software Foundation, Inc. 3259701Sdim Contributed by Mark Mitchell (mark@markmitchell.com). 4259701Sdim 5259701SdimThis file is part of GCC. 6259701Sdim 7259701SdimGCC is free software; you can redistribute it and/or modify it 8259701Sdimunder the terms of the GNU General Public License as published by 9259701Sdimthe Free Software Foundation; either version 2, or (at your option) 10259701Sdimany later version. 11259701Sdim 12259701SdimGCC is distributed in the hope that it will be useful, but 13259701SdimWITHOUT ANY WARRANTY; without even the implied warranty of 14259701SdimMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15259701SdimGeneral Public License for more details. 16259701Sdim 17259701SdimYou should have received a copy of the GNU General Public License 18259701Sdimalong with GCC; see the file COPYING. If not, write to 19259701Sdimthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20259701SdimBoston, MA 02110-1301, USA. */ 21259701Sdim 22259701Sdim/* For an easily readable description of splay-trees, see: 23259701Sdim 24259701Sdim Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 25259701Sdim Algorithms. Harper-Collins, Inc. 1991. 26259701Sdim 27259701Sdim The major feature of splay trees is that all basic tree operations 28259701Sdim are amortized O(log n) time for a tree with n nodes. */ 29259701Sdim 30259701Sdim#ifndef _SPLAY_TREE_H 31259701Sdim#define _SPLAY_TREE_H 32259701Sdim 33259701Sdim#ifdef __cplusplus 34259701Sdimextern "C" { 35259701Sdim#endif /* __cplusplus */ 36259701Sdim 37259701Sdim#include "ansidecl.h" 38259701Sdim 39259701Sdim#ifndef GTY 40259701Sdim#define GTY(X) 41259701Sdim#endif 42259701Sdim 43259701Sdim/* Use typedefs for the key and data types to facilitate changing 44259701Sdim these types, if necessary. These types should be sufficiently wide 45259701Sdim that any pointer or scalar can be cast to these types, and then 46259701Sdim cast back, without loss of precision. */ 47259701Sdimtypedef unsigned long int splay_tree_key; 48259701Sdimtypedef unsigned long int splay_tree_value; 49259701Sdim 50259701Sdim/* Forward declaration for a node in the tree. */ 51259701Sdimtypedef struct splay_tree_node_s *splay_tree_node; 52259701Sdim 53259701Sdim/* The type of a function which compares two splay-tree keys. The 54259701Sdim function should return values as for qsort. */ 55259701Sdimtypedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); 56259701Sdim 57259701Sdim/* The type of a function used to deallocate any resources associated 58259701Sdim with the key. */ 59259701Sdimtypedef void (*splay_tree_delete_key_fn) (splay_tree_key); 60259701Sdim 61259701Sdim/* The type of a function used to deallocate any resources associated 62259701Sdim with the value. */ 63259701Sdimtypedef void (*splay_tree_delete_value_fn) (splay_tree_value); 64259701Sdim 65259701Sdim/* The type of a function used to iterate over the tree. */ 66259701Sdimtypedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); 67259701Sdim 68259701Sdim/* The type of a function used to allocate memory for tree root and 69259701Sdim node structures. The first argument is the number of bytes needed; 70259701Sdim the second is a data pointer the splay tree functions pass through 71259701Sdim to the allocator. This function must never return zero. */ 72259701Sdimtypedef void *(*splay_tree_allocate_fn) (int, void *); 73259701Sdim 74259701Sdim/* The type of a function used to free memory allocated using the 75259701Sdim corresponding splay_tree_allocate_fn. The first argument is the 76259701Sdim memory to be freed; the latter is a data pointer the splay tree 77259701Sdim functions pass through to the freer. */ 78259701Sdimtypedef void (*splay_tree_deallocate_fn) (void *, void *); 79259701Sdim 80259701Sdim/* The nodes in the splay tree. */ 81259701Sdimstruct splay_tree_node_s GTY(()) 82259701Sdim{ 83259701Sdim /* The key. */ 84259701Sdim splay_tree_key GTY ((use_param1)) key; 85259701Sdim 86259701Sdim /* The value. */ 87259701Sdim splay_tree_value GTY ((use_param2)) value; 88259701Sdim 89259701Sdim /* The left and right children, respectively. */ 90259701Sdim splay_tree_node GTY ((use_params)) left; 91259701Sdim splay_tree_node GTY ((use_params)) right; 92259701Sdim}; 93259701Sdim 94259701Sdim/* The splay tree itself. */ 95259701Sdimstruct splay_tree_s GTY(()) 96259701Sdim{ 97259701Sdim /* The root of the tree. */ 98259701Sdim splay_tree_node GTY ((use_params)) root; 99259701Sdim 100259701Sdim /* The comparision function. */ 101259701Sdim splay_tree_compare_fn comp; 102259701Sdim 103259701Sdim /* The deallocate-key function. NULL if no cleanup is necessary. */ 104259701Sdim splay_tree_delete_key_fn delete_key; 105259701Sdim 106259701Sdim /* The deallocate-value function. NULL if no cleanup is necessary. */ 107259701Sdim splay_tree_delete_value_fn delete_value; 108259701Sdim 109259701Sdim /* Allocate/free functions, and a data pointer to pass to them. */ 110259701Sdim splay_tree_allocate_fn allocate; 111259701Sdim splay_tree_deallocate_fn deallocate; 112259701Sdim void * GTY((skip)) allocate_data; 113259701Sdim 114259701Sdim}; 115259701Sdimtypedef struct splay_tree_s *splay_tree; 116259701Sdim 117259701Sdimextern splay_tree splay_tree_new (splay_tree_compare_fn, 118259701Sdim splay_tree_delete_key_fn, 119259701Sdim splay_tree_delete_value_fn); 120259701Sdimextern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, 121259701Sdim splay_tree_delete_key_fn, 122259701Sdim splay_tree_delete_value_fn, 123259701Sdim splay_tree_allocate_fn, 124259701Sdim splay_tree_deallocate_fn, 125259701Sdim void *); 126259701Sdimextern void splay_tree_delete (splay_tree); 127259701Sdimextern splay_tree_node splay_tree_insert (splay_tree, 128259701Sdim splay_tree_key, 129259701Sdim splay_tree_value); 130259701Sdimextern void splay_tree_remove (splay_tree, splay_tree_key); 131259701Sdimextern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key); 132259701Sdimextern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key); 133259701Sdimextern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key); 134259701Sdimextern splay_tree_node splay_tree_max (splay_tree); 135259701Sdimextern splay_tree_node splay_tree_min (splay_tree); 136259701Sdimextern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); 137259701Sdimextern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); 138259701Sdimextern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); 139259701Sdim 140259701Sdim#ifdef __cplusplus 141259701Sdim} 142259701Sdim#endif /* __cplusplus */ 143259701Sdim 144259701Sdim#endif /* _SPLAY_TREE_H */ 145259701Sdim