aboutsummaryrefslogtreecommitdiffstats
path: root/hicn-plugin/src/hashtb.c
diff options
context:
space:
mode:
Diffstat (limited to 'hicn-plugin/src/hashtb.c')
-rw-r--r--hicn-plugin/src/hashtb.c1017
1 files changed, 0 insertions, 1017 deletions
diff --git a/hicn-plugin/src/hashtb.c b/hicn-plugin/src/hashtb.c
deleted file mode 100644
index 6deddbd84..000000000
--- a/hicn-plugin/src/hashtb.c
+++ /dev/null
@@ -1,1017 +0,0 @@
-/*
- * Copyright (c) 2017-2019 Cisco and/or its affiliates.
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at:
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <stdlib.h>
-#include <errno.h>
-#include <assert.h>
-#include <inttypes.h>
-
-#include <vlib/vlib.h>
-#include <vppinfra/pool.h>
-
-#include "pcs.h"
-#include "hashtb.h"
-#include "parser.h"
-#include "error.h"
-
-/* return dvd/dvr, rounded up (intended for integer values) */
-#define CEIL(dvd, dvr) \
- ({ \
- __typeof__ (dvd) _dvd = (dvd); \
- __typeof__ (dvr) _dvr = (dvr); \
- (_dvd + _dvr - 1)/_dvr; \
- })
-
-#ifndef ALIGN8
-#define ALIGN8(p) (((p) + 0x7) & ~(0x7))
-#endif
-
-#ifndef ALIGNPTR8
-#define ALIGNPTR8(p) ((void *)(((u8 * )(p) + 0x7) & ~(0x7)))
-#endif
-
-#ifndef ALIGN64
-#define ALIGN64(p) (((p) + 0x3f) & ~(0x3f))
-#endif
-
-#ifndef TRUE
-#define TRUE 1
-#endif
-
-#ifndef FALSE
-#define FALSE 0
-#endif
-
-
-/*
- * Offset to aligned start of additional data (PIT/CS, FIB) embedded in each
- * node.
- */
-u32 ht_node_data_offset_aligned;
-
-/* Some support for posix vs vpp mem management */
-#define MEM_ALLOC(x) clib_mem_alloc_aligned((x), 8)
-#define MEM_FREE(p) clib_mem_free((p))
-
-/*
- * Internal utilities
- */
-
-/* Allocate an overflow bucket */
-static hicn_hash_bucket_t *
-alloc_overflow_bucket (hicn_hashtb_h h)
-{
- hicn_hash_bucket_t *newbkt = NULL;
-
- if (h->ht_overflow_buckets_used < h->ht_overflow_bucket_count)
- {
- pool_get_aligned (h->ht_overflow_buckets, newbkt, 8);
-
- if (newbkt)
- {
- h->ht_overflow_buckets_used++;
- }
- }
- return (newbkt);
-}
-
-/* Free an overflow bucket; clear caller's pointer */
-static void
-free_overflow_bucket (hicn_hashtb_h h, hicn_hash_bucket_t ** pb)
-{
- hicn_hash_bucket_t *bkt = *pb;
-
- ASSERT (h->ht_overflow_buckets_used > 0);
-
- pool_put (h->ht_overflow_buckets, bkt);
- h->ht_overflow_buckets_used--;
- *pb = NULL;
-}
-
-/*
- * Init, allocate a new hashtable
- */
-int
-hicn_hashtb_alloc (hicn_hashtb_h * ph, u32 max_elems, size_t app_data_size)
-{
- int ret = HICN_ERROR_NONE;
- hicn_hashtb_h h = NULL;
- u32 count;
- u32 total_buckets;
- size_t sz;
- hicn_hash_node_t *nodep;
- hicn_hash_bucket_t *bucket;
-
- if (ph == NULL)
- {
- ret = HICN_ERROR_HASHTB_INVAL;
- goto done;
- }
- if (max_elems < HICN_HASHTB_MIN_ENTRIES ||
- max_elems > HICN_HASHTB_MAX_ENTRIES)
- {
- goto done;
- }
- /* Allocate and init main hashtable struct */
- h = MEM_ALLOC (sizeof (hicn_hashtb_t));
- if (h == NULL)
- {
- ret = HICN_ERROR_HASHTB_NOMEM;
- goto done;
- }
- memset (h, 0, sizeof (hicn_hashtb_t));
-
- /* Compute main table bucket (row) count and size, and allocate */
-
- /* Consider the last entry as used for containing the overflow bucket */
- total_buckets = CEIL (max_elems, HICN_HASHTB_BUCKET_ENTRIES - 1);
- count = ALIGN8 (CEIL (total_buckets, HICN_HASHTB_FILL_FACTOR));
-
- h->ht_bucket_count = count;
-
- /* We _really_ expect to have buckets aligned on cache lines ... */
- sz = sizeof (hicn_hash_bucket_t);
- assert (sz == ALIGN64 (sz));
-
- h->ht_buckets = MEM_ALLOC (count * sz);
- if (h->ht_buckets == NULL)
- {
- ret = HICN_ERROR_HASHTB_NOMEM;
- goto done;
- }
- memset (h->ht_buckets, 0, count * sz);
-
- /*
- * First time through, compute offset to aligned extra data start in
- * each node struct it's crucial that both the node struct (that the
- * base hashtable uses) and the extra data area (that's also probably
- * a struct) are aligned.
- */
- if (ht_node_data_offset_aligned == 0)
- {
- count = STRUCT_OFFSET_OF (hicn_hash_node_t, hn_data);
- ht_node_data_offset_aligned = ALIGN8 (count);
- }
- //check app struct fits into space provided(HICN_HASH_NODE_APP_DATA_SIZE)
- u32 ht_node_data_size;
- ht_node_data_size = sizeof (hicn_hash_node_t) - ht_node_data_offset_aligned;
- if (app_data_size > ht_node_data_size)
- {
- clib_error
- ("hicn hashtable: fatal error: requested app data size(%u) > hashtb node's configured bytes available(%u), sizeof(hicn_shared_t)=%u, sizeof(hicn_pit_entry_t)=%u, sizeof(hicn_cs_entry_t)=%u",
- app_data_size, ht_node_data_size, sizeof (hicn_pcs_shared_t),
- sizeof (hicn_pit_entry_t), sizeof (hicn_cs_entry_t));
- }
- /*
- * Compute entry node count and size, allocate Allocate/'Hide' the
- * zero-th node so can use zero as an 'empty' value
- */
- pool_alloc_aligned (h->ht_nodes, max_elems, 8);
- if (h->ht_nodes == NULL)
- {
- ret = HICN_ERROR_HASHTB_NOMEM;
- goto done;
- }
- pool_get_aligned (h->ht_nodes, nodep, 8);
- //alloc node 0
- nodep = nodep; /* Silence 'not used' warning */
-
- h->ht_node_count = max_elems;
- h->ht_nodes_used = 1;
-
- /*
- * Compute overflow bucket count and size, allocate
- */
- //count = ALIGN8(CEIL(max_elems, HICN_HASHTB_OVERFLOW_FRACTION));
- count = ALIGN8 (total_buckets - h->ht_bucket_count);
-
- pool_alloc_aligned (h->ht_overflow_buckets, count, 8);
- if (h->ht_overflow_buckets == NULL)
- {
- ret = HICN_ERROR_HASHTB_NOMEM;
- goto done;
- }
- /* 'Hide' the zero-th node so we can use zero as an 'empty' value */
- pool_get_aligned (h->ht_overflow_buckets, bucket, 8);
- bucket = bucket; /* Silence 'not used' warning */
-
- h->ht_overflow_bucket_count = count;
- h->ht_overflow_buckets_used = 1;
-
-done:
-
- if (h)
- {
- if ((ret == HICN_ERROR_NONE) && ph)
- {
- *ph = h;
- }
- else
- {
- hicn_hashtb_free (&h);
- }
- }
- return (ret);
-}
-
-/*
- * Free, de-allocate a hashtable
- */
-int
-hicn_hashtb_free (hicn_hashtb_h * ph)
-{
- int ret = 0;
-
- if (ph)
- {
- if ((*ph)->ht_nodes)
- {
- pool_free ((*ph)->ht_nodes);
- (*ph)->ht_nodes = 0;
- }
- if ((*ph)->ht_overflow_buckets)
- {
- pool_free ((*ph)->ht_overflow_buckets);
- (*ph)->ht_overflow_buckets = 0;
- }
- if ((*ph)->ht_buckets)
- {
- MEM_FREE ((*ph)->ht_buckets);
- (*ph)->ht_buckets = 0;
- }
- MEM_FREE (*ph);
-
- *ph = NULL;
- }
- return (ret);
-}
-
-
-
-/*
- * Basic api to lookup a specific hash+key tuple. This does the entire lookup
- * operation, retrieving node structs and comparing keys, so it's not
- * optimized for prefetching or high performance.
- *
- * Returns zero and mails back a node on success, errno otherwise.
- */
-int
-hicn_hashtb_lookup_node (hicn_hashtb_h h, const u8 * key,
- u32 keylen, u64 hashval, u8 is_data,
- u32 * node_id, index_t * dpo_ctx_id, u8 * vft_id,
- u8 * is_cs, u8 * hash_entry_id, u32 * bucket_id,
- u8 * bucket_is_overflow)
-{
- return (hicn_hashtb_lookup_node_ex
- (h, key, keylen, hashval, is_data, FALSE /* deleted nodes */ ,
- node_id,
- dpo_ctx_id, vft_id, is_cs, hash_entry_id, bucket_id,
- bucket_is_overflow));
-}
-
-/*
- * Extended api to lookup a specific hash+key tuple. The implementation
- * allows the caller to locate nodes that are marked for deletion, which is
- * part of some hashtable applications, such as the FIB.
- *
- * This does the entire lookup operation, retrieving node structs and comparing
- * keys, so it's not optimized for prefetching or high performance.
- *
- * Returns zero and mails back a node on success, errno otherwise.
- */
-int
-hicn_hashtb_lookup_node_ex (hicn_hashtb_h h, const u8 * key,
- u32 keylen, u64 hashval, u8 is_data,
- int include_deleted_p, u32 * node_id,
- index_t * dpo_ctx_id, u8 * vft_id, u8 * is_cs,
- u8 * hash_entry_id, u32 * bucket_id,
- u8 * bucket_is_overflow)
-{
- int i, ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND;
- int found_p = FALSE;
- u32 bidx;
- hicn_hash_bucket_t *bucket;
- u32 current_bucket_id = ~0;
-
- /*
- * Use some bits of the low half of the hash to locate a row/bucket
- * in the table
- */
- current_bucket_id = bidx = (hashval & (h->ht_bucket_count - 1));
-
- bucket = h->ht_buckets + bidx;
-
- *bucket_is_overflow = 0;
- /* Check the entries in the bucket for matching hash value */
-
-loop_buckets:
-
- for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES && !found_p; i++)
- {
- /*
- * If an entry is marked for deletion, ignore it unless the
- * caller explicitly wants these nodes.
- */
- if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED)
- {
- if (!include_deleted_p)
- {
- continue;
- }
- }
- if (bucket->hb_entries[i].he_msb64 == hashval)
- {
- /*
- * Found a candidate - must retrieve the actual node
- * and check the key.
- */
- *node_id = bucket->hb_entries[i].he_node;
- *dpo_ctx_id = bucket->hb_entries[i].dpo_ctx_id;
- *vft_id = bucket->hb_entries[i].vft_id;
- *is_cs =
- bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_CS_ENTRY;
- *hash_entry_id = i;
- *bucket_id = current_bucket_id;
- /*
- * If we are doing lookup for a data, do not take a
- * lock in case of a hit with a CS entry
- */
- if (!(is_data && *is_cs))
- {
- bucket->hb_entries[i].locks++;
- }
- found_p = TRUE;
- ret = HICN_ERROR_NONE;
- goto done;
- }
- }
-
- /*
- * Be prepared to continue to an overflow bucket if necessary. We
- * only expect the last entry in a bucket to refer to an overflow
- * bucket...
- */
- i = HICN_HASHTB_BUCKET_ENTRIES - 1;
- if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)
- {
- current_bucket_id = bucket->hb_entries[i].he_node;
- bucket = pool_elt_at_index (h->ht_overflow_buckets,
- bucket->hb_entries[i].he_node);
- *bucket_is_overflow = 1;
- goto loop_buckets;
- }
-done:
-
- return (ret);
-}
-
-/**
- * This function allows to split the hash verification from the comparison of
- * the entire key. Useful to exploit prefertching.
- * return 1 if equals, 0 otherwise
- */
-int
-hicn_node_compare (const u8 * key, u32 keylen, hicn_hash_node_t * node)
-{
-
- int ret = 0;
-
- if (key && keylen == node->hn_keysize)
- {
- ret = (memcmp (key, node->hn_key.ks.key, keylen) == 0);
- }
- return ret;
-}
-
-/*
- * Utility to init a new entry in a hashtable bucket/row. We use this to add
- * new a node+hash, and to clear out an entry during removal.
- */
-void
-hicn_hashtb_init_entry (hicn_hash_entry_t * entry, u32 nodeidx,
- u64 hashval, u32 locks)
-{
- entry->he_msb64 = hashval;
- entry->he_node = nodeidx;
-
- /* Clear out some other fields in the entry */
- entry->he_flags = 0;
- entry->locks = locks;
- entry->vft_id = 0;
- entry->dpo_ctx_id = 0;
-}
-
-/*
- * Insert a node into the hashtable. We expect the caller has a) computed the
- * hash value to use, b) initialized the node with the hash and key info, and
- * c) filled in its app-specific data portion of the node.
- */
-
-int
-hicn_hashtb_insert (hicn_hashtb_h h, hicn_hash_node_t * node,
- hicn_hash_entry_t ** hash_entry, u64 hash,
- u32 * node_id,
- index_t * dpo_ctx_id, u8 * vft_id, u8 * is_cs,
- u8 * hash_entry_id, u32 * bucket_id,
- u8 * bucket_is_overflow)
-{
- int i, ret = HICN_ERROR_HASHTB_INVAL;
- u32 bidx;
- hicn_hash_bucket_t *bucket, *newbkt;
- int use_seven;
- u32 current_bucket_id = ~0;
- int is_overflow = 0;
-
- *hash_entry = NULL;
-
- if (h == NULL)
- {
- goto done;
- }
- /*
- * Use some bits of the low half of the hash to locate a row/bucket
- * in the table
- */
- current_bucket_id = bidx = (hash & (h->ht_bucket_count - 1));
-
- bucket = h->ht_buckets + bidx;
-
- use_seven = (h->ht_flags & HICN_HASHTB_FLAG_USE_SEVEN);
-
- /* Locate a free entry slot in the bucket */
-
-loop_buckets:
-
- for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++)
- {
-
- /*
- * If an entry is marked for deletion, ignore it
- */
- if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED)
- {
- continue;
- }
- /*
- * Be sure that we are not inserting the same entry twice
- */
- if (bucket->hb_entries[i].he_msb64 == hash)
- {
- /*
- * We hit an existing pit entry. increase lock.
- */
-
- *node_id = bucket->hb_entries[i].he_node;
- *dpo_ctx_id = bucket->hb_entries[i].dpo_ctx_id;
- *vft_id = bucket->hb_entries[i].vft_id;
- *is_cs =
- bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_CS_ENTRY;
- *hash_entry_id = i;
- *bucket_id = current_bucket_id;
- *hash_entry = &(bucket->hb_entries[i]);
- /*
- * If we are doing lookup for a data, do not take a
- * lock in case of a hit with a CS entry
- */
- if (!(*is_cs))
- bucket->hb_entries[i].locks++;
- *bucket_is_overflow = is_overflow;
- ret = HICN_ERROR_HASHTB_EXIST;
- goto done;
- }
- if ((bucket->hb_entries[i].he_msb64 == 0LL) &&
- (bucket->hb_entries[i].he_node == 0))
- {
- /* Found a candidate -- fill it in */
-
- /*
- * Special case if the application asked not to use
- * the last entry in each bucket.
- */
- if ((i != (HICN_HASHTB_BUCKET_ENTRIES - 1)) || use_seven)
- {
- hicn_hashtb_init_entry (&(bucket->hb_entries[i]),
- NODE_IDX_FROM_NODE (node, h), hash, 0);
-
- *hash_entry = &(bucket->hb_entries[i]);
-
- node->bucket_id = current_bucket_id;
- node->entry_idx = i;
- (*hash_entry)->vft_id = *vft_id;
- (*hash_entry)->dpo_ctx_id = *dpo_ctx_id;
- if (is_overflow)
- node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET;
-
- ret = HICN_ERROR_NONE;
- goto done;
- }
- }
- }
- /*
- * Be prepared to continue to an overflow bucket if necessary, or to
- * add a new overflow bucket. We only expect the last entry in a
- * bucket to refer to an overflow bucket...
- */
- i = HICN_HASHTB_BUCKET_ENTRIES - 1;
- if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)
- {
- /* Existing overflow bucket - re-start the search loop */
- current_bucket_id = bucket->hb_entries[i].he_node;
- bucket = pool_elt_at_index (h->ht_overflow_buckets, current_bucket_id);
- is_overflow = 1;
- goto loop_buckets;
-
- }
- else
- {
- /*
- * Overflow - reached the end of a bucket without finding a
- * free entry slot. Need to allocate an overflow bucket, and
- * connect it to this bucket.
- */
- newbkt = alloc_overflow_bucket (h);
- if (newbkt == NULL)
- {
- ret = HICN_ERROR_HASHTB_NOMEM;
- goto done;
- }
- /*
- * We're touching some more bytes than we absolutely have to
- * here, but ... that seems ok.
- */
- memset (newbkt, 0, sizeof (hicn_hash_bucket_t));
-
- if (use_seven)
- {
- /*
- * Copy existing entry into new bucket - we really
- * expect these to be properly aligned so they can be
- * treated as int.
- */
- memcpy (&(newbkt->hb_entries[0]),
- &(bucket->hb_entries[i]), sizeof (hicn_hash_entry_t));
-
- /* Update bucket id and entry_idx on the hash node */
- hicn_hash_node_t *node =
- pool_elt_at_index (h->ht_nodes, newbkt->hb_entries[0].he_node);
- node->bucket_id = (newbkt - h->ht_overflow_buckets);
- node->entry_idx = 0;
- node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET;
-
- }
- /*
- * Connect original bucket to the index of the new overflow
- * bucket
- */
- bucket->hb_entries[i].he_flags |= HICN_HASH_ENTRY_FLAG_OVERFLOW;
- bucket->hb_entries[i].he_node = (newbkt - h->ht_overflow_buckets);
-
- /* Add new entry to new overflow bucket */
- bucket = newbkt;
-
- /*
- * Use entry [1] in the new bucket _if_ we just copied into
- * entry [zero] above.
- */
- if (use_seven)
- {
-
- hicn_hashtb_init_entry (&(bucket->hb_entries[1]),
- NODE_IDX_FROM_NODE (node, h), hash, 0);
- *hash_entry = &(bucket->hb_entries[1]);
-
- node->bucket_id = (newbkt - h->ht_overflow_buckets);
- node->entry_idx = 1;
- node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET;
- (*hash_entry)->vft_id = *vft_id;
- (*hash_entry)->dpo_ctx_id = *dpo_ctx_id;
- }
- else
- {
-
- hicn_hashtb_init_entry (&(bucket->hb_entries[0]),
- NODE_IDX_FROM_NODE (node, h), hash, 0);
- *hash_entry = &(bucket->hb_entries[0]);
- node->bucket_id = (newbkt - h->ht_overflow_buckets);
- node->entry_idx = 0;
- node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET;
- (*hash_entry)->vft_id = *vft_id;
- (*hash_entry)->dpo_ctx_id = *dpo_ctx_id;
- }
- }
-
- /* And we're done with the overflow bucket */
- ret = HICN_ERROR_NONE;
-
-done:
-
- return (ret);
-}
-
-/*
- * Delete a node from a hashtable using the node itself, and delete/free the
- * node. Caller's pointer is cleared on success.
- */
-void
-hicn_hashtb_delete (hicn_hashtb_h h, hicn_hash_node_t ** pnode, u64 hashval)
-{
-
- hicn_hashtb_remove_node (h, *pnode, hashval);
- hicn_hashtb_free_node (h, *pnode);
- *pnode = NULL;
-
-}
-
-/*
- * Delete an entry from a hashtable using the node itself. If the node was
- * stored in an overflow bucket, and the bucket is empty after freeing the
- * node, the bucket is freed as well.
- */
-void
-hicn_hashtb_remove_node (hicn_hashtb_h h, hicn_hash_node_t * node,
- u64 hashval)
-{
- int i, count;
- u32 bidx, overflow_p;
- hicn_hash_bucket_t *bucket, *parent;
-
- if ((h == NULL) || (node == NULL))
- {
- goto done;
- }
- if (node->hn_flags & HICN_HASH_NODE_OVERFLOW_BUCKET)
- bucket = pool_elt_at_index (h->ht_overflow_buckets, node->bucket_id);
- else
- {
- /*
- * Use some bits of the low half of the hash to locate a
- * row/bucket in the table
- */
- bidx = (hashval & (h->ht_bucket_count - 1));
- ASSERT (bidx == node->bucket_id);
- bucket = h->ht_buckets + node->bucket_id;
- }
-
- overflow_p = node->hn_flags & HICN_HASH_NODE_OVERFLOW_BUCKET;
-
- /* Clear out the entry. */
- hicn_hashtb_init_entry (&(bucket->hb_entries[node->entry_idx]), 0, 0LL, 0);
-
- if (!overflow_p)
- {
- /*
- * And we're done, in the easy case where we didn't change an
- * overflow bucket
- */
- goto done;
- }
- /*
- * The special case: if this is the last remaining entry in an
- * overflow bucket, liberate the bucket. That in turn has a special
- * case if this bucket is in the middle of a chain of overflow
- * buckets.
- *
- * Note that we're not trying aggressively (yet) to condense buckets at
- * every possible opportunity.
- */
-
- /*
- * Reset this flag; we'll set it again if this bucket links to
- * another
- */
- overflow_p = FALSE;
-
- for (i = 0, count = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++)
- {
- if (bucket->hb_entries[i].he_node != 0)
- {
- count++;
- }
- if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1) &&
- (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW))
- {
- count--; /* Doesn't count as a 'real' entry */
- overflow_p = TRUE;
- }
- }
-
- if (count > 0)
- {
- /* Still a (real) entry in the row */
- goto done;
- }
- /*
- * Need to locate the predecessor of 'bucket': start at the beginning
- * of the chain of buckets and move forward
- */
- bidx = (hashval & (h->ht_bucket_count - 1));
-
- for (parent = h->ht_buckets + bidx; parent != NULL;)
- {
-
- if ((parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_flags &
- HICN_HASH_ENTRY_FLAG_OVERFLOW) == 0)
- {
- parent = NULL;
- break;
- }
- bidx = parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node;
-
- if (pool_elt_at_index (h->ht_overflow_buckets, bidx) == bucket)
- {
- /*
- * Found the predecessor of 'bucket'. If 'bucket' has
- * a successor, connect 'parent' to it, and take
- * 'bucket out of the middle.
- */
- if (overflow_p)
- {
- parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node =
- bucket->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node;
- }
- else
- {
- /*
- * Just clear the predecessor entry pointing
- * at 'bucket'
- */
- hicn_hashtb_init_entry (&parent->hb_entries
- [(HICN_HASHTB_BUCKET_ENTRIES - 1)], 0,
- 0LL, 0);
- }
-
- break;
- }
- /*
- * After the first iteration, 'parent' will be an overflow
- * bucket too
- */
- parent = pool_elt_at_index (h->ht_overflow_buckets, bidx);
- }
-
- /* We really expect to have found the predecessor */
- ASSERT (parent != NULL);
-
- /* And now, finally, we can put 'bucket' back on the free list */
- free_overflow_bucket (h, &bucket);
-
-done:
- return;
-}
-
-/*
- * Prepare a hashtable node, supplying the key, and computed hash info.
- */
-void
-hicn_hashtb_init_node (hicn_hashtb_h h, hicn_hash_node_t * node,
- const u8 * key, u32 keylen)
-{
- assert (h != NULL);
- assert (node != NULL);
- assert (keylen <= HICN_PARAM_HICN_NAME_LEN_MAX);
-
- /* Init the node struct */
- node->hn_flags = HICN_HASH_NODE_FLAGS_DEFAULT;
- node->hn_keysize = 0;
- node->hn_keysize = keylen;
- memcpy (node->hn_key.ks.key, key, keylen);
- node->bucket_id = ~0;
- node->entry_idx = ~0;
-}
-
-/*
- * Release a hashtable node back to the free list when an entry is cleared
- */
-void
-hicn_hashtb_free_node (hicn_hashtb_h h, hicn_hash_node_t * node)
-{
- ASSERT (h->ht_nodes_used > 0);
-
- /* Return 'node' to the free list */
- pool_put (h->ht_nodes, node);
- h->ht_nodes_used--;
-
-}
-
-/*
- * Walk a hashtable, iterating through the nodes, keeping context in 'ctx'.
- */
-int
-hicn_hashtb_next_node (hicn_hashtb_h h, hicn_hash_node_t ** pnode, u64 * ctx)
-{
- int i, j, ret = HICN_ERROR_HASHTB_INVAL;
- u32 bidx, entry;
- hicn_hash_bucket_t *bucket;
-
- if ((h == NULL) || (pnode == NULL) || (ctx == NULL))
- {
- goto done;
- }
- /* Special-case for new iteration */
- if (*ctx == HICN_HASH_WALK_CTX_INITIAL)
- {
- bidx = 0;
- bucket = &h->ht_buckets[0];
- entry = 0;
- j = 0;
- i = 0;
- goto search_table;
- }
- /* Convert context to bucket and entry indices */
- bidx = *ctx & 0xffffffffLL;
- entry = *ctx >> 32;
-
- if (bidx >= h->ht_bucket_count)
- {
- ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND;
- goto done;
- }
- bucket = h->ht_buckets + bidx;
-
- /* Init total index into entries (includes fixed bucket and overflow) */
- j = 0;
-
-skip_processed_bucket_chunks:
- /*
- * Figure out where to resume the search for the next entry in the
- * table, by trying to find the last entry returned, from the cookie.
- * Loop walks one (regular or overflow) bucket chunk, label is used
- * for walking chain of chunks. Note that if there was a deletion or
- * an addition that created an overflow, iterator can skip entries or
- * return duplicate entries, for entries that are present from before
- * the walk starts until after it ends.
- */
-
- for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++, j++)
- {
- if (j > entry)
- {
- /*
- * Start search for next here, use existing 'bucket'
- * and 'i'
- */
- break;
- }
- /*
- * If an entry is marked for deletion, ignore it
- */
- if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED)
- {
- continue;
- }
- /*
- * Be prepared to continue to an overflow bucket if
- * necessary. (We only expect the last entry in a bucket to
- * refer to an overflow bucket...)
- */
- if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1))
- {
- if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)
- {
- bucket = pool_elt_at_index (h->ht_overflow_buckets,
- bucket->hb_entries[i].he_node);
-
- /* Increment overall entry counter 'j' */
- j++;
-
- goto skip_processed_bucket_chunks;
- }
- /*
- * end of row (end of fixed bucket plus any
- * overflows)
- */
- i = 0;
- j = 0;
-
- bidx++;
-
- /* Special case - we're at the end */
- if (bidx >= h->ht_bucket_count)
- {
- ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND;
- goto done;
- }
- bucket = h->ht_buckets + bidx;
- break;
- }
- }
-
-search_table:
-
- /*
- * Now we're searching through the table for the next entry that's
- * set
- */
-
- for (; i < HICN_HASHTB_BUCKET_ENTRIES; i++, j++)
- {
- /*
- * If an entry is marked for deletion, ignore it
- */
- if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED)
- {
- continue;
- }
- /* Is this entry set? */
- if (bucket->hb_entries[i].he_node != 0)
- {
-
- /* Retrieve the node struct */
- *pnode = pool_elt_at_index (h->ht_nodes,
- bucket->hb_entries[i].he_node);
-
- /*
- * Set 'entry' as we exit, so we can update the
- * cookie
- */
- entry = j;
- ret = HICN_ERROR_NONE;
- break;
- }
- /*
- * Be prepared to continue to an overflow bucket if
- * necessary. (We only expect the last entry in a bucket to
- * refer to an overflow bucket...)
- */
- if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1))
- {
- if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)
- {
- bucket = pool_elt_at_index (h->ht_overflow_buckets,
- bucket->hb_entries[i].he_node);
- /*
- * Reset per-bucket index 'i', here (not done
- * in iterator)
- */
- i = 0;
- /* Increment overall entry counter 'j' */
- j++;
-
- goto search_table;
- }
- else
- {
- /*
- * Move to next bucket, resetting per-bucket
- * and overall entry indexes
- */
- i = 0;
- j = 0;
-
- bidx++;
-
- /* Special case - we're at the end */
- if (bidx >= h->ht_bucket_count)
- {
- ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND;
- goto done;
- }
- bucket = h->ht_buckets + bidx;
- goto search_table;
- }
- }
- }
-
-done:
-
- if (ret == HICN_ERROR_NONE)
- {
- /* Update context */
- *ctx = bidx;
- *ctx |= ((u64) entry << 32);
- }
- return (ret);
-}
-
-int
-hicn_hashtb_key_to_buf (u8 ** vec_res, hicn_hashtb_h h,
- const hicn_hash_node_t * node)
-{
- int ret = HICN_ERROR_NONE;
- u8 *vec = *vec_res;
-
- if (node->hn_keysize <= HICN_HASH_KEY_BYTES)
- {
- vec_add (vec, node->hn_key.ks.key, node->hn_keysize);
- }
- *vec_res = vec;
- return (ret);
-}
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables: eval: (c-set-style "gnu") End:
- */