[dpdk-dev] [PATCH v8 2/4] hash: add extendable bucket feature

Bruce Richardson bruce.richardson at intel.com
Tue Oct 23 10:55:35 CEST 2018


On Mon, Oct 22, 2018 at 11:39:46AM -0700, Yipeng Wang wrote:
> 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 at intel.com>
> Acked-by: Dharmik Thakkar <dharmik.thakkar at arm.com>
> ---
Acked-by: Bruce Richardson <bruce.richardson at intel.com>


More information about the dev mailing list