[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bc name_tree gets too high
From: |
Golubev I. N. |
Subject: |
bc name_tree gets too high |
Date: |
Sat, 26 Jan 2002 16:10:43 (GMT) |
Version: 1.03 - 1.06
It happens when monotonously increasing identifiers are fed into `bc',
like
a
b
c
...
name_tree height increases too fast, so `insert_id_rec' calls take too
much time and create too long call stacks.
bc/util.c(insert_id_rec): According to comment, notify caller about
tree height increase when balance becomes +-1. Fixes unnecessary
(possibly linear rather than logarithmic) tree height growth.
--- util.c 2002/01/26 15:41:15 1.1
+++ util.c 2002/01/26 15:46:10 1.2
@@ -423,7 +423,7 @@
case 0: /* no height increase. */
return (FALSE);
case -1: /* height increase. */
- return (FALSE);
+ return (TRUE);
case -2: /* we need to do a rebalancing act. */
A = *root;
B = (*root)->left;
@@ -476,7 +476,7 @@
case 0: /* no height increase. */
return (FALSE);
case 1: /* height increase. */
- return (FALSE);
+ return (TRUE);
case 2: /* we need to do a rebalancing act. */
A = *root;
B = (*root)->right;
- bc name_tree gets too high,
Golubev I. N. <=