Home | History | Annotate | Download | only in json-c
      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 (at) 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 THIS_FUNCTION_IS_DEPRECATED(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 extern int lh_table_length(struct lh_table *t);
    284 
    285 void lh_abort(const char *msg, ...);
    286 void lh_table_resize(struct lh_table *t, int new_size);
    287 
    288 #ifdef __cplusplus
    289 }
    290 #endif
    291 
    292 #endif
    293