Index: head/share/man/man3/Makefile =================================================================== --- head/share/man/man3/Makefile (revision 352336) +++ head/share/man/man3/Makefile (revision 352337) @@ -1,444 +1,481 @@ # @(#)Makefile 8.2 (Berkeley) 12/13/93 # $FreeBSD$ .include -MAN= assert.3 \ +MAN= arb.3 \ + assert.3 \ ATOMIC_VAR_INIT.3 \ bitstring.3 \ CMSG_DATA.3 \ end.3 \ fpgetround.3 \ intro.3 \ makedev.3 \ offsetof.3 \ ${PTHREAD_MAN} \ Q_FRAWMASK.3 \ Q_IFRAWMASK.3 \ Q_INI.3 \ Q_IRAWMASK.3 \ Q_QABS.3 \ Q_QADDI.3 \ Q_QADDQ.3 \ Q_SIGNED.3 \ Q_SIGNSHFT.3 \ qmath.3 \ queue.3 \ sigevent.3 \ siginfo.3 \ stdarg.3 \ sysexits.3 \ tgmath.3 \ timeradd.3 \ tree.3 +MLINKS+= arb.3 ARB8_ENTRY.3 \ + arb.3 ARB16_ENTRY.3 \ + arb.3 ARB32_ENTRY.3 \ + arb.3 ARB8_HEAD.3 \ + arb.3 ARB16_HEAD.3 \ + arb.3 ARB32_HEAD.3 \ + arb.3 ARB_ALLOCSIZE.3 \ + arb.3 ARB_INITIALIZER.3 \ + arb.3 ARB_ROOT.3 \ + arb.3 ARB_EMPTY.3 \ + arb.3 ARB_FULL.3 \ + arb.3 ARB_CURNODES.3 \ + arb.3 ARB_MAXNODES.3 \ + arb.3 ARB_NEXT.3 \ + arb.3 ARB_PREV.3 \ + arb.3 ARB_MIN.3 \ + arb.3 ARB_MAX.3 \ + arb.3 ARB_FIND.3 \ + arb.3 ARB_NFIND.3 \ + arb.3 ARB_LEFT.3 \ + arb.3 ARB_LEFTIDX.3 \ + arb.3 ARB_RIGHT.3 \ + arb.3 ARB_RIGHTIDX.3 \ + arb.3 ARB_PARENT.3 \ + arb.3 ARB_PARENTIDX.3 \ + arb.3 ARB_GETFREE.3 \ + arb.3 ARB_FREEIDX.3 \ + arb.3 ARB_FOREACH.3 \ + arb.3 ARB_FOREACH_FROM.3 \ + arb.3 ARB_FOREACH_SAFE.3 \ + arb.3 ARB_FOREACH_REVERSE.3 \ + arb.3 ARB_FOREACH_REVERSE_FROM.3 \ + arb.3 ARB_FOREACH_REVERSE_SAFE.3 \ + arb.3 ARB_INIT.3 \ + arb.3 ARB_INSERT.3 \ + arb.3 ARB_REMOVE.3 MLINKS= ATOMIC_VAR_INIT.3 atomic_compare_exchange_strong.3 \ ATOMIC_VAR_INIT.3 atomic_compare_exchange_strong_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_compare_exchange_weak.3 \ ATOMIC_VAR_INIT.3 atomic_compare_exchange_weak_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_exchange.3 \ ATOMIC_VAR_INIT.3 atomic_exchange_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_add.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_add_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_and.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_and_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_or.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_or_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_sub.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_sub_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_xor.3 \ ATOMIC_VAR_INIT.3 atomic_fetch_xor_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_init.3 \ ATOMIC_VAR_INIT.3 atomic_is_lock_free.3 \ ATOMIC_VAR_INIT.3 atomic_load.3 \ ATOMIC_VAR_INIT.3 atomic_load_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_store.3 \ ATOMIC_VAR_INIT.3 atomic_store_explicit.3 MLINKS+= bitstring.3 bit_alloc.3 \ bitstring.3 bit_clear.3 \ bitstring.3 bit_decl.3 \ bitstring.3 bit_ffc.3 \ bitstring.3 bit_ffc_at.3 \ bitstring.3 bit_ffs.3 \ bitstring.3 bit_ffs_at.3 \ bitstring.3 bit_nclear.3 \ bitstring.3 bit_nset.3 \ bitstring.3 bit_set.3 \ bitstring.3 bitstr_size.3 \ bitstring.3 bit_test.3 MLINKS+= CMSG_DATA.3 CMSG_FIRSTHDR.3 \ CMSG_DATA.3 CMSG_LEN.3 \ CMSG_DATA.3 CMSG_NEXTHDR.3 \ CMSG_DATA.3 CMSG_SPACE.3 MLINKS+= end.3 edata.3 \ end.3 etext.3 MLINKS+= fpgetround.3 fpgetmask.3 \ fpgetround.3 fpgetprec.3 \ fpgetround.3 fpgetsticky.3 \ fpgetround.3 fpresetsticky.3 \ fpgetround.3 fpsetmask.3 \ fpgetround.3 fpsetprec.3 \ fpgetround.3 fpsetround.3 MLINKS+= makedev.3 major.3 \ makedev.3 minor.3 MLINKS+= ${PTHREAD_MLINKS} MLINKS+= Q_FRAWMASK.3 Q_GFRAW.3 \ Q_FRAWMASK.3 Q_GFABSVAL.3 \ Q_FRAWMASK.3 Q_GFVAL.3 \ Q_FRAWMASK.3 Q_SFVAL.3 MLINKS+= Q_IFRAWMASK.3 Q_IFVALIMASK.3 \ Q_IFRAWMASK.3 Q_IFVALFMASK.3 \ Q_IFRAWMASK.3 Q_GIFRAW.3 \ Q_IFRAWMASK.3 Q_GIFABSVAL.3 \ Q_IFRAWMASK.3 Q_GIFVAL.3 \ Q_IFRAWMASK.3 Q_SIFVAL.3 \ Q_IFRAWMASK.3 Q_SIFVALS.3 MLINKS+= Q_INI.3 Q_NCBITS.3 \ Q_INI.3 Q_BT.3 \ Q_INI.3 Q_TC.3 \ Q_INI.3 Q_NTBITS.3 \ Q_INI.3 Q_NFCBITS.3 \ Q_INI.3 Q_MAXNFBITS.3 \ Q_INI.3 Q_NFBITS.3 \ Q_INI.3 Q_NIBITS.3 \ Q_INI.3 Q_RPSHFT.3 \ Q_INI.3 Q_ABS.3 \ Q_INI.3 Q_MAXSTRLEN.3 \ Q_INI.3 Q_TOSTR.3 \ Q_INI.3 Q_SHL.3 \ Q_INI.3 Q_SHR.3 \ Q_INI.3 Q_DEBUG.3 \ Q_INI.3 Q_DFV2BFV.3 MLINKS+= Q_IRAWMASK.3 Q_GIRAW.3 \ Q_IRAWMASK.3 Q_GIABSVAL.3 \ Q_IRAWMASK.3 Q_GIVAL.3 \ Q_IRAWMASK.3 Q_SIVAL.3 MLINKS+= Q_QABS.3 Q_Q2D.3 \ Q_QABS.3 Q_Q2F.3 MLINKS+= Q_QADDI.3 Q_QDIVI.3 \ Q_QADDI.3 Q_QMULI.3 \ Q_QADDI.3 Q_QSUBI.3 \ Q_QADDI.3 Q_QFRACI.3 \ Q_QADDI.3 Q_QCPYVALI.3 MLINKS+= Q_QADDQ.3 Q_QDIVQ.3 \ Q_QADDQ.3 Q_QMULQ.3 \ Q_QADDQ.3 Q_QSUBQ.3 \ Q_QADDQ.3 Q_NORMPREC.3 \ Q_QADDQ.3 Q_QMAXQ.3 \ Q_QADDQ.3 Q_QMINQ.3 \ Q_QADDQ.3 Q_QCLONEQ.3 \ Q_QADDQ.3 Q_QCPYVALQ.3 MLINKS+= Q_SIGNED.3 Q_LTZ.3 \ Q_SIGNED.3 Q_PRECEQ.3 \ Q_SIGNED.3 Q_QLTQ.3 \ Q_SIGNED.3 Q_QLEQ.3 \ Q_SIGNED.3 Q_QGTQ.3 \ Q_SIGNED.3 Q_QGEQ.3 \ Q_SIGNED.3 Q_QEQ.3 \ Q_SIGNED.3 Q_QNEQ.3 \ Q_SIGNED.3 Q_OFLOW.3 \ Q_SIGNED.3 Q_RELPREC.3 MLINKS+= Q_SIGNSHFT.3 Q_SSIGN.3 \ Q_SIGNSHFT.3 Q_CRAWMASK.3 \ Q_SIGNSHFT.3 Q_SRAWMASK.3 \ Q_SIGNSHFT.3 Q_GCRAW.3 \ Q_SIGNSHFT.3 Q_GCVAL.3 \ Q_SIGNSHFT.3 Q_SCVAL.3 MLINKS+= queue.3 LIST_CLASS_ENTRY.3 \ queue.3 LIST_CLASS_HEAD.3 \ queue.3 LIST_EMPTY.3 \ queue.3 LIST_ENTRY.3 \ queue.3 LIST_FIRST.3 \ queue.3 LIST_FOREACH.3 \ queue.3 LIST_FOREACH_FROM.3 \ queue.3 LIST_FOREACH_FROM_SAFE.3 \ queue.3 LIST_FOREACH_SAFE.3 \ queue.3 LIST_HEAD.3 \ queue.3 LIST_HEAD_INITIALIZER.3 \ queue.3 LIST_INIT.3 \ queue.3 LIST_INSERT_AFTER.3 \ queue.3 LIST_INSERT_BEFORE.3 \ queue.3 LIST_INSERT_HEAD.3 \ queue.3 LIST_NEXT.3 \ queue.3 LIST_PREV.3 \ queue.3 LIST_REMOVE.3 \ queue.3 LIST_SWAP.3 \ queue.3 SLIST_CLASS_ENTRY.3 \ queue.3 SLIST_CLASS_HEAD.3 \ queue.3 SLIST_EMPTY.3 \ queue.3 SLIST_ENTRY.3 \ queue.3 SLIST_FIRST.3 \ queue.3 SLIST_FOREACH.3 \ queue.3 SLIST_FOREACH_FROM.3 \ queue.3 SLIST_FOREACH_FROM_SAFE.3 \ queue.3 SLIST_FOREACH_SAFE.3 \ queue.3 SLIST_HEAD.3 \ queue.3 SLIST_HEAD_INITIALIZER.3 \ queue.3 SLIST_INIT.3 \ queue.3 SLIST_INSERT_AFTER.3 \ queue.3 SLIST_INSERT_HEAD.3 \ queue.3 SLIST_NEXT.3 \ queue.3 SLIST_REMOVE.3 \ queue.3 SLIST_REMOVE_AFTER.3 \ queue.3 SLIST_REMOVE_HEAD.3 \ queue.3 SLIST_REMOVE_PREVPTR.3 \ queue.3 SLIST_SWAP.3 \ queue.3 STAILQ_CLASS_ENTRY.3 \ queue.3 STAILQ_CLASS_HEAD.3 \ queue.3 STAILQ_CONCAT.3 \ queue.3 STAILQ_EMPTY.3 \ queue.3 STAILQ_ENTRY.3 \ queue.3 STAILQ_FIRST.3 \ queue.3 STAILQ_FOREACH.3 \ queue.3 STAILQ_FOREACH_FROM.3 \ queue.3 STAILQ_FOREACH_FROM_SAFE.3 \ queue.3 STAILQ_FOREACH_SAFE.3 \ queue.3 STAILQ_HEAD.3 \ queue.3 STAILQ_HEAD_INITIALIZER.3 \ queue.3 STAILQ_INIT.3 \ queue.3 STAILQ_INSERT_AFTER.3 \ queue.3 STAILQ_INSERT_HEAD.3 \ queue.3 STAILQ_INSERT_TAIL.3 \ queue.3 STAILQ_LAST.3 \ queue.3 STAILQ_NEXT.3 \ queue.3 STAILQ_REMOVE.3 \ queue.3 STAILQ_REMOVE_AFTER.3 \ queue.3 STAILQ_REMOVE_HEAD.3 \ queue.3 STAILQ_SWAP.3 \ queue.3 TAILQ_CLASS_ENTRY.3 \ queue.3 TAILQ_CLASS_HEAD.3 \ queue.3 TAILQ_CONCAT.3 \ queue.3 TAILQ_EMPTY.3 \ queue.3 TAILQ_ENTRY.3 \ queue.3 TAILQ_FIRST.3 \ queue.3 TAILQ_FOREACH.3 \ queue.3 TAILQ_FOREACH_FROM.3 \ queue.3 TAILQ_FOREACH_FROM_SAFE.3 \ queue.3 TAILQ_FOREACH_REVERSE.3 \ queue.3 TAILQ_FOREACH_REVERSE_FROM.3 \ queue.3 TAILQ_FOREACH_REVERSE_FROM_SAFE.3 \ queue.3 TAILQ_FOREACH_REVERSE_SAFE.3 \ queue.3 TAILQ_FOREACH_SAFE.3 \ queue.3 TAILQ_HEAD.3 \ queue.3 TAILQ_HEAD_INITIALIZER.3 \ queue.3 TAILQ_INIT.3 \ queue.3 TAILQ_INSERT_AFTER.3 \ queue.3 TAILQ_INSERT_BEFORE.3 \ queue.3 TAILQ_INSERT_HEAD.3 \ queue.3 TAILQ_INSERT_TAIL.3 \ queue.3 TAILQ_LAST.3 \ queue.3 TAILQ_NEXT.3 \ queue.3 TAILQ_PREV.3 \ queue.3 TAILQ_REMOVE.3 \ queue.3 TAILQ_SWAP.3 MLINKS+= stdarg.3 va_arg.3 \ stdarg.3 va_copy.3 \ stdarg.3 va_end.3 \ stdarg.3 varargs.3 \ stdarg.3 va_start.3 MLINKS+= timeradd.3 timerclear.3 \ timeradd.3 timercmp.3 \ timeradd.3 timerisset.3 \ timeradd.3 timersub.3 \ timeradd.3 timespecadd.3 \ timeradd.3 timespecsub.3 \ timeradd.3 timespecclear.3 \ timeradd.3 timespecisset.3 \ timeradd.3 timespeccmp.3 MLINKS+= tree.3 RB_EMPTY.3 \ tree.3 RB_ENTRY.3 \ tree.3 RB_FIND.3 \ tree.3 RB_FOREACH.3 \ tree.3 RB_FOREACH_FROM.3 \ tree.3 RB_FOREACH_REVERSE.3 \ tree.3 RB_FOREACH_REVERSE_FROM.3 \ tree.3 RB_FOREACH_REVERSE_SAFE.3 \ tree.3 RB_FOREACH_SAFE.3 \ tree.3 RB_GENERATE.3 \ tree.3 RB_GENERATE_FIND.3 \ tree.3 RB_GENERATE_INSERT.3 \ tree.3 RB_GENERATE_INSERT_COLOR.3 \ tree.3 RB_GENERATE_MINMAX.3 \ tree.3 RB_GENERATE_NEXT.3 \ tree.3 RB_GENERATE_NFIND.3 \ tree.3 RB_GENERATE_PREV.3 \ tree.3 RB_GENERATE_REMOVE.3 \ tree.3 RB_GENERATE_REMOVE_COLOR.3 \ tree.3 RB_GENERATE_STATIC.3 \ tree.3 RB_HEAD.3 \ tree.3 RB_INIT.3 \ tree.3 RB_INITIALIZER.3 \ tree.3 RB_INSERT.3 \ tree.3 RB_LEFT.3 \ tree.3 RB_MAX.3 \ tree.3 RB_MIN.3 \ tree.3 RB_NEXT.3 \ tree.3 RB_NFIND.3 \ tree.3 RB_PARENT.3 \ tree.3 RB_PREV.3 \ tree.3 RB_PROTOTYPE.3 \ tree.3 RB_PROTOTYPE_FIND.3 \ tree.3 RB_PROTOTYPE_INSERT.3 \ tree.3 RB_PROTOTYPE_INSERT_COLOR.3 \ tree.3 RB_PROTOTYPE_MINMAX.3 \ tree.3 RB_PROTOTYPE_NEXT.3 \ tree.3 RB_PROTOTYPE_NFIND.3 \ tree.3 RB_PROTOTYPE_PREV.3 \ tree.3 RB_PROTOTYPE_REMOVE.3 \ tree.3 RB_PROTOTYPE_REMOVE_COLOR.3 \ tree.3 RB_PROTOTYPE_STATIC.3 \ tree.3 RB_REMOVE.3 \ tree.3 RB_RIGHT.3 \ tree.3 RB_ROOT.3 \ tree.3 SPLAY_EMPTY.3 \ tree.3 SPLAY_ENTRY.3 \ tree.3 SPLAY_FIND.3 \ tree.3 SPLAY_FOREACH.3 \ tree.3 SPLAY_GENERATE.3 \ tree.3 SPLAY_HEAD.3 \ tree.3 SPLAY_INIT.3 \ tree.3 SPLAY_INITIALIZER.3 \ tree.3 SPLAY_INSERT.3 \ tree.3 SPLAY_LEFT.3 \ tree.3 SPLAY_MAX.3 \ tree.3 SPLAY_MIN.3 \ tree.3 SPLAY_NEXT.3 \ tree.3 SPLAY_PROTOTYPE.3 \ tree.3 SPLAY_REMOVE.3 \ tree.3 SPLAY_RIGHT.3 \ tree.3 SPLAY_ROOT.3 .if ${MK_LIBTHR} != "no" PTHREAD_MAN= pthread.3 \ pthread_affinity_np.3 \ pthread_atfork.3 \ pthread_attr.3 \ pthread_attr_affinity_np.3 \ pthread_attr_get_np.3 \ pthread_attr_setcreatesuspend_np.3 \ pthread_barrierattr.3 \ pthread_barrier_destroy.3 \ pthread_cancel.3 \ pthread_cleanup_pop.3 \ pthread_cleanup_push.3 \ pthread_condattr.3 \ pthread_cond_broadcast.3 \ pthread_cond_destroy.3 \ pthread_cond_init.3 \ pthread_cond_signal.3 \ pthread_cond_timedwait.3 \ pthread_cond_wait.3 \ pthread_create.3 \ pthread_detach.3 \ pthread_equal.3 \ pthread_exit.3 \ pthread_getconcurrency.3 \ pthread_getcpuclockid.3 \ pthread_getspecific.3 \ pthread_getthreadid_np.3 \ pthread_join.3 \ pthread_key_create.3 \ pthread_key_delete.3 \ pthread_kill.3 \ pthread_main_np.3 \ pthread_multi_np.3 \ pthread_mutexattr.3 \ pthread_mutexattr_getkind_np.3 \ pthread_mutex_consistent.3 \ pthread_mutex_destroy.3 \ pthread_mutex_init.3 \ pthread_mutex_lock.3 \ pthread_mutex_timedlock.3 \ pthread_mutex_trylock.3 \ pthread_mutex_unlock.3 \ pthread_once.3 \ pthread_resume_all_np.3 \ pthread_resume_np.3 \ pthread_rwlockattr_destroy.3 \ pthread_rwlockattr_getpshared.3 \ pthread_rwlockattr_init.3 \ pthread_rwlockattr_setpshared.3 \ pthread_rwlock_destroy.3 \ pthread_rwlock_init.3 \ pthread_rwlock_rdlock.3 \ pthread_rwlock_timedrdlock.3 \ pthread_rwlock_timedwrlock.3 \ pthread_rwlock_unlock.3 \ pthread_rwlock_wrlock.3 \ pthread_schedparam.3 \ pthread_self.3 \ pthread_set_name_np.3 \ pthread_setspecific.3 \ pthread_sigmask.3 \ pthread_spin_init.3 \ pthread_spin_lock.3 \ pthread_suspend_all_np.3 \ pthread_suspend_np.3 \ pthread_switch_add_np.3 \ pthread_testcancel.3 \ pthread_yield.3 PTHREAD_MLINKS= pthread_affinity_np.3 pthread_getaffinity_np.3 \ pthread_affinity_np.3 pthread_setaffinity_np.3 PTHREAD_MLINKS+=pthread_attr.3 pthread_attr_destroy.3 \ pthread_attr.3 pthread_attr_getdetachstate.3 \ pthread_attr.3 pthread_attr_getguardsize.3 \ pthread_attr.3 pthread_attr_getinheritsched.3 \ pthread_attr.3 pthread_attr_getschedparam.3 \ pthread_attr.3 pthread_attr_getschedpolicy.3 \ pthread_attr.3 pthread_attr_getscope.3 \ pthread_attr.3 pthread_attr_getstack.3 \ pthread_attr.3 pthread_attr_getstackaddr.3 \ pthread_attr.3 pthread_attr_getstacksize.3 \ pthread_attr.3 pthread_attr_init.3 \ pthread_attr.3 pthread_attr_setdetachstate.3 \ pthread_attr.3 pthread_attr_setguardsize.3 \ pthread_attr.3 pthread_attr_setinheritsched.3 \ pthread_attr.3 pthread_attr_setschedparam.3 \ pthread_attr.3 pthread_attr_setschedpolicy.3 \ pthread_attr.3 pthread_attr_setscope.3 \ pthread_attr.3 pthread_attr_setstack.3 \ pthread_attr.3 pthread_attr_setstackaddr.3 \ pthread_attr.3 pthread_attr_setstacksize.3 PTHREAD_MLINKS+=pthread_attr_affinity_np.3 pthread_attr_getaffinity_np.3 \ pthread_attr_affinity_np.3 pthread_attr_setaffinity_np.3 PTHREAD_MLINKS+=pthread_barrierattr.3 pthread_barrierattr_destroy.3 \ pthread_barrierattr.3 pthread_barrierattr_getpshared.3 \ pthread_barrierattr.3 pthread_barrierattr_init.3 \ pthread_barrierattr.3 pthread_barrierattr_setpshared.3 PTHREAD_MLINKS+=pthread_barrier_destroy.3 pthread_barrier_init.3 \ pthread_barrier_destroy.3 pthread_barrier_wait.3 PTHREAD_MLINKS+=pthread_condattr.3 pthread_condattr_destroy.3 \ pthread_condattr.3 pthread_condattr_init.3 \ pthread_condattr.3 pthread_condattr_getclock.3 \ pthread_condattr.3 pthread_condattr_setclock.3 \ pthread_condattr.3 pthread_condattr_getpshared.3 \ pthread_condattr.3 pthread_condattr_setpshared.3 PTHREAD_MLINKS+=pthread_getconcurrency.3 pthread_setconcurrency.3 PTHREAD_MLINKS+=pthread_multi_np.3 pthread_single_np.3 PTHREAD_MLINKS+=pthread_mutexattr.3 pthread_mutexattr_destroy.3 \ pthread_mutexattr.3 pthread_mutexattr_getprioceiling.3 \ pthread_mutexattr.3 pthread_mutexattr_getprotocol.3 \ pthread_mutexattr.3 pthread_mutexattr_getrobust.3 \ pthread_mutexattr.3 pthread_mutexattr_gettype.3 \ pthread_mutexattr.3 pthread_mutexattr_init.3 \ pthread_mutexattr.3 pthread_mutexattr_setprioceiling.3 \ pthread_mutexattr.3 pthread_mutexattr_setprotocol.3 \ pthread_mutexattr.3 pthread_mutexattr_setrobust.3 \ pthread_mutexattr.3 pthread_mutexattr_settype.3 PTHREAD_MLINKS+=pthread_mutexattr_getkind_np.3 pthread_mutexattr_setkind_np.3 PTHREAD_MLINKS+=pthread_rwlock_rdlock.3 pthread_rwlock_tryrdlock.3 PTHREAD_MLINKS+=pthread_rwlock_wrlock.3 pthread_rwlock_trywrlock.3 PTHREAD_MLINKS+=pthread_schedparam.3 pthread_getschedparam.3 \ pthread_schedparam.3 pthread_setschedparam.3 PTHREAD_MLINKS+=pthread_set_name_np.3 pthread_get_name_np.3 PTHREAD_MLINKS+=pthread_spin_init.3 pthread_spin_destroy.3 \ pthread_spin_lock.3 pthread_spin_trylock.3 \ pthread_spin_lock.3 pthread_spin_unlock.3 PTHREAD_MLINKS+=pthread_switch_add_np.3 pthread_switch_delete_np.3 PTHREAD_MLINKS+=pthread_testcancel.3 pthread_setcancelstate.3 \ pthread_testcancel.3 pthread_setcanceltype.3 PTHREAD_MLINKS+=pthread_join.3 pthread_timedjoin_np.3 .endif .include Index: head/share/man/man3/arb.3 =================================================================== --- head/share/man/man3/arb.3 (nonexistent) +++ head/share/man/man3/arb.3 (revision 352337) @@ -0,0 +1,483 @@ +.\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $ +.\" +.\" Copyright 2002 Niels Provos +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by Niels Provos. +.\" 4. The name of the author may not be used to endorse or promote products +.\" derived from this software without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +.\" +.\" $FreeBSD$ +.\" +.Dd May 8, 2019 +.Dt ARB 3 +.Os +.Sh NAME +.Nm ARB_PROTOTYPE , +.Nm ARB_PROTOTYPE_STATIC , +.Nm ARB_PROTOTYPE_INSERT , +.Nm ARB_PROTOTYPE_INSERT_COLOR , +.Nm ARB_PROTOTYPE_REMOVE , +.Nm ARB_PROTOTYPE_REMOVE_COLOR , +.Nm ARB_PROTOTYPE_FIND , +.Nm ARB_PROTOTYPE_NFIND , +.Nm ARB_PROTOTYPE_NEXT , +.Nm ARB_PROTOTYPE_PREV , +.Nm ARB_PROTOTYPE_MINMAX , +.Nm ARB_GENERATE , +.Nm ARB_GENERATE_STATIC , +.Nm ARB_GENERATE_INSERT , +.Nm ARB_GENERATE_INSERT_COLOR , +.Nm ARB_GENERATE_REMOVE , +.Nm ARB_GENERATE_REMOVE_COLOR , +.Nm ARB_GENERATE_FIND , +.Nm ARB_GENERATE_NFIND , +.Nm ARB_GENERATE_NEXT , +.Nm ARB_GENERATE_PREV , +.Nm ARB_GENERATE_MINMAX , +.Nm ARB8_ENTRY , +.Nm ARB16_ENTRY , +.Nm ARB32_ENTRY , +.Nm ARB8_HEAD , +.Nm ARB16_HEAD , +.Nm ARB32_HEAD , +.Nm ARB_ALLOCSIZE , +.Nm ARB_INITIALIZER , +.Nm ARB_ROOT , +.Nm ARB_EMPTY , +.Nm ARB_FULL , +.Nm ARB_CURNODES , +.Nm ARB_MAXNODES , +.Nm ARB_NEXT , +.Nm ARB_PREV , +.Nm ARB_MIN , +.Nm ARB_MAX , +.Nm ARB_FIND , +.Nm ARB_NFIND , +.Nm ARB_LEFT , +.Nm ARB_LEFTIDX , +.Nm ARB_RIGHT , +.Nm ARB_RIGHTIDX , +.Nm ARB_PARENT , +.Nm ARB_PARENTIDX , +.Nm ARB_GETFREE , +.Nm ARB_FREEIDX , +.Nm ARB_FOREACH , +.Nm ARB_FOREACH_FROM , +.Nm ARB_FOREACH_SAFE , +.Nm ARB_FOREACH_REVERSE , +.Nm ARB_FOREACH_REVERSE_FROM , +.Nm ARB_FOREACH_REVERSE_SAFE , +.Nm ARB_INIT , +.Nm ARB_INSERT , +.Nm ARB_REMOVE +.Nd "array-based red-black trees" +.Sh SYNOPSIS +.In sys/arb.h +.Fn ARB_PROTOTYPE NAME TYPE FIELD CMP +.Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP +.Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR +.Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR +.Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR +.Fn ARB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR +.Fn ARB_PROTOTYPE_FIND NAME TYPE ATTR +.Fn ARB_PROTOTYPE_NFIND NAME TYPE ATTR +.Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR +.Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR +.Fn ARB_PROTOTYPE_MINMAX NAME TYPE ATTR +.Fn ARB_GENERATE NAME TYPE FIELD CMP +.Fn ARB_GENERATE_STATIC NAME TYPE FIELD CMP +.Fn ARB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR +.Fn ARB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR +.Fn ARB_GENERATE_REMOVE NAME TYPE FIELD ATTR +.Fn ARB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR +.Fn ARB_GENERATE_FIND NAME TYPE FIELD CMP ATTR +.Fn ARB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR +.Fn ARB_GENERATE_NEXT NAME TYPE FIELD ATTR +.Fn ARB_GENERATE_PREV NAME TYPE FIELD ATTR +.Fn ARB_GENERATE_MINMAX NAME TYPE FIELD ATTR +.Fn ARB<8|16|32>_ENTRY +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Ft "size_t" +.Fn ARB_ALLOCSIZE "ARB_HEAD *head" "int<8|16|32>_t maxnodes" "struct TYPE *elm" +.Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes" +.Ft "struct TYPE *" +.Fn ARB_ROOT "ARB_HEAD *head" +.Ft "bool" +.Fn ARB_EMPTY "ARB_HEAD *head" +.Ft "bool" +.Fn ARB_FULL "ARB_HEAD *head" +.Ft "int<8|16|32>_t" +.Fn ARB_CURNODES "ARB_HEAD *head" +.Ft "int<8|16|32>_t" +.Fn ARB_MAXNODES "ARB_HEAD *head" +.Ft "struct TYPE *" +.Fn ARB_NEXT NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_PREV NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_MIN NAME "ARB_HEAD *head" +.Ft "struct TYPE *" +.Fn ARB_MAX NAME "ARB_HEAD *head" +.Ft "struct TYPE *" +.Fn ARB_FIND NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_NFIND NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_LEFT "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "int<8|16|32>_t" +.Fn ARB_LEFTIDX "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn ARB_RIGHT "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "int<8|16|32>_t" +.Fn ARB_RIGHTIDX "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn ARB_PARENT "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "int<8|16|32>_t" +.Fn ARB_PARENTIDX "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn ARB_GETFREE "ARB_HEAD *head" "FIELD" +.Ft "int<8|16|32>_t" +.Fn ARB_FREEIDX "ARB_HEAD *head" +.Fn ARB_FOREACH VARNAME NAME "ARB_HEAD *head" +.Fn ARB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME" +.Fn ARB_FOREACH_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME" +.Fn ARB_FOREACH_REVERSE VARNAME NAME "ARB_HEAD *head" +.Fn ARB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME" +.Fn ARB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME" +.Ft void +.Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes" +.Ft "struct TYPE *" +.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm" +.Sh DESCRIPTION +These macros define data structures for and array-based red-black trees. +They use a single, continuous chunk of memory, and are useful +e.g., when the tree needs to be transferred between userspace and kernel. +.Pp +In the macro definitions, +.Fa TYPE +is the name tag of a user defined structure that must contain a field of type +.Vt ARB_ENTRY , +named +.Fa ENTRYNAME . +The argument +.Fa HEADNAME +is the name tag of a user defined structure that must be declared +using the +.Fn ARB_HEAD +macro. +The argument +.Fa NAME +has to be a unique name prefix for every tree that is defined. +.Pp +The function prototypes are declared with +.Fn ARB_PROTOTYPE , +or +.Fn ARB_PROTOTYPE_STATIC . +The function bodies are generated with +.Fn ARB_GENERATE , +or +.Fn ARB_GENERATE_STATIC . +See the examples below for further explanation of how these macros are used. +.Pp +A red-black tree is a binary search tree with the node color as an +extra attribute. +It fulfills a set of conditions: +.Bl -enum -offset indent +.It +Every search path from the root to a leaf consists of the same number of +black nodes. +.It +Each red node (except for the root) has a black parent. +.It +Each leaf node is black. +.El +.Pp +Every operation on a red-black tree is bounded as +.Fn O "lg n" . +The maximum height of a red-black tree is +.Fn 2lg "n + 1" . +.Pp +.Fn ARB_* +trees require entries to be allocated as an array, and uses array +indices to link entries together. +The maximum number of +.Fn ARB_* +tree entries is therefore constrained by the minimum of array size and choice of +signed integer data type used to store array indices. +Use +.Fn ARB_ALLOCSIZE +to compute the size of memory chunk to allocate. +.Pp +A red-black tree is headed by a structure defined by the +.Fn ARB_HEAD +macro. +A +structure is declared with either of the following: +.Bd -ragged -offset indent +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Va head ; +.Ed +.Pp +where +.Fa HEADNAME +is the name of the structure to be defined, and struct +.Fa TYPE +is the type of the elements to be inserted into the tree. +.Pp +The +.Fn ARB_HEAD +variant includes a suffix denoting the signed integer data type size +.Pq in bits +used to store array indices. +For example, +.Fn ARB_HEAD8 +creates a red-black tree head strucutre with 8-bit signed array indices capable +of indexing up to 128 entries. +.Pp +The +.Fn ARB_ENTRY +macro declares a structure that allows elements to be connected in the tree. +Similarly to the +.Fn ARB<8|16|32>_HEAD +macro, the +.Fn ARB_ENTRY +variant includes a suffix denoting the signed integer data type size +.Pq in bits +used to store array indices. +Entries should use the same number of bits as the tree head structure they will +be linked into. +.Pp +In order to use the functions that manipulate the tree structure, +their prototypes need to be declared with the +.Fn ARB_PROTOTYPE +or +.Fn ARB_PROTOTYPE_STATIC +macro, +where +.Fa NAME +is a unique identifier for this particular tree. +The +.Fa TYPE +argument is the type of the structure that is being managed +by the tree. +The +.Fa FIELD +argument is the name of the element defined by +.Fn ARB_ENTRY . +Individual prototypes can be declared with +.Fn ARB_PROTOTYPE_INSERT , +.Fn ARB_PROTOTYPE_INSERT_COLOR , +.Fn ARB_PROTOTYPE_REMOVE , +.Fn ARB_PROTOTYPE_REMOVE_COLOR , +.Fn ARB_PROTOTYPE_FIND , +.Fn ARB_PROTOTYPE_NFIND , +.Fn ARB_PROTOTYPE_NEXT , +.Fn ARB_PROTOTYPE_PREV , +and +.Fn ARB_PROTOTYPE_MINMAX +in case not all functions are required. +The individual prototype macros expect +.Fa NAME , +.Fa TYPE , +and +.Fa ATTR +arguments. +The +.Fa ATTR +argument must be empty for global functions or +.Fa static +for static functions. +.Pp +The function bodies are generated with the +.Fn ARB_GENERATE +or +.Fn ARB_GENERATE_STATIC +macro. +These macros take the same arguments as the +.Fn ARB_PROTOTYPE +and +.Fn ARB_PROTOTYPE_STATIC +macros, but should be used only once. +As an alternative individual function bodies are generated with the +.Fn ARB_GENERATE_INSERT , +.Fn ARB_GENERATE_INSERT_COLOR , +.Fn ARB_GENERATE_REMOVE , +.Fn ARB_GENERATE_REMOVE_COLOR , +.Fn ARB_GENERATE_FIND , +.Fn ARB_GENERATE_NFIND , +.Fn ARB_GENERATE_NEXT , +.Fn ARB_GENERATE_PREV , +and +.Fn ARB_GENERATE_MINMAX +macros. +.Pp +Finally, +the +.Fa CMP +argument is the name of a function used to compare tree nodes +with each other. +The function takes two arguments of type +.Vt "struct TYPE *" . +If the first argument is smaller than the second, the function returns a +value smaller than zero. +If they are equal, the function returns zero. +Otherwise, it should return a value greater than zero. +The compare +function defines the order of the tree elements. +.Pp +The +.Fn ARB_INIT +macro initializes the tree referenced by +.Fa head , +with the array length of +.Fa maxnodes . +.Pp +The red-black tree can also be initialized statically by using the +.Fn ARB_INITIALIZER +macro: +.Bd -ragged -offset indent +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Va head += +.Fn ARB_INITIALIZER &head maxnodes ; +.Ed +.Pp +The +.Fn ARB_INSERT +macro inserts the new element +.Fa elm +into the tree. +.Pp +The +.Fn ARB_REMOVE +macro removes the element +.Fa elm +from the tree pointed by +.Fa head . +.Pp +The +.Fn ARB_FIND +and +.Fn ARB_NFIND +macros can be used to find a particular element in the tree. +.Bd -literal -offset indent +struct TYPE find, *res; +find.key = 30; +res = RB_FIND(NAME, head, &find); +.Ed +.Pp +The +.Fn ARB_ROOT , +.Fn ARB_MIN , +.Fn ARB_MAX , +.Fn ARB_NEXT , +and +.Fn ARB_PREV +macros can be used to traverse the tree: +.Pp +.Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))" +.Pp +Or, for simplicity, one can use the +.Fn ARB_FOREACH +or +.Fn ARB_FOREACH_REVERSE +macro: +.Bd -ragged -offset indent +.Fn RB_FOREACH np NAME head +.Ed +.Pp +The macros +.Fn ARB_FOREACH_SAFE +and +.Fn ARB_FOREACH_REVERSE_SAFE +traverse the tree referenced by head +in a forward or reverse direction respectively, +assigning each element in turn to np. +However, unlike their unsafe counterparts, +they permit both the removal of np +as well as freeing it from within the loop safely +without interfering with the traversal. +.Pp +Both +.Fn ARB_FOREACH_FROM +and +.Fn ARB_FOREACH_REVERSE_FROM +may be used to continue an interrupted traversal +in a forward or reverse direction respectively. +The head pointer is not required. +The pointer to the node from where to resume the traversal +should be passed as their last argument, +and will be overwritten to provide safe traversal. +.Pp +The +.Fn ARB_EMPTY +macro should be used to check whether a red-black tree is empty. +.Pp +Given that ARB trees have an intrinsic upper bound on the number of entries, +some ARB-specific additional macros are defined. +The +.Fn ARB_FULL +macro returns a boolean indicating whether the current number of tree entries +equals the tree's maximum. +The +.Fn ARB_CURNODES +and +.Fn ARB_MAXNODES +macros return the current and maximum number of entries respectively. +The +.Fn ARB_GETFREE +macro returns a pointer to the next free entry in the array of entries, ready to +be linked into the tree. +The +.Fn ARB_INSERT +returns +.Dv NULL +if the element was inserted in the tree successfully, otherwise they +return a pointer to the element with the colliding key. +.Pp +Accordingly, +.Fn ARB_REMOVE +returns the pointer to the removed element otherwise they return +.Dv NULL +to indicate an error. +.Sh SEE ALSO +.Xr queue 3 , +.Xr tree 3 +.Sh HISTORY +The +.Nm ARB +macros first appeared in +.Fx 13.0 . +.Sh AUTHORS +The +.Nm ARB +macros were implemented by +.An Lawrence Stewart Aq Mt lstewart@FreeBSD.org , +based on +.Xr tree 3 +macros written by +.An Niels Provos . Property changes on: head/share/man/man3/arb.3 ___________________________________________________________________ Added: svn:keywords ## -0,0 +1 ## +FreeBSD=%H \ No newline at end of property Index: head/share/man/man3/queue.3 =================================================================== --- head/share/man/man3/queue.3 (revision 352336) +++ head/share/man/man3/queue.3 (revision 352337) @@ -1,1337 +1,1338 @@ .\" Copyright (c) 1993 .\" The Regents of the University of California. All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" 3. Neither the name of the University nor the names of its contributors .\" may be used to endorse or promote products derived from this software .\" without specific prior written permission. .\" .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" .\" @(#)queue.3 8.2 (Berkeley) 1/24/94 .\" $FreeBSD$ .\" .Dd September 8, 2016 .Dt QUEUE 3 .Os .Sh NAME .Nm SLIST_CLASS_ENTRY , .Nm SLIST_CLASS_HEAD , .Nm SLIST_CONCAT , .Nm SLIST_EMPTY , .Nm SLIST_ENTRY , .Nm SLIST_FIRST , .Nm SLIST_FOREACH , .Nm SLIST_FOREACH_FROM , .Nm SLIST_FOREACH_FROM_SAFE , .Nm SLIST_FOREACH_SAFE , .Nm SLIST_HEAD , .Nm SLIST_HEAD_INITIALIZER , .Nm SLIST_INIT , .Nm SLIST_INSERT_AFTER , .Nm SLIST_INSERT_HEAD , .Nm SLIST_NEXT , .Nm SLIST_REMOVE , .Nm SLIST_REMOVE_AFTER , .Nm SLIST_REMOVE_HEAD , .Nm SLIST_SWAP , .Nm STAILQ_CLASS_ENTRY , .Nm STAILQ_CLASS_HEAD , .Nm STAILQ_CONCAT , .Nm STAILQ_EMPTY , .Nm STAILQ_ENTRY , .Nm STAILQ_FIRST , .Nm STAILQ_FOREACH , .Nm STAILQ_FOREACH_FROM , .Nm STAILQ_FOREACH_FROM_SAFE , .Nm STAILQ_FOREACH_SAFE , .Nm STAILQ_HEAD , .Nm STAILQ_HEAD_INITIALIZER , .Nm STAILQ_INIT , .Nm STAILQ_INSERT_AFTER , .Nm STAILQ_INSERT_HEAD , .Nm STAILQ_INSERT_TAIL , .Nm STAILQ_LAST , .Nm STAILQ_NEXT , .Nm STAILQ_REMOVE , .Nm STAILQ_REMOVE_AFTER , .Nm STAILQ_REMOVE_HEAD , .Nm STAILQ_SWAP , .Nm LIST_CLASS_ENTRY , .Nm LIST_CLASS_HEAD , .Nm LIST_CONCAT , .Nm LIST_EMPTY , .Nm LIST_ENTRY , .Nm LIST_FIRST , .Nm LIST_FOREACH , .Nm LIST_FOREACH_FROM , .Nm LIST_FOREACH_FROM_SAFE , .Nm LIST_FOREACH_SAFE , .Nm LIST_HEAD , .Nm LIST_HEAD_INITIALIZER , .Nm LIST_INIT , .Nm LIST_INSERT_AFTER , .Nm LIST_INSERT_BEFORE , .Nm LIST_INSERT_HEAD , .Nm LIST_NEXT , .Nm LIST_PREV , .Nm LIST_REMOVE , .Nm LIST_SWAP , .Nm TAILQ_CLASS_ENTRY , .Nm TAILQ_CLASS_HEAD , .Nm TAILQ_CONCAT , .Nm TAILQ_EMPTY , .Nm TAILQ_ENTRY , .Nm TAILQ_FIRST , .Nm TAILQ_FOREACH , .Nm TAILQ_FOREACH_FROM , .Nm TAILQ_FOREACH_FROM_SAFE , .Nm TAILQ_FOREACH_REVERSE , .Nm TAILQ_FOREACH_REVERSE_FROM , .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE , .Nm TAILQ_FOREACH_REVERSE_SAFE , .Nm TAILQ_FOREACH_SAFE , .Nm TAILQ_HEAD , .Nm TAILQ_HEAD_INITIALIZER , .Nm TAILQ_INIT , .Nm TAILQ_INSERT_AFTER , .Nm TAILQ_INSERT_BEFORE , .Nm TAILQ_INSERT_HEAD , .Nm TAILQ_INSERT_TAIL , .Nm TAILQ_LAST , .Nm TAILQ_NEXT , .Nm TAILQ_PREV , .Nm TAILQ_REMOVE , .Nm TAILQ_SWAP .Nd implementations of singly-linked lists, singly-linked tail queues, lists and tail queues .Sh SYNOPSIS .In sys/queue.h .\" .Fn SLIST_CLASS_ENTRY "CLASSTYPE" .Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME" .Fn SLIST_EMPTY "SLIST_HEAD *head" .Fn SLIST_ENTRY "TYPE" .Fn SLIST_FIRST "SLIST_HEAD *head" .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" .Fn SLIST_HEAD "HEADNAME" "TYPE" .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" .Fn SLIST_INIT "SLIST_HEAD *head" .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" .\" .Fn STAILQ_CLASS_ENTRY "CLASSTYPE" .Fn STAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" .Fn STAILQ_EMPTY "STAILQ_HEAD *head" .Fn STAILQ_ENTRY "TYPE" .Fn STAILQ_FIRST "STAILQ_HEAD *head" .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" .Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" .Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" .Fn STAILQ_HEAD "HEADNAME" "TYPE" .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" .Fn STAILQ_INIT "STAILQ_HEAD *head" .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "TYPE" .\" .Fn LIST_CLASS_ENTRY "CLASSTYPE" .Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" .Fn LIST_EMPTY "LIST_HEAD *head" .Fn LIST_ENTRY "TYPE" .Fn LIST_FIRST "LIST_HEAD *head" .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" .Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" .Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" .Fn LIST_HEAD "HEADNAME" "TYPE" .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" .Fn LIST_INIT "LIST_HEAD *head" .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME" .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" .\" .Fn TAILQ_CLASS_ENTRY "CLASSTYPE" .Fn TAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME" .Fn TAILQ_EMPTY "TAILQ_HEAD *head" .Fn TAILQ_ENTRY "TYPE" .Fn TAILQ_FIRST "TAILQ_HEAD *head" .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" .Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" .Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" .Fn TAILQ_HEAD "HEADNAME" "TYPE" .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" .Fn TAILQ_INIT "TAILQ_HEAD *head" .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME" .\" .Sh DESCRIPTION These macros define and operate on four types of data structures which can be used in both C and C++ source code: .Bl -enum -compact -offset indent .It Lists .It Singly-linked lists .It Singly-linked tail queues .It Tail queues .El All four structures support the following functionality: .Bl -enum -compact -offset indent .It Insertion of a new entry at the head of the list. .It Insertion of a new entry after any element in the list. .It O(1) removal of an entry from the head of the list. .It Forward traversal through the list. .It Swapping the contents of two lists. .El .Pp Singly-linked lists are the simplest of the four data structures and support only the above functionality. Singly-linked lists are ideal for applications with large datasets and few or no removals, or for implementing a LIFO queue. Singly-linked lists add the following functionality: .Bl -enum -compact -offset indent .It O(n) removal of any entry in the list. .It O(n) concatenation of two lists. .El .Pp Singly-linked tail queues add the following functionality: .Bl -enum -compact -offset indent .It Entries can be added at the end of a list. .It O(n) removal of any entry in the list. .It They may be concatenated. .El However: .Bl -enum -compact -offset indent .It All list insertions must specify the head of the list. .It Each head entry requires two pointers rather than one. .It Code size is about 15% greater and operations run about 20% slower than singly-linked lists. .El .Pp Singly-linked tail queues are ideal for applications with large datasets and few or no removals, or for implementing a FIFO queue. .Pp All doubly linked types of data structures (lists and tail queues) additionally allow: .Bl -enum -compact -offset indent .It Insertion of a new entry before any element in the list. .It O(1) removal of any entry in the list. .El However: .Bl -enum -compact -offset indent .It Each element requires two pointers rather than one. .It Code size and execution time of operations (except for removal) is about twice that of the singly-linked data-structures. .El .Pp Linked lists are the simplest of the doubly linked data structures. They add the following functionality over the above: .Bl -enum -compact -offset indent .It O(n) concatenation of two lists. .It They may be traversed backwards. .El However: .Bl -enum -compact -offset indent .It To traverse backwards, an entry to begin the traversal and the list in which it is contained must be specified. .El .Pp Tail queues add the following functionality: .Bl -enum -compact -offset indent .It Entries can be added at the end of a list. .It They may be traversed backwards, from tail to head. .It They may be concatenated. .El However: .Bl -enum -compact -offset indent .It All list insertions and removals must specify the head of the list. .It Each head entry requires two pointers rather than one. .It Code size is about 15% greater and operations run about 20% slower than singly-linked lists. .El .Pp In the macro definitions, .Fa TYPE is the name of a user defined structure. The structure must contain a field called .Fa NAME which is of type .Li SLIST_ENTRY , .Li STAILQ_ENTRY , .Li LIST_ENTRY , or .Li TAILQ_ENTRY . In the macro definitions, .Fa CLASSTYPE is the name of a user defined class. The class must contain a field called .Fa NAME which is of type .Li SLIST_CLASS_ENTRY , .Li STAILQ_CLASS_ENTRY , .Li LIST_CLASS_ENTRY , or .Li TAILQ_CLASS_ENTRY . The argument .Fa HEADNAME is the name of a user defined structure that must be declared using the macros .Li SLIST_HEAD , .Li SLIST_CLASS_HEAD , .Li STAILQ_HEAD , .Li STAILQ_CLASS_HEAD , .Li LIST_HEAD , .Li LIST_CLASS_HEAD , .Li TAILQ_HEAD , or .Li TAILQ_CLASS_HEAD . See the examples below for further explanation of how these macros are used. .Sh SINGLY-LINKED LISTS A singly-linked list is headed by a structure defined by the .Nm SLIST_HEAD macro. This structure contains a single pointer to the first element on the list. The elements are singly linked for minimum space and pointer manipulation overhead at the expense of O(n) removal for arbitrary elements. New elements can be added to the list after an existing element or at the head of the list. An .Fa SLIST_HEAD structure is declared as follows: .Bd -literal -offset indent SLIST_HEAD(HEADNAME, TYPE) head; .Ed .Pp where .Fa HEADNAME is the name of the structure to be defined, and .Fa TYPE is the type of the elements to be linked into the list. A pointer to the head of the list can later be declared as: .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (The names .Li head and .Li headp are user selectable.) .Pp The macro .Nm SLIST_HEAD_INITIALIZER evaluates to an initializer for the list .Fa head . .Pp The macro .Nm SLIST_CONCAT concatenates the list headed by .Fa head2 onto the end of the one headed by .Fa head1 removing all entries from the former. Use of this macro should be avoided as it traverses the entirety of the .Fa head1 list. A singly-linked tail queue should be used if this macro is needed in high-usage code paths or to operate on long lists. .Pp The macro .Nm SLIST_EMPTY evaluates to true if there are no elements in the list. .Pp The macro .Nm SLIST_ENTRY declares a structure that connects the elements in the list. .Pp The macro .Nm SLIST_FIRST returns the first element in the list or NULL if the list is empty. .Pp The macro .Nm SLIST_FOREACH traverses the list referenced by .Fa head in the forward direction, assigning each element in turn to .Fa var . .Pp The macro .Nm SLIST_FOREACH_FROM behaves identically to .Nm SLIST_FOREACH when .Fa var is NULL, else it treats .Fa var as a previously found SLIST element and begins the loop at .Fa var instead of the first element in the SLIST referenced by .Fa head . .Pp The macro .Nm SLIST_FOREACH_SAFE traverses the list referenced by .Fa head in the forward direction, assigning each element in turn to .Fa var . However, unlike .Fn SLIST_FOREACH here it is permitted to both remove .Fa var as well as free it from within the loop safely without interfering with the traversal. .Pp The macro .Nm SLIST_FOREACH_FROM_SAFE behaves identically to .Nm SLIST_FOREACH_SAFE when .Fa var is NULL, else it treats .Fa var as a previously found SLIST element and begins the loop at .Fa var instead of the first element in the SLIST referenced by .Fa head . .Pp The macro .Nm SLIST_INIT initializes the list referenced by .Fa head . .Pp The macro .Nm SLIST_INSERT_HEAD inserts the new element .Fa elm at the head of the list. .Pp The macro .Nm SLIST_INSERT_AFTER inserts the new element .Fa elm after the element .Fa listelm . .Pp The macro .Nm SLIST_NEXT returns the next element in the list. .Pp The macro .Nm SLIST_REMOVE_AFTER removes the element after .Fa elm from the list. Unlike .Fa SLIST_REMOVE , this macro does not traverse the entire list. .Pp The macro .Nm SLIST_REMOVE_HEAD removes the element .Fa elm from the head of the list. For optimum efficiency, elements being removed from the head of the list should explicitly use this macro instead of the generic .Fa SLIST_REMOVE macro. .Pp The macro .Nm SLIST_REMOVE removes the element .Fa elm from the list. Use of this macro should be avoided as it traverses the entire list. A doubly-linked list should be used if this macro is needed in high-usage code paths or to operate on long lists. .Pp The macro .Nm SLIST_SWAP swaps the contents of .Fa head1 and .Fa head2 . .Sh SINGLY-LINKED LIST EXAMPLE .Bd -literal SLIST_HEAD(slisthead, entry) head = SLIST_HEAD_INITIALIZER(head); struct slisthead *headp; /* Singly-linked List head. */ struct entry { ... SLIST_ENTRY(entry) entries; /* Singly-linked List. */ ... } *n1, *n2, *n3, *np; SLIST_INIT(&head); /* Initialize the list. */ n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ SLIST_INSERT_HEAD(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* Insert after. */ SLIST_INSERT_AFTER(n1, n2, entries); SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */ free(n2); n3 = SLIST_FIRST(&head); SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */ free(n3); /* Forward traversal. */ SLIST_FOREACH(np, &head, entries) np-> ... /* Safe forward traversal. */ SLIST_FOREACH_SAFE(np, &head, entries, np_temp) { np->do_stuff(); ... SLIST_REMOVE(&head, np, entry, entries); free(np); } while (!SLIST_EMPTY(&head)) { /* List Deletion. */ n1 = SLIST_FIRST(&head); SLIST_REMOVE_HEAD(&head, entries); free(n1); } .Ed .Sh SINGLY-LINKED TAIL QUEUES A singly-linked tail queue is headed by a structure defined by the .Nm STAILQ_HEAD macro. This structure contains a pair of pointers, one to the first element in the tail queue and the other to the last element in the tail queue. The elements are singly linked for minimum space and pointer manipulation overhead at the expense of O(n) removal for arbitrary elements. New elements can be added to the tail queue after an existing element, at the head of the tail queue, or at the end of the tail queue. A .Fa STAILQ_HEAD structure is declared as follows: .Bd -literal -offset indent STAILQ_HEAD(HEADNAME, TYPE) head; .Ed .Pp where .Li HEADNAME is the name of the structure to be defined, and .Li TYPE is the type of the elements to be linked into the tail queue. A pointer to the head of the tail queue can later be declared as: .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (The names .Li head and .Li headp are user selectable.) .Pp The macro .Nm STAILQ_HEAD_INITIALIZER evaluates to an initializer for the tail queue .Fa head . .Pp The macro .Nm STAILQ_CONCAT concatenates the tail queue headed by .Fa head2 onto the end of the one headed by .Fa head1 removing all entries from the former. .Pp The macro .Nm STAILQ_EMPTY evaluates to true if there are no items on the tail queue. .Pp The macro .Nm STAILQ_ENTRY declares a structure that connects the elements in the tail queue. .Pp The macro .Nm STAILQ_FIRST returns the first item on the tail queue or NULL if the tail queue is empty. .Pp The macro .Nm STAILQ_FOREACH traverses the tail queue referenced by .Fa head in the forward direction, assigning each element in turn to .Fa var . .Pp The macro .Nm STAILQ_FOREACH_FROM behaves identically to .Nm STAILQ_FOREACH when .Fa var is NULL, else it treats .Fa var as a previously found STAILQ element and begins the loop at .Fa var instead of the first element in the STAILQ referenced by .Fa head . .Pp The macro .Nm STAILQ_FOREACH_SAFE traverses the tail queue referenced by .Fa head in the forward direction, assigning each element in turn to .Fa var . However, unlike .Fn STAILQ_FOREACH here it is permitted to both remove .Fa var as well as free it from within the loop safely without interfering with the traversal. .Pp The macro .Nm STAILQ_FOREACH_FROM_SAFE behaves identically to .Nm STAILQ_FOREACH_SAFE when .Fa var is NULL, else it treats .Fa var as a previously found STAILQ element and begins the loop at .Fa var instead of the first element in the STAILQ referenced by .Fa head . .Pp The macro .Nm STAILQ_INIT initializes the tail queue referenced by .Fa head . .Pp The macro .Nm STAILQ_INSERT_HEAD inserts the new element .Fa elm at the head of the tail queue. .Pp The macro .Nm STAILQ_INSERT_TAIL inserts the new element .Fa elm at the end of the tail queue. .Pp The macro .Nm STAILQ_INSERT_AFTER inserts the new element .Fa elm after the element .Fa listelm . .Pp The macro .Nm STAILQ_LAST returns the last item on the tail queue. If the tail queue is empty the return value is .Dv NULL . .Pp The macro .Nm STAILQ_NEXT returns the next item on the tail queue, or NULL this item is the last. .Pp The macro .Nm STAILQ_REMOVE_AFTER removes the element after .Fa elm from the tail queue. Unlike .Fa STAILQ_REMOVE , this macro does not traverse the entire tail queue. .Pp The macro .Nm STAILQ_REMOVE_HEAD removes the element at the head of the tail queue. For optimum efficiency, elements being removed from the head of the tail queue should use this macro explicitly rather than the generic .Fa STAILQ_REMOVE macro. .Pp The macro .Nm STAILQ_REMOVE removes the element .Fa elm from the tail queue. Use of this macro should be avoided as it traverses the entire list. A doubly-linked tail queue should be used if this macro is needed in high-usage code paths or to operate on long tail queues. .Pp The macro .Nm STAILQ_SWAP swaps the contents of .Fa head1 and .Fa head2 . .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE .Bd -literal STAILQ_HEAD(stailhead, entry) head = STAILQ_HEAD_INITIALIZER(head); struct stailhead *headp; /* Singly-linked tail queue head. */ struct entry { ... STAILQ_ENTRY(entry) entries; /* Tail queue. */ ... } *n1, *n2, *n3, *np; STAILQ_INIT(&head); /* Initialize the queue. */ n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ STAILQ_INSERT_HEAD(&head, n1, entries); n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ STAILQ_INSERT_TAIL(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* Insert after. */ STAILQ_INSERT_AFTER(&head, n1, n2, entries); /* Deletion. */ STAILQ_REMOVE(&head, n2, entry, entries); free(n2); /* Deletion from the head. */ n3 = STAILQ_FIRST(&head); STAILQ_REMOVE_HEAD(&head, entries); free(n3); /* Forward traversal. */ STAILQ_FOREACH(np, &head, entries) np-> ... /* Safe forward traversal. */ STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { np->do_stuff(); ... STAILQ_REMOVE(&head, np, entry, entries); free(np); } /* TailQ Deletion. */ while (!STAILQ_EMPTY(&head)) { n1 = STAILQ_FIRST(&head); STAILQ_REMOVE_HEAD(&head, entries); free(n1); } /* Faster TailQ Deletion. */ n1 = STAILQ_FIRST(&head); while (n1 != NULL) { n2 = STAILQ_NEXT(n1, entries); free(n1); n1 = n2; } STAILQ_INIT(&head); .Ed .Sh LISTS A list is headed by a structure defined by the .Nm LIST_HEAD macro. This structure contains a single pointer to the first element on the list. The elements are doubly linked so that an arbitrary element can be removed without traversing the list. New elements can be added to the list after an existing element, before an existing element, or at the head of the list. A .Fa LIST_HEAD structure is declared as follows: .Bd -literal -offset indent LIST_HEAD(HEADNAME, TYPE) head; .Ed .Pp where .Fa HEADNAME is the name of the structure to be defined, and .Fa TYPE is the type of the elements to be linked into the list. A pointer to the head of the list can later be declared as: .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (The names .Li head and .Li headp are user selectable.) .Pp The macro .Nm LIST_HEAD_INITIALIZER evaluates to an initializer for the list .Fa head . .Pp The macro .Nm LIST_CONCAT concatenates the list headed by .Fa head2 onto the end of the one headed by .Fa head1 removing all entries from the former. Use of this macro should be avoided as it traverses the entirety of the .Fa head1 list. A tail queue should be used if this macro is needed in high-usage code paths or to operate on long lists. .Pp The macro .Nm LIST_EMPTY evaluates to true if there are no elements in the list. .Pp The macro .Nm LIST_ENTRY declares a structure that connects the elements in the list. .Pp The macro .Nm LIST_FIRST returns the first element in the list or NULL if the list is empty. .Pp The macro .Nm LIST_FOREACH traverses the list referenced by .Fa head in the forward direction, assigning each element in turn to .Fa var . .Pp The macro .Nm LIST_FOREACH_FROM behaves identically to .Nm LIST_FOREACH when .Fa var is NULL, else it treats .Fa var as a previously found LIST element and begins the loop at .Fa var instead of the first element in the LIST referenced by .Fa head . .Pp The macro .Nm LIST_FOREACH_SAFE traverses the list referenced by .Fa head in the forward direction, assigning each element in turn to .Fa var . However, unlike .Fn LIST_FOREACH here it is permitted to both remove .Fa var as well as free it from within the loop safely without interfering with the traversal. .Pp The macro .Nm LIST_FOREACH_FROM_SAFE behaves identically to .Nm LIST_FOREACH_SAFE when .Fa var is NULL, else it treats .Fa var as a previously found LIST element and begins the loop at .Fa var instead of the first element in the LIST referenced by .Fa head . .Pp The macro .Nm LIST_INIT initializes the list referenced by .Fa head . .Pp The macro .Nm LIST_INSERT_HEAD inserts the new element .Fa elm at the head of the list. .Pp The macro .Nm LIST_INSERT_AFTER inserts the new element .Fa elm after the element .Fa listelm . .Pp The macro .Nm LIST_INSERT_BEFORE inserts the new element .Fa elm before the element .Fa listelm . .Pp The macro .Nm LIST_NEXT returns the next element in the list, or NULL if this is the last. .Pp The macro .Nm LIST_PREV returns the previous element in the list, or NULL if this is the first. List .Fa head must contain element .Fa elm . .Pp The macro .Nm LIST_REMOVE removes the element .Fa elm from the list. .Pp The macro .Nm LIST_SWAP swaps the contents of .Fa head1 and .Fa head2 . .Sh LIST EXAMPLE .Bd -literal LIST_HEAD(listhead, entry) head = LIST_HEAD_INITIALIZER(head); struct listhead *headp; /* List head. */ struct entry { ... LIST_ENTRY(entry) entries; /* List. */ ... } *n1, *n2, *n3, *np, *np_temp; LIST_INIT(&head); /* Initialize the list. */ n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ LIST_INSERT_HEAD(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* Insert after. */ LIST_INSERT_AFTER(n1, n2, entries); n3 = malloc(sizeof(struct entry)); /* Insert before. */ LIST_INSERT_BEFORE(n2, n3, entries); LIST_REMOVE(n2, entries); /* Deletion. */ free(n2); /* Forward traversal. */ LIST_FOREACH(np, &head, entries) np-> ... /* Safe forward traversal. */ LIST_FOREACH_SAFE(np, &head, entries, np_temp) { np->do_stuff(); ... LIST_REMOVE(np, entries); free(np); } while (!LIST_EMPTY(&head)) { /* List Deletion. */ n1 = LIST_FIRST(&head); LIST_REMOVE(n1, entries); free(n1); } n1 = LIST_FIRST(&head); /* Faster List Deletion. */ while (n1 != NULL) { n2 = LIST_NEXT(n1, entries); free(n1); n1 = n2; } LIST_INIT(&head); .Ed .Sh TAIL QUEUES A tail queue is headed by a structure defined by the .Nm TAILQ_HEAD macro. This structure contains a pair of pointers, one to the first element in the tail queue and the other to the last element in the tail queue. The elements are doubly linked so that an arbitrary element can be removed without traversing the tail queue. New elements can be added to the tail queue after an existing element, before an existing element, at the head of the tail queue, or at the end of the tail queue. A .Fa TAILQ_HEAD structure is declared as follows: .Bd -literal -offset indent TAILQ_HEAD(HEADNAME, TYPE) head; .Ed .Pp where .Li HEADNAME is the name of the structure to be defined, and .Li TYPE is the type of the elements to be linked into the tail queue. A pointer to the head of the tail queue can later be declared as: .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (The names .Li head and .Li headp are user selectable.) .Pp The macro .Nm TAILQ_HEAD_INITIALIZER evaluates to an initializer for the tail queue .Fa head . .Pp The macro .Nm TAILQ_CONCAT concatenates the tail queue headed by .Fa head2 onto the end of the one headed by .Fa head1 removing all entries from the former. .Pp The macro .Nm TAILQ_EMPTY evaluates to true if there are no items on the tail queue. .Pp The macro .Nm TAILQ_ENTRY declares a structure that connects the elements in the tail queue. .Pp The macro .Nm TAILQ_FIRST returns the first item on the tail queue or NULL if the tail queue is empty. .Pp The macro .Nm TAILQ_FOREACH traverses the tail queue referenced by .Fa head in the forward direction, assigning each element in turn to .Fa var . .Fa var is set to .Dv NULL if the loop completes normally, or if there were no elements. .Pp The macro .Nm TAILQ_FOREACH_FROM behaves identically to .Nm TAILQ_FOREACH when .Fa var is NULL, else it treats .Fa var as a previously found TAILQ element and begins the loop at .Fa var instead of the first element in the TAILQ referenced by .Fa head . .Pp The macro .Nm TAILQ_FOREACH_REVERSE traverses the tail queue referenced by .Fa head in the reverse direction, assigning each element in turn to .Fa var . .Pp The macro .Nm TAILQ_FOREACH_REVERSE_FROM behaves identically to .Nm TAILQ_FOREACH_REVERSE when .Fa var is NULL, else it treats .Fa var as a previously found TAILQ element and begins the reverse loop at .Fa var instead of the last element in the TAILQ referenced by .Fa head . .Pp The macros .Nm TAILQ_FOREACH_SAFE and .Nm TAILQ_FOREACH_REVERSE_SAFE traverse the list referenced by .Fa head in the forward or reverse direction respectively, assigning each element in turn to .Fa var . However, unlike their unsafe counterparts, .Nm TAILQ_FOREACH and .Nm TAILQ_FOREACH_REVERSE permit to both remove .Fa var as well as free it from within the loop safely without interfering with the traversal. .Pp The macro .Nm TAILQ_FOREACH_FROM_SAFE behaves identically to .Nm TAILQ_FOREACH_SAFE when .Fa var is NULL, else it treats .Fa var as a previously found TAILQ element and begins the loop at .Fa var instead of the first element in the TAILQ referenced by .Fa head . .Pp The macro .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE behaves identically to .Nm TAILQ_FOREACH_REVERSE_SAFE when .Fa var is NULL, else it treats .Fa var as a previously found TAILQ element and begins the reverse loop at .Fa var instead of the last element in the TAILQ referenced by .Fa head . .Pp The macro .Nm TAILQ_INIT initializes the tail queue referenced by .Fa head . .Pp The macro .Nm TAILQ_INSERT_HEAD inserts the new element .Fa elm at the head of the tail queue. .Pp The macro .Nm TAILQ_INSERT_TAIL inserts the new element .Fa elm at the end of the tail queue. .Pp The macro .Nm TAILQ_INSERT_AFTER inserts the new element .Fa elm after the element .Fa listelm . .Pp The macro .Nm TAILQ_INSERT_BEFORE inserts the new element .Fa elm before the element .Fa listelm . .Pp The macro .Nm TAILQ_LAST returns the last item on the tail queue. If the tail queue is empty the return value is .Dv NULL . .Pp The macro .Nm TAILQ_NEXT returns the next item on the tail queue, or NULL if this item is the last. .Pp The macro .Nm TAILQ_PREV returns the previous item on the tail queue, or NULL if this item is the first. .Pp The macro .Nm TAILQ_REMOVE removes the element .Fa elm from the tail queue. .Pp The macro .Nm TAILQ_SWAP swaps the contents of .Fa head1 and .Fa head2 . .Sh TAIL QUEUE EXAMPLE .Bd -literal TAILQ_HEAD(tailhead, entry) head = TAILQ_HEAD_INITIALIZER(head); struct tailhead *headp; /* Tail queue head. */ struct entry { ... TAILQ_ENTRY(entry) entries; /* Tail queue. */ ... } *n1, *n2, *n3, *np; TAILQ_INIT(&head); /* Initialize the queue. */ n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ TAILQ_INSERT_HEAD(&head, n1, entries); n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ TAILQ_INSERT_TAIL(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* Insert after. */ TAILQ_INSERT_AFTER(&head, n1, n2, entries); n3 = malloc(sizeof(struct entry)); /* Insert before. */ TAILQ_INSERT_BEFORE(n2, n3, entries); TAILQ_REMOVE(&head, n2, entries); /* Deletion. */ free(n2); /* Forward traversal. */ TAILQ_FOREACH(np, &head, entries) np-> ... /* Safe forward traversal. */ TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { np->do_stuff(); ... TAILQ_REMOVE(&head, np, entries); free(np); } /* Reverse traversal. */ TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) np-> ... /* TailQ Deletion. */ while (!TAILQ_EMPTY(&head)) { n1 = TAILQ_FIRST(&head); TAILQ_REMOVE(&head, n1, entries); free(n1); } /* Faster TailQ Deletion. */ n1 = TAILQ_FIRST(&head); while (n1 != NULL) { n2 = TAILQ_NEXT(n1, entries); free(n1); n1 = n2; } TAILQ_INIT(&head); .Ed .Sh DIAGNOSTICS When debugging .Nm queue(3) , it can be useful to trace queue changes. To enable tracing, define the macro .Va QUEUE_MACRO_DEBUG_TRACE at compile time. .Pp It can also be useful to trash pointers that have been unlinked from a queue, to detect use after removal. To enable pointer trashing, define the macro .Va QUEUE_MACRO_DEBUG_TRASH at compile time. The macro .Fn QMD_IS_TRASHED "void *ptr" returns true if .Fa ptr has been trashed by the .Va QUEUE_MACRO_DEBUG_TRASH option. .Pp In the kernel (with .Va INVARIANTS enabled), the .Fn SLIST_REMOVE_PREVPTR macro is available to aid debugging: .Bl -hang -offset indent .It Fn SLIST_REMOVE_PREVPTR "TYPE **prev" "TYPE *elm" "SLIST_ENTRY NAME" .Pp Removes .Fa elm , which must directly follow the element whose .Va &SLIST_NEXT() is .Fa prev , from the SLIST. This macro validates that .Fa elm follows .Fa prev in .Va INVARIANTS mode. .El .Sh SEE ALSO +.Xr arb 3 , .Xr tree 3 .Sh HISTORY The .Nm queue functions first appeared in .Bx 4.4 . Index: head/share/man/man3/tree.3 =================================================================== --- head/share/man/man3/tree.3 (revision 352336) +++ head/share/man/man3/tree.3 (revision 352337) @@ -1,680 +1,681 @@ .\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $ .\" .\" Copyright 2002 Niels Provos .\" All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" 3. All advertising materials mentioning features or use of this software .\" must display the following acknowledgement: .\" This product includes software developed by Niels Provos. .\" 4. The name of the author may not be used to endorse or promote products .\" derived from this software without specific prior written permission. .\" .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES .\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, .\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, .\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. .\" .\" $FreeBSD$ .\" .Dd May 8, 2019 .Dt TREE 3 .Os .Sh NAME .Nm SPLAY_PROTOTYPE , .Nm SPLAY_GENERATE , .Nm SPLAY_ENTRY , .Nm SPLAY_HEAD , .Nm SPLAY_INITIALIZER , .Nm SPLAY_ROOT , .Nm SPLAY_EMPTY , .Nm SPLAY_NEXT , .Nm SPLAY_MIN , .Nm SPLAY_MAX , .Nm SPLAY_FIND , .Nm SPLAY_LEFT , .Nm SPLAY_RIGHT , .Nm SPLAY_FOREACH , .Nm SPLAY_INIT , .Nm SPLAY_INSERT , .Nm SPLAY_REMOVE , .Nm RB_PROTOTYPE , .Nm RB_PROTOTYPE_STATIC , .Nm RB_PROTOTYPE_INSERT , .Nm RB_PROTOTYPE_INSERT_COLOR , .Nm RB_PROTOTYPE_REMOVE , .Nm RB_PROTOTYPE_REMOVE_COLOR , .Nm RB_PROTOTYPE_FIND , .Nm RB_PROTOTYPE_NFIND , .Nm RB_PROTOTYPE_NEXT , .Nm RB_PROTOTYPE_PREV , .Nm RB_PROTOTYPE_MINMAX , .Nm RB_GENERATE , .Nm RB_GENERATE_STATIC , .Nm RB_GENERATE_INSERT , .Nm RB_GENERATE_INSERT_COLOR , .Nm RB_GENERATE_REMOVE , .Nm RB_GENERATE_REMOVE_COLOR , .Nm RB_GENERATE_FIND , .Nm RB_GENERATE_NFIND , .Nm RB_GENERATE_NEXT , .Nm RB_GENERATE_PREV , .Nm RB_GENERATE_MINMAX , .Nm RB_ENTRY , .Nm RB_HEAD , .Nm RB_INITIALIZER , .Nm RB_ROOT , .Nm RB_EMPTY , .Nm RB_NEXT , .Nm RB_PREV , .Nm RB_MIN , .Nm RB_MAX , .Nm RB_FIND , .Nm RB_NFIND , .Nm RB_LEFT , .Nm RB_RIGHT , .Nm RB_PARENT , .Nm RB_FOREACH , .Nm RB_FOREACH_FROM , .Nm RB_FOREACH_SAFE , .Nm RB_FOREACH_REVERSE , .Nm RB_FOREACH_REVERSE_FROM , .Nm RB_FOREACH_REVERSE_SAFE , .Nm RB_INIT , .Nm RB_INSERT , .Nm RB_REMOVE .Nd "implementations of splay and red-black trees" .Sh SYNOPSIS .In sys/tree.h .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP .Fn SPLAY_GENERATE NAME TYPE FIELD CMP .Fn SPLAY_ENTRY TYPE .Fn SPLAY_HEAD HEADNAME TYPE .Ft "struct TYPE *" .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head" .Fn SPLAY_ROOT "SPLAY_HEAD *head" .Ft bool .Fn SPLAY_EMPTY "SPLAY_HEAD *head" .Ft "struct TYPE *" .Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn SPLAY_MIN NAME "SPLAY_HEAD *head" .Ft "struct TYPE *" .Fn SPLAY_MAX NAME "SPLAY_HEAD *head" .Ft "struct TYPE *" .Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME" .Ft "struct TYPE *" .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME" .Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head" .Ft void .Fn SPLAY_INIT "SPLAY_HEAD *head" .Ft "struct TYPE *" .Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm" .Fn RB_PROTOTYPE NAME TYPE FIELD CMP .Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP .Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR .Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR .Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR .Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR .Fn RB_PROTOTYPE_FIND NAME TYPE ATTR .Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR .Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR .Fn RB_PROTOTYPE_PREV NAME TYPE ATTR .Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR .Fn RB_GENERATE NAME TYPE FIELD CMP .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP .Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR .Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR .Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR .Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR .Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR .Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR .Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR .Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR .Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR .Fn RB_ENTRY TYPE .Fn RB_HEAD HEADNAME TYPE .Fn RB_INITIALIZER "RB_HEAD *head" .Ft "struct TYPE *" .Fn RB_ROOT "RB_HEAD *head" .Ft "bool" .Fn RB_EMPTY "RB_HEAD *head" .Ft "struct TYPE *" .Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_MIN NAME "RB_HEAD *head" .Ft "struct TYPE *" .Fn RB_MAX NAME "RB_HEAD *head" .Ft "struct TYPE *" .Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME" .Ft "struct TYPE *" .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME" .Ft "struct TYPE *" .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME" .Fn RB_FOREACH VARNAME NAME "RB_HEAD *head" .Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME" .Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" .Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head" .Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME" .Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" .Ft void .Fn RB_INIT "RB_HEAD *head" .Ft "struct TYPE *" .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" .Sh DESCRIPTION These macros define data structures for different types of trees: splay trees and red-black trees. .Pp In the macro definitions, .Fa TYPE is the name tag of a user defined structure that must contain a field of type .Vt SPLAY_ENTRY , or .Vt RB_ENTRY , named .Fa ENTRYNAME . The argument .Fa HEADNAME is the name tag of a user defined structure that must be declared using the macros .Fn SPLAY_HEAD , or .Fn RB_HEAD . The argument .Fa NAME has to be a unique name prefix for every tree that is defined. .Pp The function prototypes are declared with .Fn SPLAY_PROTOTYPE , .Fn RB_PROTOTYPE , or .Fn RB_PROTOTYPE_STATIC . The function bodies are generated with .Fn SPLAY_GENERATE , .Fn RB_GENERATE , or .Fn RB_GENERATE_STATIC . See the examples below for further explanation of how these macros are used. .Sh SPLAY TREES A splay tree is a self-organizing data structure. Every operation on the tree causes a splay to happen. The splay moves the requested node to the root of the tree and partly rebalances it. .Pp This has the benefit that request locality causes faster lookups as the requested nodes move to the top of the tree. On the other hand, every lookup causes memory writes. .Pp The Balance Theorem bounds the total access time for .Ar m operations and .Ar n inserts on an initially empty tree as .Fn O "\*[lp]m + n\*[rp]lg n" . The amortized cost for a sequence of .Ar m accesses to a splay tree is .Fn O "lg n" . .Pp A splay tree is headed by a structure defined by the .Fn SPLAY_HEAD macro. A structure is declared as follows: .Bd -ragged -offset indent .Fn SPLAY_HEAD HEADNAME TYPE .Va head ; .Ed .Pp where .Fa HEADNAME is the name of the structure to be defined, and struct .Fa TYPE is the type of the elements to be inserted into the tree. .Pp The .Fn SPLAY_ENTRY macro declares a structure that allows elements to be connected in the tree. .Pp In order to use the functions that manipulate the tree structure, their prototypes need to be declared with the .Fn SPLAY_PROTOTYPE macro, where .Fa NAME is a unique identifier for this particular tree. The .Fa TYPE argument is the type of the structure that is being managed by the tree. The .Fa FIELD argument is the name of the element defined by .Fn SPLAY_ENTRY . .Pp The function bodies are generated with the .Fn SPLAY_GENERATE macro. It takes the same arguments as the .Fn SPLAY_PROTOTYPE macro, but should be used only once. .Pp Finally, the .Fa CMP argument is the name of a function used to compare tree nodes with each other. The function takes two arguments of type .Vt "struct TYPE *" . If the first argument is smaller than the second, the function returns a value smaller than zero. If they are equal, the function returns zero. Otherwise, it should return a value greater than zero. The compare function defines the order of the tree elements. .Pp The .Fn SPLAY_INIT macro initializes the tree referenced by .Fa head . .Pp The splay tree can also be initialized statically by using the .Fn SPLAY_INITIALIZER macro like this: .Bd -ragged -offset indent .Fn SPLAY_HEAD HEADNAME TYPE .Va head = .Fn SPLAY_INITIALIZER &head ; .Ed .Pp The .Fn SPLAY_INSERT macro inserts the new element .Fa elm into the tree. .Pp The .Fn SPLAY_REMOVE macro removes the element .Fa elm from the tree pointed by .Fa head . .Pp The .Fn SPLAY_FIND macro can be used to find a particular element in the tree. .Bd -literal -offset indent struct TYPE find, *res; find.key = 30; res = SPLAY_FIND(NAME, head, &find); .Ed .Pp The .Fn SPLAY_ROOT , .Fn SPLAY_MIN , .Fn SPLAY_MAX , and .Fn SPLAY_NEXT macros can be used to traverse the tree: .Bd -literal -offset indent for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np)) .Ed .Pp Or, for simplicity, one can use the .Fn SPLAY_FOREACH macro: .Bd -ragged -offset indent .Fn SPLAY_FOREACH np NAME head .Ed .Pp The .Fn SPLAY_EMPTY macro should be used to check whether a splay tree is empty. .Sh RED-BLACK TREES A red-black tree is a binary search tree with the node color as an extra attribute. It fulfills a set of conditions: .Bl -enum -offset indent .It Every search path from the root to a leaf consists of the same number of black nodes. .It Each red node (except for the root) has a black parent. .It Each leaf node is black. .El .Pp Every operation on a red-black tree is bounded as .Fn O "lg n" . The maximum height of a red-black tree is .Fn 2lg "n + 1" . .Pp A red-black tree is headed by a structure defined by the .Fn RB_HEAD macro. A structure is declared as follows: .Bd -ragged -offset indent .Fn RB_HEAD HEADNAME TYPE .Va head ; .Ed .Pp where .Fa HEADNAME is the name of the structure to be defined, and struct .Fa TYPE is the type of the elements to be inserted into the tree. .Pp The .Fn RB_ENTRY macro declares a structure that allows elements to be connected in the tree. .Pp In order to use the functions that manipulate the tree structure, their prototypes need to be declared with the .Fn RB_PROTOTYPE or .Fn RB_PROTOTYPE_STATIC macro, where .Fa NAME is a unique identifier for this particular tree. The .Fa TYPE argument is the type of the structure that is being managed by the tree. The .Fa FIELD argument is the name of the element defined by .Fn RB_ENTRY . Individual prototypes can be declared with .Fn RB_PROTOTYPE_INSERT , .Fn RB_PROTOTYPE_INSERT_COLOR , .Fn RB_PROTOTYPE_REMOVE , .Fn RB_PROTOTYPE_REMOVE_COLOR , .Fn RB_PROTOTYPE_FIND , .Fn RB_PROTOTYPE_NFIND , .Fn RB_PROTOTYPE_NEXT , .Fn RB_PROTOTYPE_PREV , and .Fn RB_PROTOTYPE_MINMAX in case not all functions are required. The individual prototype macros expect .Fa NAME , .Fa TYPE , and .Fa ATTR arguments. The .Fa ATTR argument must be empty for global functions or .Fa static for static functions. .Pp The function bodies are generated with the .Fn RB_GENERATE or .Fn RB_GENERATE_STATIC macro. These macros take the same arguments as the .Fn RB_PROTOTYPE and .Fn RB_PROTOTYPE_STATIC macros, but should be used only once. As an alternative individual function bodies are generated with the .Fn RB_GENERATE_INSERT , .Fn RB_GENERATE_INSERT_COLOR , .Fn RB_GENERATE_REMOVE , .Fn RB_GENERATE_REMOVE_COLOR , .Fn RB_GENERATE_FIND , .Fn RB_GENERATE_NFIND , .Fn RB_GENERATE_NEXT , .Fn RB_GENERATE_PREV , and .Fn RB_GENERATE_MINMAX macros. .Pp Finally, the .Fa CMP argument is the name of a function used to compare tree nodes with each other. The function takes two arguments of type .Vt "struct TYPE *" . If the first argument is smaller than the second, the function returns a value smaller than zero. If they are equal, the function returns zero. Otherwise, it should return a value greater than zero. The compare function defines the order of the tree elements. .Pp The .Fn RB_INIT macro initializes the tree referenced by .Fa head . .Pp The red-black tree can also be initialized statically by using the .Fn RB_INITIALIZER macro like this: .Bd -ragged -offset indent .Fn RB_HEAD HEADNAME TYPE .Va head = .Fn RB_INITIALIZER &head ; .Ed .Pp The .Fn RB_INSERT macro inserts the new element .Fa elm into the tree. .Pp The .Fn RB_REMOVE macro removes the element .Fa elm from the tree pointed by .Fa head . .Pp The .Fn RB_FIND and .Fn RB_NFIND macros can be used to find a particular element in the tree. .Bd -literal -offset indent struct TYPE find, *res; find.key = 30; res = RB_FIND(NAME, head, &find); .Ed .Pp The .Fn RB_ROOT , .Fn RB_MIN , .Fn RB_MAX , .Fn RB_NEXT , and .Fn RB_PREV macros can be used to traverse the tree: .Pp .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))" .Pp Or, for simplicity, one can use the .Fn RB_FOREACH or .Fn RB_FOREACH_REVERSE macro: .Bd -ragged -offset indent .Fn RB_FOREACH np NAME head .Ed .Pp The macros .Fn RB_FOREACH_SAFE and .Fn RB_FOREACH_REVERSE_SAFE traverse the tree referenced by head in a forward or reverse direction respectively, assigning each element in turn to np. However, unlike their unsafe counterparts, they permit both the removal of np as well as freeing it from within the loop safely without interfering with the traversal. .Pp Both .Fn RB_FOREACH_FROM and .Fn RB_FOREACH_REVERSE_FROM may be used to continue an interrupted traversal in a forward or reverse direction respectively. The head pointer is not required. The pointer to the node from where to resume the traversal should be passed as their last argument, and will be overwritten to provide safe traversal. .Pp The .Fn RB_EMPTY macro should be used to check whether a red-black tree is empty. .Sh EXAMPLES The following example demonstrates how to declare a red-black tree holding integers. Values are inserted into it and the contents of the tree are printed in order. Lastly, the internal structure of the tree is printed. .Bd -literal -offset 3n #include #include #include #include struct node { RB_ENTRY(node) entry; int i; }; int intcmp(struct node *e1, struct node *e2) { return (e1->i < e2->i ? -1 : e1->i > e2->i); } RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); RB_GENERATE(inttree, node, entry, intcmp) int testdata[] = { 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18, 7, 11, 14 }; void print_tree(struct node *n) { struct node *left, *right; if (n == NULL) { printf("nil"); return; } left = RB_LEFT(n, entry); right = RB_RIGHT(n, entry); if (left == NULL && right == NULL) printf("%d", n->i); else { printf("%d(", n->i); print_tree(left); printf(","); print_tree(right); printf(")"); } } int main(void) { int i; struct node *n; for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) { if ((n = malloc(sizeof(struct node))) == NULL) err(1, NULL); n->i = testdata[i]; RB_INSERT(inttree, &head, n); } RB_FOREACH(n, inttree, &head) { printf("%d\en", n->i); } print_tree(RB_ROOT(&head)); printf("\en"); return (0); } .Ed .Sh NOTES Trying to free a tree in the following way is a common error: .Bd -literal -offset indent SPLAY_FOREACH(var, NAME, head) { SPLAY_REMOVE(NAME, head, var); free(var); } free(head); .Ed .Pp Since .Va var is freed, the .Fn FOREACH macro refers to a pointer that may have been reallocated already. Proper code needs a second variable. .Bd -literal -offset indent for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) { nxt = SPLAY_NEXT(NAME, head, var); SPLAY_REMOVE(NAME, head, var); free(var); } .Ed .Pp Both .Fn RB_INSERT and .Fn SPLAY_INSERT return .Dv NULL if the element was inserted in the tree successfully, otherwise they return a pointer to the element with the colliding key. .Pp Accordingly, .Fn RB_REMOVE and .Fn SPLAY_REMOVE return the pointer to the removed element otherwise they return .Dv NULL to indicate an error. .Sh SEE ALSO +.Xr arb 3 , .Xr queue 3 .Sh AUTHORS The author of the tree macros is .An Niels Provos . Index: head/sys/sys/arb.h =================================================================== --- head/sys/sys/arb.h (nonexistent) +++ head/sys/sys/arb.h (revision 352337) @@ -0,0 +1,779 @@ +/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ +/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ +/* $FreeBSD$ */ + +/*- + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD + * + * Copyright 2002 Niels Provos + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _SYS_ARB_H_ +#define _SYS_ARB_H_ + +#include + +/* Array-based red-black trees. */ + +#define ARB_NULLIDX -1 +#define ARB_NULLCOL -1 + +#define ARB_BLACK 0 +#define ARB_RED 1 + +#define ARB_NEGINF -1 +#define ARB_INF 1 + +#define ARB_HEAD(name, type, idxbits) \ +struct name { \ + int##idxbits##_t arb_curnodes; \ + int##idxbits##_t arb_maxnodes; \ + int##idxbits##_t arb_root_idx; \ + int##idxbits##_t arb_free_idx; \ + int##idxbits##_t arb_min_idx; \ + int##idxbits##_t arb_max_idx; \ + struct type arb_nodes[]; \ +} +#define ARB8_HEAD(name, type) ARB_HEAD(name, type, 8) +#define ARB16_HEAD(name, type) ARB_HEAD(name, type, 16) +#define ARB32_HEAD(name, type) ARB_HEAD(name, type, 32) + +#define ARB_ALLOCSIZE(head, maxn, x) \ + (sizeof(*head) + (maxn) * sizeof(*x)) + +#define ARB_INITIALIZER(name, maxn) \ + ((struct name){ 0, maxn, ARB_NULLIDX, ARB_NULLIDX, \ + ARB_NULLIDX, ARB_NULLIDX }) + +#define ARB_INIT(x, field, head, maxn) \ + (head)->arb_curnodes = 0; \ + (head)->arb_maxnodes = (maxn); \ + (head)->arb_root_idx = (head)->arb_free_idx = \ + (head)->arb_min_idx = (head)->arb_max_idx = ARB_NULLIDX; \ + /* The ARB_RETURNFREE() puts all entries on the free list. */ \ + ARB_ARRFOREACH_REVWCOND(x, field, head, \ + ARB_RETURNFREE(head, x, field)) + +#define ARB_ENTRY(idxbits) \ +struct { \ + int##idxbits##_t arbe_parent_idx; \ + int##idxbits##_t arbe_left_idx; \ + int##idxbits##_t arbe_right_idx; \ + int8_t arbe_color; \ +} +#define ARB8_ENTRY() ARB_ENTRY(8) +#define ARB16_ENTRY() ARB_ENTRY(16) +#define ARB32_ENTRY() ARB_ENTRY(32) + +#define ARB_ENTRYINIT(elm, field) do { \ + (elm)->field.arbe_parent_idx = \ + (elm)->field.arbe_left_idx = \ + (elm)->field.arbe_right_idx = ARB_NULLIDX; \ + (elm)->field.arbe_color = ARB_NULLCOL; \ +} while (/*CONSTCOND*/ 0) + +#define ARB_ELMTYPE(head) __typeof(&(head)->arb_nodes[0]) +#define ARB_NODES(head) (head)->arb_nodes +#define ARB_MAXNODES(head) (head)->arb_maxnodes +#define ARB_CURNODES(head) (head)->arb_curnodes +#define ARB_EMPTY(head) ((head)->arb_curnodes == 0) +#define ARB_FULL(head) ((head)->arb_curnodes >= (head)->arb_maxnodes) +#define ARB_CNODE(head, idx) \ + ((((intptr_t)(idx) <= ARB_NULLIDX) || ((idx) >= ARB_MAXNODES(head))) ? \ + NULL : ((const ARB_ELMTYPE(head))(ARB_NODES(head) + (idx)))) +#define ARB_NODE(head, idx) \ + (__DECONST(ARB_ELMTYPE(head), ARB_CNODE(head, idx))) +#define ARB_ROOT(head) ARB_NODE(head, ARB_ROOTIDX(head)) +#define ARB_LEFT(head, elm, field) ARB_NODE(head, ARB_LEFTIDX(elm, field)) +#define ARB_RIGHT(head, elm, field) ARB_NODE(head, ARB_RIGHTIDX(elm, field)) +#define ARB_PARENT(head, elm, field) ARB_NODE(head, ARB_PARENTIDX(elm, field)) +#define ARB_FREEIDX(head) (head)->arb_free_idx +#define ARB_ROOTIDX(head) (head)->arb_root_idx +#define ARB_MINIDX(head) (head)->arb_min_idx +#define ARB_MAXIDX(head) (head)->arb_max_idx +#define ARB_SELFIDX(head, elm) \ + ((elm) ? ((intptr_t)((((const uint8_t *)(elm)) - \ + ((const uint8_t *)ARB_NODES(head))) / sizeof(*(elm)))) : \ + (intptr_t)ARB_NULLIDX) +#define ARB_LEFTIDX(elm, field) (elm)->field.arbe_left_idx +#define ARB_RIGHTIDX(elm, field) (elm)->field.arbe_right_idx +#define ARB_PARENTIDX(elm, field) (elm)->field.arbe_parent_idx +#define ARB_COLOR(elm, field) (elm)->field.arbe_color +#define ARB_PREVFREE(head, elm, field) \ + ARB_NODE(head, ARB_PREVFREEIDX(elm, field)) +#define ARB_PREVFREEIDX(elm, field) ARB_LEFTIDX(elm, field) +#define ARB_NEXTFREE(head, elm, field) \ + ARB_NODE(head, ARB_NEXTFREEIDX(elm, field)) +#define ARB_NEXTFREEIDX(elm, field) ARB_RIGHTIDX(elm, field) +#define ARB_ISFREE(elm, field) (ARB_COLOR(elm, field) == ARB_NULLCOL) + +#define ARB_SET(head, elm, parent, field) do { \ + ARB_PARENTIDX(elm, field) = \ + parent ? ARB_SELFIDX(head, parent) : ARB_NULLIDX; \ + ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(elm, field) = ARB_NULLIDX; \ + ARB_COLOR(elm, field) = ARB_RED; \ +} while (/*CONSTCOND*/ 0) + +#define ARB_SET_BLACKRED(black, red, field) do { \ + ARB_COLOR(black, field) = ARB_BLACK; \ + ARB_COLOR(red, field) = ARB_RED; \ +} while (/*CONSTCOND*/ 0) + +#ifndef ARB_AUGMENT +#define ARB_AUGMENT(x) do {} while (0) +#endif + +#define ARB_ROTATE_LEFT(head, elm, tmp, field) do { \ + __typeof(ARB_RIGHTIDX(elm, field)) _tmpidx; \ + (tmp) = ARB_RIGHT(head, elm, field); \ + _tmpidx = ARB_RIGHTIDX(elm, field); \ + ARB_RIGHTIDX(elm, field) = ARB_LEFTIDX(tmp, field); \ + if (ARB_RIGHTIDX(elm, field) != ARB_NULLIDX) { \ + ARB_PARENTIDX(ARB_LEFT(head, tmp, field), field) = \ + ARB_SELFIDX(head, elm); \ + } \ + ARB_AUGMENT(elm); \ + ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \ + if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \ + if (ARB_SELFIDX(head, elm) == \ + ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \ + ARB_LEFTIDX(ARB_PARENT(head, elm, field), \ + field) = _tmpidx; \ + else \ + ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \ + field) = _tmpidx; \ + } else \ + ARB_ROOTIDX(head) = _tmpidx; \ + ARB_LEFTIDX(tmp, field) = ARB_SELFIDX(head, elm); \ + ARB_PARENTIDX(elm, field) = _tmpidx; \ + ARB_AUGMENT(tmp); \ + if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \ + ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \ +} while (/*CONSTCOND*/ 0) + +#define ARB_ROTATE_RIGHT(head, elm, tmp, field) do { \ + __typeof(ARB_LEFTIDX(elm, field)) _tmpidx; \ + (tmp) = ARB_LEFT(head, elm, field); \ + _tmpidx = ARB_LEFTIDX(elm, field); \ + ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(tmp, field); \ + if (ARB_LEFTIDX(elm, field) != ARB_NULLIDX) { \ + ARB_PARENTIDX(ARB_RIGHT(head, tmp, field), field) = \ + ARB_SELFIDX(head, elm); \ + } \ + ARB_AUGMENT(elm); \ + ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \ + if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \ + if (ARB_SELFIDX(head, elm) == \ + ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \ + ARB_LEFTIDX(ARB_PARENT(head, elm, field), \ + field) = _tmpidx; \ + else \ + ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \ + field) = _tmpidx; \ + } else \ + ARB_ROOTIDX(head) = _tmpidx; \ + ARB_RIGHTIDX(tmp, field) = ARB_SELFIDX(head, elm); \ + ARB_PARENTIDX(elm, field) = _tmpidx; \ + ARB_AUGMENT(tmp); \ + if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \ + ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \ +} while (/*CONSTCOND*/ 0) + +#define ARB_RETURNFREE(head, elm, field) \ +({ \ + ARB_COLOR(elm, field) = ARB_NULLCOL; \ + ARB_NEXTFREEIDX(elm, field) = ARB_FREEIDX(head); \ + ARB_FREEIDX(head) = ARB_SELFIDX(head, elm); \ + elm; \ +}) + +#define ARB_GETFREEAT(head, field, fidx) \ +({ \ + __typeof(ARB_NODE(head, 0)) _elm, _prevelm; \ + int _idx = fidx; \ + if (ARB_FREEIDX(head) == ARB_NULLIDX && !ARB_FULL(head)) { \ + /* Populate the free list. */ \ + ARB_ARRFOREACH_REVERSE(_elm, field, head) { \ + if (ARB_ISFREE(_elm, field)) \ + ARB_RETURNFREE(head, _elm, field); \ + } \ + } \ + _elm = _prevelm = ARB_NODE(head, ARB_FREEIDX(head)); \ + for (; _idx > 0 && _elm != NULL; _idx--, _prevelm = _elm) \ + _elm = ARB_NODE(head, ARB_NEXTFREEIDX(_elm, field)); \ + if (_elm) { \ + if (fidx == 0) \ + ARB_FREEIDX(head) = \ + ARB_NEXTFREEIDX(_elm, field); \ + else \ + ARB_NEXTFREEIDX(_prevelm, field) = \ + ARB_NEXTFREEIDX(_elm, field); \ + } \ + _elm; \ +}) +#define ARB_GETFREE(head, field) ARB_GETFREEAT(head, field, 0) + +/* Generates prototypes and inline functions */ +#define ARB_PROTOTYPE(name, type, field, cmp) \ + ARB_PROTOTYPE_INTERNAL(name, type, field, cmp,) +#define ARB_PROTOTYPE_STATIC(name, type, field, cmp) \ + ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) +#define ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ + ARB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ + ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ + ARB_PROTOTYPE_INSERT(name, type, attr); \ + ARB_PROTOTYPE_REMOVE(name, type, attr); \ + ARB_PROTOTYPE_CFIND(name, type, attr); \ + ARB_PROTOTYPE_FIND(name, type, attr); \ + ARB_PROTOTYPE_NFIND(name, type, attr); \ + ARB_PROTOTYPE_CNEXT(name, type, attr); \ + ARB_PROTOTYPE_NEXT(name, type, attr); \ + ARB_PROTOTYPE_CPREV(name, type, attr); \ + ARB_PROTOTYPE_PREV(name, type, attr); \ + ARB_PROTOTYPE_CMINMAX(name, type, attr); \ + ARB_PROTOTYPE_MINMAX(name, type, attr); \ + ARB_PROTOTYPE_REBALANCE(name, type, attr); +#define ARB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ + attr void name##_ARB_INSERT_COLOR(struct name *, struct type *) +#define ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ + attr void name##_ARB_REMOVE_COLOR(struct name *, struct type *, struct type *) +#define ARB_PROTOTYPE_REMOVE(name, type, attr) \ + attr struct type *name##_ARB_REMOVE(struct name *, struct type *) +#define ARB_PROTOTYPE_INSERT(name, type, attr) \ + attr struct type *name##_ARB_INSERT(struct name *, struct type *) +#define ARB_PROTOTYPE_CFIND(name, type, attr) \ + attr const struct type *name##_ARB_CFIND(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_FIND(name, type, attr) \ + attr struct type *name##_ARB_FIND(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_NFIND(name, type, attr) \ + attr struct type *name##_ARB_NFIND(struct name *, struct type *) +#define ARB_PROTOTYPE_CNFIND(name, type, attr) \ + attr const struct type *name##_ARB_CNFIND(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_CNEXT(name, type, attr) \ + attr const struct type *name##_ARB_CNEXT(const struct name *head,\ + const struct type *) +#define ARB_PROTOTYPE_NEXT(name, type, attr) \ + attr struct type *name##_ARB_NEXT(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_CPREV(name, type, attr) \ + attr const struct type *name##_ARB_CPREV(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_PREV(name, type, attr) \ + attr struct type *name##_ARB_PREV(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_CMINMAX(name, type, attr) \ + attr const struct type *name##_ARB_CMINMAX(const struct name *, int) +#define ARB_PROTOTYPE_MINMAX(name, type, attr) \ + attr struct type *name##_ARB_MINMAX(const struct name *, int) +#define ARB_PROTOTYPE_REBALANCE(name, type, attr) \ + attr struct type *name##_ARB_REBALANCE(struct name *, struct type *) + +#define ARB_GENERATE(name, type, field, cmp) \ + ARB_GENERATE_INTERNAL(name, type, field, cmp,) +#define ARB_GENERATE_STATIC(name, type, field, cmp) \ + ARB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) +#define ARB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ + ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \ + ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ + ARB_GENERATE_INSERT(name, type, field, cmp, attr) \ + ARB_GENERATE_REMOVE(name, type, field, attr) \ + ARB_GENERATE_CFIND(name, type, field, cmp, attr) \ + ARB_GENERATE_FIND(name, type, field, cmp, attr) \ + ARB_GENERATE_CNEXT(name, type, field, attr) \ + ARB_GENERATE_NEXT(name, type, field, attr) \ + ARB_GENERATE_CPREV(name, type, field, attr) \ + ARB_GENERATE_PREV(name, type, field, attr) \ + ARB_GENERATE_CMINMAX(name, type, field, attr) \ + ARB_GENERATE_MINMAX(name, type, field, attr) \ + ARB_GENERATE_REBALANCE(name, type, field, cmp, attr) + +#define ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \ +attr void \ +name##_ARB_INSERT_COLOR(struct name *head, struct type *elm) \ +{ \ + struct type *parent, *gparent, *tmp; \ + while ((parent = ARB_PARENT(head, elm, field)) != NULL && \ + ARB_COLOR(parent, field) == ARB_RED) { \ + gparent = ARB_PARENT(head, parent, field); \ + if (parent == ARB_LEFT(head, gparent, field)) { \ + tmp = ARB_RIGHT(head, gparent, field); \ + if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \ + ARB_COLOR(tmp, field) = ARB_BLACK; \ + ARB_SET_BLACKRED(parent, gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (ARB_RIGHT(head, parent, field) == elm) { \ + ARB_ROTATE_LEFT(head, parent, tmp, field); \ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + ARB_SET_BLACKRED(parent, gparent, field); \ + ARB_ROTATE_RIGHT(head, gparent, tmp, field); \ + } else { \ + tmp = ARB_LEFT(head, gparent, field); \ + if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \ + ARB_COLOR(tmp, field) = ARB_BLACK; \ + ARB_SET_BLACKRED(parent, gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (ARB_LEFT(head, parent, field) == elm) { \ + ARB_ROTATE_RIGHT(head, parent, tmp, field); \ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + ARB_SET_BLACKRED(parent, gparent, field); \ + ARB_ROTATE_LEFT(head, gparent, tmp, field); \ + } \ + } \ + ARB_COLOR(ARB_ROOT(head), field) = ARB_BLACK; \ +} + +#define ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ +attr void \ +name##_ARB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ +{ \ + struct type *tmp; \ + while ((elm == NULL || ARB_COLOR(elm, field) == ARB_BLACK) && \ + elm != ARB_ROOT(head)) { \ + if (ARB_LEFT(head, parent, field) == elm) { \ + tmp = ARB_RIGHT(head, parent, field); \ + if (ARB_COLOR(tmp, field) == ARB_RED) { \ + ARB_SET_BLACKRED(tmp, parent, field); \ + ARB_ROTATE_LEFT(head, parent, tmp, field); \ + tmp = ARB_RIGHT(head, parent, field); \ + } \ + if ((ARB_LEFT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \ + (ARB_RIGHT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \ + ARB_COLOR(tmp, field) = ARB_RED; \ + elm = parent; \ + parent = ARB_PARENT(head, elm, field); \ + } else { \ + if (ARB_RIGHT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK) { \ + struct type *oleft; \ + if ((oleft = ARB_LEFT(head, tmp, field)) \ + != NULL) \ + ARB_COLOR(oleft, field) = ARB_BLACK; \ + ARB_COLOR(tmp, field) = ARB_RED; \ + ARB_ROTATE_RIGHT(head, tmp, oleft, field); \ + tmp = ARB_RIGHT(head, parent, field); \ + } \ + ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \ + ARB_COLOR(parent, field) = ARB_BLACK; \ + if (ARB_RIGHT(head, tmp, field)) \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = ARB_BLACK; \ + ARB_ROTATE_LEFT(head, parent, tmp, field); \ + elm = ARB_ROOT(head); \ + break; \ + } \ + } else { \ + tmp = ARB_LEFT(head, parent, field); \ + if (ARB_COLOR(tmp, field) == ARB_RED) { \ + ARB_SET_BLACKRED(tmp, parent, field); \ + ARB_ROTATE_RIGHT(head, parent, tmp, field); \ + tmp = ARB_LEFT(head, parent, field); \ + } \ + if ((ARB_LEFT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \ + (ARB_RIGHT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \ + ARB_COLOR(tmp, field) = ARB_RED; \ + elm = parent; \ + parent = ARB_PARENT(head, elm, field); \ + } else { \ + if (ARB_LEFT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) { \ + struct type *oright; \ + if ((oright = ARB_RIGHT(head, tmp, field)) \ + != NULL) \ + ARB_COLOR(oright, field) = ARB_BLACK; \ + ARB_COLOR(tmp, field) = ARB_RED; \ + ARB_ROTATE_LEFT(head, tmp, oright, field); \ + tmp = ARB_LEFT(head, parent, field); \ + } \ + ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \ + ARB_COLOR(parent, field) = ARB_BLACK; \ + if (ARB_LEFT(head, tmp, field)) \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) = ARB_BLACK; \ + ARB_ROTATE_RIGHT(head, parent, tmp, field); \ + elm = ARB_ROOT(head); \ + break; \ + } \ + } \ + } \ + if (elm) \ + ARB_COLOR(elm, field) = ARB_BLACK; \ +} + +#define ARB_GENERATE_REMOVE(name, type, field, attr) \ +attr struct type * \ +name##_ARB_REMOVE(struct name *head, struct type *elm) \ +{ \ + struct type *child, *parent, *old = elm; \ + int color; \ + if (ARB_LEFT(head, elm, field) == NULL) \ + child = ARB_RIGHT(head, elm, field); \ + else if (ARB_RIGHT(head, elm, field) == NULL) \ + child = ARB_LEFT(head, elm, field); \ + else { \ + struct type *left; \ + elm = ARB_RIGHT(head, elm, field); \ + while ((left = ARB_LEFT(head, elm, field)) != NULL) \ + elm = left; \ + child = ARB_RIGHT(head, elm, field); \ + parent = ARB_PARENT(head, elm, field); \ + color = ARB_COLOR(elm, field); \ + if (child) \ + ARB_PARENTIDX(child, field) = \ + ARB_SELFIDX(head, parent); \ + if (parent) { \ + if (ARB_LEFT(head, parent, field) == elm) \ + ARB_LEFTIDX(parent, field) = \ + ARB_SELFIDX(head, child); \ + else \ + ARB_RIGHTIDX(parent, field) = \ + ARB_SELFIDX(head, child); \ + ARB_AUGMENT(parent); \ + } else \ + ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \ + if (ARB_PARENT(head, elm, field) == old) \ + parent = elm; \ + (elm)->field = (old)->field; \ + if (ARB_PARENT(head, old, field)) { \ + if (ARB_LEFT(head, ARB_PARENT(head, old, field), \ + field) == old) \ + ARB_LEFTIDX(ARB_PARENT(head, old, field), \ + field) = ARB_SELFIDX(head, elm); \ + else \ + ARB_RIGHTIDX(ARB_PARENT(head, old, field),\ + field) = ARB_SELFIDX(head, elm); \ + ARB_AUGMENT(ARB_PARENT(head, old, field)); \ + } else \ + ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \ + ARB_PARENTIDX(ARB_LEFT(head, old, field), field) = \ + ARB_SELFIDX(head, elm); \ + if (ARB_RIGHT(head, old, field)) \ + ARB_PARENTIDX(ARB_RIGHT(head, old, field), \ + field) = ARB_SELFIDX(head, elm); \ + if (parent) { \ + left = parent; \ + do { \ + ARB_AUGMENT(left); \ + } while ((left = ARB_PARENT(head, left, field)) \ + != NULL); \ + } \ + goto color; \ + } \ + parent = ARB_PARENT(head, elm, field); \ + color = ARB_COLOR(elm, field); \ + if (child) \ + ARB_PARENTIDX(child, field) = ARB_SELFIDX(head, parent);\ + if (parent) { \ + if (ARB_LEFT(head, parent, field) == elm) \ + ARB_LEFTIDX(parent, field) = \ + ARB_SELFIDX(head, child); \ + else \ + ARB_RIGHTIDX(parent, field) = \ + ARB_SELFIDX(head, child); \ + ARB_AUGMENT(parent); \ + } else \ + ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \ +color: \ + if (color == ARB_BLACK) \ + name##_ARB_REMOVE_COLOR(head, parent, child); \ + ARB_CURNODES(head) -= 1; \ + if (ARB_MINIDX(head) == ARB_SELFIDX(head, old)) \ + ARB_MINIDX(head) = ARB_PARENTIDX(old, field); \ + if (ARB_MAXIDX(head) == ARB_SELFIDX(head, old)) \ + ARB_MAXIDX(head) = ARB_PARENTIDX(old, field); \ + ARB_RETURNFREE(head, old, field); \ + return (old); \ +} \ + +#define ARB_GENERATE_INSERT(name, type, field, cmp, attr) \ +/* Inserts a node into the RB tree */ \ +attr struct type * \ +name##_ARB_INSERT(struct name *head, struct type *elm) \ +{ \ + struct type *tmp; \ + struct type *parent = NULL; \ + int comp = 0; \ + tmp = ARB_ROOT(head); \ + while (tmp) { \ + parent = tmp; \ + comp = (cmp)(elm, parent); \ + if (comp < 0) \ + tmp = ARB_LEFT(head, tmp, field); \ + else if (comp > 0) \ + tmp = ARB_RIGHT(head, tmp, field); \ + else \ + return (tmp); \ + } \ + ARB_SET(head, elm, parent, field); \ + if (parent != NULL) { \ + if (comp < 0) \ + ARB_LEFTIDX(parent, field) = \ + ARB_SELFIDX(head, elm); \ + else \ + ARB_RIGHTIDX(parent, field) = \ + ARB_SELFIDX(head, elm); \ + ARB_AUGMENT(parent); \ + } else \ + ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \ + name##_ARB_INSERT_COLOR(head, elm); \ + ARB_CURNODES(head) += 1; \ + if (ARB_MINIDX(head) == ARB_NULLIDX || \ + (ARB_PARENTIDX(elm, field) == ARB_MINIDX(head) && \ + ARB_LEFTIDX(parent, field) == ARB_SELFIDX(head, elm))) \ + ARB_MINIDX(head) = ARB_SELFIDX(head, elm); \ + if (ARB_MAXIDX(head) == ARB_NULLIDX || \ + (ARB_PARENTIDX(elm, field) == ARB_MAXIDX(head) && \ + ARB_RIGHTIDX(parent, field) == ARB_SELFIDX(head, elm))) \ + ARB_MAXIDX(head) = ARB_SELFIDX(head, elm); \ + return (NULL); \ +} + +#define ARB_GENERATE_CFIND(name, type, field, cmp, attr) \ +/* Finds the node with the same key as elm */ \ +attr const struct type * \ +name##_ARB_CFIND(const struct name *head, const struct type *elm) \ +{ \ + const struct type *tmp = ARB_ROOT(head); \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) \ + tmp = ARB_LEFT(head, tmp, field); \ + else if (comp > 0) \ + tmp = ARB_RIGHT(head, tmp, field); \ + else \ + return (tmp); \ + } \ + return (NULL); \ +} + +#define ARB_GENERATE_FIND(name, type, field, cmp, attr) \ +attr struct type * \ +name##_ARB_FIND(const struct name *head, const struct type *elm) \ +{ return (__DECONST(struct type *, name##_ARB_CFIND(head, elm))); } + +#define ARB_GENERATE_CNFIND(name, type, field, cmp, attr) \ +/* Finds the first node greater than or equal to the search key */ \ +attr const struct type * \ +name##_ARB_CNFIND(const struct name *head, const struct type *elm) \ +{ \ + const struct type *tmp = ARB_ROOT(head); \ + const struct type *res = NULL; \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) { \ + res = tmp; \ + tmp = ARB_LEFT(head, tmp, field); \ + } \ + else if (comp > 0) \ + tmp = ARB_RIGHT(head, tmp, field); \ + else \ + return (tmp); \ + } \ + return (res); \ +} + +#define ARB_GENERATE_NFIND(name, type, field, cmp, attr) \ +attr struct type * \ +name##_ARB_NFIND(const struct name *head, const struct type *elm) \ +{ return (__DECONST(struct type *, name##_ARB_CNFIND(head, elm))); } + +#define ARB_GENERATE_CNEXT(name, type, field, attr) \ +/* ARGSUSED */ \ +attr const struct type * \ +name##_ARB_CNEXT(const struct name *head, const struct type *elm) \ +{ \ + if (ARB_RIGHT(head, elm, field)) { \ + elm = ARB_RIGHT(head, elm, field); \ + while (ARB_LEFT(head, elm, field)) \ + elm = ARB_LEFT(head, elm, field); \ + } else { \ + if (ARB_PARENT(head, elm, field) && \ + (elm == ARB_LEFT(head, ARB_PARENT(head, elm, field),\ + field))) \ + elm = ARB_PARENT(head, elm, field); \ + else { \ + while (ARB_PARENT(head, elm, field) && \ + (elm == ARB_RIGHT(head, ARB_PARENT(head, \ + elm, field), field))) \ + elm = ARB_PARENT(head, elm, field); \ + elm = ARB_PARENT(head, elm, field); \ + } \ + } \ + return (elm); \ +} + +#define ARB_GENERATE_NEXT(name, type, field, attr) \ +attr struct type * \ +name##_ARB_NEXT(const struct name *head, const struct type *elm) \ +{ return (__DECONST(struct type *, name##_ARB_CNEXT(head, elm))); } + +#define ARB_GENERATE_CPREV(name, type, field, attr) \ +/* ARGSUSED */ \ +attr const struct type * \ +name##_ARB_CPREV(const struct name *head, const struct type *elm) \ +{ \ + if (ARB_LEFT(head, elm, field)) { \ + elm = ARB_LEFT(head, elm, field); \ + while (ARB_RIGHT(head, elm, field)) \ + elm = ARB_RIGHT(head, elm, field); \ + } else { \ + if (ARB_PARENT(head, elm, field) && \ + (elm == ARB_RIGHT(head, ARB_PARENT(head, elm, \ + field), field))) \ + elm = ARB_PARENT(head, elm, field); \ + else { \ + while (ARB_PARENT(head, elm, field) && \ + (elm == ARB_LEFT(head, ARB_PARENT(head, elm,\ + field), field))) \ + elm = ARB_PARENT(head, elm, field); \ + elm = ARB_PARENT(head, elm, field); \ + } \ + } \ + return (elm); \ +} + +#define ARB_GENERATE_PREV(name, type, field, attr) \ +attr struct type * \ +name##_ARB_PREV(const struct name *head, const struct type *elm) \ +{ return (__DECONST(struct type *, name##_ARB_CPREV(head, elm))); } + +#define ARB_GENERATE_CMINMAX(name, type, field, attr) \ +attr const struct type * \ +name##_ARB_CMINMAX(const struct name *head, int val) \ +{ \ + const struct type *tmp = ARB_EMPTY(head) ? NULL : ARB_ROOT(head);\ + const struct type *parent = NULL; \ + while (tmp) { \ + parent = tmp; \ + if (val < 0) \ + tmp = ARB_LEFT(head, tmp, field); \ + else \ + tmp = ARB_RIGHT(head, tmp, field); \ + } \ + return (__DECONST(struct type *, parent)); \ +} + +#define ARB_GENERATE_MINMAX(name, type, field, attr) \ +attr struct type * \ +name##_ARB_MINMAX(const struct name *head, int val) \ +{ return (__DECONST(struct type *, name##_ARB_CMINMAX(head, val))); } + +#define ARB_GENERATE_REBALANCE(name, type, field, cmp, attr) \ +attr struct type * \ +name##_ARB_REBALANCE(struct name *head, struct type *elm) \ +{ \ + struct type *cmpelm; \ + if (((cmpelm = ARB_PREV(name, head, elm)) != NULL && \ + (cmp)(cmpelm, elm) >= 0) || \ + ((cmpelm = ARB_NEXT(name, head, elm)) != NULL && \ + (cmp)(elm, cmpelm) >= 0)) { \ + /* XXXLAS: Remove/insert is heavy handed. */ \ + ARB_REMOVE(name, head, elm); \ + /* Remove puts elm on the free list. */ \ + elm = ARB_GETFREE(head, field); \ + return (ARB_INSERT(name, head, elm)); \ + } \ + return (NULL); \ +} \ + +#define ARB_INSERT(name, x, y) name##_ARB_INSERT(x, y) +#define ARB_REMOVE(name, x, y) name##_ARB_REMOVE(x, y) +#define ARB_CFIND(name, x, y) name##_ARB_CFIND(x, y) +#define ARB_FIND(name, x, y) name##_ARB_FIND(x, y) +#define ARB_CNFIND(name, x, y) name##_ARB_CNFIND(x, y) +#define ARB_NFIND(name, x, y) name##_ARB_NFIND(x, y) +#define ARB_CNEXT(name, x, y) name##_ARB_CNEXT(x, y) +#define ARB_NEXT(name, x, y) name##_ARB_NEXT(x, y) +#define ARB_CPREV(name, x, y) name##_ARB_CPREV(x, y) +#define ARB_PREV(name, x, y) name##_ARB_PREV(x, y) +#define ARB_CMIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \ + name##_ARB_CMINMAX(x, ARB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x))) +#define ARB_MIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \ + name##_ARB_MINMAX(x, ARB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x))) +#define ARB_CMAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \ + name##_ARB_CMINMAX(x, ARB_INF) : ARB_CNODE(x, ARB_MAXIDX(x))) +#define ARB_MAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \ + name##_ARB_MINMAX(x, ARB_INF) : ARB_NODE(x, ARB_MAXIDX(x))) +#define ARB_REBALANCE(name, x, y) name##_ARB_REBALANCE(x, y) + +#define ARB_FOREACH(x, name, head) \ + for ((x) = ARB_MIN(name, head); \ + (x) != NULL; \ + (x) = name##_ARB_NEXT(head, x)) + +#define ARB_FOREACH_FROM(x, name, y) \ + for ((x) = (y); \ + ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \ + (x) = (y)) + +#define ARB_FOREACH_SAFE(x, name, head, y) \ + for ((x) = ARB_MIN(name, head); \ + ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \ + (x) = (y)) + +#define ARB_FOREACH_REVERSE(x, name, head) \ + for ((x) = ARB_MAX(name, head); \ + (x) != NULL; \ + (x) = name##_ARB_PREV(x)) + +#define ARB_FOREACH_REVERSE_FROM(x, name, y) \ + for ((x) = (y); \ + ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \ + (x) = (y)) + +#define ARB_FOREACH_REVERSE_SAFE(x, name, head, y) \ + for ((x) = ARB_MAX(name, head); \ + ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \ + (x) = (y)) + +#define ARB_ARRFOREACH(x, field, head) \ + for ((x) = ARB_NODES(head); \ + ARB_SELFIDX(head, x) < ARB_MAXNODES(head); \ + (x)++) + +#define ARB_ARRFOREACH_REVWCOND(x, field, head, extracond) \ + for ((x) = ARB_NODES(head) + (ARB_MAXNODES(head) - 1); \ + (x) >= ARB_NODES(head) && (extracond); \ + (x)--) + +#define ARB_ARRFOREACH_REVERSE(x, field, head) \ + ARB_ARRFOREACH_REVWCOND(x, field, head, 1) + +#endif /* _SYS_ARB_H_ */ Property changes on: head/sys/sys/arb.h ___________________________________________________________________ Added: svn:keywords ## -0,0 +1 ## +FreeBSD=%H \ No newline at end of property Index: head/tests/sys/sys/Makefile =================================================================== --- head/tests/sys/sys/Makefile (revision 352336) +++ head/tests/sys/sys/Makefile (revision 352337) @@ -1,9 +1,9 @@ # $FreeBSD$ TESTSDIR= ${TESTSBASE}/sys/sys -ATF_TESTS_C= bitstring_test qmath_test rb_test splay_test +ATF_TESTS_C= arb_test bitstring_test qmath_test rb_test splay_test WARNS?= 5 .include Index: head/tests/sys/sys/arb_test.c =================================================================== --- head/tests/sys/sys/arb_test.c (nonexistent) +++ head/tests/sys/sys/arb_test.c (revision 352337) @@ -0,0 +1,115 @@ +/* $OpenBSD: rb-test.c,v 1.4 2008/04/13 00:22:17 djm Exp $ */ +/* + * Copyright 2019 Edward Tomasz Napierala + * Copyright 2002 Niels Provos + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * $FreeBSD$ + */ +#include + +#include +#include +#include + +#include + +struct node { + ARB32_ENTRY() next; + int key; +}; + +ARB32_HEAD(tree, node) *root; + +static int +compare(const struct node *a, const struct node *b) +{ + if (a->key < b->key) return (-1); + else if (a->key > b->key) return (1); + return (0); +} + +ARB_PROTOTYPE(tree, node, next, compare); + +ARB_GENERATE(tree, node, next, compare); + +#define ITER 150 +#define MIN 5 +#define MAX 5000 + +ATF_TC_WITHOUT_HEAD(arb_test); +ATF_TC_BODY(arb_test, tc) +{ + struct node *tmp, *ins; + int i, max, min; + + max = min = 42; /* pacify gcc */ + + root = (struct tree *)calloc(1, ARB_ALLOCSIZE(root, ITER, tmp)); + + ARB_INIT(tmp, next, root, ITER); + + for (i = 0; i < ITER; i++) { + tmp = ARB_GETFREE(root, next); + ATF_REQUIRE_MSG(tmp != NULL, "ARB_GETFREE failed"); + do { + tmp->key = arc4random_uniform(MAX-MIN); + tmp->key += MIN; + } while (ARB_FIND(tree, root, tmp) != NULL); + if (i == 0) + max = min = tmp->key; + else { + if (tmp->key > max) + max = tmp->key; + if (tmp->key < min) + min = tmp->key; + } + ATF_REQUIRE_EQ(NULL, ARB_INSERT(tree, root, tmp)); + } + + ins = ARB_MIN(tree, root); + ATF_REQUIRE_MSG(ins != NULL, "ARB_MIN error"); + ATF_CHECK_EQ(min, ins->key); + tmp = ins; + ins = ARB_MAX(tree, root); + ATF_REQUIRE_MSG(ins != NULL, "ARB_MAX error"); + ATF_CHECK_EQ(max, ins->key); + + ATF_CHECK_EQ(tmp, ARB_REMOVE(tree, root, tmp)); + + for (i = 0; i < ITER - 1; i++) { + tmp = ARB_ROOT(root); + ATF_REQUIRE_MSG(tmp != NULL, "ARB_ROOT error"); + ATF_CHECK_EQ(tmp, ARB_REMOVE(tree, root, tmp)); + } +} + +ATF_TP_ADD_TCS(tp) +{ + + ATF_TP_ADD_TC(tp, arb_test); + + return (atf_no_error()); +} Property changes on: head/tests/sys/sys/arb_test.c ___________________________________________________________________ Added: svn:keywords ## -0,0 +1 ## +FreeBSD=%H \ No newline at end of property