File Manager

003 File Manager

Current Path: /usr/include/sys

📁 ..
📄 _atomic64e.h(2.91 KB)
📄 _atomic_subword.h(7.27 KB)
📄 _bitset.h(2.3 KB)
📄 _blockcount.h(1.97 KB)
📄 _bus_dma.h(2.15 KB)
📄 _callout.h(2.68 KB)
📄 _cpuset.h(1.76 KB)
📄 _cscan_atomic.h(18.1 KB)
📄 _cscan_bus.h(10.22 KB)
📄 _domainset.h(2.04 KB)
📄 _eventhandler.h(2.81 KB)
📄 _ffcounter.h(1.84 KB)
📄 _iovec.h(1.93 KB)
📄 _lock.h(2.98 KB)
📄 _lockmgr.h(1.82 KB)
📄 _mutex.h(2.63 KB)
📄 _null.h(1.7 KB)
📄 _pctrie.h(1.65 KB)
📄 _pthreadtypes.h(3.51 KB)
📄 _rangeset.h(1.86 KB)
📄 _rmlock.h(2.59 KB)
📄 _rwlock.h(2.39 KB)
📄 _semaphore.h(2.05 KB)
📄 _seqc.h(160 B)
📄 _sigset.h(2.46 KB)
📄 _smr.h(1.94 KB)
📄 _sockaddr_storage.h(2.37 KB)
📄 _stack.h(1.53 KB)
📄 _stdarg.h(2.15 KB)
📄 _stdint.h(2.6 KB)
📄 _sx.h(1.73 KB)
📄 _task.h(2.62 KB)
📄 _termios.h(7.64 KB)
📄 _timespec.h(2 KB)
📄 _timeval.h(1.88 KB)
📄 _types.h(5.66 KB)
📄 _ucontext.h(2.08 KB)
📄 _uio.h(1.99 KB)
📄 _umtx.h(2.5 KB)
📄 _unrhdr.h(1.92 KB)
📄 _winsize.h(2.14 KB)
📄 aac_ioctl.h(7.56 KB)
📄 abi_compat.h(2.42 KB)
📄 acct.h(4.95 KB)
📄 acl.h(14.62 KB)
📄 agpio.h(5.78 KB)
📄 aio.h(7.69 KB)
📄 alq.h(4.5 KB)
📄 apm.h(88 B)
📄 arb.h(28.88 KB)
📄 assym.h(2.7 KB)
📄 ata.h(45.35 KB)
📄 atomic_common.h(3.26 KB)
📄 auxv.h(1.58 KB)
📄 backlight.h(2.02 KB)
📄 bio.h(6.77 KB)
📄 bitset.h(8.53 KB)
📄 bitstring.h(12.16 KB)
📄 blist.h(3.74 KB)
📄 blockcount.h(3.03 KB)
📄 boot.h(1.8 KB)
📄 buf.h(20.73 KB)
📄 buf_ring.h(10.6 KB)
📄 bufobj.h(5.03 KB)
📄 bus.h(38.2 KB)
📄 bus_dma.h(13.68 KB)
📄 bus_dma_internal.h(2.42 KB)
📄 busdma_bufalloc.h(4.7 KB)
📄 callout.h(6.62 KB)
📄 caprights.h(4.17 KB)
📄 capsicum.h(17.54 KB)
📄 cdefs.h(27.79 KB)
📄 cdio.h(7.09 KB)
📄 cdrio.h(4.88 KB)
📄 cfictl.h(2.21 KB)
📄 chio.h(9.53 KB)
📄 ck.h(251 B)
📄 clock.h(8.07 KB)
📄 cnv.h(4.25 KB)
📄 compressor.h(2.05 KB)
📄 condvar.h(3.42 KB)
📄 conf.h(12.4 KB)
📄 cons.h(5.22 KB)
📄 consio.h(14.01 KB)
📄 copyright.h(1.97 KB)
📄 counter.h(3.02 KB)
📄 coverage.h(2.36 KB)
📄 cpu.h(7.02 KB)
📄 cpuctl.h(2.29 KB)
📄 cpuset.h(5.93 KB)
📄 csan.h(1.71 KB)
📄 ctf.h(14.4 KB)
📄 ctf_api.h(9.43 KB)
📄 ctype.h(2.81 KB)
📄 devctl.h(1.76 KB)
📄 devicestat.h(6.97 KB)
📄 devmap.h(4.04 KB)
📄 dirent.h(4.78 KB)
📁 disk
📄 disk.h(6.31 KB)
📄 disk_zone.h(6.52 KB)
📄 disklabel.h(4.39 KB)
📄 diskmbr.h(1.84 KB)
📄 dkstat.h(2.05 KB)
📄 dnv.h(3.39 KB)
📄 domain.h(3.64 KB)
📄 domainset.h(5.05 KB)
📄 dtrace.h(104.98 KB)
📄 dtrace_bsd.h(6.93 KB)
📄 dvdio.h(3.43 KB)
📄 efi.h(6.21 KB)
📄 efiio.h(2.06 KB)
📄 elf.h(1.6 KB)
📄 elf32.h(7.46 KB)
📄 elf64.h(7.79 KB)
📄 elf_common.h(59.51 KB)
📄 elf_generic.h(2.83 KB)
📄 endian.h(4.98 KB)
📄 epoch.h(4.01 KB)
📄 errno.h(8.29 KB)
📄 eui64.h(2.05 KB)
📄 event.h(12.61 KB)
📄 eventfd.h(1.86 KB)
📄 eventhandler.h(11.8 KB)
📄 eventvar.h(2.46 KB)
📄 exec.h(4.56 KB)
📄 extattr.h(4.08 KB)
📄 fail.h(13.1 KB)
📄 fbio.h(19.95 KB)
📄 fcntl.h(12.02 KB)
📄 fdcio.h(7.6 KB)
📄 file.h(14.06 KB)
📄 filedesc.h(12.13 KB)
📄 filio.h(3.67 KB)
📄 firmware.h(3.11 KB)
📄 fnv_hash.h(1.41 KB)
📄 font.h(3.85 KB)
📄 gmon.h(7.16 KB)
📄 gpio.h(9.85 KB)
📄 gpt.h(1.51 KB)
📄 gsb_crc32.h(998 B)
📄 gtaskqueue.h(4.21 KB)
📄 hash.h(3.55 KB)
📄 hhook.h(5.86 KB)
📄 iconv.h(8.22 KB)
📄 imgact.h(5.22 KB)
📄 imgact_aout.h(5.65 KB)
📄 imgact_binmisc.h(6.95 KB)
📄 imgact_elf.h(4.13 KB)
📄 interrupt.h(8.07 KB)
📄 intr.h(5.36 KB)
📄 ioccom.h(3.82 KB)
📄 ioctl.h(2.24 KB)
📄 ioctl_compat.h(6.42 KB)
📄 iov.h(11.67 KB)
📄 iov_schema.h(2.33 KB)
📄 ipc.h(4.93 KB)
📄 ipmi.h(5.4 KB)
📄 jail.h(14.98 KB)
📄 joystick.h(2.12 KB)
📄 kbio.h(7.81 KB)
📄 kcov.h(2.36 KB)
📄 kdb.h(5.04 KB)
📄 kenv.h(2.02 KB)
📄 kern_prefetch.h(1.67 KB)
📄 kernel.h(16.18 KB)
📄 kerneldump.h(4.85 KB)
📄 khelp.h(3.08 KB)
📄 kobj.h(6.92 KB)
📄 kpilite.h(2.01 KB)
📄 ksem.h(2.34 KB)
📄 kthread.h(3.04 KB)
📄 ktls.h(6.52 KB)
📄 ktr.h(10.92 KB)
📄 ktr_class.h(3.8 KB)
📄 ktrace.h(8.13 KB)
📄 libkern.h(7.74 KB)
📄 limits.h(3.69 KB)
📄 link_aout.h(10.2 KB)
📄 link_elf.h(4.06 KB)
📄 linker.h(11.88 KB)
📄 linker_set.h(3.85 KB)
📄 lock.h(12.24 KB)
📄 lock_profile.h(2.6 KB)
📄 lockf.h(5.55 KB)
📄 lockmgr.h(7 KB)
📄 lockstat.h(5.13 KB)
📄 loginclass.h(2.08 KB)
📄 mac.h(3.96 KB)
📄 malloc.h(11.76 KB)
📄 mbuf.h(50.74 KB)
📄 mchain.h(4.21 KB)
📄 md4.h(1.63 KB)
📄 md5.h(1.81 KB)
📄 mdioctl.h(3.73 KB)
📄 memdesc.h(3.79 KB)
📄 memrange.h(2.36 KB)
📄 mman.h(10.41 KB)
📄 module.h(8.77 KB)
📄 module_khelp.h(3.45 KB)
📄 mount.h(42.05 KB)
📄 mouse.h(12.69 KB)
📄 mpt_ioctl.h(4.27 KB)
📄 mqueue.h(1.86 KB)
📄 msg.h(4.78 KB)
📄 msgbuf.h(3.49 KB)
📄 mtio.h(11.94 KB)
📄 mutex.h(19.18 KB)
📄 namei.h(11.27 KB)
📄 nlist_aout.h(4.23 KB)
📄 nv.h(10.62 KB)
📄 nvpair.h(14.77 KB)
📄 osd.h(4.02 KB)
📄 param.h(12.23 KB)
📄 pciio.h(5.67 KB)
📄 pcpu.h(9.79 KB)
📄 pctrie.h(5.19 KB)
📄 physmem.h(2.92 KB)
📄 pidctrl.h(5.44 KB)
📄 pipe.h(4.63 KB)
📄 pmc.h(37.29 KB)
📄 pmckern.h(8.01 KB)
📄 pmclog.h(9.23 KB)
📄 poll.h(4.03 KB)
📄 posix4.h(3.71 KB)
📄 power.h(2.34 KB)
📄 priority.h(4.39 KB)
📄 priv.h(19.73 KB)
📄 prng.h(354 B)
📄 proc.h(50.73 KB)
📄 procctl.h(4.89 KB)
📄 procdesc.h(4.46 KB)
📄 procfs.h(4.2 KB)
📄 protosw.h(14.56 KB)
📄 ptio.h(1.57 KB)
📄 ptrace.h(8.61 KB)
📄 qmath.h(22.07 KB)
📄 queue.h(28.61 KB)
📄 racct.h(7.48 KB)
📄 random.h(5.41 KB)
📄 rangelock.h(3.86 KB)
📄 rangeset.h(2.96 KB)
📄 rctl.h(5.91 KB)
📄 reboot.h(3.41 KB)
📄 refcount.h(5.72 KB)
📄 regression.h(1.62 KB)
📄 resource.h(5.32 KB)
📄 resourcevar.h(6.33 KB)
📄 rman.h(6.41 KB)
📄 rmlock.h(5.56 KB)
📄 rtprio.h(3.08 KB)
📄 runq.h(2.54 KB)
📄 rwlock.h(10.61 KB)
📄 sbuf.h(4.68 KB)
📄 sched.h(9.06 KB)
📄 sdt.h(17.89 KB)
📄 select.h(3.5 KB)
📄 selinfo.h(2.39 KB)
📄 sem.h(4.31 KB)
📄 sema.h(2.61 KB)
📄 seqc.h(3.26 KB)
📄 serial.h(3.49 KB)
📄 sf_buf.h(5.87 KB)
📄 sglist.h(3.89 KB)
📄 shm.h(5.69 KB)
📄 sigio.h(2.83 KB)
📄 signal.h(15.83 KB)
📄 signalvar.h(12.95 KB)
📄 sleepqueue.h(5.61 KB)
📄 slicer.h(2.19 KB)
📄 smp.h(8.88 KB)
📄 smr.h(7.64 KB)
📄 smr_types.h(4.87 KB)
📄 snoop.h(1014 B)
📄 sockbuf.h(9.9 KB)
📄 socket.h(23.43 KB)
📄 socketvar.h(18.75 KB)
📄 sockio.h(7.97 KB)
📄 sockopt.h(2.98 KB)
📄 soundcard.h(69.38 KB)
📄 specialfd.h(1.56 KB)
📄 spigenio.h(2.28 KB)
📄 stack.h(2.65 KB)
📄 stat.h(13.44 KB)
📄 stats.h(34.73 KB)
📄 statvfs.h(3.08 KB)
📄 stdatomic.h(13.94 KB)
📄 stddef.h(1.7 KB)
📄 stdint.h(2.63 KB)
📄 sx.h(11.04 KB)
📄 syscall.h(13.99 KB)
📄 syscallsubr.h(16.94 KB)
📄 sysctl.h(47.96 KB)
📄 sysent.h(10.82 KB)
📄 syslimits.h(3.14 KB)
📄 syslog.h(7.25 KB)
📄 sysproto.h(153.38 KB)
📄 systm.h(21.97 KB)
📄 taskqueue.h(7.65 KB)
📄 terminal.h(8.25 KB)
📄 termios.h(151 B)
📄 thr.h(2.87 KB)
📄 tiio.h(12.62 KB)
📄 tim_filter.h(4.61 KB)
📄 time.h(16.87 KB)
📄 timeb.h(2.59 KB)
📄 timeet.h(3.65 KB)
📄 timeffc.h(11.94 KB)
📄 timepps.h(6.48 KB)
📄 timers.h(3.56 KB)
📄 times.h(2.46 KB)
📄 timespec.h(2.4 KB)
📄 timetc.h(3.16 KB)
📄 timex.h(6.61 KB)
📄 tree.h(27.93 KB)
📄 tslog.h(2.3 KB)
📄 tty.h(8.98 KB)
📄 ttycom.h(6.48 KB)
📄 ttydefaults.h(3.92 KB)
📄 ttydevsw.h(5.28 KB)
📄 ttydisc.h(2.93 KB)
📄 ttyhook.h(3.98 KB)
📄 ttyqueue.h(5.26 KB)
📄 turnstile.h(4.83 KB)
📄 types.h(11.64 KB)
📄 ucontext.h(2.91 KB)
📄 ucred.h(5.4 KB)
📄 uio.h(4.15 KB)
📄 umtx.h(5.94 KB)
📄 un.h(2.96 KB)
📄 unistd.h(7.34 KB)
📄 unpcb.h(6.77 KB)
📄 user.h(21.58 KB)
📄 utsname.h(2.47 KB)
📄 uuid.h(3.17 KB)
📄 vdso.h(4.26 KB)
📄 vmem.h(4.91 KB)
📄 vmmeter.h(7.72 KB)
📄 vnode.h(40.87 KB)
📄 vtoc.h(89 B)
📄 wait.h(6.11 KB)
📄 watchdog.h(4.22 KB)

Editing: arb.h

/*-
 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
 *
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 * Copyright 2018-2019 Netflix, Inc.
 * 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.
 *
 * $FreeBSD$
 */

#ifndef	_SYS_ARB_H_
#define	_SYS_ARB_H_

#include <sys/cdefs.h>

/* 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_REINSERT(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_REINSERT(name, type, attr)			\
	attr struct type *name##_ARB_REINSERT(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_REINSERT(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_REINSERT(name, type, field, cmp, attr)		\
attr struct type *							\
name##_ARB_REINSERT(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_REINSERT(name, x, y) name##_ARB_REINSERT(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)

#define	ARB_RESET_TREE(head, name, maxn)				\
	*(head) = ARB_INITIALIZER(name, maxn)

#endif	/* _SYS_ARB_H_ */

003 File Manager

Editing: arb.h

Upload File

Create Folder