hash.c File Reference

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include "newgen_types.h"
#include "genC.h"
#include "newgen_include.h"
#include "newgen_hash.h"

Include dependency graph for hash.c:

Go to the source code of this file.

Data Structures
struct	hash_entry
struct	__hash_table

Macros
#define	HASH_ENTRY_FREE   ((void *) 0)
	Some predefined values for the key. More...
#define	HASH_ENTRY_FREE_FOR_PUT   ((void *) -1)
#define	END_OF_SIZE_TABLE   (0)
	Constant to find the end of the prime numbers table. More...
#define	RANK(key, size)   ((((_uint)(key)) ^ 0xfab1c0e1U)%(size))
	Hash function to get the index of the array from the key. More...
#define	HASH_INC_SIZE   (31) /**31... (yes, this one is prime;-) */

Typedefs
typedef void *(*	hash_key_func_t) (const void *)
typedef void(*	hash_free_func_t) (void *)

Functions
static void	hash_enlarge_table (hash_table htp)
	Private functions. More...
static hash_entry *	hash_find_entry (hash_table htp, const void *key, _uint *prank, _uint *stats)
	return where the key is [to be] stored, depending on the operation. More...
static string	hash_print_key (hash_key_type, const void *)
static int	hash_int_equal (const void *, const void *)
static _uint	hash_int_rank (const void *, size_t)
static int	hash_pointer_equal (const void *, const void *)
static _uint	hash_pointer_rank (const void *, size_t)
static int	hash_string_equal (const char *, const char *)
_uint	hash_string_rank (const void *key, size_t size)
	en s'inspirant vaguement de Fast Hashing of Variable-Length Text Strings Peter K. More...
static int	hash_chunk_equal (const gen_chunk *, const gen_chunk *)
static _uint	hash_chunk_rank (const gen_chunk *, size_t)
static size_t	hash_size_limit (size_t current_size)
	returns the maximum number of things to hold in a table More...
static size_t	get_next_hash_table_size (size_t size)
	Now we need the table size to be a prime number. More...
void	hash_warn_on_redefinition (void)
	these function set the variable should_i_warn_on_redefinition to the value true or false More...
void	hash_dont_warn_on_redefinition (void)
bool	hash_warn_on_redefinition_p (void)
static void *	hash_store_string (const void *s)
static void	hash_free_string (void *s)
hash_table	hash_table_generic_make (hash_key_type key_type, size_t size, hash_equals_t private_equal_p, hash_rank_t private_rank)
	this function makes a hash table of size size. More...
hash_table	hash_table_make (hash_key_type key_type, size_t size)
void	hash_table_clear (hash_table htp)
	Clears all entries of a hash table HTP. More...
void	hash_table_free (hash_table htp)
	this function deletes a hash table that is no longer useful. More...
void	hash_overwrite (hash_table htp, const void *key, const void *val)
	hash_put which allows silent overwrite... More...
void	hash_put (hash_table htp, const void *key, const void *val)
	This functions stores a couple (key,val) in the hash table pointed to by htp. More...
void *	hash_delget (hash_table htp, const void *key, void **pkey)
	deletes key from the hash table. More...
void *	hash_del (hash_table htp, const void *key)
	this function removes from the hash table pointed to by htp the couple whose key is equal to key. More...
void *	hash_get (const hash_table htp, const void *key)
	this function retrieves in the hash table pointed to by htp the couple whose key is equal to key. More...
list	hash_get_default_empty_list (const hash_table h, const void *k)
	Like hash_get() but returns an empty list instead of HASH_UNDEFINED_VALUE when a key is not found. More...
bool	hash_defined_p (const hash_table htp, const void *key)
	true if key has e value in htp. More...
void	hash_update (hash_table htp, const void *key, const void *val)
	update key->val in htp, that MUST be pre-existent. More...
void	hash_table_print_header (hash_table htp, FILE *fout)
	this function prints the header of the hash_table pointed to by htp on the opened stream fout. More...
void	hash_table_print (hash_table htp)
	this function prints the content of the hash_table pointed to by htp on stderr. More...
void	hash_table_fprintf (FILE *f, gen_string_func_t key_to_string, gen_string_func_t value_to_string, const hash_table htp)
	This function prints the content of the hash_table pointed to by htp on file descriptor f, using functions key_to_string and value_to string to display the mapping. More...
void	hash_table_dump (const hash_table htp)
int	hash_table_entry_count (hash_table htp)
	now we define observers in order to hide the hash_table type... More...
int	hash_table_size (hash_table htp)
	returns the size of the internal array. More...
hash_key_type	hash_table_type (hash_table htp)
	returns the type of the hash_table. More...
void *	hash_table_scan (hash_table htp, void *hentryp_arg, void **pkey, void **pval)
int	hash_table_own_allocated_memory (hash_table htp)
void *	hash_map_get (const hash_table h, const void *k)
	newgen mapping to newgen hash... More...
bool	hash_map_defined_p (const hash_table h, const void *k)
void	hash_map_put (hash_table h, const void *k, const void *v)
void *	hash_map_del (hash_table h, const void *k)
void	hash_map_update (hash_table h, const void *k, const void *v)
hash_equals_t	hash_table_equals_function (hash_table h)
	Because the hash table data structure is hidden in this source file hash.c and not exported via the newgen_include.h, it is not possible to access its fields in other files, e.g. More...
hash_rank_t	hash_table_rank_function (hash_table h)

Variables
static size_t	prime_list []
	list of the prime numbers from 17 to 2^31-1 used as allocated size More...
static bool	should_i_warn_on_redefinition = true
	internal variable to know we should warm or not More...
static size_t	max_size_seen = 0
static int	inc_prime_list []
	distinct primes for long cycle incremental search More...

Macro Definition Documentation

END_OF_SIZE_TABLE

#define END_OF_SIZE_TABLE   (0)

Constant to find the end of the prime numbers table.

Definition at line 83 of file hash.c.

HASH_ENTRY_FREE

#define HASH_ENTRY_FREE   ((void *) 0)

Some predefined values for the key.

Definition at line 52 of file hash.c.

HASH_ENTRY_FREE_FOR_PUT

#define HASH_ENTRY_FREE_FOR_PUT   ((void *) -1)

Definition at line 53 of file hash.c.

HASH_INC_SIZE

#define HASH_INC_SIZE   (31) /**31... (yes, this one is prime;-) */

Definition at line 724 of file hash.c.

RANK

#define RANK	(		key,
			size
	)		((((_uint)(key)) ^ 0xfab1c0e1U)%(size))

Hash function to get the index of the array from the key.

Does not work : if sizeof(uintptr_t) == 8 so go into less portable way: Fabien began with this joke... :-)

Definition at line 94 of file hash.c.

Typedef Documentation

hash_free_func_t

typedef void(* hash_free_func_t) (void *)

Definition at line 61 of file hash.c.

hash_key_func_t

typedef void*(* hash_key_func_t) (const void *)

Definition at line 60 of file hash.c.

Function Documentation

get_next_hash_table_size()

static size_t get_next_hash_table_size ( size_t  size )

static

Now we need the table size to be a prime number.

So we need to retrieve the next prime number in a list.

Definition at line 166 of file hash.c.

{
  size_t * p_prime = prime_list;
  while (*p_prime <= size) {
    message_assert("size too big ", *p_prime != END_OF_SIZE_TABLE);
    p_prime++;
  }
  return *p_prime;
}

References END_OF_SIZE_TABLE, message_assert, and prime_list.

Referenced by hash_enlarge_table(), and hash_table_generic_make().

Here is the caller graph for this function:

hash_chunk_equal()

static int hash_chunk_equal ( const gen_chunk *  key1, const gen_chunk *  key2  )

static

Definition at line 688 of file hash.c.

{
  return key1->p == key2->p;
}

References gen_chunk::p.

Referenced by hash_table_generic_make().

Here is the caller graph for this function:

hash_chunk_rank()

static _uint hash_chunk_rank ( const gen_chunk *  key, size_t  size  )

static

Definition at line 662 of file hash.c.

{
  return RANK(key->i, size);
}

References gen_chunk::i, and RANK.

Referenced by hash_table_generic_make().

Here is the caller graph for this function:

hash_defined_p()

bool hash_defined_p	(	const hash_table	htp,
		const void *	key
	)

true if key has e value in htp.

Definition at line 484 of file hash.c.

{
  return hash_get(htp, key)!=HASH_UNDEFINED_VALUE;
}

References hash_get(), and HASH_UNDEFINED_VALUE.

