From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id 6708C58D4 for ; Fri, 26 Aug 2016 23:29:24 +0200 (CEST) Received: from fmsmga001.fm.intel.com ([10.253.24.23]) by fmsmga104.fm.intel.com with ESMTP; 26 Aug 2016 14:29:21 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.28,582,1464678000"; d="scan'208";a="1031831542" Received: from sie-lab-214-036.ir.intel.com (HELO silpixa00394365.ir.intel.com) ([10.237.214.36]) by fmsmga001.fm.intel.com with ESMTP; 26 Aug 2016 14:29:20 -0700 From: Pablo de Lara To: dev@dpdk.org Cc: bruce.richardson@intel.com, Pablo de Lara Date: Fri, 26 Aug 2016 22:30:09 +0100 Message-Id: <1472247009-166860-4-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1472247009-166860-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1472247009-166860-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH 3/3] hash: check if slot is empty with key index X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 26 Aug 2016 21:29:25 -0000 Instead of checking if the current and alternative signatures are 0, it is faster to check if the key index associated to an entry is 0, meaning that the slot is empty. Signed-off-by: Pablo de Lara --- lib/librte_hash/rte_cuckoo_hash.c | 16 ++++++++-------- lib/librte_hash/rte_cuckoo_hash.h | 2 ++ lib/librte_hash/rte_cuckoo_hash_x86.h | 5 ++--- 3 files changed, 12 insertions(+), 11 deletions(-) diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index be1490a..dd0290f 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -423,7 +423,7 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) next_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask; next_bkt[i] = &h->buckets[next_bucket_idx]; for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) { - if (next_bkt[i]->signatures[j].sig == NULL_SIGNATURE) + if (next_bkt[i]->key_idx[j] == EMPTY_SLOT) break; } @@ -609,7 +609,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, #endif for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { /* Check if slot is available */ - if (likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) { + if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) { prim_bkt->signatures[i].current = sig; prim_bkt->signatures[i].alt = alt_hash; prim_bkt->key_idx[i] = new_idx; @@ -707,7 +707,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, /* Check if key is in primary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->signatures[i].current == sig && - bkt->signatures[i].sig != NULL_SIGNATURE) { + bkt->key_idx[i] != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { @@ -823,7 +823,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* Check if key is in primary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->signatures[i].current == sig && - bkt->signatures[i].sig != NULL_SIGNATURE) { + bkt->key_idx[i] != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { @@ -834,7 +834,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, * substracting the first dummy index */ ret = bkt->key_idx[i] - 1; - bkt->key_idx[i] = 0; + bkt->key_idx[i] = EMPTY_SLOT; return ret; } } @@ -848,7 +848,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* Check if key is in secondary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->signatures[i].current == alt_hash && - bkt->signatures[i].sig != NULL_SIGNATURE) { + bkt->key_idx[i] != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { @@ -859,7 +859,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, * substracting the first dummy index */ ret = bkt->key_idx[i] - 1; - bkt->key_idx[i] = 0; + bkt->key_idx[i] = EMPTY_SLOT; return ret; } } @@ -1229,7 +1229,7 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32 idx = *next % RTE_HASH_BUCKET_ENTRIES; /* If current position is empty, go to the next one */ - while (h->buckets[bucket_idx].signatures[idx].sig == NULL_SIGNATURE) { + while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) { (*next)++; /* End of table */ if (*next == total_entries) diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 6c76700..e290dab 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -134,6 +134,8 @@ enum add_key_case { #define NULL_SIGNATURE 0 +#define EMPTY_SLOT 0 + #define KEY_ALIGNMENT 16 #define LCORE_CACHE_SIZE 64 diff --git a/lib/librte_hash/rte_cuckoo_hash_x86.h b/lib/librte_hash/rte_cuckoo_hash_x86.h index fa5630b..e16d69c 100644 --- a/lib/librte_hash/rte_cuckoo_hash_x86.h +++ b/lib/librte_hash/rte_cuckoo_hash_x86.h @@ -53,8 +53,7 @@ rte_hash_cuckoo_insert_mw_tm(struct rte_hash_bucket *prim_bkt, */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { /* Check if slot is available */ - if (likely(prim_bkt->signatures[i].sig == - NULL_SIGNATURE)) { + if (likely(prim_bkt->key_idx == EMPTY_SLOT)) { prim_bkt->signatures[i].current = sig; prim_bkt->signatures[i].alt = alt_hash; prim_bkt->key_idx[i] = new_idx; @@ -171,7 +170,7 @@ rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h, queue + RTE_HASH_BFS_QUEUE_MAX_LEN - 4)) { curr_bkt = tail->bkt; for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (curr_bkt->signatures[i].sig == NULL_SIGNATURE) { + if (curr_bkt->key_idx[i] == EMPTY_SLOT) { if (likely(rte_hash_cuckoo_move_insert_mw_tm(h, tail, i, sig, alt_hash, new_idx) == 0)) -- 2.7.4