X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/68bd3b6bfa120d0775bbac310c8a047a31c07886..f5e211a120f1e508a98ce8e6b823c3750b0cfeed:/lib/hash.h diff --git a/lib/hash.h b/lib/hash.h index 56618931..a9fc1876 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -1,6 +1,6 @@ -/* hash.h -- decls for hash table - Copyright (C) 1995 Free Software Foundation, Inc. - Written by Greg McGary +/* hash - hashing table processing. + Copyright (C) 1998, 1999, 2001 Free Software Foundation, Inc. + Written by Jim Meyering , 1998. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -13,132 +13,81 @@ GNU General Public License for more details. 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. */ - -#ifndef _hash_h_ -#define _hash_h_ - -#include - -typedef unsigned long (*hash_func_t) __P((void const *key)); -typedef int (*hash_cmp_func_t) __P((void const *x, void const *y)); -typedef void (*hash_map_func_t) __P((void const *item)); - -struct hash_table -{ - void **ht_vec; - unsigned long ht_size; /* total number of slots (power of 2) */ - unsigned long ht_capacity; /* usable slots, limited by loading-factor */ - unsigned long ht_fill; /* items in table */ - unsigned long ht_collisions; /* # of failed calls to comparison function */ - unsigned long ht_lookups; /* # of queries */ - unsigned int ht_rehashes; /* # of times we've expanded table */ - hash_func_t ht_hash_1; /* primary hash function */ - hash_func_t ht_hash_2; /* secondary hash function */ - hash_cmp_func_t ht_compare; /* comparison function */ -}; - -typedef int (*qsort_cmp_t) __P((void const *, void const *)); - -void hash_init __P((struct hash_table *ht, unsigned long size, - hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)); -void hash_load __P((struct hash_table *ht, void *item_table, - unsigned long cardinality, unsigned long size)); -void **hash_find_slot __P((struct hash_table *ht, void const *key)); -void *hash_find_item __P((struct hash_table *ht, void const *key)); -void *hash_insert __P((struct hash_table *ht, void *item)); -void *hash_insert_at __P((struct hash_table *ht, void *item, void const *slot)); -void *hash_delete __P((struct hash_table *ht, void const *item)); -void *hash_delete_at __P((struct hash_table *ht, void const *slot)); -void hash_delete_items __P((struct hash_table *ht)); -void hash_free_items __P((struct hash_table *ht)); -void hash_free __P((struct hash_table *ht, int free_items)); -void hash_map __P((struct hash_table *ht, hash_map_func_t map)); -void hash_print_stats __P((struct hash_table *ht, FILE *out_FILE)); -void **hash_dump __P((struct hash_table *ht, void **vector_0, qsort_cmp_t compare)); - -extern void *hash_deleted_item; -#define HASH_VACANT(item) ((item) == 0 || (void *) (item) == hash_deleted_item) - - -/* hash and comparison macros for string keys. */ - -#define STRING_HASH_1(_key_, _result_) { \ - unsigned char const *kk = (unsigned char const *) (_key_) - 1; \ - while (*++kk) \ - (_result_) += (*kk << (kk[1] & 0xf)); \ -} while (0) -#define return_STRING_HASH_1(_key_) do { \ - unsigned long result = 0; \ - STRING_HASH_1 ((_key_), result); \ - return result; \ -} while (0) - -#define STRING_HASH_2(_key_, _result_) do { \ - unsigned char const *kk = (unsigned char const *) (_key_) - 1; \ - while (*++kk) \ - (_result_) += (*kk << (kk[1] & 0x7)); \ -} while (0) -#define return_STRING_HASH_2(_key_) do { \ - unsigned long result = 0; \ - STRING_HASH_2 ((_key_), result); \ - return result; \ -} while (0) - -#define STRING_COMPARE(_x_, _y_, _result_) do { \ - unsigned char const *xx = (unsigned char const *) (_x_) - 1; \ - unsigned char const *yy = (unsigned char const *) (_y_) - 1; \ - do { \ - if (*++xx == '\0') { \ - yy++; \ - break; \ - } \ - } while (*xx == *++yy); \ - (_result_) = *xx - *yy; \ -} while (0) -#define return_STRING_COMPARE(_x_, _y_) do { \ - int result; \ - STRING_COMPARE (_x_, _y_, result); \ - return result; \ -} while (0) - -/* hash and comparison macros for integer keys. */ - -#define INTEGER_HASH_1(_key_, _result_) do { \ - (_result_) += ((unsigned long)(_key_)); \ -} while (0) -#define return_INTEGER_HASH_1(_key_) do { \ - unsigned long result = 0; \ - INTEGER_HASH_1 ((_key_), result); \ - return result; \ -} while (0) - -#define INTEGER_HASH_2(_key_, _result_) do { \ - (_result_) += ~((unsigned long)(_key_)); \ -} while (0) -#define return_INTEGER_HASH_2(_key_) do { \ - unsigned long result = 0; \ - INTEGER_HASH_2 ((_key_), result); \ - return result; \ -} while (0) - -#define INTEGER_COMPARE(_x_, _y_, _result_) do { \ - (_result_) = _x_ - _y_; \ -} while (0) -#define return_INTEGER_COMPARE(_x_, _y_) do { \ - int result; \ - INTEGER_COMPARE (_x_, _y_, result); \ - return result; \ -} while (0) - -/* hash and comparison macros for address keys. */ - -#define ADDRESS_HASH_1(_key_, _result_) INTEGER_HASH_1 (((unsigned long)(_key_)) >> 3, (_result_)) -#define ADDRESS_HASH_2(_key_, _result_) INTEGER_HASH_2 (((unsigned long)(_key_)) >> 3, (_result_)) -#define ADDRESS_COMPARE(_x_, _y_, _result_) INTEGER_COMPARE ((_x_), (_y_), (_result_)) -#define return_ADDRESS_HASH_1(_key_) return_INTEGER_HASH_1 (((unsigned long)(_key_)) >> 3) -#define return_ADDRESS_HASH_2(_key_) return_INTEGER_HASH_2 (((unsigned long)(_key_)) >> 3) -#define return_ADDRESS_COMPARE(_x_, _y_) return_INTEGER_COMPARE ((_x_), (_y_)) - -#endif /* not _hash_h_ */ + along with this program; if not, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 HASH_H_ +# define HASH_H_ + +# ifndef PARAMS +# if PROTOTYPES || __STDC__ +# define PARAMS(Args) Args +# else +# define PARAMS(Args) () +# endif +# endif + +typedef unsigned (*Hash_hasher) PARAMS ((const void *, unsigned)); +typedef bool (*Hash_comparator) PARAMS ((const void *, const void *)); +typedef void (*Hash_data_freer) PARAMS ((void *)); +typedef bool (*Hash_processor) PARAMS ((void *, void *)); + +struct hash_entry + { + void *data; + struct hash_entry *next; + }; + +struct hash_tuning + { + /* 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 hash_get_n_buckets PARAMS ((const Hash_table *)); +unsigned hash_get_n_buckets_used PARAMS ((const Hash_table *)); +unsigned hash_get_n_entries PARAMS ((const Hash_table *)); +unsigned 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 *)); + +/* Walking. */ +void *hash_get_first PARAMS ((const Hash_table *)); +void *hash_get_next PARAMS ((const Hash_table *, const void *)); +unsigned hash_get_entries PARAMS ((const Hash_table *, void **, unsigned)); +unsigned hash_do_for_each PARAMS ((const Hash_table *, Hash_processor, void *)); + +/* Allocation and clean-up. */ +unsigned hash_string PARAMS ((const char *, unsigned)); +void hash_reset_tuning PARAMS ((Hash_tuning *)); +Hash_table *hash_initialize PARAMS ((unsigned, const Hash_tuning *, + Hash_hasher, Hash_comparator, + Hash_data_freer)); +void hash_clear PARAMS ((Hash_table *)); +void hash_free PARAMS ((Hash_table *)); + +/* Insertion and deletion. */ +bool hash_rehash PARAMS ((Hash_table *, unsigned)); +void *hash_insert PARAMS ((Hash_table *, const void *)); +void *hash_delete PARAMS ((Hash_table *, const void *)); + +#endif