diff options
| -rw-r--r-- | src/H5TB.c | 11 | ||||
| -rw-r--r-- | src/H5TBprivate.h | 7 |
2 files changed, 13 insertions, 5 deletions
@@ -1575,15 +1575,17 @@ H5TB_swapkid(H5TB_NODE ** root, H5TB_NODE * ptr, int side) static herr_t H5TB_balance(H5TB_NODE ** root, H5TB_NODE * ptr, int side, int added) { + H5TB_leaf olcnt, orcnt; /* Old left & right counts for node */ + H5TB_flag odouble; /* Old 'double' status */ int deeper = added; /* 1 if sub-tree got longer; -1 if got shorter */ int odelta; - int obal; FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5TB_balance); while (NULL != ptr) { - odelta = Delta(ptr, side); /* delta before the node was added */ - obal = UnBal(ptr); + olcnt = LeftCnt(ptr); + orcnt = RightCnt(ptr); + odouble = Double(ptr); if (LEFT == side) /* One more/fewer left child: */ if (0 < added) ptr->lcnt++; /* LeftCnt(ptr)++ */ @@ -1595,6 +1597,7 @@ H5TB_balance(H5TB_NODE ** root, H5TB_NODE * ptr, int side, int added) ptr->rcnt--; /* RightCnt(ptr)-- */ if (0 != deeper) { /* One leg got longer or shorter: */ + odelta = DeltaCnt(olcnt, orcnt, odouble, side); /* compute delta before the node was added */ if ((deeper < 0 && odelta < 0) || (deeper > 0 && odelta > 0)) { /* Became too unbalanced: */ H5TB_NODE *kid; @@ -1623,7 +1626,7 @@ H5TB_balance(H5TB_NODE ** root, H5TB_NODE * ptr, int side, int added) ptr = H5TB_swapkid(root, ptr, side); } } - else if (obal) + else if (olcnt!=orcnt) { /* Just became balanced: */ ptr->flags &= ~H5TB_UNBAL; if (0 < deeper) diff --git a/src/H5TBprivate.h b/src/H5TBprivate.h index a58fc39..355fcef 100644 --- a/src/H5TBprivate.h +++ b/src/H5TBprivate.h @@ -59,14 +59,19 @@ typedef int (*H5TB_cmp_t)(const void *k1, const void *k2, int cmparg); # define HasChild(n,s) ( Cnt(n,s)>0 ) # define Heavy(n,s) ( (s) & (LeftCnt(n)>RightCnt(n) ? LEFT : \ LeftCnt(n)==RightCnt(n) ? 0 : RIGHT)) +# define HeavyCnt(l,r,s) ( (s) & ((l)>(r) ? LEFT : (l)==(r) ? 0 : RIGHT)) # define Intern(n) ( LeftCnt(n) && RightCnt(n) ) # define UnBal(n) ( LeftCnt(n)>RightCnt(n) ? LEFT : \ LeftCnt(n)==RightCnt(n) ? 0 : RIGHT) -# define UnBalanced(n) ( LeftCnt(n)!=RightCnt(n) ? 1 : 0) +# define UnBalanced(n) ( LeftCnt(n)!=RightCnt(n) ) +# define UnBalancedCnt(l,r) ( (l)!=(r) ) # define Double(n) ( H5TB_DOUBLE & (n)->flags ) # define Other(side) ( LEFT + RIGHT - (side) ) # define Weight(n) ( Double(n) ? 2 : UnBalanced(n) ) +# define WeightCnt(l,r,d) ( (d) ? 2 : UnBalancedCnt(l,r) ) # define Delta(n,s) ( Heavy(n,s) ? Weight(n) : -Weight(n) ) +# define DeltaCnt(l,r,d,s) ( HeavyCnt(l,r,s) ? WeightCnt(l,r,d) : \ + -WeightCnt(l,r,d) ) # define SetFlags(n,s,b,i) ( ( -2<(b) && (b)<2 ? 0 : H5TB_DOUBLE ) \ | ( 0>(b) ? H5TB_HEAVY(s) : (b)>0 ? H5TB_HEAVY(Other(s)) : 0 ) \ | ( (i) ? H5TB_INTERN : 0 ) ) |