1/* $NetBSD: list.h,v 1.5 2014/08/20 15:26:52 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/queue.h> 48 49#define container_of(ptr, type, member) \ 50({ \ 51 __typeof(((type *)0)->member) *_p = (ptr); \ 52 (type *)((char *)_p - offsetof(type, member)); \ 53}) 54 55/* 56 * Doubly-linked lists. 57 */ 58 59struct list_head { 60 struct list_head *prev; 61 struct list_head *next; 62}; 63 64#define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 65 66static inline void 67INIT_LIST_HEAD(struct list_head *head) 68{ 69 head->prev = head; 70 head->next = head; 71} 72 73static inline struct list_head * 74list_first(const struct list_head *head) 75{ 76 return head->next; 77} 78 79static inline struct list_head * 80list_last(const struct list_head *head) 81{ 82 return head->prev; 83} 84 85static inline struct list_head * 86list_next(const struct list_head *node) 87{ 88 return node->next; 89} 90 91static inline struct list_head * 92list_prev(const struct list_head *node) 93{ 94 return node->prev; 95} 96 97static inline int 98list_empty(const struct list_head *head) 99{ 100 return (head->next == head); 101} 102 103static inline int 104list_is_singular(const struct list_head *head) 105{ 106 107 if (list_empty(head)) 108 return false; 109 if (head->next != head->prev) 110 return false; 111 return true; 112} 113 114static inline void 115__list_add_between(struct list_head *prev, struct list_head *node, 116 struct list_head *next) 117{ 118 prev->next = node; 119 node->prev = prev; 120 node->next = next; 121 next->prev = node; 122} 123 124static inline void 125list_add(struct list_head *node, struct list_head *head) 126{ 127 __list_add_between(head, node, head->next); 128} 129 130static inline void 131list_add_tail(struct list_head *node, struct list_head *head) 132{ 133 __list_add_between(head->prev, node, head); 134} 135 136static inline void 137list_del(struct list_head *entry) 138{ 139 entry->prev->next = entry->next; 140 entry->next->prev = entry->prev; 141} 142 143static inline void 144__list_splice_between(struct list_head *prev, const struct list_head *list, 145 struct list_head *next) 146{ 147 struct list_head *first = list->next; 148 struct list_head *last = list->prev; 149 150 first->prev = prev; 151 prev->next = first; 152 153 last->next = next; 154 next->prev = last; 155} 156 157static inline void 158list_splice(const struct list_head *list, struct list_head *head) 159{ 160 if (!list_empty(list)) 161 __list_splice_between(head, list, head->next); 162} 163 164static inline void 165list_splice_tail(const struct list_head *list, struct list_head *head) 166{ 167 if (!list_empty(list)) 168 __list_splice_between(head->prev, list, head); 169} 170 171static inline void 172list_move(struct list_head *node, struct list_head *head) 173{ 174 list_del(node); 175 list_add(node, head); 176} 177 178static inline void 179list_move_tail(struct list_head *node, struct list_head *head) 180{ 181 list_del(node); 182 list_add_tail(node, head); 183} 184 185static inline void 186list_replace(struct list_head *old, struct list_head *new) 187{ 188 new->prev = old->prev; 189 old->prev->next = new; 190 new->next = old->next; 191 old->next->prev = new; 192} 193 194static inline void 195list_del_init(struct list_head *node) 196{ 197 list_del(node); 198 INIT_LIST_HEAD(node); 199} 200 201#define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 202#define list_first_entry(PTR, TYPE, FIELD) \ 203 list_entry(list_first((PTR)), TYPE, FIELD) 204#define list_last_entry(PTR, TYPE, FIELD) \ 205 list_entry(list_last((PTR)), TYPE, FIELD) 206#define list_next_entry(ENTRY, FIELD) \ 207 list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 208#define list_prev_entry(ENTRY, FIELD) \ 209 list_entry(list_prev(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 210 211#define list_for_each(VAR, HEAD) \ 212 for ((VAR) = list_first((HEAD)); \ 213 (VAR) != (HEAD); \ 214 (VAR) = list_next((VAR))) 215 216#define list_for_each_safe(VAR, NEXT, HEAD) \ 217 for ((VAR) = list_first((HEAD)); \ 218 ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 219 (VAR) = (NEXT)) 220 221#define list_for_each_entry(VAR, HEAD, FIELD) \ 222 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 223 &(VAR)->FIELD != (HEAD); \ 224 (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 225 FIELD)) 226 227#define list_for_each_entry_reverse(VAR, HEAD, FIELD) \ 228 for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \ 229 &(VAR)->FIELD != (HEAD); \ 230 (VAR) = list_entry(list_prev(&(VAR)->FIELD), typeof(*(VAR)), \ 231 FIELD)) 232 233#define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 234 for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 235 (&(VAR)->FIELD != (HEAD)) && \ 236 ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 237 typeof(*(VAR)), FIELD), 1); \ 238 (VAR) = (NEXT)) 239 240#define list_for_each_entry_continue(VAR, HEAD, FIELD) \ 241 for ((VAR) = list_next_entry((VAR), FIELD); \ 242 &(VAR)->FIELD != (HEAD); \ 243 (VAR) = list_next_entry((VAR), FIELD)) 244 245#define list_for_each_entry_continue_reverse(VAR, HEAD, FIELD) \ 246 for ((VAR) = list_prev_entry((VAR), FIELD); \ 247 &(VAR)->FIELD != (HEAD); \ 248 (VAR) = list_prev_entry((VAR), FIELD)) 249 250#define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \ 251 for (; \ 252 (&(VAR)->FIELD != (HEAD)) && \ 253 ((NEXT) = list_next_entry((VAR), FIELD)); \ 254 (VAR) = (NEXT)) 255 256#endif /* _LINUX_LIST_H_ */ 257