|
111
|
1 /* A typesafe wrapper around libiberty's splay-tree.h.
|
|
|
2 Copyright (C) 2015-2017 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify it under
|
|
|
7 the terms of the GNU General Public License as published by the Free
|
|
|
8 Software Foundation; either version 3, or (at your option) any later
|
|
|
9 version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #ifndef GCC_TYPED_SPLAY_TREE_H
|
|
|
21 #define GCC_TYPED_SPLAY_TREE_H
|
|
|
22
|
|
|
23 #include "splay-tree.h"
|
|
|
24
|
|
|
25 /* Typesafe wrapper around libiberty's splay-tree.h. */
|
|
|
26 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
27 class typed_splay_tree
|
|
|
28 {
|
|
|
29 public:
|
|
|
30 typedef KEY_TYPE key_type;
|
|
|
31 typedef VALUE_TYPE value_type;
|
|
|
32
|
|
|
33 typedef int (*compare_fn) (key_type, key_type);
|
|
|
34 typedef void (*delete_key_fn) (key_type);
|
|
|
35 typedef void (*delete_value_fn) (value_type);
|
|
|
36 typedef int (*foreach_fn) (key_type, value_type, void *);
|
|
|
37
|
|
|
38 typed_splay_tree (compare_fn,
|
|
|
39 delete_key_fn,
|
|
|
40 delete_value_fn);
|
|
|
41 ~typed_splay_tree ();
|
|
|
42
|
|
|
43 value_type lookup (key_type k);
|
|
|
44 value_type predecessor (key_type k);
|
|
|
45 value_type successor (key_type k);
|
|
|
46 void insert (key_type k, value_type v);
|
|
|
47 value_type max ();
|
|
|
48 value_type min ();
|
|
|
49 int foreach (foreach_fn, void *);
|
|
|
50
|
|
|
51 private:
|
|
|
52 /* Helper type for typed_splay_tree::foreach. */
|
|
|
53 struct closure
|
|
|
54 {
|
|
|
55 closure (foreach_fn outer_cb, void *outer_user_data)
|
|
|
56 : m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {}
|
|
|
57
|
|
|
58 foreach_fn m_outer_cb;
|
|
|
59 void *m_outer_user_data;
|
|
|
60 };
|
|
|
61
|
|
|
62 static int inner_foreach_fn (splay_tree_node node, void *user_data);
|
|
|
63
|
|
|
64 static value_type node_to_value (splay_tree_node node);
|
|
|
65
|
|
|
66 private:
|
|
|
67 ::splay_tree m_inner;
|
|
|
68 };
|
|
|
69
|
|
|
70 /* Constructor for typed_splay_tree <K, V>. */
|
|
|
71
|
|
|
72 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
73 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
|
|
|
74 typed_splay_tree (compare_fn compare_fn,
|
|
|
75 delete_key_fn delete_key_fn,
|
|
|
76 delete_value_fn delete_value_fn)
|
|
|
77 {
|
|
|
78 m_inner = splay_tree_new ((splay_tree_compare_fn)compare_fn,
|
|
|
79 (splay_tree_delete_key_fn)delete_key_fn,
|
|
|
80 (splay_tree_delete_value_fn)delete_value_fn);
|
|
|
81 }
|
|
|
82
|
|
|
83 /* Destructor for typed_splay_tree <K, V>. */
|
|
|
84
|
|
|
85 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
86 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
|
|
|
87 ~typed_splay_tree ()
|
|
|
88 {
|
|
|
89 splay_tree_delete (m_inner);
|
|
|
90 }
|
|
|
91
|
|
|
92 /* Lookup KEY, returning a value if present, and NULL
|
|
|
93 otherwise. */
|
|
|
94
|
|
|
95 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
96 inline VALUE_TYPE
|
|
|
97 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
|
|
|
98 {
|
|
|
99 splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key);
|
|
|
100 return node_to_value (node);
|
|
|
101 }
|
|
|
102
|
|
|
103 /* Return the immediate predecessor of KEY, or NULL if there is no
|
|
|
104 predecessor. KEY need not be present in the tree. */
|
|
|
105
|
|
|
106 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
107 inline VALUE_TYPE
|
|
|
108 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
|
|
|
109 {
|
|
|
110 splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key);
|
|
|
111 return node_to_value (node);
|
|
|
112 }
|
|
|
113
|
|
|
114 /* Return the immediate successor of KEY, or NULL if there is no
|
|
|
115 successor. KEY need not be present in the tree. */
|
|
|
116
|
|
|
117 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
118 inline VALUE_TYPE
|
|
|
119 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k)
|
|
|
120 {
|
|
|
121 splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k);
|
|
|
122 return node_to_value (node);
|
|
|
123 }
|
|
|
124
|
|
|
125 /* Insert a new node (associating KEY with VALUE). If a
|
|
|
126 previous node with the indicated KEY exists, its data is replaced
|
|
|
127 with the new value. */
|
|
|
128
|
|
|
129 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
130 inline void
|
|
|
131 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
|
|
|
132 value_type value)
|
|
|
133 {
|
|
|
134 splay_tree_insert (m_inner,
|
|
|
135 (splay_tree_key)key,
|
|
|
136 (splay_tree_value)value);
|
|
|
137 }
|
|
|
138
|
|
|
139 /* Get the value with maximal key. */
|
|
|
140
|
|
|
141 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
142 inline VALUE_TYPE
|
|
|
143 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
|
|
|
144 {
|
|
|
145 return node_to_value (splay_tree_max (m_inner));
|
|
|
146 }
|
|
|
147
|
|
|
148 /* Get the value with minimal key. */
|
|
|
149
|
|
|
150 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
151 inline VALUE_TYPE
|
|
|
152 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
|
|
|
153 {
|
|
|
154 return node_to_value (splay_tree_min (m_inner));
|
|
|
155 }
|
|
|
156
|
|
|
157 /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node,
|
|
|
158 following an in-order traversal. If OUTER_CB ever returns a non-zero
|
|
|
159 value, the iteration ceases immediately, and the value is returned.
|
|
|
160 Otherwise, this function returns 0. */
|
|
|
161
|
|
|
162 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
163 inline int
|
|
|
164 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb,
|
|
|
165 void *outer_user_data)
|
|
|
166 {
|
|
|
167 closure c (outer_cb, outer_user_data);
|
|
|
168
|
|
|
169 return splay_tree_foreach (m_inner, inner_foreach_fn, &c);
|
|
|
170 }
|
|
|
171
|
|
|
172 /* Helper function for typed_splay_tree::foreach. */
|
|
|
173
|
|
|
174 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
175 int
|
|
|
176 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node,
|
|
|
177 void *user_data)
|
|
|
178 {
|
|
|
179 closure *c = (closure *)user_data;
|
|
|
180
|
|
|
181 return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value,
|
|
|
182 c->m_outer_user_data);
|
|
|
183 }
|
|
|
184
|
|
|
185 /* Internal function for converting from splay_tree_node to
|
|
|
186 VALUE_TYPE. */
|
|
|
187 template <typename KEY_TYPE, typename VALUE_TYPE>
|
|
|
188 inline VALUE_TYPE
|
|
|
189 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
|
|
|
190 {
|
|
|
191 if (node)
|
|
|
192 return (value_type)node->value;
|
|
|
193 else
|
|
|
194 return 0;
|
|
|
195 }
|
|
|
196
|
|
|
197 #endif /* GCC_TYPED_SPLAY_TREE_H */
|
