lib/hash.h

   1 #ifndef HASH_H
   2 # define HASH_H 1
   3
   4 # if HAVE_CONFIG_H
   5 #  include <config.h>
   6 # endif
   7
   8 # include <stdio.h>
   9 # include <assert.h>
  10
  11 # ifdef STDC_HEADERS
  12 #  include <stdlib.h>
  13 # endif
  14
  15 # ifndef HAVE_DECL_FREE
  16 void free ();
  17 # endif
  18
  19 # ifndef HAVE_DECL_MALLOC
  20 char *malloc ();
  21 # endif
  22
  23 # ifndef PARAMS
  24 #  if defined PROTOTYPES || (defined __STDC__ && __STDC__)
  25 #   define PARAMS(Args) Args
  26 #  else
  27 #   define PARAMS(Args) ()
  28 #  endif
  29 # endif
  30
  31 # define USE_OBSTACK
  32 # ifdef USE_OBSTACK
  33 #  include "obstack.h"
  34 # endif
  35
  36 # define obstack_chunk_alloc malloc
  37 # define obstack_chunk_free free
  38
  39 struct hash_ent
  40   {
  41     void *key;
  42     struct hash_ent *next;
  43   };
  44 typedef struct hash_ent HASH_ENT;
  45
  46 /* This is particularly useful to cast uses in hash_initialize of the
  47    system free function.  */
  48 typedef void (*Hash_key_freer_type) PARAMS((void *key));
  49
  50 struct HT
  51   {
  52     /* User-supplied function for freeing keys.  It is specified in
  53        hash_initialize.  If non-null, it is used by hash_free and
  54        hash_clear.  You should specify `free' here only if you want
  55        these functions to free all of your `key' data.  This is typically
  56        the case when your key is simply an auxilliary struct that you
  57        have malloc'd to aggregate several values.   */
  58     Hash_key_freer_type hash_key_freer;
  59
  60     /* User-supplied hash function that hashes entry E to an integer
  61        in the range 0..TABLE_SIZE-1.  */
  62     unsigned int (*hash_hash) PARAMS((const void *e, unsigned int table_size));
  63
  64     /* User-supplied function that determines whether a new entry is
  65        unique by comparing the new entry to entries that hashed to the
  66        same bucket index.  It should return zero for a pair of entries
  67        that compare equal, non-zero otherwise.  */
  68
  69     int (*hash_key_comparator) PARAMS((const void *, const void *));
  70
  71     HASH_ENT **hash_table;
  72     unsigned int hash_table_size;
  73     unsigned int hash_n_slots_used;
  74     unsigned int hash_max_chain_length;
  75
  76     /* Gets set when an entry is deleted from a chain of length
  77        hash_max_chain_length.  Indicates that hash_max_chain_length
  78        may no longer be valid.  */
  79     unsigned int hash_dirty_max_chain_length;
  80
  81     /* Sum of lengths of all chains (not counting any dummy
  82        header entries).  */
  83     unsigned int hash_n_keys;
  84
  85     /* A linked list of freed HASH_ENT structs.
  86        FIXME: Perhaps this is unnecessary and we should simply free
  87        and reallocate such structs.  */
  88     HASH_ENT *hash_free_entry_list;
  89
  90     /* FIXME: comment.  */
  91 # ifdef USE_OBSTACK
  92     struct obstack ht_obstack;
  93 # endif
  94   };
  95
  96 typedef struct HT HT;
  97
  98 unsigned int
  99   hash_get_n_slots_used PARAMS((const HT *ht));
 100
 101 unsigned int
 102   hash_get_max_chain_length PARAMS((HT *ht));
 103
 104 int
 105   hash_rehash PARAMS((HT *ht, unsigned int new_table_size));
 106
 107 unsigned int
 108   hash_get_table_size PARAMS((const HT *ht));
 109
 110 HT *
 111   hash_initialize PARAMS((unsigned int table_size,
 112                           void (*key_freer) PARAMS((void *key)),
 113                           unsigned int (*hash) PARAMS((const void *,
 114                                                        unsigned int)),
 115                           int (*equality_tester) PARAMS((const void *,
 116                                                          const void *))));
 117
 118 unsigned int
 119   hash_get_n_keys PARAMS((const HT *ht));
 120
 121 int
 122   hash_query_in_table PARAMS((const HT *ht, const void *e));
 123
 124 void *
 125   hash_lookup PARAMS((const HT *ht, const void *e));
 126
 127 void *
 128   hash_insert_if_absent PARAMS((HT *ht,
 129                                 const void *e,
 130                                 int *failed));
 131
 132 void *
 133   hash_delete_if_present PARAMS((HT *ht, const void *e));
 134
 135 void
 136   hash_print_statistics PARAMS((const HT *ht, FILE *stream));
 137
 138 int
 139   hash_get_statistics PARAMS((const HT *ht, unsigned int *n_slots_used,
 140                               unsigned int *n_keys,
 141                               unsigned int *max_chain_length));
 142
 143 int
 144   hash_table_ok PARAMS((HT *ht));
 145
 146 void
 147   hash_do_for_each PARAMS((HT *ht,
 148                            void (*f) PARAMS((void *e, void *aux)),
 149                            void *aux));
 150
 151 int
 152   hash_do_for_each_2 PARAMS((HT *ht,
 153                              int (*f) PARAMS((void *e, void *aux)),
 154                              void *aux));
 155
 156 int
 157   hash_do_for_each_in_selected_bucket PARAMS((HT *ht,
 158                                               const void *key,
 159                                       int (*f) PARAMS((const void *bucket_key,
 160                                                        void *e,
 161                                                        void *aux)),
 162                                               void *aux));
 163
 164 void
 165   hash_clear PARAMS((HT *ht));
 166
 167 void
 168   hash_free PARAMS((HT *ht));
 169
 170 void
 171   hash_get_key_list PARAMS((const HT *ht,
 172                             unsigned int bufsize,
 173                             void **buf));
 174
 175 void *
 176   hash_get_first PARAMS((const HT *ht));
 177
 178 void *
 179   hash_get_next PARAMS((const HT *ht, const void *e));
 180
 181 /* This interface to hash_insert_if_absent is used frequently enough to
 182    merit a macro here.  */
 183
 184 # define HASH_INSERT_NEW_ITEM(Ht, Item, Failp)                          \
 185   do                                                                    \
 186     {                                                                   \
 187       void *_already;                                                   \
 188       _already = hash_insert_if_absent ((Ht), (Item), Failp);           \
 189       assert (_already == NULL);                                        \
 190     }                                                                   \
 191   while (0)
 192
 193 #endif /* HASH_H */