Attachment #9863 for bug #20024

View | Details | Raw Unified | Return to bug 20024
Collapse All | Expand All




 * 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 tail queue may be traversed in either direction. Tail
 * queues may be concated.
 *
 * 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

 * 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. Circle queues may be concatenated.
 *
 * For details on the use of these macros, see the queue(3) manual page.
 *

 * _INSERT_TAIL		-	-	+	+	+
 * _REMOVE_HEAD		+	-	+	-	-
 * _REMOVE		+	+	+	+	+
 * _CONCAT		-	-	-	+	+
 *
 */


	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
} while (0)

#define TAILQ_CONCAT(head1, head2, field) do {				\
	if (!TAILQ_EMPTY(head2)) {					\
		*(head1)->tqh_last = (head2)->tqh_first;		\
		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
		(head1)->tqh_last = (head2)->tqh_last;			\
		TAILQ_INIT(head2);					\
	}								\
} while (0)

#define TAILQ_REMOVE(head, elm, field) do {				\
	if (((elm)->field.tqe_next) != NULL)				\
		(elm)->field.tqe_next->field.tqe_prev = 		\

	else								\
		(head)->cqh_last->field.cqe_next = (elm);		\
	(head)->cqh_last = (elm);					\
} while (0)

#define CIRCLEQ_CONCAT(head1, head2, field) do {			\
	if (!CIRCLEQ_EMPTY(head2)) {					\
		if (!CIRCLEQ_EMPTY(head1)) {				\
			(head1)->cqh_last->field.cqe_next =		\
			    (head2)->cqh_first;				\
			(head2)->cqh_first->field.cqe_prev =		\
			    (head1)->cqh_last;				\
		} else {						\
			(head1)->cqh_first = (head2)->cqh_first;	\
			(head2)->cqh_first->field.cqe_prev =		\
			    (void *)(head1);				\
		}							\
		(head1)->cqh_last = (head2)->cqh_last;			\
		(head2)->cqh_last->field.cqe_next =			\
		    (void *)(head1);					\
		CIRCLEQ_INIT(head2);					\
	}								\
} while (0)

#define CIRCLEQ_LAST(head) ((head)->cqh_last)




.Nm TAILQ_NEXT ,
.Nm TAILQ_PREV ,
.Nm TAILQ_REMOVE ,
.Nm TAILQ_CONCAT ,
.Nm CIRCLEQ_EMPTY ,
.Nm CIRCLEQ_ENTRY ,
.Nm CIRCLEQ_FIRST ,

.Nm CIRCLE_LAST ,
.Nm CIRCLE_NEXT ,
.Nm CIRCLE_PREV ,
.Nm CIRCLEQ_REMOVE ,
.Nm CIRCLEQ_CONCAT
.Nd implementations of singly-linked lists, singly-linked tail queues,
lists, tail queues, and circular queues
.Sh SYNOPSIS

.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_CONCAT "TAILQ_HEAD *queue1" "TAILQ_HEAD *queue2" "TAILQ_ENTRY NAME"
.\"
.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
.Fn CIRCLEQ_ENTRY "TYPE"

.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"
.Fn CIRCLEQ_CONCAT "CIRCLEQ_HEAD *queue1" "CIRCLEQ_HEAD *queue2" "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,

Entries can be added at the end of a list.
.It
They may be traversed backwards, from tail to head.
.It
They may be concatenated.
.El
However:
.Bl -enum -compact -offset indent

Entries can be added at the end of a list.
.It
They may be traversed backwards, from tail to head.
.It
They may be concatenated.
.El
However:
.Bl -enum -compact -offset indent

removes the element
.Fa elm
from the tail queue.
.Pp
The macro
.Nm TAILQ_CONCAT
concatenates
.Fa queue2
onto the end of
.Fa queue1 ,
leaving
.Fa queue2
empty.
.Sh TAIL QUEUE EXAMPLE
.Bd -literal
TAILQ_HEAD(tailhead, entry) head;

removes the element
.Fa elm
from the circular queue.
.Pp
The macro
.Nm CIRCLEQ_CONCAT
concatenates
.Fa queue2
onto the end of
.Fa queue1 ,
leaving
.Fa queue2
empty.
.Sh CIRCULAR QUEUE EXAMPLE
.Bd -literal
CIRCLEQ_HEAD(circleq, entry) head;

Return to bug 20024

Lines 74-80 Link Here

