diff options
Diffstat (limited to 'static/freebsd/man3/queue.3 3.html')
| -rw-r--r-- | static/freebsd/man3/queue.3 3.html | 1187 |
1 files changed, 1187 insertions, 0 deletions
diff --git a/static/freebsd/man3/queue.3 3.html b/static/freebsd/man3/queue.3 3.html new file mode 100644 index 00000000..d35abcb8 --- /dev/null +++ b/static/freebsd/man3/queue.3 3.html @@ -0,0 +1,1187 @@ +<table class="head"> + <tr> + <td class="head-ltitle">QUEUE(3)</td> + <td class="head-vol">Library Functions Manual</td> + <td class="head-rtitle">QUEUE(3)</td> + </tr> +</table> +<div class="manual-text"> +<section class="Sh"> +<h1 class="Sh" id="NAME"><a class="permalink" href="#NAME">NAME</a></h1> +<p class="Pp"><code class="Nm">SLIST_CLASS_ENTRY</code>, + <code class="Nm">SLIST_CLASS_HEAD</code>, + <code class="Nm">SLIST_CONCAT</code>, <code class="Nm">SLIST_EMPTY</code>, + <code class="Nm">SLIST_EMPTY_ATOMIC</code>, + <code class="Nm">SLIST_ENTRY</code>, <code class="Nm">SLIST_FIRST</code>, + <code class="Nm">SLIST_FOREACH</code>, + <code class="Nm">SLIST_FOREACH_FROM</code>, + <code class="Nm">SLIST_FOREACH_FROM_SAFE</code>, + <code class="Nm">SLIST_FOREACH_SAFE</code>, + <code class="Nm">SLIST_HEAD</code>, + <code class="Nm">SLIST_HEAD_INITIALIZER</code>, + <code class="Nm">SLIST_INIT</code>, + <code class="Nm">SLIST_INSERT_AFTER</code>, + <code class="Nm">SLIST_INSERT_HEAD</code>, + <code class="Nm">SLIST_NEXT</code>, <code class="Nm">SLIST_REMOVE</code>, + <code class="Nm">SLIST_REMOVE_AFTER</code>, + <code class="Nm">SLIST_REMOVE_HEAD</code>, + <code class="Nm">SLIST_SPLIT_AFTER</code>, + <code class="Nm">SLIST_SWAP</code>, + <code class="Nm">STAILQ_CLASS_ENTRY</code>, + <code class="Nm">STAILQ_CLASS_HEAD</code>, + <code class="Nm">STAILQ_CONCAT</code>, <code class="Nm">STAILQ_EMPTY</code>, + <code class="Nm">STAILQ_EMPTY_ATOMIC</code>, + <code class="Nm">STAILQ_ENTRY</code>, <code class="Nm">STAILQ_FIRST</code>, + <code class="Nm">STAILQ_FOREACH</code>, + <code class="Nm">STAILQ_FOREACH_FROM</code>, + <code class="Nm">STAILQ_FOREACH_FROM_SAFE</code>, + <code class="Nm">STAILQ_FOREACH_SAFE</code>, + <code class="Nm">STAILQ_HEAD</code>, + <code class="Nm">STAILQ_HEAD_INITIALIZER</code>, + <code class="Nm">STAILQ_INIT</code>, + <code class="Nm">STAILQ_INSERT_AFTER</code>, + <code class="Nm">STAILQ_INSERT_HEAD</code>, + <code class="Nm">STAILQ_INSERT_TAIL</code>, + <code class="Nm">STAILQ_LAST</code>, <code class="Nm">STAILQ_NEXT</code>, + <code class="Nm">STAILQ_REMOVE</code>, + <code class="Nm">STAILQ_REMOVE_AFTER</code>, + <code class="Nm">STAILQ_REMOVE_HEAD</code>, + <code class="Nm">STAILQ_REVERSE</code>, + <code class="Nm">STAILQ_SPLIT_AFTER</code>, + <code class="Nm">STAILQ_SWAP</code>, + <code class="Nm">LIST_CLASS_ENTRY</code>, + <code class="Nm">LIST_CLASS_HEAD</code>, + <code class="Nm">LIST_CONCAT</code>, <code class="Nm">LIST_EMPTY</code>, + <code class="Nm">LIST_EMPTY_ATOMIC</code>, + <code class="Nm">LIST_ENTRY</code>, <code class="Nm">LIST_FIRST</code>, + <code class="Nm">LIST_FOREACH</code>, + <code class="Nm">LIST_FOREACH_FROM</code>, + <code class="Nm">LIST_FOREACH_FROM_SAFE</code>, + <code class="Nm">LIST_FOREACH_SAFE</code>, + <code class="Nm">LIST_HEAD</code>, + <code class="Nm">LIST_HEAD_INITIALIZER</code>, + <code class="Nm">LIST_INIT</code>, + <code class="Nm">LIST_INSERT_AFTER</code>, + <code class="Nm">LIST_INSERT_BEFORE</code>, + <code class="Nm">LIST_INSERT_HEAD</code>, <code class="Nm">LIST_NEXT</code>, + <code class="Nm">LIST_PREV</code>, <code class="Nm">LIST_REMOVE</code>, + <code class="Nm">LIST_REPLACE</code>, + <code class="Nm">LIST_SPLIT_AFTER</code>, <code class="Nm">LIST_SWAP</code>, + <code class="Nm">TAILQ_CLASS_ENTRY</code>, + <code class="Nm">TAILQ_CLASS_HEAD</code>, + <code class="Nm">TAILQ_CONCAT</code>, <code class="Nm">TAILQ_EMPTY</code>, + <code class="Nm">TAILQ_EMPTY_ATOMIC</code>, + <code class="Nm">TAILQ_ENTRY</code>, <code class="Nm">TAILQ_FIRST</code>, + <code class="Nm">TAILQ_FOREACH</code>, + <code class="Nm">TAILQ_FOREACH_FROM</code>, + <code class="Nm">TAILQ_FOREACH_FROM_SAFE</code>, + <code class="Nm">TAILQ_FOREACH_REVERSE</code>, + <code class="Nm">TAILQ_FOREACH_REVERSE_FROM</code>, + <code class="Nm">TAILQ_FOREACH_REVERSE_FROM_SAFE</code>, + <code class="Nm">TAILQ_FOREACH_REVERSE_SAFE</code>, + <code class="Nm">TAILQ_FOREACH_SAFE</code>, + <code class="Nm">TAILQ_HEAD</code>, + <code class="Nm">TAILQ_HEAD_INITIALIZER</code>, + <code class="Nm">TAILQ_INIT</code>, + <code class="Nm">TAILQ_INSERT_AFTER</code>, + <code class="Nm">TAILQ_INSERT_BEFORE</code>, + <code class="Nm">TAILQ_INSERT_HEAD</code>, + <code class="Nm">TAILQ_INSERT_TAIL</code>, + <code class="Nm">TAILQ_LAST</code>, <code class="Nm">TAILQ_NEXT</code>, + <code class="Nm">TAILQ_PREV</code>, <code class="Nm">TAILQ_REMOVE</code>, + <code class="Nm">TAILQ_REPLACE</code>, + <code class="Nm">TAILQ_SPLIT_AFTER</code>, + <code class="Nm">TAILQ_SWAP</code> — <span class="Nd">implementations + of singly-linked lists, singly-linked tail queues, lists and tail + queues</span></p> +</section> +<section class="Sh"> +<h1 class="Sh" id="SYNOPSIS"><a class="permalink" href="#SYNOPSIS">SYNOPSIS</a></h1> +<p class="Pp"><code class="In">#include + <<a class="In">sys/queue.h</a>></code></p> +<p class="Pp"><code class="Fn">SLIST_CLASS_ENTRY</code>(<var class="Fa" style="white-space: nowrap;">CLASSTYPE</var>);</p> +<p class="Pp"><code class="Fn">SLIST_CLASS_HEAD</code>(<var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">CLASSTYPE</var>);</p> +<p class="Pp"><code class="Fn">SLIST_CONCAT</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head1</var>, <var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head2</var>, <var class="Fa" style="white-space: nowrap;">TYPE</var>, + <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_EMPTY</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">SLIST_EMPTY_ATOMIC</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">SLIST_ENTRY</code>(<var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">SLIST_FIRST</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">SLIST_FOREACH</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_FOREACH_FROM</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_FOREACH_FROM_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY + NAME</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *temp_var</var>);</p> +<p class="Pp"><code class="Fn">SLIST_FOREACH_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY + NAME</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *temp_var</var>);</p> +<p class="Pp"><code class="Fn">SLIST_HEAD</code>(<var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">SLIST_HEAD_INITIALIZER</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + head</var>);</p> +<p class="Pp"><code class="Fn">SLIST_INIT</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">SLIST_INSERT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *listelm</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_INSERT_HEAD</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_NEXT</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_REMOVE</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">TYPE</var>, + <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_REMOVE_AFTER</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_REMOVE_HEAD</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_SPLIT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">SLIST_HEAD *rest</var>, + <var class="Fa" style="white-space: nowrap;">SLIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">SLIST_SWAP</code>(<var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head1</var>, <var class="Fa" style="white-space: nowrap;">SLIST_HEAD + *head2</var>, <var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_CLASS_ENTRY</code>(<var class="Fa" style="white-space: nowrap;">CLASSTYPE</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_CLASS_HEAD</code>(<var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">CLASSTYPE</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_CONCAT</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head1</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head2</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_EMPTY</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_EMPTY_ATOMIC</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_ENTRY</code>(<var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_FIRST</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_FOREACH</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_FOREACH_FROM</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_FOREACH_FROM_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY + NAME</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *temp_var</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_FOREACH_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY + NAME</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *temp_var</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_HEAD</code>(<var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_HEAD_INITIALIZER</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + head</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_INIT</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_INSERT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *listelm</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_INSERT_HEAD</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_INSERT_TAIL</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_LAST</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_NEXT</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_REMOVE</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">TYPE</var>, + <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_REMOVE_AFTER</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_REMOVE_HEAD</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_REVERSE</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE</var>, + <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_SPLIT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">STAILQ_HEAD *rest</var>, + <var class="Fa" style="white-space: nowrap;">STAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">STAILQ_SWAP</code>(<var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head1</var>, <var class="Fa" style="white-space: nowrap;">STAILQ_HEAD + *head2</var>, <var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">LIST_CLASS_ENTRY</code>(<var class="Fa" style="white-space: nowrap;">CLASSTYPE</var>);</p> +<p class="Pp"><code class="Fn">LIST_CLASS_HEAD</code>(<var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">CLASSTYPE</var>);</p> +<p class="Pp"><code class="Fn">LIST_CONCAT</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head1</var>, <var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head2</var>, <var class="Fa" style="white-space: nowrap;">TYPE</var>, + <var class="Fa" style="white-space: nowrap;">LIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_EMPTY</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">LIST_EMPTY_ATOMIC</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">LIST_ENTRY</code>(<var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">LIST_FIRST</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">LIST_FOREACH</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">LIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_FOREACH_FROM</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">LIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_FOREACH_FROM_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">LIST_ENTRY + NAME</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *temp_var</var>);</p> +<p class="Pp"><code class="Fn">LIST_FOREACH_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">LIST_ENTRY + NAME</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *temp_var</var>);</p> +<p class="Pp"><code class="Fn">LIST_HEAD</code>(<var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">LIST_HEAD_INITIALIZER</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + head</var>);</p> +<p class="Pp"><code class="Fn">LIST_INIT</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">LIST_INSERT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *listelm</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">LIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_INSERT_BEFORE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *listelm</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">LIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_INSERT_HEAD</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">LIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_NEXT</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">LIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_PREV</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE</var>, + <var class="Fa" style="white-space: nowrap;">LIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_REMOVE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">LIST_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_REPLACE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">TYPE *new</var>, + <var class="Fa" style="white-space: nowrap;">LIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_SPLIT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">LIST_HEAD *rest</var>, + <var class="Fa" style="white-space: nowrap;">LIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">LIST_SWAP</code>(<var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head1</var>, <var class="Fa" style="white-space: nowrap;">LIST_HEAD + *head2</var>, <var class="Fa" style="white-space: nowrap;">TYPE</var>, + <var class="Fa" style="white-space: nowrap;">LIST_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_CLASS_ENTRY</code>(<var class="Fa" style="white-space: nowrap;">CLASSTYPE</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_CLASS_HEAD</code>(<var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">CLASSTYPE</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_CONCAT</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head1</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head2</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_EMPTY</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_EMPTY_ATOMIC</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_ENTRY</code>(<var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FIRST</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FOREACH</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FOREACH_FROM</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FOREACH_FROM_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY + NAME</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *temp_var</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FOREACH_REVERSE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FOREACH_REVERSE_FROM</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FOREACH_REVERSE_FROM_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>, + <var class="Fa" style="white-space: nowrap;">TYPE *temp_var</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FOREACH_REVERSE_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>, + <var class="Fa" style="white-space: nowrap;">TYPE *temp_var</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_FOREACH_SAFE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *var</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY + NAME</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *temp_var</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_HEAD</code>(<var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TYPE</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_HEAD_INITIALIZER</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + head</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_INIT</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_INSERT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *listelm</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_INSERT_BEFORE</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *listelm</var>, <var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_INSERT_HEAD</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_INSERT_TAIL</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_LAST</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, + <var class="Fa" style="white-space: nowrap;">HEADNAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_NEXT</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY + NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_PREV</code>(<var class="Fa" style="white-space: nowrap;">TYPE + *elm</var>, <var class="Fa" style="white-space: nowrap;">HEADNAME</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_REMOVE</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_REPLACE</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">TYPE *new</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_SPLIT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE *elm</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD *rest</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +<p class="Pp"><code class="Fn">TAILQ_SWAP</code>(<var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head1</var>, <var class="Fa" style="white-space: nowrap;">TAILQ_HEAD + *head2</var>, <var class="Fa" style="white-space: nowrap;">TYPE</var>, + <var class="Fa" style="white-space: nowrap;">TAILQ_ENTRY NAME</var>);</p> +</section> +<section class="Sh"> +<h1 class="Sh" id="DESCRIPTION"><a class="permalink" href="#DESCRIPTION">DESCRIPTION</a></h1> +<p class="Pp">These macros define and operate on four types of data structures + which can be used in both C and C++ source code:</p> +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>Lists</li> + <li>Singly-linked lists</li> + <li>Singly-linked tail queues</li> + <li>Tail queues</li> +</ol> +All four structures support the following functionality: +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>Insertion of a new entry at the head of the list.</li> + <li>Insertion of a new entry after any element in the list.</li> + <li>O(1) removal of an entry from the head of the list.</li> + <li>Forward traversal through the list.</li> + <li>Splitting a list in two after any element in the list.</li> + <li>Swapping the contents of two lists.</li> +</ol> +<p class="Pp">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 class="Bl-enum Bd-indent Bl-compact"> + <li>O(n) removal of any entry in the list.</li> + <li>O(n) concatenation of two lists.</li> +</ol> +<p class="Pp">Singly-linked tail queues add the following functionality:</p> +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>Entries can be added at the end of a list.</li> + <li>O(n) removal of any entry in the list.</li> + <li>They may be concatenated.</li> +</ol> +However: +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>All list insertions must specify the head of the list.</li> + <li>Each head entry requires two pointers rather than one.</li> + <li>Code size is about 15% greater and operations run about 20% slower than + singly-linked lists.</li> +</ol> +<p class="Pp">Singly-linked tail queues are ideal for applications with large + datasets and few or no removals, or for implementing a FIFO queue.</p> +<p class="Pp">All doubly linked types of data structures (lists and tail queues) + additionally allow:</p> +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>Insertion of a new entry before any element in the list.</li> + <li>O(1) removal of any entry in the list.</li> +</ol> +However: +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>Each element requires two pointers rather than one.</li> + <li>Code size and execution time of operations (except for removal) is about + twice that of the singly-linked data-structures.</li> +</ol> +<p class="Pp">Linked lists are the simplest of the doubly linked data + structures. They add the following functionality over the above:</p> +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>O(n) concatenation of two lists.</li> + <li>They may be traversed backwards.</li> +</ol> +However: +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>To traverse backwards, an entry to begin the traversal and the list in + which it is contained must be specified.</li> +</ol> +<p class="Pp">Tail queues add the following functionality:</p> +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>Entries can be added at the end of a list.</li> + <li>They may be traversed backwards, from tail to head.</li> + <li>They may be concatenated.</li> +</ol> +However: +<ol class="Bl-enum Bd-indent Bl-compact"> + <li>All list insertions and removals must specify the head of the list.</li> + <li>Each head entry requires two pointers rather than one.</li> + <li>Code size is about 15% greater and operations run about 20% slower than + singly-linked lists.</li> +</ol> +<p class="Pp">In the macro definitions, <var class="Fa">TYPE</var> is the name + of a user defined structure. The structure must contain a field called + <var class="Fa">NAME</var> which is of type + <code class="Li">SLIST_ENTRY</code>, <code class="Li">STAILQ_ENTRY</code>, + <code class="Li">LIST_ENTRY</code>, or <code class="Li">TAILQ_ENTRY</code>. + In the macro definitions, <var class="Fa">CLASSTYPE</var> is the name of a + user defined class. The class must contain a field called + <var class="Fa">NAME</var> which is of type + <code class="Li">SLIST_CLASS_ENTRY</code>, + <code class="Li">STAILQ_CLASS_ENTRY</code>, + <code class="Li">LIST_CLASS_ENTRY</code>, or + <code class="Li">TAILQ_CLASS_ENTRY</code>. The argument + <var class="Fa">HEADNAME</var> is the name of a user defined structure that + must be declared using the macros <code class="Li">SLIST_HEAD</code>, + <code class="Li">SLIST_CLASS_HEAD</code>, + <code class="Li">STAILQ_HEAD</code>, + <code class="Li">STAILQ_CLASS_HEAD</code>, + <code class="Li">LIST_HEAD</code>, <code class="Li">LIST_CLASS_HEAD</code>, + <code class="Li">TAILQ_HEAD</code>, or + <code class="Li">TAILQ_CLASS_HEAD</code>. See the examples below for further + explanation of how these macros are used.</p> +</section> +<section class="Sh"> +<h1 class="Sh" id="SINGLY-LINKED_LISTS"><a class="permalink" href="#SINGLY-LINKED_LISTS">SINGLY-LINKED + LISTS</a></h1> +<p class="Pp">A singly-linked list is headed by a structure defined by the + <code class="Nm">SLIST_HEAD</code> 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 + <var class="Fa">SLIST_HEAD</var> structure is declared as follows:</p> +<div class="Bd Pp Bd-indent Li"> +<pre>SLIST_HEAD(HEADNAME, TYPE) head;</pre> +</div> +<p class="Pp">where <var class="Fa">HEADNAME</var> is the name of the structure + to be defined, and <var class="Fa">TYPE</var> 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:</p> +<div class="Bd Pp Bd-indent Li"> +<pre>struct HEADNAME *headp;</pre> +</div> +<p class="Pp">(The names <code class="Li">head</code> and + <code class="Li">headp</code> are user selectable.)</p> +<p class="Pp">The macro <code class="Nm">SLIST_HEAD_INITIALIZER</code> evaluates + to an initializer for the list <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">SLIST_CONCAT</code> concatenates the + list headed by <var class="Fa">head2</var> onto the end of the one headed by + <var class="Fa">head1</var> removing all entries from the former. Use of + this macro should be avoided as it traverses the entirety of the + <var class="Fa">head1</var> list. A singly-linked tail queue should be used + if this macro is needed in high-usage code paths or to operate on long + lists.</p> +<p class="Pp">The macro <code class="Nm">SLIST_EMPTY</code> evaluates to true if + there are no elements in the list. The + <code class="Nm">SLIST_EMPTY_ATOMIC</code> variant has the same behavior, + but can be safely used in contexts where it is possible that a different + thread is concurrently updating the list.</p> +<p class="Pp">The macro <code class="Nm">SLIST_ENTRY</code> declares a structure + that connects the elements in the list.</p> +<p class="Pp">The macro <code class="Nm">SLIST_FIRST</code> returns the first + element in the list or NULL if the list is empty.</p> +<p class="Pp">The macro <code class="Nm">SLIST_FOREACH</code> traverses the list + referenced by <var class="Fa">head</var> in the forward direction, assigning + each element in turn to <var class="Fa">var</var>.</p> +<p class="Pp">The macro <code class="Nm">SLIST_FOREACH_FROM</code> behaves + identically to <code class="Nm">SLIST_FOREACH</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found SLIST element and begins the loop at + <var class="Fa">var</var> instead of the first element in the SLIST + referenced by <var class="Fa">head</var>.</p> +<p class="Pp" id="SLIST_FOREACH">The macro + <code class="Nm">SLIST_FOREACH_SAFE</code> traverses the list referenced by + <var class="Fa">head</var> in the forward direction, assigning each element + in turn to <var class="Fa">var</var>. However, unlike + <a class="permalink" href="#SLIST_FOREACH"><code class="Fn">SLIST_FOREACH</code></a>() + here it is permitted to both remove <var class="Fa">var</var> as well as + free it from within the loop safely without interfering with the + traversal.</p> +<p class="Pp">The macro <code class="Nm">SLIST_FOREACH_FROM_SAFE</code> behaves + identically to <code class="Nm">SLIST_FOREACH_SAFE</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found SLIST element and begins the loop at + <var class="Fa">var</var> instead of the first element in the SLIST + referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">SLIST_INIT</code> initializes the list + referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">SLIST_INSERT_HEAD</code> inserts the + new element <var class="Fa">elm</var> at the head of the list.</p> +<p class="Pp">The macro <code class="Nm">SLIST_INSERT_AFTER</code> inserts the + new element <var class="Fa">elm</var> after the element + <var class="Fa">listelm</var>.</p> +<p class="Pp">The macro <code class="Nm">SLIST_NEXT</code> returns the next + element in the list.</p> +<p class="Pp">The macro <code class="Nm">SLIST_REMOVE_AFTER</code> removes the + element after <var class="Fa">elm</var> from the list. Unlike + <var class="Fa">SLIST_REMOVE</var>, this macro does not traverse the entire + list.</p> +<p class="Pp">The macro <code class="Nm">SLIST_REMOVE_HEAD</code> removes the + element <var class="Fa">elm</var> 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 + <var class="Fa">SLIST_REMOVE</var> macro.</p> +<p class="Pp">The macro <code class="Nm">SLIST_REMOVE</code> removes the element + <var class="Fa">elm</var> from the list. Use of this macro should be avoided + as it traverses the entire list. A doubly-linked list should be used if this + macro is needed in high-usage code paths or to operate on long lists.</p> +<p class="Pp">The macro <code class="Nm">SLIST_SPLIT_AFTER</code> splits the + list referenced by <var class="Fa">head</var>, making + <var class="Fa">rest</var> reference the list formed by elements after + <var class="Fa">elm</var> in <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">SLIST_SWAP</code> swaps the contents of + <var class="Fa">head1</var> and <var class="Fa">head2</var>.</p> +</section> +<section class="Sh"> +<h1 class="Sh" id="SINGLY-LINKED_LIST_EXAMPLE"><a class="permalink" href="#SINGLY-LINKED_LIST_EXAMPLE">SINGLY-LINKED + LIST EXAMPLE</a></h1> +<div class="Bd Li"> +<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(&head); /* Initialize the list. */ + +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); + /* Forward traversal. */ +SLIST_FOREACH(np, &head, entries) + np-> ... + /* Safe forward traversal. */ +SLIST_FOREACH_SAFE(np, &head, entries, np_temp) { + np->do_stuff(); + ... + SLIST_REMOVE(&head, np, entry, entries); + free(np); +} + +while (!SLIST_EMPTY(&head)) { /* List Deletion. */ + n1 = SLIST_FIRST(&head); + SLIST_REMOVE_HEAD(&head, entries); + free(n1); +}</pre> +</div> +</section> +<section class="Sh"> +<h1 class="Sh" id="SINGLY-LINKED_TAIL_QUEUES"><a class="permalink" href="#SINGLY-LINKED_TAIL_QUEUES">SINGLY-LINKED + TAIL QUEUES</a></h1> +<p class="Pp">A singly-linked tail queue is headed by a structure defined by the + <code class="Nm">STAILQ_HEAD</code> 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 O(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 <var class="Fa">STAILQ_HEAD</var> structure is declared as + follows:</p> +<div class="Bd Pp Bd-indent Li"> +<pre>STAILQ_HEAD(HEADNAME, TYPE) head;</pre> +</div> +<p class="Pp">where <code class="Li">HEADNAME</code> is the name of the + structure to be defined, and <code class="Li">TYPE</code> 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:</p> +<div class="Bd Pp Bd-indent Li"> +<pre>struct HEADNAME *headp;</pre> +</div> +<p class="Pp">(The names <code class="Li">head</code> and + <code class="Li">headp</code> are user selectable.)</p> +<p class="Pp">The macro <code class="Nm">STAILQ_HEAD_INITIALIZER</code> + evaluates to an initializer for the tail queue + <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_CONCAT</code> concatenates the + tail queue headed by <var class="Fa">head2</var> onto the end of the one + headed by <var class="Fa">head1</var> removing all entries from the + former.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_EMPTY</code> evaluates to true + if there are no items on the tail queue. The + <code class="Nm">STAILQ_EMPTY_ATOMIC</code> variant has the same behavior, + but can be safely used in contexts where it is possible that a different + thread is concurrently updating the queue.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_ENTRY</code> declares a + structure that connects the elements in the tail queue.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_FIRST</code> returns the first + item on the tail queue or NULL if the tail queue is empty.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_FOREACH</code> traverses the + tail queue referenced by <var class="Fa">head</var> in the forward + direction, assigning each element in turn to <var class="Fa">var</var>.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_FOREACH_FROM</code> behaves + identically to <code class="Nm">STAILQ_FOREACH</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found STAILQ element and begins the loop at + <var class="Fa">var</var> instead of the first element in the STAILQ + referenced by <var class="Fa">head</var>.</p> +<p class="Pp" id="STAILQ_FOREACH">The macro + <code class="Nm">STAILQ_FOREACH_SAFE</code> traverses the tail queue + referenced by <var class="Fa">head</var> in the forward direction, assigning + each element in turn to <var class="Fa">var</var>. However, unlike + <a class="permalink" href="#STAILQ_FOREACH"><code class="Fn">STAILQ_FOREACH</code></a>() + here it is permitted to both remove <var class="Fa">var</var> as well as + free it from within the loop safely without interfering with the + traversal.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_FOREACH_FROM_SAFE</code> behaves + identically to <code class="Nm">STAILQ_FOREACH_SAFE</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found STAILQ element and begins the loop at + <var class="Fa">var</var> instead of the first element in the STAILQ + referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_INIT</code> initializes the tail + queue referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_INSERT_HEAD</code> inserts the + new element <var class="Fa">elm</var> at the head of the tail queue.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_INSERT_TAIL</code> inserts the + new element <var class="Fa">elm</var> at the end of the tail queue.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_INSERT_AFTER</code> inserts the + new element <var class="Fa">elm</var> after the element + <var class="Fa">listelm</var>.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_LAST</code> returns the last + item on the tail queue. If the tail queue is empty the return value is + <code class="Dv">NULL</code>.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_NEXT</code> returns the next + item on the tail queue, or NULL this item is the last.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_REMOVE_AFTER</code> removes the + element after <var class="Fa">elm</var> from the tail queue. Unlike + <var class="Fa">STAILQ_REMOVE</var>, this macro does not traverse the entire + tail queue.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_REMOVE_HEAD</code> 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 <var class="Fa">STAILQ_REMOVE</var> + macro.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_REMOVE</code> removes the + element <var class="Fa">elm</var> from the tail queue. Use of this macro + should be avoided as it traverses the entire list. A doubly-linked tail + queue should be used if this macro is needed in high-usage code paths or to + operate on long tail queues.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_REVERSE</code> reverses the + queue in place.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_SPLIT_AFTER</code> splits the + tail queue referenced by <var class="Fa">head</var>, making + <var class="Fa">rest</var> reference the tail queue formed by elements after + <var class="Fa">elm</var> in <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">STAILQ_SWAP</code> swaps the contents + of <var class="Fa">head1</var> and <var class="Fa">head2</var>.</p> +</section> +<section class="Sh"> +<h1 class="Sh" id="SINGLY-LINKED_TAIL_QUEUE_EXAMPLE"><a class="permalink" href="#SINGLY-LINKED_TAIL_QUEUE_EXAMPLE">SINGLY-LINKED + TAIL QUEUE EXAMPLE</a></h1> +<div class="Bd Li"> +<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(&head); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +STAILQ_INSERT_HEAD(&head, n1, entries); + +n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +STAILQ_INSERT_TAIL(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +STAILQ_INSERT_AFTER(&head, n1, n2, entries); + /* Deletion. */ +STAILQ_REMOVE(&head, n2, entry, entries); +free(n2); + /* Deletion from the head. */ +n3 = STAILQ_FIRST(&head); +STAILQ_REMOVE_HEAD(&head, entries); +free(n3); + /* Forward traversal. */ +STAILQ_FOREACH(np, &head, entries) + np-> ... + /* Safe forward traversal. */ +STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { + np->do_stuff(); + ... + STAILQ_REMOVE(&head, np, entry, entries); + free(np); +} + /* TailQ Deletion. */ +while (!STAILQ_EMPTY(&head)) { + n1 = STAILQ_FIRST(&head); + STAILQ_REMOVE_HEAD(&head, entries); + free(n1); +} + /* Faster TailQ Deletion. */ +n1 = STAILQ_FIRST(&head); +while (n1 != NULL) { + n2 = STAILQ_NEXT(n1, entries); + free(n1); + n1 = n2; +} +STAILQ_INIT(&head);</pre> +</div> +</section> +<section class="Sh"> +<h1 class="Sh" id="LISTS"><a class="permalink" href="#LISTS">LISTS</a></h1> +<p class="Pp">A list is headed by a structure defined by the + <code class="Nm">LIST_HEAD</code> 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 + <var class="Fa">LIST_HEAD</var> structure is declared as follows:</p> +<div class="Bd Pp Bd-indent Li"> +<pre>LIST_HEAD(HEADNAME, TYPE) head;</pre> +</div> +<p class="Pp">where <var class="Fa">HEADNAME</var> is the name of the structure + to be defined, and <var class="Fa">TYPE</var> 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:</p> +<div class="Bd Pp Bd-indent Li"> +<pre>struct HEADNAME *headp;</pre> +</div> +<p class="Pp">(The names <code class="Li">head</code> and + <code class="Li">headp</code> are user selectable.)</p> +<p class="Pp">The macro <code class="Nm">LIST_HEAD_INITIALIZER</code> evaluates + to an initializer for the list <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">LIST_CONCAT</code> concatenates the + list headed by <var class="Fa">head2</var> onto the end of the one headed by + <var class="Fa">head1</var> removing all entries from the former. Use of + this macro should be avoided as it traverses the entirety of the + <var class="Fa">head1</var> list. A tail queue should be used if this macro + is needed in high-usage code paths or to operate on long lists.</p> +<p class="Pp">The macro <code class="Nm">LIST_EMPTY</code> evaluates to true if + there are no elements in the list. The + <code class="Nm">LIST_EMPTY_ATOMIC</code> variant has the same behavior, but + can be safely used in contexts where it is possible that a different thread + is concurrently updating the list.</p> +<p class="Pp">The macro <code class="Nm">LIST_ENTRY</code> declares a structure + that connects the elements in the list.</p> +<p class="Pp">The macro <code class="Nm">LIST_FIRST</code> returns the first + element in the list or NULL if the list is empty.</p> +<p class="Pp">The macro <code class="Nm">LIST_FOREACH</code> traverses the list + referenced by <var class="Fa">head</var> in the forward direction, assigning + each element in turn to <var class="Fa">var</var>.</p> +<p class="Pp">The macro <code class="Nm">LIST_FOREACH_FROM</code> behaves + identically to <code class="Nm">LIST_FOREACH</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found LIST element and begins the loop at + <var class="Fa">var</var> instead of the first element in the LIST + referenced by <var class="Fa">head</var>.</p> +<p class="Pp" id="LIST_FOREACH">The macro + <code class="Nm">LIST_FOREACH_SAFE</code> traverses the list referenced by + <var class="Fa">head</var> in the forward direction, assigning each element + in turn to <var class="Fa">var</var>. However, unlike + <a class="permalink" href="#LIST_FOREACH"><code class="Fn">LIST_FOREACH</code></a>() + here it is permitted to both remove <var class="Fa">var</var> as well as + free it from within the loop safely without interfering with the + traversal.</p> +<p class="Pp">The macro <code class="Nm">LIST_FOREACH_FROM_SAFE</code> behaves + identically to <code class="Nm">LIST_FOREACH_SAFE</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found LIST element and begins the loop at + <var class="Fa">var</var> instead of the first element in the LIST + referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">LIST_INIT</code> initializes the list + referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">LIST_INSERT_HEAD</code> inserts the new + element <var class="Fa">elm</var> at the head of the list.</p> +<p class="Pp">The macro <code class="Nm">LIST_INSERT_AFTER</code> inserts the + new element <var class="Fa">elm</var> after the element + <var class="Fa">listelm</var>.</p> +<p class="Pp">The macro <code class="Nm">LIST_INSERT_BEFORE</code> inserts the + new element <var class="Fa">elm</var> before the element + <var class="Fa">listelm</var>.</p> +<p class="Pp">The macro <code class="Nm">LIST_NEXT</code> returns the next + element in the list, or NULL if this is the last.</p> +<p class="Pp">The macro <code class="Nm">LIST_PREV</code> returns the previous + element in the list, or NULL if this is the first. List + <var class="Fa">head</var> must contain element + <var class="Fa">elm</var>.</p> +<p class="Pp">The macro <code class="Nm">LIST_REMOVE</code> removes the element + <var class="Fa">elm</var> from the list.</p> +<p class="Pp" id="LIST_REPLACE">The macro + <a class="permalink" href="#LIST_REPLACE"><code class="Fn">LIST_REPLACE</code></a>() + replaces the element <var class="Fa">elm</var> with + <var class="Fa">new</var> in the list. The element <var class="Fa">new</var> + must not already be on a list.</p> +<p class="Pp">The macro <code class="Nm">LIST_SPLIT_AFTER</code> splits the list + referenced by <var class="Fa">head</var>, making <var class="Fa">rest</var> + reference the list formed by elements after <var class="Fa">elm</var> in + <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">LIST_SWAP</code> swaps the contents of + <var class="Fa">head1</var> and <var class="Fa">head2</var>.</p> +</section> +<section class="Sh"> +<h1 class="Sh" id="LIST_EXAMPLE"><a class="permalink" href="#LIST_EXAMPLE">LIST + EXAMPLE</a></h1> +<div class="Bd Li"> +<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(&head); /* Initialize the list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +LIST_INSERT_HEAD(&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, &head, entries) + np-> ... + + /* Safe forward traversal. */ +LIST_FOREACH_SAFE(np, &head, entries, np_temp) { + np->do_stuff(); + ... + LIST_REMOVE(np, entries); + free(np); +} + +while (!LIST_EMPTY(&head)) { /* List Deletion. */ + n1 = LIST_FIRST(&head); + LIST_REMOVE(n1, entries); + free(n1); +} + +n1 = LIST_FIRST(&head); /* Faster List Deletion. */ +while (n1 != NULL) { + n2 = LIST_NEXT(n1, entries); + free(n1); + n1 = n2; +} +LIST_INIT(&head);</pre> +</div> +</section> +<section class="Sh"> +<h1 class="Sh" id="TAIL_QUEUES"><a class="permalink" href="#TAIL_QUEUES">TAIL + QUEUES</a></h1> +<p class="Pp">A tail queue is headed by a structure defined by the + <code class="Nm">TAILQ_HEAD</code> 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 <var class="Fa">TAILQ_HEAD</var> structure is declared as + follows:</p> +<div class="Bd Pp Bd-indent Li"> +<pre>TAILQ_HEAD(HEADNAME, TYPE) head;</pre> +</div> +<p class="Pp">where <code class="Li">HEADNAME</code> is the name of the + structure to be defined, and <code class="Li">TYPE</code> 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:</p> +<div class="Bd Pp Bd-indent Li"> +<pre>struct HEADNAME *headp;</pre> +</div> +<p class="Pp">(The names <code class="Li">head</code> and + <code class="Li">headp</code> are user selectable.)</p> +<p class="Pp">The macro <code class="Nm">TAILQ_HEAD_INITIALIZER</code> evaluates + to an initializer for the tail queue <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_CONCAT</code> concatenates the + tail queue headed by <var class="Fa">head2</var> onto the end of the one + headed by <var class="Fa">head1</var> removing all entries from the + former.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_EMPTY</code> evaluates to true if + there are no items on the tail queue. The + <code class="Nm">TAILQ_EMPTY_ATOMIC</code> variant has the same behavior, + but can be safely used in contexts where it is possible that a different + thread is concurrently updating the queue.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_ENTRY</code> declares a structure + that connects the elements in the tail queue.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_FIRST</code> returns the first + item on the tail queue or NULL if the tail queue is empty.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_FOREACH</code> traverses the tail + queue referenced by <var class="Fa">head</var> in the forward direction, + assigning each element in turn to <var class="Fa">var</var>. + <var class="Fa">var</var> is set to <code class="Dv">NULL</code> if the loop + completes normally, or if there were no elements.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_FOREACH_FROM</code> behaves + identically to <code class="Nm">TAILQ_FOREACH</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found TAILQ element and begins the loop at + <var class="Fa">var</var> instead of the first element in the TAILQ + referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_FOREACH_REVERSE</code> traverses + the tail queue referenced by <var class="Fa">head</var> in the reverse + direction, assigning each element in turn to <var class="Fa">var</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_FOREACH_REVERSE_FROM</code> + behaves identically to <code class="Nm">TAILQ_FOREACH_REVERSE</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found TAILQ element and begins the reverse loop at + <var class="Fa">var</var> instead of the last element in the TAILQ + referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macros <code class="Nm">TAILQ_FOREACH_SAFE</code> and + <code class="Nm">TAILQ_FOREACH_REVERSE_SAFE</code> traverse the list + referenced by <var class="Fa">head</var> in the forward or reverse direction + respectively, assigning each element in turn to <var class="Fa">var</var>. + However, unlike their unsafe counterparts, + <code class="Nm">TAILQ_FOREACH</code> and + <code class="Nm">TAILQ_FOREACH_REVERSE</code> permit to both remove + <var class="Fa">var</var> as well as free it from within the loop safely + without interfering with the traversal.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_FOREACH_FROM_SAFE</code> behaves + identically to <code class="Nm">TAILQ_FOREACH_SAFE</code> when + <var class="Fa">var</var> is NULL, else it treats <var class="Fa">var</var> + as a previously found TAILQ element and begins the loop at + <var class="Fa">var</var> instead of the first element in the TAILQ + referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_FOREACH_REVERSE_FROM_SAFE</code> + behaves identically to <code class="Nm">TAILQ_FOREACH_REVERSE_SAFE</code> + when <var class="Fa">var</var> is NULL, else it treats + <var class="Fa">var</var> as a previously found TAILQ element and begins the + reverse loop at <var class="Fa">var</var> instead of the last element in the + TAILQ referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_INIT</code> initializes the tail + queue referenced by <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_INSERT_HEAD</code> inserts the + new element <var class="Fa">elm</var> at the head of the tail queue.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_INSERT_TAIL</code> inserts the + new element <var class="Fa">elm</var> at the end of the tail queue.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_INSERT_AFTER</code> inserts the + new element <var class="Fa">elm</var> after the element + <var class="Fa">listelm</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_INSERT_BEFORE</code> inserts the + new element <var class="Fa">elm</var> before the element + <var class="Fa">listelm</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_LAST</code> returns the last item + on the tail queue. If the tail queue is empty the return value is + <code class="Dv">NULL</code>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_NEXT</code> returns the next item + on the tail queue, or NULL if this item is the last.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_PREV</code> returns the previous + item on the tail queue, or NULL if this item is the first.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_REMOVE</code> removes the element + <var class="Fa">elm</var> from the tail queue.</p> +<p class="Pp" id="TAILQ_REPLACE">The macro + <a class="permalink" href="#TAILQ_REPLACE"><code class="Fn">TAILQ_REPLACE</code></a>() + replaces the element <var class="Fa">elm</var> with + <var class="Fa">new</var> in the tail queue. The element + <var class="Fa">new</var> must not already be on a list.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_SPLIT_AFTER</code> splits the + tail queue referenced by <var class="Fa">head</var>, making + <var class="Fa">rest</var> reference the tail queue formed by elements after + <var class="Fa">elm</var> in <var class="Fa">head</var>.</p> +<p class="Pp">The macro <code class="Nm">TAILQ_SWAP</code> swaps the contents of + <var class="Fa">head1</var> and <var class="Fa">head2</var>.</p> +</section> +<section class="Sh"> +<h1 class="Sh" id="TAIL_QUEUE_EXAMPLE"><a class="permalink" href="#TAIL_QUEUE_EXAMPLE">TAIL + QUEUE EXAMPLE</a></h1> +<div class="Bd Li"> +<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, *n4, *np; + +TAILQ_INIT(&head); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +TAILQ_INSERT_HEAD(&head, n1, entries); + +n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +TAILQ_INSERT_TAIL(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +TAILQ_INSERT_AFTER(&head, n1, n2, entries); + +n3 = malloc(sizeof(struct entry)); /* Insert before. */ +TAILQ_INSERT_BEFORE(n2, n3, entries); + +TAILQ_REMOVE(&head, n2, entries); /* Deletion. */ +free(n2); + +n4 = malloc(sizeof(struct entry)); /* Replacement. */ +TAILQ_REPLACE(&head, n3, n4, entries); +free(n3); + /* Forward traversal. */ +TAILQ_FOREACH(np, &head, entries) + np-> ... + /* Safe forward traversal. */ +TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { + np->do_stuff(); + ... + TAILQ_REMOVE(&head, np, entries); + free(np); +} + /* Reverse traversal. */ +TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) + np-> ... + /* TailQ Deletion. */ +while (!TAILQ_EMPTY(&head)) { + n1 = TAILQ_FIRST(&head); + TAILQ_REMOVE(&head, n1, entries); + free(n1); +} + /* Faster TailQ Deletion. */ +n1 = TAILQ_FIRST(&head); +while (n1 != NULL) { + n2 = TAILQ_NEXT(n1, entries); + free(n1); + n1 = n2; +} +TAILQ_INIT(&head);</pre> +</div> +</section> +<section class="Sh"> +<h1 class="Sh" id="DIAGNOSTICS"><a class="permalink" href="#DIAGNOSTICS">DIAGNOSTICS</a></h1> +<p class="Pp"><code class="Nm">queue(3)</code> provides several diagnostic and + debugging facilities.</p> +<p class="Pp">Check code that performs basic integrity and API conformance + checks is automatically inserted when using queue macros in the kernel if + compiling it with <var class="Va">INVARIANTS</var>. One can request + insertion or elision of check code by respectively defining one of the + macros <var class="Va">QUEUE_MACRO_DEBUG_ASSERTIONS</var> or + <var class="Va">QUEUE_MACRO_NO_DEBUG_ASSERTIONS</var> before first inclusion + of <code class="In"><<a class="In">sys/queue.h</a>></code>. When check + code encounters an anomaly, it panics the kernel or aborts the program. To + this end, in the kernel or in <var class="Va">_STANDALONE</var> builds, it + by default calls <code class="Fn">panic</code>(), while in userland builds + it prints the diagnostic message on <code class="Dv">stderr</code> and then + calls <code class="Fn">abort</code>(). These behaviors can be overridden by + defining a custom <code class="Fn">QMD_PANIC</code>() macro before first + inclusion of <code class="In"><<a class="In">sys/queue.h</a>></code>. + The diagnostic messages automatically include the source file, line and + function where the failing check occurred. This behavior can be overridden + by defining a custom <code class="Fn">QMD_ASSERT</code>() macro before first + inclusion of + <code class="In"><<a class="In">sys/queue.h</a>></code>.</p> +<p class="Pp">The <code class="Fn">SLIST_REMOVE_PREVPTR</code>() macro is + available to aid debugging:</p> +<dl class="Bl-hang Bd-indent"> + <dt><code class="Fn">SLIST_REMOVE_PREVPTR</code>(<var class="Fa">TYPE + **prev</var>, <var class="Fa">TYPE *elm</var>, <var class="Fa">SLIST_ENTRY + NAME</var>)</dt> + <dd> + <p class="Pp">Removes element <var class="Fa">elm</var>, which must directly + follow the element whose <var class="Va">&SLIST_NEXT()</var> is + <var class="Fa">prev</var>, from the list. This macro may insert, under + conditions detailed above, check code that validates that + <var class="Fa">elm</var> indeed follows <var class="Fa">prev</var> in + the list (through the <code class="Fn">QMD_SLIST_CHECK_PREVPTR</code>() + macro).</p> + </dd> +</dl> +<p class="Pp">When debugging, it can be useful to trace queue changes. To enable + tracing, define the macro <var class="Va">QUEUE_MACRO_DEBUG_TRACE</var>. + Note that, at the moment, only macros for regular tail queues have been + instrumented.</p> +<p class="Pp">It can also be useful to trash pointers that have been unlinked + from a queue, to detect use after removal. To enable pointer trashing, + define the macro <var class="Va">QUEUE_MACRO_DEBUG_TRASH</var> at compile + time. Note that, at the moment, only a limited number of macros have been + instrumented. The macro + <code class="Fn">QMD_IS_TRASHED</code>(<var class="Fa">void *ptr</var>) + returns true if <var class="Fa">ptr</var> has been trashed by the + <var class="Va">QUEUE_MACRO_DEBUG_TRASH</var> option.</p> +</section> +<section class="Sh"> +<h1 class="Sh" id="SEE_ALSO"><a class="permalink" href="#SEE_ALSO">SEE + ALSO</a></h1> +<p class="Pp"><a class="Xr">arb(3)</a>, <a class="Xr">tree(3)</a></p> +</section> +<section class="Sh"> +<h1 class="Sh" id="HISTORY"><a class="permalink" href="#HISTORY">HISTORY</a></h1> +<p class="Pp">The <code class="Nm">queue</code> functions first appeared in + <span class="Ux">4.4BSD</span>.</p> +</section> +</div> +<table class="foot"> + <tr> + <td class="foot-date">April 28, 2025</td> + <td class="foot-os">FreeBSD 15.0</td> + </tr> +</table> |