1 files changed, 532 insertions, 0 deletions
diff --git a/static/netbsd/man3/gcq.3 b/static/netbsd/man3/gcq.3
new file mode 100644
index 00000000..cdc0750b
--- /dev/null
+++ b/static/netbsd/man3/gcq.3
@@ -0,0 +1,532 @@
+.\" $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 .