Initial commit of vpp code.v1.0.0

Change-Id: Ib246f1fbfce93274020ee93ce461e3d8bd8b9f17
Signed-off-by: Ed Warnicke <eaw@cisco.com>

1 files changed, 235 insertions, 0 deletions

diff --git a/vppinfra/vppinfra/sparse_vec.h b/vppinfra/vppinfra/sparse_vec.h
new file mode 100644
index 00000000000..08e97f352a9
--- /dev/null
+++ b/vppinfra/vppinfra/sparse_vec.h
@@ -0,0 +1,235 @@
+/*
+ * 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_sparse_vec_h
+#define included_sparse_vec_h
+
+#include <vppinfra/vec.h>
+#include <vppinfra/bitops.h>
+
+/* Sparsely indexed vectors.  Basic idea taken from Hacker's delight.
+   Eliot added ranges. */
+typedef struct {
+  /* Bitmap one for each sparse index. */
+  uword * is_member_bitmap;
+
+  /* member_counts[i] = total number of members with j < i. */
+  u16 * member_counts;
+
+#define SPARSE_VEC_IS_RANGE (1 << 0)
+#define SPARSE_VEC_IS_VALID_RANGE (1 << 1)
+  u8 * range_flags;
+} sparse_vec_header_t;
+
+always_inline sparse_vec_header_t *
+sparse_vec_header (void * v)
+{ return vec_header (v, sizeof (sparse_vec_header_t)); }
+
+/* Index 0 is always used to mark indices that are not valid in
+   sparse vector.  For example, you look up V[0x1234] and 0x1234 is not
+   known you'll get 0 back as an index. */
+#define SPARSE_VEC_INVALID_INDEX (0)
+
+always_inline void *
+sparse_vec_new (uword elt_bytes, uword sparse_index_bits)
+{
+  void * v;
+  sparse_vec_header_t * h;
+  word n;
+
+  ASSERT (sparse_index_bits <= 16);
+
+  v = _vec_resize (0,
+		   /* length increment */ 8,
+		   /* data bytes */ 8*elt_bytes,
+		   /* header bytes */ sizeof (h[0]),
+		   /* data align */ 0);
+
+  /* Make space for invalid entry (entry 0). */
+  _vec_len (v) = 1;
+
+  h = sparse_vec_header (v);
+
+  n = sparse_index_bits - min_log2 (BITS (uword));
+  if (n < 0)
+    n = 0;
+  n = 1 << n;
+  vec_resize (h->is_member_bitmap, n);
+  vec_resize (h->member_counts, n);
+
+  return v;
+}
+
+always_inline uword
+sparse_vec_index_internal (void * v,
+			   uword sparse_index,
+			   uword maybe_range,
+			   u32 * insert)
+{
+  sparse_vec_header_t * h;
+  uword i, b, d, w;
+  u8 is_member;
+
+  h = sparse_vec_header (v);
+  i = sparse_index / BITS (h->is_member_bitmap[0]);
+  b = (uword) 1 << (uword) (sparse_index % BITS (h->is_member_bitmap[0]));
+
+  ASSERT (i < vec_len (h->is_member_bitmap));
+  ASSERT (i < vec_len (h->member_counts));
+
+  w = h->is_member_bitmap[i];
+  d = h->member_counts[i] + count_set_bits (w & (b - 1));
+
+  is_member = (w & b) != 0;
+  if (maybe_range)
+    {
+      u8 r = h->range_flags[d];
+      u8 is_range, is_valid_range;
+
+      is_range = maybe_range & (r & SPARSE_VEC_IS_RANGE);
+      is_valid_range = (r & SPARSE_VEC_IS_VALID_RANGE) != 0;
+
+      is_member = is_range ? is_valid_range : is_member;
+    }
+
+  if (insert)
+    {
+      *insert = ! is_member;
+      if (! is_member)
+	{
+	  uword j;
+	  w |= b;
+	  h->is_member_bitmap[i] = w;
+	  for (j = i + 1; j < vec_len (h->member_counts); j++)
+	    h->member_counts[j] += 1;
+	}
+
+      return 1 + d;
+    }
+
+  d = is_member ? d : 0;
+
+  return is_member + d;
+}
+
+always_inline uword
+sparse_vec_index (void * v, uword sparse_index)
+{
+  return sparse_vec_index_internal (v, sparse_index,
+				    /* maybe range */ 0,
+				    /* insert? */ 0);
+}
+				    
+always_inline void
+sparse_vec_index2 (void * v,
+		   u32 si0, u32 si1,
+		   u32 * i0_return, u32 * i1_return)
+{
+  sparse_vec_header_t * h;
+  uword b0, b1, w0, w1, v0, v1;
+  u32 i0, i1, d0, d1;
+  u8 is_member0, is_member1;
+
+  h = sparse_vec_header (v);
+
+  i0 = si0 / BITS (h->is_member_bitmap[0]);
+  i1 = si1 / BITS (h->is_member_bitmap[0]);
+
+  b0 = (uword) 1 << (uword) (si0 % BITS (h->is_member_bitmap[0]));
+  b1 = (uword) 1 << (uword) (si1 % BITS (h->is_member_bitmap[0]));
+
+  ASSERT (i0 < vec_len (h->is_member_bitmap));
+  ASSERT (i1 < vec_len (h->is_member_bitmap));
+
+  ASSERT (i0 < vec_len (h->member_counts));
+  ASSERT (i1 < vec_len (h->member_counts));
+
+  w0 = h->is_member_bitmap[i0];
+  w1 = h->is_member_bitmap[i1];
+
+  v0 = w0 & (b0 - 1);
+  v1 = w1 & (b1 - 1);
+
+  /* Speculate that masks will have zero or one bits set. */
+  d0 = h->member_counts[i0] + (v0 != 0);
+  d1 = h->member_counts[i1] + (v1 != 0);
+
+  /* Validate speculation. */
+  if (PREDICT_FALSE (! is_pow2 (v0) || ! is_pow2 (v1)))
+    {
+      d0 += count_set_bits (v0) - (v0 != 0);
+      d1 += count_set_bits (v1) - (v1 != 0);
+    }
+
+  is_member0 = (w0 & b0) != 0;
+  is_member1 = (w1 & b1) != 0;
+
+  d0 = is_member0 ? d0 : 0;
+  d1 = is_member1 ? d1 : 0;
+
+  *i0_return = is_member0 + d0;
+  *i1_return = is_member1 + d1;
+}
+
+#define sparse_vec_free(v) vec_free(v)
+
+#define sparse_vec_elt_at_index(v,i) \
+  vec_elt_at_index ((v), sparse_vec_index ((v), (i)))
+
+#define sparse_vec_validate(v,i)					\
+({									\
+  uword _i;								\
+  u32 _insert;								\
+									\
+  if (! (v))								\
+    (v) = sparse_vec_new (sizeof ((v)[0]), BITS (u16));			\
+									\
+  _i = sparse_vec_index_internal ((v), (i),				\
+				  /* maybe range */ 0,			\
+				  /* insert? */ &_insert);		\
+  if (_insert)								\
+    vec_insert_ha ((v), 1, _i,						\
+		   /* header size */ sizeof (sparse_vec_header_t),	\
+		   /* align */ 0);					\
+									\
+  /* Invalid index is 0. */						\
+  ASSERT (_i > 0);							\
+									\
+  (v) + _i;								\
+})
+
+#endif /* included_sparse_vec_h */