[PATCH 1/4] Add null-terminated list interface.

[Peter Hutterer]

This is a set of macros to provide a struct list-alike interface for classic
linked lists such as the XF86OptionRec or the DeviceIntRec. The typical
format for these is to have a "struct foo *next" pointer in each struct foo
and walk through those. These macros provide a few basic functions to add to,
remove from and iterate through these lists.

While struct list is in some ways more flexible, switching legacy code to
use struct list is not alway viable. These macros at least reduce the amount
of open-coded lists.

Signed-off-by: Peter Hutterer <peter.hutterer at who-t.net>
---
 include/list.h |  160 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 test/list.c    |  164 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 324 insertions(+), 0 deletions(-)

diff --git a/include/list.h b/include/list.h
index 5933b97..94d76fe 100644
--- a/include/list.h
+++ b/include/list.h
@@ -278,4 +278,164 @@ list_is_empty(struct list *head)
 	 &pos->member != (head);					\
 	 pos = tmp, tmp = __container_of(pos->member.next, tmp, member))
 
+
+
+/* NULL-Terminated List Interface
+ *
+ * The interface below does _not_ use the struct list as described above.
+ * It is mainly for legacy structures that cannot easily be switched to
+ * struct list.
+ *
+ * This interface is for structs like
+ *      struct foo {
+ *          [...]
+ *          struct foo *next;
+ *           [...]
+ *      };
+ *
+ * The position and field name of "next" are arbitrary.
+ */
+
+/**
+ * Init the element as null-terminated list.
+ *
+ * Example:
+ * struct foo *list = malloc();
+ * nt_list_init(list, next);
+ *
+ * @param list The list element that will be the start of the list
+ * @param member Member name of the field pointing to next struct
+ */
+#define nt_list_init(_list, _member) \
+	(_list)->_member = NULL
+
+/**
+ * Returns the next element in the list or NULL on termination.
+ *
+ * Example:
+ * struct foo *element = list;
+ * while ((element = nt_list_next(element, next)) { }
+ *
+ * This macro is not safe for node deletion. Use list_for_each_entry_safe
+ * instead.
+ *
+ * @param list The list or current element.
+ * @param member Member name of the field pointing to next struct.
+ */
+#define nt_list_next(_list, _member) \
+	(_list)->_member
+
+/**
+ * Iterate through each element in the list.
+ *
+ * Example:
+ * struct foo *iterator;
+ * nt_list_for_each_entry(iterator, list, next) {
+ *      [modify iterator]
+ * }
+ *
+ * @param entry Assigned to the current list element
+ * @param list The list to iterate through.
+ * @param member Member name of the field pointing to next struct.
+ */
+#define nt_list_for_each_entry(_entry, _list, _member)			\
+	for (_entry = _list; _entry; _entry = (_entry)->_member)
+
+/**
+ * Iterate through each element in the list, keeping a backup pointer to the
+ * element. This macro allows for the deletion of a list element while
+ * looping through the list.
+ *
+ * See nt_list_for_each_entry for more details.
+ *
+ * @param entry Assigned to the current list element
+ * @param tmp The pointer to the next element
+ * @param list The list to iterate through.
+ * @param member Member name of the field pointing to next struct.
+ */
+#define nt_list_for_each_entry_safe(_entry, _tmp, _list, _member)	\
+	for (_entry = _list, _tmp = (_entry) ? (_entry)->_member : NULL;\
+		_entry;							\
+		_entry = _tmp, _tmp = (_tmp) ? (_tmp)->_member: NULL)
+
+
+/**
+ * Append the element to the end of the list. This macro may be used to
+ * merge two lists.
+ *
+ * Example:
+ * struct foo *elem = malloc(...);
+ * nt_list_init(elem, next)
+ * nt_list_append(elem, list, struct foo, next);
+ *
+ * Resulting list order:
+ * list_item_0 -> list_item_1 -> ... -> elem_item_0 -> elem_item_1 ...
+ *
+ * @param entry An entry (or list) to append to the list
+ * @param list The list to append to. This list must be a valid list, not
+ * NULL.
+ * @param type The list type
+ * @param member Member name of the field pointing to next struct
+ */
+#define nt_list_append(_entry, _list, _type, _member)		        \
+    do {								\
+	_type *__iterator = _list;					\
+	while (__iterator->_member) { __iterator = __iterator->_member;}\
+	__iterator->_member = _entry;					\
+    } while (0)
+
+/**
+ * Insert the element at the next position in the list. This macro may be
+ * used to insert a list into a list.
+ *
+ * struct foo *elem = malloc(...);
+ * nt_list_init(elem, next)
+ * nt_list_insert(elem, list, struct foo, next);
+ *
+ * Resulting list order:
+ * list_item_0 -> elem_item_0 -> elem_item_1 ... -> list_item_1 -> ...
+ *
+ * @param entry An entry (or list) to append to the list
+ * @param list The list to insert to. This list must be a valid list, not
+ * NULL.
+ * @param type The list type
+ * @param member Member name of the field pointing to next struct
+ */
+#define nt_list_insert(_entry, _list, _type, _member)			\
+    do {								\
+	nt_list_append((_list)->_member, _entry, _type, _member);	\
+	(_list)->_member = _entry;					\
+    } while (0)
+
+/**
+ * Delete the entry from the list by iterating through the list and
+ * removing any references from the list to the entry.
+ *
+ * Example:
+ * struct foo *elem = <assing to right element>
+ * nt_list_del(elem, list, struct foo, next);
+ *
+ * @param entry The entry to delete from the list. entry is always
+ * re-ininitialized as a null-terminated list.
+ * @param list The list containing the entry, set to the new list without
+ * the removed entry.
+ * @param type The list type
+ * @param member Member name of the field pointing to the next entry
+ */
+#define nt_list_del(_entry, _list, _type, _member)		\
+	do {							\
+		_type *__e = _entry;				\
+		if (__e == NULL) break;				\
+		if ((_list) == __e) {				\
+		    _list = __e->_member;			\
+		} else {					\
+		    _type *__prev = _list;			\
+		    while (__prev->_member && __prev->_member != __e)	\
+			__prev = nt_list_next(__prev, _member);	\
+		    if (__prev->_member)			\
+			__prev->_member = __e->_member;		\
+		}						\
+		nt_list_init(__e, _member);			\
+	} while(0)
+
 #endif
diff --git a/test/list.c b/test/list.c
index b101c76..bee968c 100644
--- a/test/list.c
+++ b/test/list.c
@@ -29,6 +29,7 @@
 #include <list.h>
 #include <string.h>
 #include <assert.h>
+#include <stdlib.h>
 
 struct parent {
     int a;
@@ -161,6 +162,164 @@ test_list_for_each(void)
     }
 }
 
+struct foo {
+    char a;
+    struct foo *next;
+    char b;
+};
+
+static void
+test_nt_list_init(void)
+{
+    struct foo foo;
+
+    foo.a = 10;
+    foo.b = 20;
+    nt_list_init(&foo, next);
+
+    assert(foo.a == 10);
+    assert(foo.b == 20);
+    assert(foo.next == NULL);
+    assert(nt_list_next(&foo, next) == NULL);
+}
+
+static void
+test_nt_list_append(void)
+{
+    int i = 1;
+    struct foo *foo = calloc(10, sizeof(struct foo));
+    struct foo *item;
+
+    for (item = foo, i = 1; i <= 10; i++, item++)
+    {
+	item->a = i;
+	item->b = i * 2;
+	nt_list_init(item, next);
+
+	if (item != foo)
+	    nt_list_append(item, foo, struct foo, next);
+    }
+
+    /* Test using nt_list_next */
+    for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next))
+    {
+	assert(item->a = i);
+	assert(item->b = i * 2);
+    }
+
+    /* Test using nt_list_for_each_entry */
+    i = 1;
+    nt_list_for_each_entry(item, foo, next) {
+	assert(item->a = i);
+	assert(item->b = i * 2);
+	i++;
+    }
+    assert(i == 11);
+}
+
+static void
+test_nt_list_insert(void)
+{
+    int i = 1;
+    struct foo *foo = calloc(10, sizeof(struct foo));
+    struct foo *item;
+
+    foo->a = 10;
+    foo->b = 20;
+    nt_list_init(foo, next);
+
+    for (item = &foo[1], i = 9; i > 0; i--, item++)
+    {
+	item->a = i;
+	item->b = i * 2;
+	nt_list_init(item, next);
+	nt_list_insert(item, foo, struct foo, next);
+    }
+
+    /* Test using nt_list_next */
+    for (item = foo, i = 10; i > 0; i--, item = nt_list_next(item, next))
+    {
+	assert(item->a = i);
+	assert(item->b = i * 2);
+    }
+
+    /* Test using nt_list_for_each_entry */
+    i = 1;
+    nt_list_for_each_entry(item, foo, next) {
+	assert(item->a = i);
+	assert(item->b = i * 2);
+	i++;
+    }
+    assert(i == 11);
+}
+
+static void
+test_nt_list_delete(void)
+{
+    int i = 1;
+    struct foo *list = calloc(10, sizeof(struct foo));
+    struct foo *foo = list;
+    struct foo *item, *tmp;
+    struct foo *empty_list = foo;
+
+    nt_list_init(empty_list, next);
+    nt_list_del(empty_list, empty_list, struct foo, next);
+    assert(!empty_list);
+
+    for (item = foo, i = 1; i <= 10; i++, item++)
+    {
+	item->a = i;
+	item->b = i * 2;
+	nt_list_init(item, next);
+
+	if (item != foo)
+	    nt_list_append(item, foo, struct foo, next);
+    }
+
+    i = 0;
+    nt_list_for_each_entry(item, foo, next) {
+	i++;
+    }
+    assert(i == 10);
+
+    /* delete last item */
+    nt_list_del(&foo[9], foo, struct foo, next);
+    i = 0;
+    nt_list_for_each_entry(item, foo, next) {
+	assert(item->a != 10); /* element 10 is gone now */
+	i++;
+    }
+    assert(i == 9); /* 9 elements left */
+
+    /* delete second item */
+    nt_list_del(foo->next, foo, struct foo, next);
+    assert(foo->next->a == 3);
+
+    i = 0;
+    nt_list_for_each_entry(item, foo, next) {
+	assert(item->a != 10); /* element 10 is gone now */
+	assert(item->a != 2); /* element 2 is gone now */
+	i++;
+    }
+    assert(i == 8); /* 9 elements left */
+
+    item = foo;
+    /* delete first item */
+    nt_list_del(foo, foo, struct foo, next);
+    assert(item != foo);
+    assert(item->next == NULL);
+    assert(foo->a == 3);
+    assert(foo->next->a == 4);
+
+    nt_list_for_each_entry_safe(item, tmp, foo, next) {
+	nt_list_del(item, foo, struct foo, next);
+    }
+
+    assert(!foo);
+    assert(!item);
+
+    free(list);
+}
 
 int main(int argc, char** argv)
 {
@@ -169,5 +328,10 @@ int main(int argc, char** argv)
     test_list_del();
     test_list_for_each();
 
+    test_nt_list_init();
+    test_nt_list_append();
+    test_nt_list_insert();
+    test_nt_list_delete();
+
     return 0;
 }
-- 
1.7.6