52 #define HASH_ENTRY_FREE ((void *) 0)
53 #define HASH_ENTRY_FREE_FOR_PUT ((void *) -1)
60 typedef void * (*hash_key_func_t)(
const void *);
83 #define END_OF_SIZE_TABLE (0)
91 #define RANK(key, size) ((((_uint)(key)) ^ 0xC001BabeFab1C0e1LLU)%(size))
94 #define RANK(key, size) ((((_uint)(key)) ^ 0xfab1c0e1U)%(size))
169 while (*p_prime <= size) {
238 htp->
type = key_type;
256 for (i = 0; i < size; i++)
283 htp->
equals = private_equal_p;
284 htp->
rank = private_rank;
287 fprintf(stderr,
"[make_hash_table] bad type %d\n", key_type);
319 for ( p = htp->
array ; p <
end ; p++ ) {
333 for (i=0; i<htp->
size; i++)
381 (void)
fprintf(stderr,
"[hash_put] key redefined: %s\n",
384 hep->
val = (
void *) val;
391 hep->
val = (
void *) val;
504 hep->
val = (
void *) val;
531 for (i = 0; i < htp->
size; i++) {
555 for (i = 0; i < htp->
size; i++) {
562 key_to_string(he.
key), value_to_string(he.
val));
573 for (i = 0; i < htp->
size; i++) {
579 fprintf(stderr,
"%zd: FREE\n", i);
581 fprintf(stderr,
"%zd: FREE FOR PUT\n", i);
596 old_size = htp->
size;
597 old_array = htp->
array;
605 for (i = 0; i < htp->
size ; i++)
608 for (i = 0; i < old_size; i++)
621 fprintf(stderr,
"[hash_enlarge_table] fatal error\n");
646 for (s = (
char*) key; *s; s++)
647 v = ((v<<7) | (v>>25)) ^ *s;
654 return RANK(key, size);
659 return RANK(key, size);
664 return RANK(key->
i, size);
672 for(; *key1 && *key2; key1++, key2++)
680 return ((
_int) key1) == ((
_int) key2);
690 return key1->
p == key2->
p;
704 sprintf(
buffer,
"%p", key);
708 fprintf(stderr,
"[hash_print_key] bad type : %d\n", t);
718 2, 3, 5, 11, 13, 19, 23, 29, 31, 41,
719 43, 47, 53, 59, 61, 67, 73, 79, 83, 89,
720 97, 101, 103, 107, 109, 113, 127, 131, 139, 149,
724 #define HASH_INC_SIZE (31)
736 r_init = (*(htp->
rank))(key, htp->
size),
748 r_first_free = r_init;
749 bool first_free_found =
false;
768 if (stats) (*stats)++;
777 if (first_free_found)
787 first_free_found =
true;
798 r = (r + r_inc) % htp->
size;
812 return &(htp->
array[r]);
852 if (!hentryp) hentryp = (
void*) htp->
array;
854 while (hentryp < hend)
856 void *key = hentryp->
key;
861 if (pval) *pval = hentryp->
val;
884 fatal(
"no value correspond to key %p", k);
912 message_assert(
"defined value (entry to delete must be defined!)",
void const char const char const int
char * alloc(int size)
ALLOC is an "iron-clad" version of malloc(3).
static int current_size
returns the number of bytes allocated for a given structure may need additional fonctions for externa...
#define NIL
The empty list (nil in Lisp)
void gen_free_area(void **p, int size)
free an area.
static size_t hash_size_limit(size_t current_size)
returns the maximum number of things to hold in a table
static bool should_i_warn_on_redefinition
internal variable to know we should warm or not
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,...
void hash_dont_warn_on_redefinition(void)
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 n...
hash_table hash_table_make(hash_key_type key_type, size_t size)
void hash_table_print(hash_table htp)
this function prints the content of the hash_table pointed to by htp on stderr.
void *(* hash_key_func_t)(const void *)
static size_t max_size_seen
bool hash_warn_on_redefinition_p(void)
int hash_table_own_allocated_memory(hash_table htp)
#define HASH_ENTRY_FREE_FOR_PUT
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.
static _uint hash_pointer_rank(const void *, size_t)
static size_t prime_list[]
list of the prime numbers from 17 to 2^31-1 used as allocated size
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.
void hash_warn_on_redefinition(void)
these function set the variable should_i_warn_on_redefinition to the value true or false
static _uint hash_chunk_rank(const gen_chunk *, size_t)
#define END_OF_SIZE_TABLE
Constant to find the end of the prime numbers table.
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.
static _uint hash_int_rank(const void *, size_t)
static int inc_prime_list[]
distinct primes for long cycle incremental search
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.
void hash_update(hash_table htp, const void *key, const void *val)
update key->val in htp, that MUST be pre-existent.
static void hash_enlarge_table(hash_table htp)
Private functions.
int hash_table_size(hash_table htp)
returns the size of the internal array.
void hash_overwrite(hash_table htp, const void *key, const void *val)
hash_put which allows silent overwrite...
static void * hash_store_string(const void *s)
static hash_entry * hash_find_entry(const hash_table htp, const void *key, _uint *prank, _uint *stats)
return where the key is [to be] stored, depending on the operation.
static int hash_int_equal(const void *, const void *)
static int hash_pointer_equal(const void *, const void *)
void hash_table_free(hash_table htp)
this function deletes a hash table that is no longer useful.
bool hash_defined_p(const hash_table htp, const void *key)
true if key has e value in htp.
static int hash_chunk_equal(const gen_chunk *, const gen_chunk *)
#define RANK(key, size)
Hash function to get the index of the array from the key.
static int hash_string_equal(const char *, const char *)
void * hash_map_get(const hash_table h, const void *k)
newgen mapping to newgen hash...
void hash_table_dump(const hash_table htp)
void hash_map_update(hash_table h, const void *k, const void *v)
hash_key_type hash_table_type(hash_table htp)
returns the type of the hash_table.
hash_rank_t hash_table_rank_function(hash_table h)
void * hash_map_del(hash_table h, const void *k)
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.
#define HASH_ENTRY_FREE
Some predefined values for the key.
void(* hash_free_func_t)(void *)
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.
_uint hash_string_rank(const void *, size_t)
en s'inspirant vaguement de Fast Hashing of Variable-Length Text Strings Peter K.
static string hash_print_key(hash_key_type, const void *)
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_delget(hash_table htp, const void *key, void **pkey)
deletes key from the hash table.
int hash_table_entry_count(hash_table htp)
now we define observers in order to hide the hash_table type...
void * hash_table_scan(hash_table htp, void *hentryp_arg, void **pkey, void **pval)
static size_t get_next_hash_table_size(size_t size)
Now we need the table size to be a prime number.
void hash_table_clear(hash_table htp)
Clears all entries of a hash table HTP.
#define message_assert(msg, ex)
hash_key_type
Equality and rank functions are provided for strings, integers, pointers and Newgen chunks.
_uint(* hash_rank_t)(const void *, size_t)
#define HASH_UNDEFINED_VALUE
value returned by hash_get() when the key is not found; could also be called HASH_KEY_NOT_FOUND,...
int(* hash_equals_t)(const void *, const void *)
#define HASH_DEFAULT_SIZE
struct __hash_table * hash_table
Define hash_table structure which is hidden.
string(* gen_string_func_t)(const void *)
int f(int off1, int off2, int n, float r[n], float a[n], float b[n])
int fprintf()
test sc_min : ce test s'appelle par : programme fichier1.data fichier2.data ...
size_t n_free_for_puts
keep statistics on the life time of the hash table...
hash_key_func_t store_key
hash_free_func_t delete_key
The structure used to build lists in NewGen.
A gen_chunk is used to store every object.
void * e
For externals (foreign objects)