summaryrefslogtreecommitdiffstats
path: root/src/H5B.c
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2004-01-16 20:26:01 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2004-01-16 20:26:01 (GMT)
commitfecdd9022de801f18d900c4c86788b2aaf967ec7 (patch)
tree0958bb40c75fcd1c268508147480778a09ab0984 /src/H5B.c
parent4c9ff323aa07206c0c6d82bf9015e982c9148659 (diff)
downloadhdf5-fecdd9022de801f18d900c4c86788b2aaf967ec7.zip
hdf5-fecdd9022de801f18d900c4c86788b2aaf967ec7.tar.gz
hdf5-fecdd9022de801f18d900c4c86788b2aaf967ec7.tar.bz2
[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
Diffstat (limited to 'src/H5B.c')
-rw-r--r--src/H5B.c47
1 files changed, 46 insertions, 1 deletions
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) {