#include <hash-map.h>

Collaboration diagram for hash_map< KeyId, Value, Traits >:

Data Structures
struct	hash_entry

class	iterator

Public Member Functions
	hash_map (size_t n=default_hash_map_size, bool ggc=false, bool sanitize_eq_and_hash=true, bool gather_mem_stats=GATHER_STATISTICS CXX_MEM_STAT_INFO)

	hash_map (const hash_map &h, bool ggc=false, bool sanitize_eq_and_hash=true, bool gather_mem_stats=GATHER_STATISTICS CXX_MEM_STAT_INFO)

bool	put (const Key &k, const Value &v)

Value *	get (const Key &k)

Value &	get_or_insert (const Key &k, bool *existed=NULL)

void	remove (const Key &k)

template<typename Arg , bool(*)(const typename Traits::key_type &, const Value &, Arg) f>
void	traverse (Arg a) const

template<typename Arg , bool()(const typename Traits::key_type &, Value , Arg) f>
void	traverse (Arg a) const

size_t	elements () const

void	empty ()

bool	is_empty () const

iterator	begin () const

iterator	end () const

Static Public Member Functions
static hash_map *	create_ggc (size_t size=default_hash_map_size, bool gather_mem_stats=GATHER_STATISTICS CXX_MEM_STAT_INFO)

Private Types
typedef Traits::key_type	Key

Private Attributes
hash_table< hash_entry >	m_table

Friends
template<typename T , typename U , typename V >
void	gt_ggc_mx (hash_map< T, U, V > *)

template<typename T , typename U , typename V >
void	gt_pch_nx (hash_map< T, U, V > *)

template<typename T , typename U , typename V >
void	gt_pch_nx (hash_map< T, U, V > , gt_pointer_operator, void )

template<typename T , typename U , typename V >
void	gt_cleare_cache (hash_map< T, U, V > *)

Detailed Description

template<typename KeyId, typename Value, typename Traits>
class hash_map< KeyId, Value, Traits >

A type-safe hash table template.
   Copyright (C) 2012-2024 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-2024 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.

Member Typedef Documentation

◆ Key

template<typename KeyId , typename Value , typename Traits >

typedef Traits::key_type hash_map< KeyId, Value, Traits >::Key

private

Constructor & Destructor Documentation

◆ hash_map() [1/2]

template<typename KeyId , typename Value , typename Traits >

hash_map< KeyId, Value, Traits >::hash_map	(	size_t	n = default_hash_map_size,
		bool	ggc = false,
		bool	sanitize_eq_and_hash = true,
		bool	gather_mem_stats = GATHER_STATISTICS CXX_MEM_STAT_INFO )

inlineexplicit

◆ hash_map() [2/2]

template<typename KeyId , typename Value , typename Traits >

hash_map< KeyId, Value, Traits >::hash_map	(	const hash_map< KeyId, Value, Traits > &	h,
		bool	ggc = false,
		bool	sanitize_eq_and_hash = true,
		bool	gather_mem_stats = GATHER_STATISTICS CXX_MEM_STAT_INFO )

inlineexplicit

Member Function Documentation

◆ begin()

template<typename KeyId , typename Value , typename Traits >

iterator hash_map< KeyId, Value, Traits >::begin ( ) const

inline

References hash_map< KeyId, Value, Traits >::m_table.

Referenced by consolidation_map< T >::begin(), ana::sm_state_map::begin(), ana::region_to_value_map::begin(), ana::binding_map::begin(), ana::store::begin(), dump_strlen_info(), ana::store::for_each_binding(), ana::store::for_each_cluster(), consolidation_map< T >::~consolidation_map(), and json::object::~object().

◆ create_ggc()

template<typename KeyId , typename Value , typename Traits >

static hash_map * hash_map< KeyId, Value, Traits >::create_ggc	(	size_t	size = default_hash_map_size,
		bool	gather_mem_stats = GATHER_STATISTICS CXX_MEM_STAT_INFO )