From 23b3a6a91b88e6cbc3474e83fba1e4eb62763126 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Tue, 5 Sep 2006 15:53:16 -0500 Subject: [svn-r12644] Description: Improve density of the B-tree further. For greater depths of B-trees, the gains are over 100%... Also, don't split internal nodes with 3->4 splits, use a 1->2 split instead, so that the density of the nodes around a split is maximized. Tested: Mac OS X/PPC 10.4 (amazon) Linux/32 2.6 (chicago) Linux/64 2.6 (chicago2) --- src/H5B2.c | 115 ++++---- src/H5B2cache.c | 82 ++---- src/H5B2dbg.c | 40 +-- src/H5B2int.c | 632 +++++++++++--------------------------------- src/H5B2pkg.h | 62 +++-- src/H5B2private.h | 3 - src/H5B2stat.c | 5 +- src/H5B2test.c | 10 +- test/btree2.c | 726 +++++++++++++++++++++++++++------------------------ tools/misc/h5debug.c | 78 ++---- 10 files changed, 696 insertions(+), 1057 deletions(-) diff --git a/src/H5B2.c b/src/H5B2.c index 7ee979b..8e66aa3 100644 --- a/src/H5B2.c +++ b/src/H5B2.c @@ -123,13 +123,12 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, /* Assign internal information */ HDmemset(&bt2->cache_info, 0, sizeof(H5AC_info_t)); - bt2->depth = 0; bt2->root.addr = HADDR_UNDEF; bt2->root.node_nrec = 0; bt2->root.all_nrec = 0; /* Initialize shared B-tree info */ - if(H5B2_shared_init(f, bt2, type, node_size, rrec_size, split_percent, merge_percent) < 0) + if(H5B2_shared_init(f, bt2, type, 0, node_size, rrec_size, split_percent, merge_percent) < 0) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create shared B-tree info") /* Allocate space for the header on disk */ @@ -184,7 +183,7 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header") /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(bt2->shared); + shared = H5RC_GET_OBJ(bt2->shared); HDassert(shared); /* Check if the root node is allocated yet */ @@ -197,21 +196,19 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, bt2_flags |= H5AC__DIRTIED_FLAG; } /* end if */ /* 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 > 1 && bt2->root.node_nrec == shared->split_brch_nrec)) { + else if(bt2->root.node_nrec == shared->node_info[shared->depth].split_nrec) { /* Split root node */ - if(H5B2_split_root(f, dxpl_id, bt2, &bt2_flags, bt2->shared) < 0) + if(H5B2_split_root(f, dxpl_id, bt2, &bt2_flags) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node") } /* end if */ /* Attempt to insert record into B-tree */ - if(bt2->depth > 0) { - if(H5B2_insert_internal(f, dxpl_id, bt2->shared, bt2->depth, &bt2_flags, &bt2->root, udata) < 0) + if(shared->depth > 0) { + if(H5B2_insert_internal(f, dxpl_id, bt2->shared, shared->depth, &bt2_flags, &bt2->root, udata) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node") } /* end if */ else { - if(H5B2_insert_leaf(f,dxpl_id,bt2->shared,&bt2->root, udata) < 0) + if(H5B2_insert_leaf(f, dxpl_id, bt2->shared, &bt2->root, udata) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node") } /* end else */ @@ -249,6 +246,7 @@ H5B2_iterate(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, H5B2_operator_t op, void *op_data) { H5B2_t *bt2=NULL; /* Pointer to the B-tree header */ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ H5RC_t *bt2_shared=NULL; /* Pointer to ref-counter for shared B-tree info */ hbool_t incr_rc=FALSE; /* Flag to indicate that we've incremented the B-tree's shared info reference count */ H5B2_node_ptr_t root_ptr; /* Node pointer info for root node */ @@ -264,29 +262,33 @@ H5B2_iterate(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, HDassert(op); /* Look up the B-tree header */ - if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_READ))) + 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; + bt2_shared = bt2->shared; H5RC_INC(bt2_shared); - incr_rc=TRUE; + incr_rc = TRUE; + + /* Get the pointer to the shared B-tree info */ + shared = H5RC_GET_OBJ(bt2->shared); + HDassert(shared); /* Make copy of the root node pointer */ root_ptr = bt2->root; /* Current depth of the tree */ - depth=bt2->depth; + depth = shared->depth; /* Release header */ - if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) + 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; + bt2 = NULL; /* Iterate through records */ - if(root_ptr.node_nrec>0) { + if(root_ptr.node_nrec > 0) { /* Iterate through nodes */ - if((ret_value=H5B2_iterate_node(f,dxpl_id,bt2_shared,depth,&root_ptr,op,op_data))<0) + if((ret_value = H5B2_iterate_node(f, dxpl_id, bt2_shared, depth, &root_ptr, op, op_data)) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTLIST, FAIL, "node iteration failed") } /* end if */ @@ -352,20 +354,20 @@ H5B2_find(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, H5RC_INC(bt2_shared); incr_rc=TRUE; + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2_shared); + HDassert(shared); + /* Make copy of the root node pointer to start search with */ curr_node_ptr = bt2->root; /* Current depth of the tree */ - depth = bt2->depth; + depth = shared->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); + bt2 = NULL; /* Check for empty tree */ if(curr_node_ptr.node_nrec==0) @@ -515,23 +517,23 @@ H5B2_index(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, H5RC_INC(bt2_shared); incr_rc=TRUE; + /* Get the pointer to the shared B-tree info */ + shared = H5RC_GET_OBJ(bt2_shared); + HDassert(shared); + /* Make copy of the root node pointer to start search with */ curr_node_ptr = bt2->root; /* Current depth of the tree */ - depth = bt2->depth; + depth = shared->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); + bt2 = NULL; /* Check for empty tree */ - if(curr_node_ptr.node_nrec==0) + if(curr_node_ptr.node_nrec == 0) HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records") /* Check for index greater than the number of records in the tree */ @@ -679,7 +681,7 @@ H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header") /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(bt2->shared); + shared = H5RC_GET_OBJ(bt2->shared); HDassert(shared); /* Check for empty B-tree */ @@ -687,14 +689,25 @@ H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree") /* Attempt to remove record from B-tree */ - if(bt2->depth > 0) { + if(shared->depth > 0) { hbool_t depth_decreased = FALSE; /* Flag to indicate whether the depth of the B-tree decreased */ - if(H5B2_remove_internal(f, dxpl_id, bt2->shared, &depth_decreased, NULL, bt2->depth, + if(H5B2_remove_internal(f, dxpl_id, bt2->shared, &depth_decreased, NULL, shared->depth, &(bt2->cache_info), &bt2_flags, &bt2->root, udata, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node") - bt2->depth -= depth_decreased; + /* Check for decreasing the depth of the B-tree */ + if(depth_decreased) { + /* Destroy free list factories for previous depth */ + if(shared->node_info[shared->depth].nat_rec_fac) + if(H5FL_fac_term(shared->node_info[shared->depth].nat_rec_fac) < 0) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy node's native record block factory") + if(shared->node_info[shared->depth].node_ptr_fac) + if(H5FL_fac_term(shared->node_info[shared->depth].node_ptr_fac) < 0) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy node's node pointer block factory") + + shared->depth -= depth_decreased; + } /* end for */ } /* end if */ else { if(H5B2_remove_leaf(f, dxpl_id, bt2->shared, &bt2->root, udata, op, op_data) < 0) @@ -789,7 +802,8 @@ herr_t H5B2_neighbor(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, H5B2_compare_t range, void *udata, H5B2_found_t op, void *op_data) { - H5B2_t *bt2=NULL; /* Pointer to the B-tree header */ + 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; FUNC_ENTER_NOAPI(H5B2_neighbor, FAIL) @@ -801,16 +815,20 @@ H5B2_neighbor(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, HDassert(op); /* Look up the B-tree header */ - if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_READ))) + 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") + /* Get the pointer to the shared B-tree info */ + shared = H5RC_GET_OBJ(bt2->shared); + HDassert(shared); + /* Check for empty tree */ if(!H5F_addr_defined(bt2->root.addr)) HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records") /* Attempt to find neighbor record in B-tree */ - if(bt2->depth>0) { - if(H5B2_neighbor_internal(f, dxpl_id, bt2->shared, bt2->depth, &bt2->root, NULL, range, udata, op, op_data)<0) + if(shared->depth > 0) { + if(H5B2_neighbor_internal(f, dxpl_id, bt2->shared, shared->depth, &bt2->root, NULL, range, udata, op, op_data)<0) HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "unable to find neighbor record in B-tree internal node") } /* end if */ else { @@ -853,7 +871,8 @@ herr_t H5B2_delete(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, H5B2_remove_t op, void *op_data) { - H5B2_t *bt2=NULL; /* Pointer to the B-tree header */ + 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; FUNC_ENTER_NOAPI(H5B2_delete, FAIL) @@ -867,9 +886,13 @@ H5B2_delete(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, if(NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header") + /* Get the pointer to the shared B-tree info */ + shared = H5RC_GET_OBJ(bt2->shared); + HDassert(shared); + /* Delete all nodes in B-tree */ if(H5F_addr_defined(bt2->root.addr)) - if(H5B2_delete_node(f, dxpl_id, bt2->shared, bt2->depth, &bt2->root, op, op_data) < 0) + if(H5B2_delete_node(f, dxpl_id, bt2->shared, shared->depth, &bt2->root, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to delete B-tree nodes") /* Release space for B-tree node on disk */ @@ -935,21 +958,21 @@ H5B2_modify(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, H5RC_INC(bt2_shared); incr_rc = TRUE; + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2_shared); + HDassert(shared); + /* Make copy of the root node pointer to start search with */ curr_node_ptr = bt2->root; /* Current depth of the tree */ - depth = bt2->depth; + depth = shared->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") diff --git a/src/H5B2cache.c b/src/H5B2cache.c index 8f8f71b..62ce32e 100644 --- a/src/H5B2cache.c +++ b/src/H5B2cache.c @@ -141,6 +141,7 @@ static H5B2_t * H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void UNUSED *udata) { const H5B2_class_t *type = (const H5B2_class_t *) _type; /* Type of B-tree */ + unsigned depth; /* Depth of B-tree */ size_t node_size, rrec_size; /* Size info for B-tree */ uint8_t split_percent, merge_percent; /* Split & merge %s for B-tree */ H5B2_t *bt2 = NULL; /* B-tree info */ @@ -196,7 +197,7 @@ H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, vo UINT16DECODE(p, rrec_size); /* Depth of tree */ - UINT16DECODE(p, bt2->depth); + UINT16DECODE(p, depth); /* Split & merge %s */ split_percent = *p++; @@ -221,7 +222,7 @@ H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, vo HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 B-tree header") /* Initialize shared B-tree info */ - if(H5B2_shared_init(f, bt2, type, node_size, rrec_size, split_percent, merge_percent) < 0) + if(H5B2_shared_init(f, bt2, type, depth, node_size, rrec_size, split_percent, merge_percent) < 0) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "can't create shared B-tree info") /* Set return value */ @@ -299,7 +300,7 @@ H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B UINT16ENCODE(p, shared->rrec_size); /* Depth of tree */ - UINT16ENCODE(p, bt2->depth); + UINT16ENCODE(p, shared->depth); /* Split & merge %s */ *p++ = shared->split_percent; @@ -494,14 +495,8 @@ H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_uda p = shared->page; /* Magic number */ - if(udata->depth > 1) { - if(HDmemcmp(p, H5B2_BRCH_MAGIC, (size_t)H5B2_SIZEOF_MAGIC)) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree internal node signature") - } /* end if */ - else { - if(HDmemcmp(p, H5B2_TWIG_MAGIC, (size_t)H5B2_SIZEOF_MAGIC)) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree internal node signature") - } /* end else */ + if(HDmemcmp(p, H5B2_INT_MAGIC, (size_t)H5B2_SIZEOF_MAGIC)) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree internal node signature") p += H5B2_SIZEOF_MAGIC; /* Version */ @@ -512,25 +507,13 @@ H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_uda if (*p++ != (uint8_t)shared->type->id) HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type") - /* Check which kind of internal node we have */ - if(udata->depth > 1) { - /* Allocate space for the native keys in memory */ - if((internal->int_native = H5FL_FAC_MALLOC(shared->brch_fac)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal native keys") - - /* Allocate space for the node pointers in memory */ - if((internal->node_ptrs = H5FL_FAC_MALLOC(shared->brch_node_ptr_fac)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal node pointers") - } /* end if */ - else { - /* Allocate space for the native keys in memory */ - if((internal->int_native = H5FL_FAC_MALLOC(shared->twig_fac)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal native keys") + /* Allocate space for the native keys in memory */ + if((internal->int_native = H5FL_FAC_MALLOC(shared->node_info[udata->depth].nat_rec_fac)) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal native keys") - /* Allocate space for the node pointers in memory */ - if((internal->node_ptrs = H5FL_FAC_MALLOC(shared->twig_node_ptr_fac)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal node pointers") - } /* end else */ + /* Allocate space for the node pointers in memory */ + if((internal->node_ptrs = H5FL_FAC_MALLOC(shared->node_info[udata->depth].node_ptr_fac)) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal node pointers") /* Set the number of records in the leaf & it's depth */ internal->nrec = udata->nrec; @@ -553,9 +536,9 @@ H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_uda for(u = 0; u < internal->nrec + 1; u++) { /* Decode node pointer */ H5F_addr_decode(f, (const uint8_t **)&p, &(int_node_ptr->addr)); - UINT16DECODE(p, int_node_ptr->node_nrec); + UINT64DECODE_VAR(p, int_node_ptr->node_nrec, shared->max_nrec_size); if(udata->depth > 1) - H5F_DECODE_LENGTH(f, p, int_node_ptr->all_nrec) + UINT64DECODE_VAR(p, int_node_ptr->all_nrec, shared->node_info[udata->depth - 1].cum_max_nrec_size) else int_node_ptr->all_nrec = int_node_ptr->node_nrec; @@ -626,10 +609,7 @@ H5B2_cache_internal_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr p = shared->page; /* Magic number */ - if(internal->depth > 1) - HDmemcpy(p, H5B2_BRCH_MAGIC, (size_t)H5B2_SIZEOF_MAGIC); - else - HDmemcpy(p, H5B2_TWIG_MAGIC, (size_t)H5B2_SIZEOF_MAGIC); + HDmemcpy(p, H5B2_INT_MAGIC, (size_t)H5B2_SIZEOF_MAGIC); p += H5B2_SIZEOF_MAGIC; /* Version # */ @@ -655,9 +635,9 @@ H5B2_cache_internal_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr for(u = 0; u < internal->nrec + 1; u++) { /* Encode node pointer */ H5F_addr_encode(f, &p, int_node_ptr->addr); - UINT16ENCODE(p, int_node_ptr->node_nrec); + UINT64ENCODE_VAR(p, int_node_ptr->node_nrec, shared->max_nrec_size); if(internal->depth > 1) - H5F_ENCODE_LENGTH(f, p, int_node_ptr->all_nrec); + UINT64ENCODE_VAR(p, int_node_ptr->all_nrec, shared->node_info[internal->depth - 1].cum_max_nrec_size); /* Move to next node pointer */ int_node_ptr++; @@ -716,25 +696,13 @@ H5B2_cache_internal_dest(H5F_t UNUSED *f, H5B2_internal_t *internal) shared = H5RC_GET_OBJ(internal->shared); HDassert(shared); - /* Check for 'branch' or 'twig' internal node */ - if(internal->depth == 1) { - /* Release internal 'twig' node's native key buffer */ - if(internal->int_native) - H5FL_FAC_FREE(shared->twig_fac, internal->int_native); - - /* Release internal 'twig' node's node pointer buffer */ - if(internal->node_ptrs) - H5FL_FAC_FREE(shared->twig_node_ptr_fac, internal->node_ptrs); - } /* end if */ - else { - /* Release internal 'branch' node's native key buffer */ - if(internal->int_native) - H5FL_FAC_FREE(shared->brch_fac, internal->int_native); + /* Release internal node's native key buffer */ + if(internal->int_native) + H5FL_FAC_FREE(shared->node_info[internal->depth].nat_rec_fac, internal->int_native); - /* Release internal 'branch' node's node pointer buffer */ - if(internal->node_ptrs) - H5FL_FAC_FREE(shared->brch_node_ptr_fac, internal->node_ptrs); - } /* end else */ + /* Release internal node's node pointer buffer */ + if(internal->node_ptrs) + H5FL_FAC_FREE(shared->node_info[internal->depth].node_ptr_fac, internal->node_ptrs); /* Decrement reference count on shared B-tree info */ if(internal->shared) @@ -889,7 +857,7 @@ H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nrec, v HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type") /* Allocate space for the native keys in memory */ - if((leaf->leaf_native = H5FL_FAC_MALLOC(shared->leaf_fac)) == NULL) + if((leaf->leaf_native = H5FL_FAC_MALLOC(shared->node_info[0].nat_rec_fac)) == NULL) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree leaf native keys") /* Set the number of records in the leaf */ @@ -1045,7 +1013,7 @@ H5B2_cache_leaf_dest(H5F_t UNUSED *f, H5B2_leaf_t *leaf) /* Release leaf's native key buffer */ if(leaf->leaf_native) - H5FL_FAC_FREE(shared->leaf_fac,leaf->leaf_native); + H5FL_FAC_FREE(shared->node_info[0].nat_rec_fac, leaf->leaf_native); /* Decrement reference count on shared B-tree info */ if(leaf->shared) diff --git a/src/H5B2dbg.c b/src/H5B2dbg.c index 2c58af8..2c02091 100644 --- a/src/H5B2dbg.c +++ b/src/H5B2dbg.c @@ -91,6 +91,8 @@ H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, { H5B2_t *bt2 = NULL; /* B-tree header info */ H5B2_shared_t *shared; /* Shared B-tree information */ + unsigned u; /* Local index variable */ + char temp_str[128]; /* Temporary string, for formatting */ herr_t ret_value = SUCCEED; /* Return value */ FUNC_ENTER_NOAPI(H5B2_hdr_debug, FAIL) @@ -140,7 +142,7 @@ H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, bt2->cache_info.is_dirty ? "True" : "False"); HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, "Depth:", - bt2->depth); + shared->depth); HDfprintf(stream, "%*s%-*s %Hu\n", indent, "", fwidth, "Number of records in tree:", bt2->root.all_nrec); @@ -150,39 +152,21 @@ H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, HDfprintf(stream, "%*s%-*s %a\n", indent, "", fwidth, "Address of root node:", bt2->root.addr); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Max. number of records per internal 'branch' node:", - shared->branch_nrec); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Max. number of records per internal 'twig' node:", - shared->twig_nrec); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Max. number of records per leaf node:", - shared->leaf_nrec); HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, "Split percent:", shared->split_percent); HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, "Merge percent:", shared->merge_percent); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Internal 'branch' node records to split at:", - shared->split_brch_nrec); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Internal 'twig' node records to split at:", - shared->split_twig_nrec); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Leaf records to split at:", - shared->split_leaf_nrec); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Internal 'branch' node records to merge at:", - shared->merge_brch_nrec); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Internal 'twig' node records to merge at:", - shared->merge_twig_nrec); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Leaf records to merge at:", - shared->merge_leaf_nrec); + + /* Print relevant node info */ + HDfprintf(stream, "%*sNode Info: (max_nrec/split_nrec/merge_nrec)\n", indent, ""); + for(u = 0; u < (shared->depth + 1); u++) { + sprintf(temp_str, "Depth %u:", u); + HDfprintf(stream, "%*s%-*s (%u/%u/%u)\n", indent + 3, "", MAX(0, fwidth - 3), + temp_str, + shared->node_info[u].max_nrec, shared->node_info[u].split_nrec, shared->node_info[u].merge_nrec); + } /* end for */ done: if(bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) diff --git a/src/H5B2int.c b/src/H5B2int.c index d1cee6e..293ee82 100644 --- a/src/H5B2int.c +++ b/src/H5B2int.c @@ -36,6 +36,7 @@ #include "H5B2pkg.h" /* v2 B-trees */ #include "H5Eprivate.h" /* Error handling */ #include "H5MFprivate.h" /* File memory management */ +#include "H5Vprivate.h" /* Vectors and arrays */ /****************/ /* Local Macros */ @@ -51,6 +52,11 @@ #define H5B2_NUM_TWIG_REC(f, n, r) \ (((n) - (H5B2_INT_PREFIX_SIZE + H5B2_TWIG_POINTER_SIZE(f))) / ((r) + H5B2_TWIG_POINTER_SIZE(f))) +/* Number of records that fit into internal node */ +/* (accounts for extra node pointer by counting it in with the prefix bytes) */ +#define H5B2_NUM_INT_REC(f, s, d) \ + (((s)->node_size - (H5B2_INT_PREFIX_SIZE + H5B2_INT_POINTER_SIZE(f, s, d))) / ((s)->rrec_size + H5B2_INT_POINTER_SIZE(f, s, d))) + /* Number of records that fit into leaf node */ #define H5B2_NUM_LEAF_REC(n, r) \ (((n) - H5B2_LEAF_PREFIX_SIZE) / (r)) @@ -81,9 +87,6 @@ static herr_t H5B2_split1(H5F_t *f, hid_t dxpl_id, unsigned depth, 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_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); static herr_t H5B2_redistribute3(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *internal, unsigned *internal_flags_ptr, unsigned idx); static herr_t H5B2_merge2(H5F_t *f, hid_t dxpl_id, unsigned depth, @@ -128,6 +131,9 @@ H5FL_BLK_DEFINE_STATIC(node_page); /* Declare a free list to manage the 'size_t' sequence information */ H5FL_SEQ_DEFINE_STATIC(size_t); +/* Declare a free list to manage the 'H5B2_node_info_t' sequence information */ +H5FL_SEQ_DEFINE_STATIC(H5B2_node_info_t); + /* Declare a free list to manage the H5B2_shared_t struct */ H5FL_DEFINE_STATIC(H5B2_shared_t); @@ -148,7 +154,7 @@ H5FL_DEFINE_STATIC(H5B2_shared_t); */ herr_t H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, - size_t node_size, size_t rrec_size, + unsigned depth, size_t node_size, size_t rrec_size, unsigned split_percent, unsigned merge_percent) { H5B2_shared_t *shared = NULL; /* Shared B-tree information */ @@ -161,25 +167,15 @@ H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, if(NULL == (shared = H5FL_CALLOC(H5B2_shared_t))) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree shared information") + /* Assign dynamic information */ + shared->depth = depth; + /* Assign user's information */ shared->split_percent = split_percent; shared->merge_percent = merge_percent; shared->node_size = node_size; shared->rrec_size = rrec_size; - /* Compute derived information */ - shared->branch_nrec = H5B2_NUM_BRCH_REC(f, shared->node_size, shared->rrec_size); - shared->split_brch_nrec = (shared->branch_nrec * shared->split_percent) / 100; - shared->merge_brch_nrec = (shared->branch_nrec * shared->merge_percent) / 100; - - shared->twig_nrec = H5B2_NUM_TWIG_REC(f, shared->node_size, shared->rrec_size); - shared->split_twig_nrec = (shared->twig_nrec * shared->split_percent) / 100; - shared->merge_twig_nrec = (shared->twig_nrec * shared->merge_percent) / 100; - - shared->leaf_nrec = H5B2_NUM_LEAF_REC(shared->node_size, shared->rrec_size); - shared->split_leaf_nrec = (shared->leaf_nrec * shared->split_percent) / 100; - shared->merge_leaf_nrec = (shared->leaf_nrec * shared->merge_percent) / 100; - /* Assign common type information */ shared->type = type; @@ -190,33 +186,54 @@ H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, HDmemset(shared->page,0,shared->node_size); #endif /* H5_USING_PURIFY */ - /* Create factory for internal 'branch' node native record storage */ - if((shared->brch_fac = H5FL_fac_init(type->nrec_size * shared->branch_nrec)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal 'branch' node native key block factory") - - /* Create factory for internal 'twig' node native record storage */ - if((shared->twig_fac = H5FL_fac_init(type->nrec_size * shared->twig_nrec)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal 'twig' node native key block factory") - - /* Create factory for leaf node native record storage */ - if((shared->leaf_fac = H5FL_fac_init(type->nrec_size * shared->leaf_nrec)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create leaf node native key block factory") - - /* Create factory for internal 'branch' node node pointer storage */ - if((shared->brch_node_ptr_fac = H5FL_fac_init(sizeof(H5B2_node_ptr_t) * (shared->branch_nrec + 1))) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal 'branch' node node pointer block factory") + /* Allocate array of node info structs */ + if((shared->node_info = H5FL_SEQ_MALLOC(H5B2_node_info_t, (size_t)(shared->depth + 1))) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") - /* Create factory for internal 'twig' node node pointer storage */ - if((shared->twig_node_ptr_fac = H5FL_fac_init(sizeof(H5B2_node_ptr_t) * (shared->twig_nrec + 1))) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal 'twig' node node pointer block factory") + /* Initialize leaf node info */ + shared->node_info[0].max_nrec = H5B2_NUM_LEAF_REC(shared->node_size, shared->rrec_size); + shared->node_info[0].split_nrec = (shared->node_info[0].max_nrec * shared->split_percent) / 100; + shared->node_info[0].merge_nrec = (shared->node_info[0].max_nrec * shared->merge_percent) / 100; + shared->node_info[0].cum_max_nrec = shared->node_info[0].max_nrec; + shared->node_info[0].cum_max_nrec_size = 0; + if((shared->node_info[0].nat_rec_fac = H5FL_fac_init(type->nrec_size * shared->node_info[0].max_nrec)) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create node native key block factory") + shared->node_info[0].node_ptr_fac = NULL; /* Allocate array of pointers to internal node native keys */ - if((shared->nat_off = H5FL_SEQ_MALLOC(size_t, MAX3(shared->branch_nrec, shared->twig_nrec, shared->leaf_nrec))) == NULL) + /* (uses leaf # of records because its the largest) */ + if((shared->nat_off = H5FL_SEQ_MALLOC(size_t, (size_t)shared->node_info[0].max_nrec)) == NULL) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") /* Initialize offsets in native key block */ - for(u = 0; u < MAX3(shared->branch_nrec, shared->twig_nrec, shared->leaf_nrec); u++) - shared->nat_off[u]=type->nrec_size*u; + /* (uses leaf # of records because its the largest) */ + for(u = 0; u < shared->node_info[0].max_nrec; u++) + shared->nat_off[u] = type->nrec_size * u; + + /* Compute size to store # of records in each node */ + /* (uses leaf # of records because its the largest) */ + shared->max_nrec_size = (H5V_log2_gen((hsize_t)shared->node_info[0].max_nrec) + 7) / 8; + HDassert(shared->max_nrec_size <= H5B2_SIZEOF_RECORDS_PER_NODE); + + /* Initialize internal node info */ + if(depth > 0) { + for(u = 1; u < (depth + 1); u++) { + shared->node_info[u].max_nrec = H5B2_NUM_INT_REC(f, shared, u); + HDassert(shared->node_info[u].max_nrec <= shared->node_info[u - 1].max_nrec); + + shared->node_info[u].split_nrec = (shared->node_info[u].max_nrec * shared->split_percent) / 100; + shared->node_info[u].merge_nrec = (shared->node_info[u].max_nrec * shared->merge_percent) / 100; + + shared->node_info[u].cum_max_nrec = ((shared->node_info[u].max_nrec + 1) * + shared->node_info[u - 1].cum_max_nrec) + shared->node_info[u].max_nrec; + shared->node_info[u].cum_max_nrec_size = (H5V_log2_gen((hsize_t)shared->node_info[u].cum_max_nrec) + 7) / 8; + + if((shared->node_info[u].nat_rec_fac = H5FL_fac_init(shared->type->nrec_size * shared->node_info[u].max_nrec)) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create node native key block factory") + if((shared->node_info[u].node_ptr_fac = H5FL_fac_init(sizeof(H5B2_node_ptr_t) * (shared->node_info[u].max_nrec + 1))) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal 'branch' node node pointer block factory") + } /* end for */ + } /* end if */ /* Make shared B-tree info reference counted */ if(NULL == (bt2->shared = H5RC_create(shared, H5B2_shared_free))) @@ -259,35 +276,28 @@ H5B2_shared_free(void *_shared) if(shared->page) H5FL_BLK_FREE(node_page, shared->page); - /* Destroy factory for internal 'branch' node native record storage */ - if(shared->brch_fac) - if(H5FL_fac_term(shared->brch_fac) < 0) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal 'branch' node native key block factory") - - /* Destroy factory for internal 'twig' node native record storage */ - if(shared->twig_fac) - if(H5FL_fac_term(shared->twig_fac) < 0) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal 'twig' node native key block factory") - - /* Destroy factory for leaf node native record storage */ - if(shared->leaf_fac) - if(H5FL_fac_term(shared->leaf_fac) < 0) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy leaf node native key block factory") - - /* Destroy factory for internal 'branch' node node pointer storage */ - if(shared->brch_node_ptr_fac) - if(H5FL_fac_term(shared->brch_node_ptr_fac) < 0) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal 'branch' node node pointer block factory") - - /* Destroy factory for internal 'twig' node node pointer storage */ - if(shared->twig_node_ptr_fac) - if(H5FL_fac_term(shared->twig_node_ptr_fac) < 0) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal 'twig' node node pointer block factory") - /* Free the array of offsets into the native key block */ if(shared->nat_off) H5FL_SEQ_FREE(size_t, shared->nat_off); + /* Release the node info */ + if(shared->node_info) { + unsigned u; /* Local index variable */ + + /* Destroy free list factories */ + for(u = 0; u < (shared->depth + 1); u++) { + if(shared->node_info[u].nat_rec_fac) + if(H5FL_fac_term(shared->node_info[u].nat_rec_fac) < 0) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy node's native record block factory") + if(shared->node_info[u].node_ptr_fac) + if(H5FL_fac_term(shared->node_info[u].node_ptr_fac) < 0) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy node's node pointer block factory") + } /* end for */ + + /* Free the array of node info structs */ + H5FL_SEQ_FREE(H5B2_node_info_t, shared->node_info); + } /* end if */ + /* Free the shared B-tree info itself */ H5FL_FREE(H5B2_shared_t, shared); @@ -544,10 +554,10 @@ done: *------------------------------------------------------------------------- */ herr_t -H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr, - H5RC_t *bt2_shared) +H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr) { H5B2_internal_t *new_root; /* Pointer to new root node */ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ 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 */ @@ -557,28 +567,47 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr, HDassert(f); HDassert(bt2); HDassert(bt2_flags_ptr); - HDassert(bt2_shared); + + /* Get the pointer to the shared B-tree info */ + shared = H5RC_GET_OBJ(bt2->shared); + HDassert(shared); /* Update depth of B-tree */ - bt2->depth++; + shared->depth++; + + /* Re-allocate array of node info structs */ + if((shared->node_info = H5FL_SEQ_REALLOC(H5B2_node_info_t, shared->node_info, (size_t)(shared->depth + 1))) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") + + /* Update node info for new depth of tree */ + shared->node_info[shared->depth].max_nrec = H5B2_NUM_INT_REC(f, shared, shared->depth); + shared->node_info[shared->depth].split_nrec = (shared->node_info[shared->depth].max_nrec * shared->split_percent) / 100; + shared->node_info[shared->depth].merge_nrec = (shared->node_info[shared->depth].max_nrec * shared->merge_percent) / 100; + shared->node_info[shared->depth].cum_max_nrec = ((shared->node_info[shared->depth].max_nrec + 1) * + shared->node_info[shared->depth - 1].cum_max_nrec) + shared->node_info[shared->depth].max_nrec; + shared->node_info[shared->depth].cum_max_nrec_size = (H5V_log2_gen((hsize_t)shared->node_info[shared->depth].cum_max_nrec) + 7) / 8; + if((shared->node_info[shared->depth].nat_rec_fac = H5FL_fac_init(shared->type->nrec_size * shared->node_info[shared->depth].max_nrec)) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create node native key block factory") + if((shared->node_info[shared->depth].node_ptr_fac = H5FL_fac_init(sizeof(H5B2_node_ptr_t) * (shared->node_info[shared->depth].max_nrec + 1))) == NULL) + HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal 'branch' node node pointer block factory") /* Keep old root node pointer info */ old_root_ptr = bt2->root; /* 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) + if(H5B2_create_internal(f, dxpl_id, bt2->shared, &(bt2->root), shared->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))) + if(NULL == (new_root = H5B2_protect_internal(f, dxpl_id, bt2->shared, bt2->root.addr, bt2->root.node_nrec, shared->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) + if(H5B2_split1(f, dxpl_id, shared->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) */ @@ -690,10 +719,10 @@ H5B2_redistribute2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *int #endif /* H5B2_DEBUG */ /* Determine whether to shuffle records left or right */ - if(*left_nrec<*right_nrec) { + if(*left_nrec < *right_nrec) { /* Moving record from right node to left */ - unsigned new_right_nrec = (*left_nrec+*right_nrec)/2; /* New number of records for right child */ + unsigned new_right_nrec = (*left_nrec + *right_nrec) / 2; /* New number of records for right child */ unsigned move_nrec = *right_nrec - new_right_nrec; /* Number of records to move from right node to left */ /* Copy record from parent node down into left child */ @@ -734,7 +763,7 @@ H5B2_redistribute2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *int else { /* Moving record from left node to right */ - unsigned new_left_nrec = (*left_nrec+*right_nrec)/2; /* New number of records for left child */ + unsigned new_left_nrec = (*left_nrec + *right_nrec) / 2; /* New number of records for left child */ unsigned move_nrec = *left_nrec - new_left_nrec; /* Number of records to move from left node to right */ /* Slide records in right node up */ @@ -926,22 +955,26 @@ H5B2_redistribute3(H5F_t *f, hid_t dxpl_id, unsigned depth, { /* Compute new # of records in each node */ unsigned total_nrec = *left_nrec + *middle_nrec + *right_nrec + 2; - 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); + 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); unsigned curr_middle_nrec = *middle_nrec; + /* Sanity check rounding */ + HDassert(new_middle_nrec <= new_left_nrec); + HDassert(new_middle_nrec <= new_right_nrec); + /* Move records into left node */ - if(new_left_nrec>*left_nrec) { - unsigned moved_middle_nrec=0; /* Number of records moved into left node */ + if(new_left_nrec > *left_nrec) { + unsigned moved_middle_nrec = 0; /* Number of records moved into left node */ /* Move left parent record down to left node */ HDmemcpy(H5B2_NAT_NREC(left_native,shared,*left_nrec),H5B2_INT_NREC(internal,shared,idx-1),shared->type->nrec_size); /* Move records from middle node into left node */ - if((new_left_nrec-1)>*left_nrec) { - moved_middle_nrec = new_left_nrec-(*left_nrec+1); - HDmemcpy(H5B2_NAT_NREC(left_native,shared,*left_nrec+1),H5B2_NAT_NREC(middle_native,shared,0),shared->type->nrec_size*moved_middle_nrec); + if((new_left_nrec - 1) > *left_nrec) { + moved_middle_nrec = new_left_nrec-(*left_nrec + 1); + HDmemcpy(H5B2_NAT_NREC(left_native, shared, *left_nrec + 1),H5B2_NAT_NREC(middle_native, shared, 0), shared->type->nrec_size * moved_middle_nrec); } /* end if */ /* Move record from middle node up to parent node */ @@ -1183,337 +1216,6 @@ done: /*------------------------------------------------------------------------- - * Function: H5B2_split3 - * - * Purpose: Perform a 3->4 node split - * - * Return: Success: Non-negative - * - * Failure: Negative - * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Feb 10 2005 - * - *------------------------------------------------------------------------- - */ -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_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 */ - haddr_t new_addr; /* Address of new child node */ - void *left_child, *right_child; /* Pointers to left & right child nodes */ - void *middle_child; /* Pointer to middle child node */ - void *new_child; /* Pointer to new child node */ - unsigned *left_nrec, *right_nrec; /* Pointers to left & right child # of records */ - unsigned *middle_nrec; /* Pointer to middle child # of records */ - unsigned *new_nrec; /* Pointer to new 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 */ - uint8_t *new_native; /* Pointer to new child's native records */ - H5B2_shared_t *shared; /* B-tree's shared info */ - 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_node_ptr_t *new_node_ptrs=NULL;/* Pointers to childs' node pointer info */ - hssize_t left_moved_nrec=0, right_moved_nrec=0; /* Number of records moved, for internal split */ - hssize_t middle_moved_nrec=0; /* Number of records moved, for internal split */ - hsize_t new_moved_nrec=0; /* Number of records moved, for internal split */ - herr_t ret_value=SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI_NOINIT(H5B2_split3) - - HDassert(f); - HDassert(internal); - - /* 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 *right_internal; /* Pointer to right internal node */ - H5B2_internal_t *middle_internal; /* Pointer to middle internal node */ - H5B2_internal_t *new_internal; /* Pointer to new internal node */ - - /* Setup information for unlocking child nodes */ - child_class = H5AC_BT2_INT; - left_addr = internal->node_ptrs[idx-1].addr; - middle_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-1].node_nrec, (depth - 1), H5AC_WRITE))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") - if (NULL == (middle_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, middle_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 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 */ - new_addr = internal->node_ptrs[idx+1].addr; - - /* Lock "new" internal node */ - if (NULL == (new_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, new_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; - new_child = new_internal; - right_child = right_internal; - left_nrec = &(left_internal->nrec); - middle_nrec = &(middle_internal->nrec); - new_nrec = &(new_internal->nrec); - right_nrec = &(right_internal->nrec); - left_native = left_internal->int_native; - middle_native = middle_internal->int_native; - new_native = new_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; - new_node_ptrs = new_internal->node_ptrs; - } /* end if */ - else { - H5B2_leaf_t *left_leaf; /* Pointer to left leaf node */ - H5B2_leaf_t *right_leaf; /* Pointer to right leaf node */ - H5B2_leaf_t *middle_leaf; /* Pointer to middle leaf node */ - H5B2_leaf_t *new_leaf; /* Pointer to new leaf node */ - - /* Setup information for unlocking child nodes */ - child_class = H5AC_BT2_LEAF; - left_addr = internal->node_ptrs[idx-1].addr; - middle_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-1].node_nrec), internal->shared, H5AC_WRITE))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node") - if (NULL == (middle_leaf = H5AC_protect(f, dxpl_id, child_class, middle_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 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 */ - new_addr = internal->node_ptrs[idx+1].addr; - - /* Lock "new" leaf node */ - if (NULL == (new_leaf = H5AC_protect(f, dxpl_id, child_class, new_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; - new_child = new_leaf; - right_child = right_leaf; - left_nrec = &(left_leaf->nrec); - middle_nrec = &(middle_leaf->nrec); - new_nrec = &(new_leaf->nrec); - right_nrec = &(right_leaf->nrec); - left_native = left_leaf->leaf_native; - middle_native = middle_leaf->leaf_native; - new_native = new_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 + *middle_nrec + *right_nrec + 2; - unsigned new_new_nrec = (total_nrec-3)/4; - unsigned new_middle_nrec = ((total_nrec-3)-new_new_nrec)/3; - unsigned new_left_nrec = ((total_nrec-3)-(new_middle_nrec+new_new_nrec))/2; - unsigned new_right_nrec = (total_nrec-3)-(new_left_nrec+new_middle_nrec+new_new_nrec); - - /* Partially fill new node from right node */ - { - unsigned right_nrec_move = *right_nrec-new_right_nrec; - - /* Move right record down from parent into new node */ - HDmemcpy(H5B2_NAT_NREC(new_native,shared,(new_new_nrec-right_nrec_move)),H5B2_INT_NREC(internal,shared,idx),shared->type->nrec_size); - - /* Move records from right node to new node */ - HDmemcpy(H5B2_NAT_NREC(new_native,shared,((new_new_nrec-right_nrec_move)+1)),H5B2_NAT_NREC(right_native,shared,0),shared->type->nrec_size*(right_nrec_move-1)); - - /* Move record from right node up to parent node */ - HDmemcpy(H5B2_INT_NREC(internal,shared,idx+1),H5B2_NAT_NREC(right_native,shared,(right_nrec_move-1)),shared->type->nrec_size); - - /* Slide records in right node down */ - HDmemmove(H5B2_NAT_NREC(right_native,shared,0),H5B2_NAT_NREC(right_native,shared,right_nrec_move),shared->type->nrec_size*new_right_nrec); - - /* Move node pointers also if this is an internal node */ - if(depth>1) { - hsize_t moved_nrec; /* Total number of records moved, for internal redistrib */ - unsigned u; /* Local index variable */ - - /* Move right node pointers into new node */ - HDmemcpy(&(new_node_ptrs[(new_new_nrec-right_nrec_move)+1]),&(right_node_ptrs[0]),sizeof(H5B2_node_ptr_t)*right_nrec_move); - - /* Count the number of records being moved into the new node */ - for(u=0, moved_nrec=0; utype->nrec_size*new_nrec_move); - - /* Move record from middle node up to parent node */ - HDmemcpy(H5B2_INT_NREC(internal,shared,idx),H5B2_NAT_NREC(middle_native,shared,((*middle_nrec-new_nrec_move)-1)),shared->type->nrec_size); - - /* Slide records in middle node up */ - HDmemmove(H5B2_NAT_NREC(middle_native,shared,(new_middle_nrec-((*middle_nrec-new_nrec_move)-1))),H5B2_NAT_NREC(middle_native,shared,0),shared->type->nrec_size*(*middle_nrec-(new_nrec_move+1))); - - /* Move node pointers also if this is an internal node */ - if(depth>1) { - hsize_t moved_nrec; /* Total number of records moved, for internal redistrib */ - unsigned u; /* Local index variable */ - - /* Move middle node pointers into new node */ - HDmemcpy(&(new_node_ptrs[0]),&(middle_node_ptrs[(*middle_nrec-new_nrec_move)]),sizeof(H5B2_node_ptr_t)*(new_nrec_move+1)); - - /* Count the number of records being moved into the new node */ - for(u=0, moved_nrec=0; utype->nrec_size); - - /* Move records from left node to middle node */ - HDmemcpy(H5B2_NAT_NREC(middle_native,shared,0),H5B2_NAT_NREC(left_native,shared,(new_left_nrec+1)),shared->type->nrec_size*(left_nrec_move-1)); - - /* Move node pointers also if this is an internal node */ - if(depth>1) { - hsize_t moved_nrec; /* Total number of records moved, for internal redistrib */ - unsigned u; /* Local index variable */ - - /* Move left node pointers into middle node */ - HDmemcpy(&(middle_node_ptrs[0]),&(left_node_ptrs[new_left_nrec+1]),sizeof(H5B2_node_ptr_t)*left_nrec_move); - - /* Count the number of records being moved into the middle node */ - for(u=0, moved_nrec=0; utype->nrec_size); - - /* Update # of records in nodes */ - *left_nrec = new_left_nrec; - *middle_nrec = new_middle_nrec; - *new_nrec = new_new_nrec; - *right_nrec = new_right_nrec; - } /* end block */ - - /* Update # of records in child nodes */ - internal->node_ptrs[idx-1].node_nrec = *left_nrec; - internal->node_ptrs[idx].node_nrec = *middle_nrec; - internal->node_ptrs[idx+1].node_nrec = *new_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-1].all_nrec += left_moved_nrec; - internal->node_ptrs[idx].all_nrec += middle_moved_nrec; - internal->node_ptrs[idx+1].all_nrec = new_moved_nrec; - internal->node_ptrs[idx+2].all_nrec += right_moved_nrec; - } /* end if */ - else { - internal->node_ptrs[idx-1].all_nrec = internal->node_ptrs[idx-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; - 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-1].all_nrec,shared,left_child,middle_child); - H5B2_assert_internal2(internal->node_ptrs[idx].all_nrec,shared,middle_child,left_child); - H5B2_assert_internal2(internal->node_ptrs[idx].all_nrec,shared,middle_child,new_child); - H5B2_assert_internal2(internal->node_ptrs[idx+1].all_nrec,shared,new_child,middle_child); - H5B2_assert_internal2(internal->node_ptrs[idx+1].all_nrec,shared,new_child,right_child); - H5B2_assert_internal2(internal->node_ptrs[idx+2].all_nrec,shared,right_child,new_child); - } /* end if */ - else { - H5B2_assert_leaf2(shared,left_child,middle_child); - H5B2_assert_leaf2(shared,middle_child,new_child); - H5B2_assert_leaf2(shared,new_child,right_child); - H5B2_assert_leaf(shared,right_child); - } /* end else */ -#endif /* H5B2_DEBUG */ - - /* Unlock child nodes (mark 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, new_addr, new_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_split3 */ - - -/*------------------------------------------------------------------------- * Function: H5B2_merge2 * * Purpose: Perform a 2->1 node merge @@ -2026,7 +1728,7 @@ H5B2_insert_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, HDassert(shared); /* Must have a leaf node with enough space to insert a record now */ - HDassert(curr_node_ptr->node_nrec < shared->split_leaf_nrec); + HDassert(curr_node_ptr->node_nrec < shared->node_info[0].max_nrec); /* Sanity check number of records */ HDassert(curr_node_ptr->all_nrec == curr_node_ptr->node_nrec); @@ -2129,13 +1831,8 @@ H5B2_insert_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, * eventually force a split */ retries = 2; - /* Determine the correct number of records to split at */ - if(depth == 1) - split_nrec = shared->split_leaf_nrec; - else if(depth == 2) - split_nrec = shared->split_twig_nrec; - else - split_nrec = shared->split_brch_nrec; + /* Determine the correct number of records to split child node at */ + split_nrec = shared->node_info[depth - 1].split_nrec; /* Preemptively split/redistribute a node we will enter */ while(internal->node_ptrs[idx].node_nrec == split_nrec) { @@ -2163,21 +1860,21 @@ H5B2_insert_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, } /* end else */ } /* end if */ else { /* Middle child */ - 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) + 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") } /* end if */ else { - if(H5B2_split3(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 else */ /* Locate node pointer for child (after split/redistribute) */ /* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */ - if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0) + if((cmp = H5B2_locate_record(shared->type, internal->nrec, shared->nat_off, internal->int_native, udata, &idx)) == 0) HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") if(cmp > 0) idx++; @@ -2188,12 +1885,12 @@ H5B2_insert_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, } /* end block */ /* Attempt to insert node */ - if(depth>1) { - if(H5B2_insert_internal(f, dxpl_id, bt2_shared, depth-1, &internal_flags, &internal->node_ptrs[idx], udata) < 0) + if(depth > 1) { + if(H5B2_insert_internal(f, dxpl_id, bt2_shared, (depth - 1), &internal_flags, &internal->node_ptrs[idx], udata) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node") } /* end if */ else { - if(H5B2_insert_leaf(f,dxpl_id,bt2_shared,&internal->node_ptrs[idx],udata)<0) + if(H5B2_insert_leaf(f, dxpl_id, bt2_shared, &internal->node_ptrs[idx], udata) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node") } /* end else */ @@ -2241,41 +1938,41 @@ H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_t *n HDassert(node_ptr); /* Allocate memory for leaf information */ - if (NULL==(leaf = H5FL_MALLOC(H5B2_leaf_t))) + if(NULL == (leaf = H5FL_MALLOC(H5B2_leaf_t))) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree leaf info") /* Set metadata cache info */ - HDmemset(&leaf->cache_info,0,sizeof(H5AC_info_t)); + HDmemset(&leaf->cache_info, 0, sizeof(H5AC_info_t)); /* Share common B-tree information */ leaf->shared = bt2_shared; H5RC_INC(leaf->shared); /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(leaf->shared); + shared = H5RC_GET_OBJ(leaf->shared); HDassert(shared); /* Allocate space for the native keys in memory */ - if((leaf->leaf_native=H5FL_FAC_MALLOC(shared->leaf_fac))==NULL) + if((leaf->leaf_native = H5FL_FAC_MALLOC(shared->node_info[0].nat_rec_fac)) == NULL) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree leaf native keys") #ifdef H5_USING_PURIFY -HDmemset(leaf->leaf_native,0,shared->type->nrec_size*shared->leaf_nrec); +HDmemset(leaf->leaf_native, 0, shared->type->nrec_size * shared->node_info[0].max_nrec); #endif /* H5_USING_PURIFY */ /* Set number of records */ - leaf->nrec=0; + leaf->nrec = 0; /* Allocate space on disk for the leaf */ - if (HADDR_UNDEF==(node_ptr->addr=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size))) + if(HADDR_UNDEF == (node_ptr->addr=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size))) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree leaf node") /* Cache the new B-tree node */ - if (H5AC_set(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) + if(H5AC_set(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree leaf to cache") done: - if (ret_value<0) { - if (leaf) + if(ret_value < 0) { + if(leaf) (void)H5B2_cache_leaf_dest(f,leaf); } /* end if */ @@ -2314,67 +2011,49 @@ H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, HDassert(depth > 0); /* Allocate memory for internal node information */ - if (NULL==(internal = H5FL_MALLOC(H5B2_internal_t))) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal info") + if(NULL == (internal = H5FL_MALLOC(H5B2_internal_t))) + HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal info") /* Set metadata cache info */ - HDmemset(&internal->cache_info,0,sizeof(H5AC_info_t)); + HDmemset(&internal->cache_info, 0, sizeof(H5AC_info_t)); /* Share common B-tree information */ internal->shared = bt2_shared; H5RC_INC(internal->shared); /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(internal->shared); + shared = H5RC_GET_OBJ(internal->shared); HDassert(shared); - /* Check whether we are creating a 'branch' or 'twig' node */ - if(depth == 1) { - /* Allocate space for the native keys in memory */ - if((internal->int_native = H5FL_FAC_MALLOC(shared->twig_fac)) == NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal 'twig' native keys") -#ifdef H5_USING_PURIFY -HDmemset(internal->int_native, 0, shared->type->nrec_size * shared->twig_nrec); -#endif /* H5_USING_PURIFY */ - - /* Allocate space for the node pointers in memory */ - if((internal->node_ptrs = H5FL_FAC_MALLOC(shared->twig_node_ptr_fac)) == NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal 'twig' node pointers") -#ifdef H5_USING_PURIFY -HDmemset(internal->node_ptrs, 0, sizeof(H5B2_node_ptr_t) * (shared->twig_nrec + 1)); -#endif /* H5_USING_PURIFY */ - } /* end if */ - else { - /* Allocate space for the native keys in memory */ - if((internal->int_native = H5FL_FAC_MALLOC(shared->brch_fac)) == NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal 'branch' native keys") + /* Allocate space for the native keys in memory */ + if((internal->int_native = H5FL_FAC_MALLOC(shared->node_info[depth].nat_rec_fac)) == NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal 'twig' native keys") #ifdef H5_USING_PURIFY -HDmemset(internal->int_native, 0, shared->type->nrec_size * shared->branch_nrec); +HDmemset(internal->int_native, 0, shared->type->nrec_size * shared->node_info[depth].max_nrec); #endif /* H5_USING_PURIFY */ - /* Allocate space for the node pointers in memory */ - if((internal->node_ptrs = H5FL_FAC_MALLOC(shared->brch_node_ptr_fac)) == NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal 'branch' node pointers") + /* Allocate space for the node pointers in memory */ + if((internal->node_ptrs = H5FL_FAC_MALLOC(shared->node_info[depth].node_ptr_fac)) == NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal 'twig' node pointers") #ifdef H5_USING_PURIFY -HDmemset(internal->node_ptrs, 0, sizeof(H5B2_node_ptr_t) * (shared->branch_nrec + 1)); +HDmemset(internal->node_ptrs, 0, sizeof(H5B2_node_ptr_t) * (shared->node_info[depth].max_nrec + 1)); #endif /* H5_USING_PURIFY */ - } /* end else */ /* Set number of records & depth of the node */ internal->nrec = 0; internal->depth = depth; /* Allocate space on disk for the internal node */ - if (HADDR_UNDEF==(node_ptr->addr=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size))) + if(HADDR_UNDEF == (node_ptr->addr = H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size))) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree internal node") /* Cache the new B-tree node */ - if (H5AC_set(f, dxpl_id, H5AC_BT2_INT, node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0) + if(H5AC_set(f, dxpl_id, H5AC_BT2_INT, node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree internal node to cache") done: - if (ret_value<0) { - if (internal) + if(ret_value < 0) { + if(internal) (void)H5B2_cache_internal_dest(f,internal); } /* end if */ @@ -2663,12 +2342,7 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, HDassert(shared); /* Determine the correct number of records to merge at */ - if(depth == 1) - merge_nrec = shared->merge_leaf_nrec; - else if(depth == 2) - merge_nrec = shared->merge_twig_nrec; - else - merge_nrec = shared->merge_brch_nrec; + merge_nrec = shared->node_info[depth - 1].merge_nrec; /* Check for needing to collapse the root node */ /* (The root node is the only internal node allowed to have 1 record) */ diff --git a/src/H5B2pkg.h b/src/H5B2pkg.h index 5c861b7..30b4adb 100644 --- a/src/H5B2pkg.h +++ b/src/H5B2pkg.h @@ -44,18 +44,22 @@ /* B-tree signatures */ #define H5B2_HDR_MAGIC "BTHD" /* Header */ -#define H5B2_BRCH_MAGIC "BTBR" /* Internal "branch" node */ -#define H5B2_TWIG_MAGIC "BTTW" /* Internal "twig" node */ +#define H5B2_INT_MAGIC "BTIN" /* Internal node */ #define H5B2_LEAF_MAGIC "BTLF" /* Leaf node */ /* Size of storage for number of records per node (on disk) */ #define H5B2_SIZEOF_RECORDS_PER_NODE 2 -/* Size of a "branch node pointer" (on disk) */ -#define H5B2_BRCH_POINTER_SIZE(f) (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE+H5F_SIZEOF_SIZE(f)) +/* Size of a "tree pointer" (on disk) */ +/* (essentially, the largest internal pointer allowed) */ +#define H5B2_TREE_POINTER_SIZE(f) (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE+H5F_SIZEOF_SIZE(f)) -/* Size of a "twig node pointer" (on disk) */ -#define H5B2_TWIG_POINTER_SIZE(f) (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE) +/* Size of a internal node pointer (on disk) */ +#define H5B2_INT_POINTER_SIZE(f, s, d) ( \ + H5F_SIZEOF_ADDR(f) /* Address of child node */ \ + + (s)->max_nrec_size /* # of records in child node */ \ + + (s)->node_info[(d) - 1].cum_max_nrec_size /* Total # of records in child & below */ \ + ) /* Size of checksum information (on disk) */ #define H5B2_SIZEOF_CHKSUM 4 @@ -79,7 +83,7 @@ + 2 /* Depth of tree */ \ + 1 /* Split % of full (as integer, ie. "98" means 98%) */ \ + 1 /* Merge % of full (as integer, ie. "98" means 98%) */ \ - + H5B2_BRCH_POINTER_SIZE(f) /* Node pointer to root node in tree */ \ + + H5B2_TREE_POINTER_SIZE(f) /* Node pointer to root node in tree */ \ ) /* Size of the v2 B-tree internal node prefix */ @@ -121,36 +125,38 @@ typedef struct { hsize_t all_nrec; /* Number of records in node pointed to and all it's children */ } H5B2_node_ptr_t; +/* Information about a node at a given depth */ +typedef struct { + unsigned max_nrec; /* Max. number of records in node */ + unsigned split_nrec; /* Number of records to split node at */ + unsigned merge_nrec; /* Number of records to merge node at */ + hsize_t cum_max_nrec; /* Cumulative max. # of records below this node's depth */ + unsigned char cum_max_nrec_size; /* Size to store cumulative max. # of records for this node (in bytes) */ + H5FL_fac_head_t *nat_rec_fac; /* Factory for native record blocks */ + H5FL_fac_head_t *node_ptr_fac; /* Factory for node pointer blocks */ +} H5B2_node_info_t; + /* Each B-tree has certain information that can be shared across all * the instances of nodes in that B-tree. */ typedef struct H5B2_shared_t { /* Shared internal data structures */ const H5B2_class_t *type; /* Type of tree */ - uint8_t *page; /* Disk page */ - H5FL_fac_head_t *brch_fac; /* Factory for internal "branch" node native record blocks */ - H5FL_fac_head_t *twig_fac; /* Factory for internal "twig" node native record blocks */ - H5FL_fac_head_t *leaf_fac; /* Factory for leaf node native record blocks */ - H5FL_fac_head_t *brch_node_ptr_fac; /* Factory for internal "branch" node node pointer blocks */ - H5FL_fac_head_t *twig_node_ptr_fac; /* Factory for internal "twig" node node pointer blocks */ - size_t *nat_off; /* Array of offsets of native records */ - - /* Information set by user */ + uint8_t *page; /* Common disk page for I/O */ + size_t *nat_off; /* Array of offsets of native records */ + H5B2_node_info_t *node_info; /* Table of node info structs for current depth of B-tree */ + + /* Information set by user (stored) */ 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 B-tree nodes, in bytes */ size_t rrec_size; /* Size of "raw" (on disk) record, in bytes */ + /* Dynamic information (stored) */ + unsigned depth; /* B-tree's overall depth */ + /* Derived information from user's information */ - size_t branch_nrec; /* Number of records which fit into an internal "branch" node */ - size_t split_brch_nrec; /* Number of records to split an internal "branch" node at */ - size_t merge_brch_nrec; /* Number of records to merge an internal "branch" node at */ - size_t twig_nrec; /* Number of records which fit into an internal "twig" node */ - size_t split_twig_nrec; /* Number of records to split an internal "twig" node at */ - size_t merge_twig_nrec; /* Number of records to merge an internal "twig" node at */ - size_t leaf_nrec; /* Number of records which fit into a leaf node */ - size_t split_leaf_nrec; /* Number of records to split a leaf node at */ - size_t merge_leaf_nrec; /* Number of records to merge a leaf node at */ + unsigned char max_nrec_size; /* Size to store max. # of records in any node (in bytes) */ } H5B2_shared_t; /* The B-tree information */ @@ -159,7 +165,6 @@ typedef struct H5B2_t { H5AC_info_t cache_info; /* Internal B-tree information */ - unsigned depth; /* B-tree's overall depth */ H5B2_node_ptr_t root; /* Node pointer to root node in B-tree */ H5RC_t *shared; /* Ref-counted shared info */ } H5B2_t; @@ -238,7 +243,8 @@ H5_DLLVAR const H5B2_class_t H5B2_TEST[1]; /* Routines for managing shared B-tree info */ H5_DLL herr_t H5B2_shared_init(H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, - size_t node_size, size_t rrec_size, unsigned split_percent, unsigned merge_percent); + unsigned depth, size_t node_size, size_t rrec_size, + unsigned split_percent, unsigned merge_percent); /* Routines for operating on internal nodes */ H5_DLL H5B2_internal_t *H5B2_protect_internal(H5F_t *f, hid_t dxpl_id, @@ -247,7 +253,7 @@ H5_DLL H5B2_internal_t *H5B2_protect_internal(H5F_t *f, hid_t dxpl_id, /* Routines for allocating nodes */ H5_DLL herr_t H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, - unsigned *bt2_flags_ptr, H5RC_t *bt2_shared); + unsigned *bt2_flags_ptr); H5_DLL herr_t H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_t *node_ptr); diff --git a/src/H5B2private.h b/src/H5B2private.h index d095e83..82c90f4 100644 --- a/src/H5B2private.h +++ b/src/H5B2private.h @@ -107,9 +107,6 @@ struct H5B2_class_t { typedef struct H5B2_stat_t { 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 1251195..ef58c7f 100644 --- a/src/H5B2stat.c +++ b/src/H5B2stat.c @@ -105,11 +105,8 @@ H5B2_stat_info(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, shared = H5RC_GET_OBJ(bt2->shared); /* Get information about the B-tree */ - info->depth = bt2->depth; + info->depth = shared->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 3ba4a34..7863b60 100644 --- a/src/H5B2test.c +++ b/src/H5B2test.c @@ -326,21 +326,21 @@ H5B2_get_node_info_test(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr H5RC_INC(bt2_shared); incr_rc=TRUE; + /* Get the pointer to the shared B-tree info */ + shared = H5RC_GET_OBJ(bt2_shared); + HDassert(shared); + /* Make copy of the root node pointer to start search with */ curr_node_ptr = bt2->root; /* Current depth of the tree */ - depth = bt2->depth; + depth = shared->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") diff --git a/test/btree2.c b/test/btree2.c index 3a999de..10b46b3 100644 --- a/test/btree2.c +++ b/test/btree2.c @@ -34,7 +34,7 @@ const char *FILENAME[] = { }; #define INSERT_SPLIT_ROOT_NREC 63 -#define INSERT_MANY (500*1000) +#define INSERT_MANY (1000*1000) #define FIND_MANY (INSERT_MANY/100) #define FIND_NEIGHBOR 2000 #define DELETE_SMALL 20 @@ -710,7 +710,7 @@ error: /*------------------------------------------------------------------------- - * Function: test_insert_level1_2leaf_split + * Function: test_insert_level1_side_split * * Purpose: Basic tests for the B-tree v2 code. This test inserts enough * records to split the root node and force the tree to depth 1. @@ -728,7 +728,7 @@ error: *------------------------------------------------------------------------- */ static int -test_insert_level1_2leaf_split(hid_t fapl) +test_insert_level1_side_split(hid_t fapl) { hid_t file=-1; char filename[1024]; @@ -752,7 +752,7 @@ test_insert_level1_2leaf_split(hid_t fapl) /* * Test inserting many records into v2 B-tree */ - TESTING("B-tree insert: split 1 leaf to 2 in level 1 B-tree (l->r)"); + TESTING("B-tree insert: split side leaf into 2 leaves in level 1 B-tree (l->r)"); /* * Create v2 B-tree @@ -810,7 +810,7 @@ test_insert_level1_2leaf_split(hid_t fapl) /* * Test inserting many records into v2 B-tree */ - TESTING("B-tree insert: split 1 leaf to 2 in level 1 B-tree (r->l)"); + TESTING("B-tree insert: split side leaf into 2 leaves in level 1 B-tree (r->l)"); /* * Create v2 B-tree @@ -876,7 +876,7 @@ error: H5Fclose(file); } H5E_END_TRY; return 1; -} /* test_insert_level1_2leaf_split() */ +} /* test_insert_level1_side_split() */ /*------------------------------------------------------------------------- @@ -1028,7 +1028,7 @@ error: /*------------------------------------------------------------------------- - * Function: test_insert_level1_3leaf_split + * Function: test_insert_level1_middle_split * * Purpose: Basic tests for the B-tree v2 code. This test inserts enough * records to split the root node and force the tree to depth 1. @@ -1047,7 +1047,7 @@ error: *------------------------------------------------------------------------- */ static int -test_insert_level1_3leaf_split(hid_t fapl) +test_insert_level1_middle_split(hid_t fapl) { hid_t file=-1; char filename[1024]; @@ -1072,7 +1072,7 @@ test_insert_level1_3leaf_split(hid_t fapl) /* * Test inserting many records into v2 B-tree */ - TESTING("B-tree insert: split 3 leaves to 4 in level 1 B-tree"); + TESTING("B-tree insert: split middle leaf into 2 leaves in level 1 B-tree"); /* * Create v2 B-tree @@ -1114,17 +1114,17 @@ test_insert_level1_3leaf_split(hid_t fapl) TEST_ERROR if(bt2_stat.nrecords != (3 * INSERT_SPLIT_ROOT_NREC)) TEST_ERROR - record = ((3 * INSERT_SPLIT_ROOT_NREC) / 4) - 1; + record = 62; 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 = (2 * ((3 * INSERT_SPLIT_ROOT_NREC) / 4)) - 1; + record = 94; 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 = 3 * ((3 * INSERT_SPLIT_ROOT_NREC) / 4); + record = 126; 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) @@ -1152,7 +1152,7 @@ error: H5Fclose(file); } H5E_END_TRY; return 1; -} /* test_insert_level1_3leaf_split() */ +} /* test_insert_level1_middle_split() */ /*------------------------------------------------------------------------- @@ -1211,7 +1211,7 @@ test_insert_make_level2(hid_t fapl) if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ - for(; u < ((INSERT_SPLIT_ROOT_NREC * 27) + 1); u++) { + for(; u < ((INSERT_SPLIT_ROOT_NREC * 29) + 1); u++) { record = u + 4; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -1222,9 +1222,9 @@ test_insert_make_level2(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 27) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 29) + 1)) TEST_ERROR - record = 885; + record = 948; 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) @@ -1253,11 +1253,11 @@ test_insert_make_level2(hid_t fapl) FAIL_STACK_ERROR /* Make certain that the index is correct */ - if(idx != ((INSERT_SPLIT_ROOT_NREC * 27) + 5)) + if(idx != ((INSERT_SPLIT_ROOT_NREC * 29) + 5)) TEST_ERROR /* Attempt to find non-existant record in level-2 B-tree */ - idx = INSERT_SPLIT_ROOT_NREC * 28; + idx = INSERT_SPLIT_ROOT_NREC * 30; H5E_BEGIN_TRY { ret = H5B2_find(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &idx, find_cb, &idx); } H5E_END_TRY; @@ -1266,12 +1266,12 @@ test_insert_make_level2(hid_t fapl) TEST_ERROR /* Attempt to find existant record in root of level-2 B-tree */ - idx = 885; + idx = 948; if(H5B2_find(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &idx, find_cb, &idx) < 0) FAIL_STACK_ERROR /* Check with B-tree */ - record = 885; + record = 948; 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) @@ -1304,15 +1304,15 @@ test_insert_make_level2(hid_t fapl) /* Attempt to index non-existant record in level-2 B-tree */ idx = 0; H5E_BEGIN_TRY { - ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)(INSERT_SPLIT_ROOT_NREC * 28), find_cb, NULL); + ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)(INSERT_SPLIT_ROOT_NREC * 30), find_cb, NULL); } H5E_END_TRY; /* Should fail */ if(ret != FAIL) TEST_ERROR /* Attempt to index existing record in root of level-2 B-tree */ - idx = 885; - if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)885, find_cb, &idx) < 0) + idx = 948; + if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)948, find_cb, &idx) < 0) FAIL_STACK_ERROR /* Attempt to index existing record in internal node of level-2 B-tree */ @@ -1398,8 +1398,8 @@ test_insert_level2_leaf_redistrib(hid_t fapl) if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ - for(; u < ((INSERT_SPLIT_ROOT_NREC * 27) + (INSERT_SPLIT_ROOT_NREC / 2)); u++) { - record = u + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 2; + for(; u < ((INSERT_SPLIT_ROOT_NREC * 29) + (INSERT_SPLIT_ROOT_NREC / 2)); u++) { + record = u + INSERT_SPLIT_ROOT_NREC + 1; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ @@ -1409,26 +1409,26 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 27) + (INSERT_SPLIT_ROOT_NREC / 2))) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 29) + (INSERT_SPLIT_ROOT_NREC / 2))) TEST_ERROR - record = 930; /* Record in root node */ + record = 1008; /* 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 = 1718; /* Right-most record in right internal node */ + record = 1859; /* 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 = 1780; /* Right-most record in right-most leaf */ + record = 1921; /* Right-most record in right-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 /* Insert record to force redistribution of rightmost leaf */ - record = u + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 2; + record = u + INSERT_SPLIT_ROOT_NREC + 1; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -1437,19 +1437,19 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 27) + (INSERT_SPLIT_ROOT_NREC / 2) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 29) + (INSERT_SPLIT_ROOT_NREC / 2) + 1)) TEST_ERROR - record = 930; /* Record in root node */ + record = 1008; /* 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 = 1734; /* Right-most record in right internal node */ + record = 1875; /* 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 = 1781; /* Right-most record in right-most leaf */ + record = 1922; /* Right-most record in right-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) @@ -1464,9 +1464,9 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 27) + (INSERT_SPLIT_ROOT_NREC / 2) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 29) + (INSERT_SPLIT_ROOT_NREC / 2) + 1)) TEST_ERROR - record = 930; /* Record in root node */ + record = 1008; /* 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) @@ -1496,9 +1496,9 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 30) + 1)) TEST_ERROR - record = 930; /* Record in root node */ + record = 1008; /* 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) @@ -1523,9 +1523,9 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 30) + 1)) TEST_ERROR - record = 930; /* Record in root node */ + record = 1008; /* 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) @@ -1535,19 +1535,19 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR if(rec_depth != 1) TEST_ERROR - record = 615; /* Record in middle node after insertion point */ + record = 630; /* Record in middle node 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 != 1) TEST_ERROR - record = 553; /* Record in leaf node just after insertion point */ + record = 568; /* 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 /* Add more records to middle leaf, to force a split and a 3 node redistribution on middle leaf */ - for(u = 0; u < (INSERT_SPLIT_ROOT_NREC / 4) + 2; u++) { + for(u = 0; u < (INSERT_SPLIT_ROOT_NREC / 2) + 1; u++) { record = u + (INSERT_SPLIT_ROOT_NREC * 8) + (INSERT_SPLIT_ROOT_NREC / 2) + 1; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -1558,9 +1558,9 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + (INSERT_SPLIT_ROOT_NREC / 4) + 3)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 30) + (INSERT_SPLIT_ROOT_NREC / 2) + 2)) TEST_ERROR - record = 930; /* Record in root node */ + record = 1008; /* 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) @@ -1575,7 +1575,7 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR if(rec_depth != 1) TEST_ERROR - record = 553; /* Record in leaf node just after insertion point */ + record = 568; /* 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) @@ -1587,7 +1587,7 @@ test_insert_level2_leaf_redistrib(hid_t fapl) FAIL_STACK_ERROR /* Make certain that the index is correct */ - if(idx != ((INSERT_SPLIT_ROOT_NREC * 28) + (INSERT_SPLIT_ROOT_NREC / 4) + 3)) + if(idx != ((INSERT_SPLIT_ROOT_NREC * 30) + (INSERT_SPLIT_ROOT_NREC / 2) + 2)) TEST_ERROR /* Close file */ @@ -1662,7 +1662,7 @@ test_insert_level2_leaf_split(hid_t fapl) if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ - for(; u < ((INSERT_SPLIT_ROOT_NREC * 27) + (INSERT_SPLIT_ROOT_NREC / 2)); u++) { + for(; u < ((INSERT_SPLIT_ROOT_NREC * 29) + (INSERT_SPLIT_ROOT_NREC / 2)); u++) { record = u + 2; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -1673,19 +1673,19 @@ test_insert_level2_leaf_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 27) + (INSERT_SPLIT_ROOT_NREC / 2))) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 29) + (INSERT_SPLIT_ROOT_NREC / 2))) TEST_ERROR - record = 883; /* Record in root node */ + record = 946; /* 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 = 1671; /* Right-most record in right internal node */ + record = 1797; /* 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 = 1733; /* Right-most record in right-most leaf */ + record = 1859; /* Right-most record in right-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) @@ -1693,7 +1693,7 @@ test_insert_level2_leaf_split(hid_t fapl) /* Insert enough records to force right-most leaf to split */ for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC / 2) + 1); u++) { - record = u + (INSERT_SPLIT_ROOT_NREC * 27) + (INSERT_SPLIT_ROOT_NREC / 2) + 2; + record = u + (INSERT_SPLIT_ROOT_NREC * 29) + (INSERT_SPLIT_ROOT_NREC / 2) + 2; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ @@ -1703,24 +1703,24 @@ test_insert_level2_leaf_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 28)) + if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 30)) TEST_ERROR - record = 883; /* Record in root node */ + record = 946; /* 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 = 1702; /* Next-to-right-most record in right-most internal node */ + record = 1828; /* Next-to-right-most record in right-most 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 = 1734; /* Right-most record in right-most internal node */ + record = 1860; /* Right-most record in right-most 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 = 1765; /* Right-most record in right-most leaf */ + record = 1891; /* Right-most record in right-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) @@ -1735,9 +1735,9 @@ test_insert_level2_leaf_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 28)) + if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 30)) TEST_ERROR - record = 883; /* Record in root node */ + record = 946; /* 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) @@ -1763,9 +1763,9 @@ test_insert_level2_leaf_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 30) + 1)) TEST_ERROR - record = 883; /* Record in root node */ + record = 946; /* 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) @@ -1795,9 +1795,9 @@ test_insert_level2_leaf_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 30) + 1)) TEST_ERROR - record = 883; /* Record in root node */ + record = 946; /* 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) @@ -1818,7 +1818,7 @@ test_insert_level2_leaf_split(hid_t fapl) if(rec_depth != 0) TEST_ERROR - /* Add another record to middle leaf, to force a 3->4 node split on middle leaf */ + /* Add another record to middle leaf, to force a 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 @@ -1828,24 +1828,24 @@ test_insert_level2_leaf_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 28) + 2)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 30) + 2)) TEST_ERROR - record = 883; /* Record in root node */ + record = 946; /* 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 */ + record = 504; /* Left-most record of 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 */ + record = 537; /* Middle record of 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 */ + record = 568; /* Right-most record of 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) @@ -1862,7 +1862,7 @@ test_insert_level2_leaf_split(hid_t fapl) FAIL_STACK_ERROR /* Make certain that the index is correct */ - if(idx != ((INSERT_SPLIT_ROOT_NREC * 28) + 2)) + if(idx != ((INSERT_SPLIT_ROOT_NREC * 30) + 2)) TEST_ERROR /* Close file */ @@ -1933,9 +1933,9 @@ test_insert_level2_2internal_redistrib(hid_t fapl) FAIL_STACK_ERROR /* Insert enough records to force root to split into 2 internal nodes */ - /* And fill up right internal node, to just before to split it */ - for(u = 0; u < (INSERT_SPLIT_ROOT_NREC * 41); u++) { - record = u + (INSERT_SPLIT_ROOT_NREC * 5) - 1; + /* And fill up right internal node, to just before to redistribute it */ + for(u = 0; u < (INSERT_SPLIT_ROOT_NREC * 44); u++) { + record = u + (INSERT_SPLIT_ROOT_NREC * 6) - 4; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ @@ -1945,26 +1945,26 @@ test_insert_level2_2internal_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 41)) + if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 44)) TEST_ERROR - record = 1195; /* Record in root node */ + record = 1318; /* 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 = 2865; /* Right-most record in right internal node */ + record = 3114; /* 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 = 2896; /* Right-most record in right leaf node */ + record = 3145; /* 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 redistribute right-most internal node */ - record = u + (INSERT_SPLIT_ROOT_NREC * 5) - 1; + record = u + (INSERT_SPLIT_ROOT_NREC * 6) - 4; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -1973,19 +1973,19 @@ test_insert_level2_2internal_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 41) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 44) + 1)) TEST_ERROR - record = 1636; /* Record in root node */ + record = 1822; /* 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 = 2865; /* Right-most record in right internal node */ + record = 3114; /* 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 = 2897; /* Right-most record in right leaf node */ + record = 3146; /* 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) @@ -2000,26 +2000,26 @@ test_insert_level2_2internal_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 41) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 44) + 1)) TEST_ERROR - record = 1636; /* Record in root node */ + record = 1822; /* 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 */ + record = 436; /* 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 */ + record = 374; /* 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; u < ((INSERT_SPLIT_ROOT_NREC * 5) - 1); u++) { + for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC * 6) - 4); u++) { record = u; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -2030,14 +2030,14 @@ test_insert_level2_2internal_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 46)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 50) - 3)) TEST_ERROR - record = 1384; /* Record in root node */ + record = 1570; /* 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 = 46; /* Left-most record in left internal node */ + record = 61; /* 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) @@ -2055,7 +2055,7 @@ test_insert_level2_2internal_redistrib(hid_t fapl) FAIL_STACK_ERROR /* Make certain that the index is correct */ - if(idx != (INSERT_SPLIT_ROOT_NREC * 46)) + if(idx != ((INSERT_SPLIT_ROOT_NREC * 50) - 3)) TEST_ERROR /* Close file */ @@ -2117,7 +2117,7 @@ test_insert_level2_2internal_split(hid_t fapl) /* * Test inserting many records into v2 B-tree */ - TESTING("B-tree insert: split 2 internals to 3 in level 2 B-tree (r->l)"); + TESTING("B-tree insert: split side internal node to 2 in level 2 B-tree (r->l)"); /* * Create v2 B-tree @@ -2127,8 +2127,8 @@ test_insert_level2_2internal_split(hid_t fapl) /* Insert enough records to force root to split into 2 internal nodes */ /* (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; + for(u = 0; u < (INSERT_SPLIT_ROOT_NREC * 59); u++) { + record = u + (INSERT_SPLIT_ROOT_NREC * 14) - (INSERT_SPLIT_ROOT_NREC / 4) + 3; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ @@ -2138,26 +2138,26 @@ test_insert_level2_2internal_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 55)) + if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 59)) TEST_ERROR - record = 2406; /* Record in root node */ + record = 2759; /* 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 */ + record = 4555; /* 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 */ + record = 4586; /* 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; + record = u + (INSERT_SPLIT_ROOT_NREC * 14) - (INSERT_SPLIT_ROOT_NREC / 4) + 3; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -2166,24 +2166,24 @@ test_insert_level2_2internal_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 55) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 59) + 1)) TEST_ERROR - record = 2406; /* Left record in root node */ + record = 2759; /* 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 */ + record = 3704; /* 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 */ + record = 4555; /* 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 */ + record = 4387; /* 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) @@ -2191,33 +2191,33 @@ test_insert_level2_2internal_split(hid_t fapl) PASSED(); - TESTING("B-tree insert: split 2 internals to 3 in level 2 B-tree (l->r)"); + TESTING("B-tree insert: split side internal node to 2 in level 2 B-tree (l->2)"); /* 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)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 59) + 1)) TEST_ERROR - record = 2406; /* Left record in root node */ + record = 2759; /* 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 = 705; /* Left-most record in left internal node */ + record = 932; /* 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 = 643; /* Left-most record in left leaf node */ + record = 870; /* 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 split */ - for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC * 10) + (INSERT_SPLIT_ROOT_NREC / 4) - 2); u++) { + for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC * 14) - (INSERT_SPLIT_ROOT_NREC / 4) + 3); u++) { record = u; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -2228,19 +2228,19 @@ test_insert_level2_2internal_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 65) + (INSERT_SPLIT_ROOT_NREC / 4) - 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 73) - (INSERT_SPLIT_ROOT_NREC / 4) + 4)) TEST_ERROR - record = 658; /* Left record in root node */ + record = 870; /* 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 = 1524; /* Next-to-left-most record in root node */ + record = 1814; /* Next-to-left-most 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 = 46; /* Left-most record in left internal node */ + record = 61; /* 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) @@ -2257,7 +2257,7 @@ test_insert_level2_2internal_split(hid_t fapl) FAIL_STACK_ERROR /* Make certain that the index is correct */ - if(idx != ((INSERT_SPLIT_ROOT_NREC * 65) + (INSERT_SPLIT_ROOT_NREC / 4) - 1)) + if(idx != ((INSERT_SPLIT_ROOT_NREC * 73) - (INSERT_SPLIT_ROOT_NREC / 4) + 4)) TEST_ERROR /* Close file */ @@ -2328,15 +2328,14 @@ test_insert_level2_3internal_redistrib(hid_t fapl) 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 */ + /* Insert enough records to force root to split into 3 internal nodes */ for(u = 0; u < (INSERT_SPLIT_ROOT_NREC * 36); u++) { record = u; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ - for(; u < ((INSERT_SPLIT_ROOT_NREC * 55) + 1); u++) { - record = u + (INSERT_SPLIT_ROOT_NREC * 9) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4); + for(; u < ((INSERT_SPLIT_ROOT_NREC * 59) + 1); u++) { + record = u + (INSERT_SPLIT_ROOT_NREC * 13) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 3; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ @@ -2346,14 +2345,14 @@ test_insert_level2_3internal_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 55) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 59) + 1)) TEST_ERROR - record = 1763; /* Left record in root node */ + record = 1889; /* 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 = 3259; /* Right record in root node */ + record = 3703; /* 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) @@ -2363,19 +2362,19 @@ test_insert_level2_3internal_redistrib(hid_t fapl) FAIL_STACK_ERROR if(rec_depth != 1) TEST_ERROR - record = 2944; /* Record to right of insertion point in middle internal node */ + record = 3199; /* Record to right of insertion point in middle 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 = 2882; /* Record just above insertion point in leaf node */ + record = 3137; /* Record just above insertion point in 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 records to fill up middle internal node */ - for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC * 9) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) - 1); u++) { + for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC * 13) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 2); u++) { record = u + (INSERT_SPLIT_ROOT_NREC * 36); if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -2386,29 +2385,29 @@ test_insert_level2_3internal_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 64) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4))) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 72) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 3)) TEST_ERROR - record = 1763; /* Left record in root node */ + record = 1889; /* 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 = 3259; /* Right record in root node */ + record = 3703; /* 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 = 2862; /* Record to left of insertion point in middle internal node */ + record = 3104; /* Record to left of insertion point in middle 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 = 2911; /* Record to right of insertion point in middle internal node */ + record = 3137; /* Record to right of insertion point in middle 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 = 2882; /* Record just above insertion point in leaf node */ + record = 3135; /* Record just above insertion point in 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) @@ -2424,29 +2423,31 @@ test_insert_level2_3internal_redistrib(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 64) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 72) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 4)) TEST_ERROR - record = 1448; /* Left record in root node */ + record = 1574; /* 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 = 2721; /* Right record in root node */ + record = 3104; /* 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 +#ifdef NONE record = 2862; /* Record to left of insertion point in right internal node (now) */ 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 = 2911; /* Record to right of insertion point in right internal node (now) */ +#endif /* NONE */ + record = 3137; /* Record to right of insertion point in right internal node (now) */ 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 = 2882; /* Record just above insertion point in leaf node */ + record = 3135; /* Record just above insertion point in 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) @@ -2458,7 +2459,7 @@ test_insert_level2_3internal_redistrib(hid_t fapl) FAIL_STACK_ERROR /* Make certain that the index is correct */ - if(idx != ((INSERT_SPLIT_ROOT_NREC * 64) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 1)) + if(idx != ((INSERT_SPLIT_ROOT_NREC * 72) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 4)) TEST_ERROR /* Close file */ @@ -2530,13 +2531,14 @@ test_insert_level2_3internal_split(hid_t fapl) FAIL_STACK_ERROR /* Insert enough records to force root to split into 3 internal nodes */ - for(u = 0; u < (INSERT_SPLIT_ROOT_NREC * 28); u++) { + /* (and fill right internal node) */ + for(u = 0; u < (INSERT_SPLIT_ROOT_NREC * 31); u++) { record = u; if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ - for(; u < ((INSERT_SPLIT_ROOT_NREC * 55) + 1); u++) { - record = u + ((INSERT_SPLIT_ROOT_NREC * 20) + ((2 * INSERT_SPLIT_ROOT_NREC) / 3) + 1); + for(; u < (INSERT_SPLIT_ROOT_NREC * 74); u++) { + record = u + ((INSERT_SPLIT_ROOT_NREC * 13) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 3); if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ @@ -2546,39 +2548,37 @@ test_insert_level2_3internal_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 55) + 1)) + if(bt2_stat.nrecords != (INSERT_SPLIT_ROOT_NREC * 74)) TEST_ERROR - record = 1763; /* Left record in root node */ + record = 1889; /* 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 = 3948; /* Right record in root node */ + record = 3703; /* 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 -#ifdef NONE - record = 2267; /* Record to left of insertion point in middle internal node */ + record = 1952; /* Record to left of insertion point in middle 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 -#endif /* NONE */ - record = 3129; /* Record to right of insertion point in middle internal node */ + record = 2884; /* Record to right of insertion point in middle 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 = 3067; /* Record just above insertion point in leaf node */ + record = 2822; /* Record just after insertion point in 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 records to fill up middle internal node */ - for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC * 20) + ((2 * INSERT_SPLIT_ROOT_NREC) / 3)); u++) { - record = u + (INSERT_SPLIT_ROOT_NREC * 28); + for(u = 0; u < ((INSERT_SPLIT_ROOT_NREC * 13) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 2); u++) { + record = u + (INSERT_SPLIT_ROOT_NREC * 31); if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR } /* end for */ @@ -2588,38 +2588,36 @@ test_insert_level2_3internal_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 75) + ((2 * INSERT_SPLIT_ROOT_NREC) / 3) + 1)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 87) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 2)) TEST_ERROR - record = 1763; /* Left record in root node */ + record = 1889; /* 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 = 3082; /* Right record in root node */ + record = 3703; /* 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 = 3049; /* Record to left of insertion point in middle internal node */ + record = 2789; /* Record to left of insertion point in middle 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 -#ifdef NONE - record = 3129; /* Record to right of insertion point in middle internal node */ + record = 2822; /* Record to right of insertion point in middle 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 -#endif /* NONE */ - record = 3067; /* Record just above insertion point in leaf node */ + record = 2823; /* Record just above insertion point in 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 middle internal node */ - record = u + (INSERT_SPLIT_ROOT_NREC * 28); + record = u + (INSERT_SPLIT_ROOT_NREC * 31); if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0) FAIL_STACK_ERROR @@ -2628,34 +2626,36 @@ test_insert_level2_3internal_split(hid_t fapl) FAIL_STACK_ERROR if(bt2_stat.depth != 2) TEST_ERROR - if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 75) + ((2 * INSERT_SPLIT_ROOT_NREC) / 3) + 2)) + if(bt2_stat.nrecords != ((INSERT_SPLIT_ROOT_NREC * 87) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 3)) TEST_ERROR - record = 1322; /* Left record in root node */ + record = 1889; /* 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 = 2421; /* Middle record in root node */ + record = 2789; /* Middle 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 = 3507; /* Right record in root node */ + record = 3703; /* 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 +#ifdef NONE record = 3049; /* Record to left of insertion point in middle 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 = 3082; /* Record to right of insertion point in middle internal node */ +#endif /* NONE */ + record = 2822; /* Record to right of insertion point in middle 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 = 3067; /* Record just above insertion point in leaf node */ + record = 2823; /* Record just after insertion point in 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) @@ -2667,7 +2667,7 @@ test_insert_level2_3internal_split(hid_t fapl) FAIL_STACK_ERROR /* Make certain that the index is correct */ - if(idx != ((INSERT_SPLIT_ROOT_NREC * 75) + ((2 * INSERT_SPLIT_ROOT_NREC) / 3) + 2)) + if(idx != ((INSERT_SPLIT_ROOT_NREC * 87) + ((3 * INSERT_SPLIT_ROOT_NREC) / 4) + 3)) TEST_ERROR /* Close file */ @@ -2715,6 +2715,7 @@ test_insert_lots(hid_t fapl) 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 */ herr_t ret; /* Generic error return value */ @@ -2726,8 +2727,14 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time); #endif /* QAK */ HDsrandom((unsigned long)curr_time); + /* + * Test inserting many records into v2 B-tree + */ + TESTING("B-tree insert: create random level 4 B-tree"); + /* 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 4) extra2 = HDstrtoll(argv[4], NULL, 0); + if(argc > 5) + extra3 = HDstrtoll(argv[5], NULL, 0); /* * Read the signature at the specified file position. @@ -235,88 +237,42 @@ main(int argc, char *argv[]) HDexit(4); } /* end switch */ - } else if(!HDmemcmp(sig, H5B2_BRCH_MAGIC, H5B2_SIZEOF_MAGIC)) { + } else if(!HDmemcmp(sig, H5B2_INT_MAGIC, H5B2_SIZEOF_MAGIC)) { /* * Debug a v2 B-tree. B-trees are debugged through the B-tree - * subclass. The subclass identifier is two bytes after the - * B-tree signature. - */ - H5B2_subid_t subtype = (H5B2_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; - - /* Check for enough valid parameters */ - if(extra == 0 || extra2 == 0) { - fprintf(stderr, "ERROR: Need v2 B-tree header address and number of records node in order to dump internal node\n"); - fprintf(stderr, "v2 B-tree internal node usage:\n"); - fprintf(stderr, "\th5debug \n"); - HDexit(4); - } /* end if */ - - /* Note: a depth of '2' is used here because the actual depth isn't - * important, as long as it's > 1, to indicate a 'branch' internal - * node. - */ - switch(subtype) { - case H5B2_TEST_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5B2_TEST, extra, (unsigned)extra2, (unsigned)2); - break; - - case H5B2_FHEAP_HUGE_INDIR_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_INDIR, extra, (unsigned)extra2, (unsigned)2); - break; - - case H5B2_FHEAP_HUGE_FILT_INDIR_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_FILT_INDIR, extra, (unsigned)extra2, (unsigned)2); - break; - - case H5B2_FHEAP_HUGE_DIR_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_DIR, extra, (unsigned)extra2, (unsigned)2); - break; - - case H5B2_FHEAP_HUGE_FILT_DIR_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_FILT_DIR, extra, (unsigned)extra2, (unsigned)2); - break; - - default: - fprintf(stderr, "Unknown B-tree subtype %u\n", (unsigned)(subtype)); - HDexit(4); - } /* end switch */ - - } else if(!HDmemcmp(sig, H5B2_TWIG_MAGIC, H5B2_SIZEOF_MAGIC)) { - /* - * Debug a v2 B-tree. B-trees are debugged through the B-tree - * subclass. The subclass identifier is two bytes after the + * subclass. The subclass identifier is the byte after the * B-tree signature. */ - H5B2_subid_t subtype = (H5B2_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; + H5B2_subid_t subtype = (H5B2_subid_t)sig[H5B2_SIZEOF_MAGIC + 1]; /* Check for enough valid parameters */ - if(extra == 0 || extra2 == 0) { - fprintf(stderr, "ERROR: Need v2 B-tree header address and number of records node in order to dump internal node\n"); + if(extra == 0 || extra2 == 0 || extra3 == 0) { + fprintf(stderr, "ERROR: Need v2 B-tree header address and the node's number of records and depth in order to dump internal node\n"); + fprintf(stderr, "NOTE: Leaf nodes are depth 0, the internal nodes above them are depth 1, etc.\n"); fprintf(stderr, "v2 B-tree internal node usage:\n"); - fprintf(stderr, "\th5debug \n"); + fprintf(stderr, "\th5debug \n"); HDexit(4); } /* end if */ - /* Note: a depth of '1' is used here to indicate a 'twig' internal node */ switch(subtype) { case H5B2_TEST_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5B2_TEST, extra, (unsigned)extra2, (unsigned)1); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5B2_TEST, extra, (unsigned)extra2, (unsigned)extra3); break; case H5B2_FHEAP_HUGE_INDIR_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_INDIR, extra, (unsigned)extra2, (unsigned)1); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_INDIR, extra, (unsigned)extra2, (unsigned)extra3); break; case H5B2_FHEAP_HUGE_FILT_INDIR_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_FILT_INDIR, extra, (unsigned)extra2, (unsigned)1); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_FILT_INDIR, extra, (unsigned)extra2, (unsigned)extra3); break; case H5B2_FHEAP_HUGE_DIR_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_DIR, extra, (unsigned)extra2, (unsigned)1); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_DIR, extra, (unsigned)extra2, (unsigned)extra3); break; case H5B2_FHEAP_HUGE_FILT_DIR_ID: - status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_FILT_DIR, extra, (unsigned)extra2, (unsigned)1); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_FILT_DIR, extra, (unsigned)extra2, (unsigned)extra3); break; default: @@ -327,10 +283,10 @@ main(int argc, char *argv[]) } else if(!HDmemcmp(sig, H5B2_LEAF_MAGIC, H5B2_SIZEOF_MAGIC)) { /* * Debug a v2 B-tree. B-trees are debugged through the B-tree - * subclass. The subclass identifier is two bytes after the + * subclass. The subclass identifier is the byte after the * B-tree signature. */ - H5B2_subid_t subtype = (H5B2_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; + H5B2_subid_t subtype = (H5B2_subid_t)sig[H5B2_SIZEOF_MAGIC + 1]; /* Check for enough valid parameters */ if(extra == 0 || extra2 == 0) { -- cgit v0.12