]>
git.wh0rd.org - fontconfig.git/blob - src/fcavl.c
4 * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
6 * Permission to use, copy, modify, distribute, and sell this software and its
7 * documentation for any purpose is hereby granted without fee, provided that
8 * the above copyright notice appear in all copies and that both that
9 * copyright notice and this permission notice appear in supporting
10 * documentation, and that the name of Keith Packard not be used in
11 * advertising or publicity pertaining to distribution of the software without
12 * specific, written prior permission. Keith Packard makes no
13 * representations about the suitability of this software for any purpose. It
14 * is provided "as is" without express or implied warranty.
16 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
18 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
19 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
20 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
21 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
22 * PERFORMANCE OF THIS SOFTWARE.
26 * Semi-Balanced trees (avl). This only contains two
27 * routines - insert and delete. Searching is
28 * reserved for the client to write.
35 FcAvlRebalanceRight (FcAvlNode
**);
38 FcAvlRebalanceLeft (FcAvlNode
**);
43 * this routine returns FcTrue if the tree has grown
48 FcAvlInsert (FcAvlMore more
, FcAvlNode
**treep
, FcAvlNode
*new)
60 if ((*more
) (new, *treep
))
62 if (FcAvlInsert (more
, &(*treep
)->right
, new))
63 switch (++(*treep
)->balance
) {
69 (void) FcAvlRebalanceRight (treep
);
74 if (FcAvlInsert (more
, &(*treep
)->left
, new))
75 switch (--(*treep
)->balance
) {
81 (void) FcAvlRebalanceLeft (treep
);
89 * delete a node from a tree
91 * this routine return FcTrue if the tree has been shortened
95 FcAvlDelete (FcAvlMore more
, FcAvlNode
**treep
, FcAvlNode
*old
)
98 return FcFalse
; /* node not found */
101 FcAvlNode
*replacement
;
102 FcAvlNode
*replacement_parent
;
103 int replacement_direction
;
104 int delete_direction
;
105 FcAvlNode
*swap_temp
;
109 * find an empty down pointer (if any)
110 * and rehook the tree
113 (*treep
) = old
->left
;
115 } else if (!old
->left
) {
116 (*treep
) = old
->right
;
120 * if both down pointers are full, then
121 * move a node from the bottom of the tree up here.
123 * This builds an incorrect tree -- the replacement
124 * node and the old node will not
125 * be in correct order. This doesn't matter as
126 * the old node will obviously not leave
127 * this routine alive.
130 * if the tree is left heavy, then go left
133 replacement_parent
= old
;
134 if (old
->balance
== -1) {
135 delete_direction
= -1;
136 replacement_direction
= -1;
137 replacement
= old
->left
;
138 while (replacement
->right
) {
139 replacement_parent
= replacement
;
140 replacement_direction
= 1;
141 replacement
= replacement
->right
;
144 delete_direction
= 1;
145 replacement_direction
= 1;
146 replacement
= old
->right
;
147 while (replacement
->left
) {
148 replacement_parent
= replacement
;
149 replacement_direction
= -1;
150 replacement
= replacement
->left
;
154 * swap the replacement node into
155 * the tree where the node is to be removed
157 * this would be faster if only the data
158 * element was swapped -- but that
159 * won't work for kalypso. The alternate
161 data_temp = old->data;
162 to _be_deleted->data = replacement->data;
163 replacement->data = data_temp;
165 swap_temp
= old
->left
;
166 old
->left
= replacement
->left
;
167 replacement
->left
= swap_temp
;
169 swap_temp
= old
->right
;
170 old
->right
= replacement
->right
;
171 replacement
->right
= swap_temp
;
173 balance_temp
= old
->balance
;
174 old
->balance
= replacement
->balance
;
175 replacement
->balance
= balance_temp
;
177 * if the replacement node is directly below
178 * the to-be-removed node, hook the old
179 * node below it (instead of below itself!)
181 if (replacement_parent
== old
)
182 replacement_parent
= replacement
;
183 if (replacement_direction
== -1)
184 replacement_parent
->left
= old
;
186 replacement_parent
->right
= old
;
187 (*treep
) = replacement
;
189 * delete the node from the sub-tree
191 if (delete_direction
== -1)
193 if (FcAvlDelete (more
, &(*treep
)->left
, old
))
195 switch (++(*treep
)->balance
) {
208 if (FcAvlDelete (more
, &(*treep
)->right
, old
))
210 switch (--(*treep
)->balance
) {
223 else if ((*more
) (old
, *treep
))
225 if (FcAvlDelete (more
, &(*treep
)->right
, old
))
228 * check the balance factors
229 * Note that the conditions are
230 * inverted from the insertion case
232 switch (--(*treep
)->balance
) {
238 return FcAvlRebalanceLeft (treep
);
245 if (FcAvlDelete (more
, &(*treep
)->left
, old
))
247 switch (++(*treep
)->balance
) {
253 return FcAvlRebalanceRight (treep
);
262 * two routines to rebalance the tree.
264 * rebalance_right -- the right sub-tree is too long
265 * rebalance_left -- the left sub-tree is too long
267 * These routines are the heart of avl trees, I've tried
268 * to make their operation reasonably clear with comments,
269 * but some study will be necessary to understand the
272 * these routines return FcTrue if the resultant
273 * tree is shorter than the un-balanced version. This
274 * is only of interest to the delete routine as the
275 * balance after insertion can never actually shorten
280 FcAvlRebalanceRight (FcAvlNode
**treep
)
286 if ((*treep
)->right
->balance
== -1) {
288 * double whammy -- the inner sub-sub tree
289 * is longer than the outer sub-sub tree
291 * this is the "double rotation" from
292 * knuth. Scheme: replace the tree top node
293 * with the inner sub-tree top node and
294 * adjust the maze of pointers and balance
295 * factors accordingly.
297 temp
= (*treep
)->right
->left
;
298 (*treep
)->right
->left
= temp
->right
;
299 temp
->right
= (*treep
)->right
;
300 switch (temp
->balance
) {
302 temp
->right
->balance
= 1;
303 (*treep
)->balance
= 0;
306 temp
->right
->balance
= 0;
307 (*treep
)->balance
= 0;
310 temp
->right
->balance
= 0;
311 (*treep
)->balance
= -1;
315 (*treep
)->right
= temp
->left
;
316 temp
->left
= (*treep
);
321 * a simple single rotation
323 * Scheme: replace the tree top node
324 * with the sub-tree top node
326 temp
= (*treep
)->right
->left
;
327 (*treep
)->right
->left
= (*treep
);
328 (*treep
) = (*treep
)->right
;
329 (*treep
)->left
->right
= temp
;
331 * only two possible configurations --
332 * if the right sub-tree was balanced, then
333 * *both* sides of it were longer than the
334 * left side, so the resultant tree will
335 * have a long leg (the left inner leg being
336 * the same length as the right leg)
338 if ((*treep
)->balance
== 0) {
339 (*treep
)->balance
= -1;
340 (*treep
)->left
->balance
= 1;
343 (*treep
)->balance
= 0;
344 (*treep
)->left
->balance
= 0;
351 FcAvlRebalanceLeft (FcAvlNode
**treep
)
357 if ((*treep
)->left
->balance
== 1) {
359 * double whammy -- the inner sub-sub tree
360 * is longer than the outer sub-sub tree
362 * this is the "double rotation" from
363 * knuth. Scheme: replace the tree top node
364 * with the inner sub-tree top node and
365 * adjust the maze of pointers and balance
366 * factors accordingly.
368 temp
= (*treep
)->left
->right
;
369 (*treep
)->left
->right
= temp
->left
;
370 temp
->left
= (*treep
)->left
;
371 switch (temp
->balance
) {
373 temp
->left
->balance
= -1;
374 (*treep
)->balance
= 0;
377 temp
->left
->balance
= 0;
378 (*treep
)->balance
= 0;
381 temp
->left
->balance
= 0;
382 (*treep
)->balance
= 1;
386 (*treep
)->left
= temp
->right
;
387 temp
->right
= (*treep
);
392 * a simple single rotation
394 * Scheme: replace the tree top node
395 * with the sub-tree top node
397 temp
= (*treep
)->left
->right
;
398 (*treep
)->left
->right
= (*treep
);
399 (*treep
) = (*treep
)->left
;
400 (*treep
)->right
->left
= temp
;
402 * only two possible configurations --
403 * if the left sub-tree was balanced, then
404 * *both* sides of it were longer than the
405 * right side, so the resultant tree will
406 * have a long leg (the right inner leg being
407 * the same length as the left leg)
409 if ((*treep
)->balance
== 0) {
410 (*treep
)->balance
= 1;
411 (*treep
)->right
->balance
= -1;
414 (*treep
)->balance
= 0;
415 (*treep
)->right
->balance
= 0;