summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/H5B2.c7
-rw-r--r--src/H5B2dbg.c5
-rw-r--r--src/H5B2int.c549
-rw-r--r--src/H5B2pkg.h15
-rw-r--r--src/H5B2private.h6
-rw-r--r--src/H5B2stat.c12
-rw-r--r--src/H5B2test.c181
7 files changed, 382 insertions, 393 deletions
diff --git a/src/H5B2.c b/src/H5B2.c
index e2fc503..7ee979b 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -199,7 +199,7 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
/* Check if we need to split the root node (equiv. to a 1->2 node split) */
else if((bt2->depth == 0 && bt2->root.node_nrec == shared->split_leaf_nrec) ||
(bt2->depth == 1 && bt2->root.node_nrec == shared->split_twig_nrec) ||
- (bt2->depth > 0 && bt2->root.node_nrec == shared->split_brch_nrec)) {
+ (bt2->depth > 1 && bt2->root.node_nrec == shared->split_brch_nrec)) {
/* Split root node */
if(H5B2_split_root(f, dxpl_id, bt2, &bt2_flags, bt2->shared) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node")
@@ -303,9 +303,8 @@ done:
* Function: H5B2_find
*
* Purpose: Locate the specified information in a B-tree and return
- * that information by filling in fields of the caller-supplied
- * UDATA pointer depending on the type of leaf node
- * requested. The UDATA can point to additional data passed
+ * that information by calling the provided 'OP' routine with an
+ * OP_DATA pointer. The UDATA parameter points to data passed
* to the key comparison function.
*
* The 'OP' routine is called with the record found and the
diff --git a/src/H5B2dbg.c b/src/H5B2dbg.c
index c1bea51..2c58af8 100644
--- a/src/H5B2dbg.c
+++ b/src/H5B2dbg.c
@@ -252,7 +252,10 @@ H5B2_int_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent,
bt2 = NULL;
/* Print opening message */
- HDfprintf(stream, "%*sv2 B-tree Internal Node...\n", indent, "");
+ if(internal->depth == 1)
+ HDfprintf(stream, "%*sv2 B-tree Internal 'Leaf' Node...\n", indent, "");
+ else
+ HDfprintf(stream, "%*sv2 B-tree Internal 'Branch' Node...\n", indent, "");
/*
* Print the values.
diff --git a/src/H5B2int.c b/src/H5B2int.c
index 0df5706..d1cee6e 100644
--- a/src/H5B2int.c
+++ b/src/H5B2int.c
@@ -76,11 +76,11 @@
static herr_t H5B2_shared_free(void *_shared);
static herr_t H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
H5B2_node_ptr_t *node_ptr, unsigned depth);
+static herr_t H5B2_split1(H5F_t *f, hid_t dxpl_id, unsigned depth,
+ H5B2_node_ptr_t *curr_node_ptr, unsigned *parent_cache_info_flags_ptr,
+ H5B2_internal_t *internal, unsigned *internal_flags_ptr, unsigned idx);
static herr_t H5B2_redistribute2(H5F_t *f, hid_t dxpl_id, unsigned depth,
H5B2_internal_t *internal, unsigned idx);
-static herr_t H5B2_split2(H5F_t *f, hid_t dxpl_id, unsigned depth,
- H5B2_node_ptr_t *curr_node_ptr, unsigned * parent_cache_info_flags_ptr,
- H5B2_internal_t *internal, unsigned *internal_flags_ptr, unsigned idx);
static herr_t H5B2_split3(H5F_t *f, hid_t dxpl_id, unsigned depth,
H5B2_node_ptr_t *curr_node_ptr, unsigned *parent_cache_info_flags,
H5B2_internal_t *internal, unsigned *internal_flags, unsigned idx);
@@ -343,26 +343,25 @@ H5B2_locate_record(const H5B2_class_t *type, unsigned nrec, size_t *rec_off,
/*-------------------------------------------------------------------------
- * Function: H5B2_split_root
+ * Function: H5B2_split1
*
- * Purpose: Split the root node
+ * Purpose: Perform a 1->2 node split
*
* Return: Success: Non-negative
- *
* Failure: Negative
*
* Programmer: Quincey Koziol
- * koziol@ncsa.uiuc.edu
- * Feb 3 2005
+ * koziol@hdfgroup.org
+ * Aug 28 2006
*
*-------------------------------------------------------------------------
*/
-herr_t
-H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr,
- H5RC_t *bt2_shared)
+static herr_t
+H5B2_split1(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *curr_node_ptr,
+ unsigned *parent_cache_info_flags_ptr, H5B2_internal_t *internal,
+ unsigned *internal_flags_ptr, unsigned idx)
{
const H5AC_class_t *child_class; /* Pointer to child node's class info */
- H5B2_internal_t *new_root; /* Pointer to new root node */
haddr_t left_addr, right_addr; /* Addresses of left & right child nodes */
void *left_child, *right_child; /* Pointers to child nodes */
unsigned *left_nrec, *right_nrec; /* Pointers to child # of records */
@@ -370,173 +369,224 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr,
H5B2_node_ptr_t *left_node_ptrs=NULL, *right_node_ptrs=NULL;/* Pointers to childs' node pointer info */
H5B2_shared_t *shared; /* B-tree's shared info */
unsigned mid_record; /* Index of "middle" record in current node */
- unsigned old_root_nrec; /* Number of records in root node */
- herr_t ret_value=SUCCEED; /* Return value */
+ unsigned old_node_nrec; /* Number of records in internal node split */
+ herr_t ret_value = SUCCEED; /* Return value */
- FUNC_ENTER_NOAPI_NOINIT(H5B2_split_root)
+ FUNC_ENTER_NOAPI_NOINIT(H5B2_split1)
HDassert(f);
- HDassert(bt2);
- HDassert(bt2_flags_ptr);
- HDassert(bt2_shared);
+ HDassert(parent_cache_info_flags_ptr);
+ HDassert(internal);
+ HDassert(internal_flags_ptr);
/* Get the pointer to the shared B-tree info */
- shared=H5RC_GET_OBJ(bt2_shared);
+ shared = H5RC_GET_OBJ(internal->shared);
HDassert(shared);
- /* Check if root is an internal node already */
- if(bt2->depth > 0) {
- H5B2_internal_t *old_int=NULL, *new_int=NULL; /* Pointers to old & new internal nodes */
- H5B2_node_ptr_t new_int_ptr; /* Node pointer to manage new internal node */
+ /* Slide records in parent node up one space, to make room for promoted record */
+ if(idx < internal->nrec) {
+ HDmemmove(H5B2_INT_NREC(internal, shared, idx + 1), H5B2_INT_NREC(internal, shared, idx), shared->type->nrec_size * (internal->nrec - idx));
+ HDmemmove(&(internal->node_ptrs[idx + 2]), &(internal->node_ptrs[idx + 1]), sizeof(H5B2_node_ptr_t) * (internal->nrec - idx));
+ } /* end if */
+
+ /* Check for the kind of B-tree node to split */
+ if(depth > 1) {
+ H5B2_internal_t *left_int = NULL, *right_int = NULL; /* Pointers to old & new internal nodes */
/* Create new internal node */
- new_int_ptr.all_nrec = new_int_ptr.node_nrec = 0;
- if(H5B2_create_internal(f, dxpl_id, bt2_shared, &new_int_ptr, bt2->depth) < 0)
+ internal->node_ptrs[idx + 1].all_nrec = internal->node_ptrs[idx + 1].node_nrec = 0;
+ if(H5B2_create_internal(f, dxpl_id, internal->shared, &(internal->node_ptrs[idx + 1]), (depth - 1)) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node")
/* Setup information for unlocking child nodes */
child_class = H5AC_BT2_INT;
- left_addr = bt2->root.addr;
- right_addr = new_int_ptr.addr;
+ left_addr = internal->node_ptrs[idx].addr;
+ right_addr = internal->node_ptrs[idx + 1].addr;
/* Protect both leafs */
- if(NULL == (old_int = H5B2_protect_internal(f, dxpl_id, bt2_shared, left_addr, bt2->root.node_nrec, bt2->depth, H5AC_WRITE)))
+ if(NULL == (left_int = H5B2_protect_internal(f, dxpl_id, internal->shared, left_addr, internal->node_ptrs[idx].node_nrec, (depth - 1), H5AC_WRITE)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
- if(NULL == (new_int = H5B2_protect_internal(f, dxpl_id, bt2_shared, right_addr, new_int_ptr.node_nrec, bt2->depth, H5AC_WRITE)))
+ if(NULL == (right_int = H5B2_protect_internal(f, dxpl_id, internal->shared, right_addr, internal->node_ptrs[idx + 1].node_nrec, (depth - 1), H5AC_WRITE)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
/* More setup for child nodes */
- left_child = old_int;
- right_child = new_int;
- left_nrec = &(old_int->nrec);
- right_nrec = &(new_int->nrec);
- left_native = old_int->int_native;
- right_native = new_int->int_native;
- left_node_ptrs = old_int->node_ptrs;
- right_node_ptrs = new_int->node_ptrs;
+ left_child = left_int;
+ right_child = right_int;
+ left_nrec = &(left_int->nrec);
+ right_nrec = &(right_int->nrec);
+ left_native = left_int->int_native;
+ right_native = right_int->int_native;
+ left_node_ptrs = left_int->node_ptrs;
+ right_node_ptrs = right_int->node_ptrs;
} /* end if */
else {
- H5B2_leaf_t *old_leaf=NULL, *new_leaf=NULL; /* Pointers to old & new leaf nodes */
- H5B2_node_ptr_t new_leaf_ptr; /* Node pointer to manage new leaf node */
+ H5B2_leaf_t *left_leaf = NULL, *right_leaf = NULL; /* Pointers to old & new leaf nodes */
/* Create new leaf node */
- new_leaf_ptr.all_nrec=new_leaf_ptr.node_nrec=0;
- if(H5B2_create_leaf(f, dxpl_id, bt2_shared, &new_leaf_ptr)<0)
+ internal->node_ptrs[idx + 1].all_nrec = internal->node_ptrs[idx + 1].node_nrec = 0;
+ if(H5B2_create_leaf(f, dxpl_id, internal->shared, &(internal->node_ptrs[idx + 1])) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new leaf node")
/* Setup information for unlocking child nodes */
child_class = H5AC_BT2_LEAF;
- left_addr = bt2->root.addr;
- right_addr = new_leaf_ptr.addr;
+ left_addr = internal->node_ptrs[idx].addr;
+ right_addr = internal->node_ptrs[idx + 1].addr;
/* Protect both leafs */
- if (NULL == (old_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, left_addr, &(bt2->root.node_nrec), bt2_shared, H5AC_WRITE)))
+ if(NULL == (left_leaf = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node")
- if (NULL == (new_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, right_addr, &(new_leaf_ptr.node_nrec), bt2_shared, H5AC_WRITE)))
+ if(NULL == (right_leaf = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx + 1].node_nrec), internal->shared, H5AC_WRITE)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node")
/* More setup for child nodes */
- left_child = old_leaf;
- right_child = new_leaf;
- left_nrec = &(old_leaf->nrec);
- right_nrec = &(new_leaf->nrec);
- left_native = old_leaf->leaf_native;
- right_native = new_leaf->leaf_native;
+ left_child = left_leaf;
+ right_child = right_leaf;
+ left_nrec = &(left_leaf->nrec);
+ right_nrec = &(right_leaf->nrec);
+ left_native = left_leaf->leaf_native;
+ right_native = right_leaf->leaf_native;
} /* end if */
- /* Set the old number of records in root node */
- old_root_nrec = bt2->root.node_nrec;
+ /* Get the number of records in node to split */
+ old_node_nrec = internal->node_ptrs[idx].node_nrec;
- /* Determine "middle" record to promote to new root */
- mid_record = old_root_nrec/2;
+ /* Determine "middle" record to promote to internal node */
+ mid_record = old_node_nrec / 2;
/* Copy "upper half" of records to new child */
HDmemcpy(H5B2_NAT_NREC(right_native, shared, 0),
H5B2_NAT_NREC(left_native, shared, mid_record + 1),
- shared->type->nrec_size * (old_root_nrec - (mid_record + 1)));
+ shared->type->nrec_size * (old_node_nrec - (mid_record + 1)));
- /* Copy "upper half" of format root's node pointers, if the children of the root are internal nodes */
- if(bt2->depth > 0)
+ /* Copy "upper half" of node pointers, if the node is an internal node */
+ if(depth > 1)
HDmemcpy(&(right_node_ptrs[0]), &(left_node_ptrs[mid_record + 1]),
- sizeof(H5B2_node_ptr_t)*(old_root_nrec-mid_record));
+ sizeof(H5B2_node_ptr_t) * (old_node_nrec - mid_record));
- /* Create new internal node to use as root */
- if(H5B2_create_internal(f, dxpl_id, bt2_shared, &(bt2->root), (bt2->depth + 1)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node")
-
- /* Protect new internal node */
- if (NULL == (new_root = H5B2_protect_internal(f, dxpl_id, bt2_shared, bt2->root.addr, bt2->root.node_nrec, (bt2->depth + 1), H5AC_WRITE)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
-
- /* Copy "middle" record to new internal node */
- HDmemcpy(H5B2_INT_NREC(new_root,shared,0),H5B2_NAT_NREC(left_native,shared,mid_record),shared->type->nrec_size);
-
- /* Set internal node pointers to child nodes */
- new_root->node_ptrs[0].addr = left_addr;
- new_root->node_ptrs[1].addr = right_addr;
+ /* Copy "middle" record to internal node */
+ HDmemcpy(H5B2_INT_NREC(internal, shared, idx), H5B2_NAT_NREC(left_native, shared, mid_record), shared->type->nrec_size);
/* Update record counts in child nodes */
- new_root->node_ptrs[0].node_nrec = *left_nrec = mid_record;
- new_root->node_ptrs[1].node_nrec = *right_nrec = old_root_nrec-(mid_record+1);
+ internal->node_ptrs[idx].node_nrec = *left_nrec = mid_record;
+ internal->node_ptrs[idx + 1].node_nrec = *right_nrec = old_node_nrec - (mid_record + 1);
/* Determine total number of records in new child nodes */
- if(bt2->depth > 0) {
+ if(depth > 1) {
unsigned u; /* Local index variable */
hsize_t new_left_all_nrec; /* New total number of records in left child */
hsize_t new_right_all_nrec; /* New total number of records in right child */
/* Compute total of all records in each child node */
- new_left_all_nrec = new_root->node_ptrs[0].node_nrec;
- for(u=0; u<(*left_nrec+1); u++)
+ new_left_all_nrec = internal->node_ptrs[idx].node_nrec;
+ for(u = 0; u < (*left_nrec + 1); u++)
new_left_all_nrec += left_node_ptrs[u].all_nrec;
- new_right_all_nrec = new_root->node_ptrs[1].node_nrec;
- for(u=0; u<(*right_nrec+1); u++)
+ new_right_all_nrec = internal->node_ptrs[idx + 1].node_nrec;
+ for(u = 0; u < (*right_nrec + 1); u++)
new_right_all_nrec += right_node_ptrs[u].all_nrec;
- new_root->node_ptrs[0].all_nrec = new_left_all_nrec;
- new_root->node_ptrs[1].all_nrec = new_right_all_nrec;
+ internal->node_ptrs[idx].all_nrec = new_left_all_nrec;
+ internal->node_ptrs[idx + 1].all_nrec = new_right_all_nrec;
} /* end if */
else {
- new_root->node_ptrs[0].all_nrec = new_root->node_ptrs[0].node_nrec;
- new_root->node_ptrs[1].all_nrec = new_root->node_ptrs[1].node_nrec;
+ internal->node_ptrs[idx].all_nrec = internal->node_ptrs[idx].node_nrec;
+ internal->node_ptrs[idx + 1].all_nrec = internal->node_ptrs[idx + 1].node_nrec;
} /* end else */
- /* Update record count in new internal node */
- new_root->nrec = 1;
+ /* Update # of records in parent node */
+ internal->nrec++;
+
+ /* Mark parent as dirty */
+ *internal_flags_ptr |= H5AC__DIRTIED_FLAG;
+
+ /* Update grandparent info */
+ curr_node_ptr->node_nrec++;
+
+ /* Mark grandparent as dirty */
+ *parent_cache_info_flags_ptr |= H5AC__DIRTIED_FLAG;
#ifdef H5B2_DEBUG
- H5B2_assert_internal(bt2->root.all_nrec,shared,new_root);
- if(bt2->depth>0) {
- H5B2_assert_internal2(new_root->node_ptrs[0].all_nrec,shared,left_child,right_child);
- H5B2_assert_internal2(new_root->node_ptrs[1].all_nrec,shared,right_child,left_child);
+ H5B2_assert_internal((hsize_t)0,shared,internal);
+ if(depth > 1) {
+ H5B2_assert_internal2(internal->node_ptrs[idx].all_nrec, shared, left_child, right_child);
+ H5B2_assert_internal2(internal->node_ptrs[idx + 1].all_nrec, shared, right_child, left_child);
} /* end if */
else {
- H5B2_assert_leaf2(shared,left_child,right_child);
- H5B2_assert_leaf(shared,right_child);
+ H5B2_assert_leaf2(shared, left_child, right_child);
+ H5B2_assert_leaf(shared, right_child);
} /* end else */
#endif /* H5B2_DEBUG */
- /* Release new internal node (marked as dirty) */
- if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, bt2->root.addr, new_root, H5AC__DIRTIED_FLAG) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree internal node")
/* Release child nodes (marked as dirty) */
- if (H5AC_unprotect(f, dxpl_id, child_class, left_addr, left_child, H5AC__DIRTIED_FLAG) < 0)
+ if(H5AC_unprotect(f, dxpl_id, child_class, left_addr, left_child, H5AC__DIRTIED_FLAG) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
- if (H5AC_unprotect(f, dxpl_id, child_class, right_addr, right_child, H5AC__DIRTIED_FLAG) < 0)
+ if(H5AC_unprotect(f, dxpl_id, child_class, right_addr, right_child, H5AC__DIRTIED_FLAG) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5B2_split1 */
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B2_split_root
+ *
+ * Purpose: Split the root node
+ *
+ * Return: Success: Non-negative
+ *
+ * Failure: Negative
+ *
+ * Programmer: Quincey Koziol
+ * koziol@ncsa.uiuc.edu
+ * Feb 3 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr,
+ H5RC_t *bt2_shared)
+{
+ H5B2_internal_t *new_root; /* Pointer to new root node */
+ unsigned new_root_flags = H5AC__NO_FLAGS_SET; /* Cache flags for new root node */
+ H5B2_node_ptr_t old_root_ptr; /* Old node pointer to root node in B-tree */
+ herr_t ret_value = SUCCEED; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5B2_split_root)
+
+ HDassert(f);
+ HDassert(bt2);
+ HDassert(bt2_flags_ptr);
+ HDassert(bt2_shared);
+
/* Update depth of B-tree */
bt2->depth++;
- /* Update pointer to B-tree's root node to pointer to new internal node */
- bt2->root.node_nrec = 1;
+ /* Keep old root node pointer info */
+ old_root_ptr = bt2->root;
- /* Mark B-tree header as dirty */
- *bt2_flags_ptr |= H5AC__DIRTIED_FLAG;
+ /* Create new internal node to use as root */
+ bt2->root.node_nrec = 0;
+ if(H5B2_create_internal(f, dxpl_id, bt2_shared, &(bt2->root), bt2->depth) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node")
+
+ /* Protect new root node */
+ if(NULL == (new_root = H5B2_protect_internal(f, dxpl_id, bt2_shared, bt2->root.addr, bt2->root.node_nrec, bt2->depth, H5AC_WRITE)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
+
+ /* Set first node pointer in root node to old root node pointer info */
+ new_root->node_ptrs[0] = old_root_ptr;
+
+ /* Split original root node */
+ if(H5B2_split1(f, dxpl_id, bt2->depth, &(bt2->root), bt2_flags_ptr, new_root, &new_root_flags, 0) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split old root node")
+
+ /* Release new root node (marked as dirty) */
+ if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, bt2->root.addr, new_root, new_root_flags) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree internal node")
done:
- FUNC_LEAVE_NOAPI(ret_value);
+ FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B2_split_root */
@@ -763,276 +813,6 @@ done:
/*-------------------------------------------------------------------------
- * Function: H5B2_split2
- *
- * Purpose: Perform a 2->3 node split
- *
- * Return: Success: Non-negative
- *
- * Failure: Negative
- *
- * Programmer: Quincey Koziol
- * koziol@ncsa.uiuc.edu
- * Feb 9 2005
- *
- *-------------------------------------------------------------------------
- */
-static herr_t
-H5B2_split2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *curr_node_ptr,
- unsigned *parent_cache_info_flags_ptr, H5B2_internal_t *internal,
- unsigned *internal_flags_ptr, unsigned idx)
-{
- const H5AC_class_t *child_class; /* Pointer to child node's class info */
- haddr_t left_addr, right_addr; /* Addresses of left & right child nodes */
- haddr_t middle_addr; /* Address of middle child node */
- void *left_child, *right_child; /* Pointers to left & right child nodes */
- void *middle_child; /* Pointer to middle child node */
- unsigned *left_nrec, *right_nrec; /* Pointers to left & right child # of records */
- unsigned *middle_nrec; /* Pointer to middle child # of records */
- uint8_t *left_native, *right_native; /* Pointers to left & right children's native records */
- uint8_t *middle_native; /* Pointer to middle child's native records */
- H5B2_node_ptr_t *left_node_ptrs=NULL, *right_node_ptrs=NULL;/* Pointers to childs' node pointer info */
- H5B2_node_ptr_t *middle_node_ptrs=NULL;/* Pointers to childs' node pointer info */
- H5B2_shared_t *shared; /* B-tree's shared info */
- hssize_t left_moved_nrec=0, right_moved_nrec=0; /* Number of records moved, for internal split */
- hsize_t middle_moved_nrec=0; /* Number of records moved, for internal split */
- herr_t ret_value=SUCCEED; /* Return value */
-
- FUNC_ENTER_NOAPI_NOINIT(H5B2_split2)
-
- HDassert(f);
- HDassert(parent_cache_info_flags_ptr);
- HDassert(internal);
- HDassert(internal_flags_ptr);
-
- /* Get the pointer to the shared B-tree info */
- shared=H5RC_GET_OBJ(internal->shared);
- HDassert(shared);
-
- /* Slide records in parent node up one space, to make room for promoted record */
- HDmemmove(H5B2_INT_NREC(internal,shared,idx+2),H5B2_INT_NREC(internal,shared,idx+1),shared->type->nrec_size*(internal->nrec-(idx+1)));
- HDmemmove(&(internal->node_ptrs[idx+2]),&(internal->node_ptrs[idx+1]),sizeof(H5B2_node_ptr_t)*(internal->nrec-idx));
-
- /* Check for the kind of B-tree node to split */
- if(depth > 1) {
- H5B2_internal_t *left_internal; /* Pointer to left internal node */
- H5B2_internal_t *middle_internal; /* Pointer to middle internal node */
- H5B2_internal_t *right_internal; /* Pointer to right internal node */
-
- /* Setup information for unlocking child nodes */
- child_class = H5AC_BT2_INT;
- left_addr = internal->node_ptrs[idx].addr;
- right_addr = internal->node_ptrs[idx+2].addr;
-
- /* Lock left & right B-tree child nodes */
- if(NULL == (left_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, left_addr, internal->node_ptrs[idx].node_nrec, (depth - 1), H5AC_WRITE)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
- if(NULL == (right_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, right_addr, internal->node_ptrs[idx+2].node_nrec, (depth - 1), H5AC_WRITE)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
-
- /* Create new empty "middle" internal node */
- internal->node_ptrs[idx+1].all_nrec=internal->node_ptrs[idx+1].node_nrec=0;
- if(H5B2_create_internal(f, dxpl_id, internal->shared, &(internal->node_ptrs[idx + 1]), (depth - 1)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node")
-
- /* Setup information for unlocking middle child node */
- middle_addr = internal->node_ptrs[idx+1].addr;
-
- /* Lock "middle" internal node */
- if(NULL == (middle_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, middle_addr, internal->node_ptrs[idx+1].node_nrec, (depth - 1), H5AC_WRITE)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
-
- /* More setup for accessing child node information */
- left_child = left_internal;
- middle_child = middle_internal;
- right_child = right_internal;
- left_nrec = &(left_internal->nrec);
- middle_nrec = &(middle_internal->nrec);
- right_nrec = &(right_internal->nrec);
- left_native = left_internal->int_native;
- middle_native = middle_internal->int_native;
- right_native = right_internal->int_native;
- left_node_ptrs = left_internal->node_ptrs;
- middle_node_ptrs = middle_internal->node_ptrs;
- right_node_ptrs = right_internal->node_ptrs;
- } /* end if */
- else {
- H5B2_leaf_t *left_leaf; /* Pointer to left leaf node */
- H5B2_leaf_t *middle_leaf; /* Pointer to middle leaf node */
- H5B2_leaf_t *right_leaf; /* Pointer to right leaf node */
-
- /* Setup information for unlocking child nodes */
- child_class = H5AC_BT2_LEAF;
- left_addr = internal->node_ptrs[idx].addr;
- right_addr = internal->node_ptrs[idx+2].addr;
-
- /* Lock left & right B-tree child nodes */
- if (NULL == (left_leaf = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node")
- if (NULL == (right_leaf = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx+2].node_nrec), internal->shared, H5AC_WRITE)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node")
-
- /* Create new empty "middle" leaf node */
- internal->node_ptrs[idx+1].all_nrec=internal->node_ptrs[idx+1].node_nrec=0;
- if(H5B2_create_leaf(f, dxpl_id, internal->shared, &(internal->node_ptrs[idx+1]))<0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new leaf node")
-
- /* Setup information for unlocking middle child node */
- middle_addr = internal->node_ptrs[idx+1].addr;
-
- /* Lock "middle" leaf node */
- if (NULL == (middle_leaf = H5AC_protect(f, dxpl_id, child_class, middle_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node")
-
- /* More setup for accessing child node information */
- left_child = left_leaf;
- middle_child = middle_leaf;
- right_child = right_leaf;
- left_nrec = &(left_leaf->nrec);
- middle_nrec = &(middle_leaf->nrec);
- right_nrec = &(right_leaf->nrec);
- left_native = left_leaf->leaf_native;
- middle_native = middle_leaf->leaf_native;
- right_native = right_leaf->leaf_native;
- } /* end else */
-
- /* Redistribute records */
- {
- /* Compute new # of records in each node */
- unsigned total_nrec = *left_nrec + *right_nrec + 1;
- unsigned new_middle_nrec = (total_nrec-2)/3;
- unsigned new_left_nrec = ((total_nrec-2)-new_middle_nrec)/2;
- unsigned new_right_nrec = (total_nrec-2)-(new_left_nrec+new_middle_nrec);
-
- /* Fill new middle node */
- {
- unsigned curr_middle_idx=0;
-
- /* Copy record(s) from left node to proper location */
- if(new_left_nrec<(*left_nrec-1)) {
- curr_middle_idx=*left_nrec-(new_left_nrec+1);
- HDmemcpy(H5B2_NAT_NREC(middle_native,shared,0),H5B2_NAT_NREC(left_native,shared,(new_left_nrec+1)),shared->type->nrec_size*curr_middle_idx);
- } /* end if */
-
- /* Copy record from parent node to proper location */
- HDmemcpy(H5B2_NAT_NREC(middle_native,shared,curr_middle_idx),H5B2_INT_NREC(internal,shared,idx),shared->type->nrec_size);
- curr_middle_idx++;
-
- /* Copy record(s) from right node to proper location */
- if(new_right_nrec<(*right_nrec-1))
- HDmemcpy(H5B2_NAT_NREC(middle_native,shared,curr_middle_idx),H5B2_NAT_NREC(right_native,shared,0),shared->type->nrec_size*(*right_nrec-(new_right_nrec+1)));
-
- /* Copy node pointers from left and right nodes into middle node */
- if(depth>1) {
- hsize_t moved_nrec; /* Total number of records moved, for internal redistrib */
- unsigned move_nptrs; /* Number of node pointers to move */
- unsigned u; /* Local index variable */
-
- /* Start tracking the total number of records in middle node */
- middle_moved_nrec = new_middle_nrec;
-
- /* Copy node pointers from left node */
- move_nptrs = (*left_nrec-new_left_nrec);
- HDmemcpy(&(middle_node_ptrs[0]),&(left_node_ptrs[new_left_nrec+1]),sizeof(H5B2_node_ptr_t)*move_nptrs);
-
- /* Count the number of records being moved from the left node */
- for(u=0, moved_nrec=0; u<move_nptrs; u++)
- moved_nrec += middle_node_ptrs[u].all_nrec;
- left_moved_nrec -= (moved_nrec+(*left_nrec-new_left_nrec));
- middle_moved_nrec += moved_nrec;
-
- /* Copy node pointers from right node */
- move_nptrs = (*right_nrec-new_right_nrec);
- HDmemcpy(&(middle_node_ptrs[(*left_nrec-new_left_nrec)]),&(right_node_ptrs[0]),sizeof(H5B2_node_ptr_t)*move_nptrs);
-
- /* Count the number of records being moved from the right node */
- for(u=0, moved_nrec=0; u<move_nptrs; u++)
- moved_nrec += right_node_ptrs[u].all_nrec;
- right_moved_nrec -= (moved_nrec+(*right_nrec-new_right_nrec));
- middle_moved_nrec += moved_nrec;
-
- /* Slide node pointers in right node down */
- HDmemmove(&(right_node_ptrs[0]),&(right_node_ptrs[move_nptrs]),sizeof(H5B2_node_ptr_t)*(new_right_nrec+1));
- } /* end if */
-
- } /* end block */
-
- /* Update # of records in middle node */
- *middle_nrec=new_middle_nrec;
-
- /* Promote records to parent node from left & right nodes */
- HDmemcpy(H5B2_INT_NREC(internal,shared,idx),H5B2_NAT_NREC(left_native,shared,new_left_nrec),shared->type->nrec_size);
- HDmemcpy(H5B2_INT_NREC(internal,shared,idx+1),H5B2_NAT_NREC(right_native,shared,(*right_nrec-(new_right_nrec+1))),shared->type->nrec_size);
-
- /* Update # of records in left node */
- *left_nrec = new_left_nrec;
-
- /* Slide records in right node to proper position */
- HDmemmove(H5B2_NAT_NREC(right_native,shared,0),H5B2_NAT_NREC(right_native,shared,(*right_nrec-new_right_nrec)),shared->type->nrec_size*new_right_nrec);
-
- /* Update # of records in right node */
- *right_nrec = new_right_nrec;
- } /* end block */
-
- /* Update # of records in child nodes */
- internal->node_ptrs[idx].node_nrec = *left_nrec;
- internal->node_ptrs[idx+1].node_nrec = *middle_nrec;
- internal->node_ptrs[idx+2].node_nrec = *right_nrec;
-
- /* Update total # of records in child B-trees */
- if(depth>1) {
- internal->node_ptrs[idx].all_nrec += left_moved_nrec;
- internal->node_ptrs[idx+1].all_nrec = middle_moved_nrec;
- internal->node_ptrs[idx+2].all_nrec += right_moved_nrec;
- } /* end if */
- else {
- internal->node_ptrs[idx].all_nrec = internal->node_ptrs[idx].node_nrec;
- internal->node_ptrs[idx+1].all_nrec = internal->node_ptrs[idx+1].node_nrec;
- internal->node_ptrs[idx+2].all_nrec = internal->node_ptrs[idx+2].node_nrec;
- } /* end else */
-
-
- /* Update # of records in parent node */
- internal->nrec++;
-
- /* Mark parent as dirty */
- *internal_flags_ptr |= H5AC__DIRTIED_FLAG;
-
- /* Update grandparent info */
- curr_node_ptr->node_nrec++;
-
- /* Mark grandparent as dirty */
- *parent_cache_info_flags_ptr |= H5AC__DIRTIED_FLAG;
-
-#ifdef H5B2_DEBUG
- H5B2_assert_internal((hsize_t)0,shared,internal);
- if(depth>1) {
- H5B2_assert_internal2(internal->node_ptrs[idx].all_nrec,shared,left_child,middle_child);
- H5B2_assert_internal2(internal->node_ptrs[idx+1].all_nrec,shared,middle_child,left_child);
- H5B2_assert_internal2(internal->node_ptrs[idx+1].all_nrec,shared,middle_child,right_child);
- H5B2_assert_internal2(internal->node_ptrs[idx+2].all_nrec,shared,right_child,middle_child);
- } /* end if */
- else {
- H5B2_assert_leaf2(shared,left_child,middle_child);
- H5B2_assert_leaf2(shared,middle_child,right_child);
- H5B2_assert_leaf(shared,right_child);
- } /* end else */
-#endif /* H5B2_DEBUG */
-
- /* Unlock child nodes (marked as dirty) */
- if (H5AC_unprotect(f, dxpl_id, child_class, left_addr, left_child, H5AC__DIRTIED_FLAG) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
- if (H5AC_unprotect(f, dxpl_id, child_class, middle_addr, middle_child, H5AC__DIRTIED_FLAG) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
- if (H5AC_unprotect(f, dxpl_id, child_class, right_addr, right_child, H5AC__DIRTIED_FLAG) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
-
-done:
- FUNC_LEAVE_NOAPI(ret_value);
-} /* end H5B2_split2 */
-
-
-/*-------------------------------------------------------------------------
* Function: H5B2_redistribute3
*
* Purpose: Redistribute records between three nodes
@@ -2360,30 +2140,30 @@ H5B2_insert_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
/* Preemptively split/redistribute a node we will enter */
while(internal->node_ptrs[idx].node_nrec == split_nrec) {
/* Attempt to redistribute records among children */
- if(idx==0) { /* Left-most child */
- if(retries>0 && (internal->node_ptrs[idx+1].node_nrec < split_nrec)) {
- if(H5B2_redistribute2(f,dxpl_id,depth,internal,idx)<0)
+ if(idx == 0) { /* Left-most child */
+ if(retries > 0 && (internal->node_ptrs[idx+1].node_nrec < split_nrec)) {
+ if(H5B2_redistribute2(f, dxpl_id, depth, internal, idx) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
} /* end if */
else {
- if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,
- parent_cache_info_flags_ptr, internal,&internal_flags,idx)<0)
+ if(H5B2_split1(f, dxpl_id, depth, curr_node_ptr,
+ parent_cache_info_flags_ptr, internal, &internal_flags, idx) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
} /* end else */
} /* end if */
- else if(idx==internal->nrec) { /* Right-most child */
- if(retries>0 && (internal->node_ptrs[idx-1].node_nrec < split_nrec)) {
- if(H5B2_redistribute2(f,dxpl_id,depth,internal,(idx-1))<0)
+ else if(idx == internal->nrec) { /* Right-most child */
+ if(retries > 0 && (internal->node_ptrs[idx - 1].node_nrec < split_nrec)) {
+ if(H5B2_redistribute2(f, dxpl_id, depth, internal, (idx - 1)) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
} /* end if */
else {
- if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,
- parent_cache_info_flags_ptr, internal,&internal_flags,(idx-1))<0)
+ if(H5B2_split1(f, dxpl_id, depth, curr_node_ptr,
+ parent_cache_info_flags_ptr, internal, &internal_flags, idx) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
} /* end else */
} /* end if */
else { /* Middle child */
- if(retries>0 && ((internal->node_ptrs[idx+1].node_nrec < split_nrec) ||
+ if(retries > 0 && ((internal->node_ptrs[idx+1].node_nrec < split_nrec) ||
(internal->node_ptrs[idx-1].node_nrec < split_nrec))) {
if(H5B2_redistribute3(f,dxpl_id,depth,internal,&internal_flags,idx)<0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
@@ -2947,6 +2727,9 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
/* Preemptively merge/redistribute a node we will enter */
while(internal->node_ptrs[idx].node_nrec == merge_nrec) {
/* Attempt to redistribute records among children */
+ /* (NOTE: These 2-node redistributions should actually get the
+ * record to promote from the node with more records. - QAK)
+ */
if(idx == 0) { /* Left-most child */
if(retries > 0 && (internal->node_ptrs[idx + 1].node_nrec > merge_nrec)) {
if(H5B2_redistribute2(f, dxpl_id, depth, internal, idx) < 0)
diff --git a/src/H5B2pkg.h b/src/H5B2pkg.h
index cd81022..5c861b7 100644
--- a/src/H5B2pkg.h
+++ b/src/H5B2pkg.h
@@ -138,7 +138,7 @@ typedef struct H5B2_shared_t {
/* Information set by user */
unsigned split_percent; /* Percent full at which to split the node, when inserting */
unsigned merge_percent; /* Percent full at which to merge the node, when deleting */
- size_t node_size; /* Size of all nodes, in bytes */
+ size_t node_size; /* Size of B-tree nodes, in bytes */
size_t rrec_size; /* Size of "raw" (on disk) record, in bytes */
/* Derived information from user's information */
@@ -195,6 +195,14 @@ typedef struct {
unsigned depth; /* Depth of node to load */
} H5B2_int_load_ud1_t;
+#ifdef H5B2_TESTING
+/* Node information for testing */
+typedef struct {
+ unsigned depth; /* Depth of node */
+ unsigned nrec; /* Number of records in node */
+} H5B2_node_info_test_t;
+#endif /* H5B2_TESTING */
+
/*****************************/
/* Package Private Variables */
@@ -298,6 +306,11 @@ H5_DLL herr_t H5B2_leaf_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
#ifdef H5B2_TESTING
H5_DLL herr_t H5B2_get_root_addr_test(H5F_t *f, hid_t dxpl_id,
const H5B2_class_t *type, haddr_t addr, haddr_t *root_addr);
+H5_DLL int H5B2_get_node_depth_test(H5F_t *f, hid_t dxpl_id,
+ const H5B2_class_t *type, haddr_t addr, void *udata);
+H5_DLL herr_t H5B2_get_node_info_test(H5F_t *f, hid_t dxpl_id,
+ const H5B2_class_t *type, haddr_t addr, void *udata,
+ H5B2_node_info_test_t *ninfo);
#endif /* H5B2_TESTING */
#endif /* _H5B2pkg_H */
diff --git a/src/H5B2private.h b/src/H5B2private.h
index cda4df0..d095e83 100644
--- a/src/H5B2private.h
+++ b/src/H5B2private.h
@@ -105,7 +105,11 @@ struct H5B2_class_t {
/* v2 B-tree metadata statistics info */
typedef struct H5B2_stat_t {
- int none; /* No information yet */
+ unsigned depth; /* Depth of B-tree */
+ unsigned nrecords; /* Number of records */
+ size_t branch_nrec; /* Number of records which fit into an internal "branch" node */
+ size_t twig_nrec; /* Number of records which fit into an internal "twig" node */
+ size_t leaf_nrec; /* Number of records which fit into a leaf node */
} H5B2_stat_t;
/*****************************/
diff --git a/src/H5B2stat.c b/src/H5B2stat.c
index b00df55..1251195 100644
--- a/src/H5B2stat.c
+++ b/src/H5B2stat.c
@@ -86,6 +86,7 @@ H5B2_stat_info(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
haddr_t addr, H5B2_stat_t *info)
{
H5B2_t *bt2 = NULL; /* Pointer to the B-tree header */
+ H5B2_shared_t *shared; /* Pointer to B-tree's shared information */
herr_t ret_value = SUCCEED; /* Return value */
FUNC_ENTER_NOAPI_NOINIT(H5B2_stat_info)
@@ -100,8 +101,15 @@ H5B2_stat_info(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
if(NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_READ)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header")
-/* XXX: Fill in metadata statistics for the heap */
- info = info; /* Quiet compiler for now) */
+ /* Get pointer to reference counted shared B-tree info */
+ shared = H5RC_GET_OBJ(bt2->shared);
+
+ /* Get information about the B-tree */
+ info->depth = bt2->depth;
+ info->nrecords = bt2->root.all_nrec;
+ info->branch_nrec = shared->branch_nrec;
+ info->twig_nrec = shared->twig_nrec;
+ info->leaf_nrec = shared->leaf_nrec;
done:
/* Release B-tree header node */
diff --git a/src/H5B2test.c b/src/H5B2test.c
index 1844e75..3ba4a34 100644
--- a/src/H5B2test.c
+++ b/src/H5B2test.c
@@ -239,7 +239,7 @@ H5B2_test_debug(FILE *stream, const H5F_t UNUSED *f, hid_t UNUSED dxpl_id,
/*-------------------------------------------------------------------------
- * Function: H5B2_get_root_addr
+ * Function: H5B2_get_root_addr_test
*
* Purpose: Retrieve the root node's address
*
@@ -282,3 +282,182 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* H5B2_get_root_addr_test() */
+
+/*-------------------------------------------------------------------------
+ * Function: H5B2_get_node_info_test
+ *
+ * Purpose: Determine information about a node holding a record in the B-tree
+ *
+ * Return: Success: non-negative
+ * Failure: negative
+ *
+ * Programmer: Quincey Koziol
+ * Thursday, August 31, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_get_node_info_test(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
+ void *udata, H5B2_node_info_test_t *ninfo)
+{
+ H5B2_t *bt2=NULL; /* Pointer to the B-tree header */
+ H5RC_t *bt2_shared=NULL; /* Pointer to ref-counter for shared B-tree info */
+ H5B2_shared_t *shared; /* Pointer to B-tree's shared information */
+ hbool_t incr_rc=FALSE; /* Flag to indicate that we've incremented the B-tree's shared info reference count */
+ H5B2_node_ptr_t curr_node_ptr; /* Node pointer info for current node */
+ unsigned depth; /* Current depth of the tree */
+ int cmp; /* Comparison value of records */
+ unsigned idx; /* Location of record which matches key */
+ herr_t ret_value = SUCCEED; /* Return value */
+
+ FUNC_ENTER_NOAPI(H5B2_get_node_info_test, FAIL)
+
+ /* Check arguments. */
+ HDassert(f);
+ HDassert(type);
+ HDassert(H5F_addr_defined(addr));
+
+ /* Look up the B-tree header */
+ if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_READ)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header")
+
+ /* Safely grab pointer to reference counted shared B-tree info, so we can release the B-tree header if necessary */
+ bt2_shared=bt2->shared;
+ H5RC_INC(bt2_shared);
+ incr_rc=TRUE;
+
+ /* Make copy of the root node pointer to start search with */
+ curr_node_ptr = bt2->root;
+
+ /* Current depth of the tree */
+ depth = bt2->depth;
+
+ /* Release header */
+ if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info")
+ bt2 = NULL;
+
+ /* Get the pointer to the shared B-tree info */
+ shared = H5RC_GET_OBJ(bt2_shared);
+ HDassert(shared);
+
+ /* Check for empty tree */
+ if(curr_node_ptr.node_nrec==0)
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records")
+
+ /* Walk down B-tree to find record or leaf node where record is located */
+ cmp = -1;
+ while(depth > 0 && cmp != 0) {
+ H5B2_internal_t *internal; /* Pointer to internal node in B-tree */
+ H5B2_node_ptr_t next_node_ptr; /* Node pointer info for next node */
+
+ /* Lock B-tree current node */
+ if(NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, curr_node_ptr.addr, curr_node_ptr.node_nrec, depth, H5AC_READ)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
+
+ /* Locate node pointer for child */
+ cmp = H5B2_locate_record(shared->type, internal->nrec, shared->nat_off, internal->int_native, udata, &idx);
+ if(cmp > 0)
+ idx++;
+
+ if(cmp != 0) {
+ /* Get node pointer for next node to search */
+ next_node_ptr = internal->node_ptrs[idx];
+
+ /* Unlock current node */
+ if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
+
+ /* Set pointer to next node to load */
+ curr_node_ptr = next_node_ptr;
+ } /* end if */
+ else {
+ /* Unlock current node */
+ if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
+
+ /* Fill in information about the node */
+ ninfo->depth = depth;
+ ninfo->nrec = curr_node_ptr.node_nrec;
+
+ /* Indicate success */
+ HGOTO_DONE(SUCCEED)
+ } /* end else */
+
+ /* Decrement depth we're at in B-tree */
+ depth--;
+ } /* end while */
+
+ {
+ H5B2_leaf_t *leaf; /* Pointer to leaf node in B-tree */
+
+ /* Lock B-tree leaf node */
+ if(NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr.addr, &(curr_node_ptr.node_nrec), bt2_shared, H5AC_READ)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
+
+ /* Locate record */
+ cmp = H5B2_locate_record(shared->type, leaf->nrec, shared->nat_off, leaf->leaf_native, udata, &idx);
+
+ /* Unlock current node */
+ if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
+
+ /* Indicate the depth that the record was found */
+ if(cmp != 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record not in B-tree")
+ } /* end block */
+
+ /* Fill in information about the leaf node */
+ ninfo->depth = depth;
+ ninfo->nrec = curr_node_ptr.node_nrec;
+
+done:
+ /* Check if we need to decrement the reference count for the B-tree's shared info */
+ if(incr_rc)
+ H5RC_DEC(bt2_shared);
+
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_get_node_info_test() */
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B2_get_node_depth_test
+ *
+ * Purpose: Determine the depth of a node holding a record in the B-tree
+ *
+ * Note: Just a simple wrapper around the H5B2_get_node_info_test() routine
+ *
+ * Return: Success: non-negative depth of the node where the record
+ * was found
+ * Failure: negative
+ *
+ * Programmer: Quincey Koziol
+ * Saturday, August 26, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+int
+H5B2_get_node_depth_test(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
+ void *udata)
+{
+ H5B2_node_info_test_t ninfo; /* Node information */
+ int ret_value; /* Return information */
+
+ FUNC_ENTER_NOAPI(H5B2_get_node_depth_test, FAIL)
+
+ /* Check arguments. */
+ HDassert(f);
+ HDassert(type);
+ HDassert(H5F_addr_defined(addr));
+
+ /* Get information abou the node */
+ if(H5B2_get_node_info_test(f, dxpl_id, type, addr, udata, &ninfo) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "error looking up node info")
+
+ /* Set return value */
+ ret_value = ninfo.depth;
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_get_node_depth_test() */
+