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