23 # define obstack_chunk_alloc malloc
24 # define obstack_chunk_free free
29 struct hash_ent *next;
31 typedef struct hash_ent HASH_ENT;
33 /* This is particularly useful to cast uses in hash_initialize of the
34 system free function. */
35 typedef void (*Hash_key_freer_type) (void *key);
39 /* User-supplied function for freeing keys. It is specified in
40 hash_initialize. If non-null, it is used by hash_free and
41 hash_clear. You should specify `free' here only if you want
42 these functions to free all of your `key' data. This is typically
43 the case when your key is simply an auxilliary struct that you
44 have malloc'd to aggregate several values. */
45 Hash_key_freer_type hash_key_freer;
47 /* User-supplied hash function that hashes entry E to an integer
48 in the range 0..TABLE_SIZE-1. */
49 unsigned int (*hash_hash) (const void *e, unsigned int table_size);
51 /* User-supplied function that determines whether a new entry is
52 unique by comparing the new entry to entries that hashed to the
53 same bucket index. It should return zero for a pair of entries
54 that compare equal, non-zero otherwise. */
56 int (*hash_key_comparator) (const void *, const void *);
58 HASH_ENT **hash_table;
59 unsigned int hash_table_size;
60 unsigned int hash_n_slots_used;
61 unsigned int hash_max_chain_length;
63 /* Gets set when an entry is deleted from a chain of length
64 hash_max_chain_length. Indicates that hash_max_chain_length
65 may no longer be valid. */
66 unsigned int hash_dirty_max_chain_length;
68 /* Sum of lengths of all chains (not counting any dummy
70 unsigned int hash_n_keys;
72 /* A linked list of freed HASH_ENT structs.
73 FIXME: Perhaps this is unnecessary and we should simply free
74 and reallocate such structs. */
75 HASH_ENT *hash_free_entry_list;
79 struct obstack ht_obstack;
86 hash_get_n_slots_used (const HT *ht);
89 hash_get_max_chain_length (HT *ht);
92 hash_rehash (HT *ht, unsigned int new_table_size);
95 hash_get_table_size (const HT *ht);
98 hash_initialize (unsigned int table_size,
99 void (*key_freer) (void *key),
100 unsigned int (*hash) (const void *, unsigned int),
101 int (*equality_tester) (const void *, const void *));
104 hash_get_n_keys (const HT *ht);
107 hash_query_in_table (const HT *ht, const void *e);
110 hash_lookup (const HT *ht, const void *e);
113 hash_insert_if_absent (HT *ht, const void *e, int *failed);
116 hash_delete_if_present (HT *ht, const void *e);
119 hash_print_statistics (const HT *ht, FILE *stream);
122 hash_get_statistics (const HT *ht, unsigned int *n_slots_used,
123 unsigned int *n_keys,
124 unsigned int *max_chain_length);
127 hash_table_ok (HT *ht);
130 hash_do_for_each (HT *ht, void (*f) (void *e, void *aux), void *aux);
133 hash_do_for_each_2 (HT *ht, int (*f) (void *e, void *aux), void *aux);
136 hash_do_for_each_in_selected_bucket (HT *ht, const void *key,
137 int (*f) (const void *bucket_key,
148 hash_get_key_list (const HT *ht, unsigned int bufsize, void **buf);
151 hash_get_first (const HT *ht);
154 hash_get_next (const HT *ht, const void *e);
156 /* This interface to hash_insert_if_absent is used frequently enough to
157 merit a macro here. */
159 # define HASH_INSERT_NEW_ITEM(Ht, Item, Failp) \
163 _already = hash_insert_if_absent ((Ht), (Item), Failp); \
164 assert (_already == NULL); \