19023fe69SRobert Mustacchi.\" 29023fe69SRobert Mustacchi.\" 3c10c16deSRichard Lowe.\" Copyright (c) 2009, Sun Microsystems Inc. All Rights Reserved. 49023fe69SRobert Mustacchi.\" Copyright 2022 Oxide Computer Company 59023fe69SRobert Mustacchi.\" 69023fe69SRobert Mustacchi.\" The contents of this file are subject to the terms of the 79023fe69SRobert Mustacchi.\" Common Development and Distribution License (the "License"). 89023fe69SRobert Mustacchi.\" You may not use this file except in compliance with the License. 99023fe69SRobert Mustacchi.\" 109023fe69SRobert Mustacchi.\" You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 119023fe69SRobert Mustacchi.\" or http://www.opensolaris.org/os/licensing. 129023fe69SRobert Mustacchi.\" See the License for the specific language governing permissions 139023fe69SRobert Mustacchi.\" and limitations under the License. 149023fe69SRobert Mustacchi.\" 159023fe69SRobert Mustacchi.\" When distributing Covered Code, include this CDDL HEADER in each 169023fe69SRobert Mustacchi.\" file and include the License file at usr/src/OPENSOLARIS.LICENSE. 179023fe69SRobert Mustacchi.\" If applicable, add the following below this CDDL HEADER, with the 189023fe69SRobert Mustacchi.\" fields enclosed by brackets "[]" replaced with your own identifying 199023fe69SRobert Mustacchi.\" information: Portions Copyright [yyyy] [name of copyright owner] 209023fe69SRobert Mustacchi.\" 219023fe69SRobert Mustacchi.Dd January 16, 2022 229023fe69SRobert Mustacchi.Dt LIST_CREATE 9F 239023fe69SRobert Mustacchi.Os 249023fe69SRobert Mustacchi.Sh NAME 259023fe69SRobert Mustacchi.Nm list_create , 269023fe69SRobert Mustacchi.Nm list_destroy , 279023fe69SRobert Mustacchi.Nm list_insert_after , 289023fe69SRobert Mustacchi.Nm list_insert_before , 299023fe69SRobert Mustacchi.Nm list_insert_head , 309023fe69SRobert Mustacchi.Nm list_insert_tail , 319023fe69SRobert Mustacchi.Nm list_remove , 329023fe69SRobert Mustacchi.Nm list_remove_head , 339023fe69SRobert Mustacchi.Nm list_remove_tail , 349023fe69SRobert Mustacchi.Nm list_head , 359023fe69SRobert Mustacchi.Nm list_tail , 369023fe69SRobert Mustacchi.Nm list_next , 379023fe69SRobert Mustacchi.Nm list_prev , 389023fe69SRobert Mustacchi.Nm list_is_empty, , 399023fe69SRobert Mustacchi.Nm list_link_init , 409023fe69SRobert Mustacchi.Nm list_link_active , 419023fe69SRobert Mustacchi.Nm list_move_tail , 429023fe69SRobert Mustacchi.Nm list_link_replace 439023fe69SRobert Mustacchi.Nd list functions 449023fe69SRobert Mustacchi.Sh SYNOPSIS 459023fe69SRobert Mustacchi.In sys/list.h 469023fe69SRobert Mustacchi.Ft void 479023fe69SRobert Mustacchi.Fo list_create 489023fe69SRobert Mustacchi.Fa "list_t *list" 499023fe69SRobert Mustacchi.Fa "size_t size" 509023fe69SRobert Mustacchi.Fa "size_t offset" 519023fe69SRobert Mustacchi.Fc 529023fe69SRobert Mustacchi.Ft void 539023fe69SRobert Mustacchi.Fo list_destroy 549023fe69SRobert Mustacchi.Fa "list_t *list" 559023fe69SRobert Mustacchi.Fc 569023fe69SRobert Mustacchi.Ft void 579023fe69SRobert Mustacchi.Fo list_insert_after 589023fe69SRobert Mustacchi.Fa "list_t *list" 599023fe69SRobert Mustacchi.Fa "void *reference_item" 609023fe69SRobert Mustacchi.Fa "void *new_item" 619023fe69SRobert Mustacchi.Fc 629023fe69SRobert Mustacchi.Ft void 639023fe69SRobert Mustacchi.Fo list_insert_before 649023fe69SRobert Mustacchi.Fa "list_t *list" 659023fe69SRobert Mustacchi.Fa "void *reference_item" 669023fe69SRobert Mustacchi.Fa "void *new_item" 679023fe69SRobert Mustacchi.Fc 689023fe69SRobert Mustacchi.Ft void 699023fe69SRobert Mustacchi.Fo list_insert_head 709023fe69SRobert Mustacchi.Fa "list_t *list*" 719023fe69SRobert Mustacchi.Fa "void *new_item" 729023fe69SRobert Mustacchi.Fc 739023fe69SRobert Mustacchi.Ft void 749023fe69SRobert Mustacchi.Fo list_insert_tail 759023fe69SRobert Mustacchi.Fa "list_t *list" 769023fe69SRobert Mustacchi.Fa "void *new_item" 779023fe69SRobert Mustacchi.Fc 789023fe69SRobert Mustacchi.Ft void 799023fe69SRobert Mustacchi.Fo list_remove 809023fe69SRobert Mustacchi.Fa "list_t *list" 819023fe69SRobert Mustacchi.Fa "void *item" 829023fe69SRobert Mustacchi.Fc 839023fe69SRobert Mustacchi.Ft "void *" 849023fe69SRobert Mustacchi.Fo list_remove_head 859023fe69SRobert Mustacchi.Fa "list_t *list" 869023fe69SRobert Mustacchi.Fc 879023fe69SRobert Mustacchi.Ft "void *" 889023fe69SRobert Mustacchi.Fo list_remove_tail 899023fe69SRobert Mustacchi.Fa "list_t *list" 909023fe69SRobert Mustacchi.Fc 919023fe69SRobert Mustacchi.Ft "void *" 929023fe69SRobert Mustacchi.Fo list_head 939023fe69SRobert Mustacchi.Fa "list_t *list" 949023fe69SRobert Mustacchi.Fc 959023fe69SRobert Mustacchi.Ft "void *" 969023fe69SRobert Mustacchi.Fo list_tail 979023fe69SRobert Mustacchi.Fa "list_t *list" 989023fe69SRobert Mustacchi.Fc 999023fe69SRobert Mustacchi.Ft "void *" 1009023fe69SRobert Mustacchi.Fo list_next 1019023fe69SRobert Mustacchi.Fa "list_t *list" 1029023fe69SRobert Mustacchi.Fa "void *reference_item" 1039023fe69SRobert Mustacchi.Fc 1049023fe69SRobert Mustacchi.Ft "void *" 1059023fe69SRobert Mustacchi.Fo list_prev 1069023fe69SRobert Mustacchi.Fa "list_t *list" 1079023fe69SRobert Mustacchi.Fa "void *reference_item" 1089023fe69SRobert Mustacchi.Fc 1099023fe69SRobert Mustacchi.Ft int 1109023fe69SRobert Mustacchi.Fo list_is_empty 1119023fe69SRobert Mustacchi.Fa "list_t *list" 1129023fe69SRobert Mustacchi.Fc 1139023fe69SRobert Mustacchi.Ft void 1149023fe69SRobert Mustacchi.Fo list_link_init 1159023fe69SRobert Mustacchi.Fa "list_node_t *node" 1169023fe69SRobert Mustacchi.Fc 1179023fe69SRobert Mustacchi.Ft int 1189023fe69SRobert Mustacchi.Fo list_link_active 1199023fe69SRobert Mustacchi.Fa "list_node_t *node" 1209023fe69SRobert Mustacchi.Fc 1219023fe69SRobert Mustacchi.Ft void 1229023fe69SRobert Mustacchi.Fo list_move_tail 1239023fe69SRobert Mustacchi.Fa "list_t *dst" 1249023fe69SRobert Mustacchi.Fa "list_t *src" 1259023fe69SRobert Mustacchi.Fc 1269023fe69SRobert Mustacchi.Ft void 1279023fe69SRobert Mustacchi.Fo list_link_replace 1289023fe69SRobert Mustacchi.Fa "list_node_t *lold" 1299023fe69SRobert Mustacchi.Fa "list_node_t *lnew" 1309023fe69SRobert Mustacchi.Fc 1319023fe69SRobert Mustacchi.Sh DESCRIPTION 1329023fe69SRobert MustacchiThese functions provide a generic doubly-linked list implementation. 1339023fe69SRobert MustacchiTo utilize it, simply embed a 1349023fe69SRobert Mustacchi.Vt list_node_t 1359023fe69SRobert Mustacchifield in the structures that will constitute the linked list elements and pass 1369023fe69SRobert Mustacchithe 1379023fe69SRobert Mustacchi.Vt list_node_t 1389023fe69SRobert Mustacchifield offset to 1399023fe69SRobert Mustacchi.Fn list_create 1409023fe69SRobert Mustacchiin the appropriate 1419023fe69SRobert Mustacchiparameter 1429023fe69SRobert Mustacchi.Pq see below . 1439023fe69SRobert MustacchiA single 1449023fe69SRobert Mustacchi.Vt list_node_t 1459023fe69SRobert Mustacchifield can only be used in a single list simultaneously, so to add a structure to 1469023fe69SRobert Mustacchimultiple lists, embed multiple 1479023fe69SRobert Mustacchi.Vt list_node_t 1489023fe69SRobert Mustacchifields in your user structure. 1499023fe69SRobert Mustacchi.Pp 1509023fe69SRobert MustacchiPlease note that a 1519023fe69SRobert Mustacchi.Vt list_node_t 1529023fe69SRobert Mustacchicontains pointers back to its parent 1539023fe69SRobert Mustacchi.Vt list_t 1549023fe69SRobert Mustacchiso you cannot copy the 1559023fe69SRobert Mustacchi.Vt list_t 1569023fe69SRobert Mustacchiaround once it has been initialized. 1579023fe69SRobert MustacchiIn particular, this kind of construct will not work: 1589023fe69SRobert Mustacchi.Bd -literal -offset indent 1593bc3cac5SSaso Kiselkovstruct { list_t l; } a, b; 1603bc3cac5SSaso Kiselkovlist_create(&a.l, ...); 1613bc3cac5SSaso Kiselkovb = a; <= This will break the list in `b', as the `l' element 1623bc3cac5SSaso Kiselkov in `a' got copied to a different memory address. 1639023fe69SRobert Mustacchi.Ed 1649023fe69SRobert Mustacchi.Pp 1653bc3cac5SSaso KiselkovTo do this you must move the list items to the new list using functions 1669023fe69SRobert Mustacchisuch as 1679023fe69SRobert Mustacchi.Fn list_move_tail . 1689023fe69SRobert Mustacchi.Pp 1699023fe69SRobert MustacchiThe 1709023fe69SRobert Mustacchi.Fn list_create 1719023fe69SRobert Mustacchifunction initializes a new list. 1729023fe69SRobert MustacchiThe driver supplies the storage for the list handle, the size of an individual 1739023fe69SRobert Mustacchielement, and the offset of a 1749023fe69SRobert Mustacchi.Vt list_node_t 1759023fe69SRobert Mustacchiwithin the element to use for the links of the list. 1769023fe69SRobert Mustacchi.Pp 1779023fe69SRobert MustacchiThe 1789023fe69SRobert Mustacchi.Fn list_destroy 1799023fe69SRobert Mustacchifunction destroys the list handle, including freeing any resources that may have 1809023fe69SRobert Mustacchibeen internally allocated for the list. 1819023fe69SRobert MustacchiThe list must be empty when this function is called. 1829023fe69SRobert Mustacchi.Pp 1839023fe69SRobert MustacchiThe 1849023fe69SRobert Mustacchi.Fn list_insert_after 1859023fe69SRobert Mustacchiand 1869023fe69SRobert Mustacchi.Fn list_insert_before 1879023fe69SRobert Mustacchifunctions insert 1889023fe69SRobert Mustacchi.Fa new_item 1899023fe69SRobert Mustacchiinto the linked list at a location after or before the reference item, which 1909023fe69SRobert Mustacchimust already be on the list. 1919023fe69SRobert Mustacchi.Pp 1929023fe69SRobert MustacchiThe 1939023fe69SRobert Mustacchi.Fn list_insert_head 1949023fe69SRobert Mustacchiand 1959023fe69SRobert Mustacchi.Fn list_insert_tail 1969023fe69SRobert Mustacchifunctions insert the 1979023fe69SRobert Mustacchi.Fa new_item 1989023fe69SRobert Mustacchion the list at either the head or tail of the list. 1999023fe69SRobert MustacchiThe head is the first item, the tail is the last item. 2009023fe69SRobert Mustacchi.Pp 2019023fe69SRobert MustacchiThe 2029023fe69SRobert Mustacchi.Fn list_remove 2039023fe69SRobert Mustacchifunction removes the item from the list. 2049023fe69SRobert Mustacchi.Pp 2059023fe69SRobert MustacchiThe 2069023fe69SRobert Mustacchi.Fn list_remove_head 2079023fe69SRobert Mustacchiand 2089023fe69SRobert Mustacchi.Fn list_remove_tail 2099023fe69SRobert Mustacchifunctions remove the head 2109023fe69SRobert Mustacchi.Pq first 2119023fe69SRobert Mustacchior tail 2129023fe69SRobert Mustacchi.Pq last 2139023fe69SRobert Mustacchiitem from the list. 2149023fe69SRobert MustacchiThe item removed is returned to the caller. 2159023fe69SRobert MustacchiIf the list is empty when these functions are called, then no change is made and 2169023fe69SRobert Mustacchi.Dv NULL 2179023fe69SRobert Mustacchiis returned to the caller. 2189023fe69SRobert Mustacchi.Pp 2199023fe69SRobert MustacchiThe 2209023fe69SRobert Mustacchi.Fn list_head 2219023fe69SRobert Mustacchiand 2229023fe69SRobert Mustacchi.Fn list_tail 2239023fe69SRobert Mustacchifunctions simply return the head 2249023fe69SRobert Mustacchi.Pq first 2259023fe69SRobert Mustacchior tail 2269023fe69SRobert Mustacchi.Pq last 2279023fe69SRobert Mustacchiitem on the list. 2289023fe69SRobert Mustacchi.Dv NULL 2299023fe69SRobert Mustacchiis returned if the list is empty. 2309023fe69SRobert Mustacchi.Pp 2319023fe69SRobert MustacchiThe 2329023fe69SRobert Mustacchi.Fn list_next 2339023fe69SRobert Mustacchiand 2349023fe69SRobert Mustacchi.Fn list_prev 2359023fe69SRobert Mustacchifunctions return the next or previous item in the list, relative to the named 2369023fe69SRobert Mustacchireference item which must be linked on the list. 237*597b3036SRobert MustacchiIf the referenced item is either the last entry in the list for 238*597b3036SRobert Mustacchi.Fn list_next 239*597b3036SRobert Mustacchior the first entry in the list for 240*597b3036SRobert Mustacchi.Fn list_prev , 241*597b3036SRobert Mustacchithen the functions will return 242*597b3036SRobert Mustacchi.Dv NULL . 243*597b3036SRobert MustacchiThis is useful for iterating over a list with the following pattern: 244*597b3036SRobert Mustacchi.Bd -literal -offset indent 245*597b3036SRobert Mustacchilist_t list_t; 246*597b3036SRobert Mustacchi\&... 247*597b3036SRobert Mustacchifor (foo_t *foo = list_head(&list_t); foo != NULL; 248*597b3036SRobert Mustacchi foo = list_next(&list_t, foo)) { 249*597b3036SRobert Mustacchi /* Process each entry of the list */ 250*597b3036SRobert Mustacchi} 251*597b3036SRobert Mustacchi 252*597b3036SRobert Mustacchifor (foo_t *foo = list_tail(&list_t); foo != NULL; 253*597b3036SRobert Mustacchi foo = list_prev(&list_t, foo)) { 254*597b3036SRobert Mustacchi /* Same thing, but in reverse */ 255*597b3036SRobert Mustacchi} 256*597b3036SRobert Mustacchi.Ed 2579023fe69SRobert Mustacchi.Pp 2589023fe69SRobert MustacchiThe 2599023fe69SRobert Mustacchi.Fn list_is_empty 2609023fe69SRobert Mustacchifunction returns 0 if the list has items in it, or non-zero otherwise. 2619023fe69SRobert Mustacchi.Pp 2629023fe69SRobert MustacchiThe 2639023fe69SRobert Mustacchi.Fn list_link_init 2649023fe69SRobert Mustacchifunction initializes the 2659023fe69SRobert Mustacchi.Vt list_node_t . 2669023fe69SRobert MustacchiIt is functionally equivalent to 2679023fe69SRobert Mustacchi.Fo bzero 2689023fe69SRobert Mustacchi.Fa "node" 2699023fe69SRobert Mustacchi.Fa "sizeof (*node)" 2709023fe69SRobert Mustacchi.Fc ; . 2719023fe69SRobert Mustacchi.Pp 2729023fe69SRobert MustacchiThe 2739023fe69SRobert Mustacchi.Fn list_link_active 2749023fe69SRobert Mustacchifunction returns non-zero if the node is on an active list. 2759023fe69SRobert Mustacchi.Pp 2769023fe69SRobert MustacchiThe 2779023fe69SRobert Mustacchi.Fn list_move_tail 2789023fe69SRobert Mustacchifunction is used to append the items on the 2799023fe69SRobert Mustacchi.Fa src 2809023fe69SRobert Mustacchilist to the end of the 2819023fe69SRobert Mustacchi.Fa dst 282c10c16deSRichard Lowelist. 2839023fe69SRobert MustacchiIt is mandatory that the two lists were initialized using identical size and 2849023fe69SRobert Mustacchioffset parameters. 2859023fe69SRobert MustacchiUpon completion, the 2869023fe69SRobert Mustacchi.Fa src 2879023fe69SRobert Mustacchilist will be empty. 2889023fe69SRobert Mustacchi.Pp 2899023fe69SRobert MustacchiThe 2909023fe69SRobert Mustacchi.Fn list_link_replace 2919023fe69SRobert Mustacchifunction replaces 2929023fe69SRobert Mustacchi.Fa lold 2939023fe69SRobert Mustacchinode on an active list with the 2949023fe69SRobert Mustacchi.Fa lnew 2959023fe69SRobert Mustacchinode. 2969023fe69SRobert MustacchiWhen the function is called the 2979023fe69SRobert Mustacchi.Fa lnew 2989023fe69SRobert Mustacchinode must not be linked on any list. 2999023fe69SRobert MustacchiUpon completion the 3009023fe69SRobert Mustacchi.Fa lold 3019023fe69SRobert Mustacchinode will be left unlinked from any list. 3029023fe69SRobert Mustacchi.Sh INTERFACE STABILITY 3039023fe69SRobert Mustacchi.Sy Committed 304