diff options
| -rw-r--r-- | src/H5B2.c | 39 | ||||
| -rw-r--r-- | src/H5B2cache.c | 86 | ||||
| -rw-r--r-- | src/H5B2dbg.c | 25 | ||||
| -rw-r--r-- | src/H5B2int.c | 248 | ||||
| -rw-r--r-- | src/H5B2pkg.h | 42 | ||||
| -rw-r--r-- | test/btree2.c | 2 | ||||
| -rw-r--r-- | tools/misc/h5debug.c | 61 |
7 files changed, 357 insertions, 146 deletions
@@ -197,8 +197,9 @@ 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>0 && bt2->root.node_nrec==shared->split_int_nrec)) { + else if((bt2->depth == 0 && bt2->root.node_nrec == shared->split_leaf_nrec) || + (bt2->depth == 1 && bt2->root.node_nrec == shared->split_twig_nrec) || + (bt2->depth > 0 && bt2->root.node_nrec == shared->split_brch_nrec)) { /* Split root node */ if(H5B2_split_root(f, dxpl_id, bt2, &bt2_flags, bt2->shared) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node") @@ -356,10 +357,10 @@ H5B2_find(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, curr_node_ptr = bt2->root; /* Current depth of the tree */ - depth=bt2->depth; + depth = bt2->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; @@ -373,12 +374,12 @@ H5B2_find(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, /* Walk down B-tree to find record or leaf node where record is located */ cmp = -1; - while(depth>0 && cmp != 0) { + while(depth > 0 && cmp != 0) { H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ H5B2_node_ptr_t next_node_ptr; /* Node pointer info for next node */ /* Lock B-tree current node */ - if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, &(curr_node_ptr.node_nrec), bt2_shared, H5AC_READ))) + if(NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, curr_node_ptr.addr, curr_node_ptr.node_nrec, depth, H5AC_READ))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Locate node pointer for child */ @@ -519,10 +520,10 @@ H5B2_index(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, curr_node_ptr = bt2->root; /* Current depth of the tree */ - depth=bt2->depth; + depth = bt2->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; @@ -539,13 +540,13 @@ H5B2_index(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree doesn't have that many records") /* Walk down B-tree to find record or leaf node where record is located */ - while(depth>0) { + while(depth > 0) { H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ H5B2_node_ptr_t next_node_ptr; /* Node pointer info for next node */ unsigned u; /* Local index variable */ /* Lock B-tree current node */ - if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, &(curr_node_ptr.node_nrec), bt2_shared, H5AC_READ))) + if(NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, curr_node_ptr.addr, curr_node_ptr.node_nrec, depth, H5AC_READ))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Search for record with correct index */ @@ -556,7 +557,7 @@ H5B2_index(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, next_node_ptr=internal->node_ptrs[u]; /* Unlock current node */ - if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0) + if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node") /* Set pointer to next node to load */ @@ -927,24 +928,24 @@ H5B2_modify(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; /* 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 = bt2->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; /* Get the pointer to the shared B-tree info */ shared=H5RC_GET_OBJ(bt2_shared); @@ -956,13 +957,13 @@ H5B2_modify(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, /* Walk down B-tree to find record or leaf node where record is located */ cmp = -1; - while(depth>0 && cmp != 0) { + while(depth > 0 && cmp != 0) { unsigned internal_flags = H5AC__NO_FLAGS_SET; H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ H5B2_node_ptr_t next_node_ptr; /* Node pointer info for next node */ /* Lock B-tree current node */ - if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, &(curr_node_ptr.node_nrec), bt2_shared, H5AC_WRITE))) + if(NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, curr_node_ptr.addr, curr_node_ptr.node_nrec, depth, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Locate node pointer for child */ diff --git a/src/H5B2cache.c b/src/H5B2cache.c index e23791d..8f8f71b 100644 --- a/src/H5B2cache.c +++ b/src/H5B2cache.c @@ -454,10 +454,9 @@ H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t UNUSED *bt2, size_t *size_ptr) *------------------------------------------------------------------------- */ static H5B2_internal_t * -H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nrec, void *_bt2_shared) +H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_udata, void UNUSED *udata2) { - const unsigned *nrec = (const unsigned *)_nrec; - H5RC_t *bt2_shared = (H5RC_t *)_bt2_shared; /* Ref counter for shared B-tree info */ + const H5B2_int_load_ud1_t *udata = (const H5B2_int_load_ud1_t *)_udata; /* Pointer to user data */ H5B2_shared_t *shared; /* Shared B-tree information */ H5B2_internal_t *internal = NULL; /* Internal node read */ uint8_t *p; /* Pointer into raw data buffer */ @@ -473,14 +472,15 @@ H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nre /* Check arguments */ HDassert(f); HDassert(H5F_addr_defined(addr)); - HDassert(bt2_shared); + HDassert(udata); + /* Allocate new internal node and reset cache info */ if(NULL == (internal = H5FL_MALLOC(H5B2_internal_t))) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") HDmemset(&internal->cache_info, 0, sizeof(H5AC_info_t)); /* Share common B-tree information */ - internal->shared = bt2_shared; + internal->shared = udata->bt2_shared; H5RC_INC(internal->shared); /* Get the pointer to the shared B-tree info */ @@ -494,8 +494,14 @@ H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nre p = shared->page; /* Magic number */ - if(HDmemcmp(p, H5B2_INT_MAGIC, (size_t)H5B2_SIZEOF_MAGIC)) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree internal node signature") + 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 */ p += H5B2_SIZEOF_MAGIC; /* Version */ @@ -506,16 +512,29 @@ H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nre if (*p++ != (uint8_t)shared->type->id) HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type") - /* Allocate space for the native keys in memory */ - if((internal->int_native = H5FL_FAC_MALLOC(shared->int_fac)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal native keys") + /* 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->node_ptr_fac)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal node pointers") + /* 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") - /* Set the number of records in the leaf */ - internal->nrec = *nrec; + /* 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 */ + + /* Set the number of records in the leaf & it's depth */ + internal->nrec = udata->nrec; + internal->depth = udata->depth; /* Deserialize records for internal node */ native = internal->int_native; @@ -535,7 +554,10 @@ H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nre /* Decode node pointer */ H5F_addr_decode(f, (const uint8_t **)&p, &(int_node_ptr->addr)); UINT16DECODE(p, int_node_ptr->node_nrec); - H5F_DECODE_LENGTH(f, p, int_node_ptr->all_nrec); + if(udata->depth > 1) + H5F_DECODE_LENGTH(f, p, int_node_ptr->all_nrec) + else + int_node_ptr->all_nrec = int_node_ptr->node_nrec; /* Move to next node pointer */ int_node_ptr++; @@ -604,7 +626,10 @@ H5B2_cache_internal_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr p = shared->page; /* Magic number */ - HDmemcpy(p, H5B2_INT_MAGIC, (size_t)H5B2_SIZEOF_MAGIC); + 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); p += H5B2_SIZEOF_MAGIC; /* Version # */ @@ -631,7 +656,8 @@ H5B2_cache_internal_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr /* Encode node pointer */ H5F_addr_encode(f, &p, int_node_ptr->addr); UINT16ENCODE(p, int_node_ptr->node_nrec); - H5F_ENCODE_LENGTH(f, p, int_node_ptr->all_nrec); + if(internal->depth > 1) + H5F_ENCODE_LENGTH(f, p, int_node_ptr->all_nrec); /* Move to next node pointer */ int_node_ptr++; @@ -690,13 +716,25 @@ H5B2_cache_internal_dest(H5F_t UNUSED *f, H5B2_internal_t *internal) shared = H5RC_GET_OBJ(internal->shared); HDassert(shared); - /* Release internal node's native key buffer */ - if(internal->int_native) - H5FL_FAC_FREE(shared->int_fac, internal->int_native); + /* 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 node's node pointer buffer */ - if(internal->node_ptrs) - H5FL_FAC_FREE(shared->node_ptr_fac, internal->node_ptrs); + /* 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 'branch' node's node pointer buffer */ + if(internal->node_ptrs) + H5FL_FAC_FREE(shared->brch_node_ptr_fac, internal->node_ptrs); + } /* end else */ /* Decrement reference count on shared B-tree info */ if(internal->shared) diff --git a/src/H5B2dbg.c b/src/H5B2dbg.c index 6f1799f..c1bea51 100644 --- a/src/H5B2dbg.c +++ b/src/H5B2dbg.c @@ -151,8 +151,11 @@ H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, "Address of root node:", bt2->root.addr); HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Max. number of records per internal node:", - shared->internal_nrec); + "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); @@ -163,14 +166,20 @@ H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, "Merge percent:", shared->merge_percent); HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Internal records to split at:", - shared->split_int_nrec); + "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 records to merge at:", - shared->merge_int_nrec); + "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); @@ -198,7 +207,7 @@ done: */ herr_t H5B2_int_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth, - const H5B2_class_t *type, haddr_t hdr_addr, unsigned nrec) + const H5B2_class_t *type, haddr_t hdr_addr, unsigned nrec, unsigned depth) { H5B2_t *bt2 = NULL; H5B2_internal_t *internal = NULL; @@ -234,7 +243,7 @@ H5B2_int_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, /* * Load the B-tree internal node */ - if(NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, addr, &nrec, bt2->shared, H5AC_READ))) + if(NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2->shared, addr, nrec, depth, H5AC_READ))) HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node") /* Release the B-tree header */ diff --git a/src/H5B2int.c b/src/H5B2int.c index 6de7514..0df5706 100644 --- a/src/H5B2int.c +++ b/src/H5B2int.c @@ -41,10 +41,15 @@ /* Local Macros */ /****************/ -/* Number of records that fit into internal node */ +/* Number of records that fit into internal "branch" node */ /* (accounts for extra node pointer by counting it in with the prefix bytes) */ -#define H5B2_NUM_INT_REC(f, n, r) \ - (((n) - (H5B2_INT_PREFIX_SIZE + H5B2_NODE_POINTER_SIZE(f))) / ((r) + H5B2_NODE_POINTER_SIZE(f))) +#define H5B2_NUM_BRCH_REC(f, n, r) \ + (((n) - (H5B2_INT_PREFIX_SIZE + H5B2_BRCH_POINTER_SIZE(f))) / ((r) + H5B2_BRCH_POINTER_SIZE(f))) + +/* Number of records that fit into internal "twig" node */ +/* (accounts for extra node pointer by counting it in with the prefix bytes) */ +#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 leaf node */ #define H5B2_NUM_LEAF_REC(n, r) \ @@ -70,7 +75,7 @@ /* Helper functions */ static herr_t H5B2_shared_free(void *_shared); static herr_t H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, - H5B2_node_ptr_t *node_ptr); + H5B2_node_ptr_t *node_ptr, unsigned depth); static herr_t H5B2_redistribute2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *internal, unsigned idx); static herr_t H5B2_split2(H5F_t *f, hid_t dxpl_id, unsigned depth, @@ -163,9 +168,13 @@ H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, shared->rrec_size = rrec_size; /* Compute derived information */ - shared->internal_nrec = H5B2_NUM_INT_REC(f, shared->node_size, shared->rrec_size); - shared->split_int_nrec = (shared->internal_nrec * shared->split_percent) / 100; - shared->merge_int_nrec = (shared->internal_nrec * shared->merge_percent) / 100; + 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; @@ -181,24 +190,32 @@ 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 node native record storage */ - if((shared->int_fac = H5FL_fac_init(type->nrec_size * shared->internal_nrec)) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal node native key block factory") + /* 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 node node pointer storage */ - if((shared->node_ptr_fac = H5FL_fac_init(sizeof(H5B2_node_ptr_t) * (shared->internal_nrec + 1))) == NULL) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal node node pointer 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") + + /* 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") /* Allocate array of pointers to internal node native keys */ - if((shared->nat_off = H5FL_SEQ_MALLOC(size_t, MAX(shared->internal_nrec, shared->leaf_nrec))) == NULL) + if((shared->nat_off = H5FL_SEQ_MALLOC(size_t, MAX3(shared->branch_nrec, shared->twig_nrec, shared->leaf_nrec))) == NULL) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") /* Initialize offsets in native key block */ - for(u = 0; u < MAX(shared->internal_nrec, shared->leaf_nrec); u++) + for(u = 0; u < MAX3(shared->branch_nrec, shared->twig_nrec, shared->leaf_nrec); u++) shared->nat_off[u]=type->nrec_size*u; /* Make shared B-tree info reference counted */ @@ -242,24 +259,34 @@ H5B2_shared_free(void *_shared) if(shared->page) H5FL_BLK_FREE(node_page, shared->page); - /* Destroy factory for internal node native record storage */ - if(shared->int_fac) - if(H5FL_fac_term(shared->int_fac) < 0) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal node native key block factory") + /* 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 node node pointer storage */ - if(shared->node_ptr_fac) - if(H5FL_fac_term(shared->node_ptr_fac) < 0) - HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal node node pointer 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); + H5FL_SEQ_FREE(size_t, shared->nat_off); /* Free the shared B-tree info itself */ H5FL_FREE(H5B2_shared_t, shared); @@ -363,8 +390,8 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr, H5B2_node_ptr_t new_int_ptr; /* Node pointer to manage new internal node */ /* Create new internal node */ - new_int_ptr.all_nrec=new_int_ptr.node_nrec=0; - if(H5B2_create_internal(f, dxpl_id, bt2_shared, &new_int_ptr)<0) + new_int_ptr.all_nrec = new_int_ptr.node_nrec = 0; + if(H5B2_create_internal(f, dxpl_id, bt2_shared, &new_int_ptr, bt2->depth) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node") /* Setup information for unlocking child nodes */ @@ -373,9 +400,9 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr, right_addr = new_int_ptr.addr; /* Protect both leafs */ - if (NULL == (old_int = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, left_addr, &(bt2->root.node_nrec), bt2_shared, H5AC_WRITE))) + if(NULL == (old_int = H5B2_protect_internal(f, dxpl_id, bt2_shared, left_addr, bt2->root.node_nrec, bt2->depth, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") - if (NULL == (new_int = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, right_addr, &(new_int_ptr.node_nrec), bt2_shared, H5AC_WRITE))) + if(NULL == (new_int = H5B2_protect_internal(f, dxpl_id, bt2_shared, right_addr, new_int_ptr.node_nrec, bt2->depth, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* More setup for child nodes */ @@ -434,11 +461,11 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr, sizeof(H5B2_node_ptr_t)*(old_root_nrec-mid_record)); /* Create new internal node to use as root */ - if(H5B2_create_internal(f, dxpl_id, bt2_shared, &(bt2->root))<0) + if(H5B2_create_internal(f, dxpl_id, bt2_shared, &(bt2->root), (bt2->depth + 1)) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node") /* Protect new internal node */ - if (NULL == (new_root = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, bt2->root.addr, &(bt2->root.node_nrec), bt2_shared, H5AC_WRITE))) + if (NULL == (new_root = H5B2_protect_internal(f, dxpl_id, bt2_shared, bt2->root.addr, bt2->root.node_nrec, (bt2->depth + 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Copy "middle" record to new internal node */ @@ -453,7 +480,7 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, unsigned *bt2_flags_ptr, new_root->node_ptrs[1].node_nrec = *right_nrec = old_root_nrec-(mid_record+1); /* Determine total number of records in new child nodes */ - if(bt2->depth>0) { + if(bt2->depth > 0) { unsigned u; /* Local index variable */ hsize_t new_left_all_nrec; /* New total number of records in left child */ hsize_t new_right_all_nrec; /* New total number of records in right child */ @@ -551,7 +578,7 @@ H5B2_redistribute2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *int HDassert(shared); /* Check for the kind of B-tree node to redistribute */ - if(depth>1) { + if(depth > 1) { H5B2_internal_t *left_internal; /* Pointer to left internal node */ H5B2_internal_t *right_internal; /* Pointer to right internal node */ @@ -561,9 +588,9 @@ H5B2_redistribute2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *int right_addr = internal->node_ptrs[idx+1].addr; /* Lock left & right B-tree child nodes */ - if (NULL == (left_internal = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE))) + if (NULL == (left_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, left_addr, internal->node_ptrs[idx].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node") - if (NULL == (right_internal = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE))) + if (NULL == (right_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, right_addr, internal->node_ptrs[idx+1].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node") /* More setup for child nodes */ @@ -787,7 +814,7 @@ H5B2_split2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *curr_node_ 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) { + if(depth > 1) { H5B2_internal_t *left_internal; /* Pointer to left internal node */ H5B2_internal_t *middle_internal; /* Pointer to middle internal node */ H5B2_internal_t *right_internal; /* Pointer to right internal node */ @@ -798,21 +825,21 @@ H5B2_split2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *curr_node_ right_addr = internal->node_ptrs[idx+2].addr; /* Lock left & right B-tree child nodes */ - if (NULL == (left_internal = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE))) + if(NULL == (left_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, left_addr, internal->node_ptrs[idx].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") - if (NULL == (right_internal = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx+2].node_nrec), internal->shared, H5AC_WRITE))) + if(NULL == (right_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, right_addr, internal->node_ptrs[idx+2].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Create new empty "middle" internal node */ internal->node_ptrs[idx+1].all_nrec=internal->node_ptrs[idx+1].node_nrec=0; - if(H5B2_create_internal(f, dxpl_id, internal->shared, &(internal->node_ptrs[idx+1]))<0) + if(H5B2_create_internal(f, dxpl_id, internal->shared, &(internal->node_ptrs[idx + 1]), (depth - 1)) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node") /* Setup information for unlocking middle child node */ middle_addr = internal->node_ptrs[idx+1].addr; /* Lock "middle" internal node */ - if (NULL == (middle_internal = H5AC_protect(f, dxpl_id, child_class, middle_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE))) + if(NULL == (middle_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, middle_addr, internal->node_ptrs[idx+1].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* More setup for accessing child node information */ @@ -1051,7 +1078,7 @@ H5B2_redistribute3(H5F_t *f, hid_t dxpl_id, unsigned depth, HDassert(shared); /* Check for the kind of B-tree node to redistribute */ - if(depth>1) { + if(depth > 1) { H5B2_internal_t *left_internal; /* Pointer to left internal node */ H5B2_internal_t *middle_internal; /* Pointer to middle internal node */ H5B2_internal_t *right_internal; /* Pointer to right internal node */ @@ -1063,11 +1090,11 @@ H5B2_redistribute3(H5F_t *f, hid_t dxpl_id, unsigned depth, right_addr = internal->node_ptrs[idx+1].addr; /* Lock B-tree child nodes */ - if (NULL == (left_internal = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx-1].node_nrec), internal->shared, H5AC_WRITE))) + 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 = H5AC_protect(f, dxpl_id, child_class, middle_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE))) + 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 = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE))) + if (NULL == (right_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, right_addr, internal->node_ptrs[idx+1].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* More setup for child nodes */ @@ -1432,7 +1459,7 @@ H5B2_split3(H5F_t *f, hid_t dxpl_id, unsigned depth, 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) { + 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 */ @@ -1445,23 +1472,23 @@ H5B2_split3(H5F_t *f, hid_t dxpl_id, unsigned depth, right_addr = internal->node_ptrs[idx+2].addr; /* Lock left & right B-tree child nodes */ - if (NULL == (left_internal = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx-1].node_nrec), internal->shared, H5AC_WRITE))) + 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 = H5AC_protect(f, dxpl_id, child_class, middle_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE))) + 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 = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx+2].node_nrec), internal->shared, H5AC_WRITE))) + 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]))<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 = H5AC_protect(f, dxpl_id, child_class, new_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE))) + 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 */ @@ -1758,9 +1785,9 @@ H5B2_merge2(H5F_t *f, hid_t dxpl_id, unsigned depth, right_addr = internal->node_ptrs[idx+1].addr; /* Lock left & right B-tree child nodes */ - if(NULL == (left_internal = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE))) + if(NULL == (left_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, left_addr, internal->node_ptrs[idx].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") - if(NULL == (right_internal = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE))) + if(NULL == (right_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, right_addr, internal->node_ptrs[idx+1].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* More setup for accessing child node information */ @@ -1908,7 +1935,7 @@ H5B2_merge3(H5F_t *f, hid_t dxpl_id, unsigned depth, HDassert(shared); /* Check for the kind of B-tree node to split */ - if(depth>1) { + if(depth > 1) { H5B2_internal_t *left_internal; /* Pointer to left internal node */ H5B2_internal_t *middle_internal; /* Pointer to middle internal node */ H5B2_internal_t *right_internal; /* Pointer to right internal node */ @@ -1920,11 +1947,11 @@ H5B2_merge3(H5F_t *f, hid_t dxpl_id, unsigned depth, right_addr = internal->node_ptrs[idx+1].addr; /* Lock B-tree child nodes */ - if (NULL == (left_internal = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx-1].node_nrec), internal->shared, H5AC_WRITE))) + 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 = H5AC_protect(f, dxpl_id, child_class, middle_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE))) + 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 = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE))) + if (NULL == (right_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, right_addr, internal->node_ptrs[idx+1].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* More setup for accessing child node information */ @@ -2123,7 +2150,7 @@ H5B2_swap_leaf(H5F_t *f, hid_t dxpl_id, unsigned depth, HDassert(shared); /* Check for the kind of B-tree node to swap */ - if(depth>1) { + if(depth > 1) { H5B2_internal_t *child_internal; /* Pointer to internal node */ /* Setup information for unlocking child node */ @@ -2131,7 +2158,7 @@ H5B2_swap_leaf(H5F_t *f, hid_t dxpl_id, unsigned depth, child_addr = internal->node_ptrs[idx].addr; /* Lock B-tree child nodes */ - if (NULL == (child_internal = H5AC_protect(f, dxpl_id, child_class, child_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE))) + if(NULL == (child_internal = H5B2_protect_internal(f, dxpl_id, internal->shared, child_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") /* More setup for accessing child node information */ @@ -2289,13 +2316,13 @@ H5B2_insert_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, /* Check arguments. */ HDassert(f); HDassert(bt2_shared); - HDassert(depth>0); + HDassert(depth > 0); HDassert(parent_cache_info_flags_ptr); HDassert(curr_node_ptr); HDassert(H5F_addr_defined(curr_node_ptr->addr)); /* Lock current B-tree node */ - if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE))) + if(NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, curr_node_ptr->addr, curr_node_ptr->node_nrec, depth, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Get the pointer to the shared B-tree info */ @@ -2323,10 +2350,12 @@ H5B2_insert_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, retries = 2; /* Determine the correct number of records to split at */ - if(depth==1) + if(depth == 1) split_nrec = shared->split_leaf_nrec; + else if(depth == 2) + split_nrec = shared->split_twig_nrec; else - split_nrec = shared->split_int_nrec; + split_nrec = shared->split_brch_nrec; /* Preemptively split/redistribute a node we will enter */ while(internal->node_ptrs[idx].node_nrec == split_nrec) { @@ -2489,7 +2518,8 @@ done: *------------------------------------------------------------------------- */ static herr_t -H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_t *node_ptr) +H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, + H5B2_node_ptr_t *node_ptr, unsigned depth) { H5B2_internal_t *internal=NULL; /* Pointer to new internal node created */ H5B2_shared_t *shared; /* Shared B-tree information */ @@ -2501,6 +2531,7 @@ H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_ HDassert(f); HDassert(bt2_shared); HDassert(node_ptr); + HDassert(depth > 0); /* Allocate memory for internal node information */ if (NULL==(internal = H5FL_MALLOC(H5B2_internal_t))) @@ -2517,22 +2548,41 @@ H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_ shared=H5RC_GET_OBJ(internal->shared); HDassert(shared); - /* Allocate space for the native keys in memory */ - if((internal->int_native=H5FL_FAC_MALLOC(shared->int_fac))==NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal native keys") + /* 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->internal_nrec); +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->node_ptr_fac))==NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal node pointers") + /* 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") #ifdef H5_USING_PURIFY -HDmemset(internal->node_ptrs,0,sizeof(H5B2_node_ptr_t)*(shared->internal_nrec+1)); +HDmemset(internal->int_native, 0, shared->type->nrec_size * shared->branch_nrec); #endif /* H5_USING_PURIFY */ - /* Set number of records */ - internal->nrec=0; + /* 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") +#ifdef H5_USING_PURIFY +HDmemset(internal->node_ptrs, 0, sizeof(H5B2_node_ptr_t) * (shared->branch_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))) @@ -2553,6 +2603,48 @@ done: /*------------------------------------------------------------------------- + * Function: H5B2_protect_internal + * + * Purpose: "Protect" an internal node in the metadata cache + * + * Return: Pointer to internal node on success/NULL on failure + * + * Programmer: Quincey Koziol + * koziol@hdfgroup.org + * Aug 25 2006 + * + *------------------------------------------------------------------------- + */ +H5B2_internal_t * +H5B2_protect_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, haddr_t addr, + unsigned nrec, unsigned depth, H5AC_protect_t rw) +{ + H5B2_int_load_ud1_t udata; /* User data to pass through to cache 'load' callback */ + H5B2_internal_t *ret_value; /* Return value */ + + FUNC_ENTER_NOAPI_NOINIT(H5B2_protect_internal) + + /* Check arguments. */ + HDassert(f); + HDassert(bt2_shared); + HDassert(H5F_addr_defined(addr)); + HDassert(depth > 0); + + /* Set up user data for callback */ + udata.bt2_shared = bt2_shared; + udata.nrec = nrec; + udata.depth = depth; + + /* Protect the internal node */ + if(NULL == (ret_value = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, addr, &udata, NULL, rw))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to load B-tree internal node") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_protect_internal() */ + + +/*------------------------------------------------------------------------- * Function: H5B2_iterate_node * * Purpose: Iterate over all the records from a B-tree node, in "in-order" @@ -2597,7 +2689,7 @@ H5B2_iterate_node(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, unsigned depth, H5B2_internal_t *internal; /* Pointer to internal node */ /* Lock the current B-tree node */ - if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node->addr, &(curr_node->node_nrec), bt2_shared, H5AC_READ))) + if (NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, curr_node->addr, curr_node->node_nrec, depth, H5AC_READ))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Set up information about current node */ @@ -2783,7 +2875,7 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, /* Lock current B-tree node */ internal_addr = curr_node_ptr->addr; - if(NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, internal_addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE))) + if(NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, internal_addr, curr_node_ptr->node_nrec, depth, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Get the pointer to the shared B-tree info */ @@ -2793,8 +2885,10 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_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_int_nrec; + merge_nrec = shared->merge_brch_nrec; /* Check for needing to collapse the root node */ /* (The root node is the only internal node allowed to have 1 record) */ @@ -3089,7 +3183,7 @@ H5B2_neighbor_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, HDassert(op); /* Lock current B-tree node */ - if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_READ))) + if (NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, curr_node_ptr->addr, curr_node_ptr->node_nrec, depth, H5AC_READ))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Get the pointer to the shared B-tree info */ @@ -3172,7 +3266,7 @@ H5B2_delete_node(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, unsigned depth, unsigned u; /* Local index */ /* Lock the current B-tree node */ - if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node->addr, &(curr_node->node_nrec), bt2_shared, H5AC_WRITE))) + if (NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, curr_node->addr, curr_node->node_nrec, depth, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") /* Set up information about current node */ diff --git a/src/H5B2pkg.h b/src/H5B2pkg.h index 1b25ce7..cd81022 100644 --- a/src/H5B2pkg.h +++ b/src/H5B2pkg.h @@ -44,14 +44,18 @@ /* B-tree signatures */ #define H5B2_HDR_MAGIC "BTHD" /* Header */ -#define H5B2_INT_MAGIC "BTND" /* Internal node */ +#define H5B2_BRCH_MAGIC "BTBR" /* Internal "branch" node */ +#define H5B2_TWIG_MAGIC "BTTW" /* Internal "twig" 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 "node pointer" (on disk) */ -#define H5B2_NODE_POINTER_SIZE(f) (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE+H5F_SIZEOF_SIZE(f)) +/* 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 "twig node pointer" (on disk) */ +#define H5B2_TWIG_POINTER_SIZE(f) (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE) /* Size of checksum information (on disk) */ #define H5B2_SIZEOF_CHKSUM 4 @@ -75,7 +79,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_NODE_POINTER_SIZE(f) /* Node pointer to root node in tree */ \ + + H5B2_BRCH_POINTER_SIZE(f) /* Node pointer to root node in tree */ \ ) /* Size of the v2 B-tree internal node prefix */ @@ -124,9 +128,11 @@ 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 *int_fac; /* Factory for internal node native record blocks */ + 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 *node_ptr_fac; /* Factory for internal node node pointer 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 */ @@ -136,9 +142,12 @@ typedef struct H5B2_shared_t { size_t rrec_size; /* Size of "raw" (on disk) record, in bytes */ /* Derived information from user's information */ - size_t internal_nrec; /* Number of records which fit into an internal node */ - size_t split_int_nrec; /* Number of records to split an internal node at */ - size_t merge_int_nrec; /* Number of records to merge an internal node at */ + 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 */ @@ -176,8 +185,16 @@ typedef struct H5B2_internal_t { uint8_t *int_native; /* Pointer to native records */ H5B2_node_ptr_t *node_ptrs; /* Pointer to node pointers */ unsigned nrec; /* Number of records in node */ + unsigned depth; /* Depth of this node in the B-tree */ } H5B2_internal_t; +/* User data for metadata cache 'load' callback */ +typedef struct { + H5RC_t *bt2_shared; /* Ref counter for shared B-tree info */ + unsigned nrec; /* Number of records in node to load */ + unsigned depth; /* Depth of node to load */ +} H5B2_int_load_ud1_t; + /*****************************/ /* Package Private Variables */ @@ -215,6 +232,11 @@ H5_DLLVAR const H5B2_class_t H5B2_TEST[1]; 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); +/* Routines for operating on internal nodes */ +H5_DLL H5B2_internal_t *H5B2_protect_internal(H5F_t *f, hid_t dxpl_id, + H5RC_t *bt2_shared, haddr_t addr, unsigned nrec, unsigned depth, + H5AC_protect_t rw); + /* 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); @@ -267,7 +289,7 @@ H5_DLL herr_t H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth, const H5B2_class_t *type); H5_DLL herr_t H5B2_int_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth, const H5B2_class_t *type, - haddr_t hdr_addr, unsigned nrec); + haddr_t hdr_addr, unsigned nrec, unsigned depth); H5_DLL herr_t H5B2_leaf_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth, const H5B2_class_t *type, haddr_t hdr_addr, unsigned nrec); diff --git a/test/btree2.c b/test/btree2.c index fb77e17..66613a1 100644 --- a/test/btree2.c +++ b/test/btree2.c @@ -34,7 +34,7 @@ const char *FILENAME[] = { }; #define INSERT_SPLIT_ROOT_NREC 80 -#define INSERT_MANY (320*1000) +#define INSERT_MANY (500*1000) #define FIND_MANY (INSERT_MANY/100) #define FIND_NEIGHBOR 1000 #define DELETE_SMALL 10 diff --git a/tools/misc/h5debug.c b/tools/misc/h5debug.c index bbeb1c2..ba7f64f 100644 --- a/tools/misc/h5debug.c +++ b/tools/misc/h5debug.c @@ -235,7 +235,7 @@ main(int argc, char *argv[]) HDexit(4); } /* end switch */ - } else if(!HDmemcmp(sig, H5B2_INT_MAGIC, H5B2_SIZEOF_MAGIC)) { + } else if(!HDmemcmp(sig, H5B2_BRCH_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 @@ -245,31 +245,78 @@ main(int argc, char *argv[]) /* Check for enough valid parameters */ if(extra == 0 || extra2 == 0) { - fprintf(stderr, "ERROR: Need v2 B-tree header address and number of records in order to dump internal node\n"); + 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 <filename> <internal node address> <v2 B-tree header address> <number of records>\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 + * 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 <filename> <internal node address> <v2 B-tree header address> <number of records>\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); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5B2_TEST, extra, (unsigned)extra2, (unsigned)1); 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); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_INDIR, extra, (unsigned)extra2, (unsigned)1); 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); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_FILT_INDIR, extra, (unsigned)extra2, (unsigned)1); 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); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_DIR, extra, (unsigned)extra2, (unsigned)1); 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); + status = H5B2_int_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5HF_BT2_FILT_DIR, extra, (unsigned)extra2, (unsigned)1); break; default: |