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