Referenced by adjust_goto_from_to(), arguments_are_something(), available_component(), check_mux_availibity(), check_ref(), clean_enclosing_loops(), compute_distribution_context(), compute_distribution_controlization_context(), copy_leaf_out(), copy_obj_in(), create_or_get_a_set_from_control(), create_or_get_an_interval_node(), dagvtx_terapix_priority(), do_gpu_qualify_pointers(), entity_has_values_p(), eov_entity_to_eliminate_p(), freia_allocate_new_images_if_needed(), freia_compile(), freia_dag_optimize(), freia_extract_params(), freia_memory_management_statement(), freia_scalar_rw_dep(), freia_shuffle_move_forward(), fuse_sequences_in_unstructured(), get_upper_model(), glc_call(), hash_map_defined_p(), hash_overwrite(), hwac_freia_api(), init_label(), internal_compute_distribution_context(), quick_multi_already_seen_p(), redeclaration_enter_statement(), ref_count_rwt(), reference_written_p(), register_scalar_communications(), related_images_p(), remove_simple_scalar_pointers(), rename_loop_index(), rename_reference(), rssp_ref(), seen_p(), seq_rwt(), sigmac_name_instances(), sio_ref_rwt(), statement_to_goto_table_flt(), terapix_gram_management(), type_this_entity_if_needed(), and update_used_labels().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_del()

void* hash_del	(	hash_table	htp,
		const void *	key
	)

this function removes from the hash table pointed to by htp the couple whose key is equal to key.

nothing is done if no such couple exists. ??? should I abort ? (FC)

Definition at line 439 of file hash.c.

{
    void * tmp;
    return hash_delget(htp, key, &tmp);
}

References hash_delget().

Referenced by atomizer_of_external(), atomizer_of_intrinsic(), atomizer_of_loop(), build_first_comb(), build_number_to_statement(), calculate_delay(), da_process_list(), do_array_expansion_aux(), freia_dag_optimize(), init_statement_equivalence_table(), invalidate_expressions_in_statement(), loop_normalize_of_loop(), loop_to_complexity(), phrase_check_reference(), process_used_slots(), remove_common_variables_from_hash_table(), remove_entity_type_stack(), remove_entity_values(), remove_formal_parameters_from_hash_table(), seq_rwt(), sequence_proper_declarations_rename_in_place(), set_del_element(), set_difference(), store_expression(), update_def_into_tasks_table(), and vvs_on_prototypes().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_delget()

void* hash_delget	(	hash_table	htp,
		const void *	key,
		void **	pkey
	)

deletes key from the hash table.

returns the val and key

FI: the stack is destroyed by assert; I need to split the statement to put a breakpoint just before the stack disappears.

Definition at line 398 of file hash.c.

{
    hash_entry * hep;
    void *val;
    _uint rank;
 
    /* FI: the stack is destroyed by assert; I need to split the
       statement to put a breakpoint just before the stack
       disappears. */
    if(!(key!=HASH_ENTRY_FREE && key!=HASH_ENTRY_FREE_FOR_PUT))
      message_assert("legal input key",
                     key!=HASH_ENTRY_FREE && key!=HASH_ENTRY_FREE_FOR_PUT);
 
    htp->n_del++;
    hep = hash_find_entry(htp, key, &rank, &htp->n_del_iter);
 
    if (hep->key != HASH_ENTRY_FREE && hep->key != HASH_ENTRY_FREE_FOR_PUT) {
        // argh... was hep->key... cannot return it!
        if (htp->delete_key)
          htp->delete_key(hep->key), *pkey = NULL;
        else
          *pkey = hep->key;
        val = hep->val;
        htp->array[rank].key = HASH_ENTRY_FREE_FOR_PUT;
        htp->array[rank].val = NULL;
        htp->n_entry -= 1;
        htp->n_free_for_puts++;
        return val;
    }
 
    *pkey = 0;
    return HASH_UNDEFINED_VALUE;
}

References __hash_table::array, __hash_table::delete_key, HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_find_entry(), HASH_UNDEFINED_VALUE, hash_entry::key, message_assert, __hash_table::n_del, __hash_table::n_del_iter, __hash_table::n_entry, __hash_table::n_free_for_puts, rank, and hash_entry::val.

Referenced by gen_delete_tabulated_name(), hash_del(), hash_map_del(), replicate_cycles(), and set_delfree_element().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_dont_warn_on_redefinition()

void hash_dont_warn_on_redefinition

(

void

)

Definition at line 188 of file hash.c.

{
  should_i_warn_on_redefinition = false;
}

References should_i_warn_on_redefinition.

Referenced by comEngine_feasability(), deatomizer(), phrase_remove_dependences(), set_union(), and topologically_sorted_module_list().

Here is the caller graph for this function:

hash_enlarge_table()

static void hash_enlarge_table ( hash_table  htp )

static

Private functions.

function to enlarge the hash_table htp.

the new size will be first number in the array prime_numbers_for_table_size that will be greater or equal to the actual size

Get the next prime number in the table

Definition at line 591 of file hash.c.

{
  hash_entry * old_array;
  size_t i, old_size;
 
  old_size = htp->size;
  old_array = htp->array;
 
  htp->size++;
  /* Get the next prime number in the table */
  htp->size = get_next_hash_table_size(htp->size);
  htp->array = (hash_entry *) alloc(htp->size* sizeof(hash_entry));
  htp->limit = hash_size_limit(htp->size);
 
  for (i = 0; i < htp->size ; i++)
    htp->array[i].key = HASH_ENTRY_FREE;
 
  for (i = 0; i < old_size; i++)
  {
    hash_entry he;
    he = old_array[i];
 
    if (he.key != HASH_ENTRY_FREE && he.key != HASH_ENTRY_FREE_FOR_PUT) {
      hash_entry * nhep;
      _uint rank;
 
      htp->n_put++;
      nhep = hash_find_entry(htp, he.key, &rank, &htp->n_put_iter);
 
      if (nhep->key != HASH_ENTRY_FREE) {
        fprintf(stderr, "[hash_enlarge_table] fatal error\n");
        abort();
      }
      htp->array[rank] = he;
    }
  }
  gen_free_area((void**)old_array, old_size*sizeof(hash_entry));
}

References abort, alloc(), __hash_table::array, fprintf(), gen_free_area(), get_next_hash_table_size(), HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_find_entry(), hash_size_limit(), hash_entry::key, __hash_table::limit, __hash_table::n_put, __hash_table::n_put_iter, rank, and __hash_table::size.

Referenced by hash_put().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_find_entry()

static hash_entry * hash_find_entry ( const hash_table  htp, const void *  key, _uint *  prank, _uint *  stats  )

static

return where the key is [to be] stored, depending on the operation.

history of r_inc value RT: 1 GO: 1 + abs(r_init)%(size-1) FC: inc_prime_list[ RANK(r_init, HASH_INC_SIZE) ] FC rationnal: if r_init is perfect, 1 is fine... if it is not perfect, let us randmize here some more... I'm not sure the result is any better than 1??? It does seems to help significantly on some examples...

FC 05/06/2003 if r_init is randomized (i.e. perfect hash function) and r_inc does not kill everything (could it?) if p is the filled proportion for the table, 0<=p<1 we should have number_of_iterations = \Sigma_{i=1}{\infinity} i*(1-p)p^{i-1} this formula must simplify somehow... = 1/(1-p) ? 0.20 => 1.25 0.25 => 1.33.. 0.33.. => 1.50 0.50 => 2.00 0.66.. => 3.00 0.70 => 3.33

the r-th entry

a possible never used place is found, stop seeking! and return first free found or current if none.

this is a possible place for storing, but the key may be there anyway... so we keep on seeking, but keep the first found place.

the key is found!

GO: it is not anymore the next slot, we skip some of them depending on the reckonned increment

argh! we have made a full round... it may happen after many put and del, if the table contains no FREE, but only many FREE_FOR_PUT instead.

Definition at line 730 of file hash.c.

