.\" $NetBSD: gcq.3,v 1.4 2017/07/03 21:30:58 wiz Exp $
.\"
.\" Not (c) 2007 Matthew Orgass
.\" This file is public domain, meaning anyone can make any use of part or all
.\" of this file including copying into other works without credit.  Any use,
.\" modified or not, is solely the responsibility of the user.  If this file
.\" is part of a collection then use in the collection is governed by the
.\" terms of the collection.
.\"
.Dd May 1, 2007
.Dt GCQ 3
.Os
.Sh NAME
.Nm GCQ_INIT ,
.Nm GCQ_INIT_HEAD ,
.Nm gcq_init ,
.Nm gcq_init_head ,
.Nm gcq_q ,
.Nm gcq_hq ,
.Nm gcq_head ,
.Nm gcq_remove ,
.Nm gcq_onlist ,
.Nm gcq_empty ,
.Nm gcq_linked ,
.Nm gcq_insert_after ,
.Nm gcq_insert_before ,
.Nm gcq_insert_head ,
.Nm gcq_insert_tail ,
.Nm gcq_tie ,
.Nm gcq_tie_after ,
.Nm gcq_tie_before ,
.Nm gcq_merge ,
.Nm gcq_merge_head ,
.Nm gcq_merge_tail ,
.Nm gcq_clear ,
.Nm gcq_remove_all ,
.Nm GCQ_ITEM ,
.Nm GCQ_GOT_FIRST ,
.Nm GCQ_GOT_LAST ,
.Nm GCQ_GOT_NEXT ,
.Nm GCQ_GOT_PREV ,
.Nm GCQ_DEQUEUED_FIRST ,
.Nm GCQ_DEQUEUED_LAST ,
.Nm GCQ_DEQUEUED_NEXT ,
.Nm GCQ_DEQUEUED_PREV ,
.Nm GCQ_GOT_FIRST_TYPED ,
.Nm GCQ_GOT_LAST_TYPED ,
.Nm GCQ_GOT_NEXT_TYPED ,
.Nm GCQ_GOT_PREV_TYPED ,
.Nm GCQ_DEQUEUED_FIRST_TYPED ,
.Nm GCQ_DEQUEUED_LAST_TYPED ,
.Nm GCQ_DEQUEUED_NEXT_TYPED ,
.Nm GCQ_DEQUEUED_PREV_TYPED ,
.Nm GCQ_GOT_FIRST_COND ,
.Nm GCQ_GOT_LAST_COND ,
.Nm GCQ_GOT_NEXT_COND ,
.Nm GCQ_GOT_PREV_COND ,
.Nm GCQ_DEQUEUED_FIRST_COND ,
.Nm GCQ_DEQUEUED_LAST_COND ,
.Nm GCQ_DEQUEUED_NEXT_COND ,
.Nm GCQ_DEQUEUED_PREV_COND ,
.Nm GCQ_GOT_FIRST_COND_TYPED ,
.Nm GCQ_GOT_LAST_COND_TYPED ,
.Nm GCQ_GOT_NEXT_COND_TYPED ,
.Nm GCQ_GOT_PREV_COND_TYPED ,
.Nm GCQ_DEQUEUED_FIRST_COND_TYPED ,
.Nm GCQ_DEQUEUED_LAST_COND_TYPED ,
.Nm GCQ_DEQUEUED_NEXT_COND_TYPED ,
.Nm GCQ_DEQUEUED_PREV_COND_TYPED ,
.Nm GCQ_FOREACH ,
.Nm GCQ_FOREACH_REV ,
.Nm GCQ_FOREACH_NVAR ,
.Nm GCQ_FOREACH_NVAR_REV ,
.Nm GCQ_FOREACH_RO ,
.Nm GCQ_FOREACH_RO_REV ,
.Nm GCQ_FOREACH_DEQUEUED ,
.Nm GCQ_FOREACH_DEQUEUED_REV ,
.Nm GCQ_FOREACH_TYPED ,
.Nm GCQ_FOREACH_REV_TYPED ,
.Nm GCQ_FOREACH_NVAR_TYPED ,
.Nm GCQ_FOREACH_NVAR_REV_TYPED ,
.Nm GCQ_FOREACH_RO_TYPED ,
.Nm GCQ_FOREACH_RO_REV_TYPED ,
.Nm GCQ_FOREACH_DEQUEUED_TYPED ,
.Nm GCQ_FOREACH_DEQUEUED_REV_TYPED ,
.Nm GCQ_FIND ,
.Nm GCQ_FIND_REV ,
.Nm GCQ_FIND_TYPED ,
.Nm GCQ_FIND_REV_TYPED
.Nd "Generic Circular Queues"
.Sh SYNOPSIS
.In sys/gcq.h
.Pp
.Vt struct gcq ;
.Vt struct gcq_head ;
.Pp
.Fn GCQ_INIT name
.Fn GCQ_INIT_HEAD name
.Pp
.Ft static inline void
.Fn gcq_init "struct gcq *q"
.Ft static inline void
.Fn gcq_init_head "struct gcq_head *head"
.Ft static inline struct gcq *
.Fn gcq_q "struct gcq_head *head"
.Ft static inline struct gcq *
.Fn gcq_hq "struct gcq_head *head"
.Ft static inline struct gcq_head *
.Fn gcq_head "struct gcq *q"
.Ft static inline struct gcq *
.Fn gcq_remove "struct gcq *q"
.Ft static inline bool
.Fn gcq_onlist "struct gcq *q"
.Ft static inline bool
.Fn gcq_empty "struct gcq_head *head"
.Ft static inline bool
.Fn gcq_linked "struct gcq *prev" "struct gcq *next"
.Ft static inline void
.Fn gcq_insert_after "struct gcq *on" "struct gcq *off"
.Ft static inline void
.Fn gcq_insert_before "struct gcq *on" "struct gcq *off"
.Ft static inline void
.Fn gcq_insert_head "struct gcq_head *head" "struct gcq *q"
.Ft static inline void
.Fn gcq_insert_tail "struct gcq_head *head" "struct gcq *q"
.Ft static inline void
.Fn gcq_tie "struct gcq *dst" "struct gcq *src"
.Ft static inline void
.Fn gcq_tie_after "struct gcq *dst" "struct gcq *src"
.Ft static inline void
.Fn gcq_tie_before "struct gcq *dst" "struct gcq *src"
.Ft static inline void
.Fn gcq_merge "struct gcq *dst" "struct gcq *src"
.Ft static inline void
.Fn gcq_merge_tail "struct gcq_head *dst" "struct gcq_head *src"
.Ft static inline void
.Fn gcq_merge_head "struct gcq_head *dst" "struct gcq_head *src"
.Ft static inline void
.Fn gcq_clear "struct gcq *q"
.Ft static inline void
.Fn gcq_remove_all "struct gcq_head *head"
.Pp
.Ft type *
.Fn GCQ_ITEM q type name
.Ft bool
.Fn GCQ_GOT_FIRST var head
.Ft bool
.Fn GCQ_GOT_LAST var head
.Ft bool
.Fn GCQ_GOT_NEXT var current head start
.Ft bool
.Fn GCQ_GOT_PREV var current head start
.Ft bool
.Fn GCQ_DEQUEUED_FIRST var head
.Ft bool
.Fn GCQ_DEQUEUED_LAST var head
.Ft bool
.Fn GCQ_DEQUEUED_NEXT var current head start
.Ft bool
.Fn GCQ_DEQUEUED_PREV var current head start
.Ft bool
.Fn GCQ_GOT_FIRST_TYPED tvar head type name
.Ft bool
.Fn GCQ_GOT_LAST_TYPED tvar head type name
.Ft bool
.Fn GCQ_GOT_NEXT_TYPED tvar current head start type name
.Ft bool
.Fn GCQ_GOT_PREV_TYPED tvar current head start type name
.Ft bool
.Fn GCQ_DEQUEUED_FIRST_TYPED tvar head type name
.Ft bool
.Fn GCQ_DEQUEUED_LAST_TYPED tvar head type name
.Ft bool
.Fn GCQ_DEQUEUED_NEXT_TYPED tvar current head start type name
.Ft bool
.Fn GCQ_DEQUEUED_PREV_TYPED tvar current head start type name
.Ft bool
.Fn GCQ_GOT_FIRST_COND var head cond
.Ft bool
.Fn GCQ_GOT_LAST_COND var head cond
.Ft bool
.Fn GCQ_GOT_NEXT_COND var current head start cond
.Ft bool
.Fn GCQ_GOT_PREV_COND var current head start cond
.Ft bool
.Fn GCQ_DEQUEUED_FIRST_COND var head cond
.Ft bool
.Fn GCQ_DEQUEUED_LAST_COND var head cond
.Ft bool
.Fn GCQ_DEQUEUED_NEXT_COND var current head start cond
.Ft bool
.Fn GCQ_DEQUEUED_PREV_COND var current head start cond
.Ft bool
.Fn GCQ_GOT_FIRST_COND_TYPED tvar head type name cond
.Ft bool
.Fn GCQ_GOT_LAST_COND_TYPED tvar head type name cond
.Ft bool
.Fn GCQ_GOT_NEXT_COND_TYPED tvar current head start type name cond
.Ft bool
.Fn GCQ_GOT_PREV_COND_TYPED tvar current head start type name cond
.Ft bool
.Fn GCQ_DEQUEUED_FIRST_COND_TYPED tvar head type name cond
.Ft bool
.Fn GCQ_DEQUEUED_LAST_COND_TYPED tvar head type name cond
.Ft bool
.Fn GCQ_DEQUEUED_NEXT_COND_TYPED tvar current head start type name cond
.Ft bool
.Fn GCQ_DEQUEUED_PREV_COND_TYPED tvar current head start type name cond
.Fn GCQ_FOREACH var head
.Fn GCQ_FOREACH_REV var head
.Fn GCQ_FOREACH_NVAR var nvar head
.Fn GCQ_FOREACH_NVAR_REV var nvar head
.Fn GCQ_FOREACH_RO var nvar head
.Fn GCQ_FOREACH_RO_REV var nvar head
.Fn GCQ_FOREACH_DEQUEUED var nvar head
.Fn GCQ_FOREACH_DEQUEUED_REV var nvar head
.Fn GCQ_FOREACH_TYPED var head tvar type name
.Fn GCQ_FOREACH_REV_TYPED var head tvar type name
.Fn GCQ_FOREACH_NVAR_TYPED var nvar head tvar type name
.Fn GCQ_FOREACH_NVAR_REV_TYPED var nvar head tvar type name
.Fn GCQ_FOREACH_RO_TYPED var nvar head tvar type name
.Fn GCQ_FOREACH_RO_REV_TYPED var nvar head tvar type name
.Fn GCQ_FOREACH_DEQUEUED_TYPED var nvar head tvar type name
.Fn GCQ_FOREACH_DEQUEUED_REV_TYPED var nvar head tvar type name
.Fn GCQ_FIND var head cond
.Fn GCQ_FIND_REV var head cond
.Fn GCQ_FIND_TYPED var head tvar type name cond
.Fn GCQ_FIND_REV_TYPED var head tvar type name cond
.Fn GCQ_ASSERT cond
.Sh 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 replacement 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:
.Bd -literal -offset indent
struct gcq {
	struct gcq *q_next;
	struct gcq *q_prev;
};
.Ed
.Pp
The structure must first be initialized such that the
.Va q_next
and
.Va q_prev
members point to the beginning of the
.Vt struct gcq .
This can be done with
.Fn gcq_init
and
.Fn gcq_init_head
or with constant initializers
.Fn GCQ_INIT
and
.Fn GCQ_INIT_HEAD .
A
.Vt struct gcq
should
.Em never
be given
.Dv NULL
values.
.Pp
The structure containing the
.Vt struct gcq
can be retrieved by pointer arithmetic in the
.Fn GCQ_ITEM
macro.
List traversal normally requires knowledge of the list head to safely
retrieve list items.
.Pp
Capitalized operation names are macros and should be assumed to cause multiple
evaluation of arguments.
.Li TYPED
variants of macros set a typed pointer variable instead of or in addition to
.Vt struct gcq *
arguments.
Additional type specific inlines and macros around some GCQ operations can be
useful.
.Pp
A few assertions are provided when
.Dv DIAGNOSTIC
is defined in the kernel or
.Dv _DIAGNOSTIC
is defined in userland.
If
.Dv GCQ_USE_ASSERT
is defined prior to header inclusions
then
.Fn assert
will be used for assertions and
.Dv NDEBUG
can be used to turn them off.
.Fn GCQ_ASSERT
is a wrapper around the used assertion function.
None of the operations accept
.Dv NULL
arguments, however this is not tested by assertion.
.Pp
The head is separately named for type checking but contains only a
.Vt struct gcq ,
a pointer to which can be retrieved via
.Fn gcq_hq .
The reverse operation is performed by
.Fn gcq_head ,
turning the supplied
.Vt struct gcq *
into
.Vt struct gcq_head * .
.Fn gcq_q
returns its
.Vt struct gcq *
argument and is used for type checking in
.Fn GCQ_ITEM .
There are no functions for retrieving the raw
.Va q_prev
and
.Va q_next
pointers as these are usually clearer when used directly (if at all).
.Pp
.Fn gcq_remove
returns the element removed and is always a valid operation after
initialization.
.Fn gcq_onlist
returns
.Dv false
if the structure links to itself and
.Dv true
otherwise.
.Fn gcq_empty
is the negation of this operation performed on a head.
.Fn gcq_linked
tests if
.Li "prev->q_next == next && next->q_prev == prev" .
.Pp
.Fn gcq_tie
ties
.Va src
after
.Va dst
such that that if the old lists are DST, DST2 and SRC, SRC2, the new list is
DST, SRC, SRC2, DST2.
If
.Va dst
and
.Va src
are on the same list then any elements between but not including
.Va dst
and
.Va src
are cut from the list.
If
.Li dst == src
then the result is the same as
.Fn gcq_remove .
.Fn gcq_tie
is equivalent to
.Fn gcq_tie_after
except that the latter must only be used with arguments on separate lists or
not on lists and asserts that
.Li "src != dst && dst->q_prev != src" .
.Fn gcq_tie_before
performs the same operation on
.Li dst->q_prev .
.Pp
.Fn gcq_merge
moves any elements on list
.Va src
(but not
.Va src
itself) to list
.Va dst .
It is normally used with two heads via
.Fn gcq_merge_head
or
.Fn gcq_merge_tail .
If
.Dv GCQ_UNCONDITIONAL_MERGE
is defined prior to header inclusion then the merge operations will always
perform a tie then remove
.Va src
from the new list, which may reduce code size slightly.
.Pp
.Fn gcq_clear
initializes all elements currently linked with
.Va q
and is normally used with a head as
.Fn gcq_remove_all .
.Pp
.Fn gcq_insert_after
and
.Fn gcq_insert_before
are slightly optimized versions of
.Fn gcq_tie
for the case where
.Va off
is not on a list and include assertions to this effect, which are also useful
to detect missing initialization.
.Fn gcq_insert_head
and
.Fn gcq_insert_tail
are the same operations applied to a head.
.Pp
.Fn GCQ_GOT_FIRST
and
.Fn GCQ_GOT_LAST
set
.Va var
to a pointer to the first or last
.Vt struct gcq
in the list
or
.Dv NULL
if the list is empty and return
.Dv false
if empty and
.Dv 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
.Dv NULL
values will be optimized out if not otherwise used.
.Li DEQUEUED
variants also remove the member from the list.
.Li COND
variants take an additional condition that is evaluated when the macro would
otherwise return
.Dv true .
If the condition is false
.Va var
or
.Va tvar
is set to
.Dv NULL
and no dequeue is performed.
.Pp
.Fn 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 reaching the starting point
.Va var
will be set to
.Dv NULL
and the macro will return
.Dv false .
The next and prev macros also assert that
.Va current
is on the list unless it is equal to
.Va 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
.Fn gcq_head
can be used to treat any item as a head.
.Pp
Foreach variants contain an embedded
.Li for
statement for iterating over a list.
Those containing
.Li REV
use the
.Va q_prev
pointer for traversal, others use
.Va q_next .
The plain
.Fn GCQ_FOREACH
uses a single variable.
.Li NVAR
variants save the next pointer at the top of the loop so that the current
element can be removed without adjusting
.Va var .
This is useful when
.Va var
is passed to a function that might remove it but will not otherwise modify
the list.
When the head is reached both
.Va var
and
.Va nvar
elements are left pointing to the list head.
.Li FOREACH
asserts that
.Va var ,
and
.Li NVAR
asserts that
.Va 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.
.Li RO
variants also set
.Va nvar
but assert that the two variables are linked at the end of each iteration.
This is useful when calling a function that is not supposed to remove the
element passed.
.Li DEQUEUED
variants are like
.Li NVAR
but remove each element before the code block is executed.
.Li 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
.Vt struct gcq
used in this list.
.Va tvar
is set to
.Dv NULL
when the head is reached.
.Pp
.Fn GCQ_FIND
is a foreach loop that does nothing except break when the supplied condition
is true.
.Li REV
and
.Li TYPED
variants are available.
.\" .Sh EXAMPLES
.Sh SEE ALSO
.Xr gcc 1 ,
.Xr _DIAGASSERT 3 ,
.Xr assert 3 ,
.Xr queue 3 ,
.Xr KASSERT 9
.Sh HISTORY
GCQ appeared in
.Nx 5.0 .