194575Sdes/* A splay-tree datatype. 294575Sdes Copyright (C) 1998-2017 Free Software Foundation, Inc. 394575Sdes Contributed by Mark Mitchell (mark@markmitchell.com). 494575Sdes 594575Sdes This file is part of GCC. 694575Sdes 794575Sdes GCC is free software; you can redistribute it and/or modify it 894575Sdes under the terms of the GNU General Public License as published by 994575Sdes the Free Software Foundation; either version 2, or (at your option) 1094575Sdes any later version. 1194575Sdes 1294575Sdes GCC is distributed in the hope that it will be useful, but 1394575Sdes WITHOUT ANY WARRANTY; without even the implied warranty of 1494575Sdes MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1594575Sdes General Public License for more details. 1694575Sdes 1794575Sdes You should have received a copy of the GNU General Public License 1894575Sdes along with GCC; see the file COPYING. If not, write to 1994575Sdes the Free Software Foundation, 51 Franklin Street - Fifth Floor, 2094575Sdes Boston, MA 02110-1301, USA. */ 2194575Sdes 2294575Sdes/* For an easily readable description of splay-trees, see: 2394575Sdes 2494575Sdes Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 2594575Sdes Algorithms. Harper-Collins, Inc. 1991. 2694575Sdes 2794575Sdes The major feature of splay trees is that all basic tree operations 2894575Sdes are amortized O(log n) time for a tree with n nodes. */ 2994575Sdes 3094575Sdes#ifndef _SPLAY_TREE_H 3194575Sdes#define _SPLAY_TREE_H 3294575Sdes 3394575Sdes#ifdef __cplusplus 3494575Sdesextern "C" { 3594575Sdes#endif /* __cplusplus */ 3694575Sdes 3794575Sdes#include "ansidecl.h" 3894575Sdes 3994575Sdes#ifdef HAVE_STDINT_H 4094575Sdes#include <stdint.h> 4194575Sdes#endif 4294575Sdes#ifdef HAVE_INTTYPES_H 4394575Sdes#include <inttypes.h> 4494575Sdes#endif 4594575Sdes 4694575Sdes/* Use typedefs for the key and data types to facilitate changing 4794575Sdes these types, if necessary. These types should be sufficiently wide 4894575Sdes that any pointer or scalar can be cast to these types, and then 4994575Sdes cast back, without loss of precision. */ 5094575Sdestypedef uintptr_t splay_tree_key; 5194575Sdestypedef uintptr_t splay_tree_value; 5294575Sdes 5394575Sdes/* Forward declaration for a node in the tree. */ 5494575Sdestypedef struct splay_tree_node_s *splay_tree_node; 5594575Sdes 5694575Sdes/* The type of a function which compares two splay-tree keys. The 5794575Sdes function should return values as for qsort. */ 5894575Sdestypedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); 5994575Sdes 6094575Sdes/* The type of a function used to deallocate any resources associated 6194575Sdes with the key. */ 6294575Sdestypedef void (*splay_tree_delete_key_fn) (splay_tree_key); 6394575Sdes 6494575Sdes/* The type of a function used to deallocate any resources associated 6594575Sdes with the value. */ 6694575Sdestypedef void (*splay_tree_delete_value_fn) (splay_tree_value); 6794575Sdes 6894575Sdes/* The type of a function used to iterate over the tree. */ 6994575Sdestypedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); 7094575Sdes 7194575Sdes/* The type of a function used to allocate memory for tree root and 7294575Sdes node structures. The first argument is the number of bytes needed; 7394575Sdes the second is a data pointer the splay tree functions pass through 7494575Sdes to the allocator. This function must never return zero. */ 7594575Sdestypedef void *(*splay_tree_allocate_fn) (int, void *); 7694575Sdes 7794575Sdes/* The type of a function used to free memory allocated using the 7894575Sdes corresponding splay_tree_allocate_fn. The first argument is the 7994575Sdes memory to be freed; the latter is a data pointer the splay tree 8094575Sdes functions pass through to the freer. */ 8194575Sdestypedef void (*splay_tree_deallocate_fn) (void *, void *); 8294575Sdes 8394575Sdes/* The nodes in the splay tree. */ 8494575Sdesstruct splay_tree_node_s { 8594575Sdes /* The key. */ 8694575Sdes splay_tree_key key; 8794575Sdes 8894575Sdes /* The value. */ 8994575Sdes splay_tree_value value; 9094575Sdes 9194575Sdes /* The left and right children, respectively. */ 9294575Sdes splay_tree_node left; 9394575Sdes splay_tree_node right; 9494575Sdes}; 9594575Sdes 9694575Sdes/* The splay tree itself. */ 9794575Sdesstruct splay_tree_s { 9894575Sdes /* The root of the tree. */ 9994575Sdes splay_tree_node root; 10094575Sdes 10194575Sdes /* The comparision function. */ 10294575Sdes splay_tree_compare_fn comp; 10394575Sdes 10494575Sdes /* The deallocate-key function. NULL if no cleanup is necessary. */ 10594575Sdes splay_tree_delete_key_fn delete_key; 10694575Sdes 10794575Sdes /* The deallocate-value function. NULL if no cleanup is necessary. */ 10894575Sdes splay_tree_delete_value_fn delete_value; 10994575Sdes 11094575Sdes /* Node allocate function. Takes allocate_data as a parameter. */ 11194575Sdes splay_tree_allocate_fn allocate; 11294575Sdes 11394575Sdes /* Free function for nodes and trees. Takes allocate_data as a parameter. */ 11494575Sdes splay_tree_deallocate_fn deallocate; 11594575Sdes 11694575Sdes /* Parameter for allocate/free functions. */ 11794575Sdes void *allocate_data; 11894575Sdes}; 11994575Sdes 12094575Sdestypedef struct splay_tree_s *splay_tree; 12194575Sdes 12294575Sdesextern splay_tree splay_tree_new (splay_tree_compare_fn, 12394575Sdes splay_tree_delete_key_fn, 12494575Sdes splay_tree_delete_value_fn); 12594575Sdesextern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, 12694575Sdes splay_tree_delete_key_fn, 12794575Sdes splay_tree_delete_value_fn, 12894575Sdes splay_tree_allocate_fn, 12994575Sdes splay_tree_deallocate_fn, 130 void *); 131extern splay_tree splay_tree_new_typed_alloc (splay_tree_compare_fn, 132 splay_tree_delete_key_fn, 133 splay_tree_delete_value_fn, 134 splay_tree_allocate_fn, 135 splay_tree_allocate_fn, 136 splay_tree_deallocate_fn, 137 void *); 138extern void splay_tree_delete (splay_tree); 139extern splay_tree_node splay_tree_insert (splay_tree, 140 splay_tree_key, 141 splay_tree_value); 142extern void splay_tree_remove (splay_tree, splay_tree_key); 143extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key); 144extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key); 145extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key); 146extern splay_tree_node splay_tree_max (splay_tree); 147extern splay_tree_node splay_tree_min (splay_tree); 148extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); 149extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); 150extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); 151 152#ifdef __cplusplus 153} 154#endif /* __cplusplus */ 155 156#endif /* _SPLAY_TREE_H */ 157