{
  register size_t
    r_init = (*(htp->rank))(key, htp->size),
    r = r_init,
    /* history of r_inc value
     * RT: 1
     * GO: 1 + abs(r_init)%(size-1)
     * FC: inc_prime_list[ RANK(r_init, HASH_INC_SIZE) ]
     * FC rationnal: if r_init is perfect, 1 is fine...
     *    if it is not perfect, let us randmize here some more...
     *    I'm not sure the result is any better than 1???
     *    It does seems to help significantly on some examples...
     */
    r_inc  = inc_prime_list[ RANK(r_init, HASH_INC_SIZE) ],
    r_first_free = r_init;
  bool first_free_found = false;
  hash_entry he;
 
  while (1)
  {
    /* FC 05/06/2003
     * if r_init is randomized (i.e. perfect hash function)
     * and r_inc does not kill everything (could it?)
     * if p is the filled proportion for the table, 0<=p<1
     * we should have number_of_iterations
     *        = \Sigma_{i=1}{\infinity} i*(1-p)p^{i-1}
     * this formula must simplify somehow... = 1/(1-p) ?
     * 0.20   => 1.25
     * 0.25   => 1.33..
     * 0.33.. => 1.50
     * 0.50   => 2.00
     * 0.66.. => 3.00
     * 0.70   => 3.33
     */
    if (stats) (*stats)++;
 
    /* the r-th entry */
    he = htp->array[r];
 
    /* a possible never used place is found, stop seeking!
     * and return first free found or current if none.
     */
    if (he.key == HASH_ENTRY_FREE) {
      if (first_free_found)
        r = r_first_free;
      break;
    }
 
    /* this is a possible place for storing, but the key may be there anyway...
     * so we keep on seeking, but keep the first found place.
     */
    if (he.key == HASH_ENTRY_FREE_FOR_PUT && !first_free_found) {
      r_first_free = r;
      first_free_found = true;
    }
 
    /* the key is found! */
    if (he.key != HASH_ENTRY_FREE_FOR_PUT &&
        (*(htp->equals))(he.key, key))
      break;
 
    /* GO: it is not anymore the next slot, we skip some of them depending
     * on the reckonned increment
     */
    r = (r + r_inc) % htp->size;
 
    /* argh! we have made a full round...
     * it may happen after many put and del, if the table contains no FREE,
     * but only many FREE_FOR_PUT instead.
     */
    if(r == r_init) {
      message_assert("one free place was seen", first_free_found);
      r = r_first_free;
      break;
    }
  }
 
  *prank = r;
  return &(htp->array[r]);
}

References __hash_table::array, __hash_table::equals, HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, HASH_INC_SIZE, inc_prime_list, hash_entry::key, message_assert, __hash_table::rank, RANK, and __hash_table::size.

Referenced by hash_delget(), hash_enlarge_table(), hash_get(), hash_put(), and hash_update().

Here is the caller graph for this function:

hash_free_string()

static void hash_free_string ( void *  s )

static

Definition at line 203 of file hash.c.

{
  free(s);
}

References free().

Referenced by hash_table_generic_make().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_get()

void* hash_get	(	const hash_table	htp,
		const void *	key
	)

this function retrieves in the hash table pointed to by htp the couple whose key is equal to key.

the HASH_UNDEFINED_VALUE pointer is returned if no such couple exists. otherwise the corresponding value is returned.

FI: the stack is destroyed by assert; I need to split the statement to put a breakpoint just before the stack disappears.

else may be there

Definition at line 449 of file hash.c.

{
  hash_entry * hep;
  _uint n;
 
  /* FI: the stack is destroyed by assert; I need to split the
     statement to put a breakpoint just before the stack
     disappears. */
  if(!(key!=HASH_ENTRY_FREE && key!=HASH_ENTRY_FREE_FOR_PUT))
    message_assert("legal input key",
                   key!=HASH_ENTRY_FREE && key!=HASH_ENTRY_FREE_FOR_PUT);
 
  if (!htp->n_entry)
    return HASH_UNDEFINED_VALUE;
 
  /* else may be there */
  htp->n_get++;
  hep = hash_find_entry(htp, key, &n, &htp->n_get_iter);
 
  return hep->key!=HASH_ENTRY_FREE &&
    hep->key!=HASH_ENTRY_FREE_FOR_PUT ? hep->val : HASH_UNDEFINED_VALUE;
}

References HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_find_entry(), HASH_UNDEFINED_VALUE, hash_entry::key, message_assert, __hash_table::n_entry, __hash_table::n_get, __hash_table::n_get_iter, and hash_entry::val.

Referenced by add_address_of_value(), add_child_parent_pair(), add_conflicts(), add_cycle_dependency(), add_def_into_tasks_table(), add_exec_mmcd(), add_intermediate_alias_value(), add_intermediate_value(), add_local_intermediate_value(), add_local_old_value(), add_new_alias_value(), add_new_value(), add_new_value_name(), add_old_alias_value(), add_old_value(), add_rule(), add_sizeof_value(), add_toggle_inc_statements(), adg_number_to_ordering(), adg_vertex_to_ordering(), adjust_goto_from_to(), aliased_translation_p(), allocated_memory_already_seen_p(), ancestor_cycle_head_to_scc(), apply_number_to_statement(), apply_ordering_to_statement(), attach_ref_to_stat(), bourdoncle_partition(), broadcast_conditions(), build_aliases(), build_bdt_null(), build_esv_list(), build_options_menu_and_panel(), calculate_delay(), call_to_complexity(), callgraph(), check_for_conflict(), check_ref(), check_sharing(), comEngine_distribute(), comEngine_opt_loop_interchange(), common_to_defined_size_p(), common_to_size(), comp_exec_domain(), compare_dfs_weight(), compare_nodes_dim(), compare_unks_frenq(), compute_distribution_controlization_context(), control_to_ancestor(), control_to_label_name(), control_to_replicate(), control_translate_arcs(), controlize_distribution(), controls_to_hash_table(), copy_dfn(), copy_hsearch(), create_or_get_a_set_from_control(), create_or_get_an_interval_node(), create_realFifo_proc(), cutting_conditions(), da_process_list(), dag_terapix_measures(), dag_vertex_pred_imagelets(), dagvtx_terapix_priority(), davinci_print_non_deterministic_unstructured(), distribute(), do_array_expansion(), do_clone_entity(), do_clone_reference(), do_get_operator_id(), do_gpu_qualify_pointers(), do_HRE_memory_mapping_stat(), do_linearize_pointer_is_expression(), do_scalar_renaming_in_successors(), do_slightly_rename_entities(), effects_to_dma(), entity_basic_concrete_type(), entity_to_intermediate_value(), entity_to_new_value(), entity_to_old_value(), eov_get_replaced_enity(), external_value_name(), extract_non_conflicting_statements(), fill_gLoopToToggleEnt(), find_el_with_num(), find_or_create_newInd(), find_or_create_slot(), find_tmp_of_exp(), flint_initialize_statement_def_use_variables(), flint_variable_uninitialize_elsewhere(), fprint_delay(), fprint_statement_complexity(), free_already_seen_p(), freia_allocate_new_images_if_needed(), freia_compile(), freia_dag_optimize(), freia_extract_params(), freia_memory_management_statement(), freia_scalar_rw_dep(), freia_terapix_call(), fsi_cmp(), fuse_sequences_in_unstructured(), gen_get_ancestor(), gen_get_recurse_ancestor(), gen_get_tabulated_name_basic(), generate_code_call(), generate_code_loop(), generate_code_test_HRE(), generate_code_test_proc(), generate_fifo_stats(), generate_fifo_stats2(), generate_ind_fifo_stat2(), generate_io_wp65_code(), generate_mmcd_stat_from_ref(), generate_mmcd_stats_from_ref(), generate_scalar_variables(), generate_scalar_variables_from_list(), generate_stat_from_ref_list_HRE(), generate_stat_from_ref_list_HRE_list(), generic_type_equal_p(), genref_one_statement(), get_cached(), get_cycle_dependencies(), get_dfn(), get_fifo_from_ref(), get_from_entity_type_stack_table(), get_label_control(), get_methods(), get_new_user_file(), get_realFifoNum(), get_stmt_index_coeff(), get_supportedRef_HRE(), get_supportedRef_proc(), get_switch_name_function_for_intrinsic(), get_toggleEnt_from_ref(), get_typing_function_for_intrinsic(), get_upper_model(), get_use_entities_list(), gfc2pips_get_use_st(), glc_call(), gram_param(), hash_defined_p(), hash_get_default_empty_list(), hash_map_get(), hwac_freia_api(), if_conversion_compact_stats(), init_statement_equivalence_table(), insert_mapping(), intrinsic_precedence(), is_c_keyword_typedef(), is_not_trivial_p(), load_control_fix_point(), load_control_postcondition(), load_cycle_fix_point(), load_cycle_temporary_precondition(), load_statement_temporary_precondition(), local_print_statement_set(), loop_nest_to_local_variables(), loop_rwt(), make_all_movement_blocks(), make_array_bounds(), make_global_common_and_initialize(), make_init_newInd_stat(), make_load_blocks(), make_mmcd_stats_from_ref(), make_new_local_variables(), make_reindex(), make_seqStat(), make_store_blocks(), mapping_on_broadcast(), maximal_out_degree_of_points_to_graph(), module_list_sort(), module_name_to_callees(), move_declaration_control_node_declarations_to_statement(), new_value_entity_p(), opt_loop_interchange_fill_lists(), options_select(), other_significant_uses(), outliner_parameters(), partial_broadcast_coefficients(), partition_to_unstructured(), partition_unknowns(), pips_user_value_name(), plc_fprint_dfs(), plc_fprint_distance(), plc_fprint_proto(), plc_make_distance(), plc_make_min_dim(), prepare_array_bounds(), prgm_mapping(), process_code_seq(), process_gLoopToSync_HRE(), process_gLoopToSync_proc(), process_opt_replace(), process_ref_lists(), process_used_slots(), re_do_it(), ref_count_rwt(), reference_conflicting_test_and_update(), reference_conversion_expression(), reference_filter(), reference_to_address_of_value(), reference_written_p(), regenerate_toggles(), register_scalar_communications(), registered_controls_p(), related_effect(), related_images_p(), remove_entity_type_stack(), remove_simple_scalar_pointers(), rename_loop_index(), rename_reference(), rename_statement_declarations(), rename_variable_type(), replace_entities_call_walker(), replace_entities_expression_walker(), replace_entities_in_cusq_context(), replace_entities_loop_walker(), replace_expression_similar_to_pattern(), reuse_pred_slot(), sc_inst(), sc_kernel_specific_agent(), sc_vtx_tostring(), scc_to_dag(), search_scc_bdt(), seq_rwt(), sequence_proper_declarations_rename_in_place(), sesamify(), set_belong_p(), set_control_to_label(), set_dimensions_of_local_variables(), set_intersection(), shared_obj(), shared_obj_in(), shared_simple_in(), sigmac_name_instances(), sigmac_params_decl(), simd_replace_parameters(), sio_ref_rwt(), some_conflicts_between(), sort_unknowns(), spoc_alu_conf(), spoc_measure_conf(), spoc_poc_conf(), spoc_th_conf(), statement_to_goto_table_flt(), step_install(), step_statement_path_get(), storage_space_of_variable(), store_control_fix_point(), store_control_postcondition(), substitute_statement_label(), substitute_variable_by_expression(), terapix_gram_management(), test_rwt(), text_statement_array_comp_regions(), text_statement_continuation_conditions(), tiling_sequence(), top_down_abc_flt(), top_down_abc_rwt(), topological_number_assign_to_module(), transitive_positions(), translate_IO_ref(), type_to_sizeof_value(), uns_rwt(), unstructured_to_complexity(), update_control_postcondition(), update_def_into_tasks_table(), update_erosions(), update_number_to_statement(), update_options(), update_temporary_precondition(), update_toggle_init_stats_list(), use_output_slot(), usual_loop_tiling(), value_entity_p(), value_to_variable(), valuer(), vertex_statement(), vvs_on_prototypes(), words_intrinsic_call(), write_resulting_bdt(), and xml_Chain_Graph().

