slist: new module

3 files changed, 844 insertions, 0 deletions

diff --git a/Makefile.am b/Makefile.am
index 0835ada..e44c5a0 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -1,6 +1,7 @@
 EXTRA_DIST =
 MOSTLYCLEANFILES =
 
+# TODO Remove tabs
 AM_CPPFLAGS = \
 	-pipe \
 	-std=gnu11 \
@@ -41,6 +42,7 @@ librbraun_la_SOURCES = \
 	rdxtree.c \
 	rdxtree.h \
 	rdxtree_i.h \
+	slist.h \
 	shell.c \
 	shell.h \
 	x86/atomic.h \
@@ -54,6 +56,7 @@ bin_PROGRAMS = \
 	test_fmt_sprintf \
 	test_fmt_sscanf \
 	test_plist \
+	test_slist \
 	test_rbtree \
 	test_rdxtree \
 	test_shell
@@ -73,6 +76,9 @@ test_fmt_sscanf_LDADD = librbraun.la
 test_plist_SOURCES = test/test_plist.c
 test_plist_LDADD = librbraun.la
 
+test_slist_SOURCES = test/test_slist.c
+test_slist_LDADD = librbraun.la
+
 test_rbtree_SOURCES = test/test_rbtree.c
 test_rbtree_LDADD = librbraun.la
 
