1.\" 2.\" 3.\" Copyright (c) 2009, Sun Microsystems Inc. All Rights Reserved. 4.\" Copyright 2022 Oxide Computer Company 5.\" 6.\" The contents of this file are subject to the terms of the 7.\" Common Development and Distribution License (the "License"). 8.\" You may not use this file except in compliance with the License. 9.\" 10.\" You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 11.\" or http://www.opensolaris.org/os/licensing. 12.\" See the License for the specific language governing permissions 13.\" and limitations under the License. 14.\" 15.\" When distributing Covered Code, include this CDDL HEADER in each 16.\" file and include the License file at usr/src/OPENSOLARIS.LICENSE. 17.\" If applicable, add the following below this CDDL HEADER, with the 18.\" fields enclosed by brackets "[]" replaced with your own identifying 19.\" information: Portions Copyright [yyyy] [name of copyright owner] 20.\" 21.Dd January 16, 2022 22.Dt LIST_CREATE 9F 23.Os 24.Sh NAME 25.Nm list_create , 26.Nm list_destroy , 27.Nm list_insert_after , 28.Nm list_insert_before , 29.Nm list_insert_head , 30.Nm list_insert_tail , 31.Nm list_remove , 32.Nm list_remove_head , 33.Nm list_remove_tail , 34.Nm list_head , 35.Nm list_tail , 36.Nm list_next , 37.Nm list_prev , 38.Nm list_is_empty, , 39.Nm list_link_init , 40.Nm list_link_active , 41.Nm list_move_tail , 42.Nm list_link_replace 43.Nd list functions 44.Sh SYNOPSIS 45.In sys/list.h 46.Ft void 47.Fo list_create 48.Fa "list_t *list" 49.Fa "size_t size" 50.Fa "size_t offset" 51.Fc 52.Ft void 53.Fo list_destroy 54.Fa "list_t *list" 55.Fc 56.Ft void 57.Fo list_insert_after 58.Fa "list_t *list" 59.Fa "void *reference_item" 60.Fa "void *new_item" 61.Fc 62.Ft void 63.Fo list_insert_before 64.Fa "list_t *list" 65.Fa "void *reference_item" 66.Fa "void *new_item" 67.Fc 68.Ft void 69.Fo list_insert_head 70.Fa "list_t *list*" 71.Fa "void *new_item" 72.Fc 73.Ft void 74.Fo list_insert_tail 75.Fa "list_t *list" 76.Fa "void *new_item" 77.Fc 78.Ft void 79.Fo list_remove 80.Fa "list_t *list" 81.Fa "void *item" 82.Fc 83.Ft "void *" 84.Fo list_remove_head 85.Fa "list_t *list" 86.Fc 87.Ft "void *" 88.Fo list_remove_tail 89.Fa "list_t *list" 90.Fc 91.Ft "void *" 92.Fo list_head 93.Fa "list_t *list" 94.Fc 95.Ft "void *" 96.Fo list_tail 97.Fa "list_t *list" 98.Fc 99.Ft "void *" 100.Fo list_next 101.Fa "list_t *list" 102.Fa "void *reference_item" 103.Fc 104.Ft "void *" 105.Fo list_prev 106.Fa "list_t *list" 107.Fa "void *reference_item" 108.Fc 109.Ft int 110.Fo list_is_empty 111.Fa "list_t *list" 112.Fc 113.Ft void 114.Fo list_link_init 115.Fa "list_node_t *node" 116.Fc 117.Ft int 118.Fo list_link_active 119.Fa "list_node_t *node" 120.Fc 121.Ft void 122.Fo list_move_tail 123.Fa "list_t *dst" 124.Fa "list_t *src" 125.Fc 126.Ft void 127.Fo list_link_replace 128.Fa "list_node_t *lold" 129.Fa "list_node_t *lnew" 130.Fc 131.Sh DESCRIPTION 132These functions provide a generic doubly-linked list implementation. 133To utilize it, simply embed a 134.Vt list_node_t 135field in the structures that will constitute the linked list elements and pass 136the 137.Vt list_node_t 138field offset to 139.Fn list_create 140in the appropriate 141parameter 142.Pq see below . 143A single 144.Vt list_node_t 145field can only be used in a single list simultaneously, so to add a structure to 146multiple lists, embed multiple 147.Vt list_node_t 148fields in your user structure. 149.Pp 150Please note that a 151.Vt list_node_t 152contains pointers back to its parent 153.Vt list_t 154so you cannot copy the 155.Vt list_t 156around once it has been initialized. 157In particular, this kind of construct will not work: 158.Bd -literal -offset indent 159struct { list_t l; } a, b; 160list_create(&a.l, ...); 161b = a; <= This will break the list in `b', as the `l' element 162 in `a' got copied to a different memory address. 163.Ed 164.Pp 165To do this you must move the list items to the new list using functions 166such as 167.Fn list_move_tail . 168.Pp 169The 170.Fn list_create 171function initializes a new list. 172The driver supplies the storage for the list handle, the size of an individual 173element, and the offset of a 174.Vt list_node_t 175within the element to use for the links of the list. 176.Pp 177The 178.Fn list_destroy 179function destroys the list handle, including freeing any resources that may have 180been internally allocated for the list. 181The list must be empty when this function is called. 182.Pp 183The 184.Fn list_insert_after 185and 186.Fn list_insert_before 187functions insert 188.Fa new_item 189into the linked list at a location after or before the reference item, which 190must already be on the list. 191.Pp 192The 193.Fn list_insert_head 194and 195.Fn list_insert_tail 196functions insert the 197.Fa new_item 198on the list at either the head or tail of the list. 199The head is the first item, the tail is the last item. 200.Pp 201The 202.Fn list_remove 203function removes the item from the list. 204.Pp 205The 206.Fn list_remove_head 207and 208.Fn list_remove_tail 209functions remove the head 210.Pq first 211or tail 212.Pq last 213item from the list. 214The item removed is returned to the caller. 215If the list is empty when these functions are called, then no change is made and 216.Dv NULL 217is returned to the caller. 218.Pp 219The 220.Fn list_head 221and 222.Fn list_tail 223functions simply return the head 224.Pq first 225or tail 226.Pq last 227item on the list. 228.Dv NULL 229is returned if the list is empty. 230.Pp 231The 232.Fn list_next 233and 234.Fn list_prev 235functions return the next or previous item in the list, relative to the named 236reference item which must be linked on the list. 237If the referenced item is either the last entry in the list for 238.Fn list_next 239or the first entry in the list for 240.Fn list_prev , 241then the functions will return 242.Dv NULL . 243This is useful for iterating over a list with the following pattern: 244.Bd -literal -offset indent 245list_t list_t; 246\&... 247for (foo_t *foo = list_head(&list_t); foo != NULL; 248 foo = list_next(&list_t, foo)) { 249 /* Process each entry of the list */ 250} 251 252for (foo_t *foo = list_tail(&list_t); foo != NULL; 253 foo = list_prev(&list_t, foo)) { 254 /* Same thing, but in reverse */ 255} 256.Ed 257.Pp 258The 259.Fn list_is_empty 260function returns 0 if the list has items in it, or non-zero otherwise. 261.Pp 262The 263.Fn list_link_init 264function initializes the 265.Vt list_node_t . 266It is functionally equivalent to 267.Fo bzero 268.Fa "node" 269.Fa "sizeof (*node)" 270.Fc ; . 271.Pp 272The 273.Fn list_link_active 274function returns non-zero if the node is on an active list. 275.Pp 276The 277.Fn list_move_tail 278function is used to append the items on the 279.Fa src 280list to the end of the 281.Fa dst 282list. 283It is mandatory that the two lists were initialized using identical size and 284offset parameters. 285Upon completion, the 286.Fa src 287list will be empty. 288.Pp 289The 290.Fn list_link_replace 291function replaces 292.Fa lold 293node on an active list with the 294.Fa lnew 295node. 296When the function is called the 297.Fa lnew 298node must not be linked on any list. 299Upon completion the 300.Fa lold 301node will be left unlinked from any list. 302.Sh INTERFACE STABILITY 303.Sy Committed 304