splay-tree.h revision 1.1
1283010Spfg/* A splay-tree datatype. 2169695Skan Copyright 1998, 1999, 2000, 2002, 2005, 2007, 2009 3169695Skan Free Software Foundation, Inc. 4169695Skan Contributed by Mark Mitchell (mark@markmitchell.com). 5169695Skan 6169695Skan This file is part of GCC. 7169695Skan 8169695Skan GCC is free software; you can redistribute it and/or modify it 9169695Skan under the terms of the GNU General Public License as published by 10169695Skan the Free Software Foundation; either version 2, or (at your option) 11169695Skan any later version. 12169695Skan 13169695Skan GCC is distributed in the hope that it will be useful, but 14169695Skan WITHOUT ANY WARRANTY; without even the implied warranty of 15169695Skan MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16169695Skan General Public License for more details. 17169695Skan 18169695Skan You should have received a copy of the GNU General Public License 19169695Skan along with GCC; see the file COPYING. If not, write to 20169695Skan the Free Software Foundation, 51 Franklin Street - Fifth Floor, 21169695Skan Boston, MA 02110-1301, USA. */ 22169695Skan 23169695Skan/* For an easily readable description of splay-trees, see: 24169695Skan 25169695Skan Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 26169695Skan Algorithms. Harper-Collins, Inc. 1991. 27169695Skan 28169695Skan The major feature of splay trees is that all basic tree operations 29169695Skan are amortized O(log n) time for a tree with n nodes. */ 30169695Skan 31169695Skan#ifndef _SPLAY_TREE_H 32169695Skan#define _SPLAY_TREE_H 33169695Skan 34169695Skan#ifdef __cplusplus 35169695Skanextern "C" { 36169695Skan#endif /* __cplusplus */ 37169695Skan 38169695Skan#include "ansidecl.h" 39169695Skan 40169695Skan#ifndef _WIN64 41169695Skan typedef unsigned long int libi_uhostptr_t; 42169695Skan typedef long int libi_shostptr_t; 43169695Skan#else 44169695Skan#ifdef __GNUC__ 45169695Skan __extension__ 46169695Skan#endif 47169695Skan typedef unsigned long long libi_uhostptr_t; 48169695Skan#ifdef __GNUC__ 49169695Skan __extension__ 50169695Skan#endif 51169695Skan typedef long long libi_shostptr_t; 52283010Spfg#endif 53283010Spfg 54283010Spfg#ifndef GTY 55169695Skan#define GTY(X) 56169695Skan#endif 57283010Spfg 58283010Spfg/* Use typedefs for the key and data types to facilitate changing 59283010Spfg these types, if necessary. These types should be sufficiently wide 60283010Spfg that any pointer or scalar can be cast to these types, and then 61283010Spfg cast back, without loss of precision. */ 62169695Skantypedef libi_uhostptr_t splay_tree_key; 63283010Spfgtypedef libi_uhostptr_t splay_tree_value; 64169695Skan 65283010Spfg/* Forward declaration for a node in the tree. */ 66283010Spfgtypedef struct splay_tree_node_s *splay_tree_node; 67169695Skan 68283010Spfg/* The type of a function which compares two splay-tree keys. The 69283010Spfg function should return values as for qsort. */ 70169695Skantypedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); 71283010Spfg 72283010Spfg/* The type of a function used to deallocate any resources associated 73283010Spfg with the key. */ 74283010Spfgtypedef void (*splay_tree_delete_key_fn) (splay_tree_key); 75283010Spfg 76169695Skan/* The type of a function used to deallocate any resources associated 77283010Spfg with the value. */ 78283010Spfgtypedef void (*splay_tree_delete_value_fn) (splay_tree_value); 79283010Spfg 80283010Spfg/* The type of a function used to iterate over the tree. */ 81283010Spfgtypedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); 82169695Skan 83283010Spfg/* The type of a function used to allocate memory for tree root and 84283010Spfg node structures. The first argument is the number of bytes needed; 85169695Skan the second is a data pointer the splay tree functions pass through 86169695Skan to the allocator. This function must never return zero. */ 87169695Skantypedef void *(*splay_tree_allocate_fn) (int, void *); 88169695Skan 89169695Skan/* The type of a function used to free memory allocated using the 90169695Skan corresponding splay_tree_allocate_fn. The first argument is the 91 memory to be freed; the latter is a data pointer the splay tree 92 functions pass through to the freer. */ 93typedef void (*splay_tree_deallocate_fn) (void *, void *); 94 95/* The nodes in the splay tree. */ 96struct GTY(()) splay_tree_node_s { 97 /* The key. */ 98 splay_tree_key GTY ((use_param1)) key; 99 100 /* The value. */ 101 splay_tree_value GTY ((use_param2)) value; 102 103 /* The left and right children, respectively. */ 104 splay_tree_node GTY ((use_params)) left; 105 splay_tree_node GTY ((use_params)) right; 106}; 107 108/* The splay tree itself. */ 109struct GTY(()) splay_tree_s { 110 /* The root of the tree. */ 111 splay_tree_node GTY ((use_params)) root; 112 113 /* The comparision function. */ 114 splay_tree_compare_fn comp; 115 116 /* The deallocate-key function. NULL if no cleanup is necessary. */ 117 splay_tree_delete_key_fn delete_key; 118 119 /* The deallocate-value function. NULL if no cleanup is necessary. */ 120 splay_tree_delete_value_fn delete_value; 121 122 /* Allocate/free functions, and a data pointer to pass to them. */ 123 splay_tree_allocate_fn allocate; 124 splay_tree_deallocate_fn deallocate; 125 void * GTY((skip)) allocate_data; 126}; 127 128typedef struct splay_tree_s *splay_tree; 129 130extern splay_tree splay_tree_new (splay_tree_compare_fn, 131 splay_tree_delete_key_fn, 132 splay_tree_delete_value_fn); 133extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, 134 splay_tree_delete_key_fn, 135 splay_tree_delete_value_fn, 136 splay_tree_allocate_fn, 137 splay_tree_deallocate_fn, 138 void *); 139extern void splay_tree_delete (splay_tree); 140extern splay_tree_node splay_tree_insert (splay_tree, 141 splay_tree_key, 142 splay_tree_value); 143extern void splay_tree_remove (splay_tree, splay_tree_key); 144extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key); 145extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key); 146extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key); 147extern splay_tree_node splay_tree_max (splay_tree); 148extern splay_tree_node splay_tree_min (splay_tree); 149extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); 150extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); 151extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); 152 153#ifdef __cplusplus 154} 155#endif /* __cplusplus */ 156 157#endif /* _SPLAY_TREE_H */ 158