1 /*- 2 * Copyright (c) 2010 Isilon Systems, Inc. 3 * Copyright (c) 2010 iX Systems, Inc. 4 * Copyright (c) 2010 Panasas, Inc. 5 * Copyright (c) 2013-2016 Mellanox Technologies, Ltd. 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice unmodified, this list of conditions, and the following 13 * disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 * 29 * $FreeBSD$ 30 */ 31 #ifndef _LINUX_LIST_H_ 32 #define _LINUX_LIST_H_ 33 34 #define container_of(ptr, type, member) \ 35 ({ \ 36 const __typeof(((type *)0)->member) *__p = (ptr); \ 37 (type *)((uintptr_t)__p - offsetof(type, member)); \ 38 }) 39 40 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) } 41 42 #define LINUX_LIST_HEAD(name) \ 43 struct list_head name = LINUX_LIST_HEAD_INIT(name) 44 45 #ifndef LIST_HEAD_DEF 46 #define LIST_HEAD_DEF 47 struct list_head { 48 struct list_head *next; 49 struct list_head *prev; 50 }; 51 #endif 52 53 #define barrier() __asm__ __volatile__("": : :"memory") 54 55 56 #define ACCESS_ONCE(x) (*(volatile __typeof(x) *)&(x)) 57 58 #define WRITE_ONCE(x,v) do { \ 59 barrier(); \ 60 ACCESS_ONCE(x) = (v); \ 61 barrier(); \ 62 } while (0) 63 64 #define READ_ONCE(x) ({ \ 65 __typeof(x) __var = ({ \ 66 barrier(); \ 67 ACCESS_ONCE(x); \ 68 }); \ 69 barrier(); \ 70 __var; \ 71 }) 72 73 static inline void 74 INIT_LIST_HEAD(struct list_head *list) 75 { 76 77 list->next = list->prev = list; 78 } 79 80 static inline int 81 list_empty(const struct list_head *head) 82 { 83 84 return (head->next == head); 85 } 86 87 static inline int 88 list_empty_careful(const struct list_head *head) 89 { 90 struct list_head *next = head->next; 91 92 return ((next == head) && (next == head->prev)); 93 } 94 95 static inline void 96 __list_del(struct list_head *prev, struct list_head *next) 97 { 98 next->prev = prev; 99 WRITE_ONCE(prev->next, next); 100 } 101 102 static inline void 103 __list_del_entry(struct list_head *entry) 104 { 105 106 __list_del(entry->prev, entry->next); 107 } 108 109 static inline void 110 list_del(struct list_head *entry) 111 { 112 113 __list_del(entry->prev, entry->next); 114 } 115 116 static inline void 117 list_replace(struct list_head *old, struct list_head *new) 118 { 119 new->next = old->next; 120 new->next->prev = new; 121 new->prev = old->prev; 122 new->prev->next = new; 123 } 124 125 static inline void 126 list_replace_init(struct list_head *old, struct list_head *new) 127 { 128 list_replace(old, new); 129 INIT_LIST_HEAD(old); 130 } 131 132 static inline void 133 linux_list_add(struct list_head *new, struct list_head *prev, 134 struct list_head *next) 135 { 136 137 next->prev = new; 138 new->next = next; 139 new->prev = prev; 140 prev->next = new; 141 } 142 143 static inline void 144 list_del_init(struct list_head *entry) 145 { 146 147 list_del(entry); 148 INIT_LIST_HEAD(entry); 149 } 150 151 #define list_entry(ptr, type, field) container_of(ptr, type, field) 152 153 #define list_first_entry(ptr, type, member) \ 154 list_entry((ptr)->next, type, member) 155 156 #define list_last_entry(ptr, type, member) \ 157 list_entry((ptr)->prev, type, member) 158 159 #define list_first_entry_or_null(ptr, type, member) \ 160 (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL) 161 162 #define list_next_entry(ptr, member) \ 163 list_entry(((ptr)->member.next), typeof(*(ptr)), member) 164 165 #define list_safe_reset_next(ptr, n, member) \ 166 (n) = list_next_entry(ptr, member) 167 168 #define list_prev_entry(ptr, member) \ 169 list_entry(((ptr)->member.prev), typeof(*(ptr)), member) 170 171 #define list_for_each(p, head) \ 172 for (p = (head)->next; p != (head); p = (p)->next) 173 174 #define list_for_each_safe(p, n, head) \ 175 for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next) 176 177 #define list_for_each_entry(p, h, field) \ 178 for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \ 179 p = list_entry((p)->field.next, typeof(*p), field)) 180 181 #define list_for_each_entry_safe(p, n, h, field) \ 182 for (p = list_entry((h)->next, typeof(*p), field), \ 183 n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\ 184 p = n, n = list_entry(n->field.next, typeof(*n), field)) 185 186 #define list_for_each_entry_from(p, h, field) \ 187 for ( ; &(p)->field != (h); \ 188 p = list_entry((p)->field.next, typeof(*p), field)) 189 190 #define list_for_each_entry_continue(p, h, field) \ 191 for (p = list_next_entry((p), field); &(p)->field != (h); \ 192 p = list_next_entry((p), field)) 193 194 #define list_for_each_entry_safe_from(pos, n, head, member) \ 195 for (n = list_entry((pos)->member.next, typeof(*pos), member); \ 196 &(pos)->member != (head); \ 197 pos = n, n = list_entry(n->member.next, typeof(*n), member)) 198 199 #define list_for_each_entry_reverse(p, h, field) \ 200 for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \ 201 p = list_entry((p)->field.prev, typeof(*p), field)) 202 203 #define list_for_each_entry_safe_reverse(p, n, h, field) \ 204 for (p = list_entry((h)->prev, typeof(*p), field), \ 205 n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \ 206 p = n, n = list_entry(n->field.prev, typeof(*n), field)) 207 208 #define list_for_each_entry_continue_reverse(p, h, field) \ 209 for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \ 210 p = list_entry((p)->field.prev, typeof(*p), field)) 211 212 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev) 213 214 static inline void 215 list_add(struct list_head *new, struct list_head *head) 216 { 217 218 linux_list_add(new, head, head->next); 219 } 220 221 static inline void 222 list_add_tail(struct list_head *new, struct list_head *head) 223 { 224 225 linux_list_add(new, head->prev, head); 226 } 227 228 static inline void 229 list_move(struct list_head *list, struct list_head *head) 230 { 231 232 list_del(list); 233 list_add(list, head); 234 } 235 236 static inline void 237 list_move_tail(struct list_head *entry, struct list_head *head) 238 { 239 240 list_del(entry); 241 list_add_tail(entry, head); 242 } 243 244 static inline void 245 linux_list_splice(const struct list_head *list, struct list_head *prev, 246 struct list_head *next) 247 { 248 struct list_head *first; 249 struct list_head *last; 250 251 if (list_empty(list)) 252 return; 253 first = list->next; 254 last = list->prev; 255 first->prev = prev; 256 prev->next = first; 257 last->next = next; 258 next->prev = last; 259 } 260 261 static inline void 262 list_splice(const struct list_head *list, struct list_head *head) 263 { 264 265 linux_list_splice(list, head, head->next); 266 } 267 268 static inline void 269 list_splice_tail(struct list_head *list, struct list_head *head) 270 { 271 272 linux_list_splice(list, head->prev, head); 273 } 274 275 static inline void 276 list_splice_init(struct list_head *list, struct list_head *head) 277 { 278 279 linux_list_splice(list, head, head->next); 280 INIT_LIST_HEAD(list); 281 } 282 283 static inline void 284 list_splice_tail_init(struct list_head *list, struct list_head *head) 285 { 286 287 linux_list_splice(list, head->prev, head); 288 INIT_LIST_HEAD(list); 289 } 290 291 #undef LIST_HEAD 292 #define LIST_HEAD(name) struct list_head name = { &(name), &(name) } 293 294 295 struct hlist_head { 296 struct hlist_node *first; 297 }; 298 299 struct hlist_node { 300 struct hlist_node *next, **pprev; 301 }; 302 303 #define HLIST_HEAD_INIT { } 304 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT 305 #define INIT_HLIST_HEAD(head) (head)->first = NULL 306 #define INIT_HLIST_NODE(node) \ 307 do { \ 308 (node)->next = NULL; \ 309 (node)->pprev = NULL; \ 310 } while (0) 311 312 static inline int 313 hlist_unhashed(const struct hlist_node *h) 314 { 315 316 return !h->pprev; 317 } 318 319 static inline int 320 hlist_empty(const struct hlist_head *h) 321 { 322 323 return !h->first; 324 } 325 326 static inline void 327 hlist_del(struct hlist_node *n) 328 { 329 330 if (n->next) 331 n->next->pprev = n->pprev; 332 *n->pprev = n->next; 333 } 334 335 static inline void 336 hlist_del_init(struct hlist_node *n) 337 { 338 339 if (hlist_unhashed(n)) 340 return; 341 hlist_del(n); 342 INIT_HLIST_NODE(n); 343 } 344 345 static inline void 346 hlist_add_head(struct hlist_node *n, struct hlist_head *h) 347 { 348 349 n->next = h->first; 350 if (h->first) 351 h->first->pprev = &n->next; 352 h->first = n; 353 n->pprev = &h->first; 354 } 355 356 static inline void 357 hlist_add_before(struct hlist_node *n, struct hlist_node *next) 358 { 359 360 n->pprev = next->pprev; 361 n->next = next; 362 next->pprev = &n->next; 363 *(n->pprev) = n; 364 } 365 366 static inline void 367 hlist_add_after(struct hlist_node *n, struct hlist_node *next) 368 { 369 370 next->next = n->next; 371 n->next = next; 372 next->pprev = &n->next; 373 if (next->next) 374 next->next->pprev = &next->next; 375 } 376 377 static inline void 378 hlist_move_list(struct hlist_head *old, struct hlist_head *new) 379 { 380 381 new->first = old->first; 382 if (new->first) 383 new->first->pprev = &new->first; 384 old->first = NULL; 385 } 386 387 static inline int list_is_singular(const struct list_head *head) 388 { 389 return !list_empty(head) && (head->next == head->prev); 390 } 391 392 static inline void __list_cut_position(struct list_head *list, 393 struct list_head *head, struct list_head *entry) 394 { 395 struct list_head *new_first = entry->next; 396 list->next = head->next; 397 list->next->prev = list; 398 list->prev = entry; 399 entry->next = list; 400 head->next = new_first; 401 new_first->prev = head; 402 } 403 404 static inline void list_cut_position(struct list_head *list, 405 struct list_head *head, struct list_head *entry) 406 { 407 if (list_empty(head)) 408 return; 409 if (list_is_singular(head) && 410 (head->next != entry && head != entry)) 411 return; 412 if (entry == head) 413 INIT_LIST_HEAD(list); 414 else 415 __list_cut_position(list, head, entry); 416 } 417 418 static inline int list_is_last(const struct list_head *list, 419 const struct list_head *head) 420 { 421 return list->next == head; 422 } 423 424 #define hlist_entry(ptr, type, field) container_of(ptr, type, field) 425 426 #define hlist_for_each(p, head) \ 427 for (p = (head)->first; p; p = (p)->next) 428 429 #define hlist_for_each_safe(p, n, head) \ 430 for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n) 431 432 #define hlist_entry_safe(ptr, type, member) \ 433 ((ptr) ? hlist_entry(ptr, type, member) : NULL) 434 435 #define hlist_for_each_entry(pos, head, member) \ 436 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ 437 pos; \ 438 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 439 440 #define hlist_for_each_entry_continue(pos, member) \ 441 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \ 442 (pos); \ 443 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 444 445 #define hlist_for_each_entry_from(pos, member) \ 446 for (; (pos); \ 447 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 448 449 #define hlist_for_each_entry_safe(pos, n, head, member) \ 450 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \ 451 (pos) && ({ n = (pos)->member.next; 1; }); \ 452 pos = hlist_entry_safe(n, typeof(*(pos)), member)) 453 454 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, 455 struct list_head *a, struct list_head *b)); 456 457 #endif /* _LINUX_LIST_H_ */ 458