Palacios Public Git Repository

To checkout Palacios execute

  git clone http://v3vee.org/palacios/palacios.web/palacios.git
This will give you the master branch. You probably want the devel branch or one of the release branches. To switch to the devel branch, simply execute
  cd palacios
  git checkout --track -b devel origin/devel
The other branches are similar.


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