suzanne.soy/man-pages
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
gh-pages
man-pages/man3/queue.3.html
Suzanne Soy 4c89183f2b Added man pages from my system
2021-03-31 01:06:50 +01:00

1743 lines
25 KiB
HTML
Raw Permalink Blame History

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<HTML><HEAD><TITLE>Man page of QUEUE</TITLE>
</HEAD><BODY>
<H1>QUEUE</H1>
Section: C Library Functions (3)<BR><A HREF="#index">Index</A>
<A HREF="/cgi-bin/man/man2html">Return to Main Contents</A><HR>
<BR>BSD mandoc<BR>
<A NAME="lbAB">&nbsp;</A>
<H2>NAME</H2>
<B>SLIST_EMPTY</B>
<B>SLIST_ENTRY</B>
<B>SLIST_FIRST</B>
<B>SLIST_FOREACH</B>
<B>SLIST_HEAD</B>
<B>SLIST_HEAD_INITIALIZER</B>
<B>SLIST_INIT</B>
<B>SLIST_INSERT_AFTER</B>
<B>SLIST_INSERT_HEAD</B>
<B>SLIST_NEXT</B>
<B>SLIST_REMOVE_HEAD</B>
<B>SLIST_REMOVE</B>
<B>STAILQ_CONCAT</B>
<B>STAILQ_EMPTY</B>
<B>STAILQ_ENTRY</B>
<B>STAILQ_FIRST</B>
<B>STAILQ_FOREACH</B>
<B>STAILQ_HEAD</B>
<B>STAILQ_HEAD_INITIALIZER</B>
<B>STAILQ_INIT</B>
<B>STAILQ_INSERT_AFTER</B>
<B>STAILQ_INSERT_HEAD</B>
<B>STAILQ_INSERT_TAIL</B>
<B>STAILQ_NEXT</B>
<B>STAILQ_REMOVE_HEAD</B>
<B>STAILQ_REMOVE</B>
<B>LIST_EMPTY</B>
<B>LIST_ENTRY</B>
<B>LIST_FIRST</B>
<B>LIST_FOREACH</B>
<B>LIST_HEAD</B>
<B>LIST_HEAD_INITIALIZER</B>
<B>LIST_INIT</B>
<B>LIST_INSERT_AFTER</B>
<B>LIST_INSERT_BEFORE</B>
<B>LIST_INSERT_HEAD</B>
<B>LIST_NEXT</B>
<B>LIST_REMOVE</B>
<B>TAILQ_CONCAT</B>
<B>TAILQ_EMPTY</B>
<B>TAILQ_ENTRY</B>
<B>TAILQ_FIRST</B>
<B>TAILQ_FOREACH</B>
<B>TAILQ_FOREACH_REVERSE</B>
<B>TAILQ_HEAD</B>
<B>TAILQ_HEAD_INITIALIZER</B>
<B>TAILQ_INIT</B>
<B>TAILQ_INSERT_AFTER</B>
<B>TAILQ_INSERT_BEFORE</B>
<B>TAILQ_INSERT_HEAD</B>
<B>TAILQ_INSERT_TAIL</B>
<B>TAILQ_LAST</B>
<B>TAILQ_NEXT</B>
<B>TAILQ_PREV</B>
<B>TAILQ_REMOVE</B>
<B>TAILQ_SWAP</B>
- implementations of singly-linked lists, singly-linked tail queues,
lists and tail queues
<A NAME="lbAC">&nbsp;</A>
<H2>SYNOPSIS</H2>
In sys/queue.h
Fn SLIST_EMPTY SLIST_HEAD *head
Fn SLIST_ENTRY TYPE
Fn SLIST_FIRST SLIST_HEAD *head
Fn SLIST_FOREACH TYPE *var SLIST_HEAD *head SLIST_ENTRY NAME
Fn SLIST_HEAD HEADNAME TYPE
Fn SLIST_HEAD_INITIALIZER SLIST_HEAD head
Fn SLIST_INIT SLIST_HEAD *head
Fn SLIST_INSERT_AFTER TYPE *listelm TYPE *elm SLIST_ENTRY NAME
Fn SLIST_INSERT_HEAD SLIST_HEAD *head TYPE *elm SLIST_ENTRY NAME
Fn SLIST_NEXT TYPE *elm SLIST_ENTRY NAME
Fn SLIST_REMOVE_HEAD SLIST_HEAD *head SLIST_ENTRY NAME
Fn SLIST_REMOVE SLIST_HEAD *head TYPE *elm TYPE SLIST_ENTRY NAME
Fn STAILQ_CONCAT STAILQ_HEAD *head1 STAILQ_HEAD *head2
Fn STAILQ_EMPTY STAILQ_HEAD *head
Fn STAILQ_ENTRY TYPE
Fn STAILQ_FIRST STAILQ_HEAD *head
Fn STAILQ_FOREACH TYPE *var STAILQ_HEAD *head STAILQ_ENTRY NAME
Fn STAILQ_HEAD HEADNAME TYPE
Fn STAILQ_HEAD_INITIALIZER STAILQ_HEAD head
Fn STAILQ_INIT STAILQ_HEAD *head
Fn STAILQ_INSERT_AFTER STAILQ_HEAD *head TYPE *listelm TYPE *elm STAILQ_ENTRY NAME
Fn STAILQ_INSERT_HEAD STAILQ_HEAD *head TYPE *elm STAILQ_ENTRY NAME
Fn STAILQ_INSERT_TAIL STAILQ_HEAD *head TYPE *elm STAILQ_ENTRY NAME
Fn STAILQ_NEXT TYPE *elm STAILQ_ENTRY NAME
Fn STAILQ_REMOVE_HEAD STAILQ_HEAD *head STAILQ_ENTRY NAME
Fn STAILQ_REMOVE STAILQ_HEAD *head TYPE *elm TYPE STAILQ_ENTRY NAME
Fn LIST_EMPTY LIST_HEAD *head
Fn LIST_ENTRY TYPE
Fn LIST_FIRST LIST_HEAD *head
Fn LIST_FOREACH TYPE *var LIST_HEAD *head LIST_ENTRY NAME
Fn LIST_HEAD HEADNAME TYPE
Fn LIST_HEAD_INITIALIZER LIST_HEAD head
Fn LIST_INIT LIST_HEAD *head
Fn LIST_INSERT_AFTER TYPE *listelm TYPE *elm LIST_ENTRY NAME
Fn LIST_INSERT_BEFORE TYPE *listelm TYPE *elm LIST_ENTRY NAME
Fn LIST_INSERT_HEAD LIST_HEAD *head TYPE *elm LIST_ENTRY NAME
Fn LIST_NEXT TYPE *elm LIST_ENTRY NAME
Fn LIST_REMOVE TYPE *elm LIST_ENTRY NAME
Fn LIST_SWAP LIST_HEAD *head1 LIST_HEAD *head2 TYPE LIST_ENTRY NAME
Fn TAILQ_CONCAT TAILQ_HEAD *head1 TAILQ_HEAD *head2 TAILQ_ENTRY NAME
Fn TAILQ_EMPTY TAILQ_HEAD *head
Fn TAILQ_ENTRY TYPE
Fn TAILQ_FIRST TAILQ_HEAD *head
Fn TAILQ_FOREACH TYPE *var TAILQ_HEAD *head TAILQ_ENTRY NAME
Fn TAILQ_FOREACH_REVERSE TYPE *var TAILQ_HEAD *head HEADNAME TAILQ_ENTRY NAME
Fn TAILQ_HEAD HEADNAME TYPE
Fn TAILQ_HEAD_INITIALIZER TAILQ_HEAD head
Fn TAILQ_INIT TAILQ_HEAD *head
Fn TAILQ_INSERT_AFTER TAILQ_HEAD *head TYPE *listelm TYPE *elm TAILQ_ENTRY NAME
Fn TAILQ_INSERT_BEFORE TYPE *listelm TYPE *elm TAILQ_ENTRY NAME
Fn TAILQ_INSERT_HEAD TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME
Fn TAILQ_INSERT_TAIL TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME
Fn TAILQ_LAST TAILQ_HEAD *head HEADNAME
Fn TAILQ_NEXT TYPE *elm TAILQ_ENTRY NAME
Fn TAILQ_PREV TYPE *elm HEADNAME TAILQ_ENTRY NAME
Fn TAILQ_REMOVE TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME
Fn TAILQ_SWAP TAILQ_HEAD *head1 TAILQ_HEAD *head2 TYPE TAILQ_ENTRY NAME
<A NAME="lbAD">&nbsp;</A>
<H2>DESCRIPTION</H2>
These macros define and operate on four types of data structures:
singly-linked lists, singly-linked tail queues, lists, and tail queues.
All four structures support the following functionality:
<P>
<OL><P>
<LI>
Insertion of a new entry at the head of the list.
<LI>
Insertion of a new entry after any element in the list.
<LI>
<A HREF="/cgi-bin/man/man2html?1+O">O</A>(1) removal of an entry from the head of the list.
<LI>
Forward traversal through the list.
<LI>
Swapping the contents of two lists.
</OL><P>
<P>
Singly-linked lists are the simplest of the four data structures
and support only the above functionality.
Singly-linked lists are ideal for applications with large datasets
and few or no removals,
or for implementing a LIFO queue.
Singly-linked lists add the following functionality:
<P>
<OL><P>
<LI>
<A HREF="/cgi-bin/man/man2html?n+O">O</A>(n) removal of any entry in the list.
</OL><P>
<P>
Singly-linked tail queues add the following functionality:
<P>
<OL><P>
<LI>
Entries can be added at the end of a list.
<LI>
<A HREF="/cgi-bin/man/man2html?n+O">O</A>(n) removal of any entry in the list.
<LI>
They may be concatenated.
</OL><P>
<P>
However:
<P>
<OL><P>
<LI>
All list insertions must specify the head of the list.
<LI>
Each head entry requires two pointers rather than one.
<LI>
Code size is about 15% greater and operations run about 20% slower
than singly-linked lists.
</OL><P>
<P>
Singly-linked tail queues are ideal for applications with large datasets and
few or no removals,
or for implementing a FIFO queue.
<P>
All doubly linked types of data structures (lists and tail queues)
additionally allow:
<P>
<OL><P>
<LI>
Insertion of a new entry before any element in the list.
<LI>
<A HREF="/cgi-bin/man/man2html?1+O">O</A>(1) removal of any entry in the list.
</OL><P>
<P>
However:
<P>
<OL><P>
<LI>
Each element requires two pointers rather than one.
<LI>
Code size and execution time of operations (except for removal) is about
twice that of the singly-linked data-structures.
</OL><P>
<P>
Linked lists are the simplest of the doubly linked data structures.
They add the following functionality over the above:
<P>
<OL><P>
<LI>
They may be traversed backwards.
</OL><P>
<P>
However:
<P>
<OL><P>
<LI>
To traverse backwards, an entry to begin the traversal and the list in
which it is contained must be specified.
</OL><P>
<P>
Tail queues add the following functionality:
<OL><P>
<LI>
Entries can be added at the end of a list.
<LI>
They may be traversed backwards, from tail to head.
<LI>
They may be concatenated.
</OL><P>
<P>
However:
<P>
<OL><P>
<LI>
All list insertions and removals must specify the head of the list.
<LI>
Each head entry requires two pointers rather than one.
<LI>
Code size is about 15% greater and operations run about 20% slower
than singly-linked lists.
</OL><P>
<P>
In the macro definitions,
Fa TYPE
is the name of a user defined structure,
that must contain a field of type
<B>SLIST_ENTRY</B>
<B>STAILQ_ENTRY</B>
<B>LIST_ENTRY</B>
or
<B>TAILQ_ENTRY</B>
named
Fa NAME .
The argument
Fa HEADNAME
is the name of a user defined structure that must be declared
using the macros
<B>SLIST_HEAD</B>
<B>STAILQ_HEAD</B>
<B>LIST_HEAD</B>
or
<B>TAILQ_HEAD</B>
See the examples below for further explanation of how these
macros are used.
<A NAME="lbAE">&nbsp;</A>
<H3>Singly-linked lists</H3>
A singly-linked list is headed by a structure defined by the
<B>SLIST_HEAD</B>
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 <A HREF="/cgi-bin/man/man2html?n+O">O</A>(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
Fa SLIST_HEAD
structure is declared as follows:
<BLOCKQUOTE>
<PRE>
SLIST_HEAD(HEADNAME, TYPE) head;
</PRE>
</BLOCKQUOTE>
<P>
where
Fa HEADNAME
is the name of the structure to be defined, and
Fa 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:
<BLOCKQUOTE>
<PRE>
struct HEADNAME *headp;
</PRE>
</BLOCKQUOTE>
<P>
(The names
<B>head</B>
and
<B>headp</B>
are user selectable.)
<P>
The macro
<B>SLIST_HEAD_INITIALIZER</B>
evaluates to an initializer for the list
Fa head .
<P>
The macro
<B>SLIST_EMPTY</B>
evaluates to true if there are no elements in the list.
<P>
The macro
<B>SLIST_ENTRY</B>
declares a structure that connects the elements in
the list.
<P>
The macro
<B>SLIST_FIRST</B>
returns the first element in the list or NULL if the list is empty.
<P>
The macro
<B>SLIST_FOREACH</B>
traverses the list referenced by
Fa head
in the forward direction, assigning each element in
turn to
Fa var .
<P>
The macro
<B>SLIST_INIT</B>
initializes the list referenced by
Fa head .
<P>
The macro
<B>SLIST_INSERT_HEAD</B>
inserts the new element
Fa elm
at the head of the list.
<P>
The macro
<B>SLIST_INSERT_AFTER</B>
inserts the new element
Fa elm
after the element
Fa listelm .
<P>
The macro
<B>SLIST_NEXT</B>
returns the next element in the list.
<P>
The macro
<B>SLIST_REMOVE_HEAD</B>
removes the element
Fa 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
Fa SLIST_REMOVE
macro.
<P>
The macro
<B>SLIST_REMOVE</B>
removes the element
Fa elm
from the list.
<A NAME="lbAF">&nbsp;</A>
<H3>Singly-linked list example</H3>
<PRE>
SLIST_HEAD(slisthead, entry) head =
SLIST_HEAD_INITIALIZER(head);
struct slisthead *headp; /* Singly-linked List
head. */
struct entry {
...
SLIST_ENTRY(entry) entries; /* Singly-linked List. */
...
} *n1, *n2, *n3, *np;
SLIST_INIT(&amp;head); /* Initialize the list. */
n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
SLIST_INSERT_HEAD(&amp;head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* Insert after. */
SLIST_INSERT_AFTER(n1, n2, entries);
SLIST_REMOVE(&amp;head, n2, entry, entries);/* Deletion. */
free(n2);
n3 = SLIST_FIRST(&amp;head);
SLIST_REMOVE_HEAD(&amp;head, entries); /* Deletion from the head. */
free(n3);
/* Forward traversal. */
SLIST_FOREACH(np, &amp;head, entries)
np-&gt; ...
while (!SLIST_EMPTY(&amp;head)) { /* List Deletion. */
n1 = SLIST_FIRST(&amp;head);
SLIST_REMOVE_HEAD(&amp;head, entries);
free(n1);
}
</PRE>
<A NAME="lbAG">&nbsp;</A>
<H3>Singly-linked tail queues</H3>
A singly-linked tail queue is headed by a structure defined by the
<B>STAILQ_HEAD</B>
macro.
This structure contains a pair of pointers,
one to the first element in the tail queue and the other to
the last element in the tail queue.
The elements are singly linked for minimum space and pointer
manipulation overhead at the expense of <A HREF="/cgi-bin/man/man2html?n+O">O</A>(n) removal for arbitrary
elements.
New elements can be added to the tail queue after an existing element,
at the head of the tail queue, or at the end of the tail queue.
A
Fa STAILQ_HEAD
structure is declared as follows:
<BLOCKQUOTE>
<PRE>
STAILQ_HEAD(HEADNAME, TYPE) head;
</PRE>
</BLOCKQUOTE>
<P>
where
<B>HEADNAME</B>
is the name of the structure to be defined, and
<B>TYPE</B>
is the type of the elements to be linked into the tail queue.
A pointer to the head of the tail queue can later be declared as:
<BLOCKQUOTE>
<PRE>
struct HEADNAME *headp;
</PRE>
</BLOCKQUOTE>
<P>
(The names
<B>head</B>
and
<B>headp</B>
are user selectable.)
<P>
The macro
<B>STAILQ_HEAD_INITIALIZER</B>
evaluates to an initializer for the tail queue
Fa head .
<P>
The macro
<B>STAILQ_CONCAT</B>
concatenates the tail queue headed by
Fa head2
onto the end of the one headed by
Fa head1
removing all entries from the former.
<P>
The macro
<B>STAILQ_EMPTY</B>
evaluates to true if there are no items on the tail queue.
<P>
The macro
<B>STAILQ_ENTRY</B>
declares a structure that connects the elements in
the tail queue.
<P>
The macro
<B>STAILQ_FIRST</B>
returns the first item on the tail queue or NULL if the tail queue
is empty.
<P>
The macro
<B>STAILQ_FOREACH</B>
traverses the tail queue referenced by
Fa head
in the forward direction, assigning each element
in turn to
Fa var .
<P>
The macro
<B>STAILQ_INIT</B>
initializes the tail queue referenced by
Fa head .
<P>
The macro
<B>STAILQ_INSERT_HEAD</B>
inserts the new element
Fa elm
at the head of the tail queue.
<P>
The macro
<B>STAILQ_INSERT_TAIL</B>
inserts the new element
Fa elm
at the end of the tail queue.
<P>
The macro
<B>STAILQ_INSERT_AFTER</B>
inserts the new element
Fa elm
after the element
Fa listelm .
<P>
The macro
<B>STAILQ_NEXT</B>
returns the next item on the tail queue, or NULL this item is the last.
<P>
The macro
<B>STAILQ_REMOVE_HEAD</B>
removes the element at the head of the tail queue.
For optimum efficiency,
elements being removed from the head of the tail queue should
use this macro explicitly rather than the generic
Fa STAILQ_REMOVE
macro.
<P>
The macro
<B>STAILQ_REMOVE</B>
removes the element
Fa elm
from the tail queue.
<A NAME="lbAH">&nbsp;</A>
<H3>Singly-linked tail queue example</H3>
<PRE>
STAILQ_HEAD(stailhead, entry) head =
STAILQ_HEAD_INITIALIZER(head);
struct stailhead *headp; /* Singly-linked tail queue head. */
struct entry {
...
STAILQ_ENTRY(entry) entries; /* Tail queue. */
...
} *n1, *n2, *n3, *np;
STAILQ_INIT(&amp;head); /* Initialize the queue. */
n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
STAILQ_INSERT_HEAD(&amp;head, n1, entries);
n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
STAILQ_INSERT_TAIL(&amp;head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* Insert after. */
STAILQ_INSERT_AFTER(&amp;head, n1, n2, entries);
/* Deletion. */
STAILQ_REMOVE(&amp;head, n2, entry, entries);
free(n2);
/* Deletion from the head. */
n3 = STAILQ_FIRST(&amp;head);
STAILQ_REMOVE_HEAD(&amp;head, entries);
free(n3);
/* Forward traversal. */
STAILQ_FOREACH(np, &amp;head, entries)
np-&gt; ...
/* TailQ Deletion. */
while (!STAILQ_EMPTY(&amp;head)) {
n1 = STAILQ_FIRST(&amp;head);
STAILQ_REMOVE_HEAD(&amp;head, entries);
free(n1);
}
/* Faster TailQ Deletion. */
n1 = STAILQ_FIRST(&amp;head);
while (n1 != NULL) {
n2 = STAILQ_NEXT(n1, entries);
free(n1);
n1 = n2;
}
STAILQ_INIT(&amp;head);
</PRE>
<A NAME="lbAI">&nbsp;</A>
<H3>Lists</H3>
A list is headed by a structure defined by the
<B>LIST_HEAD</B>
macro.
This structure contains a single pointer to the first element
on the list.
The elements are doubly linked so that an arbitrary element can be
removed without traversing the list.
New elements can be added to the list after an existing element,
before an existing element, or at the head of the list.
A
Fa LIST_HEAD
structure is declared as follows:
<BLOCKQUOTE>
<PRE>
LIST_HEAD(HEADNAME, TYPE) head;
</PRE>
</BLOCKQUOTE>
<P>
where
Fa HEADNAME
is the name of the structure to be defined, and
Fa 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:
<BLOCKQUOTE>
<PRE>
struct HEADNAME *headp;
</PRE>
</BLOCKQUOTE>
<P>
(The names
<B>head</B>
and
<B>headp</B>
are user selectable.)
<P>
The macro
<B>LIST_HEAD_INITIALIZER</B>
evaluates to an initializer for the list
Fa head .
<P>
The macro
<B>LIST_EMPTY</B>
evaluates to true if there are no elements in the list.
<P>
The macro
<B>LIST_ENTRY</B>
declares a structure that connects the elements in
the list.
<P>
The macro
<B>LIST_FIRST</B>
returns the first element in the list or NULL if the list
is empty.
<P>
The macro
<B>LIST_FOREACH</B>
traverses the list referenced by
Fa head
in the forward direction, assigning each element in turn to
Fa var .
<P>
The macro
<B>LIST_INIT</B>
initializes the list referenced by
Fa head .
<P>
The macro
<B>LIST_INSERT_HEAD</B>
inserts the new element
Fa elm
at the head of the list.
<P>
The macro
<B>LIST_INSERT_AFTER</B>
inserts the new element
Fa elm
after the element
Fa listelm .
<P>
The macro
<B>LIST_INSERT_BEFORE</B>
inserts the new element
Fa elm
before the element
Fa listelm .
<P>
The macro
<B>LIST_NEXT</B>
returns the next element in the list, or NULL if this is the last.
<P>
The macro
<B>LIST_REMOVE</B>
removes the element
Fa elm
from the list.
<A NAME="lbAJ">&nbsp;</A>
<H3>List example</H3>
<PRE>
LIST_HEAD(listhead, entry) head =
LIST_HEAD_INITIALIZER(head);
struct listhead *headp; /* List head. */
struct entry {
...
LIST_ENTRY(entry) entries; /* List. */
...
} *n1, *n2, *n3, *np, *np_temp;
LIST_INIT(&amp;head); /* Initialize the list. */
n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
LIST_INSERT_HEAD(&amp;head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* Insert after. */
LIST_INSERT_AFTER(n1, n2, entries);
n3 = malloc(sizeof(struct entry)); /* Insert before. */
LIST_INSERT_BEFORE(n2, n3, entries);
LIST_REMOVE(n2, entries); /* Deletion. */
free(n2);
/* Forward traversal. */
LIST_FOREACH(np, &amp;head, entries)
np-&gt; ...
while (!LIST_EMPTY(&amp;head)) { /* List Deletion. */
n1 = LIST_FIRST(&amp;head);
LIST_REMOVE(n1, entries);
free(n1);
}
n1 = LIST_FIRST(&amp;head); /* Faster List Deletion. */
while (n1 != NULL) {
n2 = LIST_NEXT(n1, entries);
free(n1);
n1 = n2;
}
LIST_INIT(&amp;head);
</PRE>
<A NAME="lbAK">&nbsp;</A>
<H3>Tail queues</H3>
A tail queue is headed by a structure defined by the
<B>TAILQ_HEAD</B>
macro.
This structure contains a pair of pointers,
one to the first element in the tail queue and the other to
the last element in the tail queue.
The elements are doubly linked so that an arbitrary element can be
removed without traversing the tail queue.
New elements can be added to the tail queue after an existing element,
before an existing element, at the head of the tail queue,
or at the end of the tail queue.
A
Fa TAILQ_HEAD
structure is declared as follows:
<BLOCKQUOTE>
<PRE>
TAILQ_HEAD(HEADNAME, TYPE) head;
</PRE>
</BLOCKQUOTE>
<P>
where
<B>HEADNAME</B>
is the name of the structure to be defined, and
<B>TYPE</B>
is the type of the elements to be linked into the tail queue.
A pointer to the head of the tail queue can later be declared as:
<BLOCKQUOTE>
<PRE>
struct HEADNAME *headp;
</PRE>
</BLOCKQUOTE>
<P>
(The names
<B>head</B>
and
<B>headp</B>
are user selectable.)
<P>
The macro
<B>TAILQ_HEAD_INITIALIZER</B>
evaluates to an initializer for the tail queue
Fa head .
<P>
The macro
<B>TAILQ_CONCAT</B>
concatenates the tail queue headed by
Fa head2
onto the end of the one headed by
Fa head1
removing all entries from the former.
<P>
The macro
<B>TAILQ_EMPTY</B>
evaluates to true if there are no items on the tail queue.
<P>
The macro
<B>TAILQ_ENTRY</B>
declares a structure that connects the elements in
the tail queue.
<P>
The macro
<B>TAILQ_FIRST</B>
returns the first item on the tail queue or NULL if the tail queue
is empty.
<P>
The macro
<B>TAILQ_FOREACH</B>
traverses the tail queue referenced by
Fa head
in the forward direction, assigning each element in turn to
Fa var .
Fa var
is set to
<B>NULL</B>
if the loop completes normally, or if there were no elements.
<P>
The macro
<B>TAILQ_FOREACH_REVERSE</B>
traverses the tail queue referenced by
Fa head
in the reverse direction, assigning each element in turn to
Fa var .
<P>
The macro
<B>TAILQ_INIT</B>
initializes the tail queue referenced by
Fa head .
<P>
The macro
<B>TAILQ_INSERT_HEAD</B>
inserts the new element
Fa elm
at the head of the tail queue.
<P>
The macro
<B>TAILQ_INSERT_TAIL</B>
inserts the new element
Fa elm
at the end of the tail queue.
<P>
The macro
<B>TAILQ_INSERT_AFTER</B>
inserts the new element
Fa elm
after the element
Fa listelm .
<P>
The macro
<B>TAILQ_INSERT_BEFORE</B>
inserts the new element
Fa elm
before the element
Fa listelm .
<P>
The macro
<B>TAILQ_LAST</B>
returns the last item on the tail queue.
If the tail queue is empty the return value is
<B>NULL</B>
<P>
The macro
<B>TAILQ_NEXT</B>
returns the next item on the tail queue, or NULL if this item is the last.
<P>
The macro
<B>TAILQ_PREV</B>
returns the previous item on the tail queue, or NULL if this item
is the first.
<P>
The macro
<B>TAILQ_REMOVE</B>
removes the element
Fa elm
from the tail queue.
<P>
The macro
<B>TAILQ_SWAP</B>
swaps the contents of
Fa head1
and
Fa head2 .
<A NAME="lbAL">&nbsp;</A>
<H3>Tail queue example</H3>
<PRE>
TAILQ_HEAD(tailhead, entry) head =
TAILQ_HEAD_INITIALIZER(head);
struct tailhead *headp; /* Tail queue head. */
struct entry {
...
TAILQ_ENTRY(entry) entries; /* Tail queue. */
...
} *n1, *n2, *n3, *np;
TAILQ_INIT(&amp;head); /* Initialize the queue. */
n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
TAILQ_INSERT_HEAD(&amp;head, n1, entries);
n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
TAILQ_INSERT_TAIL(&amp;head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* Insert after. */
TAILQ_INSERT_AFTER(&amp;head, n1, n2, entries);
n3 = malloc(sizeof(struct entry)); /* Insert before. */
TAILQ_INSERT_BEFORE(n2, n3, entries);
TAILQ_REMOVE(&amp;head, n2, entries); /* Deletion. */
free(n2);
/* Forward traversal. */
TAILQ_FOREACH(np, &amp;head, entries)
np-&gt; ...
/* Reverse traversal. */
TAILQ_FOREACH_REVERSE(np, &amp;head, tailhead, entries)
np-&gt; ...
/* TailQ Deletion. */
while (!TAILQ_EMPTY(&amp;head)) {
n1 = TAILQ_FIRST(&amp;head);
TAILQ_REMOVE(&amp;head, n1, entries);
free(n1);
}
/* Faster TailQ Deletion. */
n1 = TAILQ_FIRST(&amp;head);
while (n1 != NULL) {
n2 = TAILQ_NEXT(n1, entries);
free(n1);
n1 = n2;
}
TAILQ_INIT(&amp;head);
n2 = malloc(sizeof(struct entry)); /* Insert before. */
CIRCLEQ_INSERT_BEFORE(&amp;head, n1, n2, entries);
/* Forward traversal. */
for (np = head.cqh_first; np != (void *)&amp;head;
np = np-&gt;entries.cqe_next)
np-&gt; ...
/* Reverse traversal. */
for (np = head.cqh_last; np != (void *)&amp;head; np = np-&gt;entries.cqe_prev)
np-&gt; ...
/* Delete. */
while (head.cqh_first != (void *)&amp;head)
CIRCLEQ_REMOVE(&amp;head, head.cqh_first, entries);
</PRE>
<A NAME="lbAM">&nbsp;</A>
<H2>CONFORMING TO</H2>
Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008.
Present on the BSDs.
<B>queue</B>
functions first appeared in
BSD 4.4
<A NAME="lbAN">&nbsp;</A>
<H2>SEE ALSO</H2>
<A HREF="/cgi-bin/man/man2html?3+insque">insque</A>(3)
<A NAME="lbAO">&nbsp;</A>
<H2>COLOPHON</H2>
This page is part of release 5.05 of the Linux
<I>man-pages</I>
project.
A description of the project,
information about reporting bugs,
and the latest version of this page,
can be found at
<A HREF="https://www.kernel.org/doc/man-pages/.">https://www.kernel.org/doc/man-pages/.</A>
<P>
<HR>
<A NAME="index">&nbsp;</A><H2>Index</H2>
<DL>
<DT id="1"><A HREF="#lbAB">NAME</A><DD>
<DT id="2"><A HREF="#lbAC">SYNOPSIS</A><DD>
<DT id="3"><A HREF="#lbAD">DESCRIPTION</A><DD>
<DL>
<DT id="4"><A HREF="#lbAE">Singly-linked lists</A><DD>
<DT id="5"><A HREF="#lbAF">Singly-linked list example</A><DD>
<DT id="6"><A HREF="#lbAG">Singly-linked tail queues</A><DD>
<DT id="7"><A HREF="#lbAH">Singly-linked tail queue example</A><DD>
<DT id="8"><A HREF="#lbAI">Lists</A><DD>
<DT id="9"><A HREF="#lbAJ">List example</A><DD>
<DT id="10"><A HREF="#lbAK">Tail queues</A><DD>
<DT id="11"><A HREF="#lbAL">Tail queue example</A><DD>
</DL>
<DT id="12"><A HREF="#lbAM">CONFORMING TO</A><DD>
<DT id="13"><A HREF="#lbAN">SEE ALSO</A><DD>
<DT id="14"><A HREF="#lbAO">COLOPHON</A><DD>
</DL>
<HR>
This document was created by
<A HREF="/cgi-bin/man/man2html">man2html</A>,
using the manual pages.<BR>
Time: 00:05:53 GMT, March 31, 2021
</BODY>
</HTML>
Reference in New Issue View Git Blame Copy Permalink