/** @if DOCUMENTATION_IS_IN_BIHASH_DOC_H */
-void BV(clib_bihash_init)
- (BVT(clib_bihash) * h, char * name, u32 nbuckets,
- uword memory_size)
+void BV (clib_bihash_init)
+ (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
{
- void * oldheap;
+ void *oldheap;
nbuckets = 1 << (max_log2 (nbuckets));
- h->name = (u8 *)name;
+ h->name = (u8 *) name;
h->nbuckets = nbuckets;
h->log2_nbuckets = max_log2 (nbuckets);
- h->mheap = mheap_alloc (0 /* use VM */, memory_size);
+ h->mheap = mheap_alloc (0 /* use VM */ , memory_size);
oldheap = clib_mem_set_heap (h->mheap);
vec_validate_aligned (h->buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
- h->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES,
- CLIB_CACHE_LINE_BYTES);
+ h->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES,
+ CLIB_CACHE_LINE_BYTES);
clib_mem_set_heap (oldheap);
}
-void BV(clib_bihash_free) (BVT(clib_bihash) * h)
+void BV (clib_bihash_free) (BVT (clib_bihash) * h)
{
- mheap_free (h->mheap);
- memset (h, 0, sizeof (*h));
+ mheap_free (h->mheap);
+ memset (h, 0, sizeof (*h));
}
-static BVT(clib_bihash_value) *
-BV(value_alloc) (BVT(clib_bihash) * h, u32 log2_pages)
+static
+BVT (clib_bihash_value) *
+BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
{
- BVT(clib_bihash_value) * rv = 0;
- void * oldheap;
+ BVT (clib_bihash_value) * rv = 0;
+ void *oldheap;
- ASSERT (h->writer_lock[0]);
- if (log2_pages >= vec_len (h->freelists)
- || h->freelists [log2_pages] == 0)
+ ASSERT (h->writer_lock[0]);
+ if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
{
- oldheap = clib_mem_set_heap (h->mheap);
+ oldheap = clib_mem_set_heap (h->mheap);
- vec_validate (h->freelists, log2_pages);
- vec_validate_aligned (rv, (1<<log2_pages) - 1, CLIB_CACHE_LINE_BYTES);
- clib_mem_set_heap (oldheap);
- goto initialize;
+ vec_validate (h->freelists, log2_pages);
+ vec_validate_aligned (rv, (1 << log2_pages) - 1, CLIB_CACHE_LINE_BYTES);
+ clib_mem_set_heap (oldheap);
+ goto initialize;
}
- rv = h->freelists[log2_pages];
- h->freelists[log2_pages] = rv->next_free;
-
- initialize:
- ASSERT(rv);
- ASSERT (vec_len(rv) == (1<<log2_pages));
- /*
- * Latest gcc complains that the length arg is zero
- * if we replace (1<<log2_pages) with vec_len(rv).
- * No clue.
- */
- memset (rv, 0xff, sizeof (*rv) * (1<<log2_pages));
- return rv;
+ rv = h->freelists[log2_pages];
+ h->freelists[log2_pages] = rv->next_free;
+
+initialize:
+ ASSERT (rv);
+ ASSERT (vec_len (rv) == (1 << log2_pages));
+ /*
+ * Latest gcc complains that the length arg is zero
+ * if we replace (1<<log2_pages) with vec_len(rv).
+ * No clue.
+ */
+ memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
+ return rv;
}
static void
-BV(value_free)
- (BVT(clib_bihash) * h,
- BVT(clib_bihash_value) * v)
+BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v)
{
- u32 log2_pages;
+ u32 log2_pages;
- ASSERT (h->writer_lock[0]);
-
- log2_pages = min_log2(vec_len(v));
+ ASSERT (h->writer_lock[0]);
- ASSERT(vec_len (h->freelists) > log2_pages);
+ log2_pages = min_log2 (vec_len (v));
- v->next_free = h->freelists[log2_pages];
- h->freelists[log2_pages] = v;
+ ASSERT (vec_len (h->freelists) > log2_pages);
+
+ v->next_free = h->freelists[log2_pages];
+ h->freelists[log2_pages] = v;
}
static inline void
-BV(make_working_copy)
- (BVT(clib_bihash) * h, clib_bihash_bucket_t * b)
+BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
{
- BVT(clib_bihash_value) * v;
- clib_bihash_bucket_t working_bucket __attribute__((aligned (8)));
- void * oldheap;
- BVT(clib_bihash_value) * working_copy;
- u32 cpu_number = os_get_cpu_number();
+ BVT (clib_bihash_value) * v;
+ clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8)));
+ void *oldheap;
+ BVT (clib_bihash_value) * working_copy;
+ u32 cpu_number = os_get_cpu_number ();
if (cpu_number >= vec_len (h->working_copies))
{
clib_mem_set_heap (oldheap);
}
- /*
+ /*
* working_copies are per-cpu so that near-simultaneous
* updates from multiple threads will not result in sporadic, spurious
- * lookup failures.
+ * lookup failures.
*/
working_copy = h->working_copies[cpu_number];
h->saved_bucket.as_u64 = b->as_u64;
oldheap = clib_mem_set_heap (h->mheap);
- if ((1<<b->log2_pages) > vec_len (working_copy))
+ if ((1 << b->log2_pages) > vec_len (working_copy))
{
- vec_validate_aligned (working_copy, (1<<b->log2_pages)-1,
- sizeof (u64));
+ vec_validate_aligned (working_copy, (1 << b->log2_pages) - 1,
+ sizeof (u64));
h->working_copies[cpu_number] = working_copy;
}
- _vec_len(working_copy) = 1<<b->log2_pages;
+ _vec_len (working_copy) = 1 << b->log2_pages;
clib_mem_set_heap (oldheap);
- v = BV(clib_bihash_get_value) (h, b->offset);
+ v = BV (clib_bihash_get_value) (h, b->offset);
- clib_memcpy (working_copy, v, sizeof (*v)*(1<<b->log2_pages));
+ clib_memcpy (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
working_bucket.as_u64 = b->as_u64;
- working_bucket.offset = BV(clib_bihash_get_offset) (h, working_copy);
- CLIB_MEMORY_BARRIER();
+ working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
+ CLIB_MEMORY_BARRIER ();
b->as_u64 = working_bucket.as_u64;
h->working_copies[cpu_number] = working_copy;
}
-static BVT(clib_bihash_value) *
- BV(split_and_rehash)
- (BVT(clib_bihash) * h,
- BVT(clib_bihash_value) * old_values,
- u32 new_log2_pages)
+static
+BVT (clib_bihash_value) *
+BV (split_and_rehash)
+ (BVT (clib_bihash) * h,
+ BVT (clib_bihash_value) * old_values, u32 new_log2_pages)
{
- BVT(clib_bihash_value) * new_values, * v, * new_v;
+ BVT (clib_bihash_value) * new_values, *v, *new_v;
int i, j, k;
- new_values = BV(value_alloc) (h, new_log2_pages);
+ new_values = BV (value_alloc) (h, new_log2_pages);
v = old_values;
for (i = 0; i < vec_len (old_values); i++)
{
u64 new_hash;
-
+
for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
- {
- if (BV(clib_bihash_is_free)(&(v->kvp[j])) == 0)
- {
- new_hash = BV(clib_bihash_hash) (&(v->kvp[j]));
- new_hash >>= h->log2_nbuckets;
- new_hash &= (1<<new_log2_pages) - 1;
-
- new_v = &new_values [new_hash];
-
- for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
- {
- if (BV(clib_bihash_is_free)(&(new_v->kvp[k])))
- {
- clib_memcpy (&(new_v->kvp[k]), &(v->kvp[j]),
- sizeof (new_v->kvp[k]));
- goto doublebreak;
- }
- }
- /* Crap. Tell caller to try again */
- BV(value_free) (h, new_values);
- return 0;
- }
- doublebreak:
- ;
- }
+ {
+ if (BV (clib_bihash_is_free) (&(v->kvp[j])) == 0)
+ {
+ new_hash = BV (clib_bihash_hash) (&(v->kvp[j]));
+ new_hash >>= h->log2_nbuckets;
+ new_hash &= (1 << new_log2_pages) - 1;
+
+ new_v = &new_values[new_hash];
+
+ for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
+ {
+ if (BV (clib_bihash_is_free) (&(new_v->kvp[k])))
+ {
+ clib_memcpy (&(new_v->kvp[k]), &(v->kvp[j]),
+ sizeof (new_v->kvp[k]));
+ goto doublebreak;
+ }
+ }
+ /* Crap. Tell caller to try again */
+ BV (value_free) (h, new_values);
+ return 0;
+ }
+ doublebreak:
+ ;
+ }
v++;
}
return new_values;
}
-int BV(clib_bihash_add_del)
- (BVT(clib_bihash) * h,
- BVT(clib_bihash_kv) * add_v,
- int is_add)
+int BV (clib_bihash_add_del)
+ (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
{
u32 bucket_index;
- clib_bihash_bucket_t * b, tmp_b;
- BVT(clib_bihash_value) * v, * new_v, * save_new_v, * working_copy;
+ clib_bihash_bucket_t *b, tmp_b;
+ BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
u32 value_index;
int rv = 0;
int i;
u64 hash, new_hash;
u32 new_log2_pages;
- u32 cpu_number = os_get_cpu_number();
-
- hash = BV(clib_bihash_hash) (add_v);
+ u32 cpu_number = os_get_cpu_number ();
- bucket_index = hash & (h->nbuckets-1);
+ hash = BV (clib_bihash_hash) (add_v);
+
+ bucket_index = hash & (h->nbuckets - 1);
b = &h->buckets[bucket_index];
hash >>= h->log2_nbuckets;
while (__sync_lock_test_and_set (h->writer_lock, 1))
- ;
+ ;
/* First elt in the bucket? */
if (b->offset == 0)
{
if (is_add == 0)
- {
- rv = -1;
- goto unlock;
- }
+ {
+ rv = -1;
+ goto unlock;
+ }
- v = BV(value_alloc) (h, 0);
- *v->kvp = * add_v;
+ v = BV (value_alloc) (h, 0);
+ *v->kvp = *add_v;
tmp_b.as_u64 = 0;
- tmp_b.offset = BV(clib_bihash_get_offset) (h, v);
+ tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
b->as_u64 = tmp_b.as_u64;
goto unlock;
}
- BV(make_working_copy) (h, b);
+ BV (make_working_copy) (h, b);
- v = BV(clib_bihash_get_value) (h, h->saved_bucket.offset);
- value_index = hash & ((1<<h->saved_bucket.log2_pages)-1);
+ v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
+ value_index = hash & ((1 << h->saved_bucket.log2_pages) - 1);
v += value_index;
-
+
if (is_add)
{
- /*
+ /*
* For obvious (in hindsight) reasons, see if we're supposed to
* replace an existing key, then look for an empty slot.
*/
for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
- {
- if (!memcmp(&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
- {
- clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
- CLIB_MEMORY_BARRIER();
- /* Restore the previous (k,v) pairs */
- b->as_u64 = h->saved_bucket.as_u64;
- goto unlock;
- }
- }
+ {
+ if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
+ {
+ clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
+ CLIB_MEMORY_BARRIER ();
+ /* Restore the previous (k,v) pairs */
+ b->as_u64 = h->saved_bucket.as_u64;
+ goto unlock;
+ }
+ }
for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
- {
- if (BV(clib_bihash_is_free)(&(v->kvp[i])))
- {
- clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
- CLIB_MEMORY_BARRIER();
- b->as_u64 = h->saved_bucket.as_u64;
- goto unlock;
- }
- }
+ {
+ if (BV (clib_bihash_is_free) (&(v->kvp[i])))
+ {
+ clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
+ CLIB_MEMORY_BARRIER ();
+ b->as_u64 = h->saved_bucket.as_u64;
+ goto unlock;
+ }
+ }
/* no room at the inn... split case... */
}
else
{
for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
- {
- if (!memcmp(&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
- {
- memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
- CLIB_MEMORY_BARRIER();
- b->as_u64 = h->saved_bucket.as_u64;
- goto unlock;
- }
- }
+ {
+ if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
+ {
+ memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
+ CLIB_MEMORY_BARRIER ();
+ b->as_u64 = h->saved_bucket.as_u64;
+ goto unlock;
+ }
+ }
rv = -3;
b->as_u64 = h->saved_bucket.as_u64;
goto unlock;
new_log2_pages = h->saved_bucket.log2_pages + 1;
- expand_again:
+expand_again:
working_copy = h->working_copies[cpu_number];
- new_v = BV(split_and_rehash) (h, working_copy, new_log2_pages);
+ new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
if (new_v == 0)
{
new_log2_pages++;
/* Try to add the new entry */
save_new_v = new_v;
- new_hash = BV(clib_bihash_hash) (add_v);
+ new_hash = BV (clib_bihash_hash) (add_v);
new_hash >>= h->log2_nbuckets;
- new_hash &= (1<<min_log2(vec_len(new_v))) - 1;
+ new_hash &= (1 << min_log2 (vec_len (new_v))) - 1;
new_v += new_hash;
-
+
for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
{
- if (BV(clib_bihash_is_free)(&(new_v->kvp[i])))
- {
- clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
- goto expand_ok;
- }
+ if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
+ {
+ clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
+ goto expand_ok;
+ }
}
/* Crap. Try again */
new_log2_pages++;
- BV(value_free) (h, save_new_v);
+ BV (value_free) (h, save_new_v);
goto expand_again;
- expand_ok:
+expand_ok:
tmp_b.log2_pages = min_log2 (vec_len (save_new_v));
- tmp_b.offset = BV(clib_bihash_get_offset) (h, save_new_v);
- CLIB_MEMORY_BARRIER();
+ tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
+ CLIB_MEMORY_BARRIER ();
b->as_u64 = tmp_b.as_u64;
- v = BV(clib_bihash_get_value) (h, h->saved_bucket.offset);
- BV(value_free) (h, v);
+ v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
+ BV (value_free) (h, v);
- unlock:
- CLIB_MEMORY_BARRIER();
+unlock:
+ CLIB_MEMORY_BARRIER ();
h->writer_lock[0] = 0;
return rv;
}
-int BV(clib_bihash_search)
- (BVT(clib_bihash) * h,
- BVT(clib_bihash_kv) *search_key,
- BVT(clib_bihash_kv) *valuep)
+int BV (clib_bihash_search)
+ (BVT (clib_bihash) * h,
+ BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
{
u64 hash;
u32 bucket_index;
uword value_index;
- BVT(clib_bihash_value) * v;
- clib_bihash_bucket_t * b;
+ BVT (clib_bihash_value) * v;
+ clib_bihash_bucket_t *b;
int i;
- ASSERT(valuep);
+ ASSERT (valuep);
- hash = BV(clib_bihash_hash) (search_key);
+ hash = BV (clib_bihash_hash) (search_key);
- bucket_index = hash & (h->nbuckets-1);
+ bucket_index = hash & (h->nbuckets - 1);
b = &h->buckets[bucket_index];
if (b->offset == 0)
hash >>= h->log2_nbuckets;
- v = BV(clib_bihash_get_value) (h, b->offset);
- value_index = hash & ((1<<b->log2_pages)-1);
+ v = BV (clib_bihash_get_value) (h, b->offset);
+ value_index = hash & ((1 << b->log2_pages) - 1);
v += value_index;
-
+
for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
{
- if (BV(clib_bihash_key_compare)(v->kvp[i].key, search_key->key))
- {
- *valuep = v->kvp[i];
- return 0;
- }
+ if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
+ {
+ *valuep = v->kvp[i];
+ return 0;
+ }
}
return -1;
}
-u8 * BV(format_bihash) (u8 * s, va_list * args)
+u8 *BV (format_bihash) (u8 * s, va_list * args)
{
- BVT(clib_bihash) * h
- = va_arg (*args, BVT(clib_bihash) *);
+ BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
int verbose = va_arg (*args, int);
- clib_bihash_bucket_t * b;
- BVT(clib_bihash_value) * v;
+ clib_bihash_bucket_t *b;
+ BVT (clib_bihash_value) * v;
int i, j, k;
u64 active_elements = 0;
s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
-
+
for (i = 0; i < h->nbuckets; i++)
{
- b = &h->buckets [i];
+ b = &h->buckets[i];
if (b->offset == 0)
- {
- if (verbose > 1)
- s = format (s, "[%d]: empty\n", i);
- continue;
- }
+ {
+ if (verbose > 1)
+ s = format (s, "[%d]: empty\n", i);
+ continue;
+ }
if (verbose)
- {
- s = format (s, "[%d]: heap offset %d, len %d\n", i,
- b->offset, (1<<b->log2_pages));
- }
-
- v = BV(clib_bihash_get_value) (h, b->offset);
- for (j = 0; j < (1<<b->log2_pages); j++)
- {
- for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
- {
- if (BV(clib_bihash_is_free)(&v->kvp[k]))
- {
- if (verbose > 1)
- s = format (s, " %d: empty\n",
- j * BIHASH_KVP_PER_PAGE + k);
- continue;
- }
- if (verbose)
- {
- s = format (s, " %d: %U\n",
- j * BIHASH_KVP_PER_PAGE + k,
- BV(format_bihash_kvp),
- &(v->kvp[k]));
- }
- active_elements++;
- }
- v++;
- }
+ {
+ s = format (s, "[%d]: heap offset %d, len %d\n", i,
+ b->offset, (1 << b->log2_pages));
+ }
+
+ v = BV (clib_bihash_get_value) (h, b->offset);
+ for (j = 0; j < (1 << b->log2_pages); j++)
+ {
+ for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
+ {
+ if (BV (clib_bihash_is_free) (&v->kvp[k]))
+ {
+ if (verbose > 1)
+ s = format (s, " %d: empty\n",
+ j * BIHASH_KVP_PER_PAGE + k);
+ continue;
+ }
+ if (verbose)
+ {
+ s = format (s, " %d: %U\n",
+ j * BIHASH_KVP_PER_PAGE + k,
+ BV (format_bihash_kvp), &(v->kvp[k]));
+ }
+ active_elements++;
+ }
+ v++;
+ }
}
s = format (s, " %lld active elements\n", active_elements);
return s;
}
-void BV(clib_bihash_foreach_key_value_pair)
- (BVT(clib_bihash) * h,
- void *callback,
- void *arg)
+void BV (clib_bihash_foreach_key_value_pair)
+ (BVT (clib_bihash) * h, void *callback, void *arg)
{
int i, j, k;
- clib_bihash_bucket_t * b;
- BVT(clib_bihash_value) * v;
- void (*fp)(BVT(clib_bihash_kv) *, void *) = callback;
-
+ clib_bihash_bucket_t *b;
+ BVT (clib_bihash_value) * v;
+ void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
+
for (i = 0; i < h->nbuckets; i++)
{
- b = &h->buckets [i];
+ b = &h->buckets[i];
if (b->offset == 0)
- continue;
-
- v = BV(clib_bihash_get_value) (h, b->offset);
- for (j = 0; j < (1<<b->log2_pages); j++)
- {
- for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
- {
- if (BV(clib_bihash_is_free)(&v->kvp[k]))
- continue;
-
- (*fp)(&v->kvp[k], arg);
- }
- v++;
- }
+ continue;
+
+ v = BV (clib_bihash_get_value) (h, b->offset);
+ for (j = 0; j < (1 << b->log2_pages); j++)
+ {
+ for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
+ {
+ if (BV (clib_bihash_is_free) (&v->kvp[k]))
+ continue;
+
+ (*fp) (&v->kvp[k], arg);
+ }
+ v++;
+ }
}
}
/** @endif */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
Code Review / vpp.git / blobdiff