Reorganize source tree to use single autotools instance

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

1 files changed, 408 insertions, 0 deletions

diff --git a/src/vppinfra/mhash.c b/src/vppinfra/mhash.c
new file mode 100644
index 00000000000..c917e164cd9
--- /dev/null
+++ b/src/vppinfra/mhash.c
@@ -0,0 +1,408 @@
+/*
+ * 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) 2010 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.
+*/
+
+#include <vppinfra/mhash.h>
+
+always_inline u32
+load_partial_u32 (void *d, uword n)
+{
+  if (n == 4)
+    return ((u32 *) d)[0];
+  if (n == 3)
+    return ((u16 *) d)[0] | (((u8 *) d)[2] << 16);
+  if (n == 2)
+    return ((u16 *) d)[0];
+  if (n == 1)
+    return ((u8 *) d)[0];
+  ASSERT (0);
+  return 0;
+}
+
+always_inline u32
+mhash_key_sum_inline (void *data, uword n_data_bytes, u32 seed)
+{
+  u32 *d32 = data;
+  u32 a, b, c, n_left;
+
+  a = b = c = seed;
+  n_left = n_data_bytes;
+  a ^= n_data_bytes;
+
+  while (n_left > 12)
+    {
+      a += d32[0];
+      b += d32[1];
+      c += d32[2];
+      hash_v3_mix32 (a, b, c);
+      n_left -= 12;
+      d32 += 3;
+    }
+
+  if (n_left > 8)
+    {
+      c += load_partial_u32 (d32 + 2, n_left - 8);
+      n_left = 8;
+    }
+  if (n_left > 4)
+    {
+      b += load_partial_u32 (d32 + 1, n_left - 4);
+      n_left = 4;
+    }
+  if (n_left > 0)
+    a += load_partial_u32 (d32 + 0, n_left - 0);
+
+  hash_v3_finalize32 (a, b, c);
+
+  return c;
+}
+
+#define foreach_mhash_key_size			\
+  _ (2) _ (3) _ (4) _ (5) _ (6) _ (7)		\
+  _ (8) _ (12) _ (16) _ (20)			\
+  _ (24) _ (28) _ (32) _ (36)			\
+  _ (40) _ (44) _ (48) _ (52)			\
+  _ (56) _ (60) _ (64)
+
+#define _(N_KEY_BYTES)							\
+  static uword								\
+  mhash_key_sum_##N_KEY_BYTES (hash_t * h, uword key)			\
+  {									\
+    mhash_t * hv = uword_to_pointer (h->user, mhash_t *);		\
+    return mhash_key_sum_inline (mhash_key_to_mem (hv, key),		\
+				 (N_KEY_BYTES),				\
+				 hv->hash_seed);			\
+  }									\
+									\
+  static uword								\
+  mhash_key_equal_##N_KEY_BYTES (hash_t * h, uword key1, uword key2)	\
+  {									\
+    mhash_t * hv = uword_to_pointer (h->user, mhash_t *);		\
+    void * k1 = mhash_key_to_mem (hv, key1);				\
+    void * k2 = mhash_key_to_mem (hv, key2);				\
+    return ! memcmp (k1, k2, (N_KEY_BYTES));				\
+  }
+
+foreach_mhash_key_size
+#undef _
+static uword
+mhash_key_sum_c_string (hash_t * h, uword key)
+{
+  mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
+  void *k = mhash_key_to_mem (hv, key);
+  return mhash_key_sum_inline (k, strlen (k), hv->hash_seed);
+}
+
+static uword
+mhash_key_equal_c_string (hash_t * h, uword key1, uword key2)
+{
+  mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
+  void *k1 = mhash_key_to_mem (hv, key1);
+  void *k2 = mhash_key_to_mem (hv, key2);
+  return strcmp (k1, k2) == 0;
+}
+
+static uword
+mhash_key_sum_vec_string (hash_t * h, uword key)
+{
+  mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
+  void *k = mhash_key_to_mem (hv, key);
+  return mhash_key_sum_inline (k, vec_len (k), hv->hash_seed);
+}
+
+static uword
+mhash_key_equal_vec_string (hash_t * h, uword key1, uword key2)
+{
+  mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
+  void *k1 = mhash_key_to_mem (hv, key1);
+  void *k2 = mhash_key_to_mem (hv, key2);
+  return vec_len (k1) == vec_len (k2) && memcmp (k1, k2, vec_len (k1)) == 0;
+}
+
+/* The CLIB hash user pointer must always point to a valid mhash_t.
+   Now, the address of mhash_t can change (think vec_resize).
+   So we must always be careful that it points to the correct
+   address. */
+always_inline void
+mhash_sanitize_hash_user (mhash_t * mh)
+{
+  uword *hash = mh->hash;
+  hash_t *h = hash_header (hash);
+  h->user = pointer_to_uword (mh);
+}
+
+void
+mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes)
+{
+  static struct
+  {
+    hash_key_sum_function_t *key_sum;
+    hash_key_equal_function_t *key_equal;
+  } t[] =
+  {
+#define _(N_KEY_BYTES)					\
+    [N_KEY_BYTES] = {					\
+      .key_sum = mhash_key_sum_##N_KEY_BYTES,		\
+      .key_equal = mhash_key_equal_##N_KEY_BYTES,	\
+    },
+
+    foreach_mhash_key_size
+#undef _
+      [MHASH_C_STRING_KEY] =
+    {
+    .key_sum = mhash_key_sum_c_string,.key_equal = mhash_key_equal_c_string,},
+      [MHASH_VEC_STRING_KEY] =
+    {
+  .key_sum = mhash_key_sum_vec_string,.key_equal =
+	mhash_key_equal_vec_string,},};
+
+  if (mhash_key_vector_is_heap (h))
+    heap_free (h->key_vector_or_heap);
+  else
+    vec_free (h->key_vector_or_heap);
+  vec_free (h->key_vector_free_indices);
+  {
+    int i;
+    for (i = 0; i < vec_len (h->key_tmps); i++)
+      vec_free (h->key_tmps[i]);
+  }
+  vec_free (h->key_tmps);
+  hash_free (h->hash);
+
+  memset (h, 0, sizeof (h[0]));
+  h->n_key_bytes = n_key_bytes;
+
+#if 0
+  if (h->n_key_bytes > 0)
+    {
+      vec_validate (h->key_tmp, h->n_key_bytes - 1);
+      _vec_len (h->key_tmp) = 0;
+    }
+#endif
+
+  ASSERT (n_key_bytes < ARRAY_LEN (t));
+  h->hash = hash_create2 ( /* elts */ 0,
+			  /* user */ pointer_to_uword (h),
+			  /* value_bytes */ n_value_bytes,
+			  t[n_key_bytes].key_sum, t[n_key_bytes].key_equal,
+			  /* format pair/arg */
+			  0, 0);
+}
+
+static uword
+mhash_set_tmp_key (mhash_t * h, const void *key)
+{
+  u8 *key_tmp;
+  int my_cpu = os_get_cpu_number ();
+
+  vec_validate (h->key_tmps, my_cpu);
+  key_tmp = h->key_tmps[my_cpu];
+
+  vec_reset_length (key_tmp);
+
+  if (mhash_key_vector_is_heap (h))
+    {
+      uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
+
+      if (is_c_string)
+	vec_add (key_tmp, key, strlen (key) + 1);
+      else
+	vec_add (key_tmp, key, vec_len (key));
+    }
+  else
+    vec_add (key_tmp, key, h->n_key_bytes);
+
+  h->key_tmps[my_cpu] = key_tmp;
+
+  return ~0;
+}
+
+hash_pair_t *
+mhash_get_pair (mhash_t * h, const void *key)
+{
+  uword ikey;
+  mhash_sanitize_hash_user (h);
+  ikey = mhash_set_tmp_key (h, key);
+  return hash_get_pair (h->hash, ikey);
+}
+
+typedef struct
+{
+  u32 heap_handle;
+
+  /* Must conincide with vec_header. */
+  vec_header_t vec;
+} mhash_string_key_t;
+
+uword
+mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value)
+{
+  u8 *k;
+  uword ikey, i, l = 0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
+
+  mhash_sanitize_hash_user (h);
+
+  if (mhash_key_vector_is_heap (h))
+    {
+      mhash_string_key_t *sk;
+      uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
+      uword handle;
+
+      n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
+      i =
+	heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]),
+		    handle);
+
+      sk = (void *) (h->key_vector_or_heap + i);
+      sk->heap_handle = handle;
+      sk->vec.len = n_key_bytes;
+      clib_memcpy (sk->vec.vector_data, key, n_key_bytes);
+
+      /* Advance key past vector header. */
+      i += sizeof (sk[0]);
+    }
+  else
+    {
+      key_alloc_from_free_list = (l =
+				  vec_len (h->key_vector_free_indices)) > 0;
+      if (key_alloc_from_free_list)
+	{
+	  i = h->key_vector_free_indices[l - 1];
+	  k = vec_elt_at_index (h->key_vector_or_heap, i);
+	  _vec_len (h->key_vector_free_indices) = l - 1;
+	}
+      else
+	{
+	  vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
+	  i = k - h->key_vector_or_heap;
+	}
+
+      n_key_bytes = h->n_key_bytes;
+      clib_memcpy (k, key, n_key_bytes);
+    }
+  ikey = i;
+
+  old_n_elts = hash_elts (h->hash);
+  h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
+
+  /* If element already existed remove duplicate key. */
+  if (hash_elts (h->hash) == old_n_elts)
+    {
+      hash_pair_t *p;
+
+      /* Fetch old key for return value. */
+      p = hash_get_pair (h->hash, ikey);
+      ikey = p->key;
+
+      /* Remove duplicate key. */
+      if (mhash_key_vector_is_heap (h))
+	{
+	  mhash_string_key_t *sk;
+	  sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
+	  heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
+	}
+      else
+	{
+	  if (key_alloc_from_free_list)
+	    {
+	      h->key_vector_free_indices[l] = i;
+	      _vec_len (h->key_vector_free_indices) = l + 1;
+	    }
+	  else
+	    _vec_len (h->key_vector_or_heap) -= h->n_key_bytes;
+	}
+    }
+
+  return ikey;
+}
+
+uword
+mhash_unset (mhash_t * h, void *key, uword * old_value)
+{
+  hash_pair_t *p;
+  uword i;
+
+  mhash_sanitize_hash_user (h);
+  i = mhash_set_tmp_key (h, key);
+
+  p = hash_get_pair (h->hash, i);
+  if (!p)
+    return 0;
+
+  ASSERT (p->key != ~0);
+  i = p->key;
+
+  if (mhash_key_vector_is_heap (h))
+    {
+      mhash_string_key_t *sk;
+      sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
+      heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
+    }
+  else
+    vec_add1 (h->key_vector_free_indices, i);
+
+  hash_unset3 (h->hash, i, old_value);
+  return 1;
+}
+
+u8 *
+format_mhash_key (u8 * s, va_list * va)
+{
+  mhash_t *h = va_arg (*va, mhash_t *);
+  u32 ki = va_arg (*va, u32);
+  void *k = mhash_key_to_mem (h, ki);
+
+  if (mhash_key_vector_is_heap (h))
+    {
+      uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
+      u32 l = is_c_string ? strlen (k) : vec_len (k);
+      vec_add (s, k, l);
+    }
+  else if (h->format_key)
+    s = format (s, "%U", h->format_key, k);
+  else
+    s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes);
+
+  return s;
+}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */