From fecdd9022de801f18d900c4c86788b2aaf967ec7 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Fri, 16 Jan 2004 15:26:01 -0500 Subject: [svn-r8076] Purpose: Bug fix. Description: Fix problems in B-tree deletion routine that were corrupting the data structure when the B-tree had several levels and the right-most item from a leaf node that was the right-most child of an internal node was removed. Also address similar problems when a complete internal or right-most node was removed. NOTE: The B-tree deletion routines are still _NOT_ maintaining the B-tree properties correctly, that will be addressed in a future (hopefully soon) fix. Platforms tested: FreeBSD 4.9 (sleipnir) too obscure to require h5committest --- src/H5B.c | 47 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 46 insertions(+), 1 deletion(-) diff --git a/src/H5B.c b/src/H5B.c index 9002ebd..8e8cade 100644 --- a/src/H5B.c +++ b/src/H5B.c @@ -1696,7 +1696,7 @@ H5B_remove_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type * Update left and right key dirty bits if the subtree indicates that they * have changed. If the subtree's left key changed and the subtree is the * left-most child of the current node then we must update the key in our - * parent and indicate that it changed. Similarly, if the rigt subtree + * parent and indicate that it changed. Similarly, if the right subtree * key changed and it's the right most key of this node we must update * our right key and indicate that it changed. */ @@ -1718,6 +1718,24 @@ H5B_remove_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type *rt_key_changed = FALSE; } else { HDmemcpy(rt_key, bt->key[idx+1].nkey, type->sizeof_nkey); + + /* Since our right key was changed, we must check for a right + * sibling and change it's left-most key as well. + * (Handle the ret_value==H5B_INS_REMOVE case below) + */ + if (ret_value!=H5B_INS_REMOVE && level>0) { + if (H5F_addr_defined(bt->right)) { + if (NULL==(sibling=H5AC_find(f, dxpl_id, H5AC_BT, bt->right, type, udata))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, H5B_INS_ERROR, "unable to unlink node from tree"); + + /* Make certain the native key for the right sibling is set up */ + if (!sibling->key[0].nkey && H5B_decode_key(f, sibling, 0) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTDECODE, H5B_INS_ERROR, "unable to decode key") + HDmemcpy(sibling->key[0].nkey, bt->key[idx+1].nkey, type->sizeof_nkey); + sibling->key[0].dirty = TRUE; + sibling->cache_info.dirty = TRUE; + } + } } } @@ -1745,6 +1763,14 @@ H5B_remove_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type if (H5F_addr_defined(bt->right)) { if (NULL==(sibling=H5AC_find(f, dxpl_id, H5AC_BT, bt->right, type, udata))) HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, H5B_INS_ERROR, "unable to unlink node from tree"); + + /* Copy left-most key from deleted node to left-most key in it's right neighbor */ + /* (Make certain the native key for the right sibling is set up) */ + if (!sibling->key[0].nkey && H5B_decode_key(f, sibling, 0) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTDECODE, H5B_INS_ERROR, "unable to decode key") + HDmemcpy(sibling->key[0].nkey, bt->key[0].nkey, type->sizeof_nkey); + sibling->key[0].dirty = TRUE; + sibling->left = bt->left; sibling->cache_info.dirty = TRUE; } @@ -1807,6 +1833,25 @@ H5B_remove_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type assert(bt->key[bt->nchildren].nkey); HDmemcpy(rt_key, bt->key[bt->nchildren].nkey, type->sizeof_nkey); *rt_key_changed = TRUE; + + /* Since our right key was changed, we must check for a right + * sibling and change it's left-most key as well. + * (Handle the ret_value==H5B_INS_REMOVE case below) + */ + if (level>0) { + if (H5F_addr_defined(bt->right)) { + if (NULL==(sibling=H5AC_find(f, dxpl_id, H5AC_BT, bt->right, type, udata))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, H5B_INS_ERROR, "unable to unlink node from tree"); + + /* Make certain the native key for the right sibling is set up */ + if (!sibling->key[0].nkey && H5B_decode_key(f, sibling, 0) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTDECODE, H5B_INS_ERROR, "unable to decode key") + HDmemcpy(sibling->key[0].nkey, bt->key[bt->nchildren].nkey, type->sizeof_nkey); + sibling->key[0].dirty = TRUE; + sibling->cache_info.dirty = TRUE; + } + } + ret_value = H5B_INS_NOOP; } else if (H5B_INS_REMOVE==ret_value) { -- cgit v0.12