src/libgame/hash.h

   1 /***********************************************************
   2 * Artsoft Retro-Game Library                               *
   3 *----------------------------------------------------------*
   4 * (c) 1994-2003 Artsoft Entertainment                      *
   5 *               Holger Schemel                             *
   6 *               Detmolder Strasse 189                      *
   7 *               33604 Bielefeld                            *
   8 *               Germany                                    *
   9 *               e-mail: info@artsoft.org                   *
  10 *----------------------------------------------------------*
  11 * hash.h                                                   *
  12 ***********************************************************/
  13
  14 /*
  15  * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
  16  *
  17  * Permission is hereby granted, free of charge, to any person obtaining a copy
  18  * of this software and associated documentation files (the "Software"), to
  19  * deal in the Software without restriction, including without limitation the
  20  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  21  * sell copies of the Software, and to permit persons to whom the Software is
  22  * furnished to do so, subject to the following conditions:
  23  *
  24  * The above copyright notice and this permission notice shall be included in
  25  * all copies of the Software and its documentation and acknowledgment shall be
  26  * given in the documentation and software packages that this Software was
  27  * used.
  28  *
  29  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  30  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  31  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  32  * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  33  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  34  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  35  * */
  36
  37 #ifndef HASH_H
  38 #define HASH_H
  39
  40
  41 /* Example of use:
  42  *
  43  *      struct hashtable  *h;
  44  *      struct some_key   *k;
  45  *      struct some_value *v;
  46  *
  47  *      static unsigned int         hash_from_key_fn( void *k );
  48  *      static int                  keys_equal_fn ( void *key1, void *key2 );
  49  *
  50  *      h = create_hashtable(16, 0.75, hash_from_key_fn, keys_equal_fn);
  51  *      k = (struct some_key *)     malloc(sizeof(struct some_key));
  52  *      v = (struct some_value *)   malloc(sizeof(struct some_value));
  53  *
  54  *      (initialise k and v to suitable values)
  55  *
  56  *      if (! hashtable_insert(h,k,v) )
  57  *      {     exit(-1);               }
  58  *
  59  *      if (NULL == (found = hashtable_search(h,k) ))
  60  *      {    printf("not found!");                  }
  61  *
  62  *      if (NULL == (found = hashtable_remove(h,k) ))
  63  *      {    printf("Not found\n");                 }
  64  *
  65  */
  66
  67 /* Macros may be used to define type-safe(r) hashtable access functions, with
  68  * methods specialized to take known key and value types as parameters.
  69  *
  70  * Example:
  71  *
  72  * Insert this at the start of your file:
  73  *
  74  * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
  75  * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
  76  * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
  77  *
  78  * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
  79  * These operate just like hashtable_insert etc., with the same parameters,
  80  * but their function signatures have 'struct some_key *' rather than
  81  * 'void *', and hence can generate compile time errors if your program is
  82  * supplying incorrect data as a key (and similarly for value).
  83  *
  84  * Note that the hash and key equality functions passed to create_hashtable
  85  * still take 'void *' parameters instead of 'some key *'. This shouldn't be
  86  * a difficult issue as they're only defined and passed once, and the other
  87  * functions will ensure that only valid keys are supplied to them.
  88  *
  89  * The cost for this checking is increased code size and runtime overhead
  90  * - if performance is important, it may be worth switching back to the
  91  * unsafe methods once your program has been debugged with the safe methods.
  92  * This just requires switching to some simple alternative defines - eg:
  93  * #define insert_some hashtable_insert
  94  *
  95  */
  96
  97
  98 /*****************************************************************************/
  99 struct entry
 100 {
 101     void *k, *v;
 102     unsigned int h;
 103     struct entry *next;
 104 };
 105
 106 struct hashtable {
 107     unsigned int tablelength;
 108     struct entry **table;
 109     unsigned int entrycount;
 110     unsigned int loadlimit;
 111     unsigned int (*hashfn) (void *k);
 112     int (*eqfn) (void *k1, void *k2);
 113 };
 114
 115 /*****************************************************************************/
 116 struct hashtable_itr
 117 {
 118     struct hashtable *h;
 119     struct entry *e;
 120     unsigned int index;
 121 };
 122
 123
 124 /*****************************************************************************
 125  * create_hashtable
 126
 127  * @name                    create_hashtable
 128  * @param   minsize         minimum initial size of hashtable
 129  * @param   maxloadfactor   maximum ratio entries / tablesize
 130  * @param   hashfunction    function for hashing keys
 131  * @param   key_eq_fn       function for determining key equality
 132  * @return                  newly created hashtable or NULL on failure
 133  */
 134
 135 struct hashtable *
 136 create_hashtable(unsigned int minsize, float maxloadfactor,
 137                  unsigned int (*hashfunction) (void*),
 138                  int (*key_eq_fn) (void*,void*));
 139
 140 /*****************************************************************************
 141  * hashtable_insert
 142
 143  * @name        hashtable_insert
 144  * @param   h   the hashtable to insert into
 145  * @param   k   the key - hashtable claims ownership and will free on removal
 146  * @param   v   the value - does not claim ownership
 147  * @return      non-zero for successful insertion
 148  *
 149  * This function will cause the table to expand if the insertion would take
 150  * the ratio of entries to table size over the maximum load factor.
 151  *
 152  * This function does not check for repeated insertions with a duplicate key.
 153  * The value returned when using a duplicate key is undefined -- when
 154  * the hashtable changes size, the order of retrieval of duplicate key
 155  * entries is reversed.
 156  * If in doubt, remove before insert.
 157  */
 158
 159 int
 160 hashtable_insert(struct hashtable *h, void *k, void *v);
 161
 162 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
 163 int fnname (struct hashtable *h, keytype *k, valuetype *v) \
 164 { \
 165     return hashtable_insert(h,k,v); \
 166 }
 167
 168 /*****************************************************************************
 169  * hashtable_change
 170
 171  * @name        hashtable_change
 172  * @param   h   the hashtable to search
 173  * @param   k   the key of the entry to change
 174  * @param   v   the new value
 175  * @return      non-zero for successful change
 176  */
 177
 178 int
 179 hashtable_change(struct hashtable *h, void *k, void *v);
 180
 181 #define DEFINE_HASHTABLE_CHANGE(fnname, keytype, valuetype) \
 182 int fnname (struct hashtable *h, keytype *k, valuetype *v) \
 183 { \
 184     return hashtable_change(h,k,v); \
 185 }
 186
 187 /*****************************************************************************
 188  * hashtable_search
 189
 190  * @name        hashtable_search
 191  * @param   h   the hashtable to search
 192  * @param   k   the key to search for  - does not claim ownership
 193  * @return      the value associated with the key, or NULL if none found
 194  */
 195
 196 void *
 197 hashtable_search(struct hashtable *h, void *k);
 198
 199 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
 200 valuetype * fnname (struct hashtable *h, keytype *k) \
 201 { \
 202     return (valuetype *) (hashtable_search(h,k)); \
 203 }
 204
 205 /*****************************************************************************
 206  * hashtable_remove
 207
 208  * @name        hashtable_remove
 209  * @param   h   the hashtable to remove the item from
 210  * @param   k   the key to search for  - does not claim ownership
 211  * @return      the value associated with the key, or NULL if none found
 212  */
 213
 214 void * /* returns value */
 215 hashtable_remove(struct hashtable *h, void *k);
 216
 217 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
 218 valuetype * fnname (struct hashtable *h, keytype *k) \
 219 { \
 220     return (valuetype *) (hashtable_remove(h,k)); \
 221 }
 222
 223
 224 /*****************************************************************************
 225  * hashtable_count
 226
 227  * @name        hashtable_count
 228  * @return      the number of items stored in the hashtable
 229  */
 230 unsigned int
 231 hashtable_count(struct hashtable *h);
 232
 233
 234 /*****************************************************************************
 235  * hashtable_destroy
 236
 237  * @name        hashtable_destroy
 238  * @param       free_values     whether to call 'free' on the remaining values
 239  */
 240
 241 void
 242 hashtable_destroy(struct hashtable *h, int free_values);
 243
 244
 245 /*****************************************************************************/
 246 /* hashtable_iterator
 247  */
 248
 249 struct hashtable_itr *
 250 hashtable_iterator(struct hashtable *h);
 251
 252 /*****************************************************************************/
 253 /* hashtable_iterator_key
 254  * - return the value of the (key,value) pair at the current position */
 255
 256 extern inline void *
 257 hashtable_iterator_key(struct hashtable_itr *i)
 258 {
 259     return i->e->k;
 260 }
 261
 262 /*****************************************************************************/
 263 /* value - return the value of the (key,value) pair at the current position */
 264
 265 extern inline void *
 266 hashtable_iterator_value(struct hashtable_itr *i)
 267 {
 268     return i->e->v;
 269 }
 270
 271 /*****************************************************************************/
 272 /* advance - advance the iterator to the next element
 273  *           returns zero if advanced to end of table */
 274
 275 int
 276 hashtable_iterator_advance(struct hashtable_itr *itr);
 277
 278 #endif