1 files changed, 0 insertions, 455 deletions
diff --git a/vppinfra/vppinfra/bihash_template.c b/vppinfra/vppinfra/bihash_template.c
deleted file mode 100644
index 4b0b425788a..00000000000
--- a/vppinfra/vppinfra/bihash_template.c
+++ /dev/null
@@ -1,455 +0,0 @@
-/*
- * Copyright (c) 2015 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.
- */
-
-/** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */
-
-void BV (clib_bihash_init)
-  (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
-{
-  void *oldheap;
-
-  nbuckets = 1 << (max_log2 (nbuckets));
-
-  h->name = (u8 *) name;
-  h->nbuckets = nbuckets;
-  h->log2_nbuckets = max_log2 (nbuckets);
-
-  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);
-
-  clib_mem_set_heap (oldheap);
-}
-
-void BV (clib_bihash_free) (BVT (clib_bihash) * 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)
-{
-  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)
-    {
-      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;
-    }
-  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)
-{
-  u32 log2_pages;
-
-  ASSERT (h->writer_lock[0]);
-
-  log2_pages = min_log2 (vec_len (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)
-{
-  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))
-    {
-      oldheap = clib_mem_set_heap (h->mheap);
-      vec_validate (h->working_copies, cpu_number);
-      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.
-   */
-  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))
-    {
-      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;
-  clib_mem_set_heap (oldheap);
-
-  v = BV (clib_bihash_get_value) (h, b->offset);
-
-  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 ();
-  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)
-{
-  BVT (clib_bihash_value) * new_values, *v, *new_v;
-  int i, j, k;
-
-  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:
-	  ;
-	}
-      v++;
-    }
-  return new_values;
-}
-
-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;
-  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);
-
-  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;
-	}
-
-      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);
-
-      b->as_u64 = tmp_b.as_u64;
-      goto unlock;
-    }
-
-  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 += 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;
-	    }
-	}
-      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;
-	    }
-	}
-      /* 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;
-	    }
-	}
-      rv = -3;
-      b->as_u64 = h->saved_bucket.as_u64;
-      goto unlock;
-    }
-
-  new_log2_pages = h->saved_bucket.log2_pages + 1;
-
-expand_again:
-  working_copy = h->working_copies[cpu_number];
-  new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
-  if (new_v == 0)
-    {
-      new_log2_pages++;
-      goto expand_again;
-    }
-
-  /* Try to add the new entry */
-  save_new_v = new_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_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;
-	}
-    }
-  /* Crap. Try again */
-  new_log2_pages++;
-  BV (value_free) (h, save_new_v);
-  goto expand_again;
-
-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 ();
-  b->as_u64 = tmp_b.as_u64;
-  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
-  BV (value_free) (h, v);
-
-unlock:
-  CLIB_MEMORY_BARRIER ();
-  h->writer_lock[0] = 0;
-  return rv;
-}
-
-int BV (clib_bihash_search)
-  (const 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;
-  int i;
-
-  ASSERT (valuep);
-
-  hash = BV (clib_bihash_hash) (search_key);
-
-  bucket_index = hash & (h->nbuckets - 1);
-  b = &h->buckets[bucket_index];
-
-  if (b->offset == 0)
-    return -1;
-
-  hash >>= h->log2_nbuckets;
-
-  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;
-	}
-    }
-  return -1;
-}
-
-u8 *BV (format_bihash) (u8 * s, va_list * args)
-{
-  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;
-  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];
-      if (b->offset == 0)
-	{
-	  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, "    %lld active elements\n", active_elements);
-  s = format (s, "    %d free lists\n", vec_len (h->freelists));
-
-  return s;
-}
-
-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;
-
-  for (i = 0; i < h->nbuckets; 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++;
-	}
-    }
-}
-
-/** @endcond */
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */