/**********************************************************************  avltree.c **********************************************************************  avltree - AVL tree implementation.  Copyright ?2000-2004, Stewart Adcock <stewart@linux-domain.com>  All rights reserved.  The latest version of this program should be available at:  http://gaul.sourceforge.net/  This program is free software; you can redistribute it and/or modify  it under the terms of the GNU General Public License as published by  the Free Software Foundation; either version 2 of the License, or  (at your option) any later version.  Alternatively, if your project  is incompatible with the GPL, I will probably agree to requests  for permission to use the terms of any other license.  This program is distributed in the hope that it will be useful, but  WITHOUT ANY WARRANTY WHATSOEVER.  A full copy of the GNU General Public License should be in the file  "COPYING" provided with this distribution; if not, see:  http://www.gnu.org/ **********************************************************************  Synopsis:	 AVL trees.		(Adel'son-Velskii and Landis Tree, or height-balanced		1-tree (!))  References:	Just about any datastructure text book. 		I have stubbs & webre (1985, Wadsworth Inc.) 		Much of this code comes from the GLIB gtree.c source. 		Differences to the Balanced Binary Tree code in GLIB:		  - degenerate keys are stored (I needed this - BUT NOT YET IMPLEMENTED)		  - opaque key generation (for usability)		  - primitive key comparison (for rapid comparisons)		  - traverse in order only (for small footprint)		  - no search function (a bit useless anyway)		  - additional avltree_lookup_{lowest|highest}() functions (Useful)		  - data returned after removing node (Useful - NULL means nothing removed)		  - avltree_destroy for cleaning+deleteing a tree (useful)                  - OpenMP code (shared memory parallelisation) 		By default the keys are unsigned longs, but this may		be overridden at compile time by defining the constant		AVLTREE_KEY_TYPE. 		This code should be thread safe.		For OpenMP code, USE_OPENMP must be defined and 		avltree_init_openmp() must be called prior to any other		function.		A basic test program may be compiled with something like:		gcc avltree.c -DAVLTREE_COMPILE_MAIN -g   To do:	rebuilding tree after changing key/hashing function. 		remove function return success flag. 		convert some recursive functions into iterative functions where sensible (e.g. avltree_node_count)		Use the memory_chunk allocators.  This should now be safe. **********************************************************************/#include "gaul/avltree.h"/* * Private node data structure. */typedef struct AVLNode_t  {  struct AVLNode_t *left;	/* Left subtree. */  struct AVLNode_t *right;	/* Right subtree. */  int		balance;	/* Height (left) - height (right). */  AVLKey	key;		/* The key for this node. */  vpointer	data;		/* Data stored at this node. */  } AVLNode;/* * Private function prototypes. */static AVLNode	*avltree_node_new(AVLKey key, vpointer data);static void	avltree_node_free(AVLNode *node);static void	avltree_node_delete(AVLNode *node);static AVLNode	*avltree_node_insert(AVLNode *node, AVLKey key,				     vpointer data, boolean *inserted);static AVLNode	*avltree_node_remove(AVLNode *node,                                     AVLKey key, vpointer *removed_data);static AVLNode	*avltree_node_balance(AVLNode *node);static AVLNode	*avltree_node_remove_leftmost(AVLNode *node,					     AVLNode **leftmost);static AVLNode	*avltree_node_restore_left_balance(AVLNode *node,						     int old_balance);static AVLNode	*avltree_node_restore_right_balance(AVLNode *node,						     int old_balance);static vpointer	avltree_node_lookup(AVLNode *node, AVLKey key);static int	avltree_node_count(AVLNode *node);static boolean	avltree_node_traverse(AVLNode *node,				AVLTraverseFunc traverse_func, vpointer userdata);static int	avltree_node_height(AVLNode *node);static AVLNode	*avltree_node_rotate_left(AVLNode *node);static AVLNode	*avltree_node_rotate_right(AVLNode *node);static void	avltree_node_check(AVLNode *node);/* * Compilation constants. */#define AVL_NODE_BUFFER_NUM_INCR	16#define AVL_NODE_BUFFER_SIZE		1024/* * Global variables. */static int		AVLnum_trees = 0;	/* Count number of trees in use. */static int		buffer_num = -1;static int		num_buffers = 0;static int		num_used = AVL_NODE_BUFFER_SIZE;static AVLNode		**node_buffers = NULL;static AVLNode		*node_free_list = NULL;/* * Note that a single coarse thread lock is used when a number of * less coarse locks might be better. */THREAD_LOCK_DEFINE_STATIC(avltree_node_buffer_lock);#if USE_OPENMP == 1static boolean avltree_openmp_initialised = FALSE;#endif/* * Private functions. *//* * Deallocate all memory associated with buffers.  Should * never be called outside of a "avltree_node_buffer_lock" * block. */static void _destroy_buffers(void)  {  while (buffer_num >= 0)    {    s_free(node_buffers[buffer_num]);    buffer_num--;    }  s_free(node_buffers);  node_buffers = NULL;  num_buffers = 0;  num_used = AVL_NODE_BUFFER_SIZE;  node_free_list = NULL;  return;  }static AVLNode *avltree_node_new(AVLKey key, vpointer data)  {  AVLNode *node;  THREAD_LOCK(avltree_node_buffer_lock);/* * Find an unused node.  Look for unused node in current buffer, then * in the free node list, then allocate new buffer. */  if (num_used < AVL_NODE_BUFFER_SIZE)    {    node = &(node_buffers[buffer_num][num_used]);    num_used++;    }  else    {    if (node_free_list!=NULL)      {      node = node_free_list;      node_free_list = node->right;      }    else      {      buffer_num++;      if (buffer_num == num_buffers)        {        num_buffers += AVL_NODE_BUFFER_NUM_INCR;        node_buffers = s_realloc(node_buffers, sizeof(AVLNode *)*num_buffers);        }      node_buffers[buffer_num] = s_malloc(sizeof(AVLNode)*AVL_NODE_BUFFER_SIZE);      node = node_buffers[buffer_num];      num_used = 1;      }    }  THREAD_UNLOCK(avltree_node_buffer_lock);  node->balance = 0;  node->left = NULL;  node->right = NULL;  node->key = key;  node->data = data;  return node;  }static void avltree_node_free(AVLNode *node)  {  THREAD_LOCK(avltree_node_buffer_lock);  node->right = node_free_list;  node_free_list = node;  THREAD_UNLOCK(avltree_node_buffer_lock);  return;  }static void avltree_node_delete(AVLNode *node)  {	    if (node!=NULL)    {    avltree_node_delete(node->right);    avltree_node_delete(node->left);    avltree_node_free(node);    }  return;  }/* * Actually, an iterative version would be preferable... */static void avltree_node_destroy(AVLNode *node, AVLDestructorFunc free_func)  {	    if (node!=NULL)    {    avltree_node_destroy(node->right, free_func);    avltree_node_destroy(node->left, free_func);    free_func(node->data);    avltree_node_free(node);    }  return;  }/* * Systematically search tree with a search function which has the * same ordering as the tree. * This iterative version is much faster than the equivalent recursive version. */static vpointer avltree_node_ordered_search(AVLNode *node,                     AVLSearchFunc search_func, vpointer userdata)  {  int dir;  while (node!=NULL)    {    dir = (*search_func)(node->data, userdata);    if (dir<0)      node=node->left;    else if (dir>0)      node=node->right;    else      return node->data;    }  return NULL;  }/* * Systematically search tree until AVLMatchFunc returns TRUE. * This can be fairly slow!  Don't say I didn't warn you. */static boolean avltree_node_search(AVLNode *node,                     AVLMatchFunc search_func, vpointer userdata, vpointer *node_data)  {  *node_data=node->data;  if ((*search_func)(*node_data, userdata)) return TRUE;  if (node->left!=NULL)    if (avltree_node_search(node->left, search_func, userdata, node_data))      return TRUE;  if (node->right!=NULL)    if (avltree_node_search(node->right, search_func, userdata, node_data))      return TRUE;  return FALSE;  }static AVLNode *avltree_node_insert(AVLNode *node,		    AVLKey key, vpointer data, boolean *inserted)  {  int old_balance;  if (!node)    {    *inserted = TRUE;    return avltree_node_new(key, data);    }  if (key < node->key)    {    if (node->left!=NULL)      {      old_balance = node->left->balance;      node->left = avltree_node_insert(node->left, key, data, inserted);      if ((old_balance != node->left->balance) && node->left->balance)        node->balance--;      }    else      {      *inserted = TRUE;      node->left = avltree_node_new(key, data);      node->balance--;      }    }  else if (key > node->key)    {    if (node->right!=NULL)      {      old_balance = node->right->balance;      node->right = avltree_node_insert(node->right, key, data, inserted);      if ((old_balance != node->right->balance) && node->right->balance)        node->balance++;      }    else      {      *inserted = TRUE;      node->right = avltree_node_new(key, data);      node->balance++;      }    }  else    {	/* key == node->key *//*    *inserted = FALSE; */    printf("WARNING: -- Replaced node -- (Key clash?)\n");    node->data = data;    return node;    }  if (*inserted!=FALSE && (node->balance < -1 || node->balance > 1))    node = avltree_node_balance(node);  return node;  }static AVLNode *avltree_node_remove(AVLNode *node,                            AVLKey key, vpointer *removed_data)  {  AVLNode	*new_root=NULL;  int		old_balance;  if (!node) return NULL;  if (key < node->key)    {    if (node->left!=NULL)      {      old_balance = node->left->balance;      node->left = avltree_node_remove(node->left, key, removed_data);      node = avltree_node_restore_left_balance(node, old_balance);      }    }  else if (key > node->key)    {    if (node->right!=NULL)      {      old_balance = node->right->balance;      node->right = avltree_node_remove(node->right, key, removed_data);      node = avltree_node_restore_right_balance(node, old_balance);      }    }  else if (key == node->key)    {    AVLNode *removed_node;    removed_node = node;    if (!node->right)      {      node = node->left;      }    else      {      old_balance = node->right->balance;      node->right = avltree_node_remove_leftmost(node->right, &new_root);      if (new_root==NULL) die("Internal error.  New root node is NULL.");      new_root->left = node->left;      new_root->right = node->right;      new_root->balance = node->balance;      node = avltree_node_restore_right_balance(new_root, old_balance);      }    *removed_data = removed_node->data;    avltree_node_free(removed_node);    }  return node;  }static AVLNode *avltree_node_balance(AVLNode *node)  {  if (node->balance < -1)    {    if (node->left->balance > 0)      node->left = avltree_node_rotate_left(node->left);    node = avltree_node_rotate_right(node);    }  else if (node->balance > 1)    {    if (node->right->balance < 0)      node->right = avltree_node_rotate_right(node->right);    node = avltree_node_rotate_left(node);    }  return node;  }static AVLNode *avltree_node_remove_leftmost(AVLNode  *node,			     AVLNode **leftmost)  {  int old_balance;  if (!node->left)    {    *leftmost = node;    return node->right;    }  old_balance = node->left->balance;  node->left = avltree_node_remove_leftmost(node->left, leftmost);  return avltree_node_restore_left_balance(node, old_balance);  }static AVLNode *avltree_node_lookup_leftmost(AVLNode *node)  {/* Recursive version:  if (!node->left) return node;  return avltree_node_lookup_leftmost(node->left); */  while (node->left!=NULL) node = node->left;  return node;  }static AVLNode *avltree_node_lookup_rightmost(AVLNode *node)  {/* Recursive version:  if (!node->right) return node;  return avltree_node_lookup_rightmost(node->right); */  while (node->right!=NULL) node = node->right;  return node;  }static AVLNode *avltree_node_restore_left_balance(AVLNode	*node,				  int		old_balance)  {  if ( (!node->left) || ((node->left->balance != old_balance) &&           (node->left->balance == 0)) )    {    node->balance++;    }  if (node->balance > 1) return avltree_node_balance(node);  return node;  }static AVLNode *avltree_node_restore_right_balance(AVLNode	*node,				   int		old_balance)  {  if ( (!node->right) || ((node->right->balance != old_balance) &&	   (node->right->balance == 0)) )    {    node->balance--;    }  if (node->balance < -1) return avltree_node_balance(node);  return node;  }#if 0/* Recursive version */static vpointer avltree_node_lookup(AVLNode *node, AVLKey key)  {  if (!node) return NULL;  if (key < node->key)    {    if (node->left) return avltree_node_lookup(node->left, key);    }  else if (key > node->key)    {