Here is the call graph for this function:

hash_get_default_empty_list()

list hash_get_default_empty_list	(	const hash_table	h,
		const void *	k
	)

Like hash_get() but returns an empty list instead of HASH_UNDEFINED_VALUE when a key is not found.

Definition at line 475 of file hash.c.

                                                                     {
  list l = (list) hash_get(h, k);
 
  return (l == (list) HASH_UNDEFINED_VALUE) ? NIL : l;
}

References hash_get(), HASH_UNDEFINED_VALUE, and NIL.

Referenced by controlize_goto(), covers_labels_p(), get_statement_matches(), init_label(), make_conditional_control(), and update_used_labels().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_int_equal()

static int hash_int_equal ( const void *  key1, const void *  key2  )

static

Definition at line 678 of file hash.c.

{
  return ((_int) key1) == ((_int) key2);
}

Referenced by hash_table_generic_make().

Here is the caller graph for this function:

hash_int_rank()

static _uint hash_int_rank ( const void *  key, size_t  size  )

static

Definition at line 652 of file hash.c.

{
  return RANK(key, size);
}

References RANK.

Referenced by hash_table_generic_make().

Here is the caller graph for this function:

hash_map_defined_p()

bool hash_map_defined_p	(	const hash_table	h,
		const void *	k
	)

Definition at line 888 of file hash.c.

{
  gen_chunk key;
  key.e = (void *) k;
  return hash_defined_p(h, &key);
}

References gen_chunk::e, and hash_defined_p().

Here is the call graph for this function:

hash_map_del()

void* hash_map_del	(	hash_table	h,
		const void *	k
	)

Definition at line 905 of file hash.c.

{
  gen_chunk key, * oldkeychunk, * val;
  void * result;
 
  key.e = (void *) k;
  val = hash_delget(h, &key, (void**) &oldkeychunk);
  message_assert("defined value (entry to delete must be defined!)",
                 val!=HASH_UNDEFINED_VALUE);
  result = val->e;
 
  oldkeychunk->p = NEWGEN_FREED;
  free(oldkeychunk);
 
  val->p = NEWGEN_FREED;
  free(val);
 
  return result;
}

References gen_chunk::e, free(), hash_delget(), HASH_UNDEFINED_VALUE, message_assert, NEWGEN_FREED, and gen_chunk::p.

Referenced by hash_map_update().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_map_get()

void* hash_map_get	(	const hash_table	h,
		const void *	k
	)

newgen mapping to newgen hash...

Definition at line 878 of file hash.c.

{
  gen_chunk key, * val;
  key.e = (void *) k;
  val = (gen_chunk*) hash_get(h, &key);
  if (val==HASH_UNDEFINED_VALUE)
    fatal("no value correspond to key %p", k);
  return val->e;
}

References gen_chunk::e, fatal(), hash_get(), and HASH_UNDEFINED_VALUE.

Here is the call graph for this function:

hash_map_put()

void hash_map_put	(	hash_table	h,
		const void *	k,
		const void *	v
	)

Definition at line 895 of file hash.c.

{
  gen_chunk
    * key = (gen_chunk*) alloc(sizeof(gen_chunk)),
    * val = (gen_chunk*) alloc(sizeof(gen_chunk));
  key->e = (void *) k;
  val->e = (void *) v;
  hash_put(h, key, val);
}

References alloc(), gen_chunk::e, and hash_put().

Referenced by hash_map_update().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_map_update()

void hash_map_update	(	hash_table	h,
		const void *	k,
		const void *	v
	)

Definition at line 925 of file hash.c.

{
  hash_map_del(h, k);
  hash_map_put(h, k, v);
}

References hash_map_del(), and hash_map_put().

Here is the call graph for this function:

hash_overwrite()

void hash_overwrite	(	hash_table	htp,
		const void *	key,
		const void *	val
	)

hash_put which allows silent overwrite...

Definition at line 344 of file hash.c.

{
  if (hash_defined_p(htp, key))
    hash_update(htp, key, val);
  else
    hash_put(htp, key, val);
}

References hash_defined_p(), hash_put(), and hash_update().

Referenced by overwrite_ordering_of_the_statement_to_current_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_pointer_equal()

static int hash_pointer_equal ( const void *  key1, const void *  key2  )

static

Definition at line 683 of file hash.c.

{
  return key1 == key2;
}

Referenced by hash_table_generic_make().

Here is the caller graph for this function:

hash_pointer_rank()

static _uint hash_pointer_rank ( const void *  key, size_t  size  )

static

Definition at line 657 of file hash.c.

{
  return RANK(key, size);
}

References RANK.

Referenced by hash_table_generic_make().

Here is the caller graph for this function:

hash_print_key()

static char * hash_print_key ( hash_key_type  t, const void *  key  )

static

even 8 byte pointer => ~16 chars

hey, this is just what we need!

Use extensive C99 printf formats and stdint.h types to avoid truncation warnings:

Definition at line 693 of file hash.c.

{
  static char buffer[32]; /* even 8 byte pointer => ~16 chars */
 
  if (t == hash_string)
    return (char*) key; /* hey, this is just what we need! */
  /* Use extensive C99 printf formats and stdint.h types to avoid
     truncation warnings: */
  else if (t == hash_int)
    sprintf(buffer, "%td", (_int) key);
  else if (t == hash_pointer || t == hash_private)
    sprintf(buffer, "%p", key);
  else if (t == hash_chunk)
    sprintf(buffer, "%zx", (_uint) ((gen_chunk *)key)->p);
  else {
    fprintf(stderr, "[hash_print_key] bad type : %d\n", t);
    abort();
  }
 
  return buffer;
}

References abort, buffer, fprintf(), hash_chunk, hash_int, hash_pointer, hash_private, and hash_string.

Referenced by hash_put(), and hash_table_print().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_put()

