PIPS
|
#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"
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... | |
#define END_OF_SIZE_TABLE (0) |
#define HASH_ENTRY_FREE ((void *) 0) |
#define HASH_INC_SIZE (31) /**31... (yes, this one is prime;-) */ |
#define RANK | ( | key, | |
size | |||
) | ((((_uint)(key)) ^ 0xfab1c0e1U)%(size)) |
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.
References END_OF_SIZE_TABLE, message_assert, and prime_list.
Referenced by hash_enlarge_table(), and hash_table_generic_make().
Definition at line 688 of file hash.c.
References gen_chunk::p.
Referenced by hash_table_generic_make().
Definition at line 662 of file hash.c.
References gen_chunk::i, and RANK.
Referenced by hash_table_generic_make().
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.
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().
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.
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().
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.
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().
void hash_dont_warn_on_redefinition | ( | void | ) |
Definition at line 188 of file hash.c.
References should_i_warn_on_redefinition.
Referenced by comEngine_feasability(), deatomizer(), phrase_remove_dependences(), set_union(), and topologically_sorted_module_list().
|
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.
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().
|
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.
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().
|
static |
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.
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().
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.
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().
|
static |
Definition at line 678 of file hash.c.
Referenced by hash_table_generic_make().
Definition at line 652 of file hash.c.
References RANK.
Referenced by hash_table_generic_make().
bool hash_map_defined_p | ( | const hash_table | h, |
const void * | k | ||
) |
Definition at line 888 of file hash.c.
References gen_chunk::e, and hash_defined_p().
void* hash_map_del | ( | hash_table | h, |
const void * | k | ||
) |
Definition at line 905 of file hash.c.
References gen_chunk::e, free(), hash_delget(), HASH_UNDEFINED_VALUE, message_assert, NEWGEN_FREED, and gen_chunk::p.
Referenced by hash_map_update().
void* hash_map_get | ( | const hash_table | h, |
const void * | k | ||
) |
newgen mapping to newgen hash...
Definition at line 878 of file hash.c.
References gen_chunk::e, fatal(), hash_get(), and HASH_UNDEFINED_VALUE.
void hash_map_put | ( | hash_table | h, |
const void * | k, | ||
const void * | v | ||
) |
Definition at line 895 of file hash.c.
References alloc(), gen_chunk::e, and hash_put().
Referenced by hash_map_update().
void hash_map_update | ( | hash_table | h, |
const void * | k, | ||
const void * | v | ||
) |
Definition at line 925 of file hash.c.
References hash_map_del(), and hash_map_put().
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.
References hash_defined_p(), hash_put(), and hash_update().
Referenced by overwrite_ordering_of_the_statement_to_current_mapping().
|
static |
Definition at line 683 of file hash.c.
Referenced by hash_table_generic_make().
Definition at line 657 of file hash.c.
References RANK.
Referenced by hash_table_generic_make().
|
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.
References abort, buffer, fprintf(), hash_chunk, hash_int, hash_pointer, hash_private, and hash_string.
Referenced by hash_put(), and hash_table_print().
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.
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().
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.
References current_size.
Referenced by hash_enlarge_table(), and hash_table_generic_make().
|
static |
|
static |
else check contents
Definition at line 667 of file hash.c.
Referenced by hash_table_generic_make().
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.
Referenced by control_rank(), hash_table_generic_make(), and points_to_rank().
void hash_table_clear | ( | hash_table | htp | ) |
Clears all entries of a hash table HTP.
[pj]
Definition at line 305 of file hash.c.
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().
void hash_table_dump | ( | const hash_table | htp | ) |
Definition at line 567 of file hash.c.
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.
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.
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().
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.
Definition at line 934 of file hash.c.
References __hash_table::equals.
Referenced by gen_set_closure_iterate().
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.
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().
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.
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().
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.
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().
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.
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().
int hash_table_own_allocated_memory | ( | hash_table | htp | ) |
Definition at line 869 of file hash.c.
References __hash_table::size.
Referenced by current_shared_obj_table_size(), and set_own_allocated_memory().
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.
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.
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.
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().
hash_rank_t hash_table_rank_function | ( | hash_table | h | ) |
Definition at line 939 of file hash.c.
References __hash_table::rank.
Referenced by gen_set_closure_iterate().
void* hash_table_scan | ( | hash_table | htp, |
void * | hentryp_arg, | ||
void ** | pkey, | ||
void ** | pval | ||
) |
Definition at line 844 of file hash.c.
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().
int hash_table_size | ( | hash_table | htp | ) |
returns the size of the internal array.
Definition at line 825 of file hash.c.
References __hash_table::size.
hash_key_type hash_table_type | ( | hash_table | htp | ) |
returns the type of the hash_table.
Definition at line 832 of file hash.c.
References __hash_table::type.
Referenced by copy_obj_out_constructed().
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.
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().
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.
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().
bool hash_warn_on_redefinition_p | ( | void | ) |
Definition at line 193 of file hash.c.
References should_i_warn_on_redefinition.
Referenced by set_union().
|
static |
distinct primes for long cycle incremental search
Definition at line 717 of file hash.c.
Referenced by hash_find_entry().
|
static |
Definition at line 302 of file hash.c.
Referenced by hash_table_clear().
|
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().
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().