diff options
| -rw-r--r-- | share/man/man3/queue.3 | 223 | ||||
| -rw-r--r-- | sys/sys/queue.h | 142 |
2 files changed, 21 insertions, 344 deletions
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3 index b91da86..cb1125c 100644 --- a/share/man/man3/queue.3 +++ b/share/man/man3/queue.3 @@ -90,24 +90,8 @@ .Nm TAILQ_NEXT , .Nm TAILQ_PREV , .Nm TAILQ_REMOVE , -.Nm CIRCLEQ_EMPTY , -.Nm CIRCLEQ_ENTRY , -.Nm CIRCLEQ_FIRST , -.Nm CIRCLEQ_FOREACH , -.Nm CIRCLEQ_FOREACH_REVERSE , -.Nm CIRCLEQ_HEAD , -.Nm CIRCLEQ_HEAD_INITIALIZER , -.Nm CIRCLEQ_INIT , -.Nm CIRCLEQ_INSERT_AFTER , -.Nm CIRCLEQ_INSERT_BEFORE , -.Nm CIRCLEQ_INSERT_HEAD , -.Nm CIRCLEQ_INSERT_TAIL , -.Nm CIRCLE_LAST , -.Nm CIRCLE_NEXT , -.Nm CIRCLE_PREV , -.Nm CIRCLEQ_REMOVE .Nd implementations of singly-linked lists, singly-linked tail queues, -lists, tail queues, and circular queues +lists and tail queues .Sh SYNOPSIS .Fd #include <sys/queue.h> .\" @@ -169,22 +153,6 @@ lists, tail queues, and circular queues .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" .\" -.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head" -.Fn CIRCLEQ_ENTRY "TYPE" -.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head" -.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" -.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head" -.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head" -.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head" -.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" .Sh DESCRIPTION These macros define and operate on five types of data structures: singly-linked lists, singly-linked tail queues, lists, tail queues, @@ -267,26 +235,6 @@ Code size is about 15% greater and operations run about 20% slower than singly-linked lists. .El .Pp -Circular queues add the following functionality: -.Bl -enum -compact -offset indent -.It -Entries can be added at the end of a list. -.It -They may be traversed backwards, from tail to head. -.El -However: -.Bl -enum -compact -offset indent -.It -All list insertions and removals must specify the head of the list. -.It -Each head entry requires two pointers rather than one. -.It -The termination condition for traversal is more complex. -.It -Code size is about 40% greater and operations run about 45% slower -than lists. -.El -.Pp In the macro definitions, .Fa TYPE is the name of a user defined structure, @@ -294,9 +242,8 @@ that must contain a field of type .Li SLIST_ENTRY , .Li STAILQ_ENTRY , .Li LIST_ENTRY , -.Li TAILQ_ENTRY , or -.Li CIRCLEQ_ENTRY , +.Li TAILQ_ENTRY , named .Fa NAME . The argument @@ -306,9 +253,8 @@ using the macros .Li SLIST_HEAD , .Li STAILQ_HEAD , .Li LIST_HEAD , -.Li TAILQ_HEAD , or -.Li CIRCLEQ_HEAD . +.Li TAILQ_HEAD . See the examples below for further explanation of how these macros are used. .Sh SINGLY-LINKED LISTS @@ -899,169 +845,6 @@ while (n1 != NULL) { } TAILQ_INIT(&head); .Ed -.Sh CIRCULAR QUEUES -A circular queue is headed by a structure defined by the -.Nm 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 -.Fa CIRCLEQ_HEAD -structure is declared as follows: -.Bd -literal -offset indent -CIRCLEQ_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -where -.Li HEADNAME -is the name of the structure to be defined, and -.Li 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: -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(The names -.Li head -and -.Li headp -are user selectable.) -.Pp -The macro -.Nm CIRCLEQ_HEAD_INITIALIZER -evaluates to an initializer for the circle queue -.Fa head . -.Pp -The macro -.Nm CIRCLEQ_EMPTY -evaluates to true if there are no items on the circle queue. -.Pp -The macro -.Nm CIRCLEQ_ENTRY -declares a structure that connects the elements in -the circular queue. -.Pp -The macro -.Nm CIRCLEQ_FIRST -returns the first item on the circle queue. -.Pp -The macro -.Nm CICRLEQ_FOREACH -traverses the circle queue referenced by -.Fa head -in the forward direction, assigning each element in turn to -.Fa var . -.Pp -The macro -.Nm CICRLEQ_FOREACH_REVERSE -traverses the circle queue referenced by -.Fa head -in the reverse direction, assigning each element in turn to -.Fa var . -.Pp -The macro -.Nm CIRCLEQ_INIT -initializes the circular queue referenced by -.Fa head . -.Pp -The macro -.Nm CIRCLEQ_INSERT_HEAD -inserts the new element -.Fa elm -at the head of the circular queue. -.Pp -The macro -.Nm CIRCLEQ_INSERT_TAIL -inserts the new element -.Fa elm -at the end of the circular queue. -.Pp -The macro -.Nm CIRCLEQ_INSERT_AFTER -inserts the new element -.Fa elm -after the element -.Fa listelm . -.Pp -The macro -.Nm CIRCLEQ_INSERT_BEFORE -inserts the new element -.Fa elm -before the element -.Fa listelm . -.Pp -The macro -.Nm CIRCLEQ_LAST -returns the last item on the circle queue. -.Pp -The macro -.Nm CIRCLEQ_NEXT -returns the next item on the circle queue. -.Pp -The macro -.Nm CIRCLEQ_PREV -returns the previous item on the circle queue. -.Pp -The macro -.Nm CIRCLEQ_REMOVE -removes the element -.Fa elm -from the circular queue. -.Sh CIRCULAR QUEUE EXAMPLE -.Bd -literal -CIRCLEQ_HEAD(circlehead, entry) head = - CIRCLEQ_HEAD_INITIALIZER(head); -struct circlehead *headp; /* Circular queue head. */ -struct entry { - ... - CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ - ... -} *n1, *n2, *np; - -CIRCLEQ_INIT(&head); /* Initialize the 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); - -CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */ -free(n1); - /* Forward traversal. */ -CIRCLEQ_FOREACH(np, &head, entries) - np-> ... - /* Reverse traversal. */ -CIRCLEQ_FOREACH_REVERSE(np, &head, entries) - np-> ... - /* CircleQ Deletion. */ -while (CIRCLEQ_FIRST(&head) != (void *)&head) { - n1 = CIRCLEQ_HEAD(&head); - CIRCLEQ_REMOVE(&head, n1, entries); - free(n1); -} - /* Faster CircleQ Deletion. */ -n1 = CIRCLEQ_FIRST(&head); -while (n1 != (void *)&head) { - n2 = CIRCLEQ_NEXT(n1, entries); - free(n1); - n1 = n2; -} -CIRCLEQ_INIT(&head); -.Ed .Sh HISTORY The .Nm queue diff --git a/sys/sys/queue.h b/sys/sys/queue.h index ab232b8..a4f09b1 100644 --- a/sys/sys/queue.h +++ b/sys/sys/queue.h @@ -78,35 +78,27 @@ * after an existing element, at the head of the list, or at the end of * the list. A tail queue may be traversed in either direction. * - * A circle queue is headed by a pair of pointers, one to the head of the - * list and the other to the tail of the list. The elements are doubly - * linked so that an arbitrary element can be removed without a need to - * traverse the list. New elements can be added to the list before or after - * an existing element, at the head of the list, or at the end of the list. - * A circle queue may be traversed in either direction, but has a more - * complex end of list detection. - * * For details on the use of these macros, see the queue(3) manual page. * * - * SLIST LIST STAILQ TAILQ CIRCLEQ - * _HEAD + + + + + - * _HEAD_INITIALIZER + + + + + - * _ENTRY + + + + + - * _INIT + + + + + - * _EMPTY + + + + + - * _FIRST + + + + + - * _NEXT + + + + + - * _PREV - - - + + - * _LAST - - + + + - * _FOREACH + + + + + - * _FOREACH_REVERSE - - - + + - * _INSERT_HEAD + + + + + - * _INSERT_BEFORE - + - + + - * _INSERT_AFTER + + + + + - * _INSERT_TAIL - - + + + - * _REMOVE_HEAD + - + - - - * _REMOVE + + + + + + * SLIST LIST STAILQ TAILQ + * _HEAD + + + + + * _HEAD_INITIALIZER + + + + + * _ENTRY + + + + + * _INIT + + + + + * _EMPTY + + + + + * _FIRST + + + + + * _NEXT + + + + + * _PREV - - - + + * _LAST - - + + + * _FOREACH + + + + + * _FOREACH_REVERSE - - - + + * _INSERT_HEAD + + + + + * _INSERT_BEFORE - + - + + * _INSERT_AFTER + + + + + * _INSERT_TAIL - - + + + * _REMOVE_HEAD + - + - + * _REMOVE + + + + * */ @@ -412,104 +404,6 @@ struct { \ *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ } while (0) -/* - * Circular queue declarations. - */ -#define CIRCLEQ_HEAD(name, type) \ -struct name { \ - struct type *cqh_first; /* first element */ \ - struct type *cqh_last; /* last element */ \ -} - -#define CIRCLEQ_HEAD_INITIALIZER(head) \ - { (void *)&(head), (void *)&(head) } - -#define CIRCLEQ_ENTRY(type) \ -struct { \ - struct type *cqe_next; /* next element */ \ - struct type *cqe_prev; /* previous element */ \ -} - -/* - * Circular queue functions. - */ -#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) - -#define CIRCLEQ_FIRST(head) ((head)->cqh_first) - -#define CIRCLEQ_FOREACH(var, head, field) \ - for ((var) = CIRCLEQ_FIRST((head)); \ - (var) != (void *)(head); \ - (var) = CIRCLEQ_NEXT((var), field)) - -#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ - for ((var) = CIRCLEQ_LAST((head)); \ - (var) != (void *)(head); \ - (var) = CIRCLEQ_PREV((var), field)) - -#define CIRCLEQ_INIT(head) do { \ - CIRCLEQ_FIRST((head)) = (void *)(head); \ - CIRCLEQ_LAST((head)) = (void *)(head); \ -} while (0) - -#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ - CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field); \ - CIRCLEQ_PREV((elm), field) = (listelm); \ - if (CIRCLEQ_NEXT((listelm), field) == (void *)(head)) \ - CIRCLEQ_LAST((head)) = (elm); \ - else \ - CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\ - CIRCLEQ_NEXT((listelm), field) = (elm); \ -} while (0) - -#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ - CIRCLEQ_NEXT((elm), field) = (listelm); \ - CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field); \ - if (CIRCLEQ_PREV((listelm), field) == (void *)(head)) \ - CIRCLEQ_FIRST((head)) = (elm); \ - else \ - CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\ - CIRCLEQ_PREV((listelm), field) = (elm); \ -} while (0) - -#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ - CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head)); \ - CIRCLEQ_PREV((elm), field) = (void *)(head); \ - if (CIRCLEQ_LAST((head)) == (void *)(head)) \ - CIRCLEQ_LAST((head)) = (elm); \ - else \ - CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm); \ - CIRCLEQ_FIRST((head)) = (elm); \ -} while (0) - -#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ - CIRCLEQ_NEXT((elm), field) = (void *)(head); \ - CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head)); \ - if (CIRCLEQ_FIRST((head)) == (void *)(head)) \ - CIRCLEQ_FIRST((head)) = (elm); \ - else \ - CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm); \ - CIRCLEQ_LAST((head)) = (elm); \ -} while (0) - -#define CIRCLEQ_LAST(head) ((head)->cqh_last) - -#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next) - -#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev) - -#define CIRCLEQ_REMOVE(head, elm, field) do { \ - if (CIRCLEQ_NEXT((elm), field) == (void *)(head)) \ - CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field); \ - else \ - CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) = \ - CIRCLEQ_PREV((elm), field); \ - if (CIRCLEQ_PREV((elm), field) == (void *)(head)) \ - CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field); \ - else \ - CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) = \ - CIRCLEQ_NEXT((elm), field); \ -} while (0) #ifdef _KERNEL |
