summaryrefslogtreecommitdiffstats
path: root/src/H5B.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/H5B.c')
-rw-r--r--src/H5B.c291
1 files changed, 258 insertions, 33 deletions
diff --git a/src/H5B.c b/src/H5B.c
index d8424a9..49b1f17 100644
--- a/src/H5B.c
+++ b/src/H5B.c
@@ -539,16 +539,17 @@ H5B_find(H5F_t *f, const H5B_class_t *type, const haddr_t *addr, void *udata)
}
/* compare */
if ((cmp = (type->cmp3) (f, bt->key[idx].nkey, udata,
- bt->key[idx + 1].nkey)) < 0) {
+ bt->key[idx+1].nkey)) < 0) {
rt = idx;
} else {
- lt = idx + 1;
+ lt = idx+1;
}
}
if (cmp) {
HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL,
"B-tree key not found");
}
+
/*
* Follow the link to the subtree or to the data node.
*/
@@ -560,7 +561,7 @@ H5B_find(H5F_t *f, const H5B_class_t *type, const haddr_t *addr, void *udata)
}
} else {
ret_value = (type->found) (f, bt->child + idx, bt->key[idx].nkey,
- udata, bt->key[idx + 1].nkey);
+ udata, bt->key[idx+1].nkey);
if (ret_value < 0) {
HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL,
"key not found in leaf node");
@@ -647,17 +648,17 @@ H5B_split(H5F_t *f, const H5B_class_t *type, H5B_t *old_bt,
k * recsize + new_bt->sizeof_rkey);
HDmemcpy(new_bt->native,
old_bt->native + k * type->sizeof_nkey,
- (k + 1) * type->sizeof_nkey);
+ (k+1) * type->sizeof_nkey);
for (i = 0; i <= k; i++) {
/* key */
- new_bt->key[i].dirty = old_bt->key[k + i].dirty;
- if (old_bt->key[k + i].nkey) {
+ new_bt->key[i].dirty = old_bt->key[k+i].dirty;
+ if (old_bt->key[k+i].nkey) {
new_bt->key[i].nkey = new_bt->native + i * type->sizeof_nkey;
}
/* child */
if (i < k) {
- new_bt->child[i] = old_bt->child[k + i];
+ new_bt->child[i] = old_bt->child[k+i];
}
}
new_bt->ndirty = new_bt->nchildren = k;
@@ -757,7 +758,7 @@ H5B_decode_keys(H5F_t *f, H5B_t *bt, intn idx)
HRETURN_ERROR(H5E_BTREE, H5E_CANTDECODE, FAIL,
"unable to decode key");
}
- if (!bt->key[idx + 1].nkey && H5B_decode_key(f, bt, idx + 1) < 0) {
+ if (!bt->key[idx+1].nkey && H5B_decode_key(f, bt, idx+1) < 0) {
HRETURN_ERROR(H5E_BTREE, H5E_CANTDECODE, FAIL,
"unable to decode key");
}
@@ -972,20 +973,20 @@ H5B_insert_child(H5F_t *f, const H5B_class_t *type, H5B_t *bt,
/*
* The MD_KEY is the left key of the new node.
*/
- HDmemmove(bt->page + H5B_SIZEOF_HDR(f) + (idx + 1) * recsize,
+ HDmemmove(bt->page + H5B_SIZEOF_HDR(f) + (idx+1) * recsize,
bt->page + H5B_SIZEOF_HDR(f) + idx * recsize,
(bt->nchildren - idx) * recsize + bt->sizeof_rkey);
- HDmemmove(bt->native + (idx + 1) * type->sizeof_nkey,
+ HDmemmove(bt->native + (idx+1) * type->sizeof_nkey,
bt->native + idx * type->sizeof_nkey,
((bt->nchildren - idx) + 1) * type->sizeof_nkey);
for (i = bt->nchildren; i >= idx; --i) {
- bt->key[i + 1].dirty = bt->key[i].dirty;
+ bt->key[i+1].dirty = bt->key[i].dirty;
if (bt->key[i].nkey) {
- bt->key[i + 1].nkey = bt->native + (i + 1) * type->sizeof_nkey;
+ bt->key[i+1].nkey = bt->native + (i+1) * type->sizeof_nkey;
} else {
- bt->key[i + 1].nkey = NULL;
+ bt->key[i+1].nkey = NULL;
}
}
bt->key[idx].dirty = TRUE;
@@ -997,26 +998,26 @@ H5B_insert_child(H5F_t *f, const H5B_class_t *type, H5B_t *bt,
* The MD_KEY is the right key of the new node.
*/
HDmemmove(bt->page + (H5B_SIZEOF_HDR(f) +
- (idx + 1) * recsize + bt->sizeof_rkey),
+ (idx+1) * recsize + bt->sizeof_rkey),
bt->page + (H5B_SIZEOF_HDR(f) +
idx * recsize + bt->sizeof_rkey),
(bt->nchildren - idx) * recsize);
- HDmemmove(bt->native + (idx + 2) * type->sizeof_nkey,
- bt->native + (idx + 1) * type->sizeof_nkey,
+ HDmemmove(bt->native + (idx+2) * type->sizeof_nkey,
+ bt->native + (idx+1) * type->sizeof_nkey,
(bt->nchildren - idx) * type->sizeof_nkey);
for (i = bt->nchildren; i > idx; --i) {
- bt->key[i + 1].dirty = bt->key[i].dirty;
+ bt->key[i+1].dirty = bt->key[i].dirty;
if (bt->key[i].nkey) {
- bt->key[i + 1].nkey = bt->native + (i + 1) * type->sizeof_nkey;
+ bt->key[i+1].nkey = bt->native + (i+1) * type->sizeof_nkey;
} else {
- bt->key[i + 1].nkey = NULL;
+ bt->key[i+1].nkey = NULL;
}
}
- bt->key[idx + 1].dirty = TRUE;
- bt->key[idx + 1].nkey = bt->native + (idx + 1) * type->sizeof_nkey;
- HDmemcpy(bt->key[idx + 1].nkey, md_key, type->sizeof_nkey);
+ bt->key[idx+1].dirty = TRUE;
+ bt->key[idx+1].nkey = bt->native + (idx+1) * type->sizeof_nkey;
+ HDmemcpy(bt->key[idx+1].nkey, md_key, type->sizeof_nkey);
}
HDmemmove(bt->child + idx + 1,
@@ -1111,7 +1112,7 @@ H5B_insert_helper(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
"unable to decode key");
}
if ((cmp = (type->cmp3) (f, bt->key[idx].nkey, udata,
- bt->key[idx + 1].nkey)) < 0) {
+ bt->key[idx+1].nkey)) < 0) {
rt = idx;
} else {
lt = idx + 1;
@@ -1255,9 +1256,9 @@ H5B_insert_helper(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
"unable to decode key");
}
my_ins = H5B_INS_RIGHT;
- HDmemcpy(md_key, bt->key[idx + 1].nkey, type->sizeof_nkey);
+ HDmemcpy(md_key, bt->key[idx+1].nkey, type->sizeof_nkey);
if ((type->new_node) (f, H5B_INS_RIGHT, md_key, udata,
- bt->key[idx + 1].nkey, &child_addr/*out*/) < 0) {
+ bt->key[idx+1].nkey, &child_addr/*out*/) < 0) {
HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR,
"can't insert maximum leaf node");
}
@@ -1268,7 +1269,8 @@ H5B_insert_helper(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
* We couldn't figure out which branch to follow out of this node. THIS
* IS A MAJOR PROBLEM THAT NEEDS TO BE FIXED --rpm.
*/
- assert("INTERNAL HDF5 ERROR (see rpm)" && 0);
+ assert("INTERNAL HDF5 ERROR (contact rpm)" && 0);
+ HDabort();
} else if (bt->level > 0) {
/*
@@ -1278,8 +1280,8 @@ H5B_insert_helper(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
if ((my_ins = H5B_insert_helper(f, bt->child + idx, type,
bt->key[idx].nkey, lt_key_changed,
md_key, udata,
- bt->key[idx + 1].nkey, rt_key_changed,
- &child_addr /*out */ )) < 0) {
+ bt->key[idx+1].nkey, rt_key_changed,
+ &child_addr/*out*/)) < 0) {
HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR,
"can't insert subtree");
}
@@ -1312,11 +1314,11 @@ H5B_insert_helper(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
}
if (*rt_key_changed) {
bt->dirty = TRUE;
- bt->key[idx + 1].dirty = TRUE;
- if (idx + 1 < bt->nchildren) {
+ bt->key[idx+1].dirty = TRUE;
+ if (idx+1 < bt->nchildren) {
*rt_key_changed = FALSE;
} else {
- HDmemcpy(rt_key, bt->key[idx + 1].nkey, type->sizeof_nkey);
+ HDmemcpy(rt_key, bt->key[idx+1].nkey, type->sizeof_nkey);
}
}
if (H5B_INS_CHANGE == my_ins) {
@@ -1325,7 +1327,7 @@ H5B_insert_helper(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
*/
bt->child[idx] = child_addr;
bt->dirty = TRUE;
- bt->ndirty = MAX(bt->ndirty, idx + 1);
+ bt->ndirty = MAX(bt->ndirty, idx+1);
ret_value = H5B_INS_NOOP;
} else if (H5B_INS_LEFT == my_ins || H5B_INS_RIGHT == my_ins) {
@@ -1363,6 +1365,7 @@ H5B_insert_helper(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
"can't insert child");
}
}
+
/*
* If this node split, return the mid key (the one that is shared
* by the left and right node).
@@ -1500,6 +1503,228 @@ H5B_iterate (H5F_t *f, const H5B_class_t *type, const haddr_t *addr,
/*-------------------------------------------------------------------------
+ * Function: H5B_remove_helper
+ *
+ * Purpose: The recursive part of removing an item from a B-tree. The
+ * sub B-tree that is being considered is located at ADDR and
+ * the item to remove is described by UDATA. If the removed
+ * item falls at the left or right end of the current level then
+ * it might be necessary to adjust the left and/or right keys.
+ *
+ * Return: Success: SUCCEED
+ *
+ * Failure: FAIL
+ *
+ * Programmer: Robb Matzke
+ * Wednesday, September 16, 1998
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static H5B_ins_t
+H5B_remove_helper(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
+ uint8 *lt_key/*out*/, hbool_t *lt_key_changed/*out*/,
+ uint8 *md_key/*out*/, void *udata, uint8 *rt_key/*out*/,
+ hbool_t *rt_key_changed/*out*/)
+{
+ H5B_t *bt = NULL;
+ H5B_ins_t ret_value = H5B_INS_ERROR;
+ intn idx=-1, lt=0, rt, cmp=1;
+
+ FUNC_ENTER(H5B_remove_helper, FAIL);
+ assert(f);
+ assert(addr && H5F_addr_defined(addr));
+ assert(type);
+ assert(type->decode);
+ assert(type->cmp3);
+ assert(type->found);
+ assert(lt_key && lt_key_changed);
+ assert(md_key);
+ assert(udata);
+ assert(rt_key && rt_key_changed);
+
+ /*
+ * Perform a binary search to locate the child which contains the thing
+ * for which we're searching.
+ */
+ if (NULL==(bt=H5AC_protect(f, H5AC_BT, addr, type, udata))) {
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL,
+ "unable to load B-tree node");
+ }
+ rt = bt->nchildren;
+ while (lt<rt && cmp) {
+ idx = (lt+rt)/2;
+ if (H5B_decode_keys(f, bt, idx)<0) {
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTDECODE, FAIL,
+ "unable to decode B-tree key(s)");
+ }
+ if ((cmp=(type->cmp3)(f, bt->key[idx].nkey, udata,
+ bt->key[idx+1].nkey))<0) {
+ rt = idx;
+ } else {
+ lt = idx+1;
+ }
+ }
+ if (cmp) {
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree key not found");
+ }
+
+ /*
+ * Follow the link to the subtree or to the data node. The return value
+ * will be one of H5B_INS_ERROR, H5B_INS_NOOP, or H5B_INS_REMOVE.
+ */
+ assert(idx>=0 && idx<bt->nchildren);
+ if (bt->level>0) {
+ if ((ret_value=H5B_remove_helper(f,
+ bt->child+idx,
+ type,
+ bt->key[idx].nkey/*out*/,
+ lt_key_changed/*out*/,
+ md_key/*out*/,
+ udata,
+ bt->key[idx+1].nkey/*out*/,
+ rt_key_changed/*out*/))<0) {
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL,
+ "key not found in subtree");
+ }
+ } else if (type->remove) {
+ if ((ret_value=(type->remove)(f,
+ bt->child+idx,
+ bt->key[idx].nkey,
+ lt_key_changed,
+ md_key,
+ udata,
+ bt->key[idx+1].nkey,
+ rt_key_changed))<0) {
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL,
+ "key not found in leaf node");
+ }
+ }
+
+ /*
+ * 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
+ * key changed and it's the right most key of this node we must update
+ * our right key and indicate that it changed.
+ */
+ if (*lt_key_changed) {
+ bt->dirty = TRUE;
+ bt->key[idx].dirty = TRUE;
+ if (idx>0) {
+ *lt_key_changed = FALSE;
+ } else {
+ HDmemcpy(lt_key, bt->key[idx].nkey, type->sizeof_nkey);
+ }
+ }
+ if (*rt_key_changed) {
+ bt->dirty = TRUE;
+ if (idx+1<bt->nchildren) {
+ *rt_key_changed = FALSE;
+ } else {
+ HDmemcpy(rt_key, bt->key[idx+1].nkey, type->sizeof_nkey);
+ }
+ }
+
+ /*
+ * If the subtree returned H5B_INS_REMOVE then we should remove the
+ * subtree entry from the current node. There are four cases:
+ *
+ * 1: If the subtree is the only child of this node then remove both
+ * keys and the subtree and return H5B_INS_REMOVE.
+ *
+ * 2: If the subtree is the left-most child of this node then we
+ * discard the left-most key and the left-most child (the child has
+ * already been freed) and shift everything down by one. We copy
+ * the new left-most key into lt_key and notify the caller that the
+ * left key has changed. Return H5B_INS_NOOP.
+ *
+ * 3: If the subtree is the right-most child of this node then we
+ * discard the right-most key and the right-most child (the child
+ * has already been freed). We copy the new right-most key into
+ * rt_key and notify the caller that the right key has changed.
+ * Return H5B_INS_NOOP.
+ *
+ * 4: There are subtrees out of this node to both the left and right of
+ * the subtree being removed. The key to the left of the subtree
+ * and the subtree are removed from this node and all keys and nodes
+ * to the right are shifted left by one place. The subtree has
+ * already been freed). Return H5B_INS_NOOP.
+ */
+ if (1==bt->nchildren) {
+ HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL,
+ "not implemented yet (all node removal)");
+ } else if (0==idx) {
+ HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL,
+ "not implemented yet (first node removal)");
+ } else if (idx+1==bt->nchildren) {
+ HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL,
+ "not implemented yet (last node removal)");
+ } else {
+ HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL,
+ "not implemented yet (middle node removal)");
+ }
+
+ done:
+ if (bt && H5AC_unprotect(f, H5AC_BT, addr, bt)<0) {
+ HRETURN_ERROR(H5E_BTREE, H5E_PROTECT, FAIL,
+ "unable to release node");
+ }
+ FUNC_LEAVE(ret_value);
+}
+
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_remove
+ *
+ * Purpose: Removes an item from a B-tree.
+ *
+ * Note: The current version does not attempt to rebalance the tree.
+ *
+ * Return: Success: SUCCEED
+ *
+ * Failure: FAIL. Failure includes not being able to
+ * find the object which is to be removed.
+ *
+ * Programmer: Robb Matzke
+ * Wednesday, September 16, 1998
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B_remove(H5F_t *f, const H5B_class_t *type, const haddr_t *addr,
+ void *udata)
+{
+ /* These are defined this way to satisfy alignment constraints */
+ uint64 _lt_key[128], _md_key[128], _rt_key[128];
+ uint8 *lt_key = (uint8*)_lt_key; /*left key*/
+ uint8 *md_key = (uint8*)_md_key; /*middle key*/
+ uint8 *rt_key = (uint8*)_rt_key; /*right key*/
+ hbool_t lt_key_changed = FALSE; /*left key changed?*/
+ hbool_t rt_key_changed = FALSE; /*right key changed?*/
+
+ FUNC_ENTER(H5B_remove, FAIL);
+ assert(f);
+ assert(type);
+ assert(type->sizeof_nkey <= sizeof _lt_key);
+ assert(addr && H5F_addr_defined(addr));
+
+ if (H5B_remove_helper(f, addr, type, lt_key, &lt_key_changed, md_key,
+ udata, rt_key, &rt_key_changed)<0) {
+ HRETURN_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL,
+ "unable to remove entry from B-tree");
+ }
+
+ FUNC_LEAVE(SUCCEED);
+}
+
+
+/*-------------------------------------------------------------------------
* Function: H5B_nodesize
*
* Purpose: Returns the number of bytes needed for this type of
@@ -1744,7 +1969,7 @@ H5B_assert(H5F_t *f, const haddr_t *addr, const H5B_class_t *type,
status = H5B_decode_keys(f, bt, i);
assert(status >= 0);
cmp = (type->cmp2) (f, bt->key[i].nkey, udata,
- bt->key[i + 1].nkey);
+ bt->key[i+1].nkey);
assert(cmp < 0);
}
}