vppinfra: add doubly linked list

Type: feature

Change-Id: I21511c1abea703da67f1a491e73342496275c498
Signed-off-by: Florin Coras <fcoras@cisco.com>

4 files changed, 609 insertions, 0 deletions

diff --git a/src/plugins/unittest/CMakeLists.txt b/src/plugins/unittest/CMakeLists.txt
index 2afe5e781da..5ba21bd7acb 100644
--- a/src/plugins/unittest/CMakeLists.txt
+++ b/src/plugins/unittest/CMakeLists.txt
@@ -26,6 +26,7 @@ add_vpp_plugin(unittest
   ipsec_test.c
   interface_test.c
   lisp_cp_test.c
+  llist_test.c
   mactime_test.c
   mfib_test.c
   punt_test.c
diff --git a/src/plugins/unittest/llist_test.c b/src/plugins/unittest/llist_test.c
new file mode 100644
index 00000000000..bd8f6c074c5
--- /dev/null
+++ b/src/plugins/unittest/llist_test.c
@@ -0,0 +1,353 @@
+/*
+ * Copyright (c) 2019 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.
+ */
+#include <vppinfra/llist.h>
+#include <vlib/vlib.h>
+
+#define LLIST_TEST_I(_cond, _comment, _args...)			\
+({								\
+  int _evald = (_cond);						\
+  if (!(_evald)) {						\
+    fformat(stderr, "FAIL:%d: " _comment "\n",			\
+	    __LINE__, ##_args);					\
+  } else {							\
+    fformat(stderr, "PASS:%d: " _comment "\n",			\
+	    __LINE__, ##_args);					\
+  }								\
+  _evald;							\
+})
+
+#define LLIST_TEST(_cond, _comment, _args...)			\
+{								\
+    if (!LLIST_TEST_I(_cond, _comment, ##_args)) {		\
+	return 1;                                               \
+    }								\
+}
+
+typedef struct list_elt
+{
+  clib_llist_anchor_t ll_test;
+  clib_llist_anchor_t ll_test2;
+  u32 data;
+} list_elt_t;
+
+#define list_elt_is_sane(pl,name,E,P,N)					\
+ (E->name.next == (N) - pl 						\
+  && E->name.prev == (P) - pl 						\
+  && P->name.next == (E) - pl 						\
+  && N->name.prev == (E) - pl)
+
+#define list_test_is_sane(pl,name,h)					\
+do {									\
+  typeof (pl) e;							\
+  int rv;								\
+  clib_llist_foreach (pl, name, h, e, ({					\
+    rv = list_elt_is_sane ((pl), name, (e),				\
+			   clib_llist_prev (pl,name,e),			\
+                           clib_llist_next (pl,name,e));			\
+    if (!rv)								\
+      LLIST_TEST (0, "invalid elt %u prev %u/%u next %u/%u", e - pl, 	\
+                  e->name.prev, clib_llist_prev (pl,name,e) - pl,		\
+                  e->name.next, clib_llist_next (pl,name,e) - pl);		\
+  }));									\
+} while (0)
+
+static int
+llist_test_basic (vlib_main_t * vm, unformat_input_t * input)
+{
+  list_elt_t *pelts = 0, *he, *he2, *he3, *e, *next, *nnext;
+  int __clib_unused verbose, i, rv;
+  clib_llist_index_t head, head2, head3;
+  u32 old_tail;
+
+  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
+    {
+      if (unformat (input, "verbose"))
+	verbose = 1;
+      else
+	{
+	  vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
+			   input);
+	  return -1;
+	}
+    }
+
+  head = clib_llist_make_head (pelts, ll_test);
+  he = pool_elt_at_index (pelts, head);
+
+  LLIST_TEST (he->ll_test.next == head, "head next points to itself");
+  LLIST_TEST (he->ll_test.prev == head, "head prev points to itself");
+  LLIST_TEST (he == clib_llist_next (pelts, ll_test, he),
+	      "should be the same");
+  LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he),
+	      "should be the same");
+
+  /*
+   * Add and remove one element
+   */
+  pool_get (pelts, e);
+  e->data = 1;
+  he = pool_elt_at_index (pelts, head);
+  clib_llist_add (pelts, ll_test, e, he);
+
+  LLIST_TEST (e->ll_test.next == head, "next should be head");
+  LLIST_TEST (e->ll_test.prev == head, "prev should be head");
+  LLIST_TEST (he->ll_test.prev == e - pelts, "prev should be new");
+  LLIST_TEST (he->ll_test.next == e - pelts, "prev should be new");
+
+  clib_llist_remove (pelts, ll_test, e);
+  pool_put (pelts, e);
+  LLIST_TEST (he->ll_test.prev == head, "prev should be head");
+  LLIST_TEST (he->ll_test.prev == head, "next should be head");
+  LLIST_TEST (he == clib_llist_next (pelts, ll_test, he),
+	      "should be the same");
+  LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he),
+	      "should be the same");
+
+  /*
+   * Add multiple head elements and test insertion
+   */
+  for (i = 0; i < 100; i++)
+    {
+      pool_get (pelts, e);
+      e->data = i;
+      he = pool_elt_at_index (pelts, head);
+      clib_llist_add (pelts, ll_test, e, he);
+    }
+
+  he = pool_elt_at_index (pelts, head);
+  LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
+	      "shoud not be empty");
+  list_test_is_sane (pelts, ll_test, he);
+
+  i--;
+  /* *INDENT-OFF* */
+  clib_llist_foreach (pelts, ll_test, he, e, ({
+    if (i != e->data)
+      LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
+    i--;
+  }));
+  /* *INDENT-ON* */
+
+  LLIST_TEST (i == -1, "head insertion works i = %d", i);
+
+  /*
+   * Remove elements from head
+   */
+  i = 99;
+  e = clib_llist_next (pelts, ll_test, he);
+  while (e != he)
+    {
+      next = clib_llist_next (pelts, ll_test, e);
+      clib_llist_remove (pelts, ll_test, e);
+      pool_put (pelts, e);
+      i--;
+      e = next;
+    }
+
+  he = pool_elt_at_index (pelts, head);
+  list_test_is_sane (pelts, ll_test, he);
+  LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he),
+	      "list should be empty");
+  LLIST_TEST (pool_elts (pelts) == 1, "pool should have only 1 element");
+
+  /*
+   * Add tail elements to ll_test2 and test
+   */
+  head2 = clib_llist_make_head (pelts, ll_test2);
+  for (i = 0; i < 100; i++)
+    {
+      pool_get (pelts, e);
+      e->data = i;
+      he2 = pool_elt_at_index (pelts, head2);
+      clib_llist_add_tail (pelts, ll_test2, e, he2);
+    }
+
+  he2 = pool_elt_at_index (pelts, head2);
+  list_test_is_sane (pelts, ll_test2, he2);
+  LLIST_TEST (!clib_llist_is_empty (pelts, ll_test2, he2),
+	      "list should not be empty");
+
+  i--;
+  /* *INDENT-OFF* */
+  clib_llist_foreach_reverse (pelts, ll_test2, he2, e, ({
+    if (i != e->data)
+	LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
+    i--;
+  }));
+  /* *INDENT-ON* */
+  LLIST_TEST (i == -1, "tail insertion works");
+
+  /*
+   * Remove in from ll_test2 and add to ll_test
+   */
+  i = 0;
+  he = pool_elt_at_index (pelts, head);
+  e = clib_llist_next (pelts, ll_test2, he2);
+  while (e != he2)
+    {
+      next = clib_llist_next (pelts, ll_test2, e);
+
+      if (e->data != i)
+	LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
+
+      clib_llist_remove (pelts, ll_test2, e);
+      clib_llist_add_tail (pelts, ll_test, e, he);
+      i++;
+      e = next;
+    }
+
+  he = pool_elt_at_index (pelts, head);
+  he2 = pool_elt_at_index (pelts, head2);
+  list_test_is_sane (pelts, ll_test, he);
+  LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
+	      "shoud not be empty");
+  LLIST_TEST (clib_llist_is_empty (pelts, ll_test2, he2), "shoud be empty");
+
+  i = 0;
+
+  /* *INDENT-OFF* */
+  clib_llist_foreach (pelts, ll_test, he, e, ({
+    if (i != e->data)
+	LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
+    i++;
+  }));
+  /* *INDENT-ON* */
+
+  LLIST_TEST (i == 100, "move from ll_test2 to ll_test worked i %u", i);
+
+  /*
+   * Delete and insert at random position
+   */
+  e = pool_elt_at_index (pelts, head);
+  for (i = 0; i < 10; i++)
+    e = clib_llist_next (pelts, ll_test, e);
+
+  next = clib_llist_next (pelts, ll_test, e);
+  nnext = clib_llist_next (pelts, ll_test, next);
+
+  LLIST_TEST (e->data == 9, "data should be 9 is %u", e->data);
+  LLIST_TEST (next->data == 10, "data should be 10");
+  LLIST_TEST (nnext->data == 11, "data should be 11");
+
+  clib_llist_remove (pelts, ll_test, next);
+  pool_put (pelts, next);
+  memset (next, 0xfc, sizeof (*next));
+
+  next = clib_llist_next (pelts, ll_test, e);
+  LLIST_TEST (next->data == 11, "data should be 11");
+  LLIST_TEST (next == nnext, "should be nnext");
+
+  pool_get (pelts, next);
+  next->data = 10;
+  clib_llist_insert (pelts, ll_test, next, e);
+
+  next = clib_llist_next (pelts, ll_test, e);
+  LLIST_TEST (next->data == 10, "new next data should be 10");
+  next = clib_llist_next (pelts, ll_test, next);
+  LLIST_TEST (nnext == next, "next should be linked to old nnext");
+
+  he = pool_elt_at_index (pelts, head);
+  list_test_is_sane (pelts, ll_test, he);
+
+  /*
+   * Make a new list that uses ll_test anchor
+   */
+
+  head3 = clib_llist_make_head (pelts, ll_test);
+  for (i = 0; i < 10; i++)
+    {
+      pool_get (pelts, e);
+      e->data = 300 + i;
+      he3 = pool_elt_at_index (pelts, head3);
+      clib_llist_add (pelts, ll_test, e, he3);
+    }
+
+  he = pool_elt_at_index (pelts, head);
+  he3 = pool_elt_at_index (pelts, head3);
+  list_test_is_sane (pelts, ll_test, he3);
+  e = clib_llist_prev (pelts, ll_test, he);
+  old_tail = e->data;
+
+  /*
+   * Splice third list into the tail of the first
+   */
+  clib_llist_splice (pelts, ll_test, e, he3);
+
+  list_test_is_sane (pelts, ll_test, he);
+  LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he3), "should be empty");
+
+  e = clib_llist_prev (pelts, ll_test, he);
+  LLIST_TEST (e->data == 300, "data for last spliced should be 300 is %u",
+	      e->data);
+  for (i = 0; i < 10; i++)
+    {
+      if (e->data != 300 + i)
+	LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
+      e = clib_llist_prev (pelts, ll_test, e);
+    }
+
+  LLIST_TEST (e->data == old_tail, "data should be old tail %u is %u",
+	      old_tail, e->data);
+
+  /*
+   * Cleanup
+   */
+  pool_free (pelts);
+  return 0;
+}
+
+static clib_error_t *
+llist_test (vlib_main_t * vm,
+	    unformat_input_t * input, vlib_cli_command_t * cmd_arg)
+{
+  int res = 0;
+
+  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
+    {
+      if (unformat (input, "basic"))
+	{
+	  res = llist_test_basic (vm, input);
+	}
+      else if (unformat (input, "all"))
+	{
+	  if ((res = llist_test_basic (vm, input)))
+	    goto done;
+	}
+      else
+	break;
+    }
+
+done:
+  if (res)
+    return clib_error_return (0, "llist unit test failed");
+  return 0;
+}
+
+/* *INDENT-OFF* */
+VLIB_CLI_COMMAND (llist_test_command, static) =
+{
+  .path = "test llist",
+  .short_help = "internal llist unit tests",
+  .function = llist_test,
+};
+/* *INDENT-ON* */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/CMakeLists.txt b/src/vppinfra/CMakeLists.txt
index d8b302cf399..9c5804602a1 100644
--- a/src/vppinfra/CMakeLists.txt
+++ b/src/vppinfra/CMakeLists.txt
@@ -123,6 +123,7 @@ set(VPPINFRA_HEADERS
   hash.h
   heap.h
   lb_hash_hash.h
+  llist.h
   lock.h
   longjmp.h
   macros.h
diff --git a/src/vppinfra/llist.h b/src/vppinfra/llist.h
new file mode 100644
index 00000000000..1648021681f
--- /dev/null
+++ b/src/vppinfra/llist.h
@@ -0,0 +1,254 @@
+/*
+ * Copyright (c) 2019 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.
+ *
+ * @file
+ * @brief Circular doubly linked list with head sentinel.
+ * List entries are allocated out of a "supporting" pool and all pool entries
+ * must contain a list anchor struct for each list they pertain to.
+ */
+
+#ifndef SRC_VPPINFRA_CLIB_LLIST_H_
+#define SRC_VPPINFRA_CLIB_LLIST_H_
+
+#include <vppinfra/types.h>
+#include <vppinfra/pool.h>
+
+typedef u32 clib_llist_index_t;
+
+typedef struct clib_llist_anchor
+{
+  clib_llist_index_t prev;
+  clib_llist_index_t next;
+} clib_llist_anchor_t;
+
+#define CLIB_LLIST_INVALID_INDEX ((u32)~0)
+
+/**
+ * Local variable naming macro.
+ */
+#define _ll_var(v) _llist_##v
+/**
+ * Local macros to grab llist anchor next and prev from pool entry
+ */
+#define _lnext(E,name) ((E)->name).next
+#define _lprev(E,name) ((E)->name).prev
+/**
+ * Get list entry index
+ *
+ * @param LP	linked list pool
+ * @param E	pool entry
+ * @return	pool entry index
+ */
+#define clib_llist_entry_index(LP,E) ((E) - (LP))
+/**
+ * Get next pool entry
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param E	pool entry
+ * @return	next pool entry
+ */
+#define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name))
+/**
+ * Get previous pool entry
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param E	pool entry
+ * @return	previous pool entry
+ */
+#define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name))
+/**
+ * Initialize element in llist for entry
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param E	entry whose ll anchor is to be initialized
+ */
+#define clib_llist_anchor_init(LP,name,E)				\
+do {									\
+  _lprev ((E),name) = clib_llist_entry_index ((LP), (E));		\
+  _lnext ((E),name) = _lprev ((E),name);				\
+} while (0)
+/**
+ * Initialize llist head
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ */
+#define clib_llist_make_head(LP,name)					\
+({									\
+  typeof (LP) _ll_var (head);						\
+  pool_get_zero ((LP), _ll_var (head));					\
+  clib_llist_anchor_init ((LP),name,_ll_var (head));			\
+  clib_llist_entry_index ((LP), _ll_var (head));			\
+})
+/**
+ * Check is list is empty
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param H	list head
+ * @return	1 if sentinel is the only node part of the list, 0 otherwise
+ */
+#define clib_llist_is_empty(LP,name,H) ((H) == clib_llist_next((LP),name,(H)))
+/**
+ * Insert entry between previous and next
+ *
+ * Internal use.
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param E	new entry
+ * @param P	previous in list
+ * @param N	next in list
+ */
+#define _llist_insert(LP,name,E,P,N)					\
+do {									\
+  _lprev (E,name) = _lprev(N,name);					\
+  _lnext (E,name) = _lnext(P,name);					\
+  _lprev ((N),name) = clib_llist_entry_index ((LP),(E));		\
+  _lnext ((P),name) = clib_llist_entry_index ((LP),(E));		\
+} while (0)
+/**
+ * Insert entry after previous
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param E	new entry
+ * @param P	previous in list
+ */
+#define clib_llist_insert(LP,name,E,P) 					\
+do {									\
+  typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P);		\
+  _llist_insert ((LP),name,(E),(P), _ll_var (N));			\
+} while (0)
+
+/**
+ * Add entry after head
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param E	new entry
+ * @param H	list head
+ */
+#define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
+/**
+ * Add entry after tail
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param E	new entry
+ * @param H	list head
+ */
+#define clib_llist_add_tail(LP,name,E,H)				\
+do {									\
+  typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H));		\
+  _llist_insert ((LP),name,(E),_ll_var (P),(H));			\
+} while (0)
+/**
+ * Remove entry from list
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param E	entry to be removed
+ */
+#define clib_llist_remove(LP,name,E)					\
+do {									\
+  ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\
+  ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX);			\
+  ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX);			\
+  typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E);		\
+  typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E);		\
+  _lnext (_ll_var (P),name) = _lnext (E,name);				\
+  _lprev (_ll_var (N),name) = _lprev (E,name);				\
+  _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX;		\
+}while (0)
+
+/**
+ * Splice two lists at a given position
+ *
+ * List spliced into destination list is left with 0 entries, i.e., head
+ * is made to point to itself.
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param P	position in destination where source list is spliced
+ * @param H	head of source list that will be spliced into destination
+ */
+#define clib_llist_splice(LP,name,P,H)					\
+do {									\
+  typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H);		\
+  if (_ll_var (fe) != (H))						\
+    {									\
+      typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H);		\
+      typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P);		\
+      _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P);	\
+      _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\
+      _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe));	\
+      _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\
+      _lnext (H,name) = clib_llist_entry_index(LP,H);			\
+      _lprev (H,name) = _lnext (H,name);				\
+    }									\
+} while (0)
+/**
+ * Walk list starting at head
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param H	head entry
+ * @param E	entry iterator
+ * @param body	code to be executed
+ */
+#define clib_llist_foreach(LP,name,H,E,body)				\
+do {									\
+  typeof (LP) _ll_var (n);						\
+  (E) = clib_llist_next (LP,name,H);					\
+  while (E != H)							\
+    { 									\
+      _ll_var (n) = clib_llist_next (LP,name,E);			\
+      do { body; } while (0);						\
+      (E) = _ll_var (n);						\
+    }									\
+} while (0)
+/**
+ * Walk list starting at head in reverse order
+ *
+ * @param LP	linked list pool
+ * @param name	list anchor name
+ * @param H	head entry
+ * @param E	entry iterator
+ * @param body	code to be executed
+ */
+#define clib_llist_foreach_reverse(LP,name,H,E,body)			\
+do {									\
+  typeof (LP) _ll_var (p);						\
+  (E) = clib_llist_prev (LP,name,H);					\
+  while (E != H)							\
+    { 									\
+      _ll_var (p) = clib_llist_prev (LP,name,E);			\
+      do { body; } while (0);						\
+      (E) = _ll_var (p);						\
+    }									\
+} while (0)
+
+#endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */