1130803Smarcel/* A splay-tree datatype. 2130803Smarcel Copyright 1998, 1999, 2000, 2002 Free Software Foundation, Inc. 3130803Smarcel Contributed by Mark Mitchell (mark@markmitchell.com). 4130803Smarcel 5130803SmarcelThis file is part of GCC. 6130803Smarcel 7130803SmarcelGCC is free software; you can redistribute it and/or modify it 8130803Smarcelunder the terms of the GNU General Public License as published by 9130803Smarcelthe Free Software Foundation; either version 2, or (at your option) 10130803Smarcelany later version. 11130803Smarcel 12130803SmarcelGCC is distributed in the hope that it will be useful, but 13130803SmarcelWITHOUT ANY WARRANTY; without even the implied warranty of 14130803SmarcelMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15130803SmarcelGeneral Public License for more details. 16130803Smarcel 17130803SmarcelYou should have received a copy of the GNU General Public License 18130803Smarcelalong with GCC; see the file COPYING. If not, write to 19130803Smarcelthe Free Software Foundation, 59 Temple Place - Suite 330, 20130803SmarcelBoston, MA 02111-1307, USA. */ 21130803Smarcel 22130803Smarcel/* For an easily readable description of splay-trees, see: 23130803Smarcel 24130803Smarcel Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 25130803Smarcel Algorithms. Harper-Collins, Inc. 1991. 26130803Smarcel 27130803Smarcel The major feature of splay trees is that all basic tree operations 28130803Smarcel are amortized O(log n) time for a tree with n nodes. */ 29130803Smarcel 30130803Smarcel#ifndef _SPLAY_TREE_H 31130803Smarcel#define _SPLAY_TREE_H 32130803Smarcel 33130803Smarcel#ifdef __cplusplus 34130803Smarcelextern "C" { 35130803Smarcel#endif /* __cplusplus */ 36130803Smarcel 37130803Smarcel#include "ansidecl.h" 38130803Smarcel 39130803Smarcel#ifndef GTY 40130803Smarcel#define GTY(X) 41130803Smarcel#endif 42130803Smarcel 43130803Smarcel/* Use typedefs for the key and data types to facilitate changing 44130803Smarcel these types, if necessary. These types should be sufficiently wide 45130803Smarcel that any pointer or scalar can be cast to these types, and then 46130803Smarcel cast back, without loss of precision. */ 47130803Smarceltypedef unsigned long int splay_tree_key; 48130803Smarceltypedef unsigned long int splay_tree_value; 49130803Smarcel 50130803Smarcel/* Forward declaration for a node in the tree. */ 51130803Smarceltypedef struct splay_tree_node_s *splay_tree_node; 52130803Smarcel 53130803Smarcel/* The type of a function which compares two splay-tree keys. The 54130803Smarcel function should return values as for qsort. */ 55130803Smarceltypedef int (*splay_tree_compare_fn) PARAMS((splay_tree_key, splay_tree_key)); 56130803Smarcel 57130803Smarcel/* The type of a function used to deallocate any resources associated 58130803Smarcel with the key. */ 59130803Smarceltypedef void (*splay_tree_delete_key_fn) PARAMS((splay_tree_key)); 60130803Smarcel 61130803Smarcel/* The type of a function used to deallocate any resources associated 62130803Smarcel with the value. */ 63130803Smarceltypedef void (*splay_tree_delete_value_fn) PARAMS((splay_tree_value)); 64130803Smarcel 65130803Smarcel/* The type of a function used to iterate over the tree. */ 66130803Smarceltypedef int (*splay_tree_foreach_fn) PARAMS((splay_tree_node, void*)); 67130803Smarcel 68130803Smarcel/* The type of a function used to allocate memory for tree root and 69130803Smarcel node structures. The first argument is the number of bytes needed; 70130803Smarcel the second is a data pointer the splay tree functions pass through 71130803Smarcel to the allocator. This function must never return zero. */ 72130803Smarceltypedef PTR (*splay_tree_allocate_fn) PARAMS((int, void *)); 73130803Smarcel 74130803Smarcel/* The type of a function used to free memory allocated using the 75130803Smarcel corresponding splay_tree_allocate_fn. The first argument is the 76130803Smarcel memory to be freed; the latter is a data pointer the splay tree 77130803Smarcel functions pass through to the freer. */ 78130803Smarceltypedef void (*splay_tree_deallocate_fn) PARAMS((void *, void *)); 79130803Smarcel 80130803Smarcel/* The nodes in the splay tree. */ 81130803Smarcelstruct splay_tree_node_s GTY(()) 82130803Smarcel{ 83130803Smarcel /* The key. */ 84130803Smarcel splay_tree_key GTY ((use_param1 (""))) key; 85130803Smarcel 86130803Smarcel /* The value. */ 87130803Smarcel splay_tree_value GTY ((use_param2 (""))) value; 88130803Smarcel 89130803Smarcel /* The left and right children, respectively. */ 90130803Smarcel splay_tree_node GTY ((use_params (""))) left; 91130803Smarcel splay_tree_node GTY ((use_params (""))) right; 92130803Smarcel}; 93130803Smarcel 94130803Smarcel/* The splay tree itself. */ 95130803Smarcelstruct splay_tree_s GTY(()) 96130803Smarcel{ 97130803Smarcel /* The root of the tree. */ 98130803Smarcel splay_tree_node GTY ((use_params (""))) root; 99130803Smarcel 100130803Smarcel /* The comparision function. */ 101130803Smarcel splay_tree_compare_fn comp; 102130803Smarcel 103130803Smarcel /* The deallocate-key function. NULL if no cleanup is necessary. */ 104130803Smarcel splay_tree_delete_key_fn delete_key; 105130803Smarcel 106130803Smarcel /* The deallocate-value function. NULL if no cleanup is necessary. */ 107130803Smarcel splay_tree_delete_value_fn delete_value; 108130803Smarcel 109130803Smarcel /* Allocate/free functions, and a data pointer to pass to them. */ 110130803Smarcel splay_tree_allocate_fn allocate; 111130803Smarcel splay_tree_deallocate_fn deallocate; 112130803Smarcel PTR GTY((skip (""))) allocate_data; 113130803Smarcel 114130803Smarcel}; 115130803Smarceltypedef struct splay_tree_s *splay_tree; 116130803Smarcel 117130803Smarcelextern splay_tree splay_tree_new PARAMS((splay_tree_compare_fn, 118130803Smarcel splay_tree_delete_key_fn, 119130803Smarcel splay_tree_delete_value_fn)); 120130803Smarcelextern splay_tree splay_tree_new_with_allocator 121130803Smarcel PARAMS((splay_tree_compare_fn, 122130803Smarcel splay_tree_delete_key_fn, 123130803Smarcel splay_tree_delete_value_fn, 124130803Smarcel splay_tree_allocate_fn, 125130803Smarcel splay_tree_deallocate_fn, 126130803Smarcel void *)); 127130803Smarcelextern void splay_tree_delete PARAMS((splay_tree)); 128130803Smarcelextern splay_tree_node splay_tree_insert 129130803Smarcel PARAMS((splay_tree, 130130803Smarcel splay_tree_key, 131130803Smarcel splay_tree_value)); 132130803Smarcelextern void splay_tree_remove PARAMS((splay_tree, 133130803Smarcel splay_tree_key)); 134130803Smarcelextern splay_tree_node splay_tree_lookup 135130803Smarcel PARAMS((splay_tree, 136130803Smarcel splay_tree_key)); 137130803Smarcelextern splay_tree_node splay_tree_predecessor 138130803Smarcel PARAMS((splay_tree, 139130803Smarcel splay_tree_key)); 140130803Smarcelextern splay_tree_node splay_tree_successor 141130803Smarcel PARAMS((splay_tree, 142130803Smarcel splay_tree_key)); 143130803Smarcelextern splay_tree_node splay_tree_max 144130803Smarcel PARAMS((splay_tree)); 145130803Smarcelextern splay_tree_node splay_tree_min 146130803Smarcel PARAMS((splay_tree)); 147130803Smarcelextern int splay_tree_foreach PARAMS((splay_tree, 148130803Smarcel splay_tree_foreach_fn, 149130803Smarcel void*)); 150130803Smarcelextern int splay_tree_compare_ints PARAMS((splay_tree_key, 151130803Smarcel splay_tree_key)); 152130803Smarcelextern int splay_tree_compare_pointers PARAMS((splay_tree_key, 153130803Smarcel splay_tree_key)); 154130803Smarcel 155130803Smarcel#ifdef __cplusplus 156130803Smarcel} 157130803Smarcel#endif /* __cplusplus */ 158130803Smarcel 159130803Smarcel#endif /* _SPLAY_TREE_H */ 160