#include "utils.h"
#include "u_tree.h"

/* height - returns the height of the given node */
int height(NodeEntry n)
  {
  if (n == NULL)
    return(-1);
  else
    return(n->height);
  }

static int Max( int right_side, int left_side )
  {
  return( left_side > right_side ? left_side : right_side );
  }


/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */

static NodeEntry single_rotate_with_left( NodeEntry K2 )
  {
  NodeEntry K1;

  if ((K2 == NULL) ||
      (K2->left == NULL))
    return(K2);
  
  K1 = K2->left;
  K2->left = K1->right;
  K1->right = K2;
  
  K2->height = Max(height(K2->left), height(K2->right)) + 1;
  K1->height = Max(height(K1->left), height(K1->right)) + 1;
  
  return K1;  /* New root */
  }

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */

static NodeEntry single_rotate_with_right( NodeEntry K1 )
  {
  NodeEntry K2;
  
  K2 = K1->right;
  K1->right = K2->left;
  K2->left = K1;
  
  K1->height = Max(height(K1->left), height(K1->right)) + 1;
  K2->height = Max(height(K2->left), height(K2->right)) + 1;
  
  return K2;  /* New root */
  }

/* This function can be called only if K3 has a left */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */

static NodeEntry double_rotate_with_left( NodeEntry K3 )
  {
  /* Rotate between K1 and K2 */
  K3->left = single_rotate_with_right( K3->left );
  
  /* Rotate between K3 and K2 */
  return single_rotate_with_left( K3 );
  }

/* This function can be called only if K1 has a right */
/* child and K1's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */

static NodeEntry double_rotate_with_right( NodeEntry K1 )
  {
  /* Rotate between K3 and K2 */
  K1->right = single_rotate_with_left( K1->right );
  
  /* Rotate between K1 and K2 */
  return single_rotate_with_right( K1 );
  }

AvlTree AVL_insert( u_long key, uint16_t port, struct pbsnode *node, AvlTree tree )
  {
	if (tree == NULL)
    {
    /* Create and return a node */
    if ((tree = ( AvlTree )calloc(1, sizeof( struct AvlNode ) )) == NULL)
      {
      return( tree );
      }

	  tree->key = key;
	  tree->port = port;
	  tree->pbsnode = node;
	  tree->left = NULL;
	  tree->right = NULL;
	  tree->height = 0;
	  }


	/* If key is less than current node value go left else go right.
		 If equal compare port and go left or right accordingly */
	if (key < tree->key)
		{
		tree->left = AVL_insert( key, port, node, tree->left );
		if (height(tree->left) - height(tree->right) >= 2 )
			{
			if (key <= tree->left->key )
				tree = single_rotate_with_left( tree );
			else
				tree = double_rotate_with_left( tree );
			}
		}
	else if (key > tree->key )
		{
		tree->right = AVL_insert( key, port, node, tree->right );
		if (height(tree->right) - height(tree->left) >= 2 )
		  {
		  if (key >= tree->right->key)
        tree = single_rotate_with_right( tree );
		  
		  else
        tree = double_rotate_with_right( tree );
      }
    }
	else
		{
    /* if it is in the tree, do not add it again */
    if (port == tree->port)
      return(tree);

		/* the keys are equal. sort by port */
		if (port != 0)
			{
			if (port < tree->port)
			  {
			  tree->left = AVL_insert( key, port, node, tree->left );
			  if (height(tree->left) - height(tree->right) >= 2)
			  	{
			  	if (port <= tree->left->port)
			  		tree = single_rotate_with_left( tree );
			  	else
			  		tree = double_rotate_with_left( tree );
			  	}
			  }
			else if (port > tree->port )
			  {
			  tree->right = AVL_insert( key, port, node, tree->right );
			  if (height(tree->right) - height(tree->left) >= 2)
			  	{
			  	if (port >= tree->right->port)
			  		tree = single_rotate_with_right( tree );
			  	else
			  		tree = double_rotate_with_right( tree );
			  	}
			  }
      }
		}


	tree->height = Max(height(tree->left), height(tree->right)) + 1;

	return(tree);
  } /* End AVL_insert */

/* return a pbsnode with the corresponding key and port */
struct pbsnode *AVL_find(
    
  u_long   key,
  uint16_t port,
  AvlTree  tree)

  {
	if (tree == NULL)
		{
		return( NULL );
		}

	if (key < tree->key)
		return( AVL_find( key, port, tree->left ));
	else if ( key > tree->key )
		return( AVL_find( key, port, tree->right ));
	else
		{
		if (port < tree->port)
			return( AVL_find( key, port, tree->left ) );
		else if ( port > tree->port )
			return( AVL_find( key, port, tree->right ));
		}

		return( tree->pbsnode );
  } /* end AVL_find */

/* If the key and port are found return 1 otherwise return 0 */
int AVL_is_in_tree(u_long key, uint16_t port, AvlTree tree)
  {
  AvlTree current = tree;

  while (current != NULL)
    {
    if (key < current->key)
      current = current->left;
    else if (key > current->key)
      current = current->right;
    else
      {
      if (port < current->port)
        current = current->left;
      else if(port > current->port)
        current = current->right;
      else
        return(1);
      }
    }
  return(0);
  } /* end AVL_is_in_tree */




int AVL_is_in_tree_no_port_compare(

  u_long   key,
  uint16_t port,
  AvlTree  tree)

  {
  if (tree == NULL)
    return(0);

  if (key < tree->key)
    return(AVL_is_in_tree_no_port_compare(key,port,tree->left));
  else if (key > tree->key)
    return(AVL_is_in_tree_no_port_compare(key,port,tree->right));
  else
    return(1);
  } /* END AVL_is_in_tree_no_port_compare() */




