DPDK
24.11.0
Loading...
Searching...
No Matches
rte_fbk_hash.h
Go to the documentation of this file.
1
/* SPDX-License-Identifier: BSD-3-Clause
2
* Copyright(c) 2010-2014 Intel Corporation
3
*/
4
5
#ifndef _RTE_FBK_HASH_H_
6
#define _RTE_FBK_HASH_H_
7
17
18
#include <stdint.h>
19
#include <errno.h>
20
21
#include <string.h>
22
23
#include <
rte_hash_crc.h
>
24
#include <
rte_jhash.h
>
25
26
#ifdef __cplusplus
27
extern
"C"
{
28
#endif
29
30
#ifndef RTE_FBK_HASH_INIT_VAL_DEFAULT
32
#define RTE_FBK_HASH_INIT_VAL_DEFAULT 0xFFFFFFFF
33
#endif
34
36
#define RTE_FBK_HASH_ENTRIES_MAX (1 << 20)
37
39
#define RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX 256
40
42
#define RTE_FBK_HASH_NAMESIZE 32
43
45
typedef
uint32_t (*
rte_fbk_hash_fn
)(uint32_t key, uint32_t init_val);
46
48
struct
rte_fbk_hash_params
{
49
const
char
*
name
;
50
uint32_t
entries
;
51
uint32_t
entries_per_bucket
;
52
int
socket_id
;
53
rte_fbk_hash_fn
hash_func
;
54
uint32_t
init_val
;
55
};
56
58
union
rte_fbk_hash_entry
{
59
uint64_t
whole_entry
;
60
struct
{
61
uint16_t
is_entry
;
62
uint16_t
value
;
63
uint32_t
key
;
64
}
entry
;
65
};
66
67
69
struct
rte_fbk_hash_table
{
70
char
name
[
RTE_FBK_HASH_NAMESIZE
];
71
uint32_t
entries
;
72
uint32_t
entries_per_bucket
;
73
uint32_t
used_entries
;
74
uint32_t
bucket_mask
;
75
uint32_t
bucket_shift
;
76
rte_fbk_hash_fn
hash_func
;
77
uint32_t
init_val
;
78
80
union
rte_fbk_hash_entry
t
[];
81
};
82
93
static
inline
uint32_t
94
rte_fbk_hash_get_bucket
(
const
struct
rte_fbk_hash_table
*ht, uint32_t
key
)
95
{
96
return
(ht->
hash_func
(
key
, ht->
init_val
) & ht->
bucket_mask
) <<
97
ht->
bucket_shift
;
98
}
99
116
static
inline
int
117
rte_fbk_hash_add_key_with_bucket
(
struct
rte_fbk_hash_table
*ht,
118
uint32_t
key
, uint16_t
value
, uint32_t bucket)
119
{
120
/*
121
* The writing of a new value to the hash table is done as a single
122
* 64bit operation. This should help prevent individual entries being
123
* corrupted due to race conditions, but it's still possible to
124
* overwrite entries that have just been made valid.
125
*/
126
const
uint64_t new_entry = ((uint64_t)(
key
) << 32) |
127
((uint64_t)(
value
) << 16) |
128
1;
/* 1 = is_entry bit. */
129
uint32_t i;
130
131
for
(i = 0; i < ht->
entries_per_bucket
; i++) {
132
/* Set entry if unused. */
133
if
(! ht->
t
[bucket + i].
entry
.
is_entry
) {
134
ht->
t
[bucket + i].
whole_entry
= new_entry;
135
ht->
used_entries
++;
136
return
0;
137
}
138
/* Change value if key already exists. */
139
if
(ht->
t
[bucket + i].
entry
.
key
==
key
) {
140
ht->
t
[bucket + i].
entry
.
value
=
value
;
141
return
0;
142
}
143
}
144
145
return
-ENOSPC;
/* No space in bucket. */
146
}
147
161
static
inline
int
162
rte_fbk_hash_add_key
(
struct
rte_fbk_hash_table
*ht,
163
uint32_t
key
, uint16_t
value
)
164
{
165
return
rte_fbk_hash_add_key_with_bucket
(ht,
166
key
,
value
,
rte_fbk_hash_get_bucket
(ht,
key
));
167
}
168
183
static
inline
int
184
rte_fbk_hash_delete_key_with_bucket
(
struct
rte_fbk_hash_table
*ht,
185
uint32_t
key
, uint32_t bucket)
186
{
187
uint32_t last_entry = ht->
entries_per_bucket
- 1;
188
uint32_t i, j;
189
190
for
(i = 0; i < ht->
entries_per_bucket
; i++) {
191
if
(ht->
t
[bucket + i].
entry
.
key
==
key
) {
192
/* Find last key in bucket. */
193
for
(j = ht->
entries_per_bucket
- 1; j > i; j-- ) {
194
if
(! ht->
t
[bucket + j].
entry
.
is_entry
) {
195
last_entry = j - 1;
196
}
197
}
198
/*
199
* Move the last key to the deleted key's position, and
200
* delete the last key. lastEntry and i may be same but
201
* it doesn't matter.
202
*/
203
ht->
t
[bucket + i].
whole_entry
=
204
ht->
t
[bucket + last_entry].
whole_entry
;
205
ht->
t
[bucket + last_entry].
whole_entry
= 0;
206
207
ht->
used_entries
--;
208
return
0;
209
}
210
}
211
212
return
-ENOENT;
/* Key didn't exist. */
213
}
214
226
static
inline
int
227
rte_fbk_hash_delete_key
(
struct
rte_fbk_hash_table
*ht, uint32_t
key
)
228
{
229
return
rte_fbk_hash_delete_key_with_bucket
(ht,
230
key
,
rte_fbk_hash_get_bucket
(ht,
key
));
231
}
232
246
static
inline
int
247
rte_fbk_hash_lookup_with_bucket
(
const
struct
rte_fbk_hash_table
*ht,
248
uint32_t
key
, uint32_t bucket)
249
{
250
union
rte_fbk_hash_entry
current_entry;
251
uint32_t i;
252
253
for
(i = 0; i < ht->
entries_per_bucket
; i++) {
254
/* Single read of entry, which should be atomic. */
255
current_entry.
whole_entry
= ht->
t
[bucket + i].
whole_entry
;
256
if
(! current_entry.
entry
.
is_entry
) {
257
return
-ENOENT;
/* Error once we hit an empty field. */
258
}
259
if
(current_entry.
entry
.
key
==
key
) {
260
return
current_entry.
entry
.
value
;
261
}
262
}
263
return
-ENOENT;
/* Key didn't exist. */
264
}
265
276
static
inline
int
277
rte_fbk_hash_lookup
(
const
struct
rte_fbk_hash_table
*ht, uint32_t
key
)
278
{
279
return
rte_fbk_hash_lookup_with_bucket
(ht,
280
key
,
rte_fbk_hash_get_bucket
(ht,
key
));
281
}
282
290
static
inline
void
291
rte_fbk_hash_clear_all
(
struct
rte_fbk_hash_table
*ht)
292
{
293
memset(ht->
t
, 0,
sizeof
(ht->
t
[0]) * ht->
entries
);
294
ht->
used_entries
= 0;
295
}
296
305
static
inline
double
306
rte_fbk_hash_get_load_factor
(
struct
rte_fbk_hash_table
*ht)
307
{
308
return
(
double
)ht->
used_entries
/ (double)ht->
entries
;
309
}
310
323
struct
rte_fbk_hash_table
*
rte_fbk_hash_find_existing
(
const
char
*
name
);
324
342
struct
rte_fbk_hash_table
* \
343
rte_fbk_hash_create(
const
struct
rte_fbk_hash_params
*params);
344
352
void
rte_fbk_hash_free
(
struct
rte_fbk_hash_table
*ht);
353
354
#ifdef __cplusplus
355
}
356
#endif
357
358
#endif
/* _RTE_FBK_HASH_H_ */
RTE_FBK_HASH_NAMESIZE
#define RTE_FBK_HASH_NAMESIZE
Definition
rte_fbk_hash.h:42
rte_fbk_hash_add_key_with_bucket
static int rte_fbk_hash_add_key_with_bucket(struct rte_fbk_hash_table *ht, uint32_t key, uint16_t value, uint32_t bucket)
Definition
rte_fbk_hash.h:117
rte_fbk_hash_add_key
static int rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, uint32_t key, uint16_t value)
Definition
rte_fbk_hash.h:162
rte_fbk_hash_free
void rte_fbk_hash_free(struct rte_fbk_hash_table *ht)
rte_fbk_hash_lookup_with_bucket
static int rte_fbk_hash_lookup_with_bucket(const struct rte_fbk_hash_table *ht, uint32_t key, uint32_t bucket)
Definition
rte_fbk_hash.h:247
rte_fbk_hash_delete_key_with_bucket
static int rte_fbk_hash_delete_key_with_bucket(struct rte_fbk_hash_table *ht, uint32_t key, uint32_t bucket)
Definition
rte_fbk_hash.h:184
rte_fbk_hash_find_existing
struct rte_fbk_hash_table * rte_fbk_hash_find_existing(const char *name)
rte_fbk_hash_lookup
static int rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key)
Definition
rte_fbk_hash.h:277
rte_fbk_hash_delete_key
static int rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key)
Definition
rte_fbk_hash.h:227
rte_fbk_hash_fn
uint32_t(* rte_fbk_hash_fn)(uint32_t key, uint32_t init_val)
Definition
rte_fbk_hash.h:45
rte_fbk_hash_get_bucket
static uint32_t rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key)
Definition
rte_fbk_hash.h:94
rte_fbk_hash_clear_all
static void rte_fbk_hash_clear_all(struct rte_fbk_hash_table *ht)
Definition
rte_fbk_hash.h:291
rte_fbk_hash_get_load_factor
static double rte_fbk_hash_get_load_factor(struct rte_fbk_hash_table *ht)
Definition
rte_fbk_hash.h:306
rte_hash_crc.h
rte_jhash.h
rte_fbk_hash_params
Definition
rte_fbk_hash.h:48
rte_fbk_hash_params::socket_id
int socket_id
Definition
rte_fbk_hash.h:52
rte_fbk_hash_params::entries
uint32_t entries
Definition
rte_fbk_hash.h:50
rte_fbk_hash_params::hash_func
rte_fbk_hash_fn hash_func
Definition
rte_fbk_hash.h:53
rte_fbk_hash_params::name
const char * name
Definition
rte_fbk_hash.h:49
rte_fbk_hash_params::init_val
uint32_t init_val
Definition
rte_fbk_hash.h:54
rte_fbk_hash_params::entries_per_bucket
uint32_t entries_per_bucket
Definition
rte_fbk_hash.h:51
rte_fbk_hash_table
Definition
rte_fbk_hash.h:69
rte_fbk_hash_table::entries
uint32_t entries
Definition
rte_fbk_hash.h:71
rte_fbk_hash_table::bucket_shift
uint32_t bucket_shift
Definition
rte_fbk_hash.h:75
rte_fbk_hash_table::hash_func
rte_fbk_hash_fn hash_func
Definition
rte_fbk_hash.h:76
rte_fbk_hash_table::t
union rte_fbk_hash_entry t[]
Definition
rte_fbk_hash.h:80
rte_fbk_hash_table::bucket_mask
uint32_t bucket_mask
Definition
rte_fbk_hash.h:74
rte_fbk_hash_table::used_entries
uint32_t used_entries
Definition
rte_fbk_hash.h:73
rte_fbk_hash_table::init_val
uint32_t init_val
Definition
rte_fbk_hash.h:77
rte_fbk_hash_table::name
char name[RTE_FBK_HASH_NAMESIZE]
Definition
rte_fbk_hash.h:70
rte_fbk_hash_table::entries_per_bucket
uint32_t entries_per_bucket
Definition
rte_fbk_hash.h:72
rte_fbk_hash_entry
Definition
rte_fbk_hash.h:58
rte_fbk_hash_entry::whole_entry
uint64_t whole_entry
Definition
rte_fbk_hash.h:59
rte_fbk_hash_entry::key
uint32_t key
Definition
rte_fbk_hash.h:63
rte_fbk_hash_entry::value
uint16_t value
Definition
rte_fbk_hash.h:62
rte_fbk_hash_entry::is_entry
uint16_t is_entry
Definition
rte_fbk_hash.h:61
rte_fbk_hash_entry::entry
struct rte_fbk_hash_entry::@161375022003300173325054045162201147113363210106 entry
lib
hash
rte_fbk_hash.h
Generated by
1.13.0