palacios/include/palacios/vmm_hashtable.h

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