kphash.h File Reference

Include dependency graph for kphash.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	kp_hash_bucket_t
struct	kp_hash_t

Macros
#define	KPHASH_ENTRY_PER_BUCKET   4
	vppinfra already includes tons of different hash tables. More...
#define	KP_HASH_DO_NOT_USE_SSE_BUCKETS   0
#define	clib_u32_loop_gt(a, b)   (((u32)(a)) - ((u32)(b)) < 0x7fffffff)
	32 bits integer comparison for running values. More...
#define	kp_hash_nbuckets(h)   (((h)->buckets_mask) + 1)
#define	kp_hash_size(h)   ((h)->buckets_mask + KPHASH_ENTRY_PER_BUCKET)
#define	kp_hash_foreach_bucket(h, bucket)
#define	kp_hash_foreach_entry(h, bucket, i)
#define	kp_hash_foreach_valid_entry(h, bucket, i, now)

Functions
static_always_inline kp_hash_t *	kp_hash_alloc (u32 buckets, u32 timeout)
static_always_inline void	kp_hash_free (kp_hash_t *h)
static_always_inline u32	kp_hash_hash (u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
static_always_inline void	kp_hash_prefetch_bucket (kp_hash_t *ht, u32 hash)
static_always_inline void	kp_hash_get (kp_hash_t *ht, u32 hash, u32 vip, u32 time_now, u32 *available_index, u32 *found_value)
static_always_inline u32	kp_hash_available_value (kp_hash_t *h, u32 hash, u32 available_index)
static_always_inline void	kp_hash_put (kp_hash_t *h, u32 hash, u32 value, u32 vip, u32 available_index, u32 time_now)
static_always_inline u32	kp_hash_elts (kp_hash_t *h, u32 time_now)

Macro Definition Documentation

#define clib_u32_loop_gt	(		a,
			b
	)		(((u32)(a)) - ((u32)(b)) < 0x7fffffff)

32 bits integer comparison for running values.

1 > 0 is true. But 1 > 0xffffffff also is.

Definition at line 47 of file kphash.h.

#define KP_HASH_DO_NOT_USE_SSE_BUCKETS   0

Definition at line 41 of file kphash.h.

#define kp_hash_foreach_bucket	(		h,
			bucket
	)

Value:

for (bucket = (h)->buckets; \
        bucket < (h)->buckets + kp_hash_nbuckets(h); \
        bucket++)

Definition at line 70 of file kphash.h.

#define kp_hash_foreach_entry	(		h,
			bucket,
			i
	)

Value:

kp_hash_foreach_bucket(h, bucket) \
      for (i = 0; i < KPHASH_ENTRY_PER_BUCKET; i++)

Definition at line 75 of file kphash.h.

#define kp_hash_foreach_valid_entry	(		h,
			bucket,
			i,
			now
	)

Value:

kp_hash_foreach_entry(h, bucket, i) \
       if (!clib_u32_loop_gt((now), bucket->timeout[i]))

Definition at line 79 of file kphash.h.

#define kp_hash_nbuckets

(

h

)

(((h)->buckets_mask) + 1)

Definition at line 67 of file kphash.h.

#define kp_hash_size

(

h

)

((h)->buckets_mask + KPHASH_ENTRY_PER_BUCKET)

Definition at line 68 of file kphash.h.

#define KPHASH_ENTRY_PER_BUCKET   4

vppinfra already includes tons of different hash tables.

MagLev flow table is a bit different. It has to be very efficient for both writing and reading operations. But it does not need to be 100% reliable (write can fail). It also needs to recycle old entries in a lazy way.

This hash table is the most dummy hash table you can do. Fixed total size, fixed bucket size. Advantage is that it could be very efficient (maybe).

Definition at line 39 of file kphash.h.

Function Documentation

static_always_inline kp_hash_t* kp_hash_alloc	(	u32	buckets,
		u32	timeout
	)

Definition at line 84 of file kphash.h.

Here is the call graph for this function:

Here is the caller graph for this function:

static_always_inline u32 kp_hash_available_value	(	kp_hash_t *	h,
		u32	hash,
		u32	available_index
	)

Definition at line 188 of file kphash.h.

Here is the caller graph for this function:

static_always_inline u32 kp_hash_elts	(	kp_hash_t *	h,
		u32	time_now
	)

Definition at line 205 of file kphash.h.

Here is the caller graph for this function:

static_always_inline void kp_hash_free

(

kp_hash_t *

h

)

Definition at line 102 of file kphash.h.

Here is the caller graph for this function:

static_always_inline void kp_hash_get	(	kp_hash_t *	ht,
		u32	hash,
		u32	vip,
		u32	time_now,
		u32 *	available_index,
		u32 *	found_value
	)

Definition at line 133 of file kphash.h.

Here is the caller graph for this function:

static_always_inline u32 kp_hash_hash	(	u64	k0,
		u64	k1,
		u64	k2,
		u64	k3,
		u64	k4
	)

Definition at line 109 of file kphash.h.

Here is the call graph for this function:

Here is the caller graph for this function:

static_always_inline void kp_hash_prefetch_bucket	(	kp_hash_t *	ht,
		u32	hash
	)

Definition at line 126 of file kphash.h.

Here is the caller graph for this function:

static_always_inline void kp_hash_put	(	kp_hash_t *	h,
		u32	hash,
		u32	value,
		u32	vip,
		u32	available_index,
		u32	time_now
	)

Definition at line 194 of file kphash.h.

Here is the caller graph for this function: