summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2006-08-26 07:26:07 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2006-08-26 07:26:07 (GMT)
commitf49a8d1afca48329120460f5092bcb3c37f773b0 (patch)
tree82c0d2a0656f639dded3794e4df7fdc238625488 /src
parente9889fe2d30c46af826f791eba87a8ed816b60db (diff)
downloadhdf5-f49a8d1afca48329120460f5092bcb3c37f773b0.zip
hdf5-f49a8d1afca48329120460f5092bcb3c37f773b0.tar.gz
hdf5-f49a8d1afca48329120460f5092bcb3c37f773b0.tar.bz2
[svn-r12631] Description:
Refactor the file storage of "twig" nodes in the B-tree to allow them to store more records, increasing the average density of the B-tree 30-40%. Increase # of records in "insert lots" regression test to still create B-tree of depth 4 Update h5debug to interpret difference of 'branch' and 'twig' internal nodes in B-tree correctly. Tested on: FreeBSD/32 4.11 (sleipnir) Linux/32 2.4 (heping) Linux/64 2.4 (mir) Solaris/64 2.9 (shanti)
Diffstat (limited to 'src')
-rw-r--r--src/H5B2.c39
-rw-r--r--src/H5B2cache.c86
-rw-r--r--src/H5B2dbg.c25
-rw-r--r--src/H5B2int.c248
-rw-r--r--src/H5B2pkg.h42
5 files changed, 302 insertions, 138 deletions
diff --git a/src/H5B2.c b/src/H5B2.c
index 5f2e3ca..e2fc503 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -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);