uint16_t AVL_get_port_by_ipaddr(
    
  u_long key,
  AvlTree tree)

  {
  if (tree == NULL)
    return(0);

  if (key < tree->key)
    return(AVL_get_port_by_ipaddr(key,tree->left));
  else if (key > tree->key)
    return(AVL_get_port_by_ipaddr(key,tree->right));
  else
    return(tree->port);
  } /* END AVL_get_port_by_ipaddr() */





AvlTree AVL_delete_node( 

  u_long   key, 
  uint16_t port, 
  AvlTree  tree)

  {
  AvlTree	h1 = NULL;
  AvlTree 	h2 = NULL;

  if (tree == NULL)
    return(NULL);

  if (key < tree->key)
    {
    if (tree->left)
      {
      h1 = AVL_delete_node(key, port, tree->left);
      tree->left = h1;
      }
    return(tree);
    }
  else if (key > tree->key)
    {
    if (tree->right)
      {
      h1 = AVL_delete_node(key, port, tree->right);
      tree->right = h1;
      }
    return(tree);
    }
  else if ( key == tree->key )
    {
    /* we found the key. Now find the port */
    if (port < tree->port)
      {
      if (tree->left)
        {
        h1 = AVL_delete_node(key, port, tree->left);
        tree->left = h1;
        }
      return(tree);
      }
    else if (port > tree->port)
      {
      if (tree->right)
        {
        h1 = AVL_delete_node(key, port, tree->right);
        tree->right = h1;
        }
      return(tree);
      }
    else if (port == tree->port)
      {
      
      /* We found our node. Delete it */
      if (tree->right == NULL && tree->left == NULL)
        {
        free(tree);
        return(NULL);
        }
      else if (tree->right == NULL)
        {
        h1 = tree->left;
        free(tree);
        return(h1);
        }
      else if (tree->left == NULL)
        {
        h1 = tree->right;
        free(tree);
        return(h1);
        }
      else
        {
        /* If right node has no children it replaces the deleted node
         * Otherwise get the right nodes left most decendent and 
         * promote it to the deleted node */
        h1 = tree->right;
        if (h1->left == NULL)
          {
          h1->left = tree->left;
          return(h1);
          }
        
        /* Find the left most node of this branch */
        while (h1->left != NULL)
          {
          h2 = h1;
          h1 = h1->left;
          }
        
        /* Promote leftmost node to the deleted node */
        h1->right = tree->right;
        h1->left = tree->left;
        h2->left = NULL;
        free(tree);
        return(h1);
        }
      }
    }
  return(tree);
  } /*  End delete_node */


int AVL_list_add_item(

  AvlTree   tree,
  char    **r_buf,
  long     *current_len,
  long     *max_len)

  {
  char    *tmp_buf = NULL;
  char    *current_buffer = NULL;
  int     add_len = 0;
	char    tmp_line[32];
 
	/* each entry can be a maximum of 21 bytes plus one for
	   NULL termination and one for a ','. We need at least 23 bytes to make
	   this work. (entry format XXX.XXX.XXX.XXX:XXXXX --
	   This does not work for IPV6 )*/
	if ((*max_len - *current_len) < 23)
    {
    *max_len = *max_len + 1024;
    tmp_buf = (char *)calloc(1, *max_len + 1);
    if (tmp_buf == NULL)
      return PBSE_MEM_MALLOC;
    if(*r_buf != NULL)
      {
      memcpy(tmp_buf, *r_buf, *current_len);
      free(*r_buf);
      }
    *r_buf = tmp_buf;
    }
  current_buffer = *r_buf;

	sprintf( tmp_line, "%ld.%ld.%ld.%ld:%d",
	  (tree->key & 0xFF000000) >> 24,
    (tree->key & 0x00FF0000) >> 16,
    (tree->key & 0x0000FF00) >> 8,
    (tree->key & 0x000000FF),
    tree->port);

  add_len = strlen(tmp_line);
	/* r_buf must come in with at least the first byte set to NULL
	   initially. Every time after that append
	   a comma */
	if (current_buffer[0] == 0)
	  {
		strcpy(current_buffer, tmp_line);
    *current_len = *current_len + add_len;
	  }
	else
	  {
	  strcat(current_buffer, ",");
	  strcat(current_buffer, tmp_line);
    *current_len = *current_len + add_len + 1;
	  }
  return PBSE_NONE;
  }

/* AVL_list -- return the key and port values for
 * each entry in the tree in a ',' delimited list
 * returned in Buf 
 * @param T - root of the tree to list 
 * @param Buf - output buffer 
 * @param BufSize - size of the output buffer 
 * return PBSE_NONE on success 
 * return PBSE_MEM_MALLOC if malloc failed 
 * return PBSE_RMNOPARAM if parameters are invalid.
 */ 
int AVL_list( AvlTree tree, char **Buf, long *current_len, long *max_len )
  {
	int rc = PBSE_NONE;

	if (Buf == NULL || current_len == NULL || max_len == NULL)
    {
    return PBSE_RMNOPARAM;
    }

	/* start down the left side */
	if ( tree->left != NULL )
    {
		if ((rc = AVL_list(tree->left, Buf, current_len, max_len)) != PBSE_NONE)
      return rc;
    }

  if ((rc = AVL_list_add_item(tree, Buf, current_len, max_len)) != PBSE_NONE)
    return rc;

	/* now go right */
	if ( tree->right != NULL )
    {
    if ((rc = AVL_list(tree->right, Buf, current_len, max_len)) != PBSE_NONE)
      return rc;
    }

	return PBSE_NONE;
  } /* end AVL_list */

