hash: add extendable bucket feature
authorYipeng Wang <yipeng1.wang@intel.com>
Mon, 22 Oct 2018 18:39:46 +0000 (11:39 -0700)
committerThomas Monjalon <thomas@monjalon.net>
Thu, 25 Oct 2018 23:04:33 +0000 (01:04 +0200)
commit75706568a7eb8875328e2c95f4d71871bd58e494
tree15d83e977bded5ca025e67844807e14555d8716b
parent99040943442426ebfef0ad69eca73559a9e3b730
hash: add extendable bucket feature

In use cases that hash table capacity needs to be guaranteed,
the extendable bucket feature can be used to contain extra
keys in linked lists when conflict happens. This is similar
concept to the extendable bucket hash table in packet
framework.

This commit adds the extendable bucket feature. User can turn
it on or off through the extra flag field during table
creation time.

Extendable bucket table composes of buckets that can be
linked list to current main table. When extendable bucket
is enabled, the hash table load can always achieve 100%.
In other words, the table can always accommodate the same
number of keys as the specified table size. This provides
100% table capacity guarantee.

Although keys ending up in the ext buckets may have longer
look up time, they should be rare due to the cuckoo
algorithm.

Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
Acked-by: Dharmik Thakkar <dharmik.thakkar@arm.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
doc/guides/rel_notes/release_18_11.rst
lib/librte_hash/rte_cuckoo_hash.c
lib/librte_hash/rte_cuckoo_hash.h
lib/librte_hash/rte_hash.h