1239054Sae/* $NetBSD: list.h,v 1.32 2021/12/19 11:39:24 riastradh Exp $ */ 2239054Sae 3239054Sae/*- 4239054Sae * Copyright (c) 2013 The NetBSD Foundation, Inc. 5239054Sae * All rights reserved. 6239054Sae * 7239054Sae * This code is derived from software contributed to The NetBSD Foundation 8239054Sae * by Taylor R. Campbell. 9239054Sae * 10239054Sae * Redistribution and use in source and binary forms, with or without 11239054Sae * modification, are permitted provided that the following conditions 12239054Sae * are met: 13239054Sae * 1. Redistributions of source code must retain the above copyright 14239054Sae * notice, this list of conditions and the following disclaimer. 15239054Sae * 2. Redistributions in binary form must reproduce the above copyright 16239054Sae * notice, this list of conditions and the following disclaimer in the 17239054Sae * documentation and/or other materials provided with the distribution. 18239054Sae * 19239054Sae * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20239054Sae * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21239054Sae * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22239054Sae * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23239054Sae * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24239054Sae * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25239054Sae * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26239054Sae * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27239054Sae * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28239054Sae * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29239054Sae * POSSIBILITY OF SUCH DAMAGE. 30239054Sae */ 31239054Sae 32239054Sae/* 33239054Sae * Notes on porting: 34239054Sae * 35239054Sae * - LIST_HEAD(x) means a declaration `struct list_head x = 36239054Sae * LIST_HEAD_INIT(x)' in Linux, but something else in NetBSD. 37239054Sae * Replace by the expansion. 38239054Sae */ 39239054Sae 40239054Sae#ifndef _LINUX_LIST_H_ 41239054Sae#define _LINUX_LIST_H_ 42239054Sae 43239054Sae#include <sys/null.h> 44239054Sae#include <sys/pslist.h> 45239054Sae#include <sys/queue.h> 46239054Sae 47239054Sae#include <linux/kernel.h> 48239054Sae#include <linux/types.h> 49239054Sae 50239054Sae#define POISON_INUSE 0x5a /* XXX */ 51239054Sae 52239054Sae/* 53239054Sae * Doubly-linked lists. Type defined in <linux/types.h>. 54239054Sae */ 55239054Sae 56239054Sae#define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 57239054Sae 58239054Sae#define LINUX_LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) 59239054Sae 60239054Saestatic inline void 61239054SaeINIT_LIST_HEAD(struct list_head *head) 62239054Sae{ 63239054Sae head->prev = head; 64239054Sae head->next = head; 65239054Sae} 66239054Sae 67239054Saestatic inline struct list_head * 68239054Saelist_first(const struct list_head *head) 69239054Sae{ 70239054Sae return head->next; 71239054Sae} 72239054Sae 73239054Saestatic inline struct list_head * 74239054Saelist_last(const struct list_head *head) 75239054Sae{ 76239054Sae return head->prev; 77239054Sae} 78239054Sae 79239054Saestatic inline struct list_head * 80239054Saelist_next(const struct list_head *node) 81239054Sae{ 82239054Sae return node->next; 83239054Sae} 84239054Sae 85239054Saestatic inline struct list_head * 86239054Saelist_prev(const struct list_head *node) 87239054Sae{ 88239054Sae return node->prev; 89239054Sae} 90239054Sae 91239054Saestatic inline int 92239054Saelist_empty(const struct list_head *head) 93239054Sae{ 94239054Sae return (head->next == head); 95239054Sae} 96239054Sae 97239054Saestatic inline int 98239054Saelist_is_singular(const struct list_head *head) 99239054Sae{ 100239054Sae 101239054Sae if (list_empty(head)) 102239054Sae return false; 103239054Sae if (head->next != head->prev) 104239054Sae return false; 105239054Sae return true; 106239054Sae} 107239054Sae 108239054Saestatic inline bool 109239054Saelist_is_first(const struct list_head *entry, const struct list_head *head) 110239054Sae{ 111239054Sae return head == entry->prev; 112239054Sae} 113239054Sae 114239054Saestatic inline bool 115239054Saelist_is_last(const struct list_head *entry, const struct list_head *head) 116239054Sae{ 117239054Sae return head == entry->next; 118239054Sae} 119239054Sae 120239054Saestatic inline void 121239054Sae__list_add_between(struct list_head *prev, struct list_head *node, 122239054Sae struct list_head *next) 123239054Sae{ 124239054Sae prev->next = node; 125239054Sae node->prev = prev; 126239054Sae node->next = next; 127239054Sae next->prev = node; 128239054Sae} 129239054Sae 130239054Saestatic inline void 131239054Saelist_add(struct list_head *node, struct list_head *head) 132239054Sae{ 133239054Sae __list_add_between(head, node, head->next); 134239054Sae} 135239054Sae 136239054Saestatic inline void 137239054Saelist_add_rcu(struct list_head *node, struct list_head *head) 138239054Sae{ 139239054Sae struct list_head *next = head->next; 140239054Sae 141239054Sae /* Initialize the new node first. */ 142239054Sae node->next = next; 143239054Sae node->prev = head; 144239054Sae 145239054Sae /* Now publish it. */ 146239054Sae atomic_store_release(&head->next, node); 147239054Sae 148239054Sae /* Fix up back pointers, not protected by RCU. */ 149239054Sae next->prev = node; 150239054Sae} 151239054Sae 152239054Saestatic inline void 153239054Saelist_add_tail(struct list_head *node, struct list_head *head) 154239054Sae{ 155239054Sae __list_add_between(head->prev, node, head); 156239054Sae} 157239054Sae 158239054Saestatic inline void 159239054Sae__list_del_entry(struct list_head *entry) 160239054Sae{ 161239054Sae entry->prev->next = entry->next; 162239054Sae entry->next->prev = entry->prev; 163239054Sae} 164239054Sae 165239054Saestatic inline void 166239054Saelist_del(struct list_head *entry) 167239054Sae{ 168239054Sae __list_del_entry(entry); 169239054Sae entry->next = (void *)(uintptr_t)1; 170239054Sae entry->prev = (void *)(uintptr_t)2; 171239054Sae} 172239054Sae 173239054Saestatic inline void 174239054Sae__list_splice_between(struct list_head *prev, const struct list_head *list, 175239054Sae struct list_head *next) 176239054Sae{ 177239054Sae struct list_head *first = list->next; 178239054Sae struct list_head *last = list->prev; 179239054Sae 180239054Sae first->prev = prev; 181239054Sae prev->next = first; 182239054Sae 183239054Sae last->next = next; 184254092Sae next->prev = last; 185239054Sae} 186239054Sae 187239054Saestatic inline void 188239054Saelist_splice(const struct list_head *list, struct list_head *head) 189239054Sae{ 190239054Sae if (!list_empty(list)) 191239054Sae __list_splice_between(head, list, head->next); 192239054Sae} 193239054Sae 194239054Saestatic inline void 195239054Saelist_splice_init(struct list_head *list, struct list_head *head) 196239054Sae{ 197239054Sae if (!list_empty(list)) { 198239054Sae __list_splice_between(head, list, head->next); 199239054Sae INIT_LIST_HEAD(list); 200239054Sae } 201239054Sae} 202239054Sae 203239054Saestatic inline void 204239054Saelist_splice_tail(const struct list_head *list, struct list_head *head) 205239054Sae{ 206254092Sae if (!list_empty(list)) 207254092Sae __list_splice_between(head->prev, list, head); 208254092Sae} 209254092Sae 210254092Saestatic inline void 211254092Saelist_splice_tail_init(struct list_head *list, struct list_head *head) 212254092Sae{ 213254092Sae if (!list_empty(list)) { 214239054Sae __list_splice_between(head->prev, list, head); 215239054Sae INIT_LIST_HEAD(list); 216239054Sae } 217239054Sae} 218239054Sae 219239054Saestatic inline void 220239054Saelist_move(struct list_head *node, struct list_head *head) 221239054Sae{ 222239054Sae list_del(node); 223239054Sae list_add(node, head); 224239054Sae} 225239054Sae 226239054Saestatic inline void 227239054Saelist_move_tail(struct list_head *node, struct list_head *head) 228239054Sae{ 229239054Sae list_del(node); 230239054Sae list_add_tail(node, head); 231239054Sae} 232239054Sae 233239054Saestatic inline void 234239054Saelist_bulk_move_tail(struct list_head *head, struct list_head *first, 235239054Sae struct list_head *last) 236239054Sae{ 237239054Sae 238239054Sae first->prev->next = last->next; 239239054Sae last->next->prev = first->prev; 240239054Sae 241239054Sae head->prev->next = first; 242239054Sae first->prev = head->prev; 243239054Sae 244239054Sae last->next = head; 245239054Sae head->prev = last; 246239054Sae} 247239054Sae 248239054Saestatic inline void 249239054Saelist_replace(struct list_head *old, struct list_head *new) 250239054Sae{ 251239054Sae new->prev = old->prev; 252239054Sae old->prev->next = new; 253239054Sae new->next = old->next; 254239054Sae old->next->prev = new; 255239054Sae} 256239054Sae 257239054Saestatic inline void 258239054Saelist_replace_init(struct list_head *old, struct list_head *new) 259239054Sae{ 260239054Sae list_replace(old, new); 261239054Sae INIT_LIST_HEAD(old); 262239054Sae} 263239054Sae 264239054Saestatic inline void 265239054Saelist_del_init(struct list_head *node) 266239054Sae{ 267239054Sae list_del(node); 268239054Sae INIT_LIST_HEAD(node); 269239054Sae} 270239054Sae 271239054Sae#define list_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 272239054Sae#define list_first_entry(PTR, TYPE, FIELD) \ 273239054Sae list_entry(list_first((PTR)), TYPE, FIELD) 274239054Sae#define list_first_entry_or_null(PTR, TYPE, FIELD) \ 275239054Sae (list_empty((PTR)) ? NULL : list_entry(list_first((PTR)), TYPE, FIELD)) 276239054Sae#define list_last_entry(PTR, TYPE, FIELD) \ 277239054Sae list_entry(list_last((PTR)), TYPE, FIELD) 278239054Sae#define list_next_entry(ENTRY, FIELD) \ 279239054Sae list_entry(list_next(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 280239054Sae#define list_prev_entry(ENTRY, FIELD) \ 281239054Sae list_entry(list_prev(&(ENTRY)->FIELD), typeof(*(ENTRY)), FIELD) 282239054Sae 283239054Sae#define list_for_each(VAR, HEAD) \ 284239054Sae for ((VAR) = list_first((HEAD)); \ 285239054Sae (VAR) != (HEAD); \ 286239054Sae (VAR) = list_next((VAR))) 287239054Sae 288239054Sae#define list_for_each_prev(VAR, HEAD) \ 289239054Sae for ((VAR) = list_last((HEAD)); \ 290239054Sae (VAR) != (HEAD); \ 291239054Sae (VAR) = list_prev((VAR))) 292239054Sae 293239054Sae#define list_for_each_safe(VAR, NEXT, HEAD) \ 294239054Sae for ((VAR) = list_first((HEAD)); \ 295239054Sae ((VAR) != (HEAD)) && ((NEXT) = list_next((VAR)), 1); \ 296239054Sae (VAR) = (NEXT)) 297239054Sae 298239054Sae#define list_safe_reset_next(VAR, NEXT, FIELD) \ 299239054Sae (NEXT) = list_next_entry(VAR, FIELD) 300239054Sae 301239054Sae#define list_for_each_entry(VAR, HEAD, FIELD) \ 302239054Sae for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 303239054Sae &(VAR)->FIELD != (HEAD); \ 304239054Sae (VAR) = list_entry(list_next(&(VAR)->FIELD), typeof(*(VAR)), \ 305239054Sae FIELD)) 306239054Sae 307239054Sae#define list_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 308239054Sae for ((VAR) = list_entry(list_first((HEAD)), typeof(*(VAR)), FIELD); \ 309239054Sae (&(VAR)->FIELD != (HEAD)) && \ 310239054Sae ((NEXT) = list_entry(list_next(&(VAR)->FIELD), \ 311239054Sae typeof(*(VAR)), FIELD), 1); \ 312239054Sae (VAR) = (NEXT)) 313239054Sae 314239054Sae#define list_for_each_entry_safe_reverse(VAR, NEXT, HEAD, FIELD) \ 315239054Sae for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \ 316239054Sae (&(VAR)->FIELD != (HEAD)) && \ 317239054Sae ((NEXT) = list_entry(list_prev(&(VAR)->FIELD), \ 318239054Sae typeof(*(VAR)), FIELD), 1); \ 319239054Sae (VAR) = (NEXT)) 320239054Sae 321239054Sae#define list_for_each_entry_reverse(VAR, HEAD, FIELD) \ 322239054Sae for ((VAR) = list_entry(list_last((HEAD)), typeof(*(VAR)), FIELD); \ 323239054Sae &(VAR)->FIELD != (HEAD); \ 324239054Sae (VAR) = list_entry(list_prev(&(VAR)->FIELD), typeof(*(VAR)), \ 325239054Sae FIELD)) 326239054Sae 327239054Sae#define list_for_each_entry_continue(VAR, HEAD, FIELD) \ 328239054Sae for ((VAR) = list_next_entry((VAR), FIELD); \ 329239054Sae &(VAR)->FIELD != (HEAD); \ 330239054Sae (VAR) = list_next_entry((VAR), FIELD)) 331239054Sae 332239054Sae#define list_for_each_entry_continue_reverse(VAR, HEAD, FIELD) \ 333239054Sae for ((VAR) = list_prev_entry((VAR), FIELD); \ 334239054Sae &(VAR)->FIELD != (HEAD); \ 335239054Sae (VAR) = list_prev_entry((VAR), FIELD)) 336239054Sae 337239054Sae#define list_for_each_entry_from(VAR, HEAD, FIELD) \ 338239054Sae for (; \ 339239054Sae (&(VAR)->FIELD != (HEAD)); \ 340239054Sae (VAR) = list_next_entry((VAR), FIELD)) 341239054Sae 342239054Sae#define list_for_each_entry_from_reverse(VAR, HEAD, FIELD) \ 343239054Sae for (; \ 344239054Sae (&(VAR)->FIELD != (HEAD)); \ 345239054Sae (VAR) = list_prev_entry((VAR), FIELD)) 346239054Sae 347239054Sae#define list_for_each_entry_safe_from(VAR, NEXT, HEAD, FIELD) \ 348239054Sae for (; \ 349239054Sae (&(VAR)->FIELD != (HEAD)) && \ 350239054Sae ((NEXT) = list_next_entry((VAR), FIELD)); \ 351239054Sae (VAR) = (NEXT)) 352239054Sae 353239054Sae/* 354239054Sae * `H'ead-only/`H'ash-table doubly-linked lists. 355239054Sae */ 356239054Sae 357239054Sae#define hlist_head pslist_head 358239054Sae#define hlist_node pslist_entry 359239054Sae 360239054Sae#define HLIST_HEAD_INIT PSLIST_INITIALIZER 361239054Sae#define INIT_HLIST_HEAD PSLIST_INIT 362239054Sae#define hlist_empty(h) (pslist_writer_first(h) == NULL) 363239054Sae#define hlist_first pslist_writer_first 364239054Sae#define hlist_next pslist_writer_next 365239054Sae 366239054Saestatic inline void 367239054Saehlist_add_head(struct hlist_node *node, struct hlist_head *head) 368239054Sae{ 369239054Sae 370239054Sae pslist_entry_init(node); 371239054Sae pslist_writer_insert_head(head, node); 372239054Sae} 373239054Sae 374239054Saestatic inline void 375239054Saehlist_del(struct hlist_node *node) 376239054Sae{ 377239054Sae 378239325Sae pslist_writer_remove(node); 379239054Sae /* XXX abstraction violation */ 380239054Sae node->ple_prevp = _PSLIST_POISON; 381239294Sae} 382239054Sae 383239054Saestatic inline void 384239054Saehlist_del_init(struct hlist_node *node) 385239054Sae{ 386239054Sae 387239054Sae /* XXX abstraction violation */ 388239054Sae if (node->ple_prevp != NULL) 389239054Sae pslist_writer_remove(node); 390239054Sae} 391239054Sae 392239054Sae#define hlist_entry(PTR, TYPE, FIELD) container_of(PTR, TYPE, FIELD) 393239054Sae#define hlist_for_each(VAR, HEAD) \ 394239054Sae for ((VAR) = hlist_first(HEAD); (VAR) != NULL; (VAR) = hlist_next(VAR)) 395239054Sae#define hlist_for_each_safe(VAR, NEXT, HEAD) \ 396239054Sae for ((VAR) = hlist_first(HEAD); \ 397239088Sae (VAR) != NULL && ((NEXT) = hlist_next(HEAD), 1); \ 398239054Sae (VAR) = (NEXT)) 399239054Sae#define hlist_for_each_entry(VAR, HEAD, FIELD) \ 400239054Sae for ((VAR) = (hlist_first(HEAD) == NULL ? NULL : \ 401239054Sae hlist_entry(hlist_first(HEAD), typeof(*(VAR)), \ 402239054Sae FIELD)); \ 403239054Sae (VAR) != NULL; \ 404239054Sae (VAR) = (hlist_next(&(VAR)->FIELD) == NULL ? NULL : \ 405239054Sae hlist_entry(hlist_next(&(VAR)->FIELD), typeof(*(VAR)),\ 406239054Sae FIELD))) 407239054Sae 408239054Sae#define hlist_for_each_entry_safe(VAR, NEXT, HEAD, FIELD) \ 409239054Sae for ((VAR) = (hlist_first(HEAD) == NULL ? NULL : \ 410239054Sae hlist_entry(hlist_first(HEAD), typeof(*(VAR)), \ 411239054Sae FIELD)); \ 412239054Sae ((VAR) != NULL && \ 413239054Sae ((NEXT) = hlist_next(&(VAR)->FIELD), 1)); \ 414239054Sae (VAR) = hlist_entry((NEXT), typeof(*(VAR)), FIELD)) 415239054Sae 416239054Saestatic inline void 417239054Saehlist_add_behind_rcu(struct hlist_node *node, struct hlist_node *prev) 418239054Sae{ 419239054Sae 420239054Sae pslist_entry_init(node); 421239054Sae pslist_writer_insert_after(prev, node); 422239054Sae} 423239054Sae 424239054Saestatic inline void 425239054Saehlist_add_head_rcu(struct hlist_node *node, struct hlist_head *head) 426239054Sae{ 427239054Sae 428239054Sae pslist_entry_init(node); 429239054Sae pslist_writer_insert_head(head, node); 430239054Sae} 431239054Sae 432239054Sae#define hlist_del_init_rcu hlist_del_init /* no special needs */ 433239054Sae 434239054Sae#define hlist_first_rcu pslist_reader_first 435239054Sae#define hlist_next_rcu pslist_reader_next 436239054Sae 437239054Sae#define hlist_for_each_entry_rcu(VAR, HEAD, FIELD) \ 438239054Sae for ((VAR) = (hlist_first_rcu(HEAD) == NULL ? NULL : \ 439239054Sae hlist_entry(hlist_first_rcu(HEAD), typeof(*(VAR)), \ 440239054Sae FIELD)); \ 441239054Sae (VAR) != NULL; \ 442239054Sae (VAR) = (hlist_next_rcu(&(VAR)->FIELD) == NULL ? NULL : \ 443239054Sae hlist_entry(hlist_next_rcu(&(VAR)->FIELD), \ 444239054Sae typeof(*(VAR)), FIELD))) 445239054Sae 446239054Sae#endif /* _LINUX_LIST_H_ */ 447239054Sae