diff --git a/slist.h b/slist.h
new file mode 100644
index 0000000..622dfc1
--- /dev/null
+++ b/slist.h
@@ -0,0 +1,490 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ *
+ * Singly-linked list.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#ifndef _SLIST_H
+#define _SLIST_H
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "macros.h"
+
+/*
+ * List node.
+ */
+struct slist_node {
+    struct slist_node *next;
+};
+
+/*
+ * List head.
+ */
+struct slist {
+    struct slist_node *first;
+    struct slist_node *last;
+};
+
+/*
+ * Static list initializer.
+ */
+#define SLIST_INITIALIZER(list) { NULL, NULL }
+
+/*
+ * Initialize a list.
+ */
+static inline void
+slist_init(struct slist *list)
+{
+    list->first = NULL;
+    list->last = NULL;
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define slist_entry(node, type, member) structof(node, type, member)
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct slist_node *
+slist_first(const struct slist *list)
+{
+    return list->first;
+}
+
+/*
+ * Return the last node of a list.
+ */
+static inline struct slist_node *
+slist_last(const struct slist *list)
+{
+    return list->last;
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct slist_node *
+slist_next(const struct slist_node *node)
+{
+    return node->next;
+}
+
+/*
+ * Get the first entry of a list.
+ */
+#define slist_first_entry(list, type, member)                           \
+MACRO_BEGIN                                                             \
+    struct slist_node *___first;                                        \
+                                                                        \
+    ___first = (list)->first;                                           \
+    slist_end(___first) ? NULL : slist_entry(___first, type, member);   \
+MACRO_END
+
+/*
+ * Get the last entry of a list.
+ */
+#define slist_last_entry(list, type, member)                            \
+MACRO_BEGIN                                                             \
+    struct slist_node *___last;                                         \
+                                                                        \
+    ___last = (list)->last;                                             \
+    slist_end(___last) ? NULL : slist_entry(___last, type, member);     \
+MACRO_END
+
+/*
+ * Get the entry next to the given entry.
+ */
+#define slist_next_entry(entry, member) \
+MACRO_BEGIN                                                             \
+    struct slist_node *___next;                                         \
+                                                                        \
+    ___next = (entry)->member.next;                                     \
+    slist_end(___next)                                                  \
+        ? NULL                                                          \
+        : slist_entry(___next, typeof(*entry), member);                 \
+MACRO_END
+
+/*
+ * Return true if node is invalid and denotes the end of the list.
+ */
+static inline bool
+slist_end(const struct slist_node *node)
+{
+    return node == NULL;
+}
+
+/*
+ * Return true if list is empty.
+ */
+static inline bool
+slist_empty(const struct slist *list)
+{
+    return list->first == NULL;
+}
+
+/*
+ * Return true if list contains exactly one node.
+ */
+static inline bool
+slist_singular(const struct slist *list)
+{
+    return !slist_empty(list) && (list->first == list->last);
+}
+
+/*
+ * Append the nodes of list2 at the end of list1.
+ *
+ * After completion, list2 is stale.
+ */
+static inline void
+slist_concat(struct slist *list1, const struct slist *list2)
+{
+    if (slist_empty(list2)) {
+        return;
+    }
+
+    if (slist_empty(list1)) {
+        list1->first = list2->first;
+    } else {
+        list1->last->next = list2->first;
+    }
+
+    list1->last = list2->last;
+}
+
+/*
+ * Set the new head of a list.
+ *
+ * This function is an optimized version of :
+ * list_init(&new_list);
+ * list_concat(&new_list, &old_list);
+ */
+static inline void
+slist_set_head(struct slist *new_head, const struct slist *old_head)
+{
+    *new_head = *old_head;
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+slist_insert_head(struct slist *list, struct slist_node *node)
+{
+    if (slist_empty(list)) {
+        list->last = node;
+    }
+
+    node->next = list->first;
+    list->first = node;
+}
+
+/*
+ * Insert a node at the tail of a list.
+ */
+static inline void
+slist_insert_tail(struct slist *list, struct slist_node *node)
+{
+    node->next = NULL;
+
+    if (slist_empty(list)) {
+        list->first = node;
+    } else {
+        list->last->next = node;
+    }
+
+    list->last = node;
+}
+
+/*
+ * Insert a node after another node.
+ *
+ * The prev argument is used to determine the insertion point. It may safely
+ * denote the end of the given list, in which case the node is inserted at
+ * the head of the list.
+ */
+static inline void
+slist_insert_after(struct slist *list, struct slist_node *prev,
+                   struct slist_node *node)
+{
+    if (slist_end(prev)) {
+        slist_insert_head(list, node);
+        return;
+    }
+
+    node->next = prev->next;
+    prev->next = node;
+
+    if (list->last == prev) {
+        list->last = node;
+    }
+}
+
+/*
+ * Remove a node from a list.
+ *
+ * The prev argument must point to the node immediately preceding the target
+ * node. It may safely denote the end of the given list, in which case the
+ * first node is removed.
+ */
+static inline void
+slist_remove(struct slist *list, struct slist_node *prev)
+{
+    struct slist_node *node;
+
+    if (slist_end(prev)) {
+        node = list->first;
+        list->first = node->next;
+
+        if (list->last == node) {
+            list->last = NULL;
+        }
+    } else {
+        node = prev->next;
+        prev->next = node->next;
+
+        if (list->last == node) {
+            list->last = prev;
+        }
+    }
+}
+
+/*
+ * Forge a loop to process all nodes of a list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define slist_for_each(list, node)  \
+for (node = slist_first(list);      \
+     !slist_end(node);              \
+     node = slist_next(node))
+
+/*
+ * Forge a loop to process all nodes of a list.
+ */
+#define slist_for_each_safe(list, node, tmp)            \
+for (node = slist_first(list),                          \
+     tmp = slist_end(node) ? NULL : slist_next(node);   \
+     !slist_end(node);                                  \
+     node = tmp,                                        \
+     tmp = slist_end(node) ? NULL : slist_next(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define slist_for_each_entry(list, entry, member)               \
+for (entry = slist_first_entry(list, typeof(*entry), member);   \
+     entry != NULL;                                             \
+     entry = slist_next_entry(entry, member))
+
+/*
+ * Forge a loop to process all entries of a list.
+ */
+#define slist_for_each_entry_safe(list, entry, tmp, member)             \
+for (entry = slist_first_entry(list, typeof(*entry), member),           \
+     tmp = (entry == NULL) ? NULL : slist_next_entry(entry, member);    \
+     entry != NULL;                                                     \
+     entry = tmp,                                                       \
+     tmp = (entry == NULL) ? NULL : slist_next_entry(entry, member))    \
+
+/*
+ * Lockless variants
+ *
+ * The slist_end() function may be used from read-side critical sections.
+ */
+
+/*
+ * These macros can be replaced by actual functions in an environment
+ * that provides lockless synchronization such as RCU.
+ */
+#define llsync_assign_ptr(ptr, value)   ((ptr) = (value))
+#define llsync_read_ptr(ptr)            (ptr)
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define slist_llsync_entry(node, type, member) \
+    structof(llsync_read_ptr(node), type, member)
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct slist_node *
+slist_llsync_first(const struct slist *list)
+{
+    return llsync_read_ptr(list->first);
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct slist_node *
+slist_llsync_next(const struct slist_node *node)
+{
+    return llsync_read_ptr(node->next);
+}
+
+/*
+ * Get the first entry of a list.
+ */
+#define slist_llsync_first_entry(list, type, member)                    \
+MACRO_BEGIN                                                             \
+    struct slist_node *___first;                                        \
+                                                                        \
+    ___first = slist_llsync_first(list);                                \
+    slist_end(___first) ? NULL : slist_entry(___first, type, member);   \
+MACRO_END
+
+/*
+ * Get the entry next to the given entry.
+ */
+#define slist_llsync_next_entry(entry, member)                          \
+MACRO_BEGIN                                                             \
+    struct slist_node *___next;                                         \
+                                                                        \
+    ___next = slist_llsync_next(&entry->member);                        \
+    slist_end(___next)                                                  \
+        ? NULL                                                          \
+        : slist_entry(___next, typeof(*entry), member);                 \
+MACRO_END
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+slist_llsync_insert_head(struct slist *list, struct slist_node *node)
+{
+    if (slist_empty(list)) {
+        list->last = node;
+    }
+
+    node->next = list->first;
+    llsync_assign_ptr(list->first, node);
+}
+
+/*
+ * Insert a node at the tail of a list.
+ */
+static inline void
+slist_llsync_insert_tail(struct slist *list, struct slist_node *node)
+{
+    node->next = NULL;
+
+    if (slist_empty(list)) {
+        llsync_assign_ptr(list->first, node);
+    } else {
+        llsync_assign_ptr(list->last->next, node);
+    }
+
+    list->last = node;
+}
+
+/*
+ * Insert a node after another node.
+ *
+ * The prev argument is used to determine the insertion point. It may safely
+ * denote the end of the given list, in which case the node is inserted at
+ * the head of the list.
+ */
+static inline void
+slist_llsync_insert_after(struct slist *list, struct slist_node *prev,
+                          struct slist_node *node)
+{
+    if (slist_end(prev)) {
+        slist_llsync_insert_head(list, node);
+        return;
+    }
+
+    node->next = prev->next;
+    llsync_assign_ptr(prev->next, node);
+
+    if (list->last == prev) {
+        list->last = node;
+    }
+}
+
+/*
+ * Remove a node from a list.
+ *
+ * The prev argument must point to the node immediately preceding the target
+ * node. It may safely denote the end of the given list, in which case the
+ * first node is removed.
+ */
+static inline void
+slist_llsync_remove(struct slist *list, struct slist_node *prev)
+{
+    struct slist_node *node;
+
+    if (slist_end(prev)) {
+        node = list->first;
+        llsync_assign_ptr(list->first, node->next);
+
+        if (list->last == node) {
+            list->last = NULL;
+        }
+    } else {
+        node = prev->next;
+        llsync_assign_ptr(prev->next, node->next);
+
+        if (list->last == node) {
+            list->last = prev;
+        }
+    }
+}
+
+/*
+ * Forge a loop to process all nodes of a list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define slist_llsync_for_each(list, node)   \
+for (node = slist_llsync_first(list);       \
+     !slist_end(node);                      \
+     node = slist_llsync_next(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define slist_llsync_for_each_entry(list, entry, member)                \
+for (entry = slist_llsync_first_entry(list, typeof(*entry), member);    \
+     entry != NULL;                                                     \
+     entry = slist_llsync_next_entry(entry, member))
+
+#endif /* _SLIST_H */
diff --git a/test/test_slist.c b/test/test_slist.c
new file mode 100644
index 0000000..941b80f
--- /dev/null
+++ b/test/test_slist.c
@@ -0,0 +1,348 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "../check.h"
+#include "../macros.h"
+#include "../slist.h"
+
+struct obj {
+    struct slist_node node;
+};
+
+static struct obj *
+obj_create(void)
+{
+    return malloc(sizeof(struct obj));
+}
+
+static void
+obj_destroy(struct obj *obj)
+{
+    free(obj);
+}
+
+static void
+add_obj_head(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = obj_create();
+    slist_insert_head(list, &obj->node);
+}
+
+static void
+add_obj_head_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = obj_create();
+    slist_llsync_insert_head(list, &obj->node);
+}
+
+static void
+add_obj_head2(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = obj_create();
+    slist_insert_after(list, NULL, &obj->node);
+}
+
+static void
+add_obj_head2_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = obj_create();
+    slist_llsync_insert_after(list, NULL, &obj->node);
+}
+
+static void
+add_obj_tail(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = obj_create();
+    slist_insert_tail(list, &obj->node);
+}
+
+static void
+add_obj_tail_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = obj_create();
+    slist_llsync_insert_tail(list, &obj->node);
+}
+
+static void
+add_obj_tail2(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = obj_create();
+    slist_insert_after(list, slist_last(list), &obj->node);
+}
+
+static void
+add_obj_tail2_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = obj_create();
+    slist_llsync_insert_after(list, slist_last(list), &obj->node);
+}
+
+static void
+add_obj_second(struct slist *list)
+{
+    struct slist_node *first;
+    struct obj *obj;
+
+    obj = obj_create();
+    first = slist_first(list);
+    slist_insert_after(list, first, &obj->node);
+}
+
+static void
+del_obj_head(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = slist_first_entry(list, struct obj, node);
+    slist_remove(list, NULL);
+    obj_destroy(obj);
+}
+
+static void
+del_obj_head_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = slist_first_entry(list, struct obj, node);
+    slist_llsync_remove(list, NULL);
+    obj_destroy(obj);
+}
+
+static void
+del_obj_tail(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = slist_last_entry(list, struct obj, node);
+    slist_remove(list, slist_first(list));
+    obj_destroy(obj);
+}
+
+static void
+del_obj_tail_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = slist_last_entry(list, struct obj, node);
+    slist_llsync_remove(list, slist_first(list));
+    obj_destroy(obj);
+}
+
+static void
+del_obj_second(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = slist_entry(slist_next(slist_first(list)), struct obj, node);
+    slist_remove(list, slist_first(list));
+    obj_destroy(obj);
+}
+
+static void
+del_obj_second_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    obj = slist_entry(slist_next(slist_first(list)), struct obj, node);
+    slist_llsync_remove(list, slist_first(list));
+    obj_destroy(obj);
+}
+
+static void
+walk_all_objs1(struct slist *list)
+{
+    struct slist_node *node;
+
+    slist_for_each(list, node);
+}
+
+static void
+walk_all_objs1_llsync(struct slist *list)
+{
+    struct slist_node *node;
+
+    slist_llsync_for_each(list, node);
+}
+
+static void
+walk_all_objs2(struct slist *list)
+{
+    struct slist_node *node, *tmp;
+
+    slist_for_each_safe(list, node, tmp);
+}
+
+static void
+walk_all_objs3(struct slist *list)
+{
+    struct obj *obj;
+
+    slist_for_each_entry(list, obj, node);
+}
+
+static void
+walk_all_objs3_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    slist_llsync_for_each_entry(list, obj, node);
+}
+
+static void
+walk_all_objs4(struct slist *list)
+{
+    struct obj *obj, *tmp;
+
+    slist_for_each_entry_safe(list, obj, tmp, node);
+}
+
+static void
+del_all_objs(struct slist *list)
+{
+    struct obj *obj;
+
+    while (!slist_empty(list)) {
+        obj = slist_first_entry(list, struct obj, node);
+        slist_remove(list, NULL);
+        obj_destroy(obj);
+    }
+}
+
+static void
+del_all_objs_llsync(struct slist *list)
+{
+    struct obj *obj;
+
+    while (!slist_empty(list)) {
+        obj = slist_first_entry(list, struct obj, node);
+        slist_llsync_remove(list, NULL);
+        obj_destroy(obj);
+    }
+}
+
+int
+main(void)
+{
+    struct slist list, list2;
+
+    slist_init(&list);
+    slist_init(&list2);
+
+    check(!slist_llsync_first_entry(&list, struct obj, node));
+
+    add_obj_head(&list);
+    check(slist_llsync_first_entry(&list, struct obj, node));
+    check(slist_singular(&list));
+    del_all_objs(&list);
+
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    del_obj_tail(&list);
+    add_obj_tail(&list);
+    del_obj_tail_llsync(&list);
+
+    slist_concat(&list, &list2);
+    slist_set_head(&list2, &list);
+    slist_init(&list);
+    slist_concat(&list, &list2);
+    slist_init(&list2);
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    add_obj_tail(&list2);
+    add_obj_tail(&list2);
+    slist_concat(&list, &list2);
+
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    add_obj_head(&list);
+    add_obj_head(&list);
+
+    del_all_objs(&list);
+    slist_init(&list);
+
+    add_obj_head(&list);
+    add_obj_head_llsync(&list);
+    slist_init(&list2);
+    add_obj_head_llsync(&list2);
+    del_all_objs(&list2);
+    add_obj_head(&list);
+    add_obj_head(&list);
+    add_obj_tail(&list);
+    add_obj_tail_llsync(&list);
+    slist_init(&list2);
+    add_obj_tail_llsync(&list2);
+    del_all_objs(&list2);
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    add_obj_tail(&list);
+    add_obj_head(&list);
+    add_obj_head(&list);
+    add_obj_head(&list);
+    add_obj_head2(&list);
+    add_obj_head2_llsync(&list);
+    add_obj_tail2(&list);
+    add_obj_tail2_llsync(&list);
+
+    walk_all_objs1(&list);
+    walk_all_objs2(&list);
+    walk_all_objs3(&list);
+    walk_all_objs4(&list);
+    walk_all_objs1_llsync(&list);
+    walk_all_objs3_llsync(&list);
+
+    del_obj_head(&list);
+    del_obj_head_llsync(&list);
+    del_obj_second(&list);
+    del_obj_second_llsync(&list);
+    add_obj_second(&list);
+
+    del_all_objs_llsync(&list);
+
+    return 0;
+}