summaryrefslogtreecommitdiffstats
path: root/src/H5B2.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/H5B2.c')
-rw-r--r--src/H5B2.c154
1 files changed, 129 insertions, 25 deletions
diff --git a/src/H5B2.c b/src/H5B2.c
index a2b218d..7d7345e 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -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 */
generated by cgit v0.12 at 2024-10-30 04:42:07 (GMT)