list.h revision 1.3
1/* $NetBSD: list.h,v 1.3 2014/07/16 20:56:24 riastradh 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/* 33 * Notes on porting: 34 * 35 * - LIST_HEAD(x) means a declaration `struct list_head x = 36 * LIST_HEAD_INIT(x)' in Linux, but something else in NetBSD. 37 * Replace by the expansion. 38 * 39 * - The `_rcu' routines here are not actually pserialize(9)-safe. 40 * They need dependent read memory barriers added. Please fix this 41 * if you need to use them with pserialize(9). 42 */ 43 44#ifndef _LINUX_LIST_H_ 45#define _LINUX_LIST_H_ 46 47#include <sys/null.h> 48#include <sys/queue.h> 49 50#include <linux/kernel.h> 51 52/* 53 * Doubly-linked lists. 54 */ 55 56struct list_head { 57 struct list_head *prev; 58 struct list_head *next; 59}; 60 61#define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 62 63static inline void 64INIT_LIST_HEAD(struct list_head *head) 65{ 66 head->prev = head; 67 head->next = head; 68} 69 70static inline struct list_head * 71list_first(const struct list_head *head) 72{ 73 return head->next; 74} 75 76static inline struct list_head * 77list_next(const struct list_head *node) 78{ 79 return node->next; 80} 81 82static inline struct list_head * 83list_prev(const struct list_head *node) 84{ 85 return node->prev; 86} 87 88static inline int 89list_empty(const struct list_head *head) 90{ 91 return (head->next == head); 92} 93 94static inline int 95list_is_singular(const struct list_head *head) 96{ 97 98 if (list_empty(head)) 99 return false; 100 if (head->next != head->prev) 101 return false; 102 return true; 103} 104 105static inline void 106__list_add_between(struct list_head *prev, struct list_head *node, 107 struct list_head *next) 108{ 109 prev->next = node; 110 node->prev = prev; 111 node->next = next; 112 next->prev = node; 113} 114 115static inline void 116list_add(struct list_head *node, struct list_head *head) 117{ 118 __list_add_between(head, node, head->next); 119} 120 121static inline void 122list_add_tail(struct list_head *node, struct list_head *head) 123{ 124 __list_add_between(head->prev, node, head); 125} 126 127static inline void 128list_del(struct list_head *entry) 129{ 130 entry->prev->next = entry->next; 131 entry->next->prev = entry->prev; 132} 133 134static inline void 135__list_splice_between(struct list_head *prev, const struct list_head *list, 136 struct list_head *next) 137{ 138 struct list_head *first = list->next; 139 struct list_head *last = list->prev; 140 141 first->prev = prev; 142 prev->next = first; 143 144 last->next = next; 145 next->prev = last; 146} 147 148static inline void 149list_splice(const struct list_head *list, struct list_head *head) 150{ 151 if (!list_empty(list)) 152 __list_splice_between(head, list, head->next); 153} 154 155static inline void 156list_splice_tail(const struct list_head *list, struct list_head *head) 157{ 158 if (!list_empty(list)) 159 __list_splice_between(head->prev, list, head); 160} 161 162static inline void 163list_move(struct list_head *node, struct list_head *head) 164{ 165 list_del(node); 166 list_add(node, head); 167} 168 169static inline void 170list_move_tail(struct list_head *node, struct list_head *head) 171{ 172 list_del(node); 173 list_add_tail(node, head); 174} 175 176static inline void 177list_replace(struct list_head *old, struct list_head *new) 178{ 179 new->prev = old->prev; 180 old->prev->next = new; 181 new->next = old->next; 182 old->next->prev = new; 183} 184 185static inline void 186list_del_init(struct list_head *node) 187{ 188 list_del(node); 189 INIT_LIST_HEAD(node); 190} 191 192#define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 193#define list_first_entry(PTR, TYPE, FIELD) \ 194 list_entry(list_first((PTR)), TYPE, FIELD) 195#define list_next_entry(ENTRY, FIELD) \ 196 list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 197 198#define list_for_each(VAR, HEAD) \ 199 for ((VAR) = list_first((HEAD)); \ 200 (VAR) != (HEAD); \ 201 (VAR) = list_next((VAR))) 202 203#define list_for_each_safe(VAR, NEXT, HEAD) \ 204 for ((VAR) = list_first((HEAD)); \ 205 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 206 (VAR) = (NEXT)) 207 208#define list_for_each_entry(VAR, HEAD, FIELD) \ 209 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 210 &(VAR)->FIELD != (HEAD); \ 211 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 212 FIELD)) 213 214#define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 215 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 216 (&(VAR)->FIELD != (HEAD)) && \ 217 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 218 typeof(*(VAR)), FIELD), 1); \ 219 (VAR) = (NEXT)) 220 221#define list_for_each_entry_continue(VAR, HEAD, FIELD) \ 222 for ((VAR) = list_next_entry((VAR), FIELD); \ 223 &(VAR)->FIELD != (HEAD); \ 224 (VAR) = list_next_entry((VAR), FIELD)) 225 226/* 227 * `H'ead-only/`H'ash-table doubly-linked lists. 228 */ 229 230LIST_HEAD(hlist_head, hlist_node); 231struct hlist_node { 232 LIST_ENTRY(hlist_node) hln_entry; 233}; 234 235static inline struct hlist_node * 236hlist_first(struct hlist_head *head) 237{ 238 return LIST_FIRST(head); 239} 240 241static inline struct hlist_node * 242hlist_next(struct hlist_node *node) 243{ 244 return LIST_NEXT(node, hln_entry); 245} 246 247static inline void 248hlist_add_head(struct hlist_node *node, struct hlist_head *head) 249{ 250 LIST_INSERT_HEAD(head, node, hln_entry); 251} 252 253static inline void 254hlist_add_after(struct hlist_node *node, struct hlist_node *next) 255{ 256 LIST_INSERT_AFTER(node, next, hln_entry); 257} 258 259static inline void 260hlist_del(struct hlist_node *node) 261{ 262 LIST_REMOVE(node, hln_entry); 263} 264 265static inline void 266hlist_del_init(struct hlist_node *node) 267{ 268 LIST_REMOVE(node, hln_entry); 269} 270 271#define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 272#define hlist_for_each(VAR, HEAD) LIST_FOREACH(VAR, HEAD, hln_entry) 273#define hlist_for_each_safe(VAR, NEXT, HEAD) \ 274 LIST_FOREACH_SAFE(VAR, HEAD, hln_entry, NEXT) 275 276#define hlist_for_each_entry(VAR, HEAD, FIELD) \ 277 for ((VAR) = hlist_entry(LIST_FIRST((HEAD)), typeof(*(VAR)), FIELD); \ 278 &(VAR)->FIELD != NULL; \ 279 (VAR) = hlist_entry(LIST_NEXT(&(VAR)->FIELD, hln_entry), \ 280 typeof(*(VAR)), FIELD)) 281 282/* 283 * XXX The nominally RCU-safe APIs below lack dependent read barriers, 284 * so they're not actually RCU-safe...on the alpha, anyway. Someone^TM 285 * should fix this. 286 */ 287 288#define hlist_add_after_rcu hlist_add_after 289#define hlist_add_head_rcu hlist_add_head 290#define hlist_del_init_rcu hlist_del_init 291#define hlist_for_each_entry_rcu hlist_for_each_entry 292 293#endif /* _LINUX_LIST_H_ */ 294