1
1
/* A splay-tree datatype.
2
Copyright (C) 1998 Free Software Foundation, Inc.
2
Copyright 1998, 1999, 2000, 2002 Free Software Foundation, Inc.
3
3
Contributed by Mark Mitchell (mark@markmitchell.com).
5
This file is part of GNU CC.
5
This file is part of GCC.
7
GNU CC is free software; you can redistribute it and/or modify it
7
GCC is free software; you can redistribute it and/or modify it
8
8
under the terms of the GNU General Public License as published by
9
9
the Free Software Foundation; either version 2, or (at your option)
12
GNU CC is distributed in the hope that it will be useful, but
12
GCC is distributed in the hope that it will be useful, but
13
13
WITHOUT ANY WARRANTY; without even the implied warranty of
14
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15
15
General Public License for more details.
17
17
You should have received a copy of the GNU General Public License
18
along with GNU CC; see the file COPYING. If not, write to
18
along with GCC; see the file COPYING. If not, write to
19
19
the Free Software Foundation, 59 Temple Place - Suite 330,
20
20
Boston, MA 02111-1307, USA. */
61
65
/* The type of a function used to iterate over the tree. */
62
66
typedef int (*splay_tree_foreach_fn) PARAMS((splay_tree_node, void*));
68
/* The type of a function used to allocate memory for tree root and
69
node structures. The first argument is the number of bytes needed;
70
the second is a data pointer the splay tree functions pass through
71
to the allocator. This function must never return zero. */
72
typedef PTR (*splay_tree_allocate_fn) PARAMS((int, void *));
74
/* The type of a function used to free memory allocated using the
75
corresponding splay_tree_allocate_fn. The first argument is the
76
memory to be freed; the latter is a data pointer the splay tree
77
functions pass through to the freer. */
78
typedef void (*splay_tree_deallocate_fn) PARAMS((void *, void *));
64
80
/* The nodes in the splay tree. */
65
struct splay_tree_node_s
81
struct splay_tree_node_s GTY(())
84
splay_tree_key GTY ((use_param1 (""))) key;
71
splay_tree_value value;
87
splay_tree_value GTY ((use_param2 (""))) value;
73
89
/* The left and right children, respectively. */
75
splay_tree_node right;
90
splay_tree_node GTY ((use_params (""))) left;
91
splay_tree_node GTY ((use_params (""))) right;
78
94
/* The splay tree itself. */
79
typedef struct splay_tree_s
95
struct splay_tree_s GTY(())
81
97
/* The root of the tree. */
98
splay_tree_node GTY ((use_params (""))) root;
84
100
/* The comparision function. */
85
101
splay_tree_compare_fn comp;
90
106
/* The deallocate-value function. NULL if no cleanup is necessary. */
91
107
splay_tree_delete_value_fn delete_value;
109
/* Allocate/free functions, and a data pointer to pass to them. */
110
splay_tree_allocate_fn allocate;
111
splay_tree_deallocate_fn deallocate;
112
PTR GTY((skip (""))) allocate_data;
115
typedef struct splay_tree_s *splay_tree;
94
117
extern splay_tree splay_tree_new PARAMS((splay_tree_compare_fn,
95
118
splay_tree_delete_key_fn,
96
119
splay_tree_delete_value_fn));
120
extern splay_tree splay_tree_new_with_allocator
121
PARAMS((splay_tree_compare_fn,
122
splay_tree_delete_key_fn,
123
splay_tree_delete_value_fn,
124
splay_tree_allocate_fn,
125
splay_tree_deallocate_fn,
97
127
extern void splay_tree_delete PARAMS((splay_tree));
98
128
extern splay_tree_node splay_tree_insert
99
129
PARAMS((splay_tree,
104
134
extern splay_tree_node splay_tree_lookup
105
135
PARAMS((splay_tree,
106
136
splay_tree_key));
137
extern splay_tree_node splay_tree_predecessor
140
extern splay_tree_node splay_tree_successor
143
extern splay_tree_node splay_tree_max
144
PARAMS((splay_tree));
145
extern splay_tree_node splay_tree_min
146
PARAMS((splay_tree));
107
147
extern int splay_tree_foreach PARAMS((splay_tree,
108
148
splay_tree_foreach_fn,
added
removed
include/splay-tree.h
