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 # else
  14 void free ();
  15 char *malloc ();
  16 # endif
  17
  18 # define USE_OBSTACK
  19 # ifdef USE_OBSTACK
  20 #  include "obstack.h"
  21 # endif
  22
  23 # define obstack_chunk_alloc malloc
  24 # define obstack_chunk_free free
  25
  26 struct hash_ent
  27   {
  28     void *key;
  29     struct hash_ent *next;
  30   };
  31 typedef struct hash_ent HASH_ENT;
  32
  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);
  36
  37 struct HT
  38   {
  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;
  46
  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);
  50
  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.  */
  55
  56     int (*hash_key_comparator) (const void *, const void *);
  57
  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;
  62
  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;
  67
  68     /* Sum of lengths of all chains (not counting any dummy
  69        header entries).  */
  70     unsigned int hash_n_keys;
  71
  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;
  76
  77     /* FIXME: comment.  */
  78 # ifdef USE_OBSTACK
  79     struct obstack ht_obstack;
  80 # endif
  81   };
  82
  83 typedef struct HT HT;
  84
  85 unsigned int
  86   hash_get_n_slots_used (const HT *ht);
  87
  88 unsigned int
  89   hash_get_max_chain_length (HT *ht);
  90
  91 int
  92   hash_rehash (HT *ht, unsigned int new_table_size);
  93
  94 unsigned int
  95   hash_get_table_size (const HT *ht);
  96
  97 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 *));
 102
 103 unsigned int
 104   hash_get_n_keys (const HT *ht);
 105
 106 int
 107   hash_query_in_table (const HT *ht, const void *e);
 108
 109 void *
 110   hash_lookup (const HT *ht, const void *e);
 111
 112 void *
 113   hash_insert_if_absent (HT *ht, const void *e, int *failed);
 114
 115 void *
 116   hash_delete_if_present (HT *ht, const void *e);
 117
 118 void
 119   hash_print_statistics (const HT *ht, FILE *stream);
 120
 121 int
 122   hash_get_statistics (const HT *ht, unsigned int *n_slots_used,
 123                        unsigned int *n_keys,
 124                        unsigned int *max_chain_length);
 125
 126 int
 127   hash_table_ok (HT *ht);
 128
 129 void
 130   hash_do_for_each (HT *ht, void (*f) (void *e, void *aux), void *aux);
 131
 132 int
 133   hash_do_for_each_2 (HT *ht, int (*f) (void *e, void *aux), void *aux);
 134
 135 int
 136   hash_do_for_each_in_selected_bucket (HT *ht, const void *key,
 137                                        int (*f) (const void *bucket_key,
 138                                                  void *e, void *aux),
 139                                        void *aux);
 140
 141 void
 142   hash_clear (HT *ht);
 143
 144 void
 145   hash_free (HT *ht);
 146
 147 void
 148   hash_get_key_list (const HT *ht, unsigned int bufsize, void **buf);
 149
 150 void *
 151   hash_get_first (const HT *ht);
 152
 153 void *
 154   hash_get_next (const HT *ht, const void *e);
 155
 156 /* This interface to hash_insert_if_absent is used frequently enough to
 157    merit a macro here.  */
 158
 159 # define HASH_INSERT_NEW_ITEM(Ht, Item, Failp)                          \
 160   do                                                                    \
 161     {                                                                   \
 162       void *_already;                                                   \
 163       _already = hash_insert_if_absent ((Ht), (Item), Failp);           \
 164       assert (_already == NULL);                                        \
 165     }                                                                   \
 166   while (0)
 167
 168 #endif /* HASH_H */