]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*- |
2 | * BSD LICENSE | |
3 | * | |
4 | * Copyright(c) 2010-2015 Intel Corporation. All rights reserved. | |
5 | * All rights reserved. | |
6 | * | |
7 | * Redistribution and use in source and binary forms, with or without | |
8 | * modification, are permitted provided that the following conditions | |
9 | * are met: | |
10 | * | |
11 | * * Redistributions of source code must retain the above copyright | |
12 | * notice, this list of conditions and the following disclaimer. | |
13 | * * Redistributions in binary form must reproduce the above copyright | |
14 | * notice, this list of conditions and the following disclaimer in | |
15 | * the documentation and/or other materials provided with the | |
16 | * distribution. | |
17 | * * Neither the name of Intel Corporation nor the names of its | |
18 | * contributors may be used to endorse or promote products derived | |
19 | * from this software without specific prior written permission. | |
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 | |
25 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
26 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
27 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
28 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
29 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
30 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
31 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
32 | */ | |
33 | ||
34 | #ifndef _RTE_HASH_H_ | |
35 | #define _RTE_HASH_H_ | |
36 | ||
37 | /** | |
38 | * @file | |
39 | * | |
40 | * RTE Hash Table | |
41 | */ | |
42 | ||
43 | #include <stdint.h> | |
44 | #include <stddef.h> | |
45 | ||
46 | #ifdef __cplusplus | |
47 | extern "C" { | |
48 | #endif | |
49 | ||
50 | /** Maximum size of hash table that can be created. */ | |
51 | #define RTE_HASH_ENTRIES_MAX (1 << 30) | |
52 | ||
53 | /** Maximum number of characters in hash name.*/ | |
54 | #define RTE_HASH_NAMESIZE 32 | |
55 | ||
56 | /** Maximum number of keys that can be searched for using rte_hash_lookup_bulk. */ | |
57 | #define RTE_HASH_LOOKUP_BULK_MAX 64 | |
58 | #define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX | |
59 | ||
60 | /** Enable Hardware transactional memory support. */ | |
61 | #define RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT 0x01 | |
62 | ||
63 | /** Default behavior of insertion, single writer/multi writer */ | |
64 | #define RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD 0x02 | |
65 | ||
66 | /** Signature of key that is stored internally. */ | |
67 | typedef uint32_t hash_sig_t; | |
68 | ||
69 | /** Type of function that can be used for calculating the hash value. */ | |
70 | typedef uint32_t (*rte_hash_function)(const void *key, uint32_t key_len, | |
71 | uint32_t init_val); | |
72 | ||
73 | /** Type of function used to compare the hash key. */ | |
74 | typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len); | |
75 | ||
76 | /** | |
77 | * Parameters used when creating the hash table. | |
78 | */ | |
79 | struct rte_hash_parameters { | |
80 | const char *name; /**< Name of the hash. */ | |
81 | uint32_t entries; /**< Total hash table entries. */ | |
82 | uint32_t reserved; /**< Unused field. Should be set to 0 */ | |
83 | uint32_t key_len; /**< Length of hash key. */ | |
84 | rte_hash_function hash_func; /**< Primary Hash function used to calculate hash. */ | |
85 | uint32_t hash_func_init_val; /**< Init value used by hash_func. */ | |
86 | int socket_id; /**< NUMA Socket ID for memory. */ | |
87 | uint8_t extra_flag; /**< Indicate if additional parameters are present. */ | |
88 | }; | |
89 | ||
90 | /** @internal A hash table structure. */ | |
91 | struct rte_hash; | |
92 | ||
93 | /** | |
94 | * Create a new hash table. | |
95 | * | |
96 | * @param params | |
97 | * Parameters used to create and initialise the hash table. | |
98 | * @return | |
99 | * Pointer to hash table structure that is used in future hash table | |
100 | * operations, or NULL on error, with error code set in rte_errno. | |
101 | * Possible rte_errno errors include: | |
102 | * - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure | |
103 | * - E_RTE_SECONDARY - function was called from a secondary process instance | |
104 | * - ENOENT - missing entry | |
105 | * - EINVAL - invalid parameter passed to function | |
106 | * - ENOSPC - the maximum number of memzones has already been allocated | |
107 | * - EEXIST - a memzone with the same name already exists | |
108 | * - ENOMEM - no appropriate memory area found in which to create memzone | |
109 | */ | |
110 | struct rte_hash * | |
111 | rte_hash_create(const struct rte_hash_parameters *params); | |
112 | ||
113 | /** | |
114 | * Set a new hash compare function other than the default one. | |
115 | * | |
116 | * @note Function pointer does not work with multi-process, so do not use it | |
117 | * in multi-process mode. | |
118 | * | |
119 | * @param h | |
120 | * Hash table for which the function is to be changed | |
121 | * @param func | |
122 | * New compare function | |
123 | */ | |
124 | void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func); | |
125 | ||
126 | /** | |
127 | * Find an existing hash table object and return a pointer to it. | |
128 | * | |
129 | * @param name | |
130 | * Name of the hash table as passed to rte_hash_create() | |
131 | * @return | |
132 | * Pointer to hash table or NULL if object not found | |
133 | * with rte_errno set appropriately. Possible rte_errno values include: | |
134 | * - ENOENT - value not available for return | |
135 | */ | |
136 | struct rte_hash * | |
137 | rte_hash_find_existing(const char *name); | |
138 | ||
139 | /** | |
140 | * De-allocate all memory used by hash table. | |
141 | * @param h | |
142 | * Hash table to free | |
143 | */ | |
144 | void | |
145 | rte_hash_free(struct rte_hash *h); | |
146 | ||
147 | /** | |
148 | * Reset all hash structure, by zeroing all entries | |
149 | * @param h | |
150 | * Hash table to reset | |
151 | */ | |
152 | void | |
153 | rte_hash_reset(struct rte_hash *h); | |
154 | ||
155 | /** | |
156 | * Add a key-value pair to an existing hash table. | |
157 | * This operation is not multi-thread safe | |
158 | * and should only be called from one thread. | |
159 | * | |
160 | * @param h | |
161 | * Hash table to add the key to. | |
162 | * @param key | |
163 | * Key to add to the hash table. | |
164 | * @param data | |
165 | * Data to add to the hash table. | |
166 | * @return | |
167 | * - 0 if added successfully | |
168 | * - -EINVAL if the parameters are invalid. | |
169 | * - -ENOSPC if there is no space in the hash for this key. | |
170 | */ | |
171 | int | |
172 | rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data); | |
173 | ||
174 | /** | |
175 | * Add a key-value pair with a pre-computed hash value | |
176 | * to an existing hash table. | |
177 | * This operation is not multi-thread safe | |
178 | * and should only be called from one thread. | |
179 | * | |
180 | * @param h | |
181 | * Hash table to add the key to. | |
182 | * @param key | |
183 | * Key to add to the hash table. | |
184 | * @param sig | |
185 | * Precomputed hash value for 'key' | |
186 | * @param data | |
187 | * Data to add to the hash table. | |
188 | * @return | |
189 | * - 0 if added successfully | |
190 | * - -EINVAL if the parameters are invalid. | |
191 | * - -ENOSPC if there is no space in the hash for this key. | |
192 | */ | |
193 | int32_t | |
194 | rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key, | |
195 | hash_sig_t sig, void *data); | |
196 | ||
197 | /** | |
198 | * Add a key to an existing hash table. This operation is not multi-thread safe | |
199 | * and should only be called from one thread. | |
200 | * | |
201 | * @param h | |
202 | * Hash table to add the key to. | |
203 | * @param key | |
204 | * Key to add to the hash table. | |
205 | * @return | |
206 | * - -EINVAL if the parameters are invalid. | |
207 | * - -ENOSPC if there is no space in the hash for this key. | |
208 | * - A positive value that can be used by the caller as an offset into an | |
209 | * array of user data. This value is unique for this key. | |
210 | */ | |
211 | int32_t | |
212 | rte_hash_add_key(const struct rte_hash *h, const void *key); | |
213 | ||
214 | /** | |
215 | * Add a key to an existing hash table. | |
216 | * This operation is not multi-thread safe | |
217 | * and should only be called from one thread. | |
218 | * | |
219 | * @param h | |
220 | * Hash table to add the key to. | |
221 | * @param key | |
222 | * Key to add to the hash table. | |
223 | * @param sig | |
224 | * Precomputed hash value for 'key'. | |
225 | * @return | |
226 | * - -EINVAL if the parameters are invalid. | |
227 | * - -ENOSPC if there is no space in the hash for this key. | |
228 | * - A positive value that can be used by the caller as an offset into an | |
229 | * array of user data. This value is unique for this key. | |
230 | */ | |
231 | int32_t | |
232 | rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); | |
233 | ||
234 | /** | |
235 | * Remove a key from an existing hash table. | |
236 | * This operation is not multi-thread safe | |
237 | * and should only be called from one thread. | |
238 | * | |
239 | * @param h | |
240 | * Hash table to remove the key from. | |
241 | * @param key | |
242 | * Key to remove from the hash table. | |
243 | * @return | |
244 | * - -EINVAL if the parameters are invalid. | |
245 | * - -ENOENT if the key is not found. | |
246 | * - A positive value that can be used by the caller as an offset into an | |
247 | * array of user data. This value is unique for this key, and is the same | |
248 | * value that was returned when the key was added. | |
249 | */ | |
250 | int32_t | |
251 | rte_hash_del_key(const struct rte_hash *h, const void *key); | |
252 | ||
253 | /** | |
254 | * Remove a key from an existing hash table. | |
255 | * This operation is not multi-thread safe | |
256 | * and should only be called from one thread. | |
257 | * | |
258 | * @param h | |
259 | * Hash table to remove the key from. | |
260 | * @param key | |
261 | * Key to remove from the hash table. | |
262 | * @param sig | |
263 | * Precomputed hash value for 'key'. | |
264 | * @return | |
265 | * - -EINVAL if the parameters are invalid. | |
266 | * - -ENOENT if the key is not found. | |
267 | * - A positive value that can be used by the caller as an offset into an | |
268 | * array of user data. This value is unique for this key, and is the same | |
269 | * value that was returned when the key was added. | |
270 | */ | |
271 | int32_t | |
272 | rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); | |
273 | ||
274 | /** | |
275 | * Find a key in the hash table given the position. | |
276 | * This operation is multi-thread safe. | |
277 | * | |
278 | * @param h | |
279 | * Hash table to get the key from. | |
280 | * @param position | |
281 | * Position returned when the key was inserted. | |
282 | * @param key | |
283 | * Output containing a pointer to the key | |
284 | * @return | |
285 | * - 0 if retrieved successfully | |
286 | * - EINVAL if the parameters are invalid. | |
287 | * - ENOENT if no valid key is found in the given position. | |
288 | */ | |
289 | int | |
290 | rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, | |
291 | void **key); | |
292 | ||
293 | /** | |
294 | * Find a key-value pair in the hash table. | |
295 | * This operation is multi-thread safe. | |
296 | * | |
297 | * @param h | |
298 | * Hash table to look in. | |
299 | * @param key | |
300 | * Key to find. | |
301 | * @param data | |
302 | * Output with pointer to data returned from the hash table. | |
303 | * @return | |
304 | * 0 if successful lookup | |
305 | * - EINVAL if the parameters are invalid. | |
306 | * - ENOENT if the key is not found. | |
307 | */ | |
308 | int | |
309 | rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data); | |
310 | ||
311 | /** | |
312 | * Find a key-value pair with a pre-computed hash value | |
313 | * to an existing hash table. | |
314 | * This operation is multi-thread safe. | |
315 | * | |
316 | * @param h | |
317 | * Hash table to look in. | |
318 | * @param key | |
319 | * Key to find. | |
320 | * @param sig | |
321 | * Precomputed hash value for 'key' | |
322 | * @param data | |
323 | * Output with pointer to data returned from the hash table. | |
324 | * @return | |
325 | * 0 if successful lookup | |
326 | * - EINVAL if the parameters are invalid. | |
327 | * - ENOENT if the key is not found. | |
328 | */ | |
329 | int | |
330 | rte_hash_lookup_with_hash_data(const struct rte_hash *h, const void *key, | |
331 | hash_sig_t sig, void **data); | |
332 | ||
333 | /** | |
334 | * Find a key in the hash table. | |
335 | * This operation is multi-thread safe. | |
336 | * | |
337 | * @param h | |
338 | * Hash table to look in. | |
339 | * @param key | |
340 | * Key to find. | |
341 | * @return | |
342 | * - -EINVAL if the parameters are invalid. | |
343 | * - -ENOENT if the key is not found. | |
344 | * - A positive value that can be used by the caller as an offset into an | |
345 | * array of user data. This value is unique for this key, and is the same | |
346 | * value that was returned when the key was added. | |
347 | */ | |
348 | int32_t | |
349 | rte_hash_lookup(const struct rte_hash *h, const void *key); | |
350 | ||
351 | /** | |
352 | * Find a key in the hash table. | |
353 | * This operation is multi-thread safe. | |
354 | * | |
355 | * @param h | |
356 | * Hash table to look in. | |
357 | * @param key | |
358 | * Key to find. | |
359 | * @param sig | |
360 | * Hash value to remove from the hash table. | |
361 | * @return | |
362 | * - -EINVAL if the parameters are invalid. | |
363 | * - -ENOENT if the key is not found. | |
364 | * - A positive value that can be used by the caller as an offset into an | |
365 | * array of user data. This value is unique for this key, and is the same | |
366 | * value that was returned when the key was added. | |
367 | */ | |
368 | int32_t | |
369 | rte_hash_lookup_with_hash(const struct rte_hash *h, | |
370 | const void *key, hash_sig_t sig); | |
371 | ||
372 | /** | |
373 | * Calc a hash value by key. | |
374 | * This operation is not multi-thread safe. | |
375 | * | |
376 | * @param h | |
377 | * Hash table to look in. | |
378 | * @param key | |
379 | * Key to find. | |
380 | * @return | |
381 | * - hash value | |
382 | */ | |
383 | hash_sig_t | |
384 | rte_hash_hash(const struct rte_hash *h, const void *key); | |
385 | ||
386 | /** | |
387 | * Find multiple keys in the hash table. | |
388 | * This operation is multi-thread safe. | |
389 | * | |
390 | * @param h | |
391 | * Hash table to look in. | |
392 | * @param keys | |
393 | * A pointer to a list of keys to look for. | |
394 | * @param num_keys | |
395 | * How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX). | |
396 | * @param hit_mask | |
397 | * Output containing a bitmask with all successful lookups. | |
398 | * @param data | |
399 | * Output containing array of data returned from all the successful lookups. | |
400 | * @return | |
401 | * -EINVAL if there's an error, otherwise number of successful lookups. | |
402 | */ | |
403 | int | |
404 | rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, | |
405 | uint32_t num_keys, uint64_t *hit_mask, void *data[]); | |
406 | ||
407 | /** | |
408 | * Find multiple keys in the hash table. | |
409 | * This operation is multi-thread safe. | |
410 | * | |
411 | * @param h | |
412 | * Hash table to look in. | |
413 | * @param keys | |
414 | * A pointer to a list of keys to look for. | |
415 | * @param num_keys | |
416 | * How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX). | |
417 | * @param positions | |
418 | * Output containing a list of values, corresponding to the list of keys that | |
419 | * can be used by the caller as an offset into an array of user data. These | |
420 | * values are unique for each key, and are the same values that were returned | |
421 | * when each key was added. If a key in the list was not found, then -ENOENT | |
422 | * will be the value. | |
423 | * @return | |
424 | * -EINVAL if there's an error, otherwise 0. | |
425 | */ | |
426 | int | |
427 | rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, | |
428 | uint32_t num_keys, int32_t *positions); | |
429 | ||
430 | /** | |
431 | * Iterate through the hash table, returning key-value pairs. | |
432 | * | |
433 | * @param h | |
434 | * Hash table to iterate | |
435 | * @param key | |
436 | * Output containing the key where current iterator | |
437 | * was pointing at | |
438 | * @param data | |
439 | * Output containing the data associated with key. | |
440 | * Returns NULL if data was not stored. | |
441 | * @param next | |
442 | * Pointer to iterator. Should be 0 to start iterating the hash table. | |
443 | * Iterator is incremented after each call of this function. | |
444 | * @return | |
445 | * Position where key was stored, if successful. | |
446 | * - -EINVAL if the parameters are invalid. | |
447 | * - -ENOENT if end of the hash table. | |
448 | */ | |
449 | int32_t | |
450 | rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next); | |
451 | #ifdef __cplusplus | |
452 | } | |
453 | #endif | |
454 | ||
455 | #endif /* _RTE_HASH_H_ */ |