summaryrefslogtreecommitdiffstats
path: root/src/H5B2int.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/H5B2int.c')
-rw-r--r--src/H5B2int.c160
1 files changed, 134 insertions, 26 deletions
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 */
generated by cgit v0.12 at 2024-11-01 14:32:20 (GMT)