linkhash.h

   1 /*
   2  * $Id: linkhash.h,v 1.6 2006/01/30 23:07:57 mclark Exp $
   3  *
   4  * Copyright (c) 2004, 2005 Metaparadigm Pte. Ltd.
   5  * Michael Clark <michael@metaparadigm.com>
   6  *
   7  * This library is free software; you can redistribute it and/or modify
   8  * it under the terms of the MIT license. See COPYING for details.
   9  *
  10  */
  11
  12 #ifndef _linkhash_h_
  13 #define _linkhash_h_
  14
  15 #ifdef __cplusplus
  16 extern "C" {
  17 #endif
  18
  19 /**
  20  * golden prime used in hash functions
  21  */
  22 #define LH_PRIME 0x9e370001UL
  23
  24 /**
  25  * sentinel pointer value for empty slots
  26  */
  27 #define LH_EMPTY (void*)-1
  28
  29 /**
  30  * sentinel pointer value for freed slots
  31  */
  32 #define LH_FREED (void*)-2
  33
  34 struct lh_entry;
  35
  36 /**
  37  * callback function prototypes
  38  */
  39 typedef void (lh_entry_free_fn) (struct lh_entry *e);
  40 /**
  41  * callback function prototypes
  42  */
  43 typedef unsigned long (lh_hash_fn) (const void *k);
  44 /**
  45  * callback function prototypes
  46  */
  47 typedef int (lh_equal_fn) (const void *k1, const void *k2);
  48
  49 /**
  50  * An entry in the hash table
  51  */
  52 struct lh_entry {
  53         /**
  54          * The key.
  55          */
  56         void *k;
  57         /**
  58          * The value.
  59          */
  60         const void *v;
  61         /**
  62          * The next entry
  63          */
  64         struct lh_entry *next;
  65         /**
  66          * The previous entry.
  67          */
  68         struct lh_entry *prev;
  69 };
  70
  71
  72 /**
  73  * The hash table structure.
  74  */
  75 struct lh_table {
  76         /**
  77          * Size of our hash.
  78          */
  79         int size;
  80         /**
  81          * Numbers of entries.
  82          */
  83         int count;
  84
  85         /**
  86          * Number of collisions.
  87          */
  88         int collisions;
  89
  90         /**
  91          * Number of resizes.
  92          */
  93         int resizes;
  94
  95         /**
  96          * Number of lookups.
  97          */
  98         int lookups;
  99
 100         /**
 101          * Number of inserts.
 102          */
 103         int inserts;
 104
 105         /**
 106          * Number of deletes.
 107          */
 108         int deletes;
 109
 110         /**
 111          * Name of the hash table.
 112          */
 113         const char *name;
 114
 115         /**
 116          * The first entry.
 117          */
 118         struct lh_entry *head;
 119
 120         /**
 121          * The last entry.
 122          */
 123         struct lh_entry *tail;
 124
 125         struct lh_entry *table;
 126
 127         /**
 128          * A pointer onto the function responsible for freeing an entry.
 129          */
 130         lh_entry_free_fn *free_fn;
 131         lh_hash_fn *hash_fn;
 132         lh_equal_fn *equal_fn;
 133 };
 134
 135
 136 /**
 137  * Pre-defined hash and equality functions
 138  */
 139 extern unsigned long lh_ptr_hash(const void *k);
 140 extern int lh_ptr_equal(const void *k1, const void *k2);
 141
 142 extern unsigned long lh_char_hash(const void *k);
 143 extern int lh_char_equal(const void *k1, const void *k2);
 144
 145
 146 /**
 147  * Convenience list iterator.
 148  */
 149 #define lh_foreach(table, entry) \
 150 for(entry = table->head; entry; entry = entry->next)
 151
 152 /**
 153  * lh_foreach_safe allows calling of deletion routine while iterating.
 154  */
 155 #define lh_foreach_safe(table, entry, tmp) \
 156 for(entry = table->head; entry && ((tmp = entry->next) || 1); entry = tmp)
 157
 158
 159
 160 /**
 161  * Create a new linkhash table.
 162  * @param size initial table size. The table is automatically resized
 163  * although this incurs a performance penalty.
 164  * @param name the table name.
 165  * @param free_fn callback function used to free memory for entries
 166  * when lh_table_free or lh_table_delete is called.
 167  * If NULL is provided, then memory for keys and values
 168  * must be freed by the caller.
 169  * @param hash_fn  function used to hash keys. 2 standard ones are defined:
 170  * lh_ptr_hash and lh_char_hash for hashing pointer values
 171  * and C strings respectively.
 172  * @param equal_fn comparison function to compare keys. 2 standard ones defined:
 173  * lh_ptr_hash and lh_char_hash for comparing pointer values
 174  * and C strings respectively.
 175  * @return a pointer onto the linkhash table.
 176  */
 177 extern struct lh_table* lh_table_new(int size, const char *name,
 178                                      lh_entry_free_fn *free_fn,
 179                                      lh_hash_fn *hash_fn,
 180                                      lh_equal_fn *equal_fn);
 181
 182 /**
 183  * Convenience function to create a new linkhash
 184  * table with char keys.
 185  * @param size initial table size.
 186  * @param name table name.
 187  * @param free_fn callback function used to free memory for entries.
 188  * @return a pointer onto the linkhash table.
 189  */
 190 extern struct lh_table* lh_kchar_table_new(int size, const char *name,
 191                                            lh_entry_free_fn *free_fn);
 192
 193
 194 /**
 195  * Convenience function to create a new linkhash
 196  * table with ptr keys.
 197  * @param size initial table size.
 198  * @param name table name.
 199  * @param free_fn callback function used to free memory for entries.
 200  * @return a pointer onto the linkhash table.
 201  */
 202 extern struct lh_table* lh_kptr_table_new(int size, const char *name,
 203                                           lh_entry_free_fn *free_fn);
 204
 205
 206 /**
 207  * Free a linkhash table.
 208  * If a callback free function is provided then it is called for all
 209  * entries in the table.
 210  * @param t table to free.
 211  */
 212 extern void lh_table_free(struct lh_table *t);
 213
 214
 215 /**
 216  * Insert a record into the table.
 217  * @param t the table to insert into.
 218  * @param k a pointer to the key to insert.
 219  * @param v a pointer to the value to insert.
 220  */
 221 extern int lh_table_insert(struct lh_table *t, void *k, const void *v);
 222
 223
 224 /**
 225  * Lookup a record into the table.
 226  * @param t the table to lookup
 227  * @param k a pointer to the key to lookup
 228  * @return a pointer to the record structure of the value or NULL if it does not exist.
 229  */
 230 extern struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k);
 231
 232 /**
 233  * Lookup a record into the table
 234  * @param t the table to lookup
 235  * @param k a pointer to the key to lookup
 236  * @return a pointer to the found value or NULL if it does not exist.
 237  */
 238 extern const void* lh_table_lookup(struct lh_table *t, const void *k);
 239
 240
 241 /**
 242  * Delete a record from the table.
 243  * If a callback free function is provided then it is called for the
 244  * for the item being deleted.
 245  * @param t the table to delete from.
 246  * @param e a pointer to the entry to delete.
 247  * @return 0 if the item was deleted.
 248  * @return -1 if it was not found.
 249  */
 250 extern int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e);
 251
 252
 253 /**
 254  * Delete a record from the table.
 255  * If a callback free function is provided then it is called for the
 256  * for the item being deleted.
 257  * @param t the table to delete from.
 258  * @param k a pointer to the key to delete.
 259  * @return 0 if the item was deleted.
 260  * @return -1 if it was not found.
 261  */
 262 extern int lh_table_delete(struct lh_table *t, const void *k);
 263
 264
 265 void lh_abort(const char *msg, ...);
 266 void lh_table_resize(struct lh_table *t, int new_size);
 267
 268 #ifdef __cplusplus
 269 }
 270 #endif
 271
 272 #endif