From 630b2901c53c66c837e39babe9da0c20020e5d4d Mon Sep 17 00:00:00 2001
From: Quincey Koziol <koziol@hdfgroup.org>
Date: Sat, 5 Mar 2005 02:50:17 -0500
Subject: [svn-r10156] Purpose: Bug fix & new feature
Description:
Allow B-tree's height to be reduced when removing records.
Platforms tested:
FreeBSD 4.11 (sleipnir)
Solaris 2.9 (shanti)
---
src/H5B2.c | 92 ++++++++++++++++++++++++++++++++++++---------
test/btree2.c | 119 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
2 files changed, 192 insertions(+), 19 deletions(-)
diff --git a/src/H5B2.c b/src/H5B2.c
index 379a440..22894f2 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -84,6 +84,11 @@ static herr_t H5B2_insert_internal(H5F_t *f, hid_t dxpl_id,
H5B2_node_ptr_t *curr_node_ptr, void *udata);
static herr_t H5B2_insert_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
H5B2_node_ptr_t *curr_node_ptr, void *udata);
+static herr_t H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+ hbool_t *depth_decreased, unsigned depth, H5AC_info_t *parent_cache_info,
+ H5B2_node_ptr_t *curr_node_ptr, void *udata);
+static herr_t H5B2_remove_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+ H5B2_node_ptr_t *curr_node_ptr, void *udata);
static herr_t H5B2_iterate_node(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
unsigned depth, const H5B2_node_ptr_t *curr_node, H5B2_operator_t op,
void *op_data);
@@ -3343,7 +3348,6 @@ H5B2_remove_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
} /* end else */
/* Update record count for parent of leaf node */
- curr_node_ptr->all_nrec--;
curr_node_ptr->node_nrec--;
done:
@@ -3370,12 +3374,18 @@ done:
*/
static herr_t
H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
- unsigned depth, H5AC_info_t *parent_cache_info,
+ hbool_t *depth_decreased, unsigned depth, H5AC_info_t *parent_cache_info,
H5B2_node_ptr_t *curr_node_ptr, void *udata)
{
+ H5AC_info_t *new_cache_info; /* Pointer to new cache info */
+ H5B2_node_ptr_t *new_node_ptr; /* Pointer to new node pointer */
H5B2_internal_t *internal; /* Pointer to internal node */
+ haddr_t internal_addr; /* Address of internal node */
H5B2_shared_t *shared; /* Pointer to B-tree's shared information */
+ unsigned internal_unprotect_flags=H5C__NO_FLAGS_SET; /* Flags for unprotecting internal node */
unsigned idx; /* Location of record which matches key */
+ size_t merge_nrec; /* Number of records to merge node at */
+ hbool_t collapsed_root = FALSE; /* Whether the root was collapsed */
herr_t ret_value = SUCCEED;
FUNC_ENTER_NOAPI_NOINIT(H5B2_remove_internal)
@@ -3389,18 +3399,55 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
HDassert(H5F_addr_defined(curr_node_ptr->addr));
/* Lock current B-tree node */
- if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
+ internal_addr = curr_node_ptr->addr;
+ if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, internal_addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
/* Get the pointer to the shared B-tree info */
shared=H5RC_GET_OBJ(bt2_shared);
HDassert(shared);
-/* Merge or redistribute child node pointers, if necessary */
- {
+ /* Determine the correct number of records to merge at */
+ if(depth==1)
+ merge_nrec = shared->merge_leaf_nrec;
+ else
+ merge_nrec = shared->merge_int_nrec;
+
+ /* Check for needing to collapse the root node */
+ /* (The root node is the only node allowed to have 1 record) */
+ if(internal->nrec == 1 &&
+ ((internal->node_ptrs[0].node_nrec + internal->node_ptrs[1].node_nrec) <= ((merge_nrec * 2) + 1))) {
+
+ /* Merge children of root node */
+ if(H5B2_merge2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,0)<0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to merge child node")
+
+ /* Release space for root B-tree node on disk */
+ if (H5MF_xfree(f, H5FD_MEM_BTREE, dxpl_id, internal_addr, (hsize_t)shared->node_size)<0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to free B-tree leaf node")
+
+ /* Let the cache know that the object is deleted */
+ internal_unprotect_flags = H5C__DELETED_FLAG;
+
+ /* Reset information in parent node pointer */
+ curr_node_ptr->addr = internal->node_ptrs[0].addr;
+ curr_node_ptr->node_nrec = internal->node_ptrs[0].node_nrec;
+
+ /* Indicate that the level of the B-tree decreased */
+ *depth_decreased = TRUE;
+ depth--;
+
+ /* Set pointers for advancing to child node */
+ new_cache_info = parent_cache_info;
+ new_node_ptr = curr_node_ptr;
+
+ /* Set flag to indicate root was collapsed */
+ collapsed_root = TRUE;
+ } /* end if */
+ /* Merge or redistribute child node pointers, if necessary */
+ else {
int cmp; /* Comparison value of records */
unsigned retries; /* Number of times to attempt redistribution */
- size_t merge_nrec; /* Number of records to merge node at */
/* Locate node pointer for child */
cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx);
@@ -3415,12 +3462,6 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
* eventually force a merge */
retries = 2;
- /* Determine the correct number of records to merge at */
- if(depth==1)
- merge_nrec = shared->merge_leaf_nrec;
- else
- merge_nrec = shared->merge_int_nrec;
-
/* Preemptively merge/redistribute a node we will enter */
while(internal->node_ptrs[idx].node_nrec==merge_nrec) {
/* Attempt to redistribute records among children */
@@ -3473,27 +3514,35 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
HGOTO_ERROR(H5E_BTREE, H5E_CANTSWAP, FAIL, "Can't swap records in B-tree")
} /* end if */
- } /* end block */
+ /* Set pointers for advancing to child node */
+ new_cache_info = &internal->cache_info;
+ new_node_ptr = &internal->node_ptrs[idx];
+ } /* end else */
/* Attempt to remove node */
if(depth>1) {
- if(H5B2_remove_internal(f,dxpl_id,bt2_shared,depth-1,&internal->cache_info,&internal->node_ptrs[idx],udata)<0)
+ if(H5B2_remove_internal(f,dxpl_id,bt2_shared,depth_decreased,depth-1,new_cache_info,new_node_ptr,udata)<0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree internal node")
} /* end if */
else {
- if(H5B2_remove_leaf(f,dxpl_id,bt2_shared,&internal->node_ptrs[idx],udata)<0)
+ if(H5B2_remove_leaf(f,dxpl_id,bt2_shared,new_node_ptr,udata)<0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree leaf node")
} /* end else */
/* Update record count for node pointer to current node */
- curr_node_ptr->all_nrec--;
+ if(!collapsed_root)
+ new_node_ptr->all_nrec--;
/* Mark node as dirty */
internal->cache_info.is_dirty = TRUE;
+#ifdef H5B2_DEBUG
+ H5B2_assert_internal((!collapsed_root ? (curr_node_ptr->all_nrec-1) : new_node_ptr->all_nrec),shared,internal);
+#endif /* H5B2_DEBUG */
+
done:
/* Release the B-tree internal node */
- if (internal && H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0)
+ if (internal && H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, internal_addr, internal, internal_unprotect_flags) < 0)
HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release internal B-tree node")
FUNC_LEAVE_NOAPI(ret_value)
@@ -3542,14 +3591,21 @@ H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
/* Attempt to remove record from B-tree */
if(bt2->depth>0) {
- if(H5B2_remove_internal(f,dxpl_id,bt2->shared,bt2->depth,&(bt2->cache_info),&bt2->root,udata)<0)
+ hbool_t depth_decreased=FALSE; /* Flag to indicate whether the depth of the B-tree decreased */
+
+ if(H5B2_remove_internal(f,dxpl_id,bt2->shared, &depth_decreased, bt2->depth,&(bt2->cache_info),&bt2->root,udata)<0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree internal node")
+
+ bt2->depth -= depth_decreased;
} /* end if */
else {
if(H5B2_remove_leaf(f,dxpl_id,bt2->shared,&bt2->root,udata)<0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree leaf node")
} /* end else */
+ /* Decrement # of records in B-tree */
+ bt2->root.all_nrec--;
+
/* Mark parent node as dirty */
bt2->cache_info.is_dirty = TRUE;
diff --git a/test/btree2.c b/test/btree2.c
index 1bebd20..86ed020 100644
--- a/test/btree2.c
+++ b/test/btree2.c
@@ -3533,7 +3533,123 @@ error:
H5Fclose(file);
} H5E_END_TRY;
return 1;
-} /* test_remove_level1_promote_3leaf_redistrib() */
+} /* test_remove_level1_promote_3leaf_merge() */
+
+
+/*-------------------------------------------------------------------------
+ * Function: test_remove_level1_collapse
+ *
+ * Purpose: Basic tests for the B-tree v2 code
+ *
+ * Return: Success: 0
+ *
+ * Failure: 1
+ *
+ * Programmer: Quincey Koziol
+ * Friday, March 4, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+test_remove_level1_collapse(hid_t fapl)
+{
+ hid_t file=-1;
+ char filename[1024];
+ H5F_t *f=NULL;
+ hsize_t record; /* Record to insert into tree */
+ hsize_t nrec; /* Number of records in B-tree */
+ haddr_t bt2_addr; /* Address of B-tree created */
+ haddr_t root_addr; /* Address of root of B-tree created */
+ unsigned u; /* Local index variable */
+
+ h5_fixname(FILENAME[0], fapl, filename, sizeof filename);
+
+ /* Create the file to work on */
+ if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR;
+
+ /* Get a pointer to the internal file object */
+ if (NULL==(f=H5I_object(file))) {
+ H5Eprint_stack(H5E_DEFAULT, stdout);
+ TEST_ERROR;
+ }
+
+ /*
+ * Test v2 B-tree creation
+ */
+ if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) {
+ H5_FAILED();
+ H5Eprint_stack(H5E_DEFAULT, stdout);
+ goto error;
+ }
+
+ /* Create level-1 B-tree with 2 leaves */
+ for(u=0; u<INSERT_SPLIT_ROOT_NREC; u++) {
+ record=u;
+ if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) {
+ H5_FAILED();
+ H5Eprint_stack(H5E_DEFAULT, stdout);
+ goto error;
+ }
+ }
+
+ /* Query the number of records in the B-tree */
+ if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) {
+ H5_FAILED();
+ H5Eprint_stack(H5E_DEFAULT, stdout);
+ goto error;
+ } /* end if */
+
+ /* Make certain that the # of records is correct */
+ if(nrec != (INSERT_SPLIT_ROOT_NREC)) TEST_ERROR;
+
+ /* Query the address of the root node in the B-tree */
+ if (H5B2_get_root_addr(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &root_addr)<0) {
+ H5_FAILED();
+ H5Eprint_stack(H5E_DEFAULT, stdout);
+ goto error;
+ } /* end if */
+
+ /* Make certain that the address of the root node is defined */
+ if(!H5F_addr_defined(root_addr)) TEST_ERROR;
+
+ /* Attempt to remove records from B-tree to force a single leaf for the B-tree */
+ TESTING("B-tree remove: collapse level-1 B-tree back to level-0");
+ for(u=0; u < 29; u++) {
+ record = INSERT_SPLIT_ROOT_NREC - (u+1);
+ if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) {
+ H5_FAILED();
+ H5Eprint_stack(H5E_DEFAULT, stdout);
+ goto error;
+ } /* end if */
+
+ /* Make certain that the record value is correct */
+ if(record != (INSERT_SPLIT_ROOT_NREC - (u+1))) TEST_ERROR;
+
+ /* Query the number of records in the B-tree */
+ if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) {
+ H5_FAILED();
+ H5Eprint_stack(H5E_DEFAULT, stdout);
+ goto error;
+ } /* end if */
+
+ /* Make certain that the # of records is correct */
+ if(nrec != (INSERT_SPLIT_ROOT_NREC-(u+1))) TEST_ERROR;
+ } /* end for */
+
+ PASSED();
+
+ if (H5Fclose(file)<0) TEST_ERROR;
+
+ return 0;
+
+error:
+ H5E_BEGIN_TRY {
+ H5Fclose(file);
+ } H5E_END_TRY;
+ return 1;
+} /* test_remove_level1_collapse() */
/*-------------------------------------------------------------------------
@@ -3596,6 +3712,7 @@ HDfprintf(stderr,"Uncomment tests!\n");
nerrors += test_remove_level1_promote_3leaf_redistrib(fapl);
nerrors += test_remove_level1_promote_2leaf_merge(fapl);
nerrors += test_remove_level1_promote_3leaf_merge(fapl);
+ nerrors += test_remove_level1_collapse(fapl);
#else /* QAK */
HDfprintf(stderr,"Uncomment tests!\n");
#endif /* QAK */
--
cgit v0.12