palacios/include/palacios/vmm_hashtable.h

   1 /* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
   2 /* Modifications made by Jack Lange <jarusl@cs.northwestern.edu> */
   3 /* (c) 2008, Jack Lange <jarusl@cs.northwestern.edu> */
   4 /* (c) 2008, The V3VEE Project <http://www.v3vee.org> */
   5
   6
   7 #ifndef __VMM_HASHTABLE_H__
   8 #define __VMM_HASHTABLE_H__
   9
  10 #ifdef __V3VEE__
  11
  12 struct hashtable;
  13
  14 /* Example of use:
  15  *
  16  *      struct hashtable  *h;
  17  *      struct some_key   *k;
  18  *      struct some_value *v;
  19  *
  20  *      static uint_t         hash_from_key_fn( void *k );
  21  *      static int                  keys_equal_fn ( void *key1, void *key2 );
  22  *
  23  *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
  24  *      k = (struct some_key *)     malloc(sizeof(struct some_key));
  25  *      v = (struct some_value *)   malloc(sizeof(struct some_value));
  26  *
  27  *      (initialise k and v to suitable values)
  28  *
  29  *      if (! hashtable_insert(h,k,v) )
  30  *      {     exit(-1);               }
  31  *
  32  *      if (NULL == (found = hashtable_search(h,k) ))
  33  *      {    printf("not found!");                  }
  34  *
  35  *      if (NULL == (found = hashtable_remove(h,k) ))
  36  *      {    printf("Not found\n");                 }
  37  *
  38  */
  39
  40 /* Macros may be used to define type-safe(r) hashtable access functions, with
  41  * methods specialized to take known key and value types as parameters.
  42  *
  43  * Example:
  44  *
  45  * Insert this at the start of your file:
  46  *
  47  * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
  48  * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
  49  * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
  50  *
  51  * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
  52  * These operate just like hashtable_insert etc., with the same parameters,
  53  * but their function signatures have 'struct some_key *' rather than
  54  * 'void *', and hence can generate compile time errors if your program is
  55  * supplying incorrect data as a key (and similarly for value).
  56  *
  57  * Note that the hash and key equality functions passed to create_hashtable
  58  * still take 'void *' parameters instead of 'some key *'. This shouldn't be
  59  * a difficult issue as they're only defined and passed once, and the other
  60  * functions will ensure that only valid keys are supplied to them.
  61  *
  62  * The cost for this checking is increased code size and runtime overhead
  63  * - if performance is important, it may be worth switching back to the
  64  * unsafe methods once your program has been debugged with the safe methods.
  65  * This just requires switching to some simple alternative defines - eg:
  66  * #define insert_some hashtable_insert
  67  *
  68  */
  69
  70 ulong_t hash_long(ulong_t val, uint_t bits);
  71 ulong_t hash_buffer(uchar_t * msg, uint_t length);
  72
  73
  74
  75
  76 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype)             \
  77   int fnname (struct hashtable * htable, keytype key, valuetype value) { \
  78     return hashtable_insert(htable, (addr_t)key, (addr_t)value);                \
  79   }
  80
  81 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype)             \
  82   valuetype * fnname (struct hashtable * htable, keytype  key) {        \
  83     return (valuetype *) (hashtable_search(htable, (addr_t)key));               \
  84   }
  85
  86 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype, free_key)   \
  87   valuetype * fnname (struct hashtable * htable, keytype key) { \
  88     return (valuetype *) (hashtable_remove(htable, (addr_t)key, free_key));     \
  89   }
  90
  91
  92
  93
  94
  95
  96 struct hashtable * create_hashtable(uint_t min_size,
  97                                     uint_t (*hashfunction) (addr_t key),
  98                                     int (*key_eq_fn) (addr_t key1, addr_t key2));
  99
 100 void hashtable_destroy(struct hashtable * htable, int free_values, int free_keys);
 101
 102 /*
 103  * returns non-zero for successful insertion
 104  *
 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.
 107  *
 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.
 113  */
 114 int hashtable_insert(struct hashtable * htable, addr_t key, addr_t value);
 115
 116 int hashtable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value);
 117
 118
 119 // returns the value associated with the key, or NULL if none found
 120 addr_t hashtable_search(struct hashtable * htable, addr_t key);
 121
 122 // returns the value associated with the key, or NULL if none found
 123 addr_t hashtable_remove(struct hashtable * htable, addr_t key, int free_key);
 124
 125 uint_t hashtable_count(struct hashtable * htable);
 126
 127   /* ************ */
 128  /* ITERATOR API */
 129 /* ************ */
 130
 131 #define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype)               \
 132   int fnname (struct hashtable_itr * iter, struct hashtable * htable, keytype * key) { \
 133     return (hashtable_iterator_search(iter, htable, key));              \
 134   }
 135
 136
 137
 138 /*****************************************************************************/
 139 /* This struct is only concrete here to allow the inlining of two of the
 140  * accessor functions. */
 141 struct hashtable_iter {
 142   struct hashtable * htable;
 143   struct hash_entry * entry;
 144   struct hash_entry * parent;
 145   uint_t index;
 146 };
 147
 148
 149 struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable);
 150
 151 /* - return the value of the (key,value) pair at the current position */
 152 //extern inline
 153 addr_t  hashtable_get_iter_key(struct hashtable_iter * iter);
 154 /* {
 155    return iter->entry->key;
 156    }
 157 */
 158
 159
 160 /* value - return the value of the (key,value) pair at the current position */
 161 //extern inline
 162 addr_t hashtable_get_iter_value(struct hashtable_iter * iter);
 163 /* {
 164    return iter->entry->value;
 165    }
 166 */
 167
 168
 169
 170 /* returns zero if advanced to end of table */
 171 int hashtable_iterator_advance(struct hashtable_iter * iter);
 172
 173 /* remove current element and advance the iterator to the next element
 174  *          NB: if you need the value to free it, read it before
 175  *          removing. ie: beware memory leaks!
 176  *          returns zero if advanced to end of table
 177  */
 178 int hashtable_iterator_remove(struct hashtable_iter * iter, int free_key);
 179
 180
 181 /* search - overwrite the supplied iterator, to point to the entry
 182  *          matching the supplied key.
 183  *          returns zero if not found. */
 184 int hashtable_iterator_search(struct hashtable_iter * iter, struct hashtable * htable, addr_t key);
 185
 186
 187
 188
 189 #endif // ! __V3VEE__
 190
 191
 192 #endif /* __VMM_HASHTABLE_H__ */
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231 /*
 232  * Copyright (c) 2002, Christopher Clark
 233  * All rights reserved.
 234  *
 235  * Redistribution and use in source and binary forms, with or without
 236  * modification, are permitted provided that the following conditions
 237  * are met:
 238  *
 239  * * Redistributions of source code must retain the above copyright
 240  * notice, this list of conditions and the following disclaimer.
 241  *
 242  * * Redistributions in binary form must reproduce the above copyright
 243  * notice, this list of conditions and the following disclaimer in the
 244  * documentation and/or other materials provided with the distribution.
 245  *
 246  * * Neither the name of the original author; nor the names of any contributors
 247  * may be used to endorse or promote products derived from this software
 248  * without specific prior written permission.
 249  *
 250  *
 251  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 252  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 253  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 254  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 255  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 256  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 257  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 258  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 259  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 260  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 261  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 262 */