template<typename KeyId, typename Value, typename Traits>
class hash_map< KeyId, Value, Traits >
A type-safe hash table template.
Copyright (C) 2012-2025 Free Software Foundation, Inc.
Contributed by Lawrence Crowl <crowl@google.com>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>.
This file implements a typed hash table.
The implementation borrows from libiberty's htab_t in hashtab.h.
INTRODUCTION TO TYPES
Users of the hash table generally need to be aware of three types.
1. The type being placed into the hash table. This type is called
the value type.
2. The type used to describe how to handle the value type within
the hash table. This descriptor type provides the hash table with
several things.
- A typedef named 'value_type' to the value type (from above).
Provided a suitable Descriptor class it may be a user-defined,
non-POD type.
- A static member function named 'hash' that takes a value_type
(or 'const value_type &') and returns a hashval_t value.
- A typedef named 'compare_type' that is used to test when a value
is found. This type is the comparison type. Usually, it will be
the same as value_type and may be a user-defined, non-POD type.
If it is not the same type, you must generally explicitly compute
hash values and pass them to the hash table.
- A static member function named 'equal' that takes a value_type
and a compare_type, and returns a bool. Both arguments can be
const references.
- A static function named 'remove' that takes an value_type pointer
and frees the memory allocated by it. This function is used when
individual elements of the table need to be disposed of (e.g.,
when deleting a hash table, removing elements from the table, etc).
- An optional static function named 'keep_cache_entry'. This
function is provided only for garbage-collected elements that
are not marked by the normal gc mark pass. It describes what
what should happen to the element at the end of the gc mark phase.
The return value should be:
- 0 if the element should be deleted
- 1 if the element should be kept and needs to be marked
- -1 if the element should be kept and is already marked.
Returning -1 rather than 1 is purely an optimization.
3. The type of the hash table itself. (More later.)
In very special circumstances, users may need to know about a fourth type.
4. The template type used to describe how hash table memory
is allocated. This type is called the allocator type. It is
parameterized on the value type. It provides two functions:
- A static member function named 'data_alloc'. This function
allocates the data elements in the table.
- A static member function named 'data_free'. This function
deallocates the data elements in the table.
Hash table are instantiated with two type arguments.
* The descriptor type, (2) above.
* The allocator type, (4) above. In general, you will not need to
provide your own allocator type. By default, hash tables will use
the class template xcallocator, which uses malloc/free for allocation.
DEFINING A DESCRIPTOR TYPE
The first task in using the hash table is to describe the element type.
We compose this into a few steps.
1. Decide on a removal policy for values stored in the table.
hash-traits.h provides class templates for the four most common
policies:
* typed_free_remove implements the static 'remove' member function
by calling free().
* typed_noop_remove implements the static 'remove' member function
by doing nothing.
* ggc_remove implements the static 'remove' member by doing nothing,
but instead provides routines for gc marking and for PCH streaming.
Use this for garbage-collected data that needs to be preserved across
collections.
* ggc_cache_remove is like ggc_remove, except that it does not
mark the entries during the normal gc mark phase. Instead it
uses 'keep_cache_entry' (described above) to keep elements that
were not collected and delete those that were. Use this for
garbage-collected caches that should not in themselves stop
the data from being collected.
You can use these policies by simply deriving the descriptor type
from one of those class template, with the appropriate argument.
Otherwise, you need to write the static 'remove' member function
in the descriptor class.
2. Choose a hash function. Write the static 'hash' member function.
3. Decide whether the lookup function should take as input an object
of type value_type or something more restricted. Define compare_type
accordingly.
4. Choose an equality testing function 'equal' that compares a value_type
and a compare_type.
If your elements are pointers, it is usually easiest to start with one
of the generic pointer descriptors described below and override the bits
you need to change.
AN EXAMPLE DESCRIPTOR TYPE
Suppose you want to put some_type into the hash table. You could define
the descriptor type as follows.
struct some_type_hasher : nofree_ptr_hash <some_type>
// Deriving from nofree_ptr_hash means that we get a 'remove' that does
// nothing. This choice is good for raw values.
{
static inline hashval_t hash (const value_type *);
static inline bool equal (const value_type *, const compare_type *);
};
inline hashval_t
some_type_hasher::hash (const value_type *e)
{ ... compute and return a hash value for E ... }
inline bool
some_type_hasher::equal (const value_type *p1, const compare_type *p2)
{ ... compare P1 vs P2. Return true if they are the 'same' ... }
AN EXAMPLE HASH_TABLE DECLARATION
To instantiate a hash table for some_type:
hash_table <some_type_hasher> some_type_hash_table;
There is no need to mention some_type directly, as the hash table will
obtain it using some_type_hasher::value_type.
You can then use any of the functions in hash_table's public interface.
See hash_table for details. The interface is very similar to libiberty's
htab_t.
If a hash table is used only in some rare cases, it is possible
to construct the hash_table lazily before first use. This is done
through:
hash_table <some_type_hasher, true> some_type_hash_table;
which will cause whatever methods actually need the allocated entries
array to allocate it later.
EASY DESCRIPTORS FOR POINTERS
There are four descriptors for pointer elements, one for each of
the removal policies above:
* nofree_ptr_hash (based on typed_noop_remove)
* free_ptr_hash (based on typed_free_remove)
* ggc_ptr_hash (based on ggc_remove)
* ggc_cache_ptr_hash (based on ggc_cache_remove)
These descriptors hash and compare elements by their pointer value,
rather than what they point to. So, to instantiate a hash table over
pointers to whatever_type, without freeing the whatever_types, use:
hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
HASH TABLE ITERATORS
The hash table provides standard C++ iterators. For example, consider a
hash table of some_info. We wish to consume each element of the table:
extern void consume (some_info *);
We define a convenience typedef and the hash table:
typedef hash_table <some_info_hasher> info_table_type;
info_table_type info_table;
Then we write the loop in typical C++ style:
for (info_table_type::iterator iter = info_table.begin ();
iter != info_table.end ();
++iter)
if ((*iter).status == INFO_READY)
consume (&*iter);
Or with common sub-expression elimination:
for (info_table_type::iterator iter = info_table.begin ();
iter != info_table.end ();
++iter)
{
some_info &elem = *iter;
if (elem.status == INFO_READY)
consume (&elem);
}
One can also use a more typical GCC style:
typedef some_info *some_info_p;
some_info *elem_ptr;
info_table_type::iterator iter;
FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
if (elem_ptr->status == INFO_READY)
consume (elem_ptr);
A memory statistics tracking infrastructure.
Copyright (C) 2015-2025 Free Software Foundation, Inc.
Contributed by Martin Liska <mliska@suse.cz>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>.
Forward declaration.