[groff] 01/02: Add Linux Kernel style doubled linked lists and use C++ unit test framework cppunit.

[Bertrand Garrigues]

bgarrigues pushed a commit to branch format_knuth_plass
in repository groff.

commit 894dfbfa69e2d4bc7446818d6415d3e77f94cd85
Author: Bertrand Garrigues <address@hidden>
Date:   Sun Apr 3 00:11:49 2016 +0200

    Add Linux Kernel style doubled linked lists and use C++ unit test
    framework cppunit.
    
    * configure.ac: detect presence of pkgconfig and cppunit.
    
    * src/include/list.h: doubled linked list implementation.
    
    * test: new directory for tests.
    
    * test/utest_list.cpp: unit tests for list.h.
    
    * Makefile.am: add new file test/test.am
---
 Makefile.am         |   1 +
 configure.ac        |  10 ++-
 src/include/list.h  | 218 ++++++++++++++++++++++++++++++++++++++++++++++
 test/test.am        |  25 ++++++
 test/utest_list.cpp | 246 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 499 insertions(+), 1 deletion(-)

diff --git a/Makefile.am b/Makefile.am
index 986fb30..b19a353 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -690,6 +690,7 @@ include $(top_srcdir)/src/utils/lookbib/lookbib.am
 include $(top_srcdir)/src/utils/pfbtops/pfbtops.am
 include $(top_srcdir)/src/utils/tfmtodit/tfmtodit.am
 include $(top_srcdir)/src/utils/xtotroff/xtotroff.am
+include $(top_srcdir)/test/test.am
 include $(top_srcdir)/tmac/tmac.am
 
 # Adding defs.h to BUILT_SOURCES will ensure that it will be built on
diff --git a/configure.ac b/configure.ac
index 40c829d..0ad9eef 100644
--- a/configure.ac
+++ b/configure.ac
@@ -90,6 +90,9 @@ GROFF_PROG_XPMTOPPM
 PKG_PROG_PKG_CONFIG
 GROFF_UCHARDET
 
+# check for pkgconfig
+PKG_PROG_PKG_CONFIG
+
 # use a dummy substitution if no csh hack is necessary to avoid errors
 # with non-GNU sed programs
 GROFF_CSH_HACK([SH_SCRIPT_SED_CMD='1s/.*/:/'], [SH_SCRIPT_SED_CMD='1s/a/a/'])
@@ -187,6 +190,10 @@ gl_LOCALCHARSET
 # checked in GROFF_HTML_PROGRAMS
 GROFF_URW_FONTS
 
+# Check for cppunit, unit test framework
+PKG_CHECK_MODULES([CPPUNIT], [cppunit >= 1.9.6], have_cppunit=yes, 
have_cppunit=no)
+AM_CONDITIONAL([BUILD_UNIT_TESTS], [test "$have_cppunit" = "yes" ])
+
 AM_CONDITIONAL([BUILD_WINSCRIPTS], [test -n "$make_winscripts"])
 
 # If X11 is not available, don't build:
@@ -240,7 +247,8 @@ echo "\
 fi
 echo "\
  URW fonts for pdf               : $groff_have_urw_fonts
- Use uchardet library for preconv: $groff_have_uchardet"
+ Use uchardet library for preconv: $groff_have_uchardet
+ Unit tests build  : $have_cppunit"
 echo "\
 ----------------------------------------------------------------------"
 
