bug-gnu-utils
[Top][All Lists]
Advanced

[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;



reply via email to

[Prev in Thread] Current Thread [Next in Thread]