vppinfra: move unused code to extras/deprecated/vppinfra

Type: improvement

Signed-off-by: Dave Barach <dave@barachs.net>
Change-Id: Id28299a188feefa1899d835fd499f018af95d81b

1 files changed, 0 insertions, 1017 deletions

diff --git a/src/vppinfra/phash.c b/src/vppinfra/phash.c
deleted file mode 100644
index 52c29b33f78..00000000000
--- a/src/vppinfra/phash.c
+++ /dev/null
@@ -1,1017 +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.
- */
-/*
-  Copyright (c) 2005 Eliot Dresselhaus
-
-  Permission is hereby granted, free of charge, to any person obtaining
-  a copy of this software and associated documentation files (the
-  "Software"), to deal in the Software without restriction, including
-  without limitation the rights to use, copy, modify, merge, publish,
-  distribute, sublicense, and/or sell copies of the Software, and to
-  permit persons to whom the Software is furnished to do so, subject to
-  the following conditions:
-
-  The above copyright notice and this permission notice shall be
-  included in all copies or substantial portions of the Software.
-
-  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
-  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
-  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
-  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
-  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-*/
-
-/* This is all stolen from Bob Jenkins and reworked for clib.  Thanks
-   once again Bob for the great work. */
-
-/*
-------------------------------------------------------------------------------
-perfect.c: code to generate code for a hash for perfect hashing.
-(c) Bob Jenkins, September 1996, December 1999
-You may use this code in any way you wish, and it is free.  No warranty.
-I hereby place this in the public domain.
-Source is http://burtleburtle.net/bob/c/perfect.c
-
-This generates a minimal perfect hash function.  That means, given a
-set of n keys, this determines a hash function that maps each of
-those keys into a value in 0..n-1 with no collisions.
-
-The perfect hash function first uses a normal hash function on the key
-to determine (a,b) such that the pair (a,b) is distinct for all
-keys, then it computes a^scramble[tab[b]] to get the final perfect hash.
-tab[] is an array of 1-byte values and scramble[] is a 256-term array of
-2-byte or 4-byte values.  If there are n keys, the length of tab[] is a
-power of two between n/3 and n.
-
-I found the idea of computing distinct (a,b) values in "Practical minimal
-perfect hash functions for large databases", Fox, Heath, Chen, and Daoud,
-Communications of the ACM, January 1992.  They found the idea in Chichelli
-(CACM Jan 1980).  Beyond that, our methods differ.
-
-The key is hashed to a pair (a,b) where a in 0..*alen*-1 and b in
-0..*blen*-1.  A fast hash function determines both a and b
-simultaneously.  Any decent hash function is likely to produce
-hashes so that (a,b) is distinct for all pairs.  I try the hash
-using different values of *salt* until all pairs are distinct.
-
-The final hash is (a XOR scramble[tab[b]]).  *scramble* is a
-predetermined mapping of 0..255 into 0..smax-1.  *tab* is an
-array that we fill in in such a way as to make the hash perfect.
-
-First we fill in all values of *tab* that are used by more than one
-key.  We try all possible values for each position until one works.
-
-This leaves m unmapped keys and m values that something could hash to.
-If you treat unmapped keys as lefthand nodes and unused hash values
-as righthand nodes, and draw a line connecting each key to each hash
-value it could map to, you get a bipartite graph.  We attempt to
-find a perfect matching in this graph.  If we succeed, we have
-determined a perfect hash for the whole set of keys.
-
-*scramble* is used because (a^tab[i]) clusters keys around *a*.
-------------------------------------------------------------------------------
-*/
-
-#include <vppinfra/bitmap.h>
-#include <vppinfra/format.h>
-#include <vppinfra/phash.h>
-#include <vppinfra/random.h>
-
-static void
-init_keys_direct_u32 (phash_main_t * pm)
-{
-  int n_keys_left, b_mask, a_shift;
-  u32 seed;
-  phash_key_t *k;
-
-  seed = pm->hash_seed;
-  b_mask = (1 << pm->b_bits) - 1;
-  a_shift = BITS (seed) - pm->a_bits;
-
-  k = pm->keys;
-  n_keys_left = vec_len (pm->keys);
-
-  while (n_keys_left >= 2)
-    {
-      u32 x0, y0, z0;
-      u32 x1, y1, z1;
-
-      x0 = y0 = z0 = seed;
-      x1 = y1 = z1 = seed;
-      x0 += (u32) k[0].key;
-      x1 += (u32) k[1].key;
-
-      hash_mix32 (x0, y0, z0);
-      hash_mix32 (x1, y1, z1);
-
-      k[0].b = z0 & b_mask;
-      k[1].b = z1 & b_mask;
-      k[0].a = z0 >> a_shift;
-      k[1].a = z1 >> a_shift;
-      if (PREDICT_FALSE (a_shift >= BITS (z0)))
-	k[0].a = k[1].a = 0;
-
-      k += 2;
-      n_keys_left -= 2;
-    }
-
-  if (n_keys_left >= 1)
-    {
-      u32 x0, y0, z0;
-
-      x0 = y0 = z0 = seed;
-      x0 += k[0].key;
-
-      hash_mix32 (x0, y0, z0);
-
-      k[0].b = z0 & b_mask;
-      k[0].a = z0 >> a_shift;
-      if (PREDICT_FALSE (a_shift >= BITS (z0)))
-	k[0].a = 0;
-
-      k += 1;
-      n_keys_left -= 1;
-    }
-}
-
-static void
-init_keys_direct_u64 (phash_main_t * pm)
-{
-  int n_keys_left, b_mask, a_shift;
-  u64 seed;
-  phash_key_t *k;
-
-  seed = pm->hash_seed;
-  b_mask = (1 << pm->b_bits) - 1;
-  a_shift = BITS (seed) - pm->a_bits;
-
-  k = pm->keys;
-  n_keys_left = vec_len (pm->keys);
-
-  while (n_keys_left >= 2)
-    {
-      u64 x0, y0, z0;
-      u64 x1, y1, z1;
-
-      x0 = y0 = z0 = seed;
-      x1 = y1 = z1 = seed;
-      x0 += (u64) k[0].key;
-      x1 += (u64) k[1].key;
-
-      hash_mix64 (x0, y0, z0);
-      hash_mix64 (x1, y1, z1);
-
-      k[0].b = z0 & b_mask;
-      k[1].b = z1 & b_mask;
-      k[0].a = z0 >> a_shift;
-      k[1].a = z1 >> a_shift;
-      if (PREDICT_FALSE (a_shift >= BITS (z0)))
-	k[0].a = k[1].a = 0;
-
-      k += 2;
-      n_keys_left -= 2;
-    }
-
-  if (n_keys_left >= 1)
-    {
-      u64 x0, y0, z0;
-
-      x0 = y0 = z0 = seed;
-      x0 += k[0].key;
-
-      hash_mix64 (x0, y0, z0);
-
-      k[0].b = z0 & b_mask;
-      k[0].a = z0 >> a_shift;
-      if (PREDICT_FALSE (a_shift >= BITS (z0)))
-	k[0].a = 0;
-
-      k += 1;
-      n_keys_left -= 1;
-    }
-}
-
-static void
-init_keys_indirect_u32 (phash_main_t * pm)
-{
-  int n_keys_left, b_mask, a_shift;
-  u32 seed;
-  phash_key_t *k;
-
-  seed = pm->hash_seed;
-  b_mask = (1 << pm->b_bits) - 1;
-  a_shift = BITS (seed) - pm->a_bits;
-
-  k = pm->keys;
-  n_keys_left = vec_len (pm->keys);
-
-  while (n_keys_left >= 2)
-    {
-      u32 xyz[6];
-      u32 x0, y0, z0;
-      u32 x1, y1, z1;
-
-      pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz);
-
-      x0 = y0 = z0 = seed;
-      x1 = y1 = z1 = seed;
-      x0 += xyz[0];
-      y0 += xyz[1];
-      z0 += xyz[2];
-      x1 += xyz[3];
-      y1 += xyz[4];
-      z1 += xyz[5];
-
-      hash_mix32 (x0, y0, z0);
-      hash_mix32 (x1, y1, z1);
-
-      k[0].b = z0 & b_mask;
-      k[1].b = z1 & b_mask;
-      k[0].a = z0 >> a_shift;
-      k[1].a = z1 >> a_shift;
-      if (PREDICT_FALSE (a_shift >= BITS (z0)))
-	k[0].a = k[1].a = 0;
-
-      k += 2;
-      n_keys_left -= 2;
-    }
-
-  if (n_keys_left >= 1)
-    {
-      u32 xyz[3];
-      u32 x0, y0, z0;
-
-      pm->key_seed1 (pm->private, k[0].key, &xyz);
-
-      x0 = y0 = z0 = seed;
-      x0 += xyz[0];
-      y0 += xyz[1];
-      z0 += xyz[2];
-
-      hash_mix32 (x0, y0, z0);
-
-      k[0].b = z0 & b_mask;
-      k[0].a = z0 >> a_shift;
-      if (PREDICT_FALSE (a_shift >= BITS (z0)))
-	k[0].a = 0;
-
-      k += 1;
-      n_keys_left -= 1;
-    }
-}
-
-static void
-init_keys_indirect_u64 (phash_main_t * pm)
-{
-  int n_keys_left, b_mask, a_shift;
-  u64 seed;
-  phash_key_t *k;
-
-  seed = pm->hash_seed;
-  b_mask = (1 << pm->b_bits) - 1;
-  a_shift = BITS (seed) - pm->a_bits;
-
-  k = pm->keys;
-  n_keys_left = vec_len (pm->keys);
-
-  while (n_keys_left >= 2)
-    {
-      u64 xyz[6];
-      u64 x0, y0, z0;
-      u64 x1, y1, z1;
-
-      pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz);
-
-      x0 = y0 = z0 = seed;
-      x1 = y1 = z1 = seed;
-      x0 += xyz[0];
-      y0 += xyz[1];
-      z0 += xyz[2];
-      x1 += xyz[3];
-      y1 += xyz[4];
-      z1 += xyz[5];
-
-      hash_mix64 (x0, y0, z0);
-      hash_mix64 (x1, y1, z1);
-
-      k[0].b = z0 & b_mask;
-      k[1].b = z1 & b_mask;
-      k[0].a = z0 >> a_shift;
-      k[1].a = z1 >> a_shift;
-      if (PREDICT_FALSE (a_shift >= BITS (z0)))
-	k[0].a = k[1].a = 0;
-
-      k += 2;
-      n_keys_left -= 2;
-    }
-
-  if (n_keys_left >= 1)
-    {
-      u64 xyz[3];
-      u64 x0, y0, z0;
-
-      pm->key_seed1 (pm->private, k[0].key, &xyz);
-
-      x0 = y0 = z0 = seed;
-      x0 += xyz[0];
-      y0 += xyz[1];
-      z0 += xyz[2];
-
-      hash_mix64 (x0, y0, z0);
-
-      k[0].b = z0 & b_mask;
-      k[0].a = z0 >> a_shift;
-      if (PREDICT_FALSE (a_shift >= BITS (z0)))
-	k[0].a = 0;
-
-      k += 1;
-      n_keys_left -= 1;
-    }
-}
-
-/*
- * insert keys into table according to key->b
- * check if the initial hash might work
- */
-static int
-init_tabb (phash_main_t * pm)
-{
-  int no_collisions;
-  phash_tabb_t *tb;
-  phash_key_t *k, *l;
-
-  if (pm->key_seed1)
-    {
-      if (pm->flags & PHASH_FLAG_MIX64)
-	init_keys_indirect_u64 (pm);
-      else
-	init_keys_indirect_u32 (pm);
-    }
-  else
-    {
-      if (pm->flags & PHASH_FLAG_MIX64)
-	init_keys_direct_u64 (pm);
-      else
-	init_keys_direct_u32 (pm);
-    }
-
-  if (!pm->tabb)
-    vec_resize (pm->tabb, 1 << pm->b_bits);
-  else
-    vec_foreach (tb, pm->tabb) phash_tabb_free (tb);
-
-  /* Two keys with the same (a,b) guarantees a collision */
-  no_collisions = 1;
-  vec_foreach (k, pm->keys)
-  {
-    u32 i, *ki;
-
-    tb = pm->tabb + k->b;
-    ki = tb->keys;
-    for (i = 0; i < vec_len (ki); i++)
-      {
-	l = pm->keys + ki[i];
-	if (k->a == l->a)
-	  {
-	    /* Given keys are supposed to be unique. */
-	    if (pm->key_is_equal
-		&& pm->key_is_equal (pm->private, l->key, k->key))
-	      clib_error ("duplicate keys");
-	    no_collisions = 0;
-	    goto done;
-	  }
-      }
-
-    vec_add1 (tb->keys, k - pm->keys);
-  }
-
-done:
-  return no_collisions;
-}
-
-/* Try to apply an augmenting list */
-static int
-apply (phash_main_t * pm, u32 tail, u32 rollback)
-{
-  phash_key_t *k;
-  phash_tabb_t *pb;
-  phash_tabq_t *q_child, *q_parent;
-  u32 ki, i, hash, child, parent;
-  u32 stabb;			/* scramble[tab[b]] */
-  int no_collision;
-
-  no_collision = 1;
-
-  /* Walk from child to parent until root is reached. */
-  for (child = tail - 1; child; child = parent)
-    {
-      q_child = &pm->tabq[child];
-      parent = q_child->parent_q;
-      q_parent = &pm->tabq[parent];
-
-      /* find parent's list of siblings */
-      ASSERT (q_parent->b_q < vec_len (pm->tabb));
-      pb = pm->tabb + q_parent->b_q;
-
-      /* erase old hash values */
-      stabb = pm->scramble[pb->val_b];
-      for (i = 0; i < vec_len (pb->keys); i++)
-	{
-	  ki = pb->keys[i];
-	  k = pm->keys + ki;
-	  hash = k->a ^ stabb;
-
-	  /* Erase hash for all of child's siblings. */
-	  if (ki == pm->tabh[hash])
-	    pm->tabh[hash] = ~0;
-	}
-
-      /* change pb->val_b, which will change the hashes of all parent siblings */
-      pb->val_b = rollback ? q_child->oldval_q : q_child->newval_q;
-
-      /* set new hash values */
-      stabb = pm->scramble[pb->val_b];
-      for (i = 0; i < vec_len (pb->keys); i++)
-	{
-	  ki = pb->keys[i];
-	  k = pm->keys + ki;
-
-	  hash = k->a ^ stabb;
-	  if (rollback)
-	    {
-	      if (parent == 0)
-		continue;	/* root never had a hash */
-	    }
-	  else if (pm->tabh[hash] != ~0)
-	    {
-	      /* Very rare case: roll back any changes. */
-	      apply (pm, tail, /* rollback changes */ 1);
-	      no_collision = 0;
-	      goto done;
-	    }
-	  pm->tabh[hash] = ki;
-	}
-    }
-
-done:
-  return no_collision;
-}
-
-
-/*
--------------------------------------------------------------------------------
-augment(): Add item to the mapping.
-
-Construct a spanning tree of *b*s with *item* as root, where each
-parent can have all its hashes changed (by some new val_b) with
-at most one collision, and each child is the b of that collision.
-
-I got this from Tarjan's "Data Structures and Network Algorithms".  The
-path from *item* to a *b* that can be remapped with no collision is
-an "augmenting path".  Change values of tab[b] along the path so that
-the unmapped key gets mapped and the unused hash value gets used.
-
-Assuming 1 key per b, if m out of n hash values are still unused,
-you should expect the transitive closure to cover n/m nodes before
-an unused node is found.  Sum(i=1..n)(n/i) is about nlogn, so expect
-this approach to take about nlogn time to map all single-key b's.
--------------------------------------------------------------------------------
-
-high_water: a value higher than any now in tabb[].water_b.
-*/
-static int
-augment (phash_main_t * pm, u32 b_root, u32 high_water)
-{
-  u32 q;			/* current position walking through the queue */
-  u32 tail;			/* tail of the queue.  0 is the head of the queue. */
-  phash_tabb_t *tb_parent, *tb_child, *tb_hit;
-  phash_key_t *k_parent, *k_child;
-  u32 v, v_limit;		/* possible value for myb->val_b */
-  u32 i, ki, hash;
-
-  v_limit =
-    1 << ((pm->flags & PHASH_FLAG_USE_SCRAMBLE) ? pm->s_bits : BITS (u8));
-
-  /* Initialize the root of the spanning tree. */
-  pm->tabq[0].b_q = b_root;
-  tail = 1;
-
-  /* construct the spanning tree by walking the queue, add children to tail */
-  for (q = 0; q < tail; q++)
-    {
-      if ((pm->flags & PHASH_FLAG_FAST_MODE)
-	  && !(pm->flags & PHASH_FLAG_MINIMAL) && q == 1)
-	break;			/* don't do transitive closure */
-
-      tb_parent = pm->tabb + pm->tabq[q].b_q;	/* the b for this node */
-
-      for (v = 0; v < v_limit; v++)
-	{
-	  tb_child = 0;
-
-	  for (i = 0; i < vec_len (tb_parent->keys); i++)
-	    {
-	      ki = tb_parent->keys[i];
-	      k_parent = pm->keys + ki;
-
-	      hash = k_parent->a ^ pm->scramble[v];
-	      if (hash >= pm->hash_max)
-		goto try_next_v;	/* hash code out of bounds => we can't use this v */
-
-	      ki = pm->tabh[hash];
-	      if (ki == ~0)
-		continue;
-
-	      k_child = pm->keys + ki;
-	      tb_hit = pm->tabb + k_child->b;
-
-	      if (tb_child)
-		{
-		  /* Hit at most one child b. */
-		  if (tb_child == tb_hit)
-		    goto try_next_v;
-		}
-	      else
-		{
-		  /* Remember this as child b. */
-		  tb_child = tb_hit;
-		  if (tb_hit->water_b == high_water)
-		    goto try_next_v;	/* already explored */
-		}
-	    }
-
-	  /* tb_parent with v has either one or zero collisions. */
-
-	  /* add child b to the queue of reachable things */
-	  if (tb_child)
-	    tb_child->water_b = high_water;
-	  pm->tabq[tail].b_q = tb_child ? tb_child - pm->tabb : ~0;
-	  pm->tabq[tail].newval_q = v;	/* how to make parent (myb) use this hash */
-	  pm->tabq[tail].oldval_q = tb_parent->val_b;	/* need this for rollback */
-	  pm->tabq[tail].parent_q = q;
-	  ++tail;
-
-	  /* Found a v with no collisions? */
-	  if (!tb_child)
-	    {
-	      /* Try to apply the augmenting path. */
-	      if (apply (pm, tail, /* rollback */ 0))
-		return 1;	/* success, item was added to the perfect hash */
-	      --tail;		/* don't know how to handle such a child! */
-	    }
-
-	try_next_v:
-	  ;
-	}
-    }
-  return 0;
-}
-
-
-static phash_tabb_t *sort_tabb;
-
-static int
-phash_tabb_compare (void *a1, void *a2)
-{
-  u32 *b1 = a1;
-  u32 *b2 = a2;
-  phash_tabb_t *tb1, *tb2;
-
-  tb1 = sort_tabb + b1[0];
-  tb2 = sort_tabb + b2[0];
-
-  return ((int) vec_len (tb2->keys) - (int) vec_len (tb1->keys));
-}
-
-/* find a mapping that makes this a perfect hash */
-static int
-perfect (phash_main_t * pm)
-{
-  u32 i;
-
-  /* clear any state from previous attempts */
-  if (vec_bytes (pm->tabh))
-    clib_memset (pm->tabh, ~0, vec_bytes (pm->tabh));
-
-  vec_validate (pm->tabb_sort, vec_len (pm->tabb) - 1);
-  for (i = 0; i < vec_len (pm->tabb_sort); i++)
-    pm->tabb_sort[i] = i;
-
-  sort_tabb = pm->tabb;
-
-  vec_sort_with_function (pm->tabb_sort, phash_tabb_compare);
-
-  /* In descending order by number of keys, map all *b*s */
-  for (i = 0; i < vec_len (pm->tabb_sort); i++)
-    {
-      if (!augment (pm, pm->tabb_sort[i], i + 1))
-	return 0;
-    }
-
-  /* Success!  We found a perfect hash of all keys into 0..nkeys-1. */
-  return 1;
-}
-
-
-/*
- * Find initial a_bits = log2 (a_max), b_bits = log2 (b_max).
- * Initial a_max and b_max values were found empirically.  Some factors:
- *
- * If s_max<256 there is no scramble, so tab[b] needs to cover 0..s_max-1.
- *
- * a_max and b_max must be powers of 2 because the values in 0..a_max-1 and
- * 0..b_max-1 are produced by applying a bitmask to the initial hash function.
- *
- * a_max must be less than s_max, in fact less than n_keys, because otherwise
- * there would often be no i such that a^scramble[i] is in 0..n_keys-1 for
- * all the *a*s associated with a given *b*, so there would be no legal
- * value to assign to tab[b].  This only matters when we're doing a minimal
- * perfect hash.
- *
- * It takes around 800 trials to find distinct (a,b) with nkey=s_max*(5/8)
- * and a_max*b_max = s_max*s_max/32.
- *
- * Values of b_max less than s_max/4 never work, and s_max/2 always works.
- *
- * We want b_max as small as possible because it is the number of bytes in
- * the huge array we must create for the perfect hash.
- *
- * When nkey <= s_max*(5/8), b_max=s_max/4 works much more often with
- * a_max=s_max/8 than with a_max=s_max/4.  Above s_max*(5/8), b_max=s_max/4
- * doesn't seem to care whether a_max=s_max/8 or a_max=s_max/4.  I think it
- * has something to do with 5/8 = 1/8 * 5.  For example examine 80000,
- * 85000, and 90000 keys with different values of a_max.  This only matters
- * if we're doing a minimal perfect hash.
- *
- * When a_max*b_max <= 1<<U32BITS, the initial hash must produce one integer.
- * Bigger than that it must produce two integers, which increases the
- * cost of the hash per character hashed.
- */
-static void
-guess_initial_parameters (phash_main_t * pm)
-{
-  u32 s_bits, s_max, a_max, b_max, n_keys;
-  int is_minimal, is_fast_mode;
-  const u32 b_max_use_scramble_threshold = 4096;
-
-  is_minimal = (pm->flags & PHASH_FLAG_MINIMAL) != 0;
-  is_fast_mode = (pm->flags & PHASH_FLAG_FAST_MODE) != 0;
-
-  n_keys = vec_len (pm->keys);
-  s_bits = max_log2 (n_keys);
-  s_max = 1 << s_bits;
-  a_max = 0;
-
-  if (is_minimal)
-    {
-      switch (s_bits)
-	{
-	case 0:
-	  a_max = 1;
-	  b_max = 1;
-	case 1:
-	case 2:
-	case 3:
-	case 4:
-	case 5:
-	case 6:
-	case 7:
-	case 8:
-	  /*
-	   * Was: a_max = is_minimal ? s_max / 2 : s_max;
-	   * However, we know that is_minimal must be true, so the
-	   * if-arm of the ternary expression is always executed.
-	   */
-	  a_max = s_max / 2;
-	  b_max = s_max / 2;
-	  break;
-	case 9:
-	case 10:
-	case 11:
-	case 12:
-	case 13:
-	case 14:
-	case 15:
-	case 16:
-	case 17:
-	  if (is_fast_mode)
-	    {
-	      a_max = s_max / 2;
-	      b_max = s_max / 4;
-	    }
-	  else if (s_max / 4 < b_max_use_scramble_threshold)
-	    {
-	      if (n_keys <= s_max * 0.52)
-		a_max = b_max = s_max / 8;
-	      else
-		a_max = b_max = s_max / 4;
-	    }
-	  else
-	    {
-	      a_max = ((n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 :
-		       (n_keys <=
-			s_max * (3.0 / 4.0)) ? s_max / 4 : s_max / 2);
-	      b_max = s_max / 4;	/* always give the small size a shot */
-	    }
-	  break;
-	case 18:
-	  if (is_fast_mode)
-	    a_max = b_max = s_max / 2;
-	  else
-	    {
-	      a_max = s_max / 8;	/* never require the multiword hash */
-	      b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2;
-	    }
-	  break;
-	case 19:
-	case 20:
-	  a_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 : s_max / 2;
-	  b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2;
-	  break;
-	default:
-	  /* Just find a hash as quick as possible.
-	     We'll be thrashing virtual memory at this size. */
-	  a_max = b_max = s_max / 2;
-	  break;
-	}
-    }
-  else
-    {
-      /* Non-minimal perfect hash. */
-      if (is_fast_mode && n_keys > s_max * 0.8)
-	{
-	  s_max *= 2;
-	  s_bits += 1;
-	}
-
-      if (s_max / 4 <= (1 << 14))
-	b_max = ((n_keys <= s_max * 0.56) ? s_max / 32 :
-		 (n_keys <= s_max * 0.74) ? s_max / 16 : s_max / 8);
-      else
-	b_max = ((n_keys <= s_max * 0.6) ? s_max / 16 :
-		 (n_keys <= s_max * 0.8) ? s_max / 8 : s_max / 4);
-
-      if (is_fast_mode && b_max < s_max / 8)
-	b_max = s_max / 8;
-
-      if (a_max < 1)
-	a_max = 1;
-      if (b_max < 1)
-	b_max = 1;
-    }
-
-  ASSERT (s_max == (1 << s_bits));
-  ASSERT (is_pow2 (a_max));
-  ASSERT (is_pow2 (b_max));
-  pm->s_bits = s_bits;
-  pm->a_bits = min_log2 (a_max);
-  pm->b_bits = min_log2 (b_max);
-  if (b_max >= b_max_use_scramble_threshold)
-    pm->flags |= PHASH_FLAG_USE_SCRAMBLE;
-}
-
-/* compute p(x), where p is a permutation of 0..(1<<nbits)-1 */
-/* permute(0)=0.  This is intended and useful. */
-always_inline u32
-scramble_permute (u32 x, u32 nbits)
-{
-  int i;
-  int mask = (1 << nbits) - 1;
-  int const2 = 1 + nbits / 2;
-  int const3 = 1 + nbits / 3;
-  int const4 = 1 + nbits / 4;
-  int const5 = 1 + nbits / 5;
-  for (i = 0; i < 20; i++)
-    {
-      x = (x + (x << const2)) & mask;
-      x = (x ^ (x >> const3));
-      x = (x + (x << const4)) & mask;
-      x = (x ^ (x >> const5));
-    }
-  return x;
-}
-
-/* initialize scramble[] with distinct random values in 0..smax-1 */
-static void
-scramble_init (phash_main_t * pm)
-{
-  u32 i;
-
-  /* fill scramble[] with distinct random integers in 0..smax-1 */
-  vec_validate (pm->scramble, (1 << (pm->s_bits < 8 ? 8 : pm->s_bits)) - 1);
-  for (i = 0; i < vec_len (pm->scramble); i++)
-    pm->scramble[i] = scramble_permute (i, pm->s_bits);
-}
-
-/* Try to find a perfect hash function. */
-clib_error_t *
-phash_find_perfect_hash (phash_main_t * pm)
-{
-  clib_error_t *error = 0;
-  u32 max_a_bits, n_tries_this_a_b, want_minimal;
-
-  /* guess initial values for s_max, a_max and b_max */
-  guess_initial_parameters (pm);
-
-  want_minimal = pm->flags & PHASH_FLAG_MINIMAL;
-
-new_s:
-  if (pm->b_bits == 0)
-    pm->a_bits = pm->s_bits;
-
-  max_a_bits = pm->s_bits - want_minimal;
-  if (max_a_bits < 1)
-    max_a_bits = 1;
-
-  pm->hash_max = want_minimal ? vec_len (pm->keys) : (1 << pm->s_bits);
-
-  scramble_init (pm);
-
-  /* Allocate working memory. */
-  vec_free (pm->tabh);
-  vec_validate_init_empty (pm->tabh, pm->hash_max - 1, ~0);
-  vec_free (pm->tabq);
-  vec_validate (pm->tabq, 1 << pm->b_bits);
-
-  /* Actually find the perfect hash */
-  n_tries_this_a_b = 0;
-  while (1)
-    {
-      /* Choose random hash seeds until keys become unique. */
-      pm->hash_seed = random_u64 (&pm->random_seed);
-      pm->n_seed_trials++;
-      if (init_tabb (pm))
-	{
-	  /* Found unique (A, B). */
-
-	  /* Hash may already be perfect. */
-	  if (pm->b_bits == 0)
-	    goto done;
-
-	  pm->n_perfect_calls++;
-	  if (perfect (pm))
-	    goto done;
-
-	  goto increase_b;
-	}
-
-      /* Keep trying with different seed value. */
-      n_tries_this_a_b++;
-      if (n_tries_this_a_b < 2048)
-	continue;
-
-      /* Try to put more bits in (A,B) to make distinct (A,B) more likely */
-      if (pm->a_bits < max_a_bits)
-	pm->a_bits++;
-      else if (pm->b_bits < pm->s_bits)
-	{
-	increase_b:
-	  vec_resize (pm->tabb, vec_len (pm->tabb));
-	  vec_resize (pm->tabq, vec_len (pm->tabq));
-	  pm->b_bits++;
-	}
-      else
-	{
-	  /* Can't increase (A, B) any more, so try increasing S. */
-	  goto new_s;
-	}
-    }
-
-done:
-  /* Construct mapping table for hash lookups. */
-  if (!error)
-    {
-      u32 b, v;
-
-      pm->a_shift = ((pm->flags & PHASH_FLAG_MIX64) ? 64 : 32) - pm->a_bits;
-      pm->b_mask = (1 << pm->b_bits) - 1;
-
-      vec_resize (pm->tab, vec_len (pm->tabb));
-      for (b = 0; b < vec_len (pm->tabb); b++)
-	{
-	  v = pm->tabb[b].val_b;
-
-	  /* Apply scramble now for small enough value of b_bits. */
-	  if (!(pm->flags & PHASH_FLAG_USE_SCRAMBLE))
-	    v = pm->scramble[v];
-
-	  pm->tab[b] = v;
-	}
-    }
-
-  /* Free working memory. */
-  phash_main_free_working_memory (pm);
-
-  return error;
-}
-
-/* Slow hash computation for general keys. */
-uword
-phash_hash_slow (phash_main_t * pm, uword key)
-{
-  u32 a, b, v;
-
-  if (pm->flags & PHASH_FLAG_MIX64)
-    {
-      u64 x0, y0, z0;
-
-      x0 = y0 = z0 = pm->hash_seed;
-
-      if (pm->key_seed1)
-	{
-	  u64 xyz[3];
-	  pm->key_seed1 (pm->private, key, &xyz);
-	  x0 += xyz[0];
-	  y0 += xyz[1];
-	  z0 += xyz[2];
-	}
-      else
-	x0 += key;
-
-      hash_mix64 (x0, y0, z0);
-
-      a = z0 >> pm->a_shift;
-      b = z0 & pm->b_mask;
-    }
-  else
-    {
-      u32 x0, y0, z0;
-
-      x0 = y0 = z0 = pm->hash_seed;
-
-      if (pm->key_seed1)
-	{
-	  u32 xyz[3];
-	  pm->key_seed1 (pm->private, key, &xyz);
-	  x0 += xyz[0];
-	  y0 += xyz[1];
-	  z0 += xyz[2];
-	}
-      else
-	x0 += key;
-
-      hash_mix32 (x0, y0, z0);
-
-      a = z0 >> pm->a_shift;
-      b = z0 & pm->b_mask;
-    }
-
-  v = pm->tab[b];
-  if (pm->flags & PHASH_FLAG_USE_SCRAMBLE)
-    v = pm->scramble[v];
-  return a ^ v;
-}
-
-/* Verify that perfect hash is perfect. */
-clib_error_t *
-phash_validate (phash_main_t * pm)
-{
-  phash_key_t *k;
-  uword *unique_bitmap = 0;
-  clib_error_t *error = 0;
-
-  vec_foreach (k, pm->keys)
-  {
-    uword h = phash_hash_slow (pm, k->key);
-
-    if (h >= pm->hash_max)
-      {
-	error = clib_error_return (0, "hash out of range %wd", h);
-	goto done;
-      }
-
-    if (clib_bitmap_get (unique_bitmap, h))
-      {
-	error = clib_error_return (0, "hash non-unique");
-	goto done;
-      }
-
-    unique_bitmap = clib_bitmap_ori (unique_bitmap, h);
-  }
-
-done:
-  clib_bitmap_free (unique_bitmap);
-  return error;
-}
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */