Add some linked list primitives.

This adds basic linked list structures, initializers, and iterators. Signed-off-by: Peter Jones <pjones@redhat.com>
rhboot · Feb 13, 2021 · 94ad063 · 94ad063
1 parent be0612c
commit 94ad063
Show file tree

Hide file tree

Showing 3 changed files with 105 additions and 0 deletions.
diff --git a/.clang-format b/.clang-format
@@ -68,6 +68,10 @@ FixNamespaceComments: true
 ForEachMacros:
   - certlist_for_each_certentry
   - certentry_for_each_cert
+  - list_for_each
+  - list_for_each_safe
+  - list_for_each_prev
+  - list_for_each_prev_safe
 IncludeBlocks:   Preserve
 IncludeCategories:
   - Regex:           '.*'

diff --git a/include/list.h b/include/list.h
@@ -0,0 +1,100 @@
+// SPDX-License-Identifier: BSD-2-Clause-Patent
+/*
+ * list.h - simple list primitives
+ */
+
+#ifndef LIST_H_
+#define LIST_H_
+
+#define container_of(ptr, type, member)                      \
+	({                                                   \
+		void *__mptr = (void *)(ptr);                \
+		((type *)(__mptr - offsetof(type, member))); \
+	})
+
+struct list_head {
+	struct list_head *next;
+	struct list_head *prev;
+};
+
+typedef struct list_head list_t;
+
+#define LIST_HEAD_INIT(name)                     \
+	{                                        \
+		.next = &(name), .prev = &(name) \
+	}
+
+#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
+
+#define INIT_LIST_HEAD(ptr)          \
+	({                           \
+		(ptr)->next = (ptr); \
+		(ptr)->prev = (ptr); \
+	})
+
+static inline void
+__list_add(struct list_head *new, struct list_head *prev,
+           struct list_head *next)
+{
+	next->prev = new;
+	new->next = next;
+	new->prev = prev;
+	prev->next = new;
+}
+
+static inline void
+list_add(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head, head->next);
+}
+
+static inline void
+list_add_tail(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head->prev, head);
+}
+
+static inline void
+__list_del(struct list_head *prev, struct list_head *next)
+{
+	next->prev = prev;
+	prev->next = next;
+}
+
+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(entry);
+	entry->next = NULL;
+	entry->prev = NULL;
+}
+
+#define list_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define list_first_entry(ptr, type, member) \
+	list_entry((ptr)->next, type, member)
+
+#define list_last_entry(ptr, type, member) list_entry((ptr)->prev, type, member)
+
+#define list_for_each(pos, head) \
+	for (pos = (head)->next; pos != (head); pos = pos->next)
+
+#define list_for_each_safe(pos, n, head)                       \
+	for (pos = (head)->next, n = pos->next; pos != (head); \
+	     pos = n, n = pos->next)
+
+#define list_for_each_prev(pos, head) \
+	for (pos = (head)->prev; pos != (head); pos = pos->prev)
+
+#define list_for_each_prev_safe(pos, n, head)                  \
+	for (pos = (head)->prev, n = pos->prev; pos != (head); \
+	     pos = n, n = pos->prev)
+
+#endif /* !LIST_H_ */
+// vim:fenc=utf-8:tw=75:noet
diff --git a/shim.h b/shim.h
@@ -122,6 +122,7 @@
 
 #include "include/asm.h"
 #include "include/compiler.h"
+#include "include/list.h"
 #include "include/configtable.h"
 #include "include/console.h"
 #include "include/crypt_blowfish.h"