1 /* Definitions for C++ name lookup routines.
2 Copyright (C) 2003 Free Software Foundation, Inc.
3 Contributed by Gabriel Dos Reis <gdr@integrable-solutions.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
28 #include "name-lookup.h"
31 /* Compute the chain index of a binding_entry given the HASH value of its
32 name and the total COUNT of chains. COUNT is assumed to be a power
34 #define ENTRY_INDEX(HASH, COUNT) (((HASH) >> 3) & ((COUNT) - 1))
36 /* A free list of "binding_entry"s awaiting for re-use. */
37 static GTY((deletable(""))) binding_entry free_binding_entry = NULL;
39 /* Create a binding_entry object for (NAME, TYPE). */
40 static inline binding_entry
41 binding_entry_make (tree name, tree type)
45 if (free_binding_entry)
47 entry = free_binding_entry;
48 free_binding_entry = entry->chain;
51 entry = ggc_alloc (sizeof (struct binding_entry_s));
60 /* Put ENTRY back on the free list. */
62 binding_entry_free (binding_entry entry)
64 entry->chain = free_binding_entry;
65 free_binding_entry = entry;
68 /* The datatype used to implement the mapping from names to types at
70 struct binding_table_s GTY(())
72 /* Array of chains of "binding_entry"s */
73 binding_entry * GTY((length ("%h.chain_count"))) chain;
75 /* The number of chains in this table. This is the length of the
76 the member "chain" considered as an array. */
79 /* Number of "binding_entry"s in this table. */
83 /* Construct TABLE with an initial CHAIN_COUNT. */
85 binding_table_construct (binding_table table, size_t chain_count)
87 table->chain_count = chain_count;
88 table->entry_count = 0;
89 table->chain = ggc_alloc_cleared
90 (table->chain_count * sizeof (binding_entry));
93 /* Free TABLE by making its entries ready for reuse. */
95 binding_table_free (binding_table table)
101 for (i = 0; i < table->chain_count; ++i)
103 binding_entry temp = table->chain[i];
106 binding_entry entry = temp;
109 binding_entry_free (entry);
111 table->chain[i] = temp;
113 table->entry_count = 0;
116 /* Allocate a table with CHAIN_COUNT, assumed to be a power of two. */
118 binding_table_new (size_t chain_count)
120 binding_table table = ggc_alloc (sizeof (struct binding_table_s));
122 binding_table_construct (table, chain_count);
126 /* Expand TABLE to twice its current chain_count. */
128 binding_table_expand (binding_table table)
130 const size_t old_chain_count = table->chain_count;
131 const size_t old_entry_count = table->entry_count;
132 const size_t new_chain_count = 2 * old_chain_count;
133 binding_entry *old_chains = table->chain;
136 binding_table_construct (table, new_chain_count);
137 for (i = 0; i < old_chain_count; ++i)
139 binding_entry entry = old_chains[i];
140 for (; entry != NULL; entry = old_chains[i])
142 const unsigned int hash = IDENTIFIER_HASH_VALUE (entry->name);
143 const size_t j = ENTRY_INDEX (hash, new_chain_count);
145 old_chains[i] = entry->chain;
146 entry->chain = table->chain[j];
147 table->chain[j] = entry;
150 table->entry_count = old_entry_count;
153 /* Insert a binding for NAME to TYPe into TABLE. */
155 binding_table_insert (binding_table table, tree name, tree type)
157 const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
158 const size_t i = ENTRY_INDEX (hash, table->chain_count);
159 binding_entry entry = binding_entry_make (name, type);
161 entry->chain = table->chain[i];
162 table->chain[i] = entry;
163 ++table->entry_count;
165 if (3 * table->chain_count < 5 * table->entry_count)
166 binding_table_expand (table);
169 /* Return the binding_entry, if any, that maps NAME. */
171 binding_table_find (binding_table table, tree name)
173 const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
174 binding_entry entry = table->chain[ENTRY_INDEX (hash, table->chain_count)];
176 while (entry != NULL && entry->name != name)
177 entry = entry->chain;
182 /* Return the binding_entry, if any, that maps name to an anonymous type. */
184 binding_table_find_anon_type (binding_table table, tree name)
186 const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
187 binding_entry entry = table->chain[ENTRY_INDEX (hash, table->chain_count)];
189 while (entry != NULL && TYPE_IDENTIFIER (entry->type) != name)
190 entry = entry->chain;
192 return entry ? entry->type : NULL;
195 /* Return the binding_entry, if any, that has TYPE as target. If NAME
196 is non-null, then set the domain and rehash that entry. */
198 binding_table_reverse_maybe_remap (binding_table table, tree type, tree name)
200 const size_t chain_count = table->chain_count;
201 binding_entry entry = NULL;
202 binding_entry *p = NULL;
205 for (i = 0; i < chain_count && entry == NULL; ++i)
207 p = &table->chain[i];
208 while (*p != NULL && entry == NULL)
209 if ((*p)->type == type)
215 if (entry != NULL && name != NULL && entry->name != name)
217 /* Remove the bucket from the previous chain. */
220 /* Remap the name type to type. */
221 i = ENTRY_INDEX (IDENTIFIER_HASH_VALUE (name), chain_count);
222 entry->chain = table->chain[i];
224 table->chain[i] = entry;
230 /* Remove from TABLE all entries that map to anonymous enums or
233 binding_table_remove_anonymous_types (binding_table table)
235 const size_t chain_count = table->chain_count;
238 for (i = 0; i < chain_count; ++i)
240 binding_entry *p = &table->chain[i];
243 if (ANON_AGGRNAME_P ((*p)->name))
245 binding_entry e = *p;
247 --table->entry_count;
248 binding_entry_free (e);
255 /* Apply PROC -- with DATA -- to all entries in TABLE. */
257 binding_table_foreach (binding_table table, bt_foreach_proc proc, void *data)
259 const size_t chain_count = table->chain_count;
262 for (i = 0; i < chain_count; ++i)
264 binding_entry entry = table->chain[i];
265 for (; entry != NULL; entry = entry->chain)
271 /* A free list of "cxx_binding"s, connected by their PREVIOUS. */
272 static GTY((deletable (""))) cxx_binding *free_bindings;
274 /* (GC)-allocate a binding object with VALUE and TYPE member initialized. */
276 cxx_binding_make (tree value, tree type)
278 cxx_binding *binding;
281 binding = free_bindings;
282 free_bindings = binding->previous;
285 binding = ggc_alloc (sizeof (cxx_binding));
287 binding->value = value;
288 binding->type = type;
289 binding->previous = NULL;
294 /* Put BINDING back on the free list. */
296 cxx_binding_free (cxx_binding *binding)
298 binding->previous = free_bindings;
299 free_bindings = binding;
302 /* Return (from the stack of) the BINDING, if any, establihsed at SCOPE. */
304 static inline cxx_binding *
305 find_binding (cxx_scope *scope, cxx_binding *binding)
307 timevar_push (TV_NAME_LOOKUP);
309 for (; binding != NULL; binding = binding->previous)
310 if (BINDING_SCOPE (binding) == scope)
311 POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, binding);
313 POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, (cxx_binding *)0);
316 /* Return the binding for NAME in SCOPE, if any. Otherwise, return NULL. */
318 cxx_scope_find_binding_for_name (cxx_scope *scope, tree name)
320 cxx_binding *b = IDENTIFIER_NAMESPACE_BINDINGS (name);
323 /* Fold-in case where NAME is used only once. */
324 if (scope == BINDING_SCOPE (b) && b->previous == NULL)
326 return find_binding (scope, b);
331 /* Always returns a binding for name in scope. If no binding is
332 found, make a new one. */
335 binding_for_name (cxx_scope *scope, tree name)
339 result = cxx_scope_find_binding_for_name (scope, name);
342 /* Not found, make a new one. */
343 result = cxx_binding_make (NULL, NULL);
344 result->previous = IDENTIFIER_NAMESPACE_BINDINGS (name);
345 BINDING_SCOPE (result) = scope;
346 result->is_local = false;
347 result->value_is_inherited = false;
348 IDENTIFIER_NAMESPACE_BINDINGS (name) = result;
352 /* Namespace-scope manipulation routines. */
354 /* Return the binding value for name in scope. */
357 namespace_binding (tree name, tree scope)
359 cxx_binding *binding;
362 scope = global_namespace;
363 scope = ORIGINAL_NAMESPACE (scope);
364 binding = cxx_scope_find_binding_for_name (NAMESPACE_LEVEL (scope), name);
366 return binding ? binding->value : NULL_TREE;
369 /* Set the binding value for name in scope. */
372 set_namespace_binding (tree name, tree scope, tree val)
376 timevar_push (TV_NAME_LOOKUP);
377 if (scope == NULL_TREE)
378 scope = global_namespace;
379 b = binding_for_name (NAMESPACE_LEVEL (scope), name);
380 if (!BINDING_VALUE (b)
381 || TREE_CODE (val) == OVERLOAD
382 || val == error_mark_node)
383 BINDING_VALUE (b) = val;
385 add_binding (b, val);
386 timevar_pop (TV_NAME_LOOKUP);
389 #include "gt-cp-name-lookup.h"