commit 965d778b2682158cb9d362c71bce8eb61c4df21d Author: Nick Mathewson <nickm@torproject.org> Date: Tue Oct 30 19:16:07 2012 -0400 Add a copy of the queue(3) manpage to the git repository. See 7105 --- src/ext/tor_queue.txt | 883 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 883 insertions(+), 0 deletions(-) diff --git a/src/ext/tor_queue.txt b/src/ext/tor_queue.txt new file mode 100644 index 0000000..f284e71 --- /dev/null +++ b/src/ext/tor_queue.txt @@ -0,0 +1,883 @@ +Below follows the manpage for tor_queue.h, as included with OpenBSD's +sys/queue.h. License follows at the end of the file. + +====================================================================== +QUEUE(3) OpenBSD Programmer's Manual QUEUE(3) + +NAME + SLIST_ENTRY, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_FIRST, SLIST_NEXT, + SLIST_END, SLIST_EMPTY, SLIST_FOREACH, SLIST_FOREACH_SAFE, SLIST_INIT, + SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_REMOVE_AFTER, + SLIST_REMOVE_HEAD, SLIST_REMOVE, LIST_ENTRY, LIST_HEAD, + LIST_HEAD_INITIALIZER, LIST_FIRST, LIST_NEXT, LIST_END, LIST_EMPTY, + LIST_FOREACH, LIST_FOREACH_SAFE, LIST_INIT, LIST_INSERT_AFTER, + LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_REMOVE, LIST_REPLACE, + SIMPLEQ_ENTRY, SIMPLEQ_HEAD, SIMPLEQ_HEAD_INITIALIZER, SIMPLEQ_FIRST, + SIMPLEQ_NEXT, SIMPLEQ_END, SIMPLEQ_EMPTY, SIMPLEQ_FOREACH, + SIMPLEQ_FOREACH_SAFE, SIMPLEQ_INIT, SIMPLEQ_INSERT_AFTER, + SIMPLEQ_INSERT_HEAD, SIMPLEQ_INSERT_TAIL, SIMPLEQ_REMOVE_AFTER, + SIMPLEQ_REMOVE_HEAD, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, + TAILQ_FIRST, TAILQ_NEXT, TAILQ_END, TAILQ_LAST, TAILQ_PREV, TAILQ_EMPTY, + TAILQ_FOREACH, TAILQ_FOREACH_SAFE, TAILQ_FOREACH_REVERSE, + TAILQ_FOREACH_REVERSE_SAFE, TAILQ_INIT, TAILQ_INSERT_AFTER, + TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, + TAILQ_REPLACE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_HEAD_INITIALIZER, + CIRCLEQ_FIRST, CIRCLEQ_LAST, CIRCLEQ_END, CIRCLEQ_NEXT, CIRCLEQ_PREV, + CIRCLEQ_EMPTY, CIRCLEQ_FOREACH, CIRCLEQ_FOREACH_SAFE, + CIRCLEQ_FOREACH_REVERSE_SAFE, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, + CIRCLEQ_INSERT_BEFORE, CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, + CIRCLEQ_REMOVE, CIRCLEQ_REPLACE - implementations of singly-linked lists, + doubly-linked lists, simple queues, tail queues, and circular queues + +SYNOPSIS + #include <sys/queue.h> + + SLIST_ENTRY(TYPE); + + SLIST_HEAD(HEADNAME, TYPE); + + SLIST_HEAD_INITIALIZER(SLIST_HEAD head); + + struct TYPE * + SLIST_FIRST(SLIST_HEAD *head); + + struct TYPE * + SLIST_NEXT(struct TYPE *listelm, SLIST_ENTRY NAME); + + struct TYPE * + SLIST_END(SLIST_HEAD *head); + + int + SLIST_EMPTY(SLIST_HEAD *head); + + SLIST_FOREACH(VARNAME, SLIST_HEAD *head, SLIST_ENTRY NAME); + + SLIST_FOREACH_SAFE(VARNAME, SLIST_HEAD *head, SLIST_ENTRY + NAME, TEMP_VARNAME); + + void + SLIST_INIT(SLIST_HEAD *head); + + void + SLIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm, SLIST_ENTRY + NAME); + + void + SLIST_INSERT_HEAD(SLIST_HEAD *head, struct TYPE *elm, SLIST_ENTRY NAME); + + void + SLIST_REMOVE_AFTER(struct TYPE *elm, SLIST_ENTRY NAME); + + void + SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME); + + void + SLIST_REMOVE(SLIST_HEAD *head, struct TYPE *elm, TYPE, SLIST_ENTRY NAME); + + LIST_ENTRY(TYPE); + + LIST_HEAD(HEADNAME, TYPE); + + LIST_HEAD_INITIALIZER(LIST_HEAD head); + + struct TYPE * + LIST_FIRST(LIST_HEAD *head); + + struct TYPE * + LIST_NEXT(struct TYPE *listelm, LIST_ENTRY NAME); + + struct TYPE * + LIST_END(LIST_HEAD *head); + + int + LIST_EMPTY(LIST_HEAD *head); + + LIST_FOREACH(VARNAME, LIST_HEAD *head, LIST_ENTRY NAME); + + LIST_FOREACH_SAFE(VARNAME, LIST_HEAD *head, LIST_ENTRY + NAME, TEMP_VARNAME); + + void + LIST_INIT(LIST_HEAD *head); + + void + LIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm, LIST_ENTRY + NAME); + + void + LIST_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, LIST_ENTRY + NAME); + + void + LIST_INSERT_HEAD(LIST_HEAD *head, struct TYPE *elm, LIST_ENTRY NAME); + + void + LIST_REMOVE(struct TYPE *elm, LIST_ENTRY NAME); + + void + LIST_REPLACE(struct TYPE *elm, struct TYPE *elm2, LIST_ENTRY NAME); + + SIMPLEQ_ENTRY(TYPE); + + SIMPLEQ_HEAD(HEADNAME, TYPE); + + SIMPLEQ_HEAD_INITIALIZER(SIMPLEQ_HEAD head); + + struct TYPE * + SIMPLEQ_FIRST(SIMPLEQ_HEAD *head); + + struct TYPE * + SIMPLEQ_NEXT(struct TYPE *listelm, SIMPLEQ_ENTRY NAME); + + struct TYPE * + SIMPLEQ_END(SIMPLEQ_HEAD *head); + + int + SIMPLEQ_EMPTY(SIMPLEQ_HEAD *head); + + SIMPLEQ_FOREACH(VARNAME, SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY NAME); + + SIMPLEQ_FOREACH_SAFE(VARNAME, SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY + NAME, TEMP_VARNAME); + + void + SIMPLEQ_INIT(SIMPLEQ_HEAD *head); + + void + SIMPLEQ_INSERT_AFTER(SIMPLEQ_HEAD *head, struct TYPE *listelm, struct + TYPE *elm, SIMPLEQ_ENTRY NAME); + + void + SIMPLEQ_INSERT_HEAD(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY + NAME); + + void + SIMPLEQ_INSERT_TAIL(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY + NAME); + + void + SIMPLEQ_REMOVE_AFTER(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY + NAME); + + void + SIMPLEQ_REMOVE_HEAD(SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY NAME); + + TAILQ_ENTRY(TYPE); + + TAILQ_HEAD(HEADNAME, TYPE); + + TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head); + + struct TYPE * + TAILQ_FIRST(TAILQ_HEAD *head); + + struct TYPE * + TAILQ_NEXT(struct TYPE *listelm, TAILQ_ENTRY NAME); + + struct TYPE * + TAILQ_END(TAILQ_HEAD *head); + + struct TYPE * + TAILQ_LAST(TAILQ_HEAD *head, HEADNAME NAME); + + struct TYPE * + TAILQ_PREV(struct TYPE *listelm, HEADNAME NAME, TAILQ_ENTRY NAME); + + int + TAILQ_EMPTY(TAILQ_HEAD *head); + + TAILQ_FOREACH(VARNAME, TAILQ_HEAD *head, TAILQ_ENTRY NAME); + + TAILQ_FOREACH_SAFE(VARNAME, TAILQ_HEAD *head, TAILQ_ENTRY + NAME, TEMP_VARNAME); + + TAILQ_FOREACH_REVERSE(VARNAME, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY + NAME); + + TAILQ_FOREACH_REVERSE_SAFE(VARNAME, TAILQ_HEAD + *head, HEADNAME, TAILQ_ENTRY NAME, TEMP_VARNAME); + + void + TAILQ_INIT(TAILQ_HEAD *head); + + void + TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm, struct TYPE + *elm, TAILQ_ENTRY NAME); + + void + TAILQ_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, TAILQ_ENTRY + NAME); + + void + TAILQ_INSERT_HEAD(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); + + void + TAILQ_INSERT_TAIL(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); + + void + TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); + + void + TAILQ_REPLACE(TAILQ_HEAD *head, struct TYPE *elm, struct TYPE + *elm2, TAILQ_ENTRY NAME); + + CIRCLEQ_ENTRY(TYPE); + + CIRCLEQ_HEAD(HEADNAME, TYPE); + + CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD head); + + struct TYPE * + CIRCLEQ_FIRST(CIRCLEQ_HEAD *head); + + struct TYPE * + CIRCLEQ_LAST(CIRCLEQ_HEAD *head); + + struct TYPE * + CIRCLEQ_END(CIRCLEQ_HEAD *head); + + struct TYPE * + CIRCLEQ_NEXT(struct TYPE *listelm, CIRCLEQ_ENTRY NAME); + + struct TYPE * + CIRCLEQ_PREV(struct TYPE *listelm, CIRCLEQ_ENTRY NAME); + + int + CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head); + + CIRCLEQ_FOREACH(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME); + + CIRCLEQ_FOREACH_SAFE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY + NAME, TEMP_VARNAME); + + CIRCLEQ_FOREACH_REVERSE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME); + + CIRCLEQ_FOREACH_REVERSE_SAFE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY + NAME, TEMP_VARNAME); + + void + CIRCLEQ_INIT(CIRCLEQ_HEAD *head); + + void + CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, struct TYPE *listelm, struct + TYPE *elm, CIRCLEQ_ENTRY NAME); + + void + CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, struct TYPE *listelm, struct + TYPE *elm, CIRCLEQ_ENTRY NAME); + + void + CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY + NAME); + + void + CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY + NAME); + + void + CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY NAME); + + void + CIRCLEQ_REPLACE(CIRCLEQ_HEAD *head, struct TYPE *elm, struct TYPE + *elm2, CIRCLEQ_ENTRY NAME); + +DESCRIPTION + These macros define and operate on five types of data structures: singly- + linked lists, simple queues, lists, tail queues, and circular queues. + All five structures support the following functionality: + + 1. Insertion of a new entry at the head of the list. + 2. Insertion of a new entry after any element in the list. + 3. Removal of an entry from the head of the list. + 4. Forward traversal through the list. + + Singly-linked lists are the simplest of the five 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. + + Simple queues add the following functionality: + + 1. Entries can be added at the end of a list. + + However: + + 1. All list insertions must specify the head of the list. + 2. Each head entry requires two pointers rather than one. + 3. Code size is about 15% greater and operations run about 20% + slower than singly-linked lists. + + Simple queues are ideal for applications with large datasets and few or + no removals, or for implementing a FIFO queue. + + All doubly linked types of data structures (lists, tail queues, and + circle queues) additionally allow: + + 1. Insertion of a new entry before any element in the list. + 2. Removal of any entry in the list. + + However: + + 1. Each element requires two pointers rather than one. + 2. Code size and execution time of operations (except for + removal) is about twice that of the singly-linked data- + structures. + + Lists are the simplest of the doubly linked data structures and support + only the above functionality over singly-linked lists. + + Tail queues add the following functionality: + + 1. Entries can be added at the end of a list. + 2. They may be traversed backwards, at a cost. + + However: + + 1. All list insertions and removals must specify the head of the + list. + 2. Each head entry requires two pointers rather than one. + 3. Code size is about 15% greater and operations run about 20% + slower than singly-linked lists. + + Circular queues add the following functionality: + + 1. Entries can be added at the end of a list. + 2. They may be traversed backwards, from tail to head. + + However: + + 1. All list insertions and removals must specify the head of the + list. + 2. Each head entry requires two pointers rather than one. + 3. The termination condition for traversal is more complex. + 4. Code size is about 40% greater and operations run about 45% + slower than lists. + + In the macro definitions, TYPE is the name tag of a user defined + structure that must contain a field of type SLIST_ENTRY, LIST_ENTRY, + SIMPLEQ_ENTRY, TAILQ_ENTRY, or CIRCLEQ_ENTRY, named NAME. The argument + HEADNAME is the name tag of a user defined structure that must be + declared using the macros SLIST_HEAD(), LIST_HEAD(), SIMPLEQ_HEAD(), + TAILQ_HEAD(), or CIRCLEQ_HEAD(). See the examples below for further + explanation of how these macros are used. + +SINGLY-LINKED LISTS + A singly-linked list is headed by a structure defined by the SLIST_HEAD() + macro. This structure contains a single pointer to the first element on + the list. The elements are singly linked for minimum space and pointer + manipulation overhead at the expense of O(n) removal for arbitrary + elements. New elements can be added to the list after an existing + element or at the head of the list. A SLIST_HEAD structure is declared + as follows: + + SLIST_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the list. A pointer + to the head of the list can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The HEADNAME facility is often not used, leading to the following bizarre + code: + + SLIST_HEAD(, TYPE) head, *headp; + + The SLIST_ENTRY() macro declares a structure that connects the elements + in the list. + + The SLIST_INIT() macro initializes the list referenced by head. + + The list can also be initialized statically by using the + SLIST_HEAD_INITIALIZER() macro like this: + + SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head); + + The SLIST_INSERT_HEAD() macro inserts the new element elm at the head of + the list. + + The SLIST_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The SLIST_REMOVE_HEAD() macro removes the first element of the list + pointed by head. + + The SLIST_REMOVE_AFTER() macro removes the list element immediately + following elm. + + The SLIST_REMOVE() macro removes the element elm of the list pointed by + head. + + The SLIST_FIRST() and SLIST_NEXT() macros can be used to traverse the + list: + + for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, NAME)) + + Or, for simplicity, one can use the SLIST_FOREACH() macro: + + SLIST_FOREACH(np, head, NAME) + + The macro SLIST_FOREACH_SAFE() traverses the list referenced by head in a + forward direction, assigning each element in turn to var. However, + unlike SLIST_FOREACH() it is permitted to remove var as well as free it + from within the loop safely without interfering with the traversal. + + The SLIST_EMPTY() macro should be used to check whether a simple list is + empty. + +SINGLY-LINKED LIST EXAMPLE + SLIST_HEAD(listhead, entry) head; + struct entry { + ... + SLIST_ENTRY(entry) entries; /* Simple list. */ + ... + } *n1, *n2, *np; + + SLIST_INIT(&head); /* Initialize simple 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_FOREACH(np, &head, entries) /* Forward traversal. */ + np-> ... + + while (!SLIST_EMPTY(&head)) { /* Delete. */ + n1 = SLIST_FIRST(&head); + SLIST_REMOVE_HEAD(&head, entries); + free(n1); + } + + +LISTS + A list is headed by a structure defined by the LIST_HEAD() 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 LIST_HEAD structure is declared as follows: + + LIST_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the list. A pointer + to the head of the list can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The HEADNAME facility is often not used, leading to the following bizarre + code: + + LIST_HEAD(, TYPE) head, *headp; + + The LIST_ENTRY() macro declares a structure that connects the elements in + the list. + + The LIST_INIT() macro initializes the list referenced by head. + + The list can also be initialized statically by using the + LIST_HEAD_INITIALIZER() macro like this: + + LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head); + + The LIST_INSERT_HEAD() macro inserts the new element elm at the head of + the list. + + The LIST_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The LIST_INSERT_BEFORE() macro inserts the new element elm before the + element listelm. + + The LIST_REMOVE() macro removes the element elm from the list. + + The LIST_REPLACE() macro replaces the list element elm with the new + element elm2. + + The LIST_FIRST() and LIST_NEXT() macros can be used to traverse the list: + + for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, NAME)) + + Or, for simplicity, one can use the LIST_FOREACH() macro: + + LIST_FOREACH(np, head, NAME) + + The macro LIST_FOREACH_SAFE() traverses the list referenced by head in a + forward direction, assigning each element in turn to var. However, + unlike LIST_FOREACH() it is permitted to remove var as well as free it + from within the loop safely without interfering with the traversal. + + The LIST_EMPTY() macro should be used to check whether a list is empty. + +LIST EXAMPLE + LIST_HEAD(listhead, entry) head; + struct entry { + ... + LIST_ENTRY(entry) entries; /* List. */ + ... + } *n1, *n2, *np; + + LIST_INIT(&head); /* Initialize 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); + + n2 = malloc(sizeof(struct entry)); /* Insert before. */ + LIST_INSERT_BEFORE(n1, n2, entries); + /* Forward traversal. */ + LIST_FOREACH(np, &head, entries) + np-> ... + + while (!LIST_EMPTY(&head)) /* Delete. */ + n1 = LIST_FIRST(&head); + LIST_REMOVE(n1, entries); + free(n1); + } + +SIMPLE QUEUES + A simple queue is headed by a structure defined by the SIMPLEQ_HEAD() + macro. This structure contains a pair of pointers, one to the first + element in the simple queue and the other to the last element in the + simple queue. The elements are singly linked. New elements can be added + to the queue after an existing element, at the head of the queue or at + the tail of the queue. A SIMPLEQ_HEAD structure is declared as follows: + + SIMPLEQ_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the queue. A pointer + to the head of the queue can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The SIMPLEQ_ENTRY() macro declares a structure that connects the elements + in the queue. + + The SIMPLEQ_INIT() macro initializes the queue referenced by head. + + The queue can also be initialized statically by using the + SIMPLEQ_HEAD_INITIALIZER() macro like this: + + SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head); + + The SIMPLEQ_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The SIMPLEQ_INSERT_HEAD() macro inserts the new element elm at the head + of the queue. + + The SIMPLEQ_INSERT_TAIL() macro inserts the new element elm at the end of + the queue. + + The SIMPLEQ_REMOVE_AFTER() macro removes the queue element immediately + following elm. + + The SIMPLEQ_REMOVE_HEAD() macro removes the first element from the queue. + + The SIMPLEQ_FIRST() and SIMPLEQ_NEXT() macros can be used to traverse the + queue. The SIMPLEQ_FOREACH() is used for queue traversal: + + SIMPLEQ_FOREACH(np, head, NAME) + + The macro SIMPLEQ_FOREACH_SAFE() traverses the queue referenced by head + in a forward direction, assigning each element in turn to var. However, + unlike SIMPLEQ_FOREACH() it is permitted to remove var as well as free it + from within the loop safely without interfering with the traversal. + + The SIMPLEQ_EMPTY() macro should be used to check whether a list is + empty. + +SIMPLE QUEUE EXAMPLE + SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); + struct entry { + ... + SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ + ... + } *n1, *n2, *np; + + n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ + SIMPLEQ_INSERT_HEAD(&head, n1, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert after. */ + SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ + SIMPLEQ_INSERT_TAIL(&head, n2, entries); + /* Forward traversal. */ + SIMPLEQ_FOREACH(np, &head, entries) + np-> ... + /* Delete. */ + while (!SIMPLEQ_EMPTY(&head)) { + n1 = SIMPLEQ_FIRST(&head); + SIMPLEQ_REMOVE_HEAD(&head, entries); + free(n1); + } + +TAIL QUEUES + A tail queue is headed by a structure defined by the TAILQ_HEAD() 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 + queue after an existing element, before an existing element, at the head + of the queue, or at the end of the queue. A TAILQ_HEAD structure is + declared as follows: + + TAILQ_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE 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: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The TAILQ_ENTRY() macro declares a structure that connects the elements + in the tail queue. + + The TAILQ_INIT() macro initializes the tail queue referenced by head. + + The tail queue can also be initialized statically by using the + TAILQ_HEAD_INITIALIZER() macro. + + The TAILQ_INSERT_HEAD() macro inserts the new element elm at the head of + the tail queue. + + The TAILQ_INSERT_TAIL() macro inserts the new element elm at the end of + the tail queue. + + The TAILQ_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The TAILQ_INSERT_BEFORE() macro inserts the new element elm before the + element listelm. + + The TAILQ_REMOVE() macro removes the element elm from the tail queue. + + The TAILQ_REPLACE() macro replaces the list element elm with the new + element elm2. + + TAILQ_FOREACH() and TAILQ_FOREACH_REVERSE() are used for traversing a + tail queue. TAILQ_FOREACH() starts at the first element and proceeds + towards the last. TAILQ_FOREACH_REVERSE() starts at the last element and + proceeds towards the first. + + TAILQ_FOREACH(np, &head, NAME) + TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, NAME) + + The macros TAILQ_FOREACH_SAFE() and TAILQ_FOREACH_REVERSE_SAFE() traverse + the list referenced by head in a forward or reverse direction + respectively, assigning each element in turn to var. However, unlike + their unsafe counterparts, they permit both the removal of var as well as + freeing it from within the loop safely without interfering with the + traversal. + + The TAILQ_FIRST(), TAILQ_NEXT(), TAILQ_LAST() and TAILQ_PREV() macros can + be used to manually traverse a tail queue or an arbitrary part of one. + + The TAILQ_EMPTY() macro should be used to check whether a tail queue is + empty. + +TAIL QUEUE EXAMPLE + TAILQ_HEAD(tailhead, entry) head; + struct entry { + ... + TAILQ_ENTRY(entry) entries; /* Tail queue. */ + ... + } *n1, *n2, *np; + + TAILQ_INIT(&head); /* Initialize 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); + + n2 = malloc(sizeof(struct entry)); /* Insert before. */ + TAILQ_INSERT_BEFORE(n1, n2, entries); + /* Forward traversal. */ + TAILQ_FOREACH(np, &head, entries) + np-> ... + /* Manual forward traversal. */ + for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries)) + np-> ... + /* Delete. */ + while ((np = TAILQ_FIRST(&head))) { + TAILQ_REMOVE(&head, np, entries); + free(np); + } + + +CIRCULAR QUEUES + A circular queue is headed by a structure defined by the CIRCLEQ_HEAD() + macro. This structure contains a pair of pointers, one to the first + element in the circular queue and the other to the last element in the + circular queue. The elements are doubly linked so that an arbitrary + element can be removed without traversing the queue. New elements can be + added to the queue after an existing element, before an existing element, + at the head of the queue, or at the end of the queue. A CIRCLEQ_HEAD + structure is declared as follows: + + CIRCLEQ_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the circular queue. A + pointer to the head of the circular queue can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The CIRCLEQ_ENTRY() macro declares a structure that connects the elements + in the circular queue. + + The CIRCLEQ_INIT() macro initializes the circular queue referenced by + head. + + The circular queue can also be initialized statically by using the + CIRCLEQ_HEAD_INITIALIZER() macro. + + The CIRCLEQ_INSERT_HEAD() macro inserts the new element elm at the head + of the circular queue. + + The CIRCLEQ_INSERT_TAIL() macro inserts the new element elm at the end of + the circular queue. + + The CIRCLEQ_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The CIRCLEQ_INSERT_BEFORE() macro inserts the new element elm before the + element listelm. + + The CIRCLEQ_REMOVE() macro removes the element elm from the circular + queue. + + The CIRCLEQ_REPLACE() macro replaces the list element elm with the new + element elm2. + + The CIRCLEQ_FIRST(), CIRCLEQ_LAST(), CIRCLEQ_END(), CIRCLEQ_NEXT() and + CIRCLEQ_PREV() macros can be used to traverse a circular queue. The + CIRCLEQ_FOREACH() is used for circular queue forward traversal: + + CIRCLEQ_FOREACH(np, head, NAME) + + The CIRCLEQ_FOREACH_REVERSE() macro acts like CIRCLEQ_FOREACH() but + traverses the circular queue backwards. + + The macros CIRCLEQ_FOREACH_SAFE() and CIRCLEQ_FOREACH_REVERSE_SAFE() + traverse the list referenced by head in a forward or reverse direction + respectively, assigning each element in turn to var. However, unlike + their unsafe counterparts, they permit both the removal of var as well as + freeing it from within the loop safely without interfering with the + traversal. + + The CIRCLEQ_EMPTY() macro should be used to check whether a circular + queue is empty. + +CIRCULAR QUEUE EXAMPLE + CIRCLEQ_HEAD(circleq, entry) head; + struct entry { + ... + CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ + ... + } *n1, *n2, *np; + + CIRCLEQ_INIT(&head); /* Initialize circular queue. */ + + n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ + CIRCLEQ_INSERT_HEAD(&head, n1, entries); + + n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ + CIRCLEQ_INSERT_TAIL(&head, n1, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert after. */ + CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert before. */ + CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); + /* Forward traversal. */ + CIRCLEQ_FOREACH(np, &head, entries) + np-> ... + /* Reverse traversal. */ + CIRCLEQ_FOREACH_REVERSE(np, &head, entries) + np-> ... + /* Delete. */ + while (!CIRCLEQ_EMPTY(&head)) { + n1 = CIRCLEQ_FIRST(&head); + CIRCLEQ_REMOVE(&head, n1, entries); + free(n1); + } + +NOTES + It is an error to assume the next and previous fields are preserved after + an element has been removed from a list or queue. Using any macro + (except the various forms of insertion) on an element removed from a list + or queue is incorrect. An example of erroneous usage is removing the + same element twice. + + The SLIST_END(), LIST_END(), SIMPLEQ_END() and TAILQ_END() macros are + provided for symmetry with CIRCLEQ_END(). They expand to NULL and don't + serve any useful purpose. + + Trying to free a list in the following way is a common error: + + LIST_FOREACH(var, head, entry) + free(var); + free(head); + + Since var is free'd, the FOREACH macros refer to a pointer that may have + been reallocated already. A similar situation occurs when the current + element is deleted from the list. In cases like these the data + structure's FOREACH_SAFE macros should be used instead. + +HISTORY + The queue functions first appeared in 4.4BSD. + +OpenBSD 5.0 April 11, 2012 OpenBSD 5.0 +====================================================================== +.\" $OpenBSD: queue.3,v 1.56 2012/04/11 13:29:14 naddy Exp $ +.\" $NetBSD: queue.3,v 1.4 1995/07/03 00:25:36 mycroft Exp $ +.\" +.\" Copyright (c) 1993 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +