diff options
| -rw-r--r-- | src/H5B2.c | 154 | ||||
| -rw-r--r-- | src/H5B2cache.c | 67 | ||||
| -rw-r--r-- | src/H5B2hdr.c | 46 | ||||
| -rw-r--r-- | src/H5B2int.c | 160 | ||||
| -rw-r--r-- | src/H5B2pkg.h | 32 | ||||
| -rw-r--r-- | src/H5B2stat.c | 25 |
6 files changed, 359 insertions, 125 deletions
@@ -128,11 +128,11 @@ H5FL_DEFINE_STATIC(H5B2_t); H5B2_t * H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udata) { - H5B2_t *bt2 = NULL; /* Pointer to the B-tree */ - H5B2_hdr_t *hdr = NULL; /* Pointer to the B-tree header */ + H5B2_t *bt2 = NULL; /* Pointer to the B-tree */ + H5B2_hdr_t *hdr = NULL; /* Pointer to the B-tree header */ H5B2_hdr_cache_ud_t cache_udata; /* User-data for callback */ haddr_t hdr_addr; /* B-tree header address */ - H5B2_t *ret_value; /* Return value */ + H5B2_t *ret_value; /* Return value */ FUNC_ENTER_NOAPI(NULL) @@ -147,7 +147,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat /* Create shared v2 B-tree header */ if(HADDR_UNDEF == (hdr_addr = H5B2_hdr_create(f, dxpl_id, cparam, ctx_udata))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't create v2 B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't create v2 B-tree header") /* Create v2 B-tree wrapper */ if(NULL == (bt2 = H5FL_MALLOC(H5B2_t))) @@ -157,7 +157,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat cache_udata.f = f; cache_udata.ctx_udata = ctx_udata; if(NULL == (hdr = (H5B2_hdr_t *)H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, hdr_addr, &cache_udata, H5AC_WRITE))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to load B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to load B-tree header") /* Point v2 B-tree wrapper at header and bump it's ref count */ bt2->hdr = hdr; @@ -166,7 +166,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat /* Increment # of files using this v2 B-tree header */ if(H5B2_hdr_fuse_incr(bt2->hdr) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment file reference count on shared v2 B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment file reference count on shared v2 B-tree header") /* Set file pointer for this v2 B-tree open context */ bt2->f = f; @@ -299,11 +299,11 @@ H5B2_insert(H5B2_t *bt2, hid_t dxpl_id, void *udata) /* Attempt to insert record into B-tree */ if(hdr->depth > 0) { - if(H5B2_insert_internal(hdr, dxpl_id, hdr->depth, NULL, &hdr->root, udata) < 0) + if(H5B2_insert_internal(hdr, dxpl_id, hdr->depth, NULL, &hdr->root, H5B2_POS_ROOT, udata) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node") } /* end if */ else { - if(H5B2_insert_leaf(hdr, dxpl_id, &hdr->root, udata) < 0) + if(H5B2_insert_leaf(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, udata) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node") } /* end else */ @@ -420,12 +420,13 @@ htri_t H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op, void *op_data) { - H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ + H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ H5B2_node_ptr_t curr_node_ptr; /* Node pointer info for current node */ unsigned depth; /* Current depth of the tree */ int cmp; /* Comparison value of records */ unsigned idx; /* Location of record which matches key */ - htri_t ret_value = TRUE; /* Return value */ + H5B2_nodepos_t curr_pos; /* Position of the current node */ + htri_t ret_value = TRUE; /* Return value */ FUNC_ENTER_NOAPI(FAIL) @@ -441,16 +442,39 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op, /* Make copy of the root node pointer to start search with */ curr_node_ptr = hdr->root; - /* Current depth of the tree */ - depth = hdr->depth; - /* Check for empty tree */ if(curr_node_ptr.node_nrec == 0) HGOTO_DONE(FALSE) + /* Check record against min & max records in tree, to attempt to quickly + * find candidates or avoid further searching. + */ + if(hdr->min_native_rec != NULL) { + if((cmp = (hdr->cls->compare)(udata, hdr->min_native_rec)) < 0) + HGOTO_DONE(FALSE) /* Less than the least record--not found */ + else if(cmp == 0) { /* Record is found */ + if(op && (op)(hdr->min_native_rec, op_data) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation") + HGOTO_DONE(TRUE) + } /* end if */ + } /* end if */ + if(hdr->max_native_rec != NULL) { + if((cmp = (hdr->cls->compare)(udata, hdr->max_native_rec)) > 0) + HGOTO_DONE(FALSE) /* Greater than the greatest record--not found */ + else if(cmp == 0) { /* Record is found */ + if(op && (op)(hdr->max_native_rec, op_data) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation") + HGOTO_DONE(TRUE) + } /* end if */ + } /* end if */ + + /* Current depth of the tree */ + depth = hdr->depth; + /* Walk down B-tree to find record or leaf node where record is located */ cmp = -1; - while(depth > 0 && cmp != 0) { + curr_pos = H5B2_POS_ROOT; + 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 */ @@ -467,6 +491,24 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op, /* Get node pointer for next node to search */ next_node_ptr=internal->node_ptrs[idx]; + /* Set the position of the next node */ + if(H5B2_POS_MIDDLE != curr_pos) { + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) + curr_pos = H5B2_POS_LEFT; + else + curr_pos = H5B2_POS_MIDDLE; + } /* end if */ + else if(idx == internal->nrec) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) + curr_pos = H5B2_POS_RIGHT; + else + curr_pos = H5B2_POS_MIDDLE; + } /* end if */ + else + curr_pos = H5B2_POS_MIDDLE; + } /* end if */ + /* Unlock current node */ if(H5AC_unprotect(hdr->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") @@ -523,6 +565,27 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op, HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation") } /* end if */ + + /* Check for record being the min or max for the tree */ + /* (Don't use 'else' for the idx check, to allow for root leaf node) */ + if(H5B2_POS_MIDDLE != curr_pos) { + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->min_native_rec == NULL) + if(NULL == (hdr->min_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree min record info") + HDmemcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); + } /* end if */ + } /* end if */ + if(idx == (unsigned)(leaf->nrec - 1)) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->max_native_rec == NULL) + if(NULL == (hdr->max_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree max record info") + HDmemcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); + } /* end if */ + } /* end if */ + } /* end if */ } /* end else */ /* Unlock current node */ @@ -577,9 +640,6 @@ H5B2_index(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order, hsize_t idx, /* Make copy of the root node pointer to start search with */ curr_node_ptr = hdr->root; - /* Current depth of the tree */ - depth = hdr->depth; - /* Check for empty tree */ if(curr_node_ptr.node_nrec == 0) HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records") @@ -588,6 +648,9 @@ H5B2_index(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order, hsize_t idx, if(idx >= curr_node_ptr.all_nrec) HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree doesn't have that many records") + /* Current depth of the tree */ + depth = hdr->depth; + /* Check for reverse indexing and map requested index to appropriate forward index */ if(order == H5_ITER_DEC) idx = curr_node_ptr.all_nrec - (idx + 1); @@ -736,7 +799,7 @@ H5B2_remove(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_remove_t op, hbool_t depth_decreased = FALSE; /* Flag to indicate whether the depth of the B-tree decreased */ if(H5B2_remove_internal(hdr, dxpl_id, &depth_decreased, NULL, hdr->depth, - &(hdr->cache_info), NULL, &hdr->root, udata, op, op_data) < 0) + &(hdr->cache_info), NULL, H5B2_POS_ROOT, &hdr->root, udata, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node") /* Check for decreasing the depth of the B-tree */ @@ -754,7 +817,7 @@ H5B2_remove(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_remove_t op, } /* end for */ } /* end if */ else { - if(H5B2_remove_leaf(hdr, dxpl_id, &hdr->root, udata, op, op_data) < 0) + if(H5B2_remove_leaf(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, udata, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node") } /* end else */ @@ -818,7 +881,7 @@ H5B2_remove_by_idx(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order, hbool_t depth_decreased = FALSE; /* Flag to indicate whether the depth of the B-tree decreased */ if(H5B2_remove_internal_by_idx(hdr, dxpl_id, &depth_decreased, NULL, hdr->depth, - &(hdr->cache_info), NULL, &hdr->root, idx, op, op_data) < 0) + &(hdr->cache_info), NULL, &hdr->root, H5B2_POS_ROOT, idx, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node") /* Check for decreasing the depth of the B-tree */ @@ -836,7 +899,7 @@ H5B2_remove_by_idx(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order, } /* end for */ } /* end if */ else { - if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, &hdr->root, (unsigned)idx, op, op_data) < 0) + if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, (unsigned)idx, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node") } /* end else */ @@ -970,6 +1033,7 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op, { H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ H5B2_node_ptr_t curr_node_ptr; /* Node pointer info for current node */ + H5B2_nodepos_t curr_pos; /* Position of current node */ unsigned depth; /* Current depth of the tree */ int cmp; /* Comparison value of records */ unsigned idx; /* Location of record which matches key */ @@ -990,16 +1054,17 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op, /* Make copy of the root node pointer to start search with */ curr_node_ptr = hdr->root; - /* Current depth of the tree */ - depth = hdr->depth; - /* Check for empty tree */ if(0 == curr_node_ptr.node_nrec) HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records") + /* Current depth of the tree */ + depth = hdr->depth; + /* Walk down B-tree to find record or leaf node where record is located */ cmp = -1; - while(depth > 0 && cmp != 0) { + curr_pos = H5B2_POS_ROOT; + while(depth > 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 */ @@ -1017,6 +1082,24 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op, /* Get node pointer for next node to search */ next_node_ptr = internal->node_ptrs[idx]; + /* Set the position of the next node */ + if(H5B2_POS_MIDDLE != curr_pos) { + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) + curr_pos = H5B2_POS_LEFT; + else + curr_pos = H5B2_POS_MIDDLE; + } /* end if */ + else if(idx == internal->nrec) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) + curr_pos = H5B2_POS_RIGHT; + else + curr_pos = H5B2_POS_MIDDLE; + } /* end if */ + else + curr_pos = H5B2_POS_MIDDLE; + } /* end if */ + /* Unlock current node */ if(H5AC_unprotect(hdr->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") @@ -1092,6 +1175,27 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op, HGOTO_ERROR(H5E_BTREE, H5E_CANTMODIFY, FAIL, "'modify' callback failed for B-tree find operation") } /* end if */ + + /* Check for modified record being the min or max for the tree */ + /* (Don't use 'else' for the idx check, to allow for root leaf node) */ + if(H5B2_POS_MIDDLE != curr_pos) { + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->min_native_rec == NULL) + if(NULL == (hdr->min_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree min record info") + HDmemcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); + } /* end if */ + } /* end if */ + if(idx == (unsigned)(leaf->nrec - 1)) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->max_native_rec == NULL) + if(NULL == (hdr->max_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree max record info") + HDmemcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); + } /* end if */ + } /* end if */ + } /* end if */ } /* end else */ /* Mark the node as dirty if it changed */ diff --git a/src/H5B2cache.c b/src/H5B2cache.c index 1554501..1e2a6a3 100644 --- a/src/H5B2cache.c +++ b/src/H5B2cache.c @@ -15,11 +15,11 @@ /*------------------------------------------------------------------------- * - * Created: H5B2cache.c - * Jan 31 2005 - * Quincey Koziol <koziol@ncsa.uiuc.edu> + * Created: H5B2cache.c + * Jan 31 2005 + * Quincey Koziol <koziol@hdfgroup.org> * - * Purpose: Implement v2 B-tree metadata cache methods. + * Purpose: Implement v2 B-tree metadata cache methods. * *------------------------------------------------------------------------- */ @@ -174,7 +174,7 @@ H5B2__cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata) /* Allocate new B-tree header and reset cache info */ if(NULL == (hdr = H5B2_hdr_alloc(udata->f))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "allocation failed for B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "allocation failed for B-tree header") /* Wrap the local buffer for serialized header info */ if(NULL == (wb = H5WB_wrap(hdr_buf, sizeof(hdr_buf)))) @@ -186,7 +186,7 @@ H5B2__cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata) /* Read header from disk */ if(H5F_block_read(f, H5FD_MEM_BTREE, addr, hdr->hdr_size, dxpl_id, buf) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree header") /* Get temporary pointer to serialized header */ p = buf; @@ -203,7 +203,7 @@ H5B2__cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata) /* B-tree class */ id = (H5B2_subid_t)*p++; if(id >= H5B2_NUM_BTREE_ID) - HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type") + HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type") /* Node size (in bytes) */ UINT32DECODE(p, cparam.node_size); @@ -234,12 +234,12 @@ H5B2__cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata) /* Verify checksum */ if(stored_chksum != computed_chksum) - HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 B-tree header") /* Initialize B-tree header info */ cparam.cls = H5B2_client_class_g[id]; if(H5B2_hdr_init(hdr, &cparam, udata->ctx_udata, depth) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't initialize B-tree header info") + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't initialize B-tree header info") /* Set the B-tree header's address */ hdr->addr = addr; @@ -342,17 +342,17 @@ H5B2__cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, /* Metadata checksum */ UINT32ENCODE(p, metadata_chksum); - /* Write the B-tree header. */ + /* Write the B-tree header. */ HDassert((size_t)(p - buf) == hdr->hdr_size); - if(H5F_block_write(f, H5FD_MEM_BTREE, addr, hdr->hdr_size, dxpl_id, buf) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B-tree header to disk") + if(H5F_block_write(f, H5FD_MEM_BTREE, addr, hdr->hdr_size, dxpl_id, buf) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B-tree header to disk") - hdr->cache_info.is_dirty = FALSE; + hdr->cache_info.is_dirty = FALSE; } /* end if */ if(destroy) if(H5B2__cache_hdr_dest(f, hdr) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header") done: /* Release resources */ @@ -445,17 +445,17 @@ done: /*------------------------------------------------------------------------- - * Function: H5B2__cache_hdr_size + * Function: H5B2__cache_hdr_size * - * Purpose: Compute the size in bytes of a B-tree header - * on disk, and return it in *size_ptr. On failure, - * the value of *size_ptr is undefined. + * Purpose: Compute the size in bytes of a B-tree header + * on disk, and return it in *size_ptr. On failure, + * the value of *size_ptr is undefined. * - * Return: Non-negative on success/Negative on failure + * Return: SUCCEED (Can't fail) * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Feb 1 2005 + * Programmer: Quincey Koziol + * koziol@hdfgroup.org + * Feb 1 2005 * *------------------------------------------------------------------------- */ @@ -466,6 +466,7 @@ H5B2__cache_hdr_size(const H5F_t UNUSED *f, const H5B2_hdr_t *hdr, size_t *size_ /* check arguments */ HDassert(f); + HDassert(hdr); HDassert(size_ptr); /* Set size value */ @@ -519,14 +520,14 @@ H5B2__cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata) /* Increment ref. count on B-tree header */ if(H5B2_hdr_incr(udata->hdr) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment ref. count on B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment ref. count on B-tree header") /* Share B-tree information */ internal->hdr = udata->hdr; /* Read header from disk */ if(H5F_block_read(f, H5FD_MEM_BTREE, addr, udata->hdr->node_size, dxpl_id, udata->hdr->page) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree internal node") + HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree internal node") p = udata->hdr->page; @@ -541,7 +542,7 @@ H5B2__cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata) /* B-tree type */ if(*p++ != (uint8_t)udata->hdr->cls->id) - HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type") + HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type") /* Allocate space for the native keys in memory */ if(NULL == (internal->int_native = (uint8_t *)H5FL_FAC_MALLOC(udata->hdr->node_info[udata->depth].nat_rec_fac))) @@ -593,7 +594,7 @@ H5B2__cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, void *_udata) /* Verify checksum */ if(stored_chksum != computed_chksum) - HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 internal node") + HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, NULL, "incorrect metadata checksum for v2 internal node") /* Set return value */ ret_value = internal; @@ -853,7 +854,7 @@ H5B2__cache_leaf_load(H5F_t UNUSED *f, hid_t dxpl_id, haddr_t addr, void *_udata /* Allocate new leaf node and reset cache info */ if(NULL == (leaf = H5FL_MALLOC(H5B2_leaf_t))) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") + HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") HDmemset(&leaf->cache_info, 0, sizeof(H5AC_info_t)); /* Set the B-tree header's file context for this operation */ @@ -861,33 +862,33 @@ H5B2__cache_leaf_load(H5F_t UNUSED *f, hid_t dxpl_id, haddr_t addr, void *_udata /* Increment ref. count on B-tree header */ if(H5B2_hdr_incr(udata->hdr) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment ref. count on B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment ref. count on B-tree header") /* Share B-tree header information */ leaf->hdr = udata->hdr; /* Read header from disk */ if(H5F_block_read(udata->f, H5FD_MEM_BTREE, addr, udata->hdr->node_size, dxpl_id, udata->hdr->page) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree leaf node") + HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree leaf node") p = udata->hdr->page; /* Magic number */ if(HDmemcmp(p, H5B2_LEAF_MAGIC, (size_t)H5_SIZEOF_MAGIC)) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node signature") + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node signature") p += H5_SIZEOF_MAGIC; /* Version */ if(*p++ != H5B2_LEAF_VERSION) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node version") + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node version") /* B-tree type */ if(*p++ != (uint8_t)udata->hdr->cls->id) - HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type") + HGOTO_ERROR(H5E_BTREE, H5E_BADTYPE, NULL, "incorrect B-tree type") /* Allocate space for the native keys in memory */ if(NULL == (leaf->leaf_native = (uint8_t *)H5FL_FAC_MALLOC(udata->hdr->node_info[0].nat_rec_fac))) - HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree leaf native keys") + HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree leaf native keys") /* Set the number of records in the leaf */ leaf->nrec = udata->nrec; diff --git a/src/H5B2hdr.c b/src/H5B2hdr.c index 443a2e5..452a35d 100644 --- a/src/H5B2hdr.c +++ b/src/H5B2hdr.c @@ -166,7 +166,7 @@ HDmemset(hdr->page, 0, hdr->node_size); hdr->node_info[0].cum_max_nrec = hdr->node_info[0].max_nrec; hdr->node_info[0].cum_max_nrec_size = 0; if(NULL == (hdr->node_info[0].nat_rec_fac = H5FL_fac_init(hdr->cls->nrec_size * hdr->node_info[0].max_nrec))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't create node native key block factory") + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't create node native key block factory") hdr->node_info[0].node_ptr_fac = NULL; /* Allocate array of pointers to internal node native keys */ @@ -250,7 +250,7 @@ H5B2_hdr_alloc(H5F_t *f) /* Allocate space for the shared information */ if(NULL == (hdr = H5FL_CALLOC(H5B2_hdr_t))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree header") /* Assign non-zero information */ hdr->f = f; @@ -298,19 +298,19 @@ H5B2_hdr_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, /* Allocate v2 B-tree header */ if(NULL == (hdr = H5B2_hdr_alloc(f))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, HADDR_UNDEF, "allocation failed for B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, HADDR_UNDEF, "allocation failed for B-tree header") /* Initialize shared B-tree info */ if(H5B2_hdr_init(hdr, cparam, ctx_udata, (uint16_t)0) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, HADDR_UNDEF, "can't create shared B-tree info") + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, HADDR_UNDEF, "can't create shared B-tree info") /* Allocate space for the header on disk */ if(HADDR_UNDEF == (hdr->addr = H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)hdr->hdr_size))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, HADDR_UNDEF, "file allocation failed for B-tree header") + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, HADDR_UNDEF, "file allocation failed for B-tree header") /* Cache the new B-tree node */ if(H5AC_insert_entry(f, dxpl_id, H5AC_BT2_HDR, hdr->addr, hdr, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, HADDR_UNDEF, "can't add B-tree header to cache") + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, HADDR_UNDEF, "can't add B-tree header to cache") /* Set address of v2 B-tree header to return */ ret_value = hdr->addr; @@ -398,15 +398,15 @@ done: /*------------------------------------------------------------------------- - * Function: H5B2_hdr_fuse_incr + * Function: H5B2_hdr_fuse_incr * - * Purpose: Increment file reference count on shared v2 B-tree header + * Purpose: Increment file reference count on shared v2 B-tree header * - * Return: Non-negative on success/Negative on failure + * Return: SUCCEED (Can't fail) * - * Programmer: Quincey Koziol - * koziol@hdfgroup.org - * Oct 27 2009 + * Programmer: Quincey Koziol + * koziol@hdfgroup.org + * Oct 27 2009 * *------------------------------------------------------------------------- */ @@ -426,15 +426,15 @@ H5B2_hdr_fuse_incr(H5B2_hdr_t *hdr) /*------------------------------------------------------------------------- - * Function: H5B2_hdr_fuse_decr + * Function: H5B2_hdr_fuse_decr * - * Purpose: Decrement file reference count on shared v2 B-tree header + * Purpose: Decrement file reference count on shared v2 B-tree header * - * Return: Non-negative on success/Negative on failure + * Return: The file's reference count after the decrement. (Can't fail) * - * Programmer: Quincey Koziol - * koziol@hdfgroup.org - * Oct 27 2009 + * Programmer: Quincey Koziol + * koziol@hdfgroup.org + * Oct 27 2009 * *------------------------------------------------------------------------- */ @@ -542,6 +542,16 @@ H5B2_hdr_free(H5B2_hdr_t *hdr) hdr->node_info = H5FL_SEQ_FREE(H5B2_node_info_t, hdr->node_info); } /* end if */ + /* Release the min & max record info, if set */ + if(hdr->min_native_rec) { + HDfree(hdr->min_native_rec); + hdr->min_native_rec = NULL; + } /* end if */ + if(hdr->max_native_rec) { + HDfree(hdr->max_native_rec); + hdr->max_native_rec = NULL; + } /* end if */ + /* Free B-tree header info */ hdr = H5FL_FREE(H5B2_hdr_t, hdr); diff --git a/src/H5B2int.c b/src/H5B2int.c index 630ff98..ef83e93 100644 --- a/src/H5B2int.c +++ b/src/H5B2int.c @@ -172,9 +172,9 @@ H5B2_locate_record(const H5B2_class_t *type, unsigned nrec, size_t *rec_off, *------------------------------------------------------------------------- */ static herr_t -H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *curr_node_ptr, - unsigned *parent_cache_info_flags_ptr, H5B2_internal_t *internal, - unsigned *internal_flags_ptr, unsigned idx) +H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, + H5B2_node_ptr_t *curr_node_ptr, unsigned *parent_cache_info_flags_ptr, + H5B2_internal_t *internal, unsigned *internal_flags_ptr, unsigned idx) { const H5AC_class_t *child_class; /* Pointer to child node's class info */ haddr_t left_addr, right_addr; /* Addresses of left & right child nodes */ @@ -214,7 +214,7 @@ H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *cur left_addr = internal->node_ptrs[idx].addr; right_addr = internal->node_ptrs[idx + 1].addr; - /* Protect both leafs */ + /* Protect both leaves */ if(NULL == (left_int = H5B2_protect_internal(hdr, dxpl_id, left_addr, internal->node_ptrs[idx].node_nrec, (depth - 1), H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node") if(NULL == (right_int = H5B2_protect_internal(hdr, dxpl_id, right_addr, internal->node_ptrs[idx + 1].node_nrec, (depth - 1), H5AC_WRITE))) @@ -243,7 +243,7 @@ H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *cur left_addr = internal->node_ptrs[idx].addr; right_addr = internal->node_ptrs[idx + 1].addr; - /* Protect both leafs */ + /* Protect both leaves */ if(NULL == (left_leaf = H5B2_protect_leaf(hdr, dxpl_id, left_addr, internal->node_ptrs[idx].node_nrec, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node") if(NULL == (right_leaf = H5B2_protect_leaf(hdr, dxpl_id, right_addr, internal->node_ptrs[idx + 1].node_nrec, H5AC_WRITE))) @@ -341,7 +341,7 @@ done: HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node") FUNC_LEAVE_NOAPI(ret_value) -} /* end H5B2_split1 */ +} /* end H5B2_split1() */ /*------------------------------------------------------------------------- @@ -646,7 +646,7 @@ done: HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node") FUNC_LEAVE_NOAPI(ret_value) -} /* end H5B2_redistribute2 */ +} /* end H5B2_redistribute2() */ /*------------------------------------------------------------------------- @@ -1033,7 +1033,7 @@ done: HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node") FUNC_LEAVE_NOAPI(ret_value) -} /* end H5B2_redistribute3 */ +} /* end H5B2_redistribute3() */ /*------------------------------------------------------------------------- @@ -1505,7 +1505,7 @@ done: HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node") FUNC_LEAVE_NOAPI(ret_value) -} /* end H5B2_swap_leaf */ +} /* end H5B2_swap_leaf() */ /*------------------------------------------------------------------------- @@ -1523,7 +1523,7 @@ done: */ herr_t H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr, - void *udata) + H5B2_nodepos_t curr_pos, void *udata) { H5B2_leaf_t *leaf; /* Pointer to leaf node */ int cmp; /* Comparison value of records */ @@ -1574,6 +1574,27 @@ H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr, /* Update record count for current node */ leaf->nrec++; + /* Check for new record being the min or max for the tree */ + /* (Don't use 'else' for the idx check, to allow for root leaf node) */ + if(H5B2_POS_MIDDLE != curr_pos) { + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->min_native_rec == NULL) + if(NULL == (hdr->min_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree min record info") + HDmemcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); + } /* end if */ + } /* end if */ + if(idx == (unsigned)(leaf->nrec - 1)) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->max_native_rec == NULL) + if(NULL == (hdr->max_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree max record info") + HDmemcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); + } /* end if */ + } /* end if */ + } /* end if */ + done: /* Release the B-tree leaf node (marked as dirty) */ if(leaf && H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr->addr, leaf, H5AC__DIRTIED_FLAG) < 0) @@ -1599,11 +1620,12 @@ done: herr_t H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, unsigned *parent_cache_info_flags_ptr, H5B2_node_ptr_t *curr_node_ptr, - void *udata) + H5B2_nodepos_t curr_pos, void *udata) { - H5B2_internal_t *internal; /* Pointer to internal node */ + H5B2_internal_t *internal = NULL; /* Pointer to internal node */ unsigned internal_flags = H5AC__NO_FLAGS_SET; unsigned idx; /* Location of record which matches key */ + H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE; /* Position of node */ herr_t ret_value = SUCCEED; /* Return value */ FUNC_ENTER_NOAPI_NOINIT @@ -1618,7 +1640,7 @@ H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, if(NULL == (internal = H5B2_protect_internal(hdr, dxpl_id, curr_node_ptr->addr, curr_node_ptr->node_nrec, depth, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node") -/* Split or redistribute child node pointers, if necessary */ + /* Split or redistribute child node pointers, if necessary */ { int cmp; /* Comparison value of records */ unsigned retries; /* Number of times to attempt redistribution */ @@ -1691,13 +1713,25 @@ H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, } /* end while */ } /* end block */ + /* Check if this node is left/right-most */ + if(H5B2_POS_MIDDLE != curr_pos) { + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) + next_pos = H5B2_POS_LEFT; + } /* end if */ + else if(idx == internal->nrec) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) + next_pos = H5B2_POS_RIGHT; + } /* end else */ + } /* end if */ + /* Attempt to insert node */ if(depth > 1) { - if(H5B2_insert_internal(hdr, dxpl_id, (depth - 1), &internal_flags, &internal->node_ptrs[idx], udata) < 0) + if(H5B2_insert_internal(hdr, dxpl_id, (depth - 1), &internal_flags, &internal->node_ptrs[idx], next_pos, udata) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node") } /* end if */ else { - if(H5B2_insert_leaf(hdr, dxpl_id, &internal->node_ptrs[idx], udata) < 0) + if(H5B2_insert_leaf(hdr, dxpl_id, &internal->node_ptrs[idx], next_pos, udata) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node") } /* end else */ @@ -2074,7 +2108,7 @@ done: */ herr_t H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr, - void *udata, H5B2_remove_t op, void *op_data) + H5B2_nodepos_t curr_pos, void *udata, H5B2_remove_t op, void *op_data) { H5B2_leaf_t *leaf; /* Pointer to leaf node */ haddr_t leaf_addr = HADDR_UNDEF; /* Leaf address on disk */ @@ -2102,6 +2136,27 @@ H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr, if(H5B2_locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx) != 0) HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree") + /* Check for invalidating the min/max record for the tree */ + if(H5B2_POS_MIDDLE != curr_pos) { + /* (Don't use 'else' for the idx check, to allow for root leaf node) */ + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->min_native_rec) { + HDfree(hdr->min_native_rec); + hdr->min_native_rec = NULL; + } /* end if */ + } /* end if */ + } /* end if */ + if(idx == (unsigned)(leaf->nrec - 1)) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->max_native_rec) { + HDfree(hdr->max_native_rec); + hdr->max_native_rec = NULL; + } /* end if */ + } /* end if */ + } /* end if */ + } /* end if */ + /* Make 'remove' callback if there is one */ if(op) if((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data) < 0) @@ -2154,13 +2209,14 @@ done: herr_t H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info, - unsigned *parent_cache_info_flags_ptr, H5B2_node_ptr_t *curr_node_ptr, - void *udata, H5B2_remove_t op, void *op_data) + unsigned *parent_cache_info_flags_ptr, H5B2_nodepos_t curr_pos, + H5B2_node_ptr_t *curr_node_ptr, void *udata, H5B2_remove_t op, void *op_data) { H5AC_info_t *new_cache_info; /* Pointer to new cache info */ unsigned *new_cache_info_flags_ptr = NULL; H5B2_node_ptr_t *new_node_ptr; /* Pointer to new node pointer */ H5B2_internal_t *internal; /* Pointer to internal node */ + H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE; /* Position of next node */ unsigned internal_flags = H5AC__NO_FLAGS_SET; haddr_t internal_addr; /* Address of internal node */ size_t merge_nrec; /* Number of records to merge node at */ @@ -2211,6 +2267,9 @@ H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased, /* Set flag to indicate root was collapsed */ collapsed_root = TRUE; + + /* Indicate position of next node */ + next_pos = H5B2_POS_ROOT; } /* end if */ /* Merge or redistribute child node pointers, if necessary */ else { @@ -2306,16 +2365,28 @@ H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased, new_cache_info_flags_ptr = &internal_flags; new_cache_info = &internal->cache_info; new_node_ptr = &internal->node_ptrs[idx]; + + /* Indicate position of next node */ + if(H5B2_POS_MIDDLE != curr_pos) { + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) + next_pos = H5B2_POS_LEFT; + } /* end if */ + else if(idx == internal->nrec) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) + next_pos = H5B2_POS_RIGHT; + } /* end if */ + } /* end if */ } /* end else */ /* Attempt to remove record from child node */ if(depth > 1) { if(H5B2_remove_internal(hdr, dxpl_id, depth_decreased, swap_loc, depth - 1, - new_cache_info, new_cache_info_flags_ptr, new_node_ptr, udata, op, op_data) < 0) + new_cache_info, new_cache_info_flags_ptr, next_pos, new_node_ptr, udata, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node") } /* end if */ else { - if(H5B2_remove_leaf(hdr, dxpl_id, new_node_ptr, udata, op, op_data) < 0) + if(H5B2_remove_leaf(hdr, dxpl_id, new_node_ptr, next_pos, udata, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node") } /* end else */ @@ -2355,8 +2426,8 @@ done: */ herr_t H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id, - H5B2_node_ptr_t *curr_node_ptr, unsigned idx, H5B2_remove_t op, - void *op_data) + H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, + unsigned idx, H5B2_remove_t op, void *op_data) { H5B2_leaf_t *leaf; /* Pointer to leaf node */ haddr_t leaf_addr = HADDR_UNDEF; /* Leaf address on disk */ @@ -2380,6 +2451,27 @@ H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id, HDassert(leaf->nrec == curr_node_ptr->node_nrec); HDassert(idx < leaf->nrec); + /* Check for invalidating the min/max record for the tree */ + if(H5B2_POS_MIDDLE != curr_pos) { + /* (Don't use 'else' for the idx check, to allow for root leaf node) */ + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->min_native_rec) { + HDfree(hdr->min_native_rec); + hdr->min_native_rec = NULL; + } /* end if */ + } /* end if */ + } /* end if */ + if(idx == (unsigned)(leaf->nrec - 1)) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) { + if(hdr->max_native_rec) { + HDfree(hdr->max_native_rec); + hdr->max_native_rec = NULL; + } /* end if */ + } /* end if */ + } /* end if */ + } /* end if */ + /* Make 'remove' callback if there is one */ if(op) if((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data) < 0) @@ -2434,13 +2526,14 @@ herr_t H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info, unsigned *parent_cache_info_flags_ptr, - H5B2_node_ptr_t *curr_node_ptr, hsize_t n, H5B2_remove_t op, - void *op_data) + H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, hsize_t n, + H5B2_remove_t op, void *op_data) { H5AC_info_t *new_cache_info; /* Pointer to new cache info */ unsigned *new_cache_info_flags_ptr = NULL; H5B2_node_ptr_t *new_node_ptr; /* Pointer to new node pointer */ H5B2_internal_t *internal; /* Pointer to internal node */ + H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE; /* Position of next node */ unsigned internal_flags = H5AC__NO_FLAGS_SET; haddr_t internal_addr; /* Address of internal node */ size_t merge_nrec; /* Number of records to merge node at */ @@ -2494,6 +2587,9 @@ H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id, /* Set flag to indicate root was collapsed */ collapsed_root = TRUE; + + /* Indicate position of next node */ + next_pos = H5B2_POS_ROOT; } /* end if */ /* Merge or redistribute child node pointers, if necessary */ else { @@ -2641,16 +2737,28 @@ H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id, new_cache_info_flags_ptr = &internal_flags; new_cache_info = &internal->cache_info; new_node_ptr = &internal->node_ptrs[idx]; + + /* Indicate position of next node */ + if(H5B2_POS_MIDDLE != curr_pos) { + if(idx == 0) { + if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) + next_pos = H5B2_POS_LEFT; + } /* end if */ + else if(idx == internal->nrec) { + if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) + next_pos = H5B2_POS_RIGHT; + } /* end if */ + } /* end if */ } /* end else */ /* Attempt to remove record from child node */ if(depth > 1) { if(H5B2_remove_internal_by_idx(hdr, dxpl_id, depth_decreased, swap_loc, depth - 1, - new_cache_info, new_cache_info_flags_ptr, new_node_ptr, n, op, op_data) < 0) + new_cache_info, new_cache_info_flags_ptr, new_node_ptr, next_pos, n, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node") } /* end if */ else { - if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, new_node_ptr, (unsigned)n, op, op_data) < 0) + if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, new_node_ptr, next_pos, (unsigned)n, op, op_data) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node") } /* end else */ diff --git a/src/H5B2pkg.h b/src/H5B2pkg.h index b820853..7a538bd 100644 --- a/src/H5B2pkg.h +++ b/src/H5B2pkg.h @@ -172,6 +172,8 @@ typedef struct H5B2_hdr_t { uint8_t *page; /* Common disk page for I/O */ size_t *nat_off; /* Array of offsets of native records */ H5B2_node_info_t *node_info; /* Table of node info structs for current depth of B-tree */ + uint8_t *min_native_rec; /* Pointer to minimum native record */ + uint8_t *max_native_rec; /* Pointer to maximum native record */ /* Client information (not stored) */ const H5B2_class_t *cls; /* Class of B-tree client */ @@ -208,6 +210,14 @@ struct H5B2_t { H5F_t *f; /* Pointer to file for v2 B-tree */ }; +/* Node position, for min/max determination */ +typedef enum H5B2_nodepos_t { + H5B2_POS_ROOT, /* Node is root (i.e. both right & left-most in tree) */ + H5B2_POS_RIGHT, /* Node is right-most in tree, at a given depth */ + H5B2_POS_LEFT, /* Node is left-most in tree, at a given depth */ + H5B2_POS_MIDDLE /* Node is neither right or left-most in tree */ +} H5B2_nodepos_t; + /* Callback info for loading a free space header into the cache */ typedef struct H5B2_hdr_cache_ud_t { H5F_t *f; /* File that v2 b-tree header is within */ @@ -304,9 +314,9 @@ H5_DLL herr_t H5B2_internal_free(H5B2_internal_t *i); /* Routines for inserting records */ H5_DLL herr_t H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, unsigned *parent_cache_info_flags_ptr, - H5B2_node_ptr_t *curr_node_ptr, void *udata); + H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, void *udata); H5_DLL herr_t H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, - H5B2_node_ptr_t *curr_node_ptr, void *udata); + H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, void *udata); /* Routines for iterating over nodes/records */ H5_DLL herr_t H5B2_iterate_node(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, @@ -326,19 +336,21 @@ H5_DLL herr_t H5B2_neighbor_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, /* Routines for removing records */ H5_DLL herr_t H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, - hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info, - hbool_t * parent_cache_info_dirtied_ptr, H5B2_node_ptr_t *curr_node_ptr, void *udata, + hbool_t *depth_decreased, void *swap_loc, unsigned depth, + H5AC_info_t *parent_cache_info, hbool_t * parent_cache_info_dirtied_ptr, + H5B2_nodepos_t curr_pos, H5B2_node_ptr_t *curr_node_ptr, void *udata, H5B2_remove_t op, void *op_data); H5_DLL herr_t H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, - H5B2_node_ptr_t *curr_node_ptr, void *udata, H5B2_remove_t op, - void *op_data); + H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, + void *udata, H5B2_remove_t op, void *op_data); H5_DLL herr_t H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id, - hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info, - hbool_t * parent_cache_info_dirtied_ptr, H5B2_node_ptr_t *curr_node_ptr, hsize_t idx, + hbool_t *depth_decreased, void *swap_loc, unsigned depth, + H5AC_info_t *parent_cache_info, hbool_t * parent_cache_info_dirtied_ptr, + H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, hsize_t idx, H5B2_remove_t op, void *op_data); H5_DLL herr_t H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id, - H5B2_node_ptr_t *curr_node_ptr, unsigned idx, H5B2_remove_t op, - void *op_data); + H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, + unsigned idx, H5B2_remove_t op, void *op_data); /* Routines for deleting nodes */ H5_DLL herr_t H5B2_delete_node(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, diff --git a/src/H5B2stat.c b/src/H5B2stat.c index 5e48a6f..5d159ed 100644 --- a/src/H5B2stat.c +++ b/src/H5B2stat.c @@ -13,10 +13,10 @@ * access to either file, you may request a copy from help@hdfgroup.org. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ -/* Programmer: Quincey Koziol <koziol@ncsa.uiuc.edu> +/* Programmer: Quincey Koziol <koziol@hdfgroup.org> * Monday, March 6, 2006 * - * Purpose: v2 B-tree metadata statistics functions. + * Purpose: v2 B-tree metadata statistics functions. * */ @@ -24,15 +24,15 @@ /* Module Setup */ /****************/ -#define H5B2_PACKAGE /*suppress error about including H5B2pkg */ +#define H5B2_PACKAGE /* Suppress error about including H5B2pkg */ /***********/ /* Headers */ /***********/ -#include "H5private.h" /* Generic Functions */ -#include "H5B2pkg.h" /* v2 B-trees */ -#include "H5Eprivate.h" /* Error handling */ +#include "H5private.h" /* Generic Functions */ +#include "H5B2pkg.h" /* v2 B-trees */ +#include "H5Eprivate.h" /* Error handling */ /****************/ @@ -71,14 +71,13 @@ /*------------------------------------------------------------------------- - * Function: H5B2_stat_info + * Function: H5B2_stat_info * - * Purpose: Retrieve metadata statistics for a v2 B-tree + * Purpose: Retrieve metadata statistics for a v2 B-tree * - * Return: Success: non-negative - * Failure: negative + * Return: SUCCEED (Can't fail) * - * Programmer: Quincey Koziol + * Programmer: Quincey Koziol * Monday, March 6, 2006 * *------------------------------------------------------------------------- @@ -105,7 +104,7 @@ H5B2_stat_info(H5B2_t *bt2, H5B2_stat_t *info) * Purpose: Iterate over all the records in the B-tree, collecting * storage info. * - * Return: non-negative on success, negative on error + * Return: SUCCEED/FAIL * * Programmer: Vailin Choi * June 19 2007 @@ -115,7 +114,7 @@ H5B2_stat_info(H5B2_t *bt2, H5B2_stat_t *info) herr_t H5B2_size(H5B2_t *bt2, hid_t dxpl_id, hsize_t *btree_size) { - H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ + H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ herr_t ret_value = SUCCEED; /* Return value */ FUNC_ENTER_NOAPI(FAIL) |