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 } 218