[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)

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 */