From d1e7ac416e81d70c98a36f7ab265bf58e2a224c4 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Mon, 4 Sep 2006 11:37:41 -0500 Subject: [svn-r12638] Description: Split edge nodes in the tree with a 1->2 node split, instead of a 2->3 node split, which creates a more dense tree when a pattern of record insertions occurs (because it leaves behind full nodes instead of 2/3 full nodes). Tested: FreeBSD/32 4.11 (sleipnir) Linux/64 2.4 (mir) Linux/32 2.4 (heping) Solaris/64 2.9 (shanti) --- src/H5B2.c | 7 +- src/H5B2dbg.c | 5 +- src/H5B2int.c | 549 ++--- src/H5B2pkg.h | 15 +- src/H5B2private.h | 6 +- src/H5B2stat.c | 12 +- src/H5B2test.c | 181 +- test/btree2.c | 5804 +++++++++++++++++++++++++++++++++-------------------- 8 files changed, 4020 insertions(+), 2559 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; utype->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() */ + diff --git a/test/btree2.c b/test/btree2.c index 66613a1..3a999de 100644 --- a/test/btree2.c +++ b/test/btree2.c @@ -33,13 +33,13 @@ const char *FILENAME[] = { NULL }; -#define INSERT_SPLIT_ROOT_NREC 80 +#define INSERT_SPLIT_ROOT_NREC 63 #define INSERT_MANY (500*1000) #define FIND_MANY (INSERT_MANY/100) -#define FIND_NEIGHBOR 1000 -#define DELETE_SMALL 10 +#define FIND_NEIGHBOR 2000 +#define DELETE_SMALL 20 #define DELETE_MEDIUM 200 -#define DELETE_LARGE 1000 +#define DELETE_LARGE 2000 /*------------------------------------------------------------------------- @@ -397,65 +397,99 @@ test_insert_split_root(hid_t fapl) hsize_t record; /* Record to insert into tree */ hsize_t idx; /* Index within B-tree, for iterator */ haddr_t bt2_addr; /* Address of B-tree created */ + H5B2_stat_t bt2_stat; /* Statistics about B-tree created */ + int rec_depth; /* Depth of record in B-tree */ unsigned u; /* Local index variable */ herr_t ret; /* Generic error return value */ h5_fixname(FILENAME[0], fapl, filename, sizeof filename); /* Create the file to work on */ - if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR + if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0) + STACK_ERROR /* Get a pointer to the internal file object */ - if (NULL==(f=H5I_object(file))) { - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(NULL == (f = H5I_object(file))) + STACK_ERROR /* - * Test v2 B-tree creation + * Test inserting enough records into v2 B-tree to split the root node */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + TESTING("B-tree insert: split root"); /* - * Test inserting many records into v2 B-tree + * Test v2 B-tree creation */ - TESTING("B-tree insert: split root"); + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR - for(u=0; ur)"); /* - * Test inserting many records into v2 B-tree + * Create v2 B-tree */ - TESTING("B-tree insert: redistribute 2 leaves in level 1 B-tree (l->r)"); + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Insert enough records to force root to split into 2 leaves */ - for(u=0; ul)"); /* - * Test inserting many records into v2 B-tree + * Create v2 B-tree */ - TESTING("B-tree insert: redistribute 2 leaves in level 1 B-tree (r->l)"); + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Insert enough records to force root to split into 2 leaves */ - for(u=0; ur)"); /* - * Test inserting many records into v2 B-tree + * Create v2 B-tree */ - TESTING("B-tree insert: split 2 leaves to 3 in level 1 B-tree (l->r)"); + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Insert enough records to force root to split into 2 leaves */ - for(u=0; ul)"); /* - * Test inserting many records into v2 B-tree + * Create v2 B-tree */ - TESTING("B-tree insert: split 2 leaves to 3 in level 1 B-tree (r->l)"); + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Insert enough records to force root to split into 2 leaves */ - for(u=0; u1 split and then a + * 2 node redistribution on left leaf + */ + for(u = 0; u < (INSERT_SPLIT_ROOT_NREC / 2) + 1; u++) { + record = u; + if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) + FAIL_STACK_ERROR + } /* end for */ + + /* Check up on B-tree */ + if(H5B2_stat_info(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &bt2_stat) < 0) + FAIL_STACK_ERROR + if(bt2_stat.depth != 2) + TEST_ERROR + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + 1)) + TEST_ERROR + record = 930; /* Record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 2) + TEST_ERROR + record = 47; /* Left-most record in left internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 0; + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 0) + TEST_ERROR PASSED(); TESTING("B-tree insert: redistrib middle leaf in level 2 B-tree"); - /* Add more records to middle leaf, to force a 3 node redistribution on middle leaf */ - for(u=0; u3 node split on left leaf */ - for(u=0; u2 node split on left leaf */ + record = 0; + if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) + FAIL_STACK_ERROR + + /* Check up on B-tree */ + if(H5B2_stat_info(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &bt2_stat) < 0) + FAIL_STACK_ERROR + if(bt2_stat.depth != 2) + TEST_ERROR + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + 1)) + TEST_ERROR + record = 883; /* Record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 2) + TEST_ERROR + record = 63; /* Next-to-left-most record in left internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 32; /* Left-most record in left internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 0; /* Left-most record in left-most leaf */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 0) + TEST_ERROR PASSED(); TESTING("B-tree insert: split middle leaf in level 2 B-tree"); - /* Add more records to middle leaf, to force a 3->4 node split on middle leaf */ - for(u=0; u4 node split on middle leaf */ + record = (INSERT_SPLIT_ROOT_NREC * 8) + 1; + if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) + FAIL_STACK_ERROR + + /* Check up on B-tree */ + if(H5B2_stat_info(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &bt2_stat) < 0) + FAIL_STACK_ERROR + if(bt2_stat.depth != 2) + TEST_ERROR + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + 2)) + TEST_ERROR + record = 883; /* Record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 2) + TEST_ERROR + record = 488; /* Left-most record of 3->4 split in left internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 536; /* Middle record of 3->4 split in left internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 583; /* Right-most record of 3->4 split in left internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 506; /* Record in leaf node just after insertion point */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 0) + TEST_ERROR /* Iterate over B-tree to check records have been inserted correctly */ idx = 0; - if(H5B2_iterate(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, iter_cb, &idx)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_iterate(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, iter_cb, &idx) < 0) + FAIL_STACK_ERROR /* Make certain that the index is correct */ - if(idx != (INSERT_SPLIT_ROOT_NREC*14)) TEST_ERROR + if(idx != ((INSERT_SPLIT_ROOT_NREC * 28) + 2)) + TEST_ERROR - PASSED(); + /* Close file */ + if(H5Fclose(file) < 0) + FAIL_STACK_ERROR - if (H5Fclose(file)<0) TEST_ERROR + PASSED(); return 0; @@ -1373,73 +1906,163 @@ test_insert_level2_2internal_redistrib(hid_t fapl) H5F_t *f=NULL; hsize_t record; /* Record to insert into tree */ haddr_t bt2_addr; /* Address of B-tree created */ + H5B2_stat_t bt2_stat; /* Statistics about B-tree created */ + int rec_depth; /* Depth of record in B-tree */ hsize_t idx; /* Index within B-tree, for iterator */ unsigned u; /* Local index variable */ h5_fixname(FILENAME[0], fapl, filename, sizeof filename); /* Create the file to work on */ - if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR + if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0) + STACK_ERROR /* Get a pointer to the internal file object */ - if (NULL==(f=H5I_object(file))) { - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(NULL == (f = H5I_object(file))) + STACK_ERROR /* - * Create v2 B-tree + * Test inserting many records into v2 B-tree */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + TESTING("B-tree insert: redist. 2 internal (r->l) in level 2 B-tree"); /* - * Test inserting many records into v2 B-tree + * Create v2 B-tree */ - TESTING("B-tree insert: redist. 2 internal (r->l) in level 2 B-tree"); + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Insert enough records to force root to split into 2 internal nodes */ - /* Also forces right-most internal node to redistribute */ - for(u=0; ur) in level 2 B-tree"); + /* Check up on B-tree */ + if(H5B2_stat_info(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &bt2_stat) < 0) + FAIL_STACK_ERROR + if(bt2_stat.depth != 2) + TEST_ERROR + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 41) + 1)) + TEST_ERROR + record = 1636; /* Record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 2) + TEST_ERROR + record = 376; /* Left-most record in left internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 314; /* Left-most record in left leaf node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 0) + TEST_ERROR + /* Force left-most internal node to redistribute */ - for(u=0; ul)"); /* - * Test inserting many records into v2 B-tree + * Create v2 B-tree */ - TESTING("B-tree insert: split 2 internals to 3 in level 2 B-tree (r->l)"); + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Insert enough records to force root to split into 2 internal nodes */ - /* Also forces right-most internal node to split */ - for(u=0; u<(INSERT_SPLIT_ROOT_NREC*21); u++) { - record=u+(INSERT_SPLIT_ROOT_NREC*8); - if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } - } + /* (And fill up two child internal nodes) */ + for(u = 0; u < (INSERT_SPLIT_ROOT_NREC * 55); u++) { + record = u + (INSERT_SPLIT_ROOT_NREC * 10) + (INSERT_SPLIT_ROOT_NREC / 4) - 2; + if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) + FAIL_STACK_ERROR + } /* end for */ + + /* Check up on B-tree */ + if(H5B2_stat_info(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &bt2_stat) < 0) + FAIL_STACK_ERROR + if(bt2_stat.depth != 2) + TEST_ERROR + if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 55)) + TEST_ERROR + record = 2406; /* Record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 2) + TEST_ERROR + record = 4076; /* Right-most record in right internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 4107; /* Right-most record in right leaf node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 0) + TEST_ERROR + + /* Insert record to split right-most internal node */ + record = u + (INSERT_SPLIT_ROOT_NREC * 10) + (INSERT_SPLIT_ROOT_NREC / 4) - 2; + if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) + FAIL_STACK_ERROR + + /* Check up on B-tree */ + if(H5B2_stat_info(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &bt2_stat) < 0) + FAIL_STACK_ERROR + if(bt2_stat.depth != 2) + TEST_ERROR + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 55) + 1)) + TEST_ERROR + record = 2406; /* Left record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 2) + TEST_ERROR + record = 3288; /* Right record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 2) + TEST_ERROR + record = 4076; /* Right-most record in right internal node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 4108; /* Right-most record in right leaf node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 0) + TEST_ERROR PASSED(); TESTING("B-tree insert: split 2 internals to 3 in level 2 B-tree (l->r)"); - /* Force left-most internal node to split */ - for(u=0; ul)"); /* * Test v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Create level-1 B-tree with 3 leaves */ - for(u=0; ul)"); - for(u=0; u < (INSERT_SPLIT_ROOT_NREC/2); u++) { - record = (INSERT_SPLIT_ROOT_NREC*2)-(u+1); + for(u = 0; u < 8; u++) { + record = (INSERT_SPLIT_ROOT_NREC * 2) - (u + 1); rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != ((INSERT_SPLIT_ROOT_NREC*2)-(u+1))) TEST_ERROR + if(rrecord != ((INSERT_SPLIT_ROOT_NREC * 2) - (u + 1))) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != ((INSERT_SPLIT_ROOT_NREC*2)-(u+1))) TEST_ERROR + if(nrec != ((INSERT_SPLIT_ROOT_NREC * 2) - (u + 1))) + TEST_ERROR } /* end for */ + /* Check record values in root of B-tree */ + record = 62; /* Left record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 90; /* Right record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + PASSED(); /* Attempt to remove enough records from left leaf of a level-1 B-tree to force redistribution */ TESTING("B-tree remove: redistribute 2 leaves in level-1 B-tree (l->r)"); - for(u=0; u < (INSERT_SPLIT_ROOT_NREC/4); u++) { + for(u = 0; u < 39; u++) { record = u; rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != u) TEST_ERROR + if(rrecord != u) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != (((INSERT_SPLIT_ROOT_NREC*2)-(INSERT_SPLIT_ROOT_NREC/2))-(u+1))) TEST_ERROR + if(nrec != (((INSERT_SPLIT_ROOT_NREC * 2) - 8) - (u + 1))) + TEST_ERROR } /* end for */ + /* Check record values in root of B-tree */ + record = 64; /* Left record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 90; /* Right record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + PASSED(); /* Attempt to remove enough records from middle leaf of a level-1 B-tree to force redistribution */ TESTING("B-tree remove: redistribute 3 leaves in level-1 B-tree"); - for(u=0; u < (INSERT_SPLIT_ROOT_NREC/8); u++) { - record = ((INSERT_SPLIT_ROOT_NREC/4)*3) + u; + for(u = 0; u < 2; u++) { + record = INSERT_SPLIT_ROOT_NREC + 2 + u; rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != (((INSERT_SPLIT_ROOT_NREC/4)*3) + u)) TEST_ERROR + if(rrecord != (INSERT_SPLIT_ROOT_NREC + 2 + u)) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != (((INSERT_SPLIT_ROOT_NREC*2)-(3*(INSERT_SPLIT_ROOT_NREC/4)))-(u+1))) TEST_ERROR + if(nrec != ((((INSERT_SPLIT_ROOT_NREC * 2) - 47)) - (u + 1))) + TEST_ERROR } /* end for */ - PASSED(); + /* Check record values in root of B-tree */ + record = 64; /* Left record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR + record = 91; /* Right record in root node */ + if((rec_depth = H5B2_get_node_depth_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)) < 0) + FAIL_STACK_ERROR + if(rec_depth != 1) + TEST_ERROR - if (H5Fclose(file)<0) TEST_ERROR + /* Close file */ + if(H5Fclose(file) < 0) + TEST_ERROR + + PASSED(); return 0; @@ -2649,125 +3598,154 @@ test_remove_level1_2leaf_merge(hid_t fapl) hsize_t nrec; /* Number of records in B-tree */ haddr_t bt2_addr; /* Address of B-tree created */ haddr_t root_addr; /* Address of root of B-tree created */ + H5B2_node_info_test_t ninfo; /* B-tree node info */ + int rec_depth; /* Depth of record in B-tree */ unsigned u; /* Local index variable */ h5_fixname(FILENAME[0], fapl, filename, sizeof filename); /* Create the file to work on */ - if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR + if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0) + STACK_ERROR /* Get a pointer to the internal file object */ - if (NULL==(f=H5I_object(file))) { - H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR - } + if(NULL == (f = H5I_object(file))) + STACK_ERROR + + TESTING("B-tree remove: merge 2 leaves to 1 in level-1 B-tree (r->l)"); /* * Test v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Create level-1 B-tree with 3 leaves */ - for(u=0; ul)"); - for(u=0; u < INSERT_SPLIT_ROOT_NREC; u++) { - record = (INSERT_SPLIT_ROOT_NREC*2)-(u+1); + for(u = 0; u < (INSERT_SPLIT_ROOT_NREC / 4); u++) { + record = (INSERT_SPLIT_ROOT_NREC * 2) - (u + 1); rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != ((INSERT_SPLIT_ROOT_NREC*2)-(u+1))) TEST_ERROR + if(rrecord != ((INSERT_SPLIT_ROOT_NREC * 2) - (u + 1))) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != ((INSERT_SPLIT_ROOT_NREC*2)-(u+1))) TEST_ERROR + if(nrec != ((INSERT_SPLIT_ROOT_NREC * 2) - (u + 1))) + TEST_ERROR } /* end for */ + /* Check record values in root of B-tree */ + record = 62; /* Left record in root node */ + if(H5B2_get_node_info_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, &ninfo) < 0) + FAIL_STACK_ERROR + if(ninfo.depth != 1) + TEST_ERROR + if(ninfo.nrec != 1) + TEST_ERROR + PASSED(); /* Attempt to remove enough records from left leaf of a level-1 B-tree to force redistribution */ TESTING("B-tree remove: merge 2 leaves to 1 in level-1 B-tree (l->r)"); /* Fill B-tree back up */ - for(u=0; u1 merge"); /* - * Test v2 B-tree creation + * v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Create level-1 B-tree with 3 leaves */ - for(u=0; u1 merge"); /* Remove records from right leaf until its ready to redistribute */ - for(u=0; u < 66; u++) { - record = (INSERT_SPLIT_ROOT_NREC*2)-(u+1); + for(u = 0; u < 14; u++) { + record = (INSERT_SPLIT_ROOT_NREC * 2) - (u + 1); rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != ((INSERT_SPLIT_ROOT_NREC*2)-(u+1))) TEST_ERROR + if(rrecord != ((INSERT_SPLIT_ROOT_NREC * 2) - (u + 1))) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != ((INSERT_SPLIT_ROOT_NREC*2)-(u+1))) TEST_ERROR + if(nrec != ((INSERT_SPLIT_ROOT_NREC * 2) - (u + 1))) + TEST_ERROR } /* end for */ - record = 68; + record = 87; rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != 68) TEST_ERROR + if(rrecord != 87) + TEST_ERROR + + /* Check record values in root of B-tree */ + record = 62; /* Middle record in root node */ + if(H5B2_get_node_info_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, &ninfo) < 0) + FAIL_STACK_ERROR + if(ninfo.depth != 1) + TEST_ERROR + if(ninfo.nrec != 1) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != (INSERT_SPLIT_ROOT_NREC*2)-67) TEST_ERROR + if(nrec != (INSERT_SPLIT_ROOT_NREC * 2) - 15) + TEST_ERROR - PASSED(); + /* Close file */ + if(H5Fclose(file) < 0) + TEST_ERROR - if (H5Fclose(file)<0) TEST_ERROR + PASSED(); return 0; @@ -3501,109 +4608,118 @@ test_remove_level1_promote_3leaf_merge(hid_t fapl) hsize_t nrec; /* Number of records in B-tree */ haddr_t bt2_addr; /* Address of B-tree created */ haddr_t root_addr; /* Address of root of B-tree created */ + int rec_depth; /* Depth of record in B-tree */ + H5B2_node_info_test_t ninfo; /* B-tree node info */ unsigned u; /* Local index variable */ h5_fixname(FILENAME[0], fapl, filename, sizeof filename); /* Create the file to work on */ - if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR + if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0) + STACK_ERROR /* Get a pointer to the internal file object */ - if (NULL==(f=H5I_object(file))) { - H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR - } + if(NULL == (f = H5I_object(file))) + STACK_ERROR + + TESTING("B-tree remove: promote from leaf of level-1 B-tree w/3->2 merge"); /* - * Test v2 B-tree creation + * v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR - /* Create level-1 B-tree with 3 leaves */ - for(u=0; u2 merge"); - /* Remove records from right leaf until its ready to redistribute */ - for(u=0; u < 81; u++) { - record = 43 + u; + /* Remove records from middle leaf until its ready to redistribute */ + for(u = 0; u < 50; u++) { + record = ((3 * INSERT_SPLIT_ROOT_NREC) / 2) - (u + 1); rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != (43 + u)) TEST_ERROR + if(rrecord != (((3 * INSERT_SPLIT_ROOT_NREC) / 2) - (u + 1))) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != ((INSERT_SPLIT_ROOT_NREC*2)-(u+1))) TEST_ERROR + if(nrec != ((INSERT_SPLIT_ROOT_NREC * 2) - (u + 1))) + TEST_ERROR } /* end for */ - record = 26; + record = 25; rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != 26) TEST_ERROR + if(rrecord != 25) + TEST_ERROR + + /* Check record values in root of B-tree */ + record = 37; /* Right record in root node */ + if(H5B2_get_node_info_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, &ninfo) < 0) + FAIL_STACK_ERROR + if(ninfo.depth != 1) + TEST_ERROR + if(ninfo.nrec != 1) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != (INSERT_SPLIT_ROOT_NREC*2)-82) TEST_ERROR + if(nrec != (INSERT_SPLIT_ROOT_NREC * 2) - 51) + TEST_ERROR - PASSED(); + /* Close file */ + if(H5Fclose(file) < 0) + TEST_ERROR - if (H5Fclose(file)<0) TEST_ERROR + PASSED(); return 0; @@ -3640,86 +4756,109 @@ test_remove_level1_collapse(hid_t fapl) hsize_t nrec; /* Number of records in B-tree */ haddr_t bt2_addr; /* Address of B-tree created */ haddr_t root_addr; /* Address of root of B-tree created */ + H5B2_node_info_test_t ninfo; /* B-tree node info */ unsigned u; /* Local index variable */ h5_fixname(FILENAME[0], fapl, filename, sizeof filename); /* Create the file to work on */ - if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR + if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0) + STACK_ERROR /* Get a pointer to the internal file object */ - if (NULL==(f=H5I_object(file))) { - H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR - } + if(NULL == (f = H5I_object(file))) + STACK_ERROR + + TESTING("B-tree remove: collapse level-1 B-tree back to level-0"); /* - * Test v2 B-tree creation + * v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Create level-1 B-tree with 2 leaves */ - for(u=0; ur)"); /* - * Test v2 B-tree creation + * v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Create level-2 B-tree with 3 internal nodes */ - for(u=0; ur)"); - for(u=0; u < (INSERT_SPLIT_ROOT_NREC*5); u++) { + for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC * 20) + 15); u++) { record = u; rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != u) TEST_ERROR + if(rrecord != u) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != ((INSERT_SPLIT_ROOT_NREC*21)-(u+1))) TEST_ERROR + if(nrec != (((INSERT_SPLIT_ROOT_NREC * 55) + 1) - (u + 1))) + TEST_ERROR } /* end for */ - PASSED(); + record = 2645; /* Middle record in root node */ + if(H5B2_get_node_info_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, &ninfo) < 0) + FAIL_STACK_ERROR + if(ninfo.depth != 2) + TEST_ERROR + if(ninfo.nrec != 1) + TEST_ERROR - if (H5Fclose(file)<0) TEST_ERROR + /* Close file */ + if(H5Fclose(file) < 0) + TEST_ERROR + + PASSED(); return 0; @@ -4630,86 +5930,98 @@ test_remove_level2_2internal_merge_right(hid_t fapl) hsize_t nrec; /* Number of records in B-tree */ haddr_t bt2_addr; /* Address of B-tree created */ haddr_t root_addr; /* Address of root of B-tree created */ + int rec_depth; /* Depth of record in B-tree */ + H5B2_node_info_test_t ninfo; /* B-tree node info */ unsigned u; /* Local index variable */ h5_fixname(FILENAME[0], fapl, filename, sizeof filename); /* Create the file to work on */ - if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR + if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0) + STACK_ERROR /* Get a pointer to the internal file object */ - if (NULL==(f=H5I_object(file))) { - H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR - } + if(NULL == (f = H5I_object(file))) + STACK_ERROR + + TESTING("B-tree remove: merge 2 internal nodes to 1 in level-2 B-tree (r->l)"); /* - * Test v2 B-tree creation + * v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Create level-2 B-tree with 3 internal nodes */ - for(u=0; ul)"); - for(u=0; u < (INSERT_SPLIT_ROOT_NREC*6); u++) { - record = (INSERT_SPLIT_ROOT_NREC*21) - (u + 1); + for(u=0; u < ((INSERT_SPLIT_ROOT_NREC * 5) + 17); u++) { + record = ((INSERT_SPLIT_ROOT_NREC * 55) + 1) - (u + 1); rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(rrecord != ((INSERT_SPLIT_ROOT_NREC*21) - (u + 1))) TEST_ERROR + if(rrecord != (((INSERT_SPLIT_ROOT_NREC * 55) + 1) - (u + 1))) + TEST_ERROR - /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + /* Query the number of records in the B-tree */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != ((INSERT_SPLIT_ROOT_NREC*21)-(u+1))) TEST_ERROR + if(nrec != (((INSERT_SPLIT_ROOT_NREC * 55) + 1) - (u+ 1))) + TEST_ERROR } /* end for */ - PASSED(); + record = 1763; /* Middle record in root node */ + if(H5B2_get_node_info_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, &ninfo) < 0) + FAIL_STACK_ERROR + if(ninfo.depth != 2) + TEST_ERROR + if(ninfo.nrec != 1) + TEST_ERROR - if (H5Fclose(file)<0) TEST_ERROR + /* Close file */ + if(H5Fclose(file) < 0) + TEST_ERROR + + PASSED(); return 0; @@ -4746,86 +6058,98 @@ test_remove_level2_3internal_merge(hid_t fapl) hsize_t nrec; /* Number of records in B-tree */ haddr_t bt2_addr; /* Address of B-tree created */ haddr_t root_addr; /* Address of root of B-tree created */ + int rec_depth; /* Depth of record in B-tree */ + H5B2_node_info_test_t ninfo; /* B-tree node info */ unsigned u; /* Local index variable */ h5_fixname(FILENAME[0], fapl, filename, sizeof filename); /* Create the file to work on */ - if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR + if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0) + STACK_ERROR /* Get a pointer to the internal file object */ - if (NULL==(f=H5I_object(file))) { - H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR - } + if(NULL == (f = H5I_object(file))) + STACK_ERROR + + TESTING("B-tree remove: merge 3 internal nodes to 2 in level-2 B-tree"); /* - * Test v2 B-tree creation + * v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Create level-2 B-tree with 3 internal nodes */ - for(u=0; ul)"); /* - * Test v2 B-tree creation + * v2 B-tree creation */ - if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } + if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0) + FAIL_STACK_ERROR /* Create level-2 B-tree with 3 internal nodes */ - for(u=0; ul)"); - for(u=0; u < (INSERT_SPLIT_ROOT_NREC*12); u++) { - record = (INSERT_SPLIT_ROOT_NREC*21)-(u+1); + for(u = 0; u < (INSERT_SPLIT_ROOT_NREC * 32) + 17; u++) { + record = ((INSERT_SPLIT_ROOT_NREC * 55) + 1) - (u + 1); rrecord = HSIZET_MAX; - if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record, remove_cb, &rrecord) < 0) + FAIL_STACK_ERROR /* Make certain that the record value is correct */ - if(record != ((INSERT_SPLIT_ROOT_NREC*21)-(u+1))) TEST_ERROR + if(record != (((INSERT_SPLIT_ROOT_NREC * 55) + 1) - (u + 1))) + TEST_ERROR /* Query the number of records in the B-tree */ - if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { - H5_FAILED(); - H5Eprint_stack(H5E_DEFAULT, stdout); - goto error; - } /* end if */ + if(H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec) < 0) + FAIL_STACK_ERROR /* Make certain that the # of records is correct */ - if(nrec != ((INSERT_SPLIT_ROOT_NREC*21)-(u+1))) TEST_ERROR + if(nrec != (((INSERT_SPLIT_ROOT_NREC * 55) + 1) - (u + 1))) + TEST_ERROR } /* end for */ - PASSED(); + /* Check up on B-tree */ + if(H5B2_stat_info(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &bt2_stat) < 0) + FAIL_STACK_ERROR + if(bt2_stat.depth != 1) + TEST_ERROR - if (H5Fclose(file)<0) TEST_ERROR + /* Close file */ + if(H5Fclose(file) < 0) + TEST_ERROR + + PASSED(); return 0; @@ -4978,11 +6313,13 @@ test_remove_lots(hid_t fapl) hsize_t record; /* Record to insert into tree */ hsize_t rrecord; /* Record to remove from tree */ haddr_t bt2_addr; /* Address of B-tree created */ + haddr_t root_addr; /* Address of root of B-tree created */ time_t curr_time; /* Current time, for seeding random number generator */ hsize_t *records; /* Record #'s for random insertion */ unsigned u; /* Local index variable */ unsigned swap_idx; /* Location to swap with when shuffling */ hsize_t temp_rec; /* Temporary record */ + H5B2_stat_t bt2_stat; /* Statistics about B-tree created */ hsize_t nrec; /* Number of records in B-tree */ /* Initialize random number seed */ @@ -4993,8 +6330,14 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time); #endif /* QAK */ HDsrandom((unsigned long)curr_time); + /* + * Test removing many records into v2 B-tree + */ + TESTING("B-tree remove: create random level 4 B-tree and delete all records"); + /* Allocate space for the records */ - if((records = HDmalloc(sizeof(hsize_t)*INSERT_MANY))==NULL) TEST_ERROR + if((records = HDmalloc(sizeof(hsize_t)*INSERT_MANY))==NULL) + TEST_ERROR /* Initialize record #'s */ for(u=0; u