/*
@author Rohit Gupta
*/
#ifndef	_LINUX_AVLTREE_H
#define	_LINUX_AVLTREE_H

#include <linux/kernel.h>
#include <linux/stddef.h>

struct avl_node
{
  int balf;  //Balance Factor
  struct avl_node *avl_left;
  struct avl_node *avl_right;
  struct avl_node *avl_parent;
};

struct avl_root
{
  struct avl_node *avl_node;
};


#define AVL_ROOT (struct avl_root) {NULL, }
#define	avl_entry(ptr, type, member) container_of(ptr, type, member)
#define AVL_EMPTY_ROOT(root)	((root)->avl_node == NULL)
#define AVL_EMPTY_NODE(node)	(((node)->avl_parent) == node)


/*Inserts node in avl tree*/
extern void insert_avl_node(struct avl_node*,struct avl_root *);

/*Deletes node form avl tree*/
extern void delete_avl_node(struct avl_node*,struct avl_root*);

/* Find logical next and previous nodes in a tree */
extern struct avl_node *avl_next(struct avl_node *);
extern struct avl_node *avl_prev(struct avl_node *);
extern struct avl_node *avl_first(struct avl_root *);
extern struct avl_node *avl_last(struct avl_root *);

static inline void avl_link_node(struct avl_node * node, struct avl_node * parent,struct avl_node ** avl_link)
{
  node->avl_parent = parent;
  node->avl_left = node->avl_right = NULL;
  node->balf = 0;
  *avl_link = node;
}

#endif /* _LINUX_AVLTREE_H */