void hash_put	(	hash_table	htp,
		const void *	key,
		const void *	val
	)

This functions stores a couple (key,val) in the hash table pointed to by htp.

If a couple with the same key was already stored in the table and if hash_warn_on_redefintion was requested, hash_put complains but replace the old value by the new one. This is a potential source for a memory leak. If the value to store is HASH_UNDEFINED_VALUE or if the key is HASH_ENTRY_FREE or HASH_ENTRY_FREE_FOR_INPUT, hash_put aborts. The restrictions on the key should be avoided by changing the implementation. The undefined value should be user-definable. It might be argued that users should be free to assign HASH_UNDEFINED_VALUE, but they can always perform hash_del() to get the same result

Definition at line 364 of file hash.c.

{
  _uint rank;
  hash_entry * hep;
 
  if (htp->n_entry+1 >= (htp->limit))
    hash_enlarge_table(htp);
 
  message_assert("legal input key",
                 key!=HASH_ENTRY_FREE && key!=HASH_ENTRY_FREE_FOR_PUT);
  message_assert("input value must be defined", val!=HASH_UNDEFINED_VALUE);
 
  htp->n_put++;
  hep = hash_find_entry(htp, key, &rank, &htp->n_put_iter);
 
  if (hep->key != HASH_ENTRY_FREE && hep->key != HASH_ENTRY_FREE_FOR_PUT) {
    if (should_i_warn_on_redefinition && hep->val != val) {
      (void) fprintf(stderr, "[hash_put] key redefined: %s\n",
                     hash_print_key(htp->type, key));
    }
    hep->val = (void *) val;
  }
  else {
    if (hep->key == HASH_ENTRY_FREE_FOR_PUT)
      htp->n_free_for_puts--;
    htp->n_entry += 1;
    hep->key = htp->store_key? htp->store_key(key): (void*) key;
    hep->val = (void *) val;
  }
}

References fprintf(), hash_enlarge_table(), HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_find_entry(), hash_print_key(), HASH_UNDEFINED_VALUE, hash_entry::key, __hash_table::limit, message_assert, __hash_table::n_entry, __hash_table::n_free_for_puts, __hash_table::n_put, __hash_table::n_put_iter, rank, should_i_warn_on_redefinition, __hash_table::store_key, __hash_table::type, and hash_entry::val.

Referenced by _expression_similar_p(), add_address_of_value(), add_child_parent_pair(), add_common_variables_to_hash_table(), add_cycle_dependency(), add_def_into_tasks_table(), add_formal_parameters_to_hash_table(), add_intermediate_alias_value(), add_intermediate_value(), add_local_intermediate_value(), add_local_old_value(), add_new_alias_value(), add_new_value(), add_new_value_name(), add_old_alias_value(), add_old_value(), add_ordering_of_the_statement(), add_ordering_of_the_statement_to_current_mapping(), add_rule(), add_sizeof_value(), add_synonym_values(), adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_rename_entities(), adg_reorder_statement_number(), aliased_translation_p(), alloc_new_slot(), allocated_memory_already_seen_p(), assign_tmp_to_exp(), attach_ref_to_stat(), bourdoncle_component(), build_aliases(), build_first_comb(), build_options_menu_and_panel(), c_parser_put_new_typedef(), calculate_delay(), call_rwt(), callgraph(), check_for_conflict(), check_ref(), check_stmt(), clean_enclosing_loops(), clean_up_sequences_rewrite(), comp_secs_map_to_listmap(), compute_distribution_context(), compute_distribution_controlization_context(), compute_fifo_from_ref(), compute_ordering_to_dg_mapping(), control_shallow_copy(), controls_to_hash_table(), copy_dfn(), copy_hput(), copy_obj_out_constructed(), create_or_get_a_set_from_control(), create_or_get_an_interval_node(), create_realFifo_proc(), create_statements_of_label(), da_process_list(), dag_fix_image_reuse(), declarations_read(), declare_new_typedef(), do_array_expansion(), do_clone_entity(), do_HRE_memory_mapping_loop(), do_linearize_expression_is_pointer(), do_scalar_renaming_in_successors(), do_slightly_rename_entities(), edge_weight(), effects_to_dma(), effectsmap_to_listmap(), entity_basic_concrete_type(), eov_add_entity_to_eliminate(), fetch_callees_complexities(), fetch_complexity_parameters(), fill_gLoopToOpt(), fill_gLoopToToggleEnt(), fill_gRefToEncLoop_call(), fill_gRefToEncLoop_test(), find_or_create_emulated_shared_variable(), find_or_create_fifo_from_ref(), find_or_create_newInd(), finish_new_gd_ins(), FixCInternalLabels(), flint_initialize_statement_def_use_variables(), free_already_seen_p(), freia_allocate_new_images_if_needed(), freia_dag_optimize(), freia_extract_params(), freia_scalar_rw_dep(), freia_terapix_call(), freia_trpx_compile_one_dag(), fsi_seq_flt(), fsi_sort(), fuse_sequences_in_unstructured(), gen_put_tabulated_name(), gen_recurse_stop(), gen_sharing_p(), generate_code_loop(), generate_scalar_variables(), generate_scalar_variables_from_list(), generic_type_equal_p(), get_a_smem_slot(), get_methods(), get_new_user_file(), get_realFifoNum(), get_sp_of_call_p(), get_supportedRef_proc(), gfc2pips_get_use_st(), glc_call(), handle_include_file(), hash_map_put(), hash_overwrite(), hwac_freia_api(), init_intrinsic_handlers(), init_label(), init_one_statement(), init_statement_equivalence_table(), init_statement_matches_map(), initialize_mu_list(), insert_mapping(), internal_compute_distribution_context(), is_not_trivial_p(), keep_track_of_typedef(), listmap_to_compsecs_map(), listmap_to_effectsmap(), loop_nest_to_local_variables(), loop_normalize_of_loop(), loop_rwt(), loop_to_complexity(), make_mmcd_stats_from_ref(), make_new_local_variables(), make_proto(), make_simd_statement(), maximal_out_degree_of_points_to_graph(), module_list_sort(), module_name_to_callees(), mppa_compile_dag(), opencl_compile_mergeable_dag(), opencl_generate_special_kernel_ops(), outliner_extract_loop_bound(), outliner_smart_references_computation(), parser_init_keyword_typedef_table(), phrase_check_reference(), pips_user_value_name(), pipsdbm_read_statement_mapping(), plc_make_dim(), plc_make_distance(), plc_make_proto(), prepare_array_bounds(), prepare_reindexing(), preprocessor_init_keyword_typedef_table(), put_new_typedef(), put_to_entity_type_stack_table(), quick_multi_already_seen_p(), re_do_it(), ref_count_rwt(), reference_conflicting_test_and_update(), regenerate_toggles(), register_intrinsic_handler(), register_intrinsic_type_descriptor(), register_scalar_communications(), remove_simple_scalar_pointers(), replace_entity(), replicate_cycles(), reset_dfn(), restructure_if_then_else(), reuse_pred_slot(), rssp_ref(), sc_delimiter(), scc_to_dag(), seq_rwt(), sesamify(), set_add_element(), set_as_seen(), set_assign(), set_common_to_size(), set_component(), set_control_to_label(), set_dup(), set_intersection(), set_mux(), set_singleton(), set_union(), shared_obj_in(), shared_simple_in(), sigmac_name_instances(), simd_trace_call(), sort_dfg_node(), sort_unknowns(), statement_to_goto_table_flt(), statements_to_successors(), step_install(), step_statement_path_build(), storage_space_of_variable(), store_control_fix_point(), store_control_postcondition(), supported_ref_p(), sww_seq_rwt(), terapix_gram_management(), terapix_loop_handler(), test_rwt(), top_down_abc_flt(), topological_number_assign_to_module(), transitive_positions(), uns_rwt(), update_def_into_tasks_table(), update_erosions(), update_HRE_mapping_from_list(), update_number_to_statement(), update_temporary_precondition(), update_used_labels(), vvs_on_prototypes(), and wl_rwt().

Here is the call graph for this function:

hash_size_limit()

static size_t hash_size_limit ( size_t  current_size )

static

returns the maximum number of things to hold in a table

25.0% : ((current_size)>>2) 50.0% : ((current_size)>>1) next values are TOO MUCH! 62.5% : (((current_size)>>1)+((current_size)>>3)) 75.0% : (((current_size)>>1)+((current_size)>>2))

Definition at line 152 of file hash.c.

{
  /* 25.0% : ((current_size)>>2)
   * 50.0% : ((current_size)>>1)
   * next values are TOO MUCH!
   * 62.5% : (((current_size)>>1)+((current_size)>>3))
   * 75.0% : (((current_size)>>1)+((current_size)>>2))
   */
  return current_size>>1;
}

