lib/hash.h

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