# HG changeset patch # User Josef 'Jeff' Sipek # Date 1584888500 14400 # Node ID ac14924885606706b0cbbce5155c96827a809de3 # Parent 11a2d819935fe091494605f055d8cdad8de5fb6d ilist: add generic circular doubly-linked list with a sentinel node diff -r 11a2d819935f -r ac1492488560 include/sys/Makefile --- 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 \ diff -r 11a2d819935f -r ac1492488560 include/sys/ilist.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 + * + * 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 + +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 */ diff -r 11a2d819935f -r ac1492488560 include/sys/list_impl.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 +#include #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; diff -r 11a2d819935f -r ac1492488560 usr/src/pkg/manifests/system-header.mf --- 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