(-)/usr/src/sys/sys/queue.h (-2 / +32 lines)
74	* linked so that an arbitrary element can be removed without a need to	74	* linked so that an arbitrary element can be removed without a need to
75	* traverse the list. New elements can be added to the list before or	75	* traverse the list. New elements can be added to the list before or
76	* after an existing element, at the head of the list, or at the end of	76	* after an existing element, at the head of the list, or at the end of
77	* the list. A tail queue may be traversed in either direction.	77	* the list. A tail queue may be traversed in either direction. Tail
		78	* queues may be concated.
78	*	79	*
79	* A circle queue is headed by a pair of pointers, one to the head of the	80	* A circle queue is headed by a pair of pointers, one to the head of the
80	* list and the other to the tail of the list. The elements are doubly	81	* list and the other to the tail of the list. The elements are doubly
Lines 82-88 Link Here
82	* traverse the list. New elements can be added to the list before or after	83	* traverse the list. New elements can be added to the list before or after
83	* an existing element, at the head of the list, or at the end of the list.	84	* an existing element, at the head of the list, or at the end of the list.
84	* A circle queue may be traversed in either direction, but has a more	85	* A circle queue may be traversed in either direction, but has a more
85	* complex end of list detection.	86	* complex end of list detection. Circle queues may be concatenated.
86	*	87	*
87	* For details on the use of these macros, see the queue(3) manual page.	88	* For details on the use of these macros, see the queue(3) manual page.
88	*	89	*
Lines 104-109 Link Here
104	* _INSERT_TAIL - - + + +	105	* _INSERT_TAIL - - + + +
105	* _REMOVE_HEAD + - + - -	106	* _REMOVE_HEAD + - + - -
106	* _REMOVE + + + + +	107	* _REMOVE + + + + +
		108	* _CONCAT - - - + +
107	*	109	*
108	*/	110	*/
109		111
Lines 387-392 Link Here
387	(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \	389	(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
388	} while (0)	390	} while (0)
389		391
		392	#define TAILQ_CONCAT(head1, head2, field) do { \
		393	if (!TAILQ_EMPTY(head2)) { \
		394	*(head1)->tqh_last = (head2)->tqh_first; \
		395	(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
		396	(head1)->tqh_last = (head2)->tqh_last; \
		397	TAILQ_INIT(head2); \
		398	} \
		399	} while (0)
		400
390	#define TAILQ_REMOVE(head, elm, field) do { \	401	#define TAILQ_REMOVE(head, elm, field) do { \
391	if (((elm)->field.tqe_next) != NULL) \	402	if (((elm)->field.tqe_next) != NULL) \
392	(elm)->field.tqe_next->field.tqe_prev = \	403	(elm)->field.tqe_next->field.tqe_prev = \
Lines 471-476 Link Here
471	else \	482	else \
472	(head)->cqh_last->field.cqe_next = (elm); \	483	(head)->cqh_last->field.cqe_next = (elm); \
473	(head)->cqh_last = (elm); \	484	(head)->cqh_last = (elm); \
		485	} while (0)
		486
		487	#define CIRCLEQ_CONCAT(head1, head2, field) do { \
		488	if (!CIRCLEQ_EMPTY(head2)) { \
		489	if (!CIRCLEQ_EMPTY(head1)) { \
		490	(head1)->cqh_last->field.cqe_next = \
		491	(head2)->cqh_first; \
		492	(head2)->cqh_first->field.cqe_prev = \
		493	(head1)->cqh_last; \
		494	} else { \
		495	(head1)->cqh_first = (head2)->cqh_first; \
		496	(head2)->cqh_first->field.cqe_prev = \
		497	(void *)(head1); \
		498	} \
		499	(head1)->cqh_last = (head2)->cqh_last; \
		500	(head2)->cqh_last->field.cqe_next = \
		501	(void *)(head1); \
		502	CIRCLEQ_INIT(head2); \
		503	} \
474	} while (0)	504	} while (0)
475		505
476	#define CIRCLEQ_LAST(head) ((head)->cqh_last)	506	#define CIRCLEQ_LAST(head) ((head)->cqh_last)

Lines 86-91 Link Here

(-)/usr/src/share/man/man3/queue.3 (-1 / +29 lines)
86	.Nm TAILQ_NEXT ,	86	.Nm TAILQ_NEXT ,
87	.Nm TAILQ_PREV ,	87	.Nm TAILQ_PREV ,
88	.Nm TAILQ_REMOVE ,	88	.Nm TAILQ_REMOVE ,
		89	.Nm TAILQ_CONCAT ,
89	.Nm CIRCLEQ_EMPTY ,	90	.Nm CIRCLEQ_EMPTY ,
90	.Nm CIRCLEQ_ENTRY ,	91	.Nm CIRCLEQ_ENTRY ,
91	.Nm CIRCLEQ_FIRST ,	92	.Nm CIRCLEQ_FIRST ,
Lines 100-106 Link Here
100	.Nm CIRCLE_LAST ,	101	.Nm CIRCLE_LAST ,
101	.Nm CIRCLE_NEXT ,	102	.Nm CIRCLE_NEXT ,
102	.Nm CIRCLE_PREV ,	103	.Nm CIRCLE_PREV ,
103	.Nm CIRCLEQ_REMOVE	104	.Nm CIRCLEQ_REMOVE ,
		105	.Nm CIRCLEQ_CONCAT
104	.Nd implementations of singly-linked lists, singly-linked tail queues,	106	.Nd implementations of singly-linked lists, singly-linked tail queues,
105	lists, tail queues, and circular queues	107	lists, tail queues, and circular queues
106	.Sh SYNOPSIS	108	.Sh SYNOPSIS
Lines 159-164 Link Here
159	.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"	161	.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
160	.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"	162	.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
161	.Fn TAILQ_REMOVE "TAILQ_HEAD head" "TYPE elm" "TAILQ_ENTRY NAME"	163	.Fn TAILQ_REMOVE "TAILQ_HEAD head" "TYPE elm" "TAILQ_ENTRY NAME"
		164	.Fn TAILQ_CONCAT "TAILQ_HEAD queue1" "TAILQ_HEAD queue2" "TAILQ_ENTRY NAME"
162	.\"	165	.\"
163	.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"	166	.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
164	.Fn CIRCLEQ_ENTRY "TYPE"	167	.Fn CIRCLEQ_ENTRY "TYPE"
Lines 175-180 Link Here
175	.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"	178	.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
176	.Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"	179	.Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
177	.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD head" "TYPE elm" "CIRCLEQ_ENTRY NAME"	180	.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD head" "TYPE elm" "CIRCLEQ_ENTRY NAME"
		181	.Fn CIRCLEQ_CONCAT "CIRCLEQ_HEAD queue1" "CIRCLEQ_HEAD queue2" "CIRCLEQ_ENTRY NAME"
178	.Sh DESCRIPTION	182	.Sh DESCRIPTION
179	These macros define and operate on five types of data structures:	183	These macros define and operate on five types of data structures:
180	singly-linked lists, singly-linked tail queues, lists, tail queues,	184	singly-linked lists, singly-linked tail queues, lists, tail queues,
Lines 245-250 Link Here
245	Entries can be added at the end of a list.	249	Entries can be added at the end of a list.
246	.It	250	.It
247	They may be traversed backwards, from tail to head.	251	They may be traversed backwards, from tail to head.
		252	.It
		253	They may be concatenated.
248	.El	254	.El
249	However:	255	However:
250	.Bl -enum -compact -offset indent	256	.Bl -enum -compact -offset indent
Lines 263-268 Link Here
263	Entries can be added at the end of a list.	269	Entries can be added at the end of a list.
264	.It	270	.It
265	They may be traversed backwards, from tail to head.	271	They may be traversed backwards, from tail to head.
		272	.It
		273	They may be concatenated.
266	.El	274	.El
267	However:	275	However:
268	.Bl -enum -compact -offset indent	276	.Bl -enum -compact -offset indent
Lines 826-831 Link Here
826	removes the element	834	removes the element
827	.Fa elm	835	.Fa elm
828	from the tail queue.	836	from the tail queue.
		837	.Pp
		838	The macro
		839	.Nm TAILQ_CONCAT
		840	concatenates
		841	.Fa queue2
		842	onto the end of
		843	.Fa queue1 ,
		844	leaving
		845	.Fa queue2
		846	empty.
829	.Sh TAIL QUEUE EXAMPLE	847	.Sh TAIL QUEUE EXAMPLE
830	.Bd -literal	848	.Bd -literal
831	TAILQ_HEAD(tailhead, entry) head;	849	TAILQ_HEAD(tailhead, entry) head;
Lines 984-989 Link Here
984	removes the element	1002	removes the element
985	.Fa elm	1003	.Fa elm
986	from the circular queue.	1004	from the circular queue.
		1005	.Pp
		1006	The macro
		1007	.Nm CIRCLEQ_CONCAT
		1008	concatenates
		1009	.Fa queue2
		1010	onto the end of
		1011	.Fa queue1 ,
		1012	leaving
		1013	.Fa queue2
		1014	empty.
987	.Sh CIRCULAR QUEUE EXAMPLE	1015	.Sh CIRCULAR QUEUE EXAMPLE
988	.Bd -literal	1016	.Bd -literal
989	CIRCLEQ_HEAD(circleq, entry) head;	1017	CIRCLEQ_HEAD(circleq, entry) head;