References current_size.

Referenced by hash_enlarge_table(), and hash_table_generic_make().

Here is the caller graph for this function:

hash_store_string()

static void* hash_store_string ( const void *  s )

static

Definition at line 198 of file hash.c.

{
  return strdup((char*) s);
}

References strdup().

Referenced by hash_table_generic_make().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_string_equal()

static int hash_string_equal ( const char *  key1, const char *  key2  )

static

else check contents

Definition at line 667 of file hash.c.

{
  if (key1==key2)
    return true;
  /* else check contents */
  for(; *key1 && *key2; key1++, key2++)
    if (*key1!=*key2)
      return false;
  return *key1==*key2;
}

Referenced by hash_table_generic_make().

Here is the caller graph for this function:

hash_string_rank()

_uint hash_string_rank	(	const void *	key,
		size_t	size
	)

en s'inspirant vaguement de Fast Hashing of Variable-Length Text Strings Peter K.

Pearson CACM vol 33, nb 6, June 1990 qui ne donne qu'une valeur entre 0 et 255

unsigned int T[256] with random values unsigned int h = 0; for (char * s = (char*) key; *s; s++) h = ROTATION(...,h) ^ T[ (h^(*s)) % 256]; mais...

FC:

GO: v <<= 2, v += *s;

Definition at line 642 of file hash.c.

{
  _uint v = 0;
  const char * s;
  for (s = (char*) key; *s; s++)
    /* FC: */ v = ((v<<7) | (v>>25)) ^ *s;
    /* GO: v <<= 2, v += *s; */
  return v % size;
}

Referenced by control_rank(), hash_table_generic_make(), and points_to_rank().

Here is the caller graph for this function:

hash_table_clear()

void hash_table_clear

(

hash_table

htp

)

Clears all entries of a hash table HTP.

[pj]

Definition at line 305 of file hash.c.

{
  hash_entry * p, * end ;
 
  if (htp->size > max_size_seen) {
    max_size_seen = htp->size;
#ifdef DBG_HASH
    fprintf(stderr, "[hash_table_clear] maximum size is %d\n", max_size_seen);
#endif
  }
 
  end = htp->array + htp->size ;
  htp->n_entry = 0 ;
 
  for ( p = htp->array ; p < end ; p++ ) {
    p->key = HASH_ENTRY_FREE ;
  }
}

References __hash_table::array, end, fprintf(), HASH_ENTRY_FREE, hash_entry::key, max_size_seen, __hash_table::n_entry, and __hash_table::size.

Referenced by atomizer_of_unstructured(), dag_terapix_reset_erosion(), free_callees_complexities(), gen_sharing_p(), init_statement_equivalence_table(), seq_rwt(), sesamify(), set_clear(), and shared_pointers().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_table_dump()

void hash_table_dump

(

const hash_table

htp

)

Definition at line 567 of file hash.c.

{
    size_t i;
 
    hash_table_print_header (htp,stderr);
 
    for (i = 0; i < htp->size; i++) {
        hash_entry he = htp->array[i];
 
        if (he.key != HASH_ENTRY_FREE && he.key != HASH_ENTRY_FREE_FOR_PUT)
          fprintf(stderr, "%zd: %p -> %p\n", i, he.key, he.val);
        else if(he.key == HASH_ENTRY_FREE && he.key != HASH_ENTRY_FREE_FOR_PUT)
          fprintf(stderr, "%zd: FREE\n", i);
        else
          fprintf(stderr, "%zd: FREE FOR PUT\n", i);
    }
}

References __hash_table::array, fprintf(), HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_table_print_header(), hash_entry::key, __hash_table::size, and hash_entry::val.

Here is the call graph for this function:

hash_table_entry_count()

int hash_table_entry_count

(

hash_table

htp

)

now we define observers in order to hide the hash_table type...

Definition at line 818 of file hash.c.

{
    return htp->n_entry;
}

References __hash_table::n_entry.

Referenced by aproximate_number_of_analyzed_variables(), controlize_distribution(), dag_to_flow_sensitive_preconditions(), davinci_print_non_deterministic_unstructured(), db_clean_all_required_resources(), db_module_exists_p(), make_global_common_and_initialize(), number_of_analyzed_values(), number_of_analyzed_variables(), print_control_postcondition_map(), print_statement_temporary_precondition(), replicate_cycles(), set_size(), test_mapping_entry_consistency(), and unstructured_to_flow_sensitive_postconditions_or_transformers().

Here is the caller graph for this function:

hash_table_equals_function()

hash_equals_t hash_table_equals_function

(

hash_table

h

)

Because the hash table data structure is hidden in this source file hash.c and not exported via the newgen_include.h, it is not possible to access its fields in other files, e.g.

set.c.

Definition at line 934 of file hash.c.

{
  return h->equals;
}

References __hash_table::equals.

Referenced by gen_set_closure_iterate().

Here is the caller graph for this function:

hash_table_fprintf()

void hash_table_fprintf	(	FILE *	f,
		gen_string_func_t	key_to_string,
		gen_string_func_t	value_to_string,
		const hash_table	htp
	)

This function prints the content of the hash_table pointed to by htp on file descriptor f, using functions key_to_string and value_to string to display the mapping.

it is mostly useful when debugging programs.

Definition at line 548 of file hash.c.

{
    size_t i;
 
    hash_table_print_header (htp,f);
 
    for (i = 0; i < htp->size; i++) {
        hash_entry he;
 
        he = htp->array[i];
 
        if (he.key != HASH_ENTRY_FREE && he.key != HASH_ENTRY_FREE_FOR_PUT) {
            fprintf(f, "%s -> %s\n",
                    key_to_string(he.key), value_to_string(he.val));
        }
    }
}

References __hash_table::array, f(), fprintf(), HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_table_print_header(), hash_entry::key, __hash_table::size, and hash_entry::val.

Referenced by print_value_mappings(), and statement_flatten_declarations().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_table_free()

void hash_table_free

(

hash_table

htp

)

this function deletes a hash table that is no longer useful.

unused memory is freed.

Definition at line 327 of file hash.c.

{
  // free allocated keys if necessary
  if (htp->delete_key)
  {
    size_t i;
    for (i=0; i<htp->size; i++)
      if (htp->array[i].key != HASH_ENTRY_FREE &&
          htp->array[i].key != HASH_ENTRY_FREE_FOR_PUT)
        htp->delete_key(htp->array[i].key);
  }
  gen_free_area((void**) htp->array, htp->size*sizeof(hash_entry));
  gen_free_area((void**) htp, sizeof(struct __hash_table));
}

References __hash_table::array, __hash_table::delete_key, gen_free_area(), HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_entry::key, and __hash_table::size.

Referenced by adg_dataflowgraph(), aliased_translation_p(), array_expansion(), bourdoncle_free(), bourdoncle_partition(), callgraph(), clean_enclosing_loops(), clean_stats_to_image(), clean_up_sequences_rewrite(), clone_statement(), close_processed_include_cache(), close_seen(), comEngine_distribute(), comEngine_distribute_code(), comEngine_feasability(), comEngine_generate_code(), comEngine_generate_HRECode(), comEngine_generate_procCode(), control_graph(), control_graph_to_interval_graph_format(), controlize_distribution(), controlize_forloop(), controlize_list(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_test(), controlize_whileloop(), da_process_list(), dag_terapix_measures(), davinci_dump_expression(), discard_statement_to_goto_table(), distribute(), do_isolate_statement(), do_linearize_array(), do_scalar_renaming_in_graph(), entity_basic_concrete_types_reset(), eov_free_ctx(), error_free_value_mappings(), expression_similar_get_context_p(), expression_similar_p(), FixCInternalLabels(), flint_free_statement_def_use_variables(), free_callees_complexities(), free_glopriv(), free_keyword_typedef_table(), free_obj_out(), free_statement_equivalence_table(), free_statement_matches_map(), freia_aipo_compile_calls(), freia_clean_image_occurrences(), freia_close_dep_cache(), freia_compile(), freia_dag_optimize(), freia_mppa_compile_calls(), freia_opencl_compile_calls(), freia_shuffle_move_forward(), freia_spoc_pipeline(), freia_terapix_call(), fs_filter(), fsi_sort(), fuse_sequences_in_unstructured(), gen_allocated_memory(), gen_free(), gen_free_tabulated(), gen_full_free_list(), gen_internal_context_multi_recurse(), gen_local_copy_tree(), gen_write_without_sharing(), generate_code(), generate_code_loop(), generic_print_xml_application(), get_any_comp_regions_text(), get_continuation_condition_text(), get_semantic_text(), hcfg(), HRE_distribute(), if_conversion_compact_stats(), init_statement_equivalence_table(), is_not_trivial_p(), loop_nest_to_wp65_code(), loop_statistics(), make_simd_statement(), maximal_out_degree_of_points_to_graph(), module_to_wp65_modules(), move_declaration_control_node_declarations_to_statement(), mppa_compile_dag(), outliner_parameters(), partition_to_unstructured(), phrase_remove_dependences_rwt(), pop_gen_trav_env(), print_code_or_source_comp(), reindexing(), remove_simple_scalar_pointers(), replace_entity(), replace_expression_similar_to_pattern(), reset_common_size_map(), reset_common_size_map_on_error(), reset_entity_to_size(), reset_entity_type_stack_table(), reset_ordering_to_statement(), reset_vector_to_expressions(), safe_reset_entity_to_size(), sc_delimiter(), scc_to_dag(), search_graph_bdt(), seq_rwt(), set_free(), sigmac_name_instances(), simd_memory_packing(), slightly_rename_entities(), sort_dfg_node(), sort_unknowns(), statement_dependence_graph(), statement_flatten_declarations(), step_install(), step_statement_path_finalize(), sww_seq_rwt(), text_unstructured(), top_down_abc_statement(), topologically_sorted_module_list(), type_structurally_equal_p(), typing_of_expressions(), unsplit_internal(), unstructured_shallow_copy(), and unstructured_to_complexity().

Here is the call graph for this function:

hash_table_generic_make()

hash_table hash_table_generic_make	(	hash_key_type	key_type,
		size_t	size,
		hash_equals_t	private_equal_p,
		hash_rank_t	private_rank
	)

this function makes a hash table of size size.

if size is less or equal to zero a default size is used. the type of keys is given by key_type (see hash.txt for further details; where is hash.txt?).

private_equal_p() is a predicate to decide if two elements are equal or not

private_rank() returns an integer in interval [0,size-1]

if private_equal_p(e1, e2) then private_rank(e1)==private_rank(e2) or results are unpredicatbale.

No functionality has been used or tested for hash_type==hash_private.

Definition at line 223 of file hash.c.

{
  size_t i;
  hash_table htp;
 
  if (size<HASH_DEFAULT_SIZE) size=HASH_DEFAULT_SIZE - 1;
  // get the next prime number in the table
  size = get_next_hash_table_size(size);
 
  htp = (hash_table) alloc(sizeof(struct __hash_table));
  message_assert("allocated", htp);
 
  htp->type = key_type;
  htp->size = size;
  htp->n_entry = 0;
  htp->limit = hash_size_limit(size);
  htp->array = (hash_entry*) alloc(size*sizeof(hash_entry));
 
  // initialize statistics
  htp->n_free_for_puts = 0;
  htp->n_put = 0;
  htp->n_get = 0;
  htp->n_del = 0;
  htp->n_upd = 0;
 
  htp->n_put_iter = 0;
  htp->n_get_iter = 0;
  htp->n_del_iter = 0;
  htp->n_upd_iter = 0;
 
  for (i = 0; i < size; i++)
    htp->array[i].key = HASH_ENTRY_FREE;
 
  htp->store_key = NULL;
  htp->delete_key = NULL;
 
  switch(key_type)
  {
  case hash_string:
    htp->equals = (int(*)(const void*,const void*)) hash_string_equal;
    htp->rank = hash_string_rank;
    htp->store_key = hash_store_string;
    htp->delete_key = hash_free_string;
    break;
  case hash_int:
    htp->equals = (int(*)(const void*,const void*)) hash_int_equal;
    htp->rank = hash_int_rank;
    break;
  case hash_chunk:
    htp->equals = (int(*)(const void*,const void*)) hash_chunk_equal;
    htp->rank = (_uint (*)(const void*, _uint)) hash_chunk_rank;
    break;
  case hash_pointer:
    htp->equals = hash_pointer_equal;
    htp->rank = hash_pointer_rank;
    break;
  case hash_private:
    htp->equals = private_equal_p;
    htp->rank = private_rank;
    break;
  default:
    fprintf(stderr, "[make_hash_table] bad type %d\n", key_type);
    abort();
  }
 
  return htp;
}

References abort, alloc(), __hash_table::array, __hash_table::delete_key, __hash_table::equals, fprintf(), get_next_hash_table_size(), hash_chunk, hash_chunk_equal(), hash_chunk_rank(), HASH_DEFAULT_SIZE, HASH_ENTRY_FREE, hash_free_string(), hash_int, hash_int_equal(), hash_int_rank(), hash_pointer, hash_pointer_equal(), hash_pointer_rank(), hash_private, hash_size_limit(), hash_store_string(), hash_string, hash_string_equal(), hash_string_rank(), int, hash_entry::key, __hash_table::limit, message_assert, __hash_table::n_del, __hash_table::n_del_iter, __hash_table::n_entry, __hash_table::n_free_for_puts, __hash_table::n_get, __hash_table::n_get_iter, __hash_table::n_put, __hash_table::n_put_iter, __hash_table::n_upd, __hash_table::n_upd_iter, __hash_table::rank, __hash_table::size, __hash_table::store_key, and __hash_table::type.

Referenced by hash_table_make(), and set_generic_make().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_table_make()

hash_table hash_table_make	(	hash_key_type	key_type,
		size_t	size
	)

Use default functions for equality check and rank computation.

Definition at line 294 of file hash.c.

{
  message_assert("key_type is not hash_private for this interface",
                 key_type!=hash_private);
  /* Use default functions for equality check and rank computation. */
  return hash_table_generic_make(key_type, size, NULL, NULL);
}

References hash_private, hash_table_generic_make(), and message_assert.

Referenced by adg_dataflowgraph(), adg_read_paf(), adg_reorder_statement_number(), aliased_translation_p(), allocate_number_to_statement(), allocate_value_mappings(), array_expansion(), bourdoncle_partition(), build_aliases(), build_options_menu_and_panel(), callgraph(), clean_enclosing_loops(), clean_up_sequences_rewrite(), clone_statement(), comEngine_distribute_code(), comEngine_feasability(), comEngine_generate_code(), comEngine_generate_HRECode(), comEngine_generate_procCode(), compute_communications(), compute_distribution_context(), compute_distribution_controlization_context(), compute_ordering_to_dg_mapping(), compute_statement_to_goto_table(), control_graph(), control_graph_to_interval_graph_format(), controlize_distribution(), controlize_forloop(), controlize_list(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_test(), controlize_whileloop(), copy_obj_out_constructed(), CreateIntrinsics(), da_process_list(), dag_terapix_measures(), davinci_dump_expression(), declarations_read(), do_HRE_memory_mapping_loop(), do_isolate_statement(), do_scalar_renaming_in_graph(), edge_weight(), entity_basic_concrete_types_init(), eov_make_ctx(), expression_similar_get_context_p(), expression_similar_p(), fetch_callees_complexities(), fetch_complexity_parameters(), FixCInternalLabels(), flint_initialize_statement_def_use_variables(), freia_aipo_compile_calls(), freia_allocate_new_images_if_needed(), freia_build_image_occurrences(), freia_compile(), freia_dag_optimize(), freia_init_dep_cache(), freia_mppa_compile_calls(), freia_opencl_compile_calls(), freia_scalar_rw_dep(), freia_shuffle_move_forward(), freia_spoc_pipeline(), freia_terapix_call(), fsi_sort(), fuse_sequences_in_unstructured(), gen_alloc_constructed(), gen_allocated_memory(), gen_free(), gen_free_tabulated(), gen_full_free_list(), gen_init_tabulated(), gen_internal_context_multi_recurse(), gen_local_copy_tree(), gen_sharing_p(), generate_code(), generic_print_xml_application(), get_methods(), gfc2pips_get_use_st(), hcfg(), HRE_distribute(), hwac_freia_api(), init_entity_type_storage_table(), init_expression_is_pointer(), init_intrinsic_handlers(), init_processed_include_cache(), init_seen(), init_statement_equivalence_table(), init_statement_matches_map(), init_vector_to_expressions(), initialize_common_size_map(), initialize_global_variables(), insert_mapping(), is_not_trivial_p(), kernel_data_mapping(), loop_nest_to_wp65_code(), loop_statistics(), make_keyword_typedef_table(), make_simd_statement(), maximal_out_degree_of_points_to_graph(), module_name_to_callees(), module_to_wp65_modules(), move_declaration_control_node_declarations_to_statement(), mppa_compile_dag(), new_glopriv(), normalize_microcode(), outliner_init(), outliner_smart_references_computation(), partition_to_unstructured(), phrase_remove_dependences_rwt(), pipsdbm_read_statement_mapping(), plc_make_dim(), plc_make_distance(), plc_make_min_dim(), plc_make_proto(), push_gen_trav_env(), register_scalar_communications(), reindexing(), remove_simple_scalar_pointers(), replace_entity(), restructure_if_then_else(), sc_delimiter(), scc_to_dag(), search_graph_bdt(), seq_rwt(), sesamify(), set_entity_to_size(), set_ordering_to_statement(), sigmac_name_instances(), simd_memory_packing(), simd_operator_mappings(), slightly_rename_entities(), sort_dfg_node(), sort_unknowns(), statement_dependence_graph(), statement_flatten_declarations(), statements_to_successors(), static_controlize(), step_install(), step_statement_path_init(), storage_space_of_variable(), sww_seq_rwt(), text_unstructured(), tiling_sequence(), top_down_abc_statement(), topologically_sorted_module_list(), type_structurally_equal_p(), typing_of_expressions(), unsplit_internal(), unstructured_shallow_copy(), and unstructured_to_complexity().

Here is the call graph for this function:

hash_table_own_allocated_memory()

int hash_table_own_allocated_memory

(

hash_table

htp

)

Definition at line 869 of file hash.c.

{
    return htp ?
      sizeof(struct __hash_table) + sizeof(hash_entry)*(htp->size) : 0 ;
}

References __hash_table::size.

Referenced by current_shared_obj_table_size(), and set_own_allocated_memory().

Here is the caller graph for this function:

hash_table_print()

void hash_table_print

(

hash_table

htp

)

this function prints the content of the hash_table pointed to by htp on stderr.

it is mostly useful when debugging programs.

Definition at line 525 of file hash.c.

{
  size_t i;
 
  hash_table_print_header (htp,stderr);
 
  for (i = 0; i < htp->size; i++) {
    hash_entry he;
 
    he = htp->array[i];
 
    if (he.key != HASH_ENTRY_FREE && he.key != HASH_ENTRY_FREE_FOR_PUT) {
      fprintf(stderr, "%zd %s %p\n",
              i, hash_print_key(htp->type, he.key),
              he.val);
    }
  }
}

References __hash_table::array, fprintf(), HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_print_key(), hash_table_print_header(), hash_entry::key, __hash_table::size, __hash_table::type, and hash_entry::val.

Here is the call graph for this function:

hash_table_print_header()

void hash_table_print_header	(	hash_table	htp,
		FILE *	fout
	)

this function prints the header of the hash_table pointed to by htp on the opened stream fout.

to be used by pips, we should not print this as it is only for debugging NewGen and it is not important data I (go) comment it. fprintf(fout, "limit %d\n", htp->limit);

Definition at line 510 of file hash.c.

{
  fprintf(fout, "hash_key_type:     %d\n", htp->type);
  fprintf(fout, "size:         %zd\n", htp->size);
  /* to be used by pips, we should not print this
     as it is only for debugging NewGen and it is not important data
     I (go) comment it.
     fprintf(fout, "limit    %d\n", htp->limit);
  */
  fprintf(fout, "n_entry: %zd\n", htp->n_entry);
}

References fprintf(), __hash_table::n_entry, __hash_table::size, and __hash_table::type.

Referenced by hash_table_dump(), hash_table_fprintf(), hash_table_print(), and transformer_map_print().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_table_rank_function()

hash_rank_t hash_table_rank_function

(

hash_table

h

)

Definition at line 939 of file hash.c.

{
  return h->rank;
}

References __hash_table::rank.

Referenced by gen_set_closure_iterate().

Here is the caller graph for this function:

hash_table_scan()

void* hash_table_scan	(	hash_table	htp,
		void *	hentryp_arg,
		void **	pkey,
		void **	pval
	)

Definition at line 844 of file hash.c.

{
  hash_entry * hentryp = (hash_entry *) hentryp_arg;
  hash_entry * hend = htp->array + htp->size;
 
  if (!hentryp) hentryp = (void*) htp->array;
 
  while (hentryp < hend)
  {
    void *key = hentryp->key;
 
    if ((key !=HASH_ENTRY_FREE) && (key !=HASH_ENTRY_FREE_FOR_PUT))
    {
      *pkey = key;
      if (pval) *pval = hentryp->val;
      return hentryp + 1;
    }
    hentryp++;
  }
  return NULL;
}

References __hash_table::array, HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_entry::key, __hash_table::size, and hash_entry::val.

Referenced by covers_labels_p(), do_expressions_to_vector(), init_statement_equivalence_table(), invalidate_expressions_in_statement(), make_simd_statement(), and move_declaration_control_node_declarations_to_statement().

Here is the caller graph for this function:

hash_table_size()

int hash_table_size

(

hash_table

htp

)

returns the size of the internal array.

Definition at line 825 of file hash.c.

{
    return htp->size;
}

References __hash_table::size.

hash_table_type()

hash_key_type hash_table_type

(

hash_table

htp

)

returns the type of the hash_table.

Definition at line 832 of file hash.c.

{
    return htp->type;
}

References __hash_table::type.

Referenced by copy_obj_out_constructed().

Here is the caller graph for this function:

hash_update()

void hash_update	(	hash_table	htp,
		const void *	key,
		const void *	val
	)

update key->val in htp, that MUST be pre-existent.

Definition at line 491 of file hash.c.

{
  hash_entry * hep;
  _uint n;
 
  message_assert("illegal input key",
                 key!=HASH_ENTRY_FREE && key!=HASH_ENTRY_FREE_FOR_PUT);
 
  htp->n_upd++;
  hep = hash_find_entry(htp, key, &n, &htp->n_upd_iter);
 
  message_assert("some previous entry", htp->equals(hep->key, key));
 
  hep->val = (void *) val;
}

References __hash_table::equals, HASH_ENTRY_FREE, HASH_ENTRY_FREE_FOR_PUT, hash_find_entry(), hash_entry::key, message_assert, __hash_table::n_upd, __hash_table::n_upd_iter, and hash_entry::val.

Referenced by add_synonym_values(), controlize_goto(), fuse_sequences_in_unstructured(), glc_call(), hash_overwrite(), init_label(), init_statement_equivalence_table(), maximal_out_degree_of_points_to_graph(), ref_count_rwt(), register_scalar_communications(), remove_cycle_dependencies(), reuse_pred_slot(), shared_obj(), shared_obj_in(), sigmac_name_instances(), statement_to_goto_table_flt(), update_common_to_size(), update_control_postcondition(), update_dfn(), update_temporary_precondition(), update_used_labels(), and use_output_slot().

Here is the call graph for this function:

Here is the caller graph for this function:

hash_warn_on_redefinition()

void hash_warn_on_redefinition

(

void

)

these function set the variable should_i_warn_on_redefinition to the value true or false

Definition at line 183 of file hash.c.

{
  should_i_warn_on_redefinition = true;
}

References should_i_warn_on_redefinition.

Referenced by comEngine_feasability(), deatomizer(), fetch_complexity_parameters(), make_scalar_integer_entity(), phrase_remove_dependences(), rice_dependence_graph(), set_union(), and static_controlize().

Here is the caller graph for this function:

hash_warn_on_redefinition_p()

bool hash_warn_on_redefinition_p

(

void

)

Definition at line 193 of file hash.c.

{
  return should_i_warn_on_redefinition;
}

References should_i_warn_on_redefinition.

Referenced by set_union().

Here is the caller graph for this function:

Variable Documentation

inc_prime_list

int inc_prime_list[]

static

Initial value:

= {
    2,   3,   5,  11,  13,  19,  23,  29,  31,  41,
   43,  47,  53,  59,  61,  67,  73,  79,  83,  89,
   97, 101, 103, 107, 109, 113, 127, 131, 139, 149,
  151
}

distinct primes for long cycle incremental search

Definition at line 717 of file hash.c.

Referenced by hash_find_entry().

max_size_seen

size_t max_size_seen = 0

static

Definition at line 302 of file hash.c.

Referenced by hash_table_clear().

prime_list

size_t prime_list[]

static

list of the prime numbers from 17 to 2^31-1 used as allocated size

Definition at line 118 of file hash.c.

Referenced by get_next_hash_table_size().

should_i_warn_on_redefinition

bool should_i_warn_on_redefinition = true

static

internal variable to know we should warm or not

Definition at line 178 of file hash.c.

Referenced by hash_dont_warn_on_redefinition(), hash_put(), hash_warn_on_redefinition(), and hash_warn_on_redefinition_p().