diff --git a/src/include/list.h b/src/include/list.h
new file mode 100644
index 0000000..f47d74d
--- /dev/null
+++ b/src/include/list.h
@@ -0,0 +1,218 @@
+// -*- C++ -*-
+
+/* Copyright (C) 2016-  Free Software Foundation, Inc.
+   Written by Bertrand Garrigues (address@hidden)
+
+This file is part of groff.
+
+groff is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation, either version 3 of the License, or
+(at your option) any later version.
+
+groff is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+/*
+ * Simple doubly linked list implementation.
+ * Linux Kernel's list style.
+ */
+
+#ifndef LIST_H
+#define LIST_H
+
+#ifndef NULL
+#define NULL 0
+#endif
+
+struct list_head {
+  struct list_head *prev;
+  struct list_head *next;
+  void *container;
+};
+
+#define LIST_HEAD_INIT(name, container) { &(name), &(name), container}
+
+static inline void INIT_LIST_HEAD(struct list_head * list, void *container)
+{
+   list->next = list;
+   list->prev = list;
+   list->container = container;
+}
+
+/*
+ * Insert a new entry between two known consecutive entries.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_add(struct list_head * nnew, struct list_head * prev,
+      struct list_head * next)
+{
+   next->prev = nnew;
+   nnew->next = next;
+   nnew->prev = prev;
+   prev->next = nnew;
+}
+
+/**
+ * list_add - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+static inline void list_add(struct list_head * nnew, struct list_head * head)
+{
+   __list_add(nnew, head, head->next);
+}
+
+/**
+ * list_add_tail - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it before
+ *
+ * Insert a new entry before the specified head.
+ * This is useful for implementing queues.
+ */
+static inline void list_add_tail(struct list_head * nnew,
+      struct list_head * head)
+{
+   __list_add(nnew, head->prev, head);
+}
+
+/*
+ * Delete a list entry by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_del(struct list_head * prev, struct list_head * next)
+{
+   next->prev = prev;
+   prev->next = next;
+}
+
+/**
+ * list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty() on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+static inline void __list_del_entry(struct list_head * entry)
+{
+   __list_del(entry->prev, entry->next);
+}
+
+static inline void list_del(struct list_head * entry)
+{
+   __list_del(entry->prev, entry->next);
+   entry->next = NULL;
+   entry->prev = NULL;
+}
+
+/**
+ * list_del_init - deletes entry from list and reinitialize it.
+ * @entry: the element to delete from the list.
+ */
+static inline void list_del_init(struct list_head * entry)
+{
+   __list_del_entry(entry);
+   entry->next = entry;
+   entry->prev = entry;
+}
+
+/**
+ * list_is_last - tests whether @list is the last entry in list @head
+ * @list: the entry to test
+ * @head: the head of the list
+ */
+static inline int list_is_last(const struct list_head * list,
+      const struct list_head * head)
+{
+   return list->next == head;
+}
+
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static inline int list_empty(const struct list_head * head)
+{
+   return head->next == head;
+}
+
+
+/**
+ * list_entry - get the struct for this entry
+ * @ptr: the &struct list_head pointer.
+ * @type:   the type of the struct this is embedded in.
+ */
+#define list_entry(ptr, type) \
+  (type *)((ptr)->container)
+
+/**
+ * list_first_entry - get the first element from a list
+ * @ptr: the list head to take the element from.
+ * @type:   the type of the struct this is embedded in.
+ * @member: the name of the list_struct within the struct.
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define list_first_entry(ptr, type) \
+  (type *)((ptr)->next->container)
+
+
+/**
+ * list_for_each  -  iterate over a list
+ * @pos: the &struct list_head to use as a loop cursor.
+ * @head:   the head for your list.
+ */
+#define list_for_each(pos, head) \
+   for (pos = (head)->next; pos != (head); pos = pos->next)
+
+/**
+ * list_for_each_safe - iterate over a list safe against removal of list entry
+ * @pos: the &struct list_head to use as a loop cursor.
+ * @n:      another &struct list_head to use as temporary storage
+ * @head:   the head for your list.
+ */
+#define list_for_each_safe(pos, n, head) \
+   for (pos = (head)->next, n = pos->next; \
+        pos != (head); \
+        pos = n, n = pos->next)
+
+/**
+ * list_for_each_entry  -  iterate over list of given type
+ * @pos: the type * to use as a loop cursor.
+ * @head:   the head for your list.
+ * @member: the name of the list_struct within the struct.
+ * @type: type of the container
+ */
+#define list_for_each_entry(pos, head, member, type)     \
+   for (pos = list_entry((head)->next, type); \
+        pos != NULL && &pos->member != (head); \
+        pos = list_entry(pos->member.next, type))
+
+/**
+ * list_for_each_entry_safe - iterate over list of given type safe against
+ * removal of list entry
+ * @pos: the type * to use as a loop cursor.
+ * @n:      another type * to use as temporary storage
+ * @head:   the head for your list.
+ * @type: type of the container
+ * @member: the name of the list_struct within the struct.
+ */
+#define list_for_each_entry_safe(pos, n, head, member, type) \
+   for (pos = list_entry((head)->next, type), \
+            n = list_entry((head)->next->next, type); \
+        pos != NULL && &pos->member != (head); \
+        pos = n, n = (n != NULL ? list_entry(n->member.next, type) : NULL))
+#endif /* LIST_H */
diff --git a/test/test.am b/test/test.am
new file mode 100644
index 0000000..1bf5e39
--- /dev/null
+++ b/test/test.am
@@ -0,0 +1,25 @@
+# Copyright (C) 2016-
+#      Free Software Foundation, Inc.
+#
+# This file is part of groff.
+#
+# groff is free software; you can redistribute it and/or modify it under
+# the terms of the GNU General Public License as published by the Free
+# Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# groff is distributed in the hope that it will be useful, but WITHOUT ANY
+# WARRANTY; without even the implied warranty of MERCHANTABILITY or
+# FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+# for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <http://www.gnu.org/licenses/>.
+
+if BUILD_UNIT_TESTS
+TESTS += utest_list
+check_PROGRAMS += utest_list
+utest_list_SOURCES = test/utest_list.cpp
+utest_list_CXXFLAGS = $(CPPUNIT_CFLAGS) -I$(top_srcdir)/src/roff/troff
+utest_list_LDFLAGS = $(CPPUNIT_LIBS)
+endif
diff --git a/test/utest_list.cpp b/test/utest_list.cpp
new file mode 100644
index 0000000..20b5e33
--- /dev/null
+++ b/test/utest_list.cpp
@@ -0,0 +1,246 @@
+// -*- C++ -*-
+/* Copyright (C) 2016  Free Software Foundation, Inc.
+     Written by Bertrand Garrigues (address@hidden)
+
+This file is part of groff.
+
+groff is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation, either version 3 of the License, or
+(at your option) any later version.
+
+groff is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "list.h"
+#include <iostream>
+#include <cppunit/extensions/TestFactoryRegistry.h>
+#include <cppunit/ui/text/TestRunner.h>
+#include <cppunit/extensions/HelperMacros.h>
+
+/**
+ * A class to test the struct list_head implementation of double-linked list.
+ */
+class dummy {
+public:
+  int data;
+  struct list_head lh;  
+  dummy (int x)
+  {
+    data = x;
+    INIT_LIST_HEAD(&lh, this);
+  }
+
+  int get_data ()
+  {
+    return data;
+  }
+};
+  
+class ListTest : public CppUnit::TestFixture {
+  
+  CPPUNIT_TEST_SUITE(ListTest);
+  CPPUNIT_TEST(testAdd);
+  CPPUNIT_TEST(testAddTail);
+  CPPUNIT_TEST(testForEachEntry);
+  CPPUNIT_TEST(testForEachEntry2);
+  CPPUNIT_TEST(testForEachEntrySafe);
+  CPPUNIT_TEST(testForEachEntrySafe2);
+  CPPUNIT_TEST_SUITE_END();
+  
+private:
+  // Head of the list: we will add class dummy object to this list.
+  struct list_head head;
+  // dummy objects to be added to the list.
+  dummy *a, *b, *c;
+public:
+  // Fixture
+  void setUp()
+  {
+    INIT_LIST_HEAD(&head, NULL);
+  }
+
+  // Teardown: we rather make individual teardown at the end of each test.
+  void tearDown()
+  {
+  }
+
+  // list_add: this should add a new dummy object after head, like in a stack.
+  void testAdd()
+  {
+    a = new dummy(10);
+    b = new dummy(20);
+    c = new dummy(30);
+    
+    list_add(&a->lh, &head);
+    CPPUNIT_ASSERT(head.next == &a->lh);
+    CPPUNIT_ASSERT(head.prev == &a->lh);
+    list_add(&b->lh, &head);
+    CPPUNIT_ASSERT(head.next == &b->lh);
+    CPPUNIT_ASSERT(head.prev == &a->lh);
+    list_add(&c->lh, &head);
+    CPPUNIT_ASSERT(head.next == &c->lh);
+    CPPUNIT_ASSERT(head.prev == &a->lh);
+
+    list_del_init(&a->lh);
+    list_del_init(&b->lh);
+    list_del_init(&c->lh);
+    CPPUNIT_ASSERT(list_empty(&head));
+                   
+    // Local teardown
+    INIT_LIST_HEAD(&head, NULL);
+    delete a;
+    delete b;
+    delete c;
+  }
+
+  // list_add: this should add a new dummy object before head, like in a queue.
+  void testAddTail()
+  {
+    a = new dummy(10);
+    b = new dummy(20);
+    c = new dummy(30);
+    
+    list_add_tail(&a->lh, &head);
+    CPPUNIT_ASSERT(head.next == &a->lh);
+    CPPUNIT_ASSERT(head.prev == &a->lh);
+    list_add_tail(&b->lh, &head);
+    CPPUNIT_ASSERT(head.next == &a->lh);
+    CPPUNIT_ASSERT(head.prev == &b->lh);
+    list_add_tail(&c->lh, &head);
+    CPPUNIT_ASSERT(head.next == &a->lh);
+    CPPUNIT_ASSERT(head.prev == &c->lh);
+
+    list_del_init(&a->lh);
+    list_del_init(&b->lh);
+    list_del_init(&c->lh);
+    CPPUNIT_ASSERT(list_empty(&head));
+
+    // Local teardown
+    INIT_LIST_HEAD(&head, NULL);
+    delete a;
+    delete b;
+    delete c;
+  }
+
+  // Walk into the list and display the data of each dummy object
+  void testForEachEntry()
+  {
+    dummy *pos;
+    int k = 10;
+    
+    a = new dummy(10);
+    b = new dummy(20);
+    c = new dummy(30);
+    
+    list_add_tail(&a->lh, &head);
+    list_add_tail(&b->lh, &head);
+    list_add_tail(&c->lh, &head);
+    list_for_each_entry(pos, &head, lh, dummy) {
+      CPPUNIT_ASSERT(pos->data == k);
+      k+=10;
+    }
+    
+    CPPUNIT_ASSERT(k == 40);
+    
+    // Local teardown
+    INIT_LIST_HEAD(&head, NULL);
+    delete a;
+    delete b;
+    delete c;
+  }
+
+  // Special case of a list of size 1 or an empty list
+  void testForEachEntry2()
+  {
+    dummy *pos;
+    a = new dummy(10);
+    
+    list_add_tail(&a->lh, &head);
+    list_for_each_entry(pos, &head, lh, dummy) {
+      CPPUNIT_ASSERT(pos->data == 10);
+    }
+    list_del_init(&a->lh);
+    
+    list_for_each_entry(pos, &head, lh, dummy) {
+      // We should not enter this loop
+      CPPUNIT_ASSERT(false);
+    }
+    CPPUNIT_ASSERT(true);
+    
+    // Local teardown
+    INIT_LIST_HEAD(&head, NULL);
+    delete a;
+  }
+  
+  // Walk into the list, but this time we delete the dummy objects one by one,
+  // so we use list_for_each_entry_safe rather than list_for_each_entry
+  void testForEachEntrySafe()
+  {
+    dummy *pos, *n;
+    int k = 10;
+
+    a = new dummy(10);
+    b = new dummy(20);
+    c = new dummy(30);
+
+    list_add_tail(&a->lh, &head);
+    list_add_tail(&b->lh, &head);
+    list_add_tail(&c->lh, &head);
+    list_for_each_entry_safe(pos, n, &head, lh, dummy) {
+      list_del_init(&pos->lh);
+      CPPUNIT_ASSERT(pos->data == k);
+      k+=10;
+      delete pos;
+    }
+    
+    CPPUNIT_ASSERT(true);
+    // Local teardown
+    INIT_LIST_HEAD(&head, NULL);
+  }
+
+  // Just test that we don't crash when walking thru a list with 1 item or an
+  // empty list.
+  void testForEachEntrySafe2()
+  {
+    dummy *pos, *n;
+    a = new dummy(10);
+
+    list_add_tail(&a->lh, &head);
+    list_for_each_entry_safe(pos, n, &head, lh, dummy) {
+      list_del_init(&pos->lh);
+      CPPUNIT_ASSERT(pos->data == 10);
+      delete pos;
+    }
+
+    list_for_each_entry_safe(pos, n, &head, lh, dummy) {
+      // we should not enter this loop
+      CPPUNIT_ASSERT(false);
+    }
+
+    CPPUNIT_ASSERT(true);
+    // Local teardown
+    INIT_LIST_HEAD(&head, NULL);
+  }
+};
+
+CPPUNIT_TEST_SUITE_REGISTRATION(ListTest);
+
+int main(int argc, char **argv)
+{
+  CppUnit::TextUi::TestRunner runner;
+  bool wasSuccessful;
+  CppUnit::TestFactoryRegistry &registry =
+    CppUnit::TestFactoryRegistry::getRegistry();
+  
+  runner.addTest(registry.makeTest());
+  wasSuccessful = runner.run("", false);
+  
+  return !wasSuccessful;
+}