linux_module/util-hashtable.h

   1 /*
   2  * This file is part of the Palacios Virtual Machine Monitor developed
   3  * by the V3VEE Project with funding from the United States National
   4  * Science Foundation and the Department of Energy.
   5  *
   6  * The V3VEE Project is a joint project between Northwestern University
   7  * and the University of New Mexico.  You can find out more at
   8  * http://www.v3vee.org
   9  *
  10  * Copyright (c) 2010, Lei Xia <lxia@northwestern.edu>
  11  * Copyright (c) 2010, The V3VEE Project <http://www.v3vee.org>
  12  * All rights reserved.
  13  *
  14  * This is free software.  You are permitted to use, redistribute,
  15  * and modify it under the terms of the GNU General Public License
  16  * Version 2 (GPLv2).  The accompanying COPYING file contains the
  17  * full text of the license.
  18  */
  19
  20 #ifndef __PALACIOS_HASHTABLE_H__
  21 #define __PALACIOS_HASHTABLE_H__
  22
  23 struct hashtable;
  24
  25 #define __32BIT__
  26
  27 /* Example of use:
  28  *
  29  *      struct hashtable  *h;
  30  *      struct some_key   *k;
  31  *      struct some_value *v;
  32  *
  33  *      static uint_t         hash_from_key_fn( void *k );
  34  *      static int                  keys_equal_fn ( void *key1, void *key2 );
  35  *
  36  *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
  37  *      k = (struct some_key *)     malloc(sizeof(struct some_key));
  38  *      v = (struct some_value *)   malloc(sizeof(struct some_value));
  39  *
  40  *      (initialise k and v to suitable values)
  41  *
  42  *      if (! hashtable_insert(h,k,v) )
  43  *      {     exit(-1);               }
  44  *
  45  *      if (NULL == (found = hashtable_search(h,k) ))
  46  *      {    printf("not found!");                  }
  47  *
  48  *      if (NULL == (found = hashtable_remove(h,k) ))
  49  *      {    printf("Not found\n");                 }
  50  *
  51  */
  52
  53 /* Macros may be used to define type-safe(r) hashtable access functions, with
  54  * methods specialized to take known key and value types as parameters.
  55  *
  56  * Example:
  57  *
  58  * Insert this at the start of your file:
  59  *
  60  * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
  61  * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
  62  * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
  63  *
  64  * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
  65  * These operate just like hashtable_insert etc., with the same parameters,
  66  * but their function signatures have 'struct some_key *' rather than
  67  * 'void *', and hence can generate compile time errors if your program is
  68  * supplying incorrect data as a key (and similarly for value).
  69  *
  70  * Note that the hash and key equality functions passed to create_hashtable
  71  * still take 'void *' parameters instead of 'some key *'. This shouldn't be
  72  * a difficult issue as they're only defined and passed once, and the other
  73  * functions will ensure that only valid keys are supplied to them.
  74  *
  75  * The cost for this checking is increased code size and runtime overhead
  76  * - if performance is important, it may be worth switching back to the
  77  * unsafe methods once your program has been debugged with the safe methods.
  78  * This just requires switching to some simple alternative defines - eg:
  79  * #define insert_some hashtable_insert
  80  *
  81  */
  82
  83 typedef unsigned char uchar_t;
  84 typedef unsigned int uint_t;
  85 typedef unsigned long long ullong_t;
  86 typedef unsigned long ulong_t;
  87 typedef ulong_t addr_t;
  88
  89
  90 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype)             \
  91     static int fnname (struct hashtable * htable, keytype key, valuetype value) { \
  92         return v3_htable_insert(htable, (addr_t)key, (addr_t)value);    \
  93     }
  94
  95 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype)             \
  96     static valuetype * fnname (struct hashtable * htable, keytype  key) { \
  97         return (valuetype *) (v3_htable_search(htable, (addr_t)key));   \
  98     }
  99
 100 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype, free_key)   \
 101     static valuetype * fnname (struct hashtable * htable, keytype key) { \
 102         return (valuetype *) (v3_htable_remove(htable, (addr_t)key, free_key)); \
 103     }
 104
 105
 106
 107
 108
 109 /* These cannot be inlined because they are referenced as fn ptrs */
 110 ulong_t palacios_hash_long(ulong_t val, uint_t bits);
 111 ulong_t palacios_hash_buffer(uchar_t * msg, uint_t length);
 112
 113
 114
 115 struct hashtable * palacios_create_htable(uint_t min_size,
 116                                     uint_t (*hashfunction) (addr_t key),
 117                                     int (*key_eq_fn) (addr_t key1, addr_t key2));
 118
 119 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys);
 120
 121 /*
 122  * returns non-zero for successful insertion
 123  *
 124  * This function will cause the table to expand if the insertion would take
 125  * the ratio of entries to table size over the maximum load factor.
 126  *
 127  * This function does not check for repeated insertions with a duplicate key.
 128  * The value returned when using a duplicate key is undefined -- when
 129  * the hashtable changes size, the order of retrieval of duplicate key
 130  * entries is reversed.
 131  * If in doubt, remove before insert.
 132  */
 133 int palacios_htable_insert(struct hashtable * htable, addr_t key, addr_t value);
 134
 135 int palacios_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value);
 136
 137
 138 // returns the value associated with the key, or NULL if none found
 139 addr_t palacios_htable_search(struct hashtable * htable, addr_t key);
 140
 141 // returns the value associated with the key, or NULL if none found
 142 addr_t palacios_htable_remove(struct hashtable * htable, addr_t key, int free_key);
 143
 144 uint_t palacios_htable_count(struct hashtable * htable);
 145
 146 // Specialty functions for a counting hashtable
 147 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value);
 148 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value);
 149
 150
 151 #endif