X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fhash.h;h=ab63a863fd0c83899087f6bdbdeff3c9bc9c67ca;hb=d9e80c64c98313550d5103d8cfb22601a800e62d;hp=0cbb27e3afe822354a9a442eaadceb7adf457018;hpb=a273f0ec555a11c02e071bdd6f2477f37360ac6f;p=gnulib.git diff --git a/lib/hash.h b/lib/hash.h index 0cbb27e3a..ab63a863f 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -1,5 +1,5 @@ /* hash - hashing table processing. - Copyright (C) 1998 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2001, 2003 Free Software Foundation, Inc. Written by Jim Meyering , 1998. This program is free software; you can redistribute it and/or modify @@ -14,25 +14,23 @@ You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, - Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ /* A generic hash table package. */ /* Make sure USE_OBSTACK is defined to 1 if you want the allocator to use obstacks instead of malloc, and recompile `hash.c' with same setting. */ -#ifndef PARAMS -# if PROTOTYPES || __STDC__ -# define PARAMS(Args) Args -# else -# define PARAMS(Args) () -# endif -#endif +#ifndef HASH_H_ +# define HASH_H_ + +# include +# include -typedef unsigned int (*Hash_hasher) PARAMS ((const void *, unsigned int)); -typedef bool (*Hash_comparator) PARAMS ((const void *, const void *)); -typedef void (*Hash_data_freer) PARAMS ((void *)); -typedef bool (*Hash_processor) PARAMS ((void *, void *)); +typedef size_t (*Hash_hasher) (const void *, size_t); +typedef bool (*Hash_comparator) (const void *, const void *); +typedef void (*Hash_data_freer) (void *); +typedef bool (*Hash_processor) (void *, void *); struct hash_entry { @@ -40,64 +38,51 @@ struct hash_entry struct hash_entry *next; }; -struct hash_table +struct hash_tuning { - /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1, - for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets - are not empty, there are N_ENTRIES active entries in the table. */ - struct hash_entry *bucket; - struct hash_entry *bucket_limit; - unsigned int n_buckets; - unsigned int n_buckets_used; - unsigned int n_entries; - - /* Three functions are given to `hash_initialize', see the documentation - block for this function. In a word, HASHER randomizes a user entry - into a number up from 0 up to some maximum minus 1; COMPARATOR returns - true if two user entries compare equally; and DATA_FREER is the cleanup - function for a user entry. */ - Hash_hasher hasher; - Hash_comparator comparator; - Hash_data_freer data_freer; - - /* A linked list of freed struct hash_entry structs. */ - struct hash_entry *free_entry_list; - -#if USE_OBSTACK - /* Whenever obstacks are used, it is possible to allocate all overflowed - entries into a single stack, so they all can be freed in a single - operation. It is not clear if the speedup is worth the trouble. */ - struct obstack entry_stack; -#endif + /* This structure is mainly used for `hash_initialize', see the block + documentation of `hash_reset_tuning' for more complete comments. */ + + float shrink_threshold; /* ratio of used buckets to trigger a shrink */ + float shrink_factor; /* ratio of new smaller size to original size */ + float growth_threshold; /* ratio of used buckets to trigger a growth */ + float growth_factor; /* ratio of new bigger size to original size */ + bool is_n_buckets; /* if CANDIDATE really means table size */ }; +typedef struct hash_tuning Hash_tuning; + +struct hash_table; + typedef struct hash_table Hash_table; /* Information and lookup. */ -unsigned int hash_get_n_buckets PARAMS ((const Hash_table *)); -unsigned int hash_get_n_buckets_used PARAMS ((const Hash_table *)); -unsigned int hash_get_n_entries PARAMS ((const Hash_table *)); -unsigned int hash_get_max_bucket_length PARAMS ((const Hash_table *)); -bool hash_table_ok PARAMS ((const Hash_table *)); -void hash_print_statistics PARAMS ((const Hash_table *, FILE *)); -void *hash_lookup PARAMS ((const Hash_table *, const void *)); +size_t hash_get_n_buckets (const Hash_table *); +size_t hash_get_n_buckets_used (const Hash_table *); +size_t hash_get_n_entries (const Hash_table *); +size_t hash_get_max_bucket_length (const Hash_table *); +bool hash_table_ok (const Hash_table *); +void hash_print_statistics (const Hash_table *, FILE *); +void *hash_lookup (const Hash_table *, const void *); /* Walking. */ -void *hash_get_first PARAMS ((const Hash_table *)); -void *hash_get_next PARAMS ((const Hash_table *, const void *)); -unsigned int hash_get_entries PARAMS ((const Hash_table *, void **, - unsigned int)); -unsigned int hash_do_for_each PARAMS ((const Hash_table *, Hash_processor, - void *)); +void *hash_get_first (const Hash_table *); +void *hash_get_next (const Hash_table *, const void *); +size_t hash_get_entries (const Hash_table *, void **, size_t); +size_t hash_do_for_each (const Hash_table *, Hash_processor, void *); /* Allocation and clean-up. */ -unsigned int hash_string PARAMS ((const char *, unsigned int)); -Hash_table *hash_initialize PARAMS ((unsigned int, Hash_hasher, - Hash_comparator, Hash_data_freer)); -void hash_clear PARAMS ((Hash_table *)); -void hash_free PARAMS ((Hash_table *)); +size_t hash_string (const char *, size_t); +void hash_reset_tuning (Hash_tuning *); +Hash_table *hash_initialize (size_t, const Hash_tuning *, + Hash_hasher, Hash_comparator, + Hash_data_freer); +void hash_clear (Hash_table *); +void hash_free (Hash_table *); /* Insertion and deletion. */ -bool hash_rehash PARAMS ((Hash_table *, unsigned int)); -void *hash_insert PARAMS ((Hash_table *, const void *, bool *)); -void *hash_delete PARAMS ((Hash_table *, const void *)); +bool hash_rehash (Hash_table *, size_t); +void *hash_insert (Hash_table *, const void *); +void *hash_delete (Hash_table *, const void *); + +#endif