Reorganize source tree to use single autotools instance

Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23
Signed-off-by: Damjan Marion <damarion@cisco.com>

1 files changed, 194 insertions, 0 deletions

diff --git a/src/vppinfra/phash.h b/src/vppinfra/phash.h
new file mode 100644
index 00000000000..746a0fddfab
--- /dev/null
+++ b/src/vppinfra/phash.h
@@ -0,0 +1,194 @@
+/*
+ * 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.
+*/
+
+#ifndef included_phash_h
+#define included_phash_h
+
+#include <vppinfra/hash.h>	/* for Bob's mixing functions */
+
+typedef struct
+{
+  /* Maybe either pointer to vector or inline word. */
+  uword key;
+
+  /* Hash code (A, B). */
+  u32 a, b;
+} phash_key_t;
+
+/* Table indexed by B. */
+typedef struct
+{
+  /* Vector of key indices with this same value of B. */
+  u32 *keys;
+
+  /* hash=a^tabb[b].val_b */
+  u32 val_b;
+
+  /* High watermark of who has visited this map node. */
+  u32 water_b;
+} phash_tabb_t;
+
+always_inline void
+phash_tabb_free (phash_tabb_t * b)
+{
+  vec_free (b->keys);
+  b->val_b = b->water_b = 0;
+}
+
+typedef struct
+{
+  /* b that currently occupies this hash */
+  u32 b_q;
+
+  /* Queue position of parent that could use this hash. */
+  u32 parent_q;
+
+  /* What to change parent tab[b] to use this hash. */
+  u32 newval_q;
+
+  /* Original value of tab[b]. */
+  u32 oldval_q;
+} phash_tabq_t;
+
+typedef struct
+{
+  u8 a_bits, b_bits, s_bits, a_shift;
+  u32 b_mask;
+  u32 *tab;
+  u32 *scramble;
+
+  /* Seed value for hash mixer. */
+  u64 hash_seed;
+
+  u32 flags;
+
+  /* Key functions want 64 bit keys.
+     Use hash_mix64 rather than hash_mix32. */
+#define PHASH_FLAG_MIX64		(1 << 0)
+#define PHASH_FLAG_MIX32		(0 << 0)
+
+  /* When b_bits is large enough (>= 12) we scramble. */
+#define PHASH_FLAG_USE_SCRAMBLE		(1 << 1)
+
+  /* Slow mode gives smaller tables but at the expense of more run time. */
+#define PHASH_FLAG_SLOW_MODE		(0 << 2)
+#define PHASH_FLAG_FAST_MODE		(1 << 2)
+
+  /* Generate minimal perfect hash instead of perfect hash. */
+#define PHASH_FLAG_NON_MINIMAL		(0 << 3)
+#define PHASH_FLAG_MINIMAL		(1 << 3)
+
+  /* vec_len (keys) for minimal hash;
+     1 << s_bits for non-minimal hash. */
+  u32 hash_max;
+
+  /* Vector of keys. */
+  phash_key_t *keys;
+
+  /* Used by callbacks to identify keys. */
+  void *private;
+
+  /* Key comparison callback. */
+  int (*key_is_equal) (void *private, uword key1, uword key2);
+
+  /* Callback to reduce single key -> hash seeds. */
+  void (*key_seed1) (void *private, uword key, void *seed);
+
+  /* Callback to reduce two key2 -> hash seeds. */
+  void (*key_seed2) (void *private, uword key1, uword key2, void *seed);
+
+  /* Stuff used to compute perfect hash. */
+  u32 random_seed;
+
+  /* Stuff indexed by B. */
+  phash_tabb_t *tabb;
+
+  /* Table of B ordered by number of keys in tabb[b]. */
+  u32 *tabb_sort;
+
+  /* Unique key (or ~0 if none) for a given hash
+     H = A ^ scramble[tab[B].val_b]. */
+  u32 *tabh;
+
+  /* Stuff indexed by q. */
+  phash_tabq_t *tabq;
+
+  /* Stats. */
+  u32 n_seed_trials, n_perfect_calls;
+} phash_main_t;
+
+always_inline void
+phash_main_free_working_memory (phash_main_t * pm)
+{
+  vec_free (pm->tabb);
+  vec_free (pm->tabq);
+  vec_free (pm->tabh);
+  vec_free (pm->tabb_sort);
+  if (!(pm->flags & PHASH_FLAG_USE_SCRAMBLE))
+    vec_free (pm->scramble);
+}
+
+always_inline void
+phash_main_free (phash_main_t * pm)
+{
+  phash_main_free_working_memory (pm);
+  vec_free (pm->tab);
+  vec_free (pm->keys);
+  memset (pm, 0, sizeof (pm[0]));
+}
+
+/* Slow hash computation for general keys. */
+uword phash_hash_slow (phash_main_t * pm, uword key);
+
+/* Main routine to compute perfect hash. */
+clib_error_t *phash_find_perfect_hash (phash_main_t * pm);
+
+/* Validates that hash is indeed perfect. */
+clib_error_t *phash_validate (phash_main_t * pm);
+
+/* Unit test. */
+int phash_test_main (unformat_input_t * input);
+
+#endif /* included_phash_h */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */