Functions
unsigned int	ceil_log2 ()
unsigned int	choose_multiplier ()
unsigned int	hash_table_higher_prime_index ()
static hashval_t	mul_mod ()
hashval_t	hash_table_mod1 ()
hashval_t	hash_table_mod2 ()

Variables
struct prime_ent const	prime_tab []

Function Documentation

unsigned int ceil_log2 ( )

@verbatim A type-safe hash table template.

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 hashtab.

Table of primes and multiplicative inverses.

   Note that these are not minimally reduced inverses.  Unlike when generating
   code to divide by a constant, we want to be able to use the same algorithm
   all the time.  All of these inverses (are implied to) have bit 32 set.

   For the record, here's the function that computed the table; it's a 
   vastly simplified version of the function of the same name from gcc.

References abort().

Referenced by alloc_use_cost_map(), choose_multiplier(), emit_case_decision_tree(), find_bswap(), and ideal_phi_node_len().

unsigned int choose_multiplier ( )

References ceil_log2(), ldexp(), and pow().

unsigned int hash_table_higher_prime_index ( )

The following function returns an index into the above table of the
   nearest prime number which is greater than N, and near a power of two.

References abort(), prime_ent::prime, and prime_tab.

Referenced by hash_table< Descriptor, Allocator >::create(), hash_table< Descriptor, Allocator >::empty(), and hash_table< Descriptor, Allocator >::expand().

hashval_t hash_table_mod1 ( )

Compute the primary table index for HASH given current prime index.

References prime_ent::inv, mul_mod(), prime_ent::prime, and prime_ent::shift.

Referenced by hash_table< Descriptor, Allocator >::find_empty_slot_for_expand(), hash_table< Descriptor, Allocator >::find_slot_with_hash(), and hash_table< Descriptor, Allocator >::find_with_hash().

hashval_t hash_table_mod2 ( )

Compute the secondary table index for HASH given current prime index.

References prime_ent::inv_m2, mul_mod(), prime_ent::prime, and prime_ent::shift.

Referenced by hash_table< Descriptor, Allocator >::find_empty_slot_for_expand(), hash_table< Descriptor, Allocator >::find_slot_with_hash(), and hash_table< Descriptor, Allocator >::find_with_hash().

static hashval_t mul_mod ( )

inlinestatic

Return X % Y using multiplicative inverse values INV and SHIFT.

   The multiplicative inverses computed above are for 32-bit types,
   and requires that we be able to compute a highpart multiply.

   FIX: I am not at all convinced that
     3 loads, 2 multiplications, 3 shifts, and 3 additions
   will be faster than
     1 load and 1 modulus
   on modern systems running a compiler.

References shift.

Referenced by hash_table_mod1(), and hash_table_mod2().

Variable Documentation

struct prime_ent const prime_tab[]

Referenced by hash_table< Descriptor, Allocator >::create(), hash_table< Descriptor, Allocator >::empty(), hash_table< Descriptor, Allocator >::expand(), and hash_table_higher_prime_index().

Functions

Variables

Function Documentation

Variable Documentation