if (node->right) return avltree_node_lookup(node->right, key);    }  else    {	/* key == node->key */    return node->data;    }  return NULL;  }#endif/* * Iterative version -- much more efficient than the recursive version. */static vpointer avltree_node_lookup(AVLNode *node, AVLKey key)  {  while (node!=NULL && key!=node->key)    {    if (key < node->key)      node = node->left;    else      node = node->right;    }/* if (node) printf("Found key %p >", node->data); else printf("Not found key >");*/  return node;  }/* * Recursive node counting routine. * Need an iterative version. */static int avltree_node_count(AVLNode *node)  {  int count=1;  if (node->left!=NULL) count += avltree_node_count(node->left);  if (node->right!=NULL) count += avltree_node_count(node->right);  return count;  }/* * Stops when an AVLTraverseFunc() callback returns TRUE. */static boolean avltree_node_traverse(AVLNode *node,                     AVLTraverseFunc traverse_func, vpointer userdata)  {  if (node->left!=NULL)    {    if (avltree_node_traverse(node->left, traverse_func, userdata)) return TRUE;    }  if ((*traverse_func)(node->key, node->data, userdata)) return TRUE;  if (node->right!=NULL)    {    if (avltree_node_traverse(node->right, traverse_func, userdata)) return TRUE;    }  return FALSE;  }static int avltree_node_height(AVLNode *node)  {  int left_height;  int right_height;  if (!node) return 0;  if (node->left!=NULL)    left_height = avltree_node_height(node->left);  else    left_height = 0;  if (node->right!=NULL)    right_height = avltree_node_height(node->right);  else    right_height = 0;  return MAX(left_height, right_height) + 1;  }static AVLNode *avltree_node_rotate_left(AVLNode *node)  {  AVLNode *right;  int a_bal;  int b_bal;  right = node->right;  node->right = right->left;  right->left = node;  a_bal = node->balance;  b_bal = right->balance;  if (b_bal <= 0)    {    if (a_bal >= 1) right->balance = b_bal - 1;    else right->balance = a_bal + b_bal - 2;    node->balance = a_bal - 1;    }  else    {    if (a_bal <= b_bal) right->balance = a_bal - 2;    else right->balance = b_bal - 1;    node->balance = a_bal - b_bal - 1;    }  return right;  }static AVLNode *avltree_node_rotate_right(AVLNode *node)  {  AVLNode *left;  int a_bal;  int b_bal;  left = node->left;  node->left = left->right;  left->right = node;  a_bal = node->balance;  b_bal = left->balance;  if (b_bal <= 0)    {    if (b_bal > a_bal) left->balance = b_bal + 1;    else left->balance = a_bal + 2;    node->balance = a_bal - b_bal + 1;    }  else    {    if (a_bal <= -1) left->balance = b_bal + 1;    else left->balance = a_bal + b_bal + 2;    node->balance = a_bal + 1;    }  return left;  }static void avltree_node_check(AVLNode *node)  {  int left_height;  int right_height;  int balance;    if (node!=NULL)    {    if (node->left!=NULL)      left_height = avltree_node_height(node->left);    else      left_height = 0;    if (node->right!=NULL)      right_height = avltree_node_height(node->right);    else      right_height = 0;          balance = right_height - left_height;    if (balance != node->balance)      dief("avltree_node_check: failed: %d ( %d )", balance, node->balance);          if (node->left!=NULL)      avltree_node_check(node->left);    if (node->right!=NULL)      avltree_node_check(node->right);    }  return;  }/* * Public Interface: *//* * This function must be called before any other functions is OpenMP * code is to be used.  Can be safely called when OpenMP code is not * being used, and can be safely called more than once. */void avltree_init_openmp(void)  {#if USE_OPENMP == 1  if (avltree_openmp_initialised == FALSE)    {    omp_init_lock(&avltree_node_buffer_lock);    avltree_openmp_initialised = TRUE;    }#endif  return;  }AVLTree *avltree_new(AVLKeyFunc key_generate_func)  {  AVLTree *tree;  if (!key_generate_func) return NULL;  AVLnum_trees++;  tree = s_malloc(sizeof(AVLTree));  if (!tree) die("Unable to allocate memory.");  tree->root = NULL;  tree->key_generate_func = key_generate_func;  return tree;  }void avltree_delete(AVLTree *tree)  {  if (!tree) return;  avltree_node_delete(tree->root);  s_free(tree);  AVLnum_trees--;  THREAD_LOCK(avltree_node_buffer_lock);  if (AVLnum_trees == 0)    _destroy_buffers();  THREAD_UNLOCK(avltree_node_buffer_lock);  return;  }void avltree_destroy(AVLTree *tree, AVLDestructorFunc free_func)  {  if (!tree) return;  if (free_func!=NULL)    avltree_node_destroy(tree->root, free_func);  else    avltree_node_delete(tree->root);  s_free(tree);  AVLnum_trees--;  THREAD_LOCK(avltree_node_buffer_lock);  if (AVLnum_trees == 0)    _destroy_buffers();  THREAD_UNLOCK(avltree_node_buffer_lock);  return;  }boolean avltree_insert(AVLTree *tree, vpointer data)  {  boolean	inserted=FALSE;  if (!tree) return FALSE;  if (!data) return FALSE;	/* ordered search would barf at this! */  tree->root = avltree_node_insert(tree->root,                    tree->key_generate_func(data), data, &inserted);  return inserted;  }vpointer avltree_remove(AVLTree *tree, vpointer data)  {  vpointer removed=NULL;  if (!tree || !tree->root) return NULL;  tree->root = avltree_node_remove(tree->root, tree->key_generate_func(data), &removed);  return removed;  }vpointer avltree_remove_key(AVLTree *tree, AVLKey key)  {  vpointer removed=NULL;  if (!tree || !tree->root) return NULL;  tree->root = avltree_node_remove(tree->root, key, &removed);  return removed;  }vpointer avltree_lookup(AVLTree *tree, vpointer data)  {  AVLNode	*node;  if (!tree || !tree->root) return NULL;  node = avltree_node_lookup(tree->root, tree->key_generate_func(data));  return node?node->data:NULL;  }vpointer avltree_lookup_key(AVLTree *tree, AVLKey key)  {  AVLNode	*node;  if (!tree || !tree->root) return NULL;  node = avltree_node_lookup(tree->root, key);  return node?node->data:NULL;  }vpointer avltree_lookup_lowest(AVLTree *tree)  {  AVLNode	*node;  if (!tree || !tree->root) return NULL;  node = avltree_node_lookup_leftmost(tree->root);  return node?node->data:NULL;  }vpointer avltree_lookup_highest(AVLTree *tree)  {  AVLNode	*node;  if (!tree || !tree->root) return NULL;  node = avltree_node_lookup_rightmost(tree->root);  return node?node->data:NULL;  }vpointer avltree_ordered_search(AVLTree *tree,                    AVLSearchFunc search_func, vpointer userdata)  {  if (!tree || !tree->root) return NULL;  return avltree_node_ordered_search(tree->root, search_func, userdata);  }vpointer avltree_search(AVLTree *tree, AVLMatchFunc search_func, vpointer userdata)  {  vpointer	nodedata=NULL;  if (!tree || !tree->root) return NULL;  return avltree_node_search(tree->root, search_func, userdata, &nodedata)?nodedata:NULL;  }void avltree_traverse(AVLTree *tree, AVLTraverseFunc traverse_func, vpointer userdata)  {  if (!tree || !tree->root) return;  avltree_node_traverse(tree->root, traverse_func, userdata);  return;  }int avltree_height(AVLTree *tree)  {  return (tree!=NULL && tree->root!=NULL)?avltree_node_height(tree->root):0;  }int avltree_num_nodes(AVLTree *tree)  {  return (tree!=NULL && tree->root!=NULL)?avltree_node_count(tree->root):0;  }/* * Testing: */void avltree_diagnostics(void)  {  printf("=== AVLTree diagnostics ======================================\n");  printf("Version:                   %s\n", GA_VERSION_STRING);  printf("Build date:                %s\n", GA_BUILD_DATE_STRING);  printf("Compilation machine characteristics:\n%s\n", GA_UNAME_STRING);  printf("--------------------------------------------------------------\n");  printf("structure                  sizeof\n");  printf("AVLTree                    %lu\n", (unsigned long) sizeof(AVLTree));  printf("AVLNode                    %lu\n", (unsigned long) sizeof(AVLNode));  printf("--------------------------------------------------------------\n");  printf("Trees in use:              %d\n", AVLnum_trees);  printf("==============================================================\n");  return;  }static boolean failed = FALSE;static AVLKey test_avltree_generate(constvpointer data)  {/* * Simple casting from char to AVLKey... should work ;) * (It works when AVLKey is the default unsigned long...) */  return (AVLKey) *((char *)data);/*  return (AVLKey) (data);*/  }static boolean test_avltree_traverse(AVLKey key, vpointer data, vpointer userdata)  {/* check. */  if (key != test_avltree_generate(data))    {    printf("failure (%ld %ld) ", key, test_avltree_generate(data));    failed=TRUE;    }/* output character. */  printf("%c ", *((char *)data));/*  printf("%c=%ld ", *((char *)data), (long) test_avltree_generate(data));*//* terminate traversal if userdata is non-NULL and character is 'S'. */  if ((boolean *)userdata!=NULL && *((char *)data)=='S')    {    printf("%s ", (char *)userdata);    return TRUE;    }  return FALSE;  }#ifdef AVLTREE_COMPILE_MAINint main(int argc, char **argv)#elseboolean avltree_test(void)#endif  {  int		i, j;  AVLTree	*tree;  char		chars[62];  char		chx='x', chX='X', *ch;  printf("Testing my dodgy AVL tree routines.\n");  tree = avltree_new(test_avltree_generate);  i = 0;  for (j = 0; j < 26; j++, i++)    {    chars[i] = 'A' + (char) j;    avltree_insert(tree, &chars[i]);    }  for (j = 0; j < 26; j++, i++)    {    chars[i] = 'a' + (char) j;    avltree_insert(tree, &chars[i]);    }  for (j = 0; j < 10; j++, i++)    {    chars[i] = '0' + (char) j;    avltree_insert(tree, &chars[i]);    }  printf("height: %d\n", avltree_height(tree));  printf("num nodes: %d\n", avltree_num_nodes(tree));  printf("tree: ");  avltree_traverse(tree, test_avltree_traverse, NULL);  printf("\n");  printf("tree to 'S' then foo: ");  avltree_traverse(tree, test_avltree_traverse, "foo");  printf("\n");  for (i = 0; i < 26; i++)    if ( !avltree_remove(tree, &chars[i]) ) printf("%c not found.\n", chars[i]);  printf("height: %d\n", avltree_height(tree));  printf("num nodes: %d\n", avltree_num_nodes(tree));  printf("tree: ");  avltree_traverse(tree, test_avltree_traverse, NULL);  printf("\n");  printf("Lookup for 'x': ");  ch = (char *) avltree_lookup(tree, (vpointer) &chx);  if (ch) printf("Found '%c'\n", *ch); else printf("Not found.\n");  printf("Lookup for 'X': ");  ch = (char *) avltree_lookup(tree, (vpointer) &chX);  if (ch) printf("Found '%c'\n", *ch); else printf("Not found.\n");  printf("Tests:         %s\n", failed?"FAILED":"PASSED");  avltree_delete(tree);  return failed;  }