1 /* $NetBSD: list.h,v 1.1 2013/09/05 15:28:07 skrll Exp $ */ 2 3 /*- 4 * Copyright (c) 2013 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #ifndef _LINUX_LIST_H_ 33 #define _LINUX_LIST_H_ 34 35 #include <sys/null.h> 36 #include <sys/queue.h> 37 38 #include <linux/kernel.h> 39 40 /* 41 * Doubly-linked lists. 42 */ 43 44 struct list_head { 45 struct list_head *prev; 46 struct list_head *next; 47 }; 48 49 #define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 50 51 static inline void 52 INIT_LIST_HEAD(struct list_head *head) 53 { 54 head->prev = head; 55 head->next = head; 56 } 57 58 static inline struct list_head * 59 list_first(const struct list_head *head) 60 { 61 return head->next; 62 } 63 64 static inline struct list_head * 65 list_next(const struct list_head *node) 66 { 67 return node->next; 68 } 69 70 static inline struct list_head * 71 list_prev(const struct list_head *node) 72 { 73 return node->prev; 74 } 75 76 static inline int 77 list_empty(const struct list_head *head) 78 { 79 return (head->next == head); 80 } 81 82 static inline void 83 __list_add_between(struct list_head *prev, struct list_head *node, 84 struct list_head *next) 85 { 86 prev->next = node; 87 node->prev = prev; 88 node->next = next; 89 next->prev = node; 90 } 91 92 static inline void 93 list_add(struct list_head *node, struct list_head *head) 94 { 95 __list_add_between(head, node, head->next); 96 } 97 98 static inline void 99 list_add_tail(struct list_head *node, struct list_head *head) 100 { 101 __list_add_between(head->prev, node, head); 102 } 103 104 static inline void 105 list_del(struct list_head *entry) 106 { 107 entry->prev->next = entry->next; 108 entry->next->prev = entry->prev; 109 } 110 111 static inline void 112 __list_splice_between(struct list_head *prev, const struct list_head *list, 113 struct list_head *next) 114 { 115 struct list_head *first = list->next; 116 struct list_head *last = list->prev; 117 118 first->prev = prev; 119 prev->next = first; 120 121 last->next = next; 122 next->prev = last; 123 } 124 125 static inline void 126 list_splice(const struct list_head *list, struct list_head *head) 127 { 128 if (!list_empty(list)) 129 __list_splice_between(head, list, head->next); 130 } 131 132 static inline void 133 list_splice_tail(const struct list_head *list, struct list_head *head) 134 { 135 if (!list_empty(list)) 136 __list_splice_between(head->prev, list, head); 137 } 138 139 static inline void 140 list_move(struct list_head *node, struct list_head *head) 141 { 142 list_del(node); 143 list_add(node, head); 144 } 145 146 static inline void 147 list_move_tail(struct list_head *node, struct list_head *head) 148 { 149 list_del(node); 150 list_add_tail(node, head); 151 } 152 153 static inline void 154 list_replace(struct list_head *old, struct list_head *new) 155 { 156 new->prev = old->prev; 157 old->prev->next = new; 158 new->next = old->next; 159 old->next->prev = new; 160 } 161 162 static inline void 163 list_del_init(struct list_head *node) 164 { 165 list_del(node); 166 INIT_LIST_HEAD(node); 167 } 168 169 #define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 170 #define list_first_entry(PTR, TYPE, FIELD) \ 171 list_entry(list_first((PTR)), TYPE, FIELD) 172 173 #define list_for_each(VAR, HEAD) \ 174 for ((VAR) = list_first((HEAD)); \ 175 (VAR) != (HEAD); \ 176 (VAR) = list_next((VAR))) 177 178 #define list_for_each_safe(VAR, NEXT, HEAD) \ 179 for ((VAR) = list_first((HEAD)); \ 180 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 181 (VAR) = (NEXT)) 182 183 #define list_for_each_entry(VAR, HEAD, FIELD) \ 184 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 185 &(VAR)->FIELD != (HEAD); \ 186 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 187 FIELD)) 188 189 #define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 190 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 191 (&(VAR)->FIELD != (HEAD)) && \ 192 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 193 typeof(*(VAR)), FIELD), 1); \ 194 (VAR) = (NEXT)) 195 196 /* 197 * `H'ead-only/`H'ash-table doubly-linked lists. 198 */ 199 200 LIST_HEAD(hlist_head, hlist_node); 201 struct hlist_node { 202 LIST_ENTRY(hlist_node) hln_entry; 203 }; 204 205 static inline struct hlist_node * 206 hlist_first(struct hlist_head *head) 207 { 208 return LIST_FIRST(head); 209 } 210 211 static inline struct hlist_node * 212 hlist_next(struct hlist_node *node) 213 { 214 return LIST_NEXT(node, hln_entry); 215 } 216 217 static inline void 218 hlist_add_head(struct hlist_node *node, struct hlist_head *head) 219 { 220 LIST_INSERT_HEAD(head, node, hln_entry); 221 } 222 223 static inline void 224 hlist_add_after(struct hlist_node *node, struct hlist_node *next) 225 { 226 LIST_INSERT_AFTER(node, next, hln_entry); 227 } 228 229 static inline void 230 hlist_del(struct hlist_node *node) 231 { 232 LIST_REMOVE(node, hln_entry); 233 } 234 235 static inline void 236 hlist_del_init(struct hlist_node *node) 237 { 238 LIST_REMOVE(node, hln_entry); 239 } 240 241 #define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 242 #define hlist_for_each(VAR, HEAD) LIST_FOREACH(VAR, HEAD, hln_entry) 243 #define hlist_for_each_safe(VAR, NEXT, HEAD) \ 244 LIST_FOREACH_SAFE(VAR, HEAD, hln_entry, NEXT) 245 246 #define hlist_for_each_entry(VAR, HLIST, HEAD, FIELD) \ 247 for ((HLIST) = LIST_FIRST((HEAD)); \ 248 ((HLIST) != NULL) && \ 249 ((VAR) = hlist_entry((HLIST), typeof(*(VAR)), FIELD), 1); \ 250 (HLIST) = LIST_NEXT((HLIST), hln_entry)) 251 252 /* 253 * XXX The nominally RCU-safe APIs below lack dependent read barriers, 254 * so they're not actually RCU-safe...on the alpha, anyway. Someone^TM 255 * should fix this. 256 */ 257 258 #define hlist_add_after_rcu hlist_add_after 259 #define hlist_add_head_rcu hlist_add_head 260 #define hlist_del_init_rcu hlist_del_init 261 #define hlist_for_each_entry_rcu hlist_for_each_entry 262 263 #endif /* _LINUX_LIST_H_ */ 264