home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mitsch75.zip / scheme-7_5_17-src.zip / scheme-7.5.17 / src / microcode / avltree.c < prev    next >
C/C++ Source or Header  |  2001-03-08  |  6KB  |  239 lines
  1. /* -*-C-*-
  2.  
  3. $Id: avltree.c,v 1.5 2001/03/08 18:00:14 cph Exp $
  4.  
  5. Copyright (c) 1993-2001 Massachusetts Institute of Technology
  6.  
  7. This program is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 2 of the License, or (at
  10. your option) any later version.
  11.  
  12. This program is distributed in the hope that it will be useful, but
  13. WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15. General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program; if not, write to the Free Software
  19. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20. */
  21.  
  22. /* This file contains the code for a simple AVL tree library.
  23.    It is used by the MIT Scheme microcode to quickly map
  24.    names to indices into various tables.
  25.  */
  26.  
  27. #include "avltree.h"
  28.  
  29. extern int EXFUN (strcmp_ci, (CONST char * s1, CONST char * s2));
  30. extern PTR EXFUN (malloc, (unsigned long));
  31. extern void EXFUN (free, (PTR));
  32.  
  33. CONST char * tree_error_message = 0;
  34. CONST char * tree_error_noise = 0;
  35.  
  36. static void
  37. DEFUN (tree_error, (message, noise),
  38.        CONST char * message AND
  39.        CONST char * noise)
  40. {
  41.   tree_error_message = message;
  42.   tree_error_noise = noise;
  43. }
  44.  
  45. /* AVL trees.  o(log n) lookup, insert (and delete, not implemented here).
  46.    AVL condition: for every node
  47.      abs (height (node.left) - height (node.right)) < 2
  48.    This guarantees that the least-balanced AVL tree has Fibonacci-sized
  49.    branches, and therefore the height is at most the log base phi of the
  50.    number of nodes, where phi is the golden ratio.
  51.    With random insertion (or when created as below),
  52.    they are better, approaching log base 2.
  53.  
  54.    This version does not allow duplicate entries.  */   
  55.  
  56. #define BRANCH_HEIGHT(tree) (((tree) == 0) ? 0 : (tree)->height)
  57.  
  58. #ifndef MAX
  59. #  define MAX(a,b) (((a) >= (b)) ? (a) : (b))
  60. #endif
  61.  
  62. static void
  63. DEFUN (update_height, (tree), tree_node tree)
  64. {
  65.   tree->height = (1 + (MAX ((BRANCH_HEIGHT (tree->left)),
  66.                 (BRANCH_HEIGHT (tree->rite)))));
  67. }
  68.  
  69. static tree_node
  70. DEFUN (leaf_make, (name, value),
  71.        CONST char * name AND
  72.        unsigned long value)
  73. {
  74.   tree_node leaf = ((tree_node) (malloc (sizeof (struct tree_node_s))));
  75.   if (leaf == 0)
  76.     {
  77.       tree_error ("leaf_make: malloc failed.\n", 0);
  78.       return (leaf);
  79.     }
  80.   leaf->name = name;
  81.   leaf->value = value;
  82.   leaf->height = 1;
  83.   leaf->left = 0;
  84.   leaf->rite = 0;
  85.   return (leaf);
  86. }
  87.  
  88. static tree_node
  89. DEFUN (rotate_left, (tree), tree_node tree)
  90. {
  91.   tree_node rite = tree->rite;
  92.   tree_node beta = rite->left;
  93.   tree->rite = beta;
  94.   rite->left = tree;
  95.   update_height (tree);
  96.   update_height (rite);
  97.   return (rite);
  98. }
  99.  
  100. static tree_node
  101. DEFUN (rotate_rite, (tree), tree_node tree)
  102. {
  103.   tree_node left = tree->left;
  104.   tree_node beta = left->rite;
  105.   tree->left = beta;
  106.   left->rite = tree;
  107.   update_height (tree);
  108.   update_height (left);
  109.   return (left);
  110. }
  111.  
  112. static tree_node
  113. DEFUN (rebalance_left, (tree), tree_node tree)
  114. {
  115.   if ((1 + (BRANCH_HEIGHT (tree->rite))) >= (BRANCH_HEIGHT (tree->left)))
  116.     {
  117.       update_height (tree);
  118.       return (tree);
  119.     }
  120.   else
  121.     {
  122.       tree_node q = tree->left;
  123.       if ((BRANCH_HEIGHT (q->rite)) > (BRANCH_HEIGHT (q->left)))
  124.     tree->left = (rotate_left (q));
  125.       return (rotate_rite (tree));
  126.     }
  127. }
  128.  
  129. static tree_node
  130. DEFUN (rebalance_rite, (tree), tree_node tree)
  131. {
  132.   if ((1 + (BRANCH_HEIGHT (tree->left))) >= (BRANCH_HEIGHT (tree->rite)))
  133.     {
  134.       update_height (tree);
  135.       return (tree);
  136.     }
  137.   else
  138.     {
  139.       tree_node q = tree->rite;
  140.       if ((BRANCH_HEIGHT (q->left)) > (BRANCH_HEIGHT (q->rite)))
  141.     tree->rite = (rotate_rite (q));
  142.       return (rotate_left (tree));
  143.     }
  144. }
  145.  
  146. tree_node
  147. DEFUN (tree_insert, (tree, name, value),
  148.        tree_node tree AND
  149.        CONST char * name AND
  150.        unsigned long value)
  151. {
  152.   if (tree == 0)
  153.     return (leaf_make (name, value));
  154.   switch (strcmp_ci (name, tree->name))
  155.     {
  156.     case 0:
  157.       tree_error ("tree_insert: Duplicate entry %s.\n", name);
  158.       return (tree);
  159.       
  160.     case -1:
  161.       {
  162.     /* To the left */
  163.     tree->left = (tree_insert (tree->left, name, value));
  164.     return (rebalance_left (tree));
  165.       }
  166.  
  167.     case 1:
  168.       {
  169.     /* To the right */
  170.     tree->rite = (tree_insert (tree->rite, name, value));
  171.     return (rebalance_rite (tree));
  172.       }
  173.     }
  174.   /*NOTREACHED*/
  175.   return (0);
  176. }
  177.  
  178. tree_node
  179. DEFUN (tree_lookup, (tree, name), tree_node tree AND CONST char * name)
  180. {
  181.   while (tree != 0)
  182.     switch (strcmp_ci (name, tree->name))
  183.       {
  184.       case 0:
  185.     return (tree);
  186.  
  187.       case -1:
  188.     tree = tree->left;
  189.     break;
  190.  
  191.       case 1:
  192.     tree = tree->rite;
  193.     break;
  194.       }
  195.   return (tree);
  196. }
  197.  
  198. tree_node
  199. DEFUN (tree_build, (high, names, value),
  200.        unsigned long high AND
  201.        CONST char ** names AND
  202.        unsigned long value)
  203. {
  204.   static long bias = 0;
  205.   if (high > 1)
  206.     {
  207.       tree_node tree;
  208.       long middle = (high / 2);
  209.       long next;
  210.  
  211.       if ((high & 1) == 0)
  212.     {
  213.       middle -= bias;
  214.       bias = (1 - bias);
  215.     }
  216.       next = (middle + 1);
  217.       tree = (leaf_make (names[middle], (value + middle)));
  218.       tree->left = (tree_build (middle, names, value));
  219.       tree->rite = (tree_build ((high - next), &names[next], (value + next)));
  220.       update_height (tree);
  221.       return (tree);
  222.     }
  223.   else if (high == 1)
  224.     return (leaf_make (* names, value));
  225.   else
  226.     return (0);
  227. }
  228.  
  229. void
  230. DEFUN (tree_free, (tree), tree_node tree)
  231. {
  232.   if (tree != 0)
  233.     {
  234.       tree_free (tree->left);
  235.       tree_free (tree->rite);
  236.       free (tree);
  237.     }
  238. }
  239.