palacios/include/vnet/vnet_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 Lei Xia <lxia@northwestern.edu> */
  34
  35
  36 #ifndef __VNET_HASHTABLE_H__
  37 #define __VNET_HASHTABLE_H__
  38
  39 struct hashtable;
  40
  41 /* Example of use:
  42  *
  43  *      struct hashtable  *h;
  44  *      struct some_key   *k;
  45  *      struct some_value *v;
  46  *
  47  *      static uint_t         hash_from_key_fn( void *k );
  48  *      static int                  keys_equal_fn ( void *key1, void *key2 );
  49  *
  50  *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
  51  *      k = (struct some_key *)     malloc(sizeof(struct some_key));
  52  *      v = (struct some_value *)   malloc(sizeof(struct some_value));
  53  *
  54  *      (initialise k and v to suitable values)
  55  *
  56  *      if (! hashtable_insert(h,k,v) )
  57  *      {     exit(-1);               }
  58  *
  59  *      if (NULL == (found = hashtable_search(h,k) ))
  60  *      {    printf("not found!");                  }
  61  *
  62  *      if (NULL == (found = hashtable_remove(h,k) ))
  63  *      {    printf("Not found\n");                 }
  64  *
  65  */
  66
  67 /* Macros may be used to define type-safe(r) hashtable access functions, with
  68  * methods specialized to take known key and value types as parameters.
  69  *
  70  * Example:
  71  *
  72  * Insert this at the start of your file:
  73  *
  74  * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
  75  * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
  76  * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
  77  *
  78  * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
  79  * These operate just like hashtable_insert etc., with the same parameters,
  80  * but their function signatures have 'struct some_key *' rather than
  81  * 'void *', and hence can generate compile time errors if your program is
  82  * supplying incorrect data as a key (and similarly for value).
  83  *
  84  * Note that the hash and key equality functions passed to create_hashtable
  85  * still take 'void *' parameters instead of 'some key *'. This shouldn't be
  86  * a difficult issue as they're only defined and passed once, and the other
  87  * functions will ensure that only valid keys are supplied to them.
  88  *
  89  * The cost for this checking is increased code size and runtime overhead
  90  * - if performance is important, it may be worth switching back to the
  91  * unsafe methods once your program has been debugged with the safe methods.
  92  * This just requires switching to some simple alternative defines - eg:
  93  * #define insert_some hashtable_insert
  94  *
  95  */
  96
  97 /* These cannot be inlined because they are referenced as fn ptrs */
  98 ulong_t vnet_hash_long(ulong_t val, uint_t bits);
  99 ulong_t vnet_hash_buffer(uchar_t * msg, uint_t length);
 100
 101 struct hashtable * vnet_create_htable(uint_t min_size,
 102                                     uint_t (*hashfunction) (addr_t key),
 103                                     int (*key_eq_fn) (addr_t key1, addr_t key2));
 104
 105 void vnet_free_htable(struct hashtable * htable, int free_values, int free_keys);
 106
 107 /*
 108  * returns non-zero for successful insertion
 109  *
 110  * This function will cause the table to expand if the insertion would take
 111  * the ratio of entries to table size over the maximum load factor.
 112  *
 113  * This function does not check for repeated insertions with a duplicate key.
 114  * The value returned when using a duplicate key is undefined -- when
 115  * the hashtable changes size, the order of retrieval of duplicate key
 116  * entries is reversed.
 117  * If in doubt, remove before insert.
 118  */
 119 int vnet_htable_insert(struct hashtable * htable, addr_t key, addr_t value);
 120
 121 // returns the value associated with the key, or NULL if none found
 122 addr_t vnet_htable_search(struct hashtable * htable, addr_t key);
 123
 124 // returns the value associated with the key, or NULL if none found
 125 addr_t vnet_htable_remove(struct hashtable * htable, addr_t key, int free_key);
 126
 127 uint_t vnet_htable_count(struct hashtable * htable);
 128
 129
 130 #endif
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169 /*
 170  * Copyright (c) 2002, Christopher Clark
 171  * All rights reserved.
 172  *
 173  * Redistribution and use in source and binary forms, with or without
 174  * modification, are permitted provided that the following conditions
 175  * are met:
 176  *
 177  * * Redistributions of source code must retain the above copyright
 178  * notice, this list of conditions and the following disclaimer.
 179  *
 180  * * Redistributions in binary form must reproduce the above copyright
 181  * notice, this list of conditions and the following disclaimer in the
 182  * documentation and/or other materials provided with the distribution.
 183  *
 184  * * Neither the name of the original author; nor the names of any contributors
 185  * may be used to endorse or promote products derived from this software
 186  * without specific prior written permission.
 187  *
 188  *
 189  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 190  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 191  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 192  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 193  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 194  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 195  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 196  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 197  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 198  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 199  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 200  */