changeset 20687:ac1492488560 draft

ilist: add generic circular doubly-linked list with a sentinel node
author Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
date Sun, 22 Mar 2020 10:48:20 -0400
parents 11a2d819935f
children 302d3c7312e1
files include/sys/Makefile include/sys/ilist.h include/sys/list_impl.h usr/src/pkg/manifests/system-header.mf
diffstat 4 files changed, 163 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- a/include/sys/Makefile	Fri Mar 10 18:57:44 2017 -0500
+++ b/include/sys/Makefile	Sun Mar 22 10:48:20 2020 -0400
@@ -232,6 +232,7 @@
 	idmap.h 		\
 	ieeefp.h		\
 	id_space.h		\
+	ilist.h			\
 	instance.h		\
 	int_const.h		\
 	int_fmtio.h		\
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/include/sys/ilist.h	Sun Mar 22 10:48:20 2020 -0400
@@ -0,0 +1,160 @@
+/*
+ * Copyright 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef _SYS_ILIST_H
+#define _SYS_ILIST_H
+
+/*
+ * Generic circular doubly-linked list with a sentinel node.
+ *
+ * The entire implementation is here as C99 static inline functions.  We
+ * hide them if we are not using a C99 compiler to expose the list_node
+ * struct for list.h's benefit.
+ *
+ * Here's the summary of differences:
+ *
+ * (1) both ilist.h and list.h use the same struct list_node
+ * (1) ilist.h uses static inlines while list.h uses normal functions
+ * (2) list.h uses struct list to keep track of offsets into objects for the
+ *     struct list_node
+ * (3) ilist.h uses struct list_head as a sentinel node and has no idea
+ *     about the structures containing each of the list entries
+ */
+
+#ifdef	__cplusplus
+extern "C" {
+#endif
+
+struct list_node {
+	struct list_node *list_next;
+	struct list_node *list_prev;
+};
+
+#ifdef _STDC_C99
+
+#include <sys/null.h>
+
+static inline void ilist_init(struct list_node *node)
+{
+	node->list_next = node;
+	node->list_prev = node;
+}
+
+static inline int ilist_is_empty(struct list_node *list)
+{
+	return list->list_next == list;
+}
+
+static int ilist_link_active(struct list_node *node)
+{
+	return node->list_next != NULL;
+}
+
+static inline struct list_node *ilist_head(struct list_node *list)
+{
+	if (ilist_is_empty(list))
+		return NULL;
+
+	return list->list_next;
+}
+
+static inline struct list_node *ilist_tail(struct list_node *list)
+{
+	if (ilist_is_empty(list))
+		return NULL;
+
+	return list->list_prev;
+}
+
+static inline struct list_node *ilist_next(struct list_node *list,
+					   struct list_node *cur)
+{
+	if (cur->list_next == list)
+		return NULL;
+
+	return cur->list_next;
+}
+
+static inline struct list_node *ilist_prev(struct list_node *list,
+					   struct list_node *cur)
+{
+	if (cur->list_prev == list)
+		return NULL;
+
+	return cur->list_prev;
+}
+
+static inline void __ilist_insert(struct list_node *before,
+				  struct list_node *after,
+				  struct list_node *newnode)
+{
+	before->list_next = newnode;
+	newnode->list_prev = before;
+	newnode->list_next = after;
+	after->list_prev = newnode;
+}
+
+static inline void ilist_insert_after(struct list_node *reference,
+				      struct list_node *newnode)
+{
+	__ilist_insert(reference, reference->list_next, newnode);
+}
+
+static inline void ilist_insert_before(struct list_node *reference,
+				       struct list_node *newnode)
+{
+	__ilist_insert(reference->list_prev, reference, newnode);
+}
+
+#define ilist_insert_head(list, newnode) ilist_insert_after((list), (newnode))
+#define ilist_insert_tail(list, newnode) ilist_insert_before((list), (newnode))
+
+static inline void ilist_remove(struct list_node *node)
+{
+	node->list_prev->list_next = node->list_next;
+	node->list_next->list_prev = node->list_prev;
+
+	node->list_prev = NULL;
+	node->list_next = NULL;
+}
+
+static inline struct list_node *__ilist_remove(struct list_node *list,
+					       struct list_node *node)
+{
+	if (ilist_is_empty(list))
+		return NULL;
+
+	ilist_remove(node);
+	return node;
+}
+
+static inline struct list_node *ilist_remove_head(struct list_node *list)
+{
+	return __ilist_remove(list, list->list_next);
+}
+
+static inline struct list_node *ilist_remove_tail(struct list_node *list)
+{
+	return __ilist_remove(list, list->list_prev);
+}
+
+#endif
+
+#ifdef	__cplusplus
+}
+#endif
+
+#endif	/* _SYS_ILIST_H */
--- a/include/sys/list_impl.h	Fri Mar 10 18:57:44 2017 -0500
+++ b/include/sys/list_impl.h	Sun Mar 22 10:48:20 2020 -0400
@@ -28,16 +28,12 @@
 #define	_SYS_LIST_IMPL_H
 
 #include <sys/types.h>
+#include <sys/ilist.h>
 
 #ifdef	__cplusplus
 extern "C" {
 #endif
 
-struct list_node {
-	struct list_node *list_next;
-	struct list_node *list_prev;
-};
-
 struct list {
 	size_t	list_size;
 	size_t	list_offset;
--- a/usr/src/pkg/manifests/system-header.mf	Fri Mar 10 18:57:44 2017 -0500
+++ b/usr/src/pkg/manifests/system-header.mf	Sun Mar 22 10:48:20 2020 -0400
@@ -1092,6 +1092,7 @@
 file path=usr/include/sys/id32.h
 file path=usr/include/sys/id_space.h
 file path=usr/include/sys/idmap.h
+file path=usr/include/sys/ilist.h
 file path=usr/include/sys/inline.h
 file path=usr/include/sys/instance.h
 file path=usr/include/sys/int_const.h