Support custom build directories and move includes

One of the neat tricks an autoconf style project is capable of
is allow configurion/building in a directory other than the
source directory.  The major advantage to this is that you can
build the project various different ways while making changes
in a single source tree.

For example, this project is designed to work on various different
Linux distributions each of which work slightly differently.  This
means that changes need to verified on each of those supported
distributions perferably before the change is committed to the
public git repo.

Using nfs and custom build directories makes this much easier.
I now have a single source tree in nfs mounted on several different
systems each running a supported distribution.  When I make a
change to the source base I suspect may break things I can
concurrently build from the same source on all the systems each
in their own subdirectory.

wget -c http://github.com/downloads/behlendorf/zfs/zfs-x.y.z.tar.gz
tar -xzf zfs-x.y.z.tar.gz
cd zfs-x-y-z

------------------------- run concurrently ----------------------
<ubuntu system>  <fedora system>  <debian system>  <rhel6 system>
mkdir ubuntu     mkdir fedora     mkdir debian     mkdir rhel6
cd ubuntu        cd fedora        cd debian        cd rhel6
../configure     ../configure     ../configure     ../configure
make             make             make             make
make check       make check       make check       make check

This change also moves many of the include headers from individual
incude/sys directories under the modules directory in to a single
top level include directory.  This has the advantage of making
the build rules cleaner and logically it makes a bit more sense.

1 files changed, 164 insertions, 0 deletions

diff --git a/include/sys/avl_impl.h b/include/sys/avl_impl.h
new file mode 100644
index 000000000..fddf76906
--- /dev/null
+++ b/include/sys/avl_impl.h
@@ -0,0 +1,164 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License, Version 1.0 only
+ * (the "License").  You may not use this file except in compliance
+ * with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#ifndef	_AVL_IMPL_H
+#define	_AVL_IMPL_H
+
+
+
+/*
+ * This is a private header file.  Applications should not directly include
+ * this file.
+ */
+
+#include <sys/types.h>
+
+#ifdef	__cplusplus
+extern "C" {
+#endif
+
+
+/*
+ * generic AVL tree implementation for kernel use
+ *
+ * There are 5 pieces of information stored for each node in an AVL tree
+ *
+ * 	pointer to less than child
+ * 	pointer to greater than child
+ * 	a pointer to the parent of this node
+ *	an indication  [0/1]  of which child I am of my parent
+ * 	a "balance" (-1, 0, +1)  indicating which child tree is taller
+ *
+ * Since they only need 3 bits, the last two fields are packed into the
+ * bottom bits of the parent pointer on 64 bit machines to save on space.
+ */
+
+#ifndef _LP64
+
+struct avl_node {
+	struct avl_node *avl_child[2];	/* left/right children */
+	struct avl_node *avl_parent;	/* this node's parent */
+	unsigned short avl_child_index;	/* my index in parent's avl_child[] */
+	short avl_balance;		/* balance value: -1, 0, +1 */
+};
+
+#define	AVL_XPARENT(n)		((n)->avl_parent)
+#define	AVL_SETPARENT(n, p)	((n)->avl_parent = (p))
+
+#define	AVL_XCHILD(n)		((n)->avl_child_index)
+#define	AVL_SETCHILD(n, c)	((n)->avl_child_index = (unsigned short)(c))
+
+#define	AVL_XBALANCE(n)		((n)->avl_balance)
+#define	AVL_SETBALANCE(n, b)	((n)->avl_balance = (short)(b))
+
+#else /* _LP64 */
+
+/*
+ * for 64 bit machines, avl_pcb contains parent pointer, balance and child_index
+ * values packed in the following manner:
+ *
+ * |63                                  3|        2        |1          0 |
+ * |-------------------------------------|-----------------|-------------|
+ * |      avl_parent hi order bits       | avl_child_index | avl_balance |
+ * |                                     |                 |     + 1     |
+ * |-------------------------------------|-----------------|-------------|
+ *
+ */
+struct avl_node {
+	struct avl_node *avl_child[2];	/* left/right children nodes */
+	uintptr_t avl_pcb;		/* parent, child_index, balance */
+};
+
+/*
+ * macros to extract/set fields in avl_pcb
+ *
+ * pointer to the parent of the current node is the high order bits
+ */
+#define	AVL_XPARENT(n)		((struct avl_node *)((n)->avl_pcb & ~7))
+#define	AVL_SETPARENT(n, p)						\
+	((n)->avl_pcb = (((n)->avl_pcb & 7) | (uintptr_t)(p)))
+
+/*
+ * index of this node in its parent's avl_child[]: bit #2
+ */
+#define	AVL_XCHILD(n)		(((n)->avl_pcb >> 2) & 1)
+#define	AVL_SETCHILD(n, c)						\
+	((n)->avl_pcb = (uintptr_t)(((n)->avl_pcb & ~4) | ((c) << 2)))
+
+/*
+ * balance indication for a node, lowest 2 bits. A valid balance is
+ * -1, 0, or +1, and is encoded by adding 1 to the value to get the
+ * unsigned values of 0, 1, 2.
+ */
+#define	AVL_XBALANCE(n)		((int)(((n)->avl_pcb & 3) - 1))
+#define	AVL_SETBALANCE(n, b)						\
+	((n)->avl_pcb = (uintptr_t)((((n)->avl_pcb & ~3) | ((b) + 1))))
+
+#endif /* _LP64 */
+
+
+
+/*
+ * switch between a node and data pointer for a given tree
+ * the value of "o" is tree->avl_offset
+ */
+#define	AVL_NODE2DATA(n, o)	((void *)((uintptr_t)(n) - (o)))
+#define	AVL_DATA2NODE(d, o)	((struct avl_node *)((uintptr_t)(d) + (o)))
+
+
+
+/*
+ * macros used to create/access an avl_index_t
+ */
+#define	AVL_INDEX2NODE(x)	((avl_node_t *)((x) & ~1))
+#define	AVL_INDEX2CHILD(x)	((x) & 1)
+#define	AVL_MKINDEX(n, c)	((avl_index_t)(n) | (c))
+
+
+/*
+ * The tree structure. The fields avl_root, avl_compar, and avl_offset come
+ * first since they are needed for avl_find().  We want them to fit into
+ * a single 64 byte cache line to make avl_find() as fast as possible.
+ */
+struct avl_tree {
+	struct avl_node *avl_root;	/* root node in tree */
+	int (*avl_compar)(const void *, const void *);
+	size_t avl_offset;		/* offsetof(type, avl_link_t field) */
+	ulong_t avl_numnodes;		/* number of nodes in the tree */
+	size_t avl_size;		/* sizeof user type struct */
+};
+
+
+/*
+ * This will only by used via AVL_NEXT() or AVL_PREV()
+ */
+extern void *avl_walk(struct avl_tree *, void *, int);
+
+#ifdef	__cplusplus
+}
+#endif
+
+#endif	/* _AVL_IMPL_H */