Warning: That file was not part of the compilation database. It may have many parsing errors.

1/* A typesafe wrapper around libiberty's splay-tree.h.
2 Copyright (C) 2015-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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. */
26template <typename KEY_TYPE, typename VALUE_TYPE>
27class 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
72template <typename KEY_TYPE, typename VALUE_TYPE>
73inline 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
85template <typename KEY_TYPE, typename VALUE_TYPE>
86inline 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
95template <typename KEY_TYPE, typename VALUE_TYPE>
96inline VALUE_TYPE
97typed_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
106template <typename KEY_TYPE, typename VALUE_TYPE>
107inline VALUE_TYPE
108typed_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
117template <typename KEY_TYPE, typename VALUE_TYPE>
118inline VALUE_TYPE
119typed_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
129template <typename KEY_TYPE, typename VALUE_TYPE>
130inline void
131typed_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
141template <typename KEY_TYPE, typename VALUE_TYPE>
142inline VALUE_TYPE
143typed_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
150template <typename KEY_TYPE, typename VALUE_TYPE>
151inline VALUE_TYPE
152typed_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
162template <typename KEY_TYPE, typename VALUE_TYPE>
163inline int
164typed_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
174template <typename KEY_TYPE, typename VALUE_TYPE>
175int
176typed_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. */
187template <typename KEY_TYPE, typename VALUE_TYPE>
188inline VALUE_TYPE
189typed_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 */
198

Warning: That file was not part of the compilation database. It may have many parsing errors.