Date: Sun, 3 May 2009 17:01:11 +0400 (MSD) From: aavzz@yandex.ru To: freebsd-bugs@freebsd.org Subject: queue manpage update Message-ID: <200905031301.n43D1B97001330@localhost.my.domain>
next in thread | raw e-mail | index | archive | help
>Submitter-Id: current-users
>Originator: Alex Zimnitsky
>Organization:
>Confidential: no
>Synopsis: queue manpage update
>Severity: non-critical
>Priority: low
>Category: docs
>Class: change-request
>Release: FreeBSD-CURRENT i386
>Environment:
System: FreeBSD 7.0-RELEASE FreeBSD 7.0-RELEASE #0: Mon Sep 1 21:11:44 MSD 2008 root@:/usr/src/sys/i386/compile/GENERIC i386
>Description:
ASCII visualization of datastructures added, some wording improved (at least I think so), a tiny bug uncovered
>How-To-Repeat:
man queue
>Fix:
cp queue.3.diff /usr/src/sys/share/man/man3; patch < queue.3.diff
--- queue.3.diff begins here ---
--- queue.3.orig 2009-05-03 16:50:19.000000000 +0400
+++ queue.3 2009-05-03 16:50:25.000000000 +0400
@@ -186,12 +186,9 @@
Forward traversal through the list.
.El
.Pp
-O(n) removal of any entry in the list.
-Singly-linked lists are the simplest of the four data structures
-and support only the above functionality.
+Singly-linked lists are the simplest of the four data structures.
Singly-linked lists are ideal for applications with large datasets
-and few or no removals,
-or for implementing a LIFO queue.
+and few or no removals, or for implementing a LIFO queue.
Singly-linked lists add the following functionality:
.Bl -enum -compact -offset indent
.It
@@ -405,6 +402,31 @@
from the list.
.Sh SINGLY-LINKED LIST EXAMPLE
.Bd -literal
+
+Initialized singly linked list head:
+
++-head------+
+| |
+| slh_first-->NULL
+| |
++-----------+
+
+Non-empty singly linked list:
+
++-head------+ +->+-data-----+ +->+-data-----+
+| | | | | | | |
+| slh_first---+ | ... | | | ... |
+| | | | | | |
++-----------+ +-entry----+ | +-entry----+
+ | | | | |
+ | sle_next--- ... + | sle_next-->NULL
+ | | | |
+ +----------+ +----------+
+ | | | |
+ | ... | | ... |
+ | | | |
+ +----------+ +----------+
+
SLIST_HEAD(slisthead, entry) head =
SLIST_HEAD_INITIALIZER(head);
struct slisthead *headp; /* Singly-linked List head. */
@@ -587,6 +609,35 @@
from the tail queue.
.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
.Bd -literal
+
+Initialized singly linked tail queue head:
+
+ +-head-------+
+ | |
++-->stqh_first-->NULL
+| | stqh_last----+
+| | | |
+| +------------+ |
++----------------+
+
+Non-empty singly linked tail queue:
+
++-head-------+ +->+-data------+ +->+-data-------+
+| | | | | | | |
+| stqh_first---+ | ... | | | ... |
+| stqh_last----+ | | | | |
+| | | | | | | |
++------------+ | +-entry-----+ | +-entry------+
+ | | | | | |
+ | | stqe_next--- ... ++--> stqe_next-->NULL
+ | | | | | |
+ | +-----------+ | +------------+
+ | | | | | |
+ | | ... | | | ... |
+ | | | | | |
+ | +-----------+ | +------------+
+ +----------------------+
+
STAILQ_HEAD(stailhead, entry) head =
STAILQ_HEAD_INITIALIZER(head);
struct stailhead *headp; /* Singly-linked tail queue head. */
@@ -746,6 +797,35 @@
from the list.
.Sh LIST EXAMPLE
.Bd -literal
+
+Initialized list head:
+
++-head-----+
+| |
+| lh_first-->NULL
+| |
++----------+
+
+Non-empty list:
+
+ +-head-----+ +->+-data----+ +->+-data----+ +->+-data----+
+ | | | | | | | | | | |
++-->lh_first---+ | ... | | | ... | | | ... |
+| | | | | | | | | | |
+| +----------+ +-entry---+ | +-entry---+ | +-entry---+
+| | | | | | | | |
+| +-->le_next---++-->le_next--- ... + | le_next-->NULL
+| | | le_prev---+| | le_prev---+ | le_prev---+
+| | | | || | | | | | |
+| | +---------+ || +---------+ | +---------+ |
+| | | | || | | | | | |
+| | | ... | || | ... | | | ... | |
+| | | | || | | | | | |
+| | +---------+ || +---------+ | +---------+ |
++---------------(-------------+| | |
+ +--------------(-------------+ |
+ +------------- ... ---------------+
+
LIST_HEAD(listhead, entry) head =
LIST_HEAD_INITIALIZER(head);
struct listhead *headp; /* List head. */
@@ -945,6 +1025,39 @@
from the tail queue.
.Sh TAIL QUEUE EXAMPLE
.Bd -literal
+
+Initialized tail queue head:
+
+ +-head------+
+ | |
++-->tqh_first--->NULL
+| | tqh_last----+
+| | | |
+| +-----------+ |
++---------------+
+
+Non-empty tail queue:
+
+ +-head------+ +->+-data-----+ +->+-data-----+ +->+-data-----+
+ | | | | | | | | | | |
++-->tqh_first---+ | ... | | | ... | | | ... |
+| | tqh_last----+ | | | | | | | |
+| | | | +-entry----+ | +-entry----+ | +-entry----+
+| +-----------+ | | | | | | | | |
+| |+-->tqe_next---++-->tqe_next---...++-->tqe_next-->NULL
+| || | tqe_prev---+| | tqe_prev---+ | | tqe_prev---+
+| || | | || | | | | | | |
+| || +----------+ || +----------+ | | +----------+ |
+| || | | || | | | | | | |
+| || | ... | || | ... | | | | ... | |
+| || | | || | | | | | | |
+| || +----------+ || +----------+ | | +----------+ |
++---------------((--------------+| | | |
+ |+---------------(--------------+ | |
+ | +---------------...(--------------+
+ +-----------------------------------+
+
+
TAILQ_HEAD(tailhead, entry) head =
TAILQ_HEAD_INITIALIZER(head);
struct tailhead *headp; /* Tail queue head. */
@@ -1003,3 +1116,6 @@
.Nm queue
functions first appeared in
.Bx 4.4 .
+.Sh BUGS
+.Nm SLIST_FOREACH_PREVPTR
+macro is not used nor documented.
--- queue.3.diff ends here ---
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200905031301.n43D1B97001330>