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 *
find_id(id_rec * tree,char * id)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
insert_id(id_rec ** root,id_rec * new_id)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