\" $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 .

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.