usr.bin/menuc/avl.c

   1 /*      $NetBSD: avl.c,v 1.7 2005/02/11 06:21:22 simonb Exp $   */
   2
   3 /*
   4  * Copyright (c) 1997 Philip A. Nelson.
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. All advertising materials mentioning features or use of this software
  16  *    must display the following acknowledgement:
  17  *      This product includes software developed by Philip A. Nelson.
  18  * 4. The name of Philip A. Nelson may not be used to endorse or promote
  19  *    products derived from this software without specific prior written
  20  *    permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY PHILIP NELSON ``AS IS'' AND ANY EXPRESS OR
  23  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  24  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  25  * IN NO EVENT SHALL PHILIP NELSON BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  27  * NOT LIMITED TO,  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  * DATA, OR PROFITS;  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  * THEORY OF LIABILITY,  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  31  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 /* avl.c: Routines for manipulation an avl tree.
  35  *
  36  * an include file should define the following minimum struct.:
  37  * (Comments must be made into real comments.)
  38  *
  39  *      typedef struct id_rec {
  40  *              / * The balanced binary tree fields. * /
  41  *              char  *id;      / * The name. * /
  42  *              short balance;  / * For the balanced tree. * /
  43  *              struct id_rec *left, *right; / * Tree pointers. * /
  44  *
  45  *              / * Other information fields. * /
  46  *      } id_rec;
  47  */
  48
  49 #if HAVE_NBTOOL_CONFIG_H
  50 #include "nbtool_config.h"
  51 #endif
  52
  53 #include <sys/cdefs.h>
  54
  55 #if defined(__RCSID) && !defined(lint)
  56 __RCSID("$NetBSD: avl.c,v 1.7 2005/02/11 06:21:22 simonb Exp $");
  57 #endif
  58
  59
  60 #include <string.h>
  61
  62 #include "defs.h"
  63
  64 /*  find_id returns a pointer to node in TREE that has the correct
  65     ID.  If there is no node in TREE with ID, NULL is returned. */
  66
  67 id_rec *
  68   find_id (id_rec *tree, char *id)
  69 {
  70   int cmp_result;
  71
  72   /* Check for an empty tree. */
  73   if (tree == NULL)
  74     return NULL;
  75
  76   /* Recursively search the tree. */
  77   cmp_result = strcmp (id, tree->id);
  78   if (cmp_result == 0)
  79     return tree;  /* This is the item. */
  80   else if (cmp_result < 0)
  81     return find_id (tree->left, id);
  82   else
  83     return find_id (tree->right, id);
  84 }
  85
  86
  87 /* insert_id inserts a NEW_ID rec into the tree whose ROOT is
  88    provided.  insert_id returns TRUE if the tree height from
  89    ROOT down is increased otherwise it returns FALSE.  This is a
  90    recursive balanced binary tree insertion algorithm. */
  91
  92 int insert_id (id_rec **root, id_rec *new_id)
  93 {
  94   id_rec *A, *B;
  95
  96   /* If root is NULL, this where it is to be inserted. */
  97   if (*root == NULL)
  98     {
  99       *root = new_id;
 100       new_id->left = NULL;
 101       new_id->right = NULL;
 102       new_id->balance = 0;
 103       return (TRUE);
 104     }
 105
 106   /* We need to search for a leaf. */
 107   if (strcmp (new_id->id, (*root)->id) < 0)
 108     {
 109       /* Insert it on the left. */
 110       if (insert_id (&((*root)->left), new_id))
 111         {
 112           /* The height increased. */
 113           (*root)->balance--;
 114
 115           switch ((*root)->balance)
 116             {
 117             case  0:  /* no height increase. */
 118               return (FALSE);
 119             case -1:  /* height increase. */
 120               return (TRUE);
 121             case -2:  /* we need to do a rebalancing act. */
 122               A = *root;
 123               B = (*root)->left;
 124               if (B->balance <= 0)
 125                 {
 126                   /* Single Rotate. */
 127                   A->left = B->right;
 128                   B->right = A;
 129                   *root = B;
 130                   A->balance = 0;
 131                   B->balance = 0;
 132                 }
 133               else
 134                 {
 135                   /* Double Rotate. */
 136                   *root = B->right;
 137                   B->right = (*root)->left;
 138                   A->left = (*root)->right;
 139                   (*root)->left = B;
 140                   (*root)->right = A;
 141                   switch ((*root)->balance)
 142                     {
 143                     case -1:
 144                       A->balance = 1;
 145                       B->balance = 0;
 146                       break;
 147                     case  0:
 148                       A->balance = 0;
 149                       B->balance = 0;
 150                       break;
 151                     case  1:
 152                       A->balance = 0;
 153                       B->balance = -1;
 154                       break;
 155                     }
 156                   (*root)->balance = 0;
 157                 }
 158             }
 159         }
 160     }
 161   else
 162     {
 163       /* Insert it on the right. */
 164       if (insert_id (&((*root)->right), new_id))
 165         {
 166           /* The height increased. */
 167           (*root)->balance++;
 168           switch ((*root)->balance)
 169             {
 170             case 0:  /* no height increase. */
 171               return (FALSE);
 172             case 1:  /* height increase. */
 173               return (TRUE);
 174             case 2:  /* we need to do a rebalancing act. */
 175               A = *root;
 176               B = (*root)->right;
 177               if (B->balance >= 0)
 178                 {
 179                   /* Single Rotate. */
 180                   A->right = B->left;
 181                   B->left = A;
 182                   *root = B;
 183                   A->balance = 0;
 184                   B->balance = 0;
 185                 }
 186               else
 187                 {
 188                   /* Double Rotate. */
 189                   *root = B->left;
 190                   B->left = (*root)->right;
 191                   A->right = (*root)->left;
 192                   (*root)->left = A;
 193                   (*root)->right = B;
 194                   switch ((*root)->balance)
 195                     {
 196                     case -1:
 197                       A->balance = 0;
 198                       B->balance = 1;
 199                       break;
 200                     case  0:
 201                       A->balance = 0;
 202                       B->balance = 0;
 203                       break;
 204                     case  1:
 205                       A->balance = -1;
 206                       B->balance = 0;
 207                       break;
 208                     }
 209                   (*root)->balance = 0;
 210                 }
 211             }
 212         }
 213     }
 214
 215   /* If we fall through to here, the tree did not grow in height. */
 216   return (FALSE);
 217 }