#ifndef _LINUX_AVLTREE_H
#define _LINUX_AVLTREE_H


#ifndef AVL_MAXHEIGHT
#define AVL_MAXHEIGHT 41
#endif
/* AVL_MAXHEIGHT is only used by the macros AVL_INSERT and AVL_REMOVE.
 * They use this value to determine the stack size that should be
 * allocated.  No where in the actual code is this value checked - there is
 * no overflow detection.  However, an AVL-Tree of height 41 is gaurenteed
 * to hold at least (approx) 700733725 items.
 *
 * Minimum capacity (approx) = (1.618 ^ (Height + 3)) / sqrt(5)
 */



/*
 * Types
 */

struct avl_node {
	struct avl_node *left, *right;
	unsigned char heightdiff;
};

/*
 * Function definitions
 */

void __avl_insert(struct avl_node *node, struct avl_node **stack[]
		  , int stackmax);
void __avl_remove(struct avl_node **stack[], int stackmax);

/*
 * Function Suite
 */

/* The following macros are templates for the main functions performed on a
 * binary tree.  These templates can be used directly (via comparison code
 * specified in the __Compare parameter), or they can be used as prototypes
 * for new code.  The templates implement a fairly straight-forward binary
 * search algorithm; if one is feeling lazy and isn't doing anything
 * complex, feel free to use the macros directly.
 *
 * To make use of the macros, the "__Compare" parameter should be filled
 * with code that interrogates the provided variable "AVLNode" and returns
 * a value greater than, less than, or equal to zero depending on whether
 * the left tree should be searched, the right tree searched, or if the
 * current node should be returned.
 * Note: The __Compare parameter should be substituted with _code_ that can
 * be inlined into the search.  See the example implementation at the end
 * of this file for more information.
 */



/*  SAMPLE IMPLEMENTATION:
 *
 * #include <avltree.h>
 * 
 * struct sample_data {
 * 	   int num;
 * 	   struct avl_node treenode;
 * };
 * 
 *  * Note the use of inline here.  Inline isn't required, but since the
 *  * comparison function is small reducing call instructions should improve
 *  * performance.
 * inline int
 * sample_compare(struct avl_node *x, int num)
 * {
 * 	   int nodenum = avl_entry(x, struct sample_data, treenode)->num;
 * 
 * 	   return (num < nodenum ? -1 : num > nodenum ? 1 : 0);
 * }
 * 
 * int
 * sample_insert(struct avl_node **tree, struct sample_data *node)
 * {
 * 	    * Note: The call to sample_compare is compiled into the inner loop
 * 	    * of the macro.  It is not evaluated locally!
 * 	   return AVL_INSERT(tree,&node->treenode
 * 			     , (sample_compare(AVLNode,node->num)) );
 * }
 * 
 * int
 * sample_remove(struct avl_node **tree, int num)
 * {
 * 	    * Note: The call to sample_compare is compiled into the inner loop
 * 	    * of the macro.  It is not evaluated locally!
 * 	   return AVL_REMOVE(tree, (sample_compare(AVLNode,num)) );
 * }
 * 
 * struct sample_data *
 * sample_find(struct avl_node *tree, int num)
 * {
 * 	    * Note: The call to sample_compare is compiled into the inner loop
 * 	    * of the macro.  It is not evaluated locally!
 * 	   tree = AVL_FIND(tree, (sample_compare(AVLNode,num)) );
 * 	   if (tree) {
 * 		   return avl_entry(tree, struct sample_data, treenode);
 * 	   }
 * 	   return NULL;
 * }
 */

#endif /* _LINUX_AVLTREE_H */