Mercurial > emacs
changeset 3490:07b454ddc666
(copy_intervals): Don't adjust total_length at the end.
Set lengths of subintervals properly.
(balance_intervals): Balance left as well as right.
| author | Richard M. Stallman <rms@gnu.org> |
|---|---|
| date | Sat, 05 Jun 1993 07:57:32 +0000 |
| parents | 5c2b4797aab2 |
| children | a211389a145f |
| files | src/intervals.c |
| diffstat | 1 files changed, 25 insertions(+), 19 deletions(-) [+] |
line wrap: on
line diff
--- a/src/intervals.c Sat Jun 05 07:56:46 1993 +0000 +++ b/src/intervals.c Sat Jun 05 07:57:32 1993 +0000 @@ -1555,23 +1555,30 @@ register int threshold = (XFASTINT (interval_balance_threshold) * (total_children_size / 100)); - if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i) - && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold) - return rotate_right (i); + /* Balance within each side. */ + balance_intervals (i->left); + balance_intervals (i->right); if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i) && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold) - return rotate_right (i); + { + i = rotate_right (i); + /* If that made it unbalanced the other way, take it back. */ + if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i) + && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > threshold) + return rotate_left (i); + return i; + } -#if 0 - if (LEFT_TOTAL_LENGTH (i) > - (RIGHT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold))) - return rotate_right (i); - - if (RIGHT_TOTAL_LENGTH (i) > - (LEFT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold))) - return rotate_left (i); -#endif + if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i) + && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > threshold) + { + i = rotate_left (i); + if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i) + && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold) + return rotate_right (i); + return i; + } return i; } @@ -1608,7 +1615,7 @@ int start, length; { register INTERVAL i, new, t; - register int got; + register int got, prevlen; if (NULL_INTERVAL_P (tree) || length <= 0) return NULL_INTERVAL; @@ -1629,17 +1636,16 @@ copy_properties (i, new); t = new; + prevlen = got; while (got < length) { i = next_interval (i); - t = split_interval_right (t, got + 1); + t = split_interval_right (t, prevlen + 1); copy_properties (i, t); - got += LENGTH (i); + prevlen = LENGTH (i); + got += prevlen; } - if (got > length) - t->total_length -= (got - length); - return balance_intervals (new); }