diff options
Diffstat (limited to 'man3/slist.3')
| -rw-r--r-- | man3/slist.3 | 319 |
1 files changed, 0 insertions, 319 deletions
diff --git a/man3/slist.3 b/man3/slist.3 deleted file mode 100644 index bbfc8de18..000000000 --- a/man3/slist.3 +++ /dev/null @@ -1,319 +0,0 @@ -.\" Copyright (c) 1993 -.\" The Regents of the University of California. All rights reserved. -.\" and Copyright (c) 2020 by Alejandro Colomar <alx@kernel.org> -.\" -.\" SPDX-License-Identifier: BSD-3-Clause -.\" -.\" -.TH SLIST 3 (date) "Linux man-pages (unreleased)" -.SH NAME -SLIST_EMPTY, -SLIST_ENTRY, -SLIST_FIRST, -SLIST_FOREACH, -.\"SLIST_FOREACH_FROM, -.\"SLIST_FOREACH_FROM_SAFE, -.\"SLIST_FOREACH_SAFE, -SLIST_HEAD, -SLIST_HEAD_INITIALIZER, -SLIST_INIT, -SLIST_INSERT_AFTER, -SLIST_INSERT_HEAD, -SLIST_NEXT, -SLIST_REMOVE, -.\"SLIST_REMOVE_AFTER, -SLIST_REMOVE_HEAD -.\"SLIST_SWAP -\- implementation of a singly linked list -.SH LIBRARY -Standard C library -.RI ( libc ", " \-lc ) -.SH SYNOPSIS -.nf -.B #include <sys/queue.h> -.PP -.B SLIST_ENTRY(TYPE); -.PP -.B SLIST_HEAD(HEADNAME, TYPE); -.BI "SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD " head ); -.BI "void SLIST_INIT(SLIST_HEAD *" head ); -.PP -.BI "int SLIST_EMPTY(SLIST_HEAD *" head ); -.PP -.BI "void SLIST_INSERT_HEAD(SLIST_HEAD *" head , -.BI " struct TYPE *" elm ", SLIST_ENTRY " NAME ); -.BI "void SLIST_INSERT_AFTER(struct TYPE *" listelm , -.BI " struct TYPE *" elm ", SLIST_ENTRY " NAME ); -.PP -.BI "struct TYPE *SLIST_FIRST(SLIST_HEAD *" head ); -.BI "struct TYPE *SLIST_NEXT(struct TYPE *" elm ", SLIST_ENTRY " NAME ); -.PP -.BI "SLIST_FOREACH(struct TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME ); -.\" .BI "SLIST_FOREACH_FROM(struct TYPE *" var ", SLIST_HEAD *" head , -.\" .BI " SLIST_ENTRY " NAME ); -.\" .PP -.\" .BI "SLIST_FOREACH_SAFE(struct TYPE *" var ", SLIST_HEAD *" head , -.\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var ); -.\" .BI "SLIST_FOREACH_FROM_SAFE(struct TYPE *" var ", SLIST_HEAD *" head , -.\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var ); -.PP -.BI "void SLIST_REMOVE(SLIST_HEAD *" head ", struct TYPE *" elm , -.BI " SLIST_ENTRY " NAME ); -.BI "void SLIST_REMOVE_HEAD(SLIST_HEAD *" head , -.BI " SLIST_ENTRY " NAME ); -.\" .BI "void SLIST_REMOVE_AFTER(struct TYPE *" elm , -.\" .BI " SLIST_ENTRY " NAME ); -.\" .PP -.\" .BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 , -.\" .BI " SLIST_ENTRY " NAME ); -.fi -.SH DESCRIPTION -These macros define and operate on doubly linked lists. -.PP -In the macro definitions, -.I TYPE -is the name of a user-defined structure, -that must contain a field of type -.IR SLIST_ENTRY , -named -.IR NAME . -The argument -.I HEADNAME -is the name of a user-defined structure -that must be declared using the macro -.BR SLIST_HEAD (). -.SS Creation -A singly linked list is headed by a structure defined by the -.BR SLIST_HEAD () -macro. -This structure contains a single pointer to the first element on the list. -The elements are singly linked -for minimum space and pointer manipulation overhead -at the expense of O(n) removal for arbitrary elements. -New elements can be added to the list -after an existing element -or at the head of the list. -An -.I SLIST_HEAD -structure is declared as follows: -.PP -.in +4 -.EX -SLIST_HEAD(HEADNAME, TYPE) head; -.EE -.in -.PP -where -.I struct HEADNAME -is the structure to be defined, and -.I struct TYPE -is the type of the elements to be linked into the list. -A pointer to the head of the list can later be declared as: -.PP -.in +4 -.EX -struct HEADNAME *headp; -.EE -.in -.PP -(The names -.I head -and -.I headp -are user selectable.) -.PP -.BR SLIST_ENTRY () -declares a structure that connects the elements in -the list. -.PP -.BR SLIST_HEAD_INITIALIZER () -evaluates to an initializer for the list -.IR head . -.PP -.BR SLIST_INIT () -initializes the list referenced by -.IR head . -.PP -.BR SLIST_EMPTY () -evaluates to true if there are no elements in the list. -.SS Insertion -.BR SLIST_INSERT_HEAD () -inserts the new element -.I elm -at the head of the list. -.PP -.BR SLIST_INSERT_AFTER () -inserts the new element -.I elm -after the element -.IR listelm . -.SS Traversal -.BR SLIST_FIRST () -returns the first element in the list, or NULL if the list is empty. -.PP -.BR SLIST_NEXT () -returns the next element in the list. -.PP -.BR SLIST_FOREACH () -traverses the list referenced by -.I head -in the forward direction, -assigning each element in turn to -.IR var . -.\" .PP -.\" .BR SLIST_FOREACH_FROM () -.\" behaves identically to -.\" .BR SLIST_FOREACH () -.\" when -.\" .I var -.\" is NULL, else it treats -.\" .I var -.\" as a previously found SLIST element and begins the loop at -.\" .I var -.\" instead of the first element in the SLIST referenced by -.\" .IR head . -.\" .Pp -.\" .BR SLIST_FOREACH_SAFE () -.\" traverses the list referenced by -.\" .I head -.\" in the forward direction, assigning each element in -.\" turn to -.\" .IR var . -.\" However, unlike -.\" .BR SLIST_FOREACH () -.\" here it is permitted to both remove -.\" .I var -.\" as well as free it from within the loop safely without interfering with the -.\" traversal. -.\" .PP -.\" .BR SLIST_FOREACH_FROM_SAFE () -.\" behaves identically to -.\" .BR SLIST_FOREACH_SAFE () -.\" when -.\" .I var -.\" is NULL, else it treats -.\" .I var -.\" as a previously found SLIST element and begins the loop at -.\" .I var -.\" instead of the first element in the SLIST referenced by -.\" .IR head . -.SS Removal -.BR SLIST_REMOVE () -removes the element -.I elm -from the list. -.PP -.BR SLIST_REMOVE_HEAD () -removes the element -.I elm -from the head of the list. -For optimum efficiency, -elements being removed from the head of the list -should explicitly use this macro instead of the generic -.BR SLIST_REMOVE (). -.\" .PP -.\" .BR SLIST_REMOVE_AFTER () -.\" removes the element after -.\" .I elm -.\" from the list. -.\" Unlike -.\" .IR SLIST_REMOVE , -.\" this macro does not traverse the entire list. -.\" .SS Other features -.\" .BR SLIST_SWAP () -.\" swaps the contents of -.\" .I head1 -.\" and -.\" .IR head2 . -.SH RETURN VALUE -.BR SLIST_EMPTY () -returns nonzero if the list is empty, -and zero if the list contains at least one entry. -.PP -.BR SLIST_FIRST (), -and -.BR SLIST_NEXT () -return a pointer to the first or next -.I TYPE -structure, respectively. -.PP -.BR SLIST_HEAD_INITIALIZER () -returns an initializer that can be assigned to the list -.IR head . -.SH STANDARDS -BSD. -.SH HISTORY -4.4BSD. -.SH BUGS -.BR SLIST_FOREACH () -doesn't allow -.I var -to be removed or freed within the loop, -as it would interfere with the traversal. -.BR SLIST_FOREACH_SAFE (), -which is present on the BSDs but is not present in glibc, -fixes this limitation by allowing -.I var -to safely be removed from the list and freed from within the loop -without interfering with the traversal. -.SH EXAMPLES -.\" SRC BEGIN (slist.c) -.EX -#include <stddef.h> -#include <stdio.h> -#include <stdlib.h> -#include <sys/queue.h> -\& -struct entry { - int data; - SLIST_ENTRY(entry) entries; /* Singly linked list */ -}; -\& -SLIST_HEAD(slisthead, entry); -\& -int -main(void) -{ - struct entry *n1, *n2, *n3, *np; - struct slisthead head; /* Singly linked list - head */ -\& - SLIST_INIT(&head); /* Initialize the queue */ -\& - n1 = malloc(sizeof(struct entry)); /* Insert at the head */ - SLIST_INSERT_HEAD(&head, n1, entries); -\& - n2 = malloc(sizeof(struct entry)); /* Insert after */ - SLIST_INSERT_AFTER(n1, n2, entries); -\& - SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */ - free(n2); -\& - n3 = SLIST_FIRST(&head); - SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */ - free(n3); -\& - for (unsigned int i = 0; i < 5; i++) { - n1 = malloc(sizeof(struct entry)); - SLIST_INSERT_HEAD(&head, n1, entries); - n1\->data = i; - } -\& - /* Forward traversal */ - SLIST_FOREACH(np, &head, entries) - printf("%i\en", np\->data); -\& - while (!SLIST_EMPTY(&head)) { /* List deletion */ - n1 = SLIST_FIRST(&head); - SLIST_REMOVE_HEAD(&head, entries); - free(n1); - } - SLIST_INIT(&head); -\& - exit(EXIT_SUCCESS); -} -.EE -.\" SRC END -.SH SEE ALSO -.BR insque (3), -.BR queue (7) |