1 #ifndef __PALACIOS_HASHTABLE_H__
2 #define __PALACIOS_HASHTABLE_H__
10 * struct hashtable *h;
12 * struct some_value *v;
14 * static uint_t hash_from_key_fn( void *k );
15 * static int keys_equal_fn ( void *key1, void *key2 );
17 * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
18 * k = (struct some_key *) malloc(sizeof(struct some_key));
19 * v = (struct some_value *) malloc(sizeof(struct some_value));
21 * (initialise k and v to suitable values)
23 * if (! hashtable_insert(h,k,v) )
26 * if (NULL == (found = hashtable_search(h,k) ))
27 * { printf("not found!"); }
29 * if (NULL == (found = hashtable_remove(h,k) ))
30 * { printf("Not found\n"); }
34 /* Macros may be used to define type-safe(r) hashtable access functions, with
35 * methods specialized to take known key and value types as parameters.
39 * Insert this at the start of your file:
41 * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
42 * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
43 * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
45 * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
46 * These operate just like hashtable_insert etc., with the same parameters,
47 * but their function signatures have 'struct some_key *' rather than
48 * 'void *', and hence can generate compile time errors if your program is
49 * supplying incorrect data as a key (and similarly for value).
51 * Note that the hash and key equality functions passed to create_hashtable
52 * still take 'void *' parameters instead of 'some key *'. This shouldn't be
53 * a difficult issue as they're only defined and passed once, and the other
54 * functions will ensure that only valid keys are supplied to them.
56 * The cost for this checking is increased code size and runtime overhead
57 * - if performance is important, it may be worth switching back to the
58 * unsafe methods once your program has been debugged with the safe methods.
59 * This just requires switching to some simple alternative defines - eg:
60 * #define insert_some hashtable_insert
64 typedef unsigned char uchar_t;
65 typedef unsigned int uint_t;
66 typedef unsigned long long ullong_t;
67 typedef unsigned long ulong_t;
68 typedef ulong_t addr_t;
71 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
72 static int fnname (struct hashtable * htable, keytype key, valuetype value) { \
73 return v3_htable_insert(htable, (addr_t)key, (addr_t)value); \
76 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
77 static valuetype * fnname (struct hashtable * htable, keytype key) { \
78 return (valuetype *) (v3_htable_search(htable, (addr_t)key)); \
81 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype, free_key) \
82 static valuetype * fnname (struct hashtable * htable, keytype key) { \
83 return (valuetype *) (v3_htable_remove(htable, (addr_t)key, free_key)); \
90 /* These cannot be inlined because they are referenced as fn ptrs */
91 ulong_t palacios_hash_long(ulong_t val, uint_t bits);
92 ulong_t palacios_hash_buffer(uchar_t * msg, uint_t length);
96 struct hashtable * palacios_create_htable(uint_t min_size,
97 uint_t (*hashfunction) (addr_t key),
98 int (*key_eq_fn) (addr_t key1, addr_t key2));
100 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys);
103 * returns non-zero for successful insertion
105 * This function will cause the table to expand if the insertion would take
106 * the ratio of entries to table size over the maximum load factor.
108 * This function does not check for repeated insertions with a duplicate key.
109 * The value returned when using a duplicate key is undefined -- when
110 * the hashtable changes size, the order of retrieval of duplicate key
111 * entries is reversed.
112 * If in doubt, remove before insert.
114 int palacios_htable_insert(struct hashtable * htable, addr_t key, addr_t value);
116 int palacios_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value);
119 // returns the value associated with the key, or NULL if none found
120 addr_t palacios_htable_search(struct hashtable * htable, addr_t key);
122 // returns the value associated with the key, or NULL if none found
123 addr_t palacios_htable_remove(struct hashtable * htable, addr_t key, int free_key);
125 uint_t palacios_htable_count(struct hashtable * htable);
127 // Specialty functions for a counting hashtable
128 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value);
129 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value);