summaryrefslogtreecommitdiffstats
path: root/man3/circleq.3
diff options
context:
space:
mode:
Diffstat (limited to 'man3/circleq.3')
-rw-r--r--man3/circleq.3318
1 files changed, 318 insertions, 0 deletions
diff --git a/man3/circleq.3 b/man3/circleq.3
new file mode 100644
index 0000000..c03ab16
--- /dev/null
+++ b/man3/circleq.3
@@ -0,0 +1,318 @@
+.\" Copyright (c) 1993
+.\" The Regents of the University of California. All rights reserved.
+.\" and Copyright (c) 2020 by Alejandro Colomar <alx@kernel.org>
+.\"
+.\" SPDX-License-Identifier: BSD-3-Clause
+.\"
+.\"
+.TH CIRCLEQ 3 2023-05-03 "Linux man-pages 6.05.01"
+.SH NAME
+CIRCLEQ_EMPTY,
+CIRCLEQ_ENTRY,
+CIRCLEQ_FIRST,
+CIRCLEQ_FOREACH,
+CIRCLEQ_FOREACH_REVERSE,
+CIRCLEQ_HEAD,
+CIRCLEQ_HEAD_INITIALIZER,
+CIRCLEQ_INIT,
+CIRCLEQ_INSERT_AFTER,
+CIRCLEQ_INSERT_BEFORE,
+CIRCLEQ_INSERT_HEAD,
+CIRCLEQ_INSERT_TAIL,
+CIRCLEQ_LAST,
+CIRCLEQ_LOOP_NEXT,
+CIRCLEQ_LOOP_PREV,
+CIRCLEQ_NEXT,
+CIRCLEQ_PREV,
+CIRCLEQ_REMOVE
+\- implementation of a doubly linked circular queue
+.SH LIBRARY
+Standard C library
+.RI ( libc ", " \-lc )
+.SH SYNOPSIS
+.nf
+.B #include <sys/queue.h>
+.PP
+.B CIRCLEQ_ENTRY(TYPE);
+.PP
+.B CIRCLEQ_HEAD(HEADNAME, TYPE);
+.BI "CIRCLEQ_HEAD CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD " head );
+.BI "void CIRCLEQ_INIT(CIRCLEQ_HEAD *" head );
+.PP
+.BI "int CIRCLEQ_EMPTY(CIRCLEQ_HEAD *" head );
+.PP
+.BI "void CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *" head ,
+.BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
+.BI "void CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *" head ,
+.BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
+.BI "void CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *" head ", struct TYPE *" listelm ,
+.BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
+.BI "void CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *" head ", struct TYPE *" listelm ,
+.BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
+.PP
+.BI "struct TYPE *CIRCLEQ_FIRST(CIRCLEQ_HEAD *" head );
+.BI "struct TYPE *CIRCLEQ_LAST(CIRCLEQ_HEAD *" head );
+.BI "struct TYPE *CIRCLEQ_PREV(struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
+.BI "struct TYPE *CIRCLEQ_NEXT(struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
+.BI "struct TYPE *CIRCLEQ_LOOP_PREV(CIRCLEQ_HEAD *" head ,
+.BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
+.BI "struct TYPE *CIRCLEQ_LOOP_NEXT(CIRCLEQ_HEAD *" head ,
+.BI " struct TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
+.PP
+.BI "CIRCLEQ_FOREACH(struct TYPE *" var ", CIRCLEQ_HEAD *" head ,
+.BI " CIRCLEQ_ENTRY " NAME );
+.BI "CIRCLEQ_FOREACH_REVERSE(struct TYPE *" var ", CIRCLEQ_HEAD *" head ,
+.BI " CIRCLEQ_ENTRY " NAME );
+.PP
+.BI "void CIRCLEQ_REMOVE(CIRCLEQ_HEAD *" head ", struct TYPE *" elm ,
+.BI " CIRCLEQ_ENTRY " NAME );
+.fi
+.SH DESCRIPTION
+These macros define and operate on doubly linked circular queues.
+.PP
+In the macro definitions,
+.I TYPE
+is the name of a user-defined structure,
+that must contain a field of type
+.IR CIRCLEQ_ENTRY ,
+named
+.IR NAME .
+The argument
+.I HEADNAME
+is the name of a user-defined structure
+that must be declared using the macro
+.BR CIRCLEQ_HEAD ().
+.SS Creation
+A circular queue is headed by a structure defined by the
+.BR CIRCLEQ_HEAD ()
+macro.
+This structure contains a pair of pointers,
+one to the first element in the queue
+and the other to the last element in the 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
+.I CIRCLEQ_HEAD
+structure is declared as follows:
+.PP
+.in +4
+.EX
+CIRCLEQ_HEAD(HEADNAME, TYPE) head;
+.EE
+.in
+.PP
+where
+.I struct HEADNAME
+is the structure to be defined, and
+.I 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:
+.PP
+.in +4
+.EX
+struct HEADNAME *headp;
+.EE
+.in
+.PP
+(The names
+.I head
+and
+.I headp
+are user selectable.)
+.PP
+.BR CIRCLEQ_ENTRY ()
+declares a structure that connects the elements in the queue.
+.PP
+.BR CIRCLEQ_HEAD_INITIALIZER ()
+evaluates to an initializer for the queue
+.IR head .
+.PP
+.BR CIRCLEQ_INIT ()
+initializes the queue referenced by
+.IR head .
+.PP
+.BR CIRCLEQ_EMPTY ()
+evaluates to true if there are no items on the queue.
+.SS Insertion
+.BR CIRCLEQ_INSERT_HEAD ()
+inserts the new element
+.I elm
+at the head of the queue.
+.PP
+.BR CIRCLEQ_INSERT_TAIL ()
+inserts the new element
+.I elm
+at the end of the queue.
+.PP
+.BR CIRCLEQ_INSERT_BEFORE ()
+inserts the new element
+.I elm
+before the element
+.IR listelm .
+.PP
+.BR CIRCLEQ_INSERT_AFTER ()
+inserts the new element
+.I elm
+after the element
+.IR listelm .
+.SS Traversal
+.BR CIRCLEQ_FIRST ()
+returns the first item on the queue.
+.PP
+.BR CIRCLEQ_LAST ()
+returns the last item on the queue.
+.PP
+.BR CIRCLEQ_PREV ()
+returns the previous item on the queue, or
+.I &head
+if this item is the first one.
+.PP
+.BR CIRCLEQ_NEXT ()
+returns the next item on the queue, or
+.I &head
+if this item is the last one.
+.PP
+.BR CIRCLEQ_LOOP_PREV ()
+returns the previous item on the queue.
+If
+.I elm
+is the first element on the queue, the last element is returned.
+.PP
+.BR CIRCLEQ_LOOP_NEXT ()
+returns the next item on the queue.
+If
+.I elm
+is the last element on the queue, the first element is returned.
+.PP
+.BR CIRCLEQ_FOREACH ()
+traverses the queue referenced by
+.I head
+in the forward direction, assigning each element in turn to
+.IR var .
+.I var
+is set to
+.I &head
+if the loop completes normally, or if there were no elements.
+.PP
+.BR CIRCLEQ_FOREACH_REVERSE ()
+traverses the queue referenced by
+.I head
+in the reverse direction,
+assigning each element in turn to
+.IR var .
+.SS Removal
+.BR CIRCLEQ_REMOVE ()
+removes the element
+.I elm
+from the queue.
+.SH RETURN VALUE
+.BR CIRCLEQ_EMPTY ()
+returns nonzero if the queue is empty,
+and zero if the queue contains at least one entry.
+.PP
+.BR CIRCLEQ_FIRST (),
+.BR CIRCLEQ_LAST (),
+.BR CIRCLEQ_LOOP_PREV (),
+and
+.BR CIRCLEQ_LOOP_NEXT ()
+return a pointer to the first, last, previous, or next
+.I TYPE
+structure, respectively.
+.PP
+.BR CIRCLEQ_PREV (),
+and
+.BR CIRCLEQ_NEXT ()
+are similar to their
+.BR CIRCLEQ_LOOP_* ()
+counterparts,
+except that if the argument is the first or last element, respectively,
+they return
+.IR &head .
+.PP
+.BR CIRCLEQ_HEAD_INITIALIZER ()
+returns an initializer that can be assigned to the queue
+.IR head .
+.SH STANDARDS
+BSD.
+.SH BUGS
+.BR CIRCLEQ_FOREACH ()
+and
+.BR CIRCLEQ_FOREACH_REVERSE ()
+don't allow
+.I var
+to be removed or freed within the loop,
+as it would interfere with the traversal.
+.BR CIRCLEQ_FOREACH_SAFE ()
+and
+.BR CIRCLEQ_FOREACH_REVERSE_SAFE (),
+which are present on the BSDs but are not present in glibc,
+fix this limitation by allowing
+.I var
+to safely be removed from the list and freed from within the loop
+without interfering with the traversal.
+.SH EXAMPLES
+.\" SRC BEGIN (circleq.c)
+.EX
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/queue.h>
+\&
+struct entry {
+ int data;
+ CIRCLEQ_ENTRY(entry) entries; /* Queue */
+};
+\&
+CIRCLEQ_HEAD(circlehead, entry);
+\&
+int
+main(void)
+{
+ struct entry *n1, *n2, *n3, *np;
+ struct circlehead head; /* Queue head */
+ int i;
+\&
+ CIRCLEQ_INIT(&head); /* Initialize the 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);
+\&
+ n3 = malloc(sizeof(struct entry)); /* Insert before */
+ CIRCLEQ_INSERT_BEFORE(&head, n2, n3, entries);
+\&
+ CIRCLEQ_REMOVE(&head, n2, entries); /* Deletion */
+ free(n2);
+ /* Forward traversal */
+ i = 0;
+ CIRCLEQ_FOREACH(np, &head, entries)
+ np\->data = i++;
+ /* Reverse traversal */
+ CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
+ printf("%i\en", np\->data);
+ /* Queue deletion */
+ n1 = CIRCLEQ_FIRST(&head);
+ while (n1 != (void *)&head) {
+ n2 = CIRCLEQ_NEXT(n1, entries);
+ free(n1);
+ n1 = n2;
+ }
+ CIRCLEQ_INIT(&head);
+\&
+ exit(EXIT_SUCCESS);
+}
+.EE
+.\" SRC END
+.SH SEE ALSO
+.BR insque (3),
+.BR queue (7)