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: releng/12.2/sys/compat/linuxkpi/common/include/linux/list.h 364652 2020-08-24 10:28:15Z manu $ 30 */ 31 #ifndef _LINUX_LIST_H_ 32 #define _LINUX_LIST_H_ 33 34 #include "linux/compiler.h" 35 #include "los_list.h" 36 37 #ifdef __cplusplus 38 #if __cplusplus 39 extern "C" { 40 #endif /* __cplusplus */ 41 #endif /* __cplusplus */ 42 43 #ifndef prefetch 44 #define prefetch(x) 45 #endif 46 47 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) } 48 49 #define LINUX_LIST_HEAD(name) \ 50 struct list_head name = LINUX_LIST_HEAD_INIT(name) 51 52 #ifndef LIST_HEAD_DEF 53 #define LIST_HEAD_DEF 54 struct list_head { 55 struct list_head *next; 56 struct list_head *prev; 57 }; 58 #endif 59 60 #define container_of LOS_DL_LIST_ENTRY 61 62 static inline void 63 INIT_LIST_HEAD(struct list_head *list) 64 { 65 66 list->next = list->prev = list; 67 } 68 69 static inline int 70 list_empty(const struct list_head *head) 71 { 72 73 return (head->next == head); 74 } 75 76 static inline int 77 list_empty_careful(const struct list_head *head) 78 { 79 struct list_head *next = head->next; 80 81 return ((next == head) && (next == head->prev)); 82 } 83 84 static inline void 85 __list_del(struct list_head *prev, struct list_head *next) 86 { 87 next->prev = prev; 88 WRITE_ONCE(prev->next, next); 89 } 90 91 static inline void 92 __list_del_entry(struct list_head *entry) 93 { 94 95 __list_del(entry->prev, entry->next); 96 } 97 98 static inline void 99 list_del(struct list_head *entry) 100 { 101 102 __list_del(entry->prev, entry->next); 103 } 104 105 static inline void 106 list_replace(struct list_head *old, struct list_head *new) 107 { 108 new->next = old->next; 109 new->next->prev = new; 110 new->prev = old->prev; 111 new->prev->next = new; 112 } 113 114 static inline void 115 list_replace_init(struct list_head *old, struct list_head *new) 116 { 117 list_replace(old, new); 118 INIT_LIST_HEAD(old); 119 } 120 121 static inline void 122 linux_list_add(struct list_head *new, struct list_head *prev, 123 struct list_head *next) 124 { 125 126 next->prev = new; 127 new->next = next; 128 new->prev = prev; 129 prev->next = new; 130 } 131 132 static inline void 133 list_del_init(struct list_head *entry) 134 { 135 136 list_del(entry); 137 INIT_LIST_HEAD(entry); 138 } 139 140 #define list_entry(ptr, type, field) container_of(ptr, type, field) 141 142 #define list_first_entry(ptr, type, member) \ 143 list_entry((ptr)->next, type, member) 144 145 #define list_last_entry(ptr, type, member) \ 146 list_entry((ptr)->prev, type, member) 147 148 #define list_first_entry_or_null(ptr, type, member) \ 149 (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL) 150 151 #define list_next_entry(ptr, member) \ 152 list_entry(((ptr)->member.next), typeof(*(ptr)), member) 153 154 #define list_safe_reset_next(ptr, n, member) \ 155 (n) = list_next_entry(ptr, member) 156 157 #define list_prev_entry(ptr, member) \ 158 list_entry(((ptr)->member.prev), typeof(*(ptr)), member) 159 160 #define list_for_each(p, head) \ 161 for (p = (head)->next; p != (head); p = (p)->next) 162 163 #define list_for_each_safe(p, n, head) \ 164 for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next) 165 166 #define list_for_each_entry(p, h, field) \ 167 for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \ 168 p = list_entry((p)->field.next, typeof(*p), field)) 169 170 #define list_for_each_entry_safe(p, n, h, field) \ 171 for (p = list_entry((h)->next, typeof(*p), field), \ 172 n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\ 173 p = n, n = list_entry(n->field.next, typeof(*n), field)) 174 175 #define list_for_each_entry_from(p, h, field) \ 176 for ( ; &(p)->field != (h); \ 177 p = list_entry((p)->field.next, typeof(*p), field)) 178 179 #define list_for_each_entry_continue(p, h, field) \ 180 for (p = list_next_entry((p), field); &(p)->field != (h); \ 181 p = list_next_entry((p), field)) 182 183 #define list_for_each_entry_safe_from(pos, n, head, member) \ 184 for (n = list_entry((pos)->member.next, typeof(*pos), member); \ 185 &(pos)->member != (head); \ 186 pos = n, n = list_entry(n->member.next, typeof(*n), member)) 187 188 #define list_for_each_entry_reverse(p, h, field) \ 189 for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \ 190 p = list_entry((p)->field.prev, typeof(*p), field)) 191 192 #define list_for_each_entry_safe_reverse(p, n, h, field) \ 193 for (p = list_entry((h)->prev, typeof(*p), field), \ 194 n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \ 195 p = n, n = list_entry(n->field.prev, typeof(*n), field)) 196 197 #define list_for_each_entry_continue_reverse(p, h, field) \ 198 for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \ 199 p = list_entry((p)->field.prev, typeof(*p), field)) 200 201 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev) 202 203 #define list_for_each_entry_from_reverse(p, h, field) \ 204 for (; &p->field != (h); \ 205 p = list_prev_entry(p, field)) 206 207 static inline void 208 list_add(struct list_head *new, struct list_head *head) 209 { 210 211 linux_list_add(new, head, head->next); 212 } 213 214 static inline void 215 list_add_tail(struct list_head *new, struct list_head *head) 216 { 217 218 linux_list_add(new, head->prev, head); 219 } 220 221 static inline void 222 list_move(struct list_head *list, struct list_head *head) 223 { 224 225 list_del(list); 226 list_add(list, head); 227 } 228 229 static inline void 230 list_move_tail(struct list_head *entry, struct list_head *head) 231 { 232 233 list_del(entry); 234 list_add_tail(entry, head); 235 } 236 237 static inline void 238 list_bulk_move_tail(struct list_head *head, struct list_head *first, 239 struct list_head *last) 240 { 241 first->prev->next = last->next; 242 last->next->prev = first->prev; 243 head->prev->next = first; 244 first->prev = head->prev; 245 last->next = head; 246 head->prev = last; 247 } 248 249 static inline void 250 linux_list_splice(const struct list_head *list, struct list_head *prev, 251 struct list_head *next) 252 { 253 struct list_head *first = NULL; 254 struct list_head *last = NULL; 255 256 if (list_empty(list)) 257 return; 258 first = list->next; 259 last = list->prev; 260 first->prev = prev; 261 prev->next = first; 262 last->next = next; 263 next->prev = last; 264 } 265 266 static inline void 267 list_splice(const struct list_head *list, struct list_head *head) 268 { 269 270 linux_list_splice(list, head, head->next); 271 } 272 273 static inline void 274 list_splice_tail(struct list_head *list, struct list_head *head) 275 { 276 277 linux_list_splice(list, head->prev, head); 278 } 279 280 static inline void 281 list_splice_init(struct list_head *list, struct list_head *head) 282 { 283 284 linux_list_splice(list, head, head->next); 285 INIT_LIST_HEAD(list); 286 } 287 288 static inline void 289 list_splice_tail_init(struct list_head *list, struct list_head *head) 290 { 291 292 linux_list_splice(list, head->prev, head); 293 INIT_LIST_HEAD(list); 294 } 295 296 297 struct hlist_head { 298 struct hlist_node *first; 299 }; 300 301 struct hlist_node { 302 struct hlist_node *next, **pprev; 303 }; 304 305 #define HLIST_HEAD_INIT { } 306 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT 307 #define INIT_HLIST_HEAD(head) (head)->first = NULL 308 #define INIT_HLIST_NODE(node) \ 309 do { \ 310 (node)->next = NULL; \ 311 (node)->pprev = NULL; \ 312 } while (0) 313 314 static inline int 315 hlist_unhashed(const struct hlist_node *h) 316 { 317 318 return !h->pprev; 319 } 320 321 static inline int 322 hlist_empty(const struct hlist_head *h) 323 { 324 325 return !READ_ONCE(h->first); 326 } 327 328 static inline void 329 hlist_del(struct hlist_node *n) 330 { 331 332 WRITE_ONCE(*(n->pprev), n->next); 333 if (n->next != NULL) 334 n->next->pprev = n->pprev; 335 } 336 337 static inline void 338 hlist_del_init(struct hlist_node *n) 339 { 340 341 if (hlist_unhashed(n)) 342 return; 343 hlist_del(n); 344 INIT_HLIST_NODE(n); 345 } 346 347 static inline void 348 hlist_add_head(struct hlist_node *n, struct hlist_head *h) 349 { 350 351 n->next = h->first; 352 if (h->first != NULL) 353 h->first->pprev = &n->next; 354 WRITE_ONCE(h->first, n); 355 n->pprev = &h->first; 356 } 357 358 static inline void 359 hlist_add_before(struct hlist_node *n, struct hlist_node *next) 360 { 361 362 n->pprev = next->pprev; 363 n->next = next; 364 next->pprev = &n->next; 365 WRITE_ONCE(*(n->pprev), n); 366 } 367 368 static inline void 369 hlist_add_behind(struct hlist_node *n, struct hlist_node *prev) 370 { 371 372 n->next = prev->next; 373 WRITE_ONCE(prev->next, n); 374 n->pprev = &prev->next; 375 376 if (n->next != NULL) 377 n->next->pprev = &n->next; 378 } 379 380 static inline void 381 hlist_move_list(struct hlist_head *old, struct hlist_head *new) 382 { 383 384 new->first = old->first; 385 if (new->first) 386 new->first->pprev = &new->first; 387 old->first = NULL; 388 } 389 390 static inline int list_is_singular(const struct list_head *head) 391 { 392 return !list_empty(head) && (head->next == head->prev); 393 } 394 395 static inline void __list_cut_position(struct list_head *list, 396 struct list_head *head, struct list_head *entry) 397 { 398 struct list_head *new_first = entry->next; 399 list->next = head->next; 400 list->next->prev = list; 401 list->prev = entry; 402 entry->next = list; 403 head->next = new_first; 404 new_first->prev = head; 405 } 406 407 static inline void list_cut_position(struct list_head *list, 408 struct list_head *head, struct list_head *entry) 409 { 410 if (list_empty(head)) 411 return; 412 if (list_is_singular(head) && 413 (head->next != entry && head != entry)) 414 return; 415 if (entry == head) 416 INIT_LIST_HEAD(list); 417 else 418 __list_cut_position(list, head, entry); 419 } 420 421 static inline int list_is_first(const struct list_head *list, 422 const struct list_head *head) 423 { 424 425 return (list->prev == head); 426 } 427 428 static inline int list_is_last(const struct list_head *list, 429 const struct list_head *head) 430 { 431 return list->next == head; 432 } 433 434 #define hlist_entry(ptr, type, field) container_of(ptr, type, field) 435 436 #define hlist_for_each(p, head) \ 437 for (p = (head)->first; p; p = (p)->next) 438 439 #define hlist_for_each_safe(p, n, head) \ 440 for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n) 441 442 #define hlist_entry_safe(ptr, type, member) \ 443 ((ptr) ? hlist_entry(ptr, type, member) : NULL) 444 445 #define hlist_for_each_entry(pos, head, member) \ 446 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ 447 pos; \ 448 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 449 450 #define hlist_for_each_entry_continue(pos, member) \ 451 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \ 452 (pos); \ 453 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 454 455 #define hlist_for_each_entry_from(pos, member) \ 456 for (; (pos); \ 457 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 458 459 #define hlist_for_each_entry_safe(pos, n, head, member) \ 460 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \ 461 (pos) && ({ n = (pos)->member.next; 1; }); \ 462 pos = hlist_entry_safe(n, typeof(*(pos)), member)) 463 464 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, 465 struct list_head *a, struct list_head *b)); 466 467 468 #ifdef __cplusplus 469 #if __cplusplus 470 } 471 #endif /* __cplusplus */ 472 #endif /* __cplusplus */ 473 474 #endif /* _LINUX_LIST_H_ */ 475