1 files changed, 145 insertions, 0 deletions
diff --git a/src/vppinfra/slist.h b/src/vppinfra/slist.h
new file mode 100644
index 00000000..a7c77e27
--- /dev/null
+++ b/src/vppinfra/slist.h
@@ -0,0 +1,145 @@
+/*
+  Copyright (c) 2012 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.
+*/
+
+#ifndef included_slist_h
+#define included_slist_h
+
+#include <stdarg.h>
+#include <vppinfra/clib.h>
+#include <vppinfra/vec.h>
+#include <vppinfra/pool.h>
+#include <vppinfra/error.h>
+#include <vppinfra/format.h>
+#include <vppinfra/cache.h>
+
+typedef word (clib_slist_key_compare_function_t)
+  (void *key, u32 elt_pool_index);
+
+typedef enum
+{
+  CLIB_SLIST_MATCH = 0,
+  CLIB_SLIST_NO_MATCH
+} clib_slist_search_result_t;
+
+typedef struct
+{
+  /* Vector of next elements. Every valid instance has at least one */
+  union
+  {
+    u32 next0[2];
+    u32 *nexts;
+  } n;
+
+  /* Index of item in user's pool */
+  u32 user_pool_index;
+  /* $$$ pad to even divisor of cache line */
+} clib_slist_elt_t;
+
+static inline u32
+clib_slist_get_next_at_level (clib_slist_elt_t * elt, int level)
+{
+  if (elt->n.next0[0] & 1)
+    {
+      ASSERT (level < 2);
+      if (level == 1)
+	return elt->n.next0[1];
+      /* preserve ~0 (end of list) */
+      return (elt->n.next0[0] == (u32) ~ 0) ? elt->n.next0[0] :
+	(elt->n.next0[0] >> 1);
+    }
+  else
+    {
+      ASSERT (level < vec_len (elt->n.nexts));
+      return elt->n.nexts[level];
+    }
+}
+
+static inline void
+clib_slist_set_next_at_level (clib_slist_elt_t * elt, u32 index, int level)
+{
+  u32 old_level0_value[2];
+  /* level0 and not a vector */
+  if (level < 2 && (elt->n.next0[0] == 0 || elt->n.next0[0] & 1))
+    {
+      if (level == 0)
+	{
+	  elt->n.next0[0] = (index << 1) | 1;
+	  return;
+	}
+      elt->n.next0[1] = index;
+      return;
+    }
+  /* have to save old level0 values? */
+  if (elt->n.next0[0] & 1)
+    {
+      old_level0_value[0] = (elt->n.next0[0] == (u32) ~ 0) ?
+	elt->n.next0[0] : elt->n.next0[0] >> 1;
+      old_level0_value[1] = elt->n.next0[1];
+      elt->n.nexts = 0;
+      vec_add1 (elt->n.nexts, old_level0_value[0]);
+      vec_add1 (elt->n.nexts, old_level0_value[1]);
+    }
+  vec_validate (elt->n.nexts, level);
+  elt->n.nexts[level] = index;
+}
+
+
+typedef struct
+{
+  /* pool of skip-list elements */
+  clib_slist_elt_t *elts;
+
+  /* last search path */
+  u32 *path;
+
+  /* last search number of compares */
+  u32 ncompares;
+
+  /* occupancy stats */
+  u32 *occupancy;
+
+  /* Comparison function */
+  clib_slist_key_compare_function_t *compare;
+
+  /* Format function */
+  format_function_t *format_user_element;
+
+  /* items appear in successive plies with Pr (1 / branching_factor) */
+  f64 branching_factor;
+
+  /* random seed */
+  u32 seed;
+} clib_slist_t;
+
+clib_error_t *clib_slist_init (clib_slist_t * sp, f64 branching_factor,
+			       clib_slist_key_compare_function_t compare,
+			       format_function_t format_user_element);
+
+format_function_t format_slist;
+
+void clib_slist_add (clib_slist_t * sp, void *key, u32 user_pool_index);
+clib_slist_search_result_t clib_slist_del (clib_slist_t * sp, void *key);
+u32 clib_slist_search (clib_slist_t * sp, void *key, u32 * ncompares);
+
+#endif /* included_slist_h */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */