Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
AG_QUEUE(3)	       FreeBSD Library Functions Manual		   AG_QUEUE(3)

NAME
     AG_Queue -- agar implementation of	singly-linked lists, doubly-linked
     lists, simple queues, tail	queues,	and circular queues

SYNOPSIS
     #define _USE_AGAR_QUEUE /*	For versions without AG_ prefix	*/
     #include <agar/core.h>

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 sup-
     port only the above functionality.	 Singly-linked lists are ideal for ap-
     plications	with large datasets and	few or no removals, or for implement-
     ing 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 cir-
     cle 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 re-
		moval) is about	twice that of the singly-linked	data-struc-
		tures.

     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 struc-
     ture that must contain a field of type AG_SLIST_ENTRY, AG_LIST_ENTRY,
     AG_SIMPLEQ_ENTRY, AG_TAILQ_ENTRY, or AG_CIRCLEQ_ENTRY, named NAME.	 The
     argument HEADNAME is the name tag of a user defined structure that	must
     be	declared using the macros AG_SLIST_HEAD(), AG_LIST_HEAD(),
     AG_SIMPLEQ_HEAD(),	AG_TAILQ_HEAD(), or AG_CIRCLEQ_HEAD().	See the	exam-
     ples below	for further explanation	of how these macros are	used.

SINGLY-LINKED LISTS
     AG_SLIST_ENTRY(TYPE)

     AG_SLIST_HEAD(HEADNAME, TYPE)

     AG_SLIST_HEAD_(TYPE)

     AG_SLIST_HEAD_INITIALIZER(AG_SLIST_HEAD head)

     struct TYPE * AG_SLIST_FIRST(AG_SLIST_HEAD	*head)

     struct TYPE * AG_SLIST_NEXT(struct	TYPE *listelm, AG_SLIST_ENTRY NAME)

     struct TYPE * AG_SLIST_END(AG_SLIST_HEAD *head)

     bool AG_SLIST_EMPTY(AG_SLIST_HEAD *head)

     AG_SLIST_FOREACH(VARNAME, AG_SLIST_HEAD *head, AG_SLIST_ENTRY NAME)

     AG_SLIST_FOREACH_PREVPTR(VARNAME, VARNAMEP, AG_SLIST_HEAD *head,
     AG_SLIST_ENTRY NAME)

     void AG_SLIST_INIT(AG_SLIST_HEAD *head)

     void AG_SLIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm,
     AG_SLIST_ENTRY NAME)

     void AG_SLIST_INSERT_HEAD(AG_SLIST_HEAD *head, struct TYPE	*elm,
     AG_SLIST_ENTRY NAME)

     void AG_SLIST_REMOVE_HEAD(AG_SLIST_HEAD *head, AG_SLIST_ENTRY NAME)

     void AG_SLIST_REMOVE_NEXT(AG_SLIST_HEAD *head, struct TYPE	*elm,
     AG_SLIST_ENTRY NAME)

     void AG_SLIST_REMOVE(AG_SLIST_HEAD	*head, struct TYPE *elm, TYPE,
     AG_SLIST_ENTRY NAME)

     A singly-linked list is headed by a structure defined by the
     AG_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 AG_SLIST_HEAD structure
     is	declared as follows:

	   AG_SLIST_HEAD(HEADNAME, TYPE) head;
	   AG_SLIST_HEAD_(TYPE)	head;	   /* If HEADNAME is not needed	*/

     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 AG_SLIST_ENTRY() macro	declares a structure that connects the ele-
     ments in the list.

     The AG_SLIST_INIT() macro initializes the list referenced by head.

     The list can also be initialized statically by using the
     AG_SLIST_HEAD_INITIALIZER() macro like this:

	   AG_SLIST_HEAD(HEADNAME, TYPE) head =	AG_SLIST_HEAD_INITIALIZER(head);

     The AG_SLIST_INSERT_HEAD()	macro inserts the new element elm at the head
     of	the list.

     The AG_SLIST_INSERT_AFTER() macro inserts the new element elm after the
     element listelm.

     The AG_SLIST_REMOVE_HEAD()	macro removes the first	element	of the list
     pointed by	head.

     The AG_SLIST_REMOVE_NEXT()	macro removes the list element immediately
     following elm.

     The AG_SLIST_REMOVE() macro removes the element elm of the	list pointed
     by	head.

     The AG_SLIST_FIRST() and AG_SLIST_NEXT() macros can be used to traverse
     the list:

	   for (np = AG_SLIST_FIRST(&head);
		np != NULL;
		np = AG_SLIST_NEXT(np, NAME))

     Or, for simplicity, one can use the AG_SLIST_FOREACH() macro:

	   AG_SLIST_FOREACH(np,	head, NAME)

     The AG_SLIST_FOREACH_PREVPTR() macro is similar to	AG_SLIST_FOREACH() ex-
     cept that it stores a pointer to the previous element in VARNAMEP.	 This
     provides access to	the previous element while traversing the list,	as one
     would have	with a doubly-linked list.

     The AG_SLIST_EMPTY() macro	should be used to check	whether	a simple list
     is	empty.

SINGLY-LINKED LIST EXAMPLE
     AG_SLIST_HEAD(listhead, entry) head;
     struct entry {
	     ...
	     AG_SLIST_ENTRY(entry) entries;  /*	Simple list. */
	     ...
     } *n1, *n2, *np;

     AG_SLIST_INIT(&head);		     /*	Initialize simple list.	*/

     n1	= malloc(sizeof(struct entry));	     /*	Insert at the head. */
     AG_SLIST_INSERT_HEAD(&head, n1, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert after. */
     AG_SLIST_INSERT_AFTER(n1, n2, entries);

     AG_SLIST_FOREACH(np, &head, entries)    /*	Forward	traversal. */
	     np-> ...

     while (!AG_SLIST_EMPTY(&head))	     /*	Delete.	*/
	     AG_SLIST_REMOVE_HEAD(&head, entries);

LISTS
     AG_LIST_ENTRY(TYPE)

     AG_LIST_HEAD(HEADNAME, TYPE)

     AG_LIST_HEAD_(TYPE)

     AG_LIST_HEAD_INITIALIZER(AG_LIST_HEAD head)

     struct TYPE * AG_LIST_FIRST(AG_LIST_HEAD *head)

     struct TYPE * AG_LIST_NEXT(struct TYPE *listelm, AG_LIST_ENTRY NAME)

     struct TYPE * AG_LIST_END(AG_LIST_HEAD *head)

     bool AG_LIST_EMPTY(AG_LIST_HEAD *head)

     AG_LIST_FOREACH(VARNAME, AG_LIST_HEAD *head, AG_LIST_ENTRY	NAME)

     void AG_LIST_INIT(AG_LIST_HEAD *head)

     void AG_LIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm,
     AG_LIST_ENTRY NAME)

     void AG_LIST_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm,
     AG_LIST_ENTRY NAME)

     void AG_LIST_INSERT_HEAD(AG_LIST_HEAD *head, struct TYPE *elm,
     AG_LIST_ENTRY NAME)

     void AG_LIST_REMOVE(struct	TYPE *elm, AG_LIST_ENTRY NAME)

     void AG_LIST_REPLACE(struct TYPE *elm, struct TYPE	*elm2, AG_LIST_ENTRY
     NAME)

     A list is headed by a structure defined by	the AG_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 AG_LIST_HEAD structure is declared as	follows:

	   AG_LIST_HEAD(HEADNAME, TYPE)	head;
	   AG_LIST_HEAD_(TYPE) head;	   /* If HEADNAME is not needed	*/

     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 AG_LIST_ENTRY() macro declares	a structure that connects the elements
     in	the list.

     The AG_LIST_INIT()	macro initializes the list referenced by head.

     The list can also be initialized statically by using the
     AG_LIST_HEAD_INITIALIZER()	macro like this:

	   AG_LIST_HEAD(HEADNAME, TYPE)	head = AG_LIST_HEAD_INITIALIZER(head);

     The AG_LIST_INSERT_HEAD() macro inserts the new element elm at the	head
     of	the list.

     The AG_LIST_INSERT_AFTER()	macro inserts the new element elm after	the
     element listelm.

     The AG_LIST_INSERT_BEFORE() macro inserts the new element elm before the
     element listelm.

     The AG_LIST_REMOVE() macro	removes	the element elm	from the list.

     The AG_LIST_REPLACE() macro replaces the list element elm with the	new
     element elm2.

     The AG_LIST_FIRST() and AG_LIST_NEXT() macros can be used to traverse the
     list:

	   for (np = AG_LIST_FIRST(&head);
		np != NULL;
		np = AG_LIST_NEXT(np, NAME))

     Or, for simplicity, one can use the AG_LIST_FOREACH() macro:

	   AG_LIST_FOREACH(np, head, NAME)

     The AG_LIST_EMPTY() macro should be used to check whether a list is
     empty.

LIST EXAMPLE
     AG_LIST_HEAD(listhead, entry) head;
     struct entry {
	     ...
	     AG_LIST_ENTRY(entry) entries;   /*	List. */
	     ...
     } *n1, *n2, *np;

     AG_LIST_INIT(&head);		     /*	Initialize list. */

     n1	= malloc(sizeof(struct entry));	     /*	Insert at the head. */
     AG_LIST_INSERT_HEAD(&head,	n1, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert after. */
     AG_LIST_INSERT_AFTER(n1, n2, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert before. */
     AG_LIST_INSERT_BEFORE(n1, n2, entries);
					     /*	Forward	traversal. */
     AG_LIST_FOREACH(np, &head,	entries)
	     np-> ...

     while (!AG_LIST_EMPTY(&head))	     /*	Delete.	*/
	     AG_LIST_REMOVE(AG_LIST_FIRST(&head), entries);

SIMPLE QUEUES
     AG_SIMPLEQ_ENTRY(TYPE)

     AG_SIMPLEQ_HEAD(HEADNAME, TYPE)

     AG_SIMPLEQ_HEAD_(TYPE)

     AG_SIMPLEQ_HEAD_INITIALIZER(AG_SIMPLEQ_HEAD head)

     struct TYPE * AG_SIMPLEQ_FIRST(AG_SIMPLEQ_HEAD *head)

     struct TYPE * AG_SIMPLEQ_NEXT(struct TYPE *listelm, AG_SIMPLEQ_ENTRY
     NAME)

     struct TYPE * AG_SIMPLEQ_END(AG_SIMPLEQ_HEAD *head)

     void AG_SIMPLEQ_INIT(AG_SIMPLEQ_HEAD *head)

     void AG_SIMPLEQ_INSERT_HEAD(AG_SIMPLEQ_HEAD *head,	struct TYPE *elm,
     AG_SIMPLEQ_ENTRY NAME)

     void AG_SIMPLEQ_INSERT_TAIL(AG_SIMPLEQ_HEAD *head,	struct TYPE *elm,
     AG_SIMPLEQ_ENTRY NAME)

     void AG_SIMPLEQ_INSERT_AFTER(AG_SIMPLEQ_HEAD *head, struct	TYPE *listelm,
     struct TYPE *elm, AG_SIMPLEQ_ENTRY	NAME)

     void AG_SIMPLEQ_REMOVE_HEAD(AG_SIMPLEQ_HEAD *head,	AG_SIMPLEQ_ENTRY NAME)

     A simple queue is headed by a structure defined by	the AG_SIMPLEQ_HEAD()
     macro.  This structure contains a pair of pointers, one to	the first ele-
     ment 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 AG_SIMPLEQ_HEAD structure	is declared as follows:

	   AG_SIMPLEQ_HEAD(HEADNAME, TYPE) head;
	   AG_SIMPLEQ_HEAD_(TYPE) head;	   /* If HEADNAME is not needed	*/

     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 AG_SIMPLEQ_ENTRY() macro declares a structure that connects the ele-
     ments in the queue.

     The AG_SIMPLEQ_INIT() macro initializes the queue referenced by head.

     The queue can also	be initialized statically by using the
     AG_SIMPLEQ_HEAD_INITIALIZER() macro like this:

	   AG_SIMPLEQ_HEAD(HEADNAME, TYPE) head	=
	       AG_SIMPLEQ_HEAD_INITIALIZER(head);

     The AG_SIMPLEQ_INSERT_HEAD() macro	inserts	the new	element	elm at the
     head of the queue.

     The AG_SIMPLEQ_INSERT_TAIL() macro	inserts	the new	element	elm at the end
     of	the queue.

     The AG_SIMPLEQ_INSERT_AFTER() macro inserts the new element elm after the
     element listelm.

     The AG_SIMPLEQ_REMOVE_HEAD() macro	removes	the first element from the
     queue.

     The AG_SIMPLEQ_FIRST() and	AG_SIMPLEQ_NEXT() macros can be	used to	tra-
     verse the queue.  The AG_SIMPLEQ_FOREACH()	is used	for queue traversal:

	   AG_SIMPLEQ_FOREACH(np, head,	NAME)

     The AG_SIMPLEQ_EMPTY() macro should be used to check whether a list is
     empty.

SIMPLE QUEUE EXAMPLE
     AG_SIMPLEQ_HEAD(listhead, entry) head = AG_SIMPLEQ_HEAD_INITIALIZER(head);
     struct entry {
	     ...
	     AG_SIMPLEQ_ENTRY(entry) entries;	     /*	Simple queue. */
	     ...
     } *n1, *n2, *np;

     n1	= malloc(sizeof(struct entry));	     /*	Insert at the head. */
     AG_SIMPLEQ_INSERT_HEAD(&head, n1, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert after. */
     AG_SIMPLEQ_INSERT_AFTER(&head, n1,	n2, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert at the tail. */
     AG_SIMPLEQ_INSERT_TAIL(&head, n2, entries);
					     /*	Forward	traversal. */
     AG_SIMPLEQ_FOREACH(np, &head, entries)
	     np-> ...
					     /*	Delete.	*/
     while (!AG_SIMPLEQ_EMPTY(&head))
	     AG_SIMPLEQ_REMOVE_HEAD(&head, entries);

TAIL QUEUES
     AG_TAILQ_ENTRY(TYPE)

     AG_TAILQ_HEAD(HEADNAME, TYPE)

     AG_TAILQ_HEAD_(TYPE)

     AG_TAILQ_HEAD_INITIALIZER(AG_TAILQ_HEAD head)

     struct TYPE * AG_TAILQ_FIRST(AG_TAILQ_HEAD	*head)

     struct TYPE * AG_TAILQ_NEXT(struct	TYPE *listelm, AG_TAILQ_ENTRY NAME)

     struct TYPE * AG_TAILQ_END(AG_TAILQ_HEAD *head)

     struct TYPE * AG_TAILQ_LAST(AG_TAILQ_HEAD *head, HEADNAME NAME)

     AG_TAILQ_PREV(struct TYPE *listelm, HEADNAME NAME,	AG_TAILQ_ENTRY NAME)

     bool AG_TAILQ_EMPTY(AG_TAILQ_HEAD *head)

     AG_TAILQ_FOREACH(VARNAME, AG_TAILQ_HEAD *head, AG_TAILQ_ENTRY NAME)

     AG_TAILQ_FOREACH_REVERSE(VARNAME, AG_TAILQ_HEAD *head, HEADNAME,
     AG_TAILQ_ENTRY NAME)

     void AG_TAILQ_INIT(AG_TAILQ_HEAD *head)

     void AG_TAILQ_INSERT_AFTER(AG_TAILQ_HEAD *head, struct TYPE *listelm,
     struct TYPE *elm, AG_TAILQ_ENTRY NAME)

     void AG_TAILQ_INSERT_BEFORE(struct	TYPE *listelm, struct TYPE *elm,
     AG_TAILQ_ENTRY NAME)

     void AG_TAILQ_INSERT_HEAD(AG_TAILQ_HEAD *head, struct TYPE	*elm,
     AG_TAILQ_ENTRY NAME)

     void AG_TAILQ_INSERT_TAIL(AG_TAILQ_HEAD *head, struct TYPE	*elm,
     AG_TAILQ_ENTRY NAME)

     void AG_TAILQ_REMOVE(AG_TAILQ_HEAD	*head, struct TYPE *elm,
     AG_TAILQ_ENTRY NAME)

     A tail queue is headed by a structure defined by the AG_TAILQ_HEAD()
     macro.  This structure contains a pair of pointers, one to	the first ele-
     ment 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 AG_TAILQ_HEAD
     structure is declared as follows:

	   AG_TAILQ_HEAD(HEADNAME, TYPE) head;
	   AG_TAILQ_HEAD_(TYPE)	head;	   /* If HEADNAME is not needed	*/

     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 AG_TAILQ_ENTRY() macro	declares a structure that connects the ele-
     ments in the tail queue.

     The AG_TAILQ_INIT() macro initializes the tail queue referenced by	head.

     The tail queue can	also be	initialized statically by using	the
     AG_TAILQ_HEAD_INITIALIZER() macro.

     The AG_TAILQ_INSERT_HEAD()	macro inserts the new element elm at the head
     of	the tail queue.

     The AG_TAILQ_INSERT_TAIL()	macro inserts the new element elm at the end
     of	the tail queue.

     The AG_TAILQ_INSERT_AFTER() macro inserts the new element elm after the
     element listelm.

     The AG_TAILQ_INSERT_BEFORE() macro	inserts	the new	element	elm before the
     element listelm.

     The AG_TAILQ_REMOVE() macro removes the element elm from the tail queue.

     AG_TAILQ_FOREACH()	and AG_TAILQ_FOREACH_REVERSE() are used	for traversing
     a tail queue.  AG_TAILQ_FOREACH() starts at the first element and pro-
     ceeds towards the last.  AG_TAILQ_FOREACH_REVERSE() starts	at the last
     element and proceeds towards the first.

	   AG_TAILQ_FOREACH(np,	&head, NAME)
	   AG_TAILQ_FOREACH_REVERSE(np,	&head, HEADNAME, NAME)

     The AG_TAILQ_FIRST(), AG_TAILQ_NEXT(), AG_TAILQ_LAST() and
     AG_TAILQ_PREV() macros can	be used	to manually traverse a tail queue or
     an	arbitrary part of one.

     The AG_TAILQ_EMPTY() macro	should be used to check	whether	a tail queue
     is	empty.

TAIL QUEUE EXAMPLE
     AG_TAILQ_HEAD(tailhead, entry) head;
     struct entry {
	     ...
	     AG_TAILQ_ENTRY(entry) entries;  /*	Tail queue. */
	     ...
     } *n1, *n2, *np;

     AG_TAILQ_INIT(&head);		     /*	Initialize queue. */

     n1	= malloc(sizeof(struct entry));	     /*	Insert at the head. */
     AG_TAILQ_INSERT_HEAD(&head, n1, entries);

     n1	= malloc(sizeof(struct entry));	     /*	Insert at the tail. */
     AG_TAILQ_INSERT_TAIL(&head, n1, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert after. */
     AG_TAILQ_INSERT_AFTER(&head, n1, n2, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert before. */
     AG_TAILQ_INSERT_BEFORE(n1,	n2, entries);
					     /*	Forward	traversal. */
     AG_TAILQ_FOREACH(np, &head, entries)
	     np-> ...
					     /*	Manual forward traversal. */
     for (np = n2; np != NULL; np = AG_TAILQ_NEXT(np, entries))
	     np-> ...
					     /*	Delete.	*/
     while (np = AG_TAILQ_FIRST(&head))
	     AG_TAILQ_REMOVE(&head, np,	entries);

CIRCULAR QUEUES
     AG_CIRCLEQ_ENTRY(TYPE)

     AG_CIRCLEQ_HEAD(HEADNAME, TYPE)

     AG_CIRCLEQ_HEAD_(TYPE)

     AG_CIRCLEQ_HEAD_INITIALIZER(AG_CIRCLEQ_HEAD head)

     struct TYPE * AG_CIRCLEQ_FIRST(AG_CIRCLEQ_HEAD *head)

     struct TYPE * AG_CIRCLEQ_LAST(AG_CIRCLEQ_HEAD *head)

     struct TYPE * AG_CIRCLEQ_END(AG_CIRCLEQ_HEAD *head)

     struct TYPE * AG_CIRCLEQ_NEXT(struct TYPE *listelm, AG_CIRCLEQ_ENTRY
     NAME)

     struct TYPE * AG_CIRCLEQ_PREV(struct TYPE *listelm, AG_CIRCLEQ_ENTRY
     NAME)

     bool AG_CIRCLEQ_EMPTY(AG_CIRCLEQ_HEAD *head)

     AG_CIRCLEQ_FOREACH(VARNAME, AG_CIRCLEQ_HEAD *head,	AG_CIRCLEQ_ENTRY NAME)

     AG_CIRCLEQ_FOREACH_REVERSE(VARNAME, AG_CIRCLEQ_HEAD *head,
     AG_CIRCLEQ_ENTRY NAME)

     void AG_CIRCLEQ_INIT(AG_CIRCLEQ_HEAD *head)

     void AG_CIRCLEQ_INSERT_AFTER(AG_CIRCLEQ_HEAD *head, struct	TYPE *listelm,
     struct TYPE *elm, AG_CIRCLEQ_ENTRY	NAME)

     void AG_CIRCLEQ_INSERT_BEFORE(AG_CIRCLEQ_HEAD *head, struct TYPE
     *listelm, struct TYPE *elm, AG_CIRCLEQ_ENTRY NAME)

     void AG_CIRCLEQ_INSERT_HEAD(AG_CIRCLEQ_HEAD *head,	struct TYPE *elm,
     AG_CIRCLEQ_ENTRY NAME)

     void AG_CIRCLEQ_INSERT_TAIL(AG_CIRCLEQ_HEAD *head,	struct TYPE *elm,
     AG_CIRCLEQ_ENTRY NAME)

     void AG_CIRCLEQ_REMOVE(AG_CIRCLEQ_HEAD *head, struct TYPE *elm,
     AG_CIRCLEQ_ENTRY NAME)

     A circular	queue is headed	by a structure defined by the
     AG_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 ele-
     ment in the circular queue.  The elements are doubly linked so that an
     arbitrary element can be removed without traversing the queue.  New ele-
     ments can be added	to the queue after an existing element,	before an ex-
     isting element, at	the head of the	queue, or at the end of	the queue.  A
     AG_CIRCLEQ_HEAD structure is declared as follows:

	   AG_CIRCLEQ_HEAD(HEADNAME, TYPE) head;
	   AG_CIRCLEQ_HEAD_(TYPE) head;	   /* If HEADNAME is not needed	*/

     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 AG_CIRCLEQ_ENTRY() macro declares a structure that connects the ele-
     ments in the circular queue.

     The AG_CIRCLEQ_INIT() macro initializes the circular queue	referenced by
     head.

     The circular queue	can also be initialized	statically by using the
     AG_CIRCLEQ_HEAD_INITIALIZER() macro.

     The AG_CIRCLEQ_INSERT_HEAD() macro	inserts	the new	element	elm at the
     head of the circular queue.

     The AG_CIRCLEQ_INSERT_TAIL() macro	inserts	the new	element	elm at the end
     of	the circular queue.

     The AG_CIRCLEQ_INSERT_AFTER() macro inserts the new element elm after the
     element listelm.

     The AG_CIRCLEQ_INSERT_BEFORE() macro inserts the new element elm before
     the element listelm.

     The AG_CIRCLEQ_REMOVE() macro removes the element elm from	the circular
     queue.

     The AG_CIRCLEQ_FIRST(), AG_CIRCLEQ_LAST(),	AG_CIRCLEQ_END(),
     AG_CIRCLEQ_NEXT() and AG_CIRCLEQ_PREV() macros can	be used	to traverse a
     circular queue.  The AG_CIRCLEQ_FOREACH() is used for circular queue for-
     ward traversal:

	   AG_CIRCLEQ_FOREACH(np, head,	NAME)

     The AG_CIRCLEQ_FOREACH_REVERSE() macro acts like AG_CIRCLEQ_FOREACH() but
     traverses the circular queue backwards.

     The AG_CIRCLEQ_EMPTY() macro should be used to check whether a circular
     queue is empty.

CIRCULAR QUEUE EXAMPLE
     AG_CIRCLEQ_HEAD(circleq, entry) head;
     struct entry {
	     ...
	     AG_CIRCLEQ_ENTRY(entry) entries;	     /*	Circular queue.	*/
	     ...
     } *n1, *n2, *np;

     AG_CIRCLEQ_INIT(&head);		     /*	Initialize circular queue. */

     n1	= malloc(sizeof(struct entry));	     /*	Insert at the head. */
     AG_CIRCLEQ_INSERT_HEAD(&head, n1, entries);

     n1	= malloc(sizeof(struct entry));	     /*	Insert at the tail. */
     AG_CIRCLEQ_INSERT_TAIL(&head, n1, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert after. */
     AG_CIRCLEQ_INSERT_AFTER(&head, n1,	n2, entries);

     n2	= malloc(sizeof(struct entry));	     /*	Insert before. */
     AG_CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
					     /*	Forward	traversal. */
     AG_CIRCLEQ_FOREACH(np, &head, entries)
	     np-> ...
					     /*	Reverse	traversal. */
     AG_CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
	     np-> ...
					     /*	Delete.	*/
     while (!AG_CIRCLEQ_EMPTY(&head))
	     AG_CIRCLEQ_REMOVE(&head, AG_CIRCLEQ_FIRST(&head), entries);

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	(ex-
     cept 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 AG_SLIST_END(), AG_LIST_END(),	AG_SIMPLEQ_END() and AG_TAILQ_END()
     macros are	provided for symmetry with AG_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:

	   AG_LIST_FOREACH(var,	head, entry) {
		   free(var);
	   }
	   free(head);

     Since var is free'd, the FOREACH()	macro refers to	a pointer that may
     have been reallocated already.  Proper code needs a second	variable.

	   for (var = AG_LIST_FIRST(head);
		var != AG_LIST_END(head);
		var = nxt) {
		   nxt = AG_LIST_NEXT(var, entry);
		   free(var);
	   }
	   AG_LIST_INIT(head);	   /* to put the list back in order */

     A similar situation occurs	when the current element is deleted from the
     list.  Correct code saves a pointer to the	next element in	the list be-
     fore removing the element:

	   for (var = AG_LIST_FIRST(head);
		var != AG_LIST_END(head);
		var = nxt) {
		   nxt = AG_LIST_NEXT(var, entry);
		   if (some_condition) {
			   AG_LIST_REMOVE(var, entry);
			   some_function(var);
		   }
	   }

HISTORY
     The AG_Queue macros first appeared	in Agar	1.0 and	are based on the
     4.4BSD queue macros in sys/queue.h.

FreeBSD	13.0		       December	13, 1993		  FreeBSD 13.0

NAME | SYNOPSIS | DESCRIPTION | SINGLY-LINKED LISTS | SINGLY-LINKED LIST EXAMPLE | LISTS | LIST EXAMPLE | SIMPLE QUEUES | SIMPLE QUEUE EXAMPLE | TAIL QUEUES | TAIL QUEUE EXAMPLE | CIRCULAR QUEUES | CIRCULAR QUEUE EXAMPLE | NOTES | HISTORY

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=AG_Queue&sektion=3&manpath=FreeBSD+12.2-RELEASE+and+Ports>

home | help