bgarrigues pushed a commit to branch format_knuth_plass2 in repository groff.
commit 4cfaeaa812e753fae4a045aa6e9025c0157ba07a Author: Bertrand Garrigues <[email protected]> AuthorDate: 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 | 27 +++--- src/include/list.h | 218 ++++++++++++++++++++++++++++++++++++++++++++++ test/test.am | 25 ++++++ test/utest_list.cpp | 246 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 504 insertions(+), 13 deletions(-) diff --git a/Makefile.am b/Makefile.am index f7ab4107e..f3392502c 100644 --- a/Makefile.am +++ b/Makefile.am @@ -677,6 +677,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 4b1e92fb1..a6ce41bbb 100644 --- a/configure.ac +++ b/configure.ac @@ -80,6 +80,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/.*/:/'], @@ -178,6 +181,14 @@ GROFF_GHOSTSCRIPT_VERSION_CHECK gl_GLIBC21 gl_LOCALCHARSET +# checks for presence of URW fonts (requires ghostscript, which is +# 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: @@ -226,19 +237,9 @@ then fi fi echo "\ - C++ compiler and options : $CXX $CXXFLAGS $CPPFLAGS - use libgroff's memory allocator : $groff_use_own_allocator - C compiler and options : $CC $CFLAGS $CPPFLAGS - Perl interpreter version : $perl_version" -if test "$groff_no_x" = yes -then - echo "\ - X11 support : disabled" -else - echo "\ - X11 support : enabled - X11 app defaults directory : $appdefdir" -fi + URW fonts for pdf : $groff_have_urw_fonts + Use uchardet library for preconv: $groff_have_uchardet + Unit tests build : $have_cppunit" echo "\ 'groff -l' uses print spooler : $groff_have_spooler use URW fonts for PDF output : $groff_have_urw_fonts" diff --git a/src/include/list.h b/src/include/list.h new file mode 100644 index 000000000..f47d74d0f --- /dev/null +++ b/src/include/list.h @@ -0,0 +1,218 @@ +// -*- C++ -*- + +/* Copyright (C) 2016- Free Software Foundation, Inc. + Written by Bertrand Garrigues ([email protected]) + +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 000000000..1bf5e392c --- /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 000000000..20b5e33ff --- /dev/null +++ b/test/utest_list.cpp @@ -0,0 +1,246 @@ +// -*- C++ -*- +/* Copyright (C) 2016 Free Software Foundation, Inc. + Written by Bertrand Garrigues ([email protected]) + +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 ®istry = + CppUnit::TestFactoryRegistry::getRegistry(); + + runner.addTest(registry.makeTest()); + wasSuccessful = runner.run("", false); + + return !wasSuccessful; +} _______________________________________________ Groff-commit mailing list [email protected] https://lists.gnu.org/mailman/listinfo/groff-commit
