summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorVito Caputo <vcaputo@pengaru.com>2019-05-07 17:13:21 -0700
committerVito Caputo <vcaputo@pengaru.com>2019-05-07 17:13:21 -0700
commit2281dcf6f29f940499e6cccb8b4e54f59daa2efe (patch)
tree42d145091b90631cb7356129a021ee31e1581d98
dll: initial commit of a doubly linked list header
Looking to retire using the kernel's list.h, this is a minimal fast and nasty implementation I've barely tested to fulfill my immediate needs.
-rw-r--r--dll.h136
-rw-r--r--test.c79
2 files changed, 215 insertions, 0 deletions
diff --git a/dll.h b/dll.h
new file mode 100644
index 0000000..19556d0
--- /dev/null
+++ b/dll.h
@@ -0,0 +1,136 @@
+/*
+ * Copyright (C) 2019 - Vito Caputo - <vcaputo@pengaru.com>
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 3 as published
+ * by the Free Software Foundation.
+ *
+ * This program 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/>.
+ */
+
+/* (circular) Doubly-Linked List header */
+
+/* I've been using the Linux kernel's list.h for ages, so it definitely
+ * takes some inspiration from that API.
+ */
+
+#ifndef _DLL_H
+#define _DLL_H
+
+
+#include <stddef.h> /* offsetof() */
+
+
+typedef struct dll_t dll_t;
+
+struct dll_t {
+ dll_t *next, *previous;
+};
+
+
+/* This is analagous to container_of */
+#define DLL_ENTRY(_ptr, _type, _member) \
+ (_type *)((char *)(_ptr) - offsetof(_type, _member))
+
+
+/* Declare and initialize an empty list named _name */
+#define DLL_INIT(_name) \
+ dll_t _name = { .next = &_name, .previous = &_name }
+
+
+/* Iterate list */
+#define DLL_FOR_EACH(_head, _node) \
+ for ( (_node) = (_head)->next; \
+ (_node) != (_head); \
+ (_node) = (_node)->next \
+ )
+
+
+/* Iterate list in a removal-safe fashion */
+#define DLL_FOR_EACH_SAFE(_head, _node, _next) \
+ for ( (_node) = (_head)->next, (_next) = (_node)->next; \
+ (_node) != (_head); \
+ (_node) = (_next), (_next) = (_next->next) \
+ )
+
+
+/* Iterate list as containers */
+#define DLL_FOR_EACH_ENTRY(_head, _entry, _type, _member) \
+ for ( (_entry) = DLL_ENTRY((_head)->next, _type, _member); \
+ &(_entry)->_member != (_head); \
+ (_entry) = DLL_ENTRY((_entry)->_member.next, _type, _member) \
+ )
+
+
+/* Iterate list as containers in a removal-safe fashion */
+#define DLL_FOR_EACH_ENTRY_SAFE(_head, _entry, _next, _type, _member) \
+ for ( (_entry) = DLL_ENTRY((_head)->next, _type, _member), \
+ (_next) = DLL_ENTRY((_entry)->_member.next, _type, _member); \
+ &(_entry)->_member != (_head); \
+ (_entry) = (_next), \
+ (_next) = DLL_ENTRY((_next)->_member.next, _type, _member) \
+ )
+
+
+/* Initialize node to an empty list state,
+ * node is returned for convenience.
+ */
+static inline dll_t * dll_init(dll_t *node)
+{
+ return node->next = node->previous = node;
+}
+
+
+/* Delete node from the list it belongs to,
+ * node is returned for convenience.
+ */
+static inline dll_t * dll_del(dll_t *node)
+{
+ node->next->previous = node->previous;
+ node->previous->next = node->next;
+
+ return dll_init(node);
+}
+
+
+/* Insert node immediately before where,
+ * node is returned for convenience.
+ */
+static inline dll_t * dll_pre(dll_t *where, dll_t *node)
+{
+ node->next = where;
+ node->previous = where->previous;
+ where->previous->next = node;
+ where->previous = node;
+
+ return node;
+}
+
+
+/* Append node immediately after where,
+ * node is returned for convenience.
+ */
+static inline dll_t * dll_post(dll_t *where, dll_t *node)
+{
+ node->next = where->next;
+ node->previous = where;
+ where->next->previous = node;
+ where->next = node;
+
+ return node;
+}
+
+
+static inline int dll_empty(dll_t *dll)
+{
+ return (dll->next == dll && dll->next == dll->previous);
+}
+
+
+#endif
diff --git a/test.c b/test.c
new file mode 100644
index 0000000..6e3ccd6
--- /dev/null
+++ b/test.c
@@ -0,0 +1,79 @@
+#include <assert.h>
+#include <stdio.h>
+
+#include "dll.h"
+
+#define NUM_NODES 100
+
+DLL_INIT(foo);
+
+typedef struct entry_t {
+ dll_t node;
+ int id;
+} entry_t;
+
+
+int main(int argc, char *argv[])
+{
+ entry_t entries[NUM_NODES], *entry, *_entry;
+ dll_t nodes[NUM_NODES];
+ dll_t *tmp, *_tmp;
+
+ for (int i = 0; i < NUM_NODES; i++) {
+ dll_pre(&foo, &nodes[i]);
+ printf("appended %i:%p to tail\n", i, &nodes[i]);
+ }
+
+ DLL_FOR_EACH(&foo, tmp)
+ printf("node=%p\n", tmp);
+
+ for (int i = 0; i < NUM_NODES; i++) {
+ if (!(i % 2))
+ continue;
+
+ printf("deleted %i:%p\n", i, dll_del(&nodes[i]));
+ }
+
+ DLL_FOR_EACH(&foo, tmp)
+ printf("node=%p\n", tmp);
+
+ assert(!dll_empty(&foo));
+
+ DLL_FOR_EACH_SAFE(&foo, tmp, _tmp)
+ printf("deleted %p\n", dll_del(tmp));
+
+ DLL_FOR_EACH(&foo, tmp)
+ printf("!!!notempty!!! node=%p\n", tmp);
+
+ assert(dll_empty(&foo));
+
+ for (int i = 0; i < NUM_NODES; i++) {
+ dll_pre(&foo, &entries[i].node);
+ entries[i].id = i;
+ }
+
+ DLL_FOR_EACH_ENTRY(&foo, entry, entry_t, node) {
+ printf("id=%i entry=%p node=%p\n",
+ entry->id, entry, &entry->node);
+ }
+
+ for (int i = 0; i < NUM_NODES; i++) {
+ if (!(i % 2))
+ continue;
+
+ printf("deleted %i:%p\n", i, dll_del(&entries[i].node));
+ }
+
+ DLL_FOR_EACH_ENTRY(&foo, entry, entry_t, node) {
+ printf("id=%i entry=%p node=%p\n",
+ entry->id, entry, &entry->node);
+ }
+
+ DLL_FOR_EACH_ENTRY_SAFE(&foo, entry, _entry, entry_t, node)
+ printf("deleted %p\n", dll_del(&entry->node));
+
+ DLL_FOR_EACH_ENTRY(&foo, entry, entry_t, node)
+ printf("!!!notempty!!! entry=%p\n", entry);
+
+ assert(dll_empty(&foo));
+}
© 2021 All Rights Reserved