Mercurial > unleashed > wips

comparison include/sys/ilist.h @ 20687:ac1492488560 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
children
comparison
equal deleted inserted replaced
18357:11a2d819935f 20687:ac1492488560
1 /*
2 * Copyright 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
3 *
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 #ifndef _SYS_ILIST_H
18 #define _SYS_ILIST_H
19
20 /*
21 * Generic circular doubly-linked list with a sentinel node.
22 *
23 * The entire implementation is here as C99 static inline functions. We
24 * hide them if we are not using a C99 compiler to expose the list_node
25 * struct for list.h's benefit.
26 *
27 * Here's the summary of differences:
28 *
29 * (1) both ilist.h and list.h use the same struct list_node
30 * (1) ilist.h uses static inlines while list.h uses normal functions
31 * (2) list.h uses struct list to keep track of offsets into objects for the
32 * struct list_node
33 * (3) ilist.h uses struct list_head as a sentinel node and has no idea
34 * about the structures containing each of the list entries
35 */
36
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40
41 struct list_node {
42 struct list_node *list_next;
43 struct list_node *list_prev;
44 };
45
46 #ifdef _STDC_C99
47
48 #include <sys/null.h>
49
50 static inline void ilist_init(struct list_node *node)
51 {
52 node->list_next = node;
53 node->list_prev = node;
54 }
55
56 static inline int ilist_is_empty(struct list_node *list)
57 {
58 return list->list_next == list;
59 }
60
61 static int ilist_link_active(struct list_node *node)
62 {
63 return node->list_next != NULL;
64 }
65
66 static inline struct list_node *ilist_head(struct list_node *list)
67 {
68 if (ilist_is_empty(list))
69 return NULL;
70
71 return list->list_next;
72 }
73
74 static inline struct list_node *ilist_tail(struct list_node *list)
75 {
76 if (ilist_is_empty(list))
77 return NULL;
78
79 return list->list_prev;
80 }
81
82 static inline struct list_node *ilist_next(struct list_node *list,
83 struct list_node *cur)
84 {
85 if (cur->list_next == list)
86 return NULL;
87
88 return cur->list_next;
89 }
90
91 static inline struct list_node *ilist_prev(struct list_node *list,
92 struct list_node *cur)
93 {
94 if (cur->list_prev == list)
95 return NULL;
96
97 return cur->list_prev;
98 }
99
100 static inline void __ilist_insert(struct list_node *before,
101 struct list_node *after,
102 struct list_node *newnode)
103 {
104 before->list_next = newnode;
105 newnode->list_prev = before;
106 newnode->list_next = after;
107 after->list_prev = newnode;
108 }
109
110 static inline void ilist_insert_after(struct list_node *reference,
111 struct list_node *newnode)
112 {
113 __ilist_insert(reference, reference->list_next, newnode);
114 }
115
116 static inline void ilist_insert_before(struct list_node *reference,
117 struct list_node *newnode)
118 {
119 __ilist_insert(reference->list_prev, reference, newnode);
120 }
121
122 #define ilist_insert_head(list, newnode) ilist_insert_after((list), (newnode))
123 #define ilist_insert_tail(list, newnode) ilist_insert_before((list), (newnode))
124
125 static inline void ilist_remove(struct list_node *node)
126 {
127 node->list_prev->list_next = node->list_next;
128 node->list_next->list_prev = node->list_prev;
129
130 node->list_prev = NULL;
131 node->list_next = NULL;
132 }
133
134 static inline struct list_node *__ilist_remove(struct list_node *list,
135 struct list_node *node)
136 {
137 if (ilist_is_empty(list))
138 return NULL;
139
140 ilist_remove(node);
141 return node;
142 }
143
144 static inline struct list_node *ilist_remove_head(struct list_node *list)
145 {
146 return __ilist_remove(list, list->list_next);
147 }
148
149 static inline struct list_node *ilist_remove_tail(struct list_node *list)
150 {
151 return __ilist_remove(list, list->list_prev);
152 }
153
154 #endif
155
156 #ifdef __cplusplus
157 }
158 #endif
159
160 #endif /* _SYS_ILIST_H */