GCQ(3) BSD Library Functions Manual GCQ(3)NAME
GCQ_INIT, GCQ_INIT_HEAD, gcq_init, gcq_init_head, gcq_q, gcq_hq,
gcq_head, gcq_remove, gcq_onlist, gcq_empty, gcq_linked,
gcq_insert_after, gcq_insert_before, gcq_insert_head, gcq_insert_tail,
gcq_tie, gcq_tie_after, gcq_tie_before, gcq_merge, gcq_merge_head,
gcq_merge_tail, gcq_clear, gcq_remove_all, GCQ_ITEM, GCQ_GOT_FIRST,
GCQ_GOT_LAST, GCQ_GOT_NEXT, GCQ_GOT_PREV, GCQ_DEQUEUED_FIRST,
GCQ_DEQUEUED_LAST, GCQ_DEQUEUED_NEXT, GCQ_DEQUEUED_PREV,
GCQ_GOT_FIRST_TYPED, GCQ_GOT_LAST_TYPED, GCQ_GOT_NEXT_TYPED,
GCQ_GOT_PREV_TYPED, GCQ_DEQUEUED_FIRST_TYPED, GCQ_DEQUEUED_LAST_TYPED,
GCQ_DEQUEUED_NEXT_TYPED, GCQ_DEQUEUED_PREV_TYPED, GCQ_GOT_FIRST_COND,
GCQ_GOT_LAST_COND, GCQ_GOT_NEXT_COND, GCQ_GOT_PREV_COND,
GCQ_DEQUEUED_FIRST_COND, GCQ_DEQUEUED_LAST_COND, GCQ_DEQUEUED_NEXT_COND,
GCQ_DEQUEUED_PREV_COND, GCQ_GOT_FIRST_COND_TYPED,
GCQ_GOT_LAST_COND_TYPED, GCQ_GOT_NEXT_COND_TYPED,
GCQ_GOT_PREV_COND_TYPED, GCQ_DEQUEUED_FIRST_COND_TYPED,
GCQ_DEQUEUED_LAST_COND_TYPED, GCQ_DEQUEUED_NEXT_COND_TYPED,
GCQ_DEQUEUED_PREV_COND_TYPED, GCQ_FOREACH, GCQ_FOREACH_REV,
GCQ_FOREACH_NVAR, GCQ_FOREACH_NVAR_REV, GCQ_FOREACH_RO,
GCQ_FOREACH_RO_REV, GCQ_FOREACH_DEQUEUED, GCQ_FOREACH_DEQUEUED_REV,
GCQ_FOREACH_TYPED, GCQ_FOREACH_REV_TYPED, GCQ_FOREACH_NVAR_TYPED,
GCQ_FOREACH_NVAR_REV_TYPED, GCQ_FOREACH_RO_TYPED,
GCQ_FOREACH_RO_REV_TYPED, GCQ_FOREACH_DEQUEUED_TYPED,
GCQ_FOREACH_DEQUEUED_REV_TYPED, GCQ_FIND, GCQ_FIND_REV, GCQ_FIND_TYPED,
GCQ_FIND_REV_TYPED — Generic Circular Queues
SYNOPSIS
#include <sys/gcq.h>
struct gcq;
struct gcq_head;
GCQ_INIT(name);
GCQ_INIT_HEAD(name);
static inline void
gcq_init(struct gcq *q);
static inline void
gcq_init_head(struct gcq_head *head);
static inline struct gcq *
gcq_q(struct gcq_head *head);
static inline struct gcq *
gcq_hq(struct gcq_head *head);
static inline struct gcq_head *
gcq_head(struct gcq *q);
static inline struct gcq *
gcq_remove(struct gcq *q);
static inline bool
gcq_onlist(struct gcq *q);
static inline bool
gcq_empty(struct gcq_head *head);
static inline bool
gcq_linked(struct gcq *prev, struct gcq *next);
static inline void
gcq_insert_after(struct gcq *on, struct gcq *off);
static inline void
gcq_insert_before(struct gcq *on, struct gcq *off);
static inline void
gcq_insert_head(struct gcq_head *head, struct gcq *q);
static inline void
gcq_insert_tail(struct gcq_head *head, struct gcq *q);
static inline void
gcq_tie(struct gcq *dst, struct gcq *src);
static inline void
gcq_tie_after(struct gcq *dst, struct gcq *src);
static inline void
gcq_tie_before(struct gcq *dst, struct gcq *src);
static inline void
gcq_merge(struct gcq *dst, struct gcq *src);
static inline void
gcq_merge_tail(struct gcq_head *dst, struct gcq_head *src);
static inline void
gcq_merge_head(struct gcq_head *dst, struct gcq_head *src);
static inline void
gcq_clear(struct gcq *q);
static inline void
gcq_remove_all(struct gcq_head *head);
type *
GCQ_ITEM(q, type, name);
bool
GCQ_GOT_FIRST(var, head);
bool
GCQ_GOT_LAST(var, head);
bool
GCQ_GOT_NEXT(var, current, head, start);
bool
GCQ_GOT_PREV(var, current, head, start);
bool
GCQ_DEQUEUED_FIRST(var, head);
bool
GCQ_DEQUEUED_LAST(var, head);
bool
GCQ_DEQUEUED_NEXT(var, current, head, start);
bool
GCQ_DEQUEUED_PREV(var, current, head, start);
bool
GCQ_GOT_FIRST_TYPED(tvar, head, type, name);
bool
GCQ_GOT_LAST_TYPED(tvar, head, type, name);
bool
GCQ_GOT_NEXT_TYPED(tvar, current, head, start, type, name);
bool
GCQ_GOT_PREV_TYPED(tvar, current, head, start, type, name);
bool
GCQ_DEQUEUED_FIRST_TYPED(tvar, head, type, name);
bool
GCQ_DEQUEUED_LAST_TYPED(tvar, head, type, name);
bool
GCQ_DEQUEUED_NEXT_TYPED(tvar, current, head, start, type, name);
bool
GCQ_DEQUEUED_PREV_TYPED(tvar, current, head, start, type, name);
bool
GCQ_GOT_FIRST_COND(var, head, cond);
bool
GCQ_GOT_LAST_COND(var, head, cond);
bool
GCQ_GOT_NEXT_COND(var, current, head, start, cond);
bool
GCQ_GOT_PREV_COND(var, current, head, start, cond);
bool
GCQ_DEQUEUED_FIRST_COND(var, head, cond);
bool
GCQ_DEQUEUED_LAST_COND(var, head, cond);
bool
GCQ_DEQUEUED_NEXT_COND(var, current, head, start, cond);
bool
GCQ_DEQUEUED_PREV_COND(var, current, head, start, cond);
bool
GCQ_GOT_FIRST_COND_TYPED(tvar, head, type, name, cond);
bool
GCQ_GOT_LAST_COND_TYPED(tvar, head, type, name, cond);
bool
GCQ_GOT_NEXT_COND_TYPED(tvar, current, head, start, type, name, cond);
bool
GCQ_GOT_PREV_COND_TYPED(tvar, current, head, start, type, name, cond);
bool
GCQ_DEQUEUED_FIRST_COND_TYPED(tvar, head, type, name, cond);
bool
GCQ_DEQUEUED_LAST_COND_TYPED(tvar, head, type, name, cond);
bool
GCQ_DEQUEUED_NEXT_COND_TYPED(tvar, current, head, start, type, name,
cond);
bool
GCQ_DEQUEUED_PREV_COND_TYPED(tvar, current, head, start, type, name,
cond);
GCQ_FOREACH(var, head);
GCQ_FOREACH_REV(var, head);
GCQ_FOREACH_NVAR(var, nvar, head);
GCQ_FOREACH_NVAR_REV(var, nvar, head);
GCQ_FOREACH_RO(var, nvar, head);
GCQ_FOREACH_RO_REV(var, nvar, head);
GCQ_FOREACH_DEQUEUED(var, nvar, head);
GCQ_FOREACH_DEQUEUED_REV(var, nvar, head);
GCQ_FOREACH_TYPED(var, head, tvar, type, name);
GCQ_FOREACH_REV_TYPED(var, head, tvar, type, name);
GCQ_FOREACH_NVAR_TYPED(var, nvar, head, tvar, type, name);
GCQ_FOREACH_NVAR_REV_TYPED(var, nvar, head, tvar, type, name);
GCQ_FOREACH_RO_TYPED(var, nvar, head, tvar, type, name);
GCQ_FOREACH_RO_REV_TYPED(var, nvar, head, tvar, type, name);
GCQ_FOREACH_DEQUEUED_TYPED(var, nvar, head, tvar, type, name);
GCQ_FOREACH_DEQUEUED_REV_TYPED(var, nvar, head, tvar, type, name);
GCQ_FIND(var, head, cond);
GCQ_FIND_REV(var, head, cond);
GCQ_FIND_TYPED(var, head, tvar, type, name, cond);
GCQ_FIND_REV_TYPED(var, head, tvar, type, name, cond);
GCQ_ASSERT(cond);
DESCRIPTION
The generic circular queue is a doubly linked list designed for efficient
merge operations and unconditional removal. All basic operations can be
performed with or without use of a separate head, allowing easy replace‐
ment of any pointers where efficient removal is desired. The meaning of
the data type will not change; direct use and defined operations can be
mixed when convenient. The basic type is:
struct gcq {
struct gcq *q_next;
struct gcq *q_prev;
};
The structure must first be initialized such that the q_next and q_prev
members point to the beginning of the struct gcq. This can be done with
gcq_init() and gcq_init_head() or with constant initializers GCQ_INIT()
and GCQ_INIT_HEAD(). A struct gcq should never be given NULL values.
The structure containing the struct gcq can be retrieved by pointer
arithmetic in the GCQ_ITEM() macro. List traversal normally requires
knowledge of the list head to safely retrieve list items.
Capitalized operation names are macros and should be assumed to cause
multiple evaluation of arguments. TYPED variants of macros set a typed
pointer variable instead of or in addition to struct gcq * arguments.
Additional type specific inlines and macros around some GCQ operations
can be useful.
A few assertions are provided when DIAGNOSTIC is defined in the kernel or
_DIAGNOSTIC is defined in userland. If GCQ_USE_ASSERT is defined prior
to header inclusions then assert() will be used for assertions and NDEBUG
can be used to turn them off. GCQ_ASSERT() is a wrapper around the used
assertion function. None of the operations accept NULL arguments, how‐
ever this is not tested by assertion.
The head is separately named for type checking but contains only a struct
gcq, a pointer to which can be retrieved via gcq_hq(). The reverse oper‐
ation is performed by gcq_head(), turning the supplied struct gcq * into
struct gcq_head *. gcq_q() returns its struct gcq * argument and is used
for type checking in GCQ_ITEM(). There are no functions for retrieving
the raw q_prev and q_next pointers as these are usually clearer when used
directly (if at all).
gcq_remove() returns the element removed and is always a valid operation
after initialization. gcq_onlist() returns false if the structure links
to itself and true otherwise. gcq_empty() is the negation of this opera‐
tion performed on a head. gcq_linked() tests if prev->q_next == next &&
next->q_prev == prev.
gcq_tie() ties src after dst such that that if the old lists are DST,
DST2 and SRC, SRC2, the new list is DST, SRC, SRC2, DST2. If dst and src
are on the same list then any elements between but not including dst and
src are cut from the list. If dst == src then the result is the same as
gcq_remove(). gcq_tie() is equivalent to gcq_tie_after() except that the
latter must only be used with arguments on separate lists or not on lists
and asserts that src != dst && dst->q_prev != src. gcq_tie_before() per‐
forms the same operation on dst->q_prev.
gcq_merge() moves any elements on list src (but not src itself) to list
dst. It is normally used with two heads via gcq_merge_head() or
gcq_merge_tail(). If GCQ_UNCONDITIONAL_MERGE is defined prior to header
inclusion then the merge operations will always perform a tie then remove
src from the new list, which may reduce code size slightly.
gcq_clear() initializes all elements currently linked with q and is nor‐
mally used with a head as gcq_remove_all().
gcq_insert_after() and gcq_insert_before() are slightly optimized ver‐
sions of gcq_tie() for the case where off is not on a list and include
assertions to this effect, which are also useful to detect missing ini‐
tialization. gcq_insert_head() and gcq_insert_tail() are the same opera‐
tions applied to a head.
GCQ_GOT_FIRST() and GCQ_GOT_LAST() set var to a pointer to the first or
last struct gcq in the list or NULL if the list is empty and return false
if empty and true otherwise. The boolean return is to emphasise that it
is not normally safe and useful to directly pass the raw first/next/etc.
pointer to another function. The macros are written such that the NULL
values will be optimized out if not otherwise used. DEQUEUED variants
also remove the member from the list. COND variants take an additional
condition that is evaluated when the macro would otherwise return true.
If the condition is false var or tvar is set to NULL and no dequeue is
performed.
GCQ_GOT_NEXT() and variants take pointers to the current position, list
head, and starting point as arguments. The list head will be skipped
when it is reached unless it is equal to the starting point; upon reach‐
ing the starting point var will be set to NULL and the macro will return
false. The next and prev macros also assert that current is on the list
unless it is equal to start. These macros are the only provided method
for iterating through the list from an arbitrary point. Traversal macros
are only provided for list heads, however gcq_head() can be used to treat
any item as a head.
Foreach variants contain an embedded for statement for iterating over a
list. Those containing REV use the q_prev pointer for traversal, others
use q_next. The plain GCQ_FOREACH() uses a single variable. NVAR vari‐
ants save the next pointer at the top of the loop so that the current
element can be removed without adjusting var. This is useful when var is
passed to a function that might remove it but will not otherwise modify
the list. When the head is reached both var and nvar elements are left
pointing to the list head. FOREACH asserts that var, and NVAR asserts
that nvar does not point to itself when starting the next loop. This
assertion takes place after the variable is tested against the head so it
is safe to remove all elements from the list. RO variants also set nvar
but assert that the two variables are linked at the end of each itera‐
tion. This is useful when calling a function that is not supposed to
remove the element passed. DEQUEUED variants are like NVAR but remove
each element before the code block is executed. TYPED variants are
equivalent to the untyped versions except that they take three extra
arguments: a typed pointer, the type name, and the member name of the
struct gcq used in this list. tvar is set to NULL when the head is
reached.
GCQ_FIND() is a foreach loop that does nothing except break when the sup‐
plied condition is true. REV and TYPED variants are available.
SEE ALSOgcc(1), _DIAGASSERT(3), assert(3), queue(3), KASSERT(9)HISTORYGCQ appeared in NetBSD 5.0.
BSD May 1, 2007 BSD
