include/libjson/linkhash.h

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