summaryrefslogtreecommitdiffstats
path: root/src/H5B2int.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/H5B2int.c')
-rw-r--r--src/H5B2int.c520
1 files changed, 466 insertions, 54 deletions
diff --git a/src/H5B2int.c b/src/H5B2int.c
index b8c9634..8bdde3e 100644
--- a/src/H5B2int.c
+++ b/src/H5B2int.c
@@ -38,7 +38,8 @@
#include "H5B2pkg.h" /* v2 B-trees */
#include "H5Eprivate.h" /* Error handling */
#include "H5MFprivate.h" /* File memory management */
-#include "H5VMprivate.h" /* Vectors and arrays */
+#include "H5MMprivate.h" /* Memory management */
+#include "H5VMprivate.h" /* Vectors and arrays */
/****************/
/* Local Macros */
@@ -133,28 +134,33 @@ H5FL_SEQ_EXTERN(H5B2_node_info_t);
*
*-------------------------------------------------------------------------
*/
-int
+herr_t
H5B2__locate_record(const H5B2_class_t *type, unsigned nrec, size_t *rec_off,
- const uint8_t *native, const void *udata, unsigned *idx)
+ const uint8_t *native, const void *udata, unsigned *idx, int *cmp)
{
unsigned lo = 0, hi; /* Low & high index values */
unsigned my_idx = 0; /* Final index value */
- int cmp = -1; /* Key comparison value */
+ herr_t ret_value = SUCCEED;
+
+ FUNC_ENTER_PACKAGE
- FUNC_ENTER_PACKAGE_NOERR
+ *cmp = -1;
hi = nrec;
- while(lo < hi && cmp) {
- my_idx = (lo + hi) / 2;
- if((cmp = (type->compare)(udata, native + rec_off[my_idx])) < 0)
- hi = my_idx;
- else
- lo = my_idx + 1;
- }
+ while(lo < hi && *cmp) {
+ my_idx = (lo + hi) / 2;
+ if((type->compare)(udata, native + rec_off[my_idx], cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
+ if(*cmp < 0)
+ hi = my_idx;
+ else
+ lo = my_idx + 1;
+ } /* end while */
*idx = my_idx;
- FUNC_LEAVE_NOAPI(cmp)
+done:
+ FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B2__locate_record */
@@ -1513,6 +1519,62 @@ done:
/*-------------------------------------------------------------------------
+ * Function: H5B2__insert_hdr
+ *
+ * Purpose: Adds a new record to the B-tree.
+ *
+ * Return: Non-negative on success/Negative on failure
+ *
+ * Programmer: Quincey Koziol
+ * koziol@hdfgroup.org
+ * Dec 23 2015
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2__insert_hdr(H5B2_hdr_t *hdr, hid_t dxpl_id, void *udata)
+{
+ herr_t ret_value = SUCCEED; /* Return value */
+
+ FUNC_ENTER_PACKAGE
+
+ /* Check arguments. */
+ HDassert(hdr);
+ HDassert(udata);
+
+ /* Check if the root node is allocated yet */
+ if(!H5F_addr_defined(hdr->root.addr)) {
+ /* Create root node as leaf node in B-tree */
+ if(H5B2__create_leaf(hdr, dxpl_id, &(hdr->root)) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create root node")
+ } /* end if */
+ /* Check if we need to split the root node (equiv. to a 1->2 node split) */
+ else if(hdr->root.node_nrec == hdr->node_info[hdr->depth].split_nrec) {
+ /* Split root node */
+ if(H5B2__split_root(hdr, dxpl_id) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node")
+ } /* end if */
+
+ /* Attempt to insert record into B-tree */
+ if(hdr->depth > 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, H5B2_POS_ROOT, udata) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node")
+ } /* end else */
+
+ /* Mark B-tree header as dirty */
+ if(H5B2__hdr_dirty(hdr) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTMARKDIRTY, FAIL, "unable to mark B-tree header dirty")
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2__insert_hdr() */
+
+
+/*-------------------------------------------------------------------------
* Function: H5B2__insert_leaf
*
* Purpose: Adds a new record to a B-tree leaf node.
@@ -1557,7 +1619,9 @@ H5B2__insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr
idx = 0;
else {
/* Find correct location to insert this record */
- if((cmp = H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx)) == 0)
+ if(H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
+ if(cmp == 0)
HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
if(cmp > 0)
idx++;
@@ -1584,7 +1648,7 @@ H5B2__insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr
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)))
+ if(NULL == (hdr->min_native_rec = H5MM_malloc(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 */
@@ -1592,7 +1656,7 @@ H5B2__insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr
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)))
+ if(NULL == (hdr->max_native_rec = H5MM_malloc(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 */
@@ -1644,6 +1708,9 @@ H5B2__insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, uint16_t depth,
if(NULL == (internal = H5B2__protect_internal(hdr, dxpl_id, curr_node_ptr->addr, curr_node_ptr->node_nrec, depth, H5AC__NO_FLAGS_SET)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node")
+ /* Sanity check number of records */
+ HDassert(internal->nrec == curr_node_ptr->node_nrec);
+
/* Split or redistribute child node pointers, if necessary */
{
int cmp; /* Comparison value of records */
@@ -1651,7 +1718,10 @@ H5B2__insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, uint16_t depth,
size_t split_nrec; /* Number of records to split node at */
/* Locate node pointer for child */
- if((cmp = H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx)) == 0)
+ if(H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native,
+ udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
+ if(cmp == 0)
HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
if(cmp > 0)
idx++;
@@ -1706,8 +1776,11 @@ H5B2__insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, uint16_t depth,
} /* end else */
/* Locate node pointer for child (after split/redistribute) */
-/* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */
- if((cmp = H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx)) == 0)
+ /* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */
+ if(H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native,
+ udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
+ if(cmp == 0)
HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
if(cmp > 0)
idx++;
@@ -1755,6 +1828,350 @@ done:
/*-------------------------------------------------------------------------
+ * Function: H5B2__update_leaf
+ *
+ * Purpose: Insert or modify a record in a B-tree leaf node.
+ * If the record exists already, it is modified as if H5B2_modify
+ * was called). If it doesn't exist, it is inserted as if
+ * H5B2_insert was called.
+ *
+ * Return: Non-negative on success/Negative on failure
+ *
+ * Programmer: Quincey Koziol
+ * koziol@hdfgroup.org
+ * Dec 23 2015
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2__update_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
+ H5B2_update_status_t *status, H5B2_nodepos_t curr_pos, void *udata,
+ H5B2_modify_t op, void *op_data)
+{
+ H5B2_leaf_t *leaf; /* Pointer to leaf node */
+ unsigned leaf_flags = H5AC__NO_FLAGS_SET; /* Flags for unprotecting the leaf node */
+ int cmp = -1; /* Comparison value of records */
+ unsigned idx; /* Location of record which matches key */
+ herr_t ret_value = SUCCEED; /* Return value */
+
+ FUNC_ENTER_PACKAGE
+
+ /* Check arguments. */
+ HDassert(hdr);
+ HDassert(curr_node_ptr);
+ HDassert(H5F_addr_defined(curr_node_ptr->addr));
+
+ /* Lock current B-tree node */
+ if(NULL == (leaf = H5B2__protect_leaf(hdr, dxpl_id, curr_node_ptr->addr, curr_node_ptr->node_nrec, H5AC__NO_FLAGS_SET)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node")
+
+ /* Sanity check number of records */
+ HDassert(curr_node_ptr->all_nrec == curr_node_ptr->node_nrec);
+ HDassert(leaf->nrec == curr_node_ptr->node_nrec);
+
+ /* Check for inserting into empty leaf */
+ if(leaf->nrec == 0)
+ idx = 0;
+ else {
+ /* Find correct location to insert this record */
+ if(H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
+
+ /* Check for inserting a record */
+ if(0 != cmp) {
+ /* Check if the leaf node is full */
+ if(curr_node_ptr->node_nrec == hdr->node_info[0].split_nrec) {
+ /* Indicate that the leaf is full, but we need to insert */
+ *status = H5B2_UPDATE_INSERT_CHILD_FULL;
+
+ /* Let calling routine handle insertion */
+ HGOTO_DONE(SUCCEED)
+ } /* end if */
+
+ /* Adjust index to leave room for record to insert */
+ if(cmp > 0)
+ idx++;
+
+ /* Make room for new record */
+ if(idx < leaf->nrec)
+ HDmemmove(H5B2_LEAF_NREC(leaf, hdr, idx + 1), H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size * (leaf->nrec - idx));
+ } /* end if */
+ } /* end else */
+
+ /* Check for modifying existing record */
+ if(0 == cmp) {
+ hbool_t changed = FALSE; /* Whether the 'modify' callback changed the record */
+
+ /* Make callback for current record */
+ if((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data, &changed) < 0) {
+ /* Make certain that the callback didn't modify the value if it failed */
+ HDassert(changed == FALSE);
+
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTMODIFY, FAIL, "'modify' callback failed for B-tree update operation")
+ } /* end if */
+
+ /* Mark the node as dirty if it changed */
+ leaf_flags |= (changed ? H5AC__DIRTIED_FLAG : 0);
+
+ /* Indicate that the record was modified */
+ *status = H5B2_UPDATE_MODIFY_DONE;
+ } /* end if */
+ else {
+ /* Must have a leaf node with enough space to insert a record now */
+ HDassert(curr_node_ptr->node_nrec < hdr->node_info[0].max_nrec);
+
+ /* Make callback to store record in native form */
+ if((hdr->cls->store)(H5B2_LEAF_NREC(leaf, hdr, idx), udata) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node")
+
+ /* Mark the node as dirty if it changed */
+ leaf_flags |= H5AC__DIRTIED_FLAG;
+
+ /* Indicate that the record was inserted */
+ *status = H5B2_UPDATE_INSERT_DONE;
+
+ /* Update record count for node pointer to current node */
+ curr_node_ptr->all_nrec++;
+ curr_node_ptr->node_nrec++;
+
+ /* Update record count for current node */
+ leaf->nrec++;
+ } /* end else */
+
+ /* 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 = H5MM_malloc(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 = H5MM_malloc(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 */
+ if(leaf && H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr->addr, leaf, leaf_flags) < 0)
+ HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release leaf B-tree node")
+
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2__update_leaf() */
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B2__update_internal
+ *
+ * Purpose: Insert or modify a record in a B-tree leaf node.
+ * If the record exists already, it is modified as if H5B2_modify
+ * was called). If it doesn't exist, it is inserted as if
+ * H5B2_insert was called.
+ *
+ * Return: Non-negative on success/Negative on failure
+ *
+ * Programmer: Quincey Koziol
+ * koziol@hdfgroup.org
+ * Dec 24 2015
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2__update_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, uint16_t depth,
+ unsigned *parent_cache_info_flags_ptr, H5B2_node_ptr_t *curr_node_ptr,
+ H5B2_update_status_t *status, H5B2_nodepos_t curr_pos, void *udata,
+ H5B2_modify_t op, void *op_data)
+{
+ H5B2_internal_t *internal = NULL; /* Pointer to internal node */
+ unsigned internal_flags = H5AC__NO_FLAGS_SET;
+ int cmp; /* Comparison value of records */
+ 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_PACKAGE
+
+ /* Check arguments. */
+ HDassert(hdr);
+ HDassert(depth > 0);
+ HDassert(curr_node_ptr);
+ HDassert(H5F_addr_defined(curr_node_ptr->addr));
+
+ /* Lock current B-tree node */
+ if(NULL == (internal = H5B2__protect_internal(hdr, dxpl_id, curr_node_ptr->addr, curr_node_ptr->node_nrec, depth, H5AC__NO_FLAGS_SET)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node")
+
+ /* Sanity check number of records */
+ HDassert(internal->nrec == curr_node_ptr->node_nrec);
+
+ /* Locate node pointer for child */
+ if(H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
+
+ /* Check for modifying existing record */
+ if(0 == cmp) {
+ hbool_t changed = FALSE; /* Whether the 'modify' callback changed the record */
+
+ /* Make callback for current record */
+ if((op)(H5B2_INT_NREC(internal, hdr, idx), op_data, &changed) < 0) {
+ /* Make certain that the callback didn't modify the value if it failed */
+ HDassert(changed == FALSE);
+
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTMODIFY, FAIL, "'modify' callback failed for B-tree update operation")
+ } /* end if */
+
+ /* Mark the node as dirty if it changed */
+ internal_flags |= (changed ? H5AC__DIRTIED_FLAG : 0);
+
+ /* Indicate that the record was modified */
+ *status = H5B2_UPDATE_MODIFY_DONE;
+ } /* end if */
+ else {
+ /* Adjust index to leave room for node to insert */
+ if(cmp > 0)
+ idx++;
+
+ /* 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 update record in child */
+ if(depth > 1) {
+ if(H5B2__update_internal(hdr, dxpl_id, (uint16_t)(depth - 1), &internal_flags, &internal->node_ptrs[idx], status, next_pos, udata, op, op_data) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL, "unable to update record in internal B-tree node")
+ } /* end if */
+ else {
+ if(H5B2__update_leaf(hdr, dxpl_id, &internal->node_ptrs[idx], status, next_pos, udata, op, op_data) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL, "unable to update record in leaf B-tree node")
+ } /* end else */
+
+ /* Take actions based on child's status report */
+ switch(*status) {
+ case H5B2_UPDATE_MODIFY_DONE:
+ /* No action */
+ break;
+
+ case H5B2_UPDATE_INSERT_DONE:
+ /* Mark node as dirty */
+ internal_flags |= H5AC__DIRTIED_FLAG;
+
+ /* Update total record count for node pointer to current node */
+ curr_node_ptr->all_nrec++;
+ break;
+
+ case H5B2_UPDATE_INSERT_CHILD_FULL:
+ /* Split/redistribute this node */
+ if(internal->nrec == hdr->node_info[depth].split_nrec) {
+ hbool_t could_split = FALSE; /* Whether the child node could split */
+
+#ifdef QAK
+HDfprintf(stderr, "%s: idx = %u, internal->nrec = %u\n", FUNC, idx, internal->nrec);
+HDfprintf(stderr, "%s: hdr->node_info[%u].split_nrec = %u\n", FUNC, (unsigned)depth, (unsigned)hdr->node_info[depth].split_nrec);
+HDfprintf(stderr, "%s: hdr->node_info[%u].split_nrec = %u\n", FUNC, (unsigned)(depth - 1), (unsigned)hdr->node_info[depth - 1].split_nrec);
+#endif /* QAK */
+ if(idx == 0) { /* Left-most child */
+#ifdef QAK
+HDfprintf(stderr, "%s: Left-most child\n", FUNC);
+HDfprintf(stderr, "%s: internal->node_ptrs[%u].node_nrec = %u\n", FUNC, (unsigned)idx, (unsigned)internal->node_ptrs[idx].node_nrec);
+HDfprintf(stderr, "%s: internal->node_ptrs[%u].node_nrec = %u\n", FUNC, (unsigned)(idx + 1), (unsigned)internal->node_ptrs[idx + 1].node_nrec);
+#endif /* QAK */
+ /* Check for left-most child and its neighbor being close to full */
+ if((internal->node_ptrs[idx].node_nrec + internal->node_ptrs[idx + 1].node_nrec)
+ >= ((hdr->node_info[depth - 1].split_nrec * 2) - 1))
+ could_split = TRUE;
+ } /* end if */
+ else if(idx == internal->nrec) { /* Right-most child */
+#ifdef QAK
+HDfprintf(stderr, "%s: Right-most child\n", FUNC);
+HDfprintf(stderr, "%s: internal->node_ptrs[%u].node_nrec = %u\n", FUNC, (unsigned)(idx - 1), (unsigned)internal->node_ptrs[idx - 1].node_nrec);
+HDfprintf(stderr, "%s: internal->node_ptrs[%u].node_nrec = %u\n", FUNC, (unsigned)idx, (unsigned)internal->node_ptrs[idx].node_nrec);
+#endif /* QAK */
+ /* Check for right-most child and its neighbor being close to full */
+ if((internal->node_ptrs[idx - 1].node_nrec + internal->node_ptrs[idx].node_nrec)
+ >= ((hdr->node_info[depth - 1].split_nrec * 2) - 1))
+ could_split = TRUE;
+ } /* end else-if */
+ else { /* Middle child */
+#ifdef QAK
+HDfprintf(stderr, "%s: Middle child\n", FUNC);
+HDfprintf(stderr, "%s: internal->node_ptrs[%u].node_nrec = %u\n", FUNC, (unsigned)(idx - 1), (unsigned)internal->node_ptrs[idx - 1].node_nrec);
+HDfprintf(stderr, "%s: internal->node_ptrs[%u].node_nrec = %u\n", FUNC, (unsigned)idx, (unsigned)internal->node_ptrs[idx].node_nrec);
+HDfprintf(stderr, "%s: internal->node_ptrs[%u].node_nrec = %u\n", FUNC, (unsigned)(idx + 1), (unsigned)internal->node_ptrs[idx + 1].node_nrec);
+#endif /* QAK */
+ /* Check for middle child and its left neighbor being close to full */
+ if((internal->node_ptrs[idx - 1].node_nrec + internal->node_ptrs[idx].node_nrec)
+ >= ((hdr->node_info[depth - 1].split_nrec * 2) - 1))
+ could_split = TRUE;
+ /* Check for middle child and its right neighbor being close to full */
+ else if((internal->node_ptrs[idx].node_nrec + internal->node_ptrs[idx + 1].node_nrec)
+ >= ((hdr->node_info[depth - 1].split_nrec * 2) - 1))
+ could_split = TRUE;
+ } /* end if */
+
+ /* If this node is full and the child node insertion could
+ * cause a split, punt back up to caller, leaving the
+ * "insert child full" status.
+ */
+ if(could_split) {
+ /* Release the internal B-tree node */
+ if(H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, internal, internal_flags) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release internal B-tree node")
+ internal = NULL;
+
+#ifdef QAK
+HDfprintf(stderr, "%s: Punting back to caller\n", FUNC);
+#endif /* QAK */
+ /* Punt back to caller */
+ HGOTO_DONE(SUCCEED);
+ } /* end if */
+ } /* end if */
+
+ /* Release the internal B-tree node */
+ if(H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, internal, internal_flags) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release internal B-tree node")
+ internal = NULL;
+
+ /* Indicate that the record was inserted */
+ *status = H5B2_UPDATE_INSERT_DONE;
+
+ /* Dodge sideways into inserting a record into this node */
+ if(H5B2__insert_internal(hdr, dxpl_id, depth, parent_cache_info_flags_ptr, curr_node_ptr, curr_pos, udata) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into internal B-tree node")
+ break;
+
+ case H5B2_UPDATE_UNKNOWN:
+ default:
+ HDassert(0 && "Invalid update status");
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL, "invalid update status")
+ } /* end switch */
+ } /* end else */
+
+done:
+ /* Release the internal B-tree node */
+ if(internal && H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, internal, internal_flags) < 0)
+ HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release internal B-tree node")
+
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2__update_internal() */
+
+
+/*-------------------------------------------------------------------------
* Function: H5B2__create_leaf
*
* Purpose: Creates empty leaf node of a B-tree and update node pointer
@@ -1789,32 +2206,30 @@ H5B2__create_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *node_ptr)
/* Increment ref. count on B-tree header */
if(H5B2__hdr_incr(hdr) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, FAIL, "can't increment ref. count on B-tree header")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, FAIL, "can't increment ref. count on B-tree header")
/* Share B-tree header information */
leaf->hdr = hdr;
/* Allocate space for the native keys in memory */
if(NULL == (leaf->leaf_native = (uint8_t *)H5FL_FAC_MALLOC(hdr->node_info[0].nat_rec_fac)))
- HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree leaf native keys")
-#ifdef H5_CLEAR_MEMORY
-HDmemset(leaf->leaf_native, 0, hdr->cls->nrec_size * hdr->node_info[0].max_nrec);
-#endif /* H5_CLEAR_MEMORY */
+ HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree leaf native keys")
+ HDmemset(leaf->leaf_native, 0, hdr->cls->nrec_size * hdr->node_info[0].max_nrec);
/* Set number of records */
leaf->nrec = 0;
/* Allocate space on disk for the leaf */
if(HADDR_UNDEF == (node_ptr->addr = H5MF_alloc(hdr->f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)hdr->node_size)))
- HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree leaf node")
+ HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree leaf node")
/* Cache the new B-tree node */
if(H5AC_insert_entry(hdr->f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree leaf to cache")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree leaf to cache")
done:
if(ret_value < 0) {
- if(leaf)
+ if(leaf)
if(H5B2__leaf_free(leaf) < 0)
HDONE_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to release v2 B-tree leaf node")
} /* end if */
@@ -1911,16 +2326,12 @@ H5B2__create_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *node_ptr,
/* Allocate space for the native keys in memory */
if(NULL == (internal->int_native = (uint8_t *)H5FL_FAC_MALLOC(hdr->node_info[depth].nat_rec_fac)))
HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal native keys")
-#ifdef H5_CLEAR_MEMORY
-HDmemset(internal->int_native, 0, hdr->cls->nrec_size * hdr->node_info[depth].max_nrec);
-#endif /* H5_CLEAR_MEMORY */
+ HDmemset(internal->int_native, 0, hdr->cls->nrec_size * hdr->node_info[depth].max_nrec);
/* Allocate space for the node pointers in memory */
if(NULL == (internal->node_ptrs = (H5B2_node_ptr_t *)H5FL_FAC_MALLOC(hdr->node_info[depth].node_ptr_fac)))
HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal node pointers")
-#ifdef H5_CLEAR_MEMORY
-HDmemset(internal->node_ptrs, 0, sizeof(H5B2_node_ptr_t) * (hdr->node_info[depth].max_nrec + 1));
-#endif /* H5_CLEAR_MEMORY */
+ HDmemset(internal->node_ptrs, 0, sizeof(H5B2_node_ptr_t) * (hdr->node_info[depth].max_nrec + 1));
/* Set number of records & depth of the node */
internal->nrec = 0;
@@ -2124,6 +2535,7 @@ H5B2__remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr
haddr_t leaf_addr = HADDR_UNDEF; /* Leaf address on disk */
unsigned leaf_flags = H5AC__NO_FLAGS_SET; /* Flags for unprotecting leaf node */
unsigned idx; /* Location of record which matches key */
+ int cmp; /* Comparison value of records */
herr_t ret_value = SUCCEED; /* Return value */
FUNC_ENTER_PACKAGE
@@ -2143,7 +2555,9 @@ H5B2__remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr
HDassert(leaf->nrec == curr_node_ptr->node_nrec);
/* Find correct location to remove this record */
- if(H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx) != 0)
+ if(H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
+ if(cmp != 0)
HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree")
/* Check for invalidating the min/max record for the tree */
@@ -2151,18 +2565,14 @@ H5B2__remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr
/* (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 */
+ if(hdr->min_native_rec)
+ hdr->min_native_rec = H5MM_xfree(hdr->min_native_rec);
} /* 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 */
+ if(hdr->max_native_rec)
+ hdr->max_native_rec = H5MM_xfree(hdr->max_native_rec);
} /* end if */
} /* end if */
} /* end if */
@@ -2291,7 +2701,9 @@ H5B2__remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased,
if(swap_loc)
idx = 0;
else {
- cmp = H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx);
+ if(H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native,
+ udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
if(cmp >= 0)
idx++;
} /* end else */
@@ -2353,7 +2765,8 @@ H5B2__remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased,
idx = 0;
else {
/* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */
- cmp = H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx);
+ if(H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
if(cmp >= 0)
idx++;
} /* end else */
@@ -2466,18 +2879,14 @@ H5B2__remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
/* (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 */
+ if(hdr->min_native_rec)
+ hdr->min_native_rec = H5MM_xfree(hdr->min_native_rec);
} /* 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 */
+ if(hdr->max_native_rec)
+ hdr->max_native_rec = H5MM_xfree(hdr->max_native_rec);
} /* end if */
} /* end if */
} /* end if */
@@ -2841,7 +3250,8 @@ H5B2__neighbor_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_p
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node")
/* Locate node pointer for child */
- cmp = H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx);
+ if(H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
if(cmp > 0)
idx++;
else
@@ -2928,7 +3338,9 @@ H5B2__neighbor_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, uint16_t depth,
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node")
/* Locate node pointer for child */
- cmp = H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx);
+ if(H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native,
+ udata, &idx, &cmp) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records")
if(cmp > 0)
idx++;
generated by cgit v0.12 at 2024-07-22 00:33:00 (GMT)