[svn-r10094] Purpose:

    New features & refactor

Description:
    Add basic record removal (only handles level-0 B-trees currently)

    Add query routine to check the number of records in a B-tree

    Add debugging routine to check the address of the root node in the B-tree

Platforms tested:
    FreeBSD 4.11 (sleipnir)
    Solaris 2.9 (shanti)

4 files changed, 306 insertions, 26 deletions

diff --git a/src/H5B2.c b/src/H5B2.c
index 0b6ed65..6dbb52c 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -1800,9 +1800,7 @@ done:
 /*-------------------------------------------------------------------------
  * Function:	H5B2_insert
  *
- * Purpose:	Adds a new record to the B-tree.  If the root node of
- *		the B-tree splits then the B-tree header tracks the new
- *              root node created.
+ * Purpose:	Adds a new record to the B-tree.
  *
  * Return:	Non-negative on success/Negative on failure
  *
@@ -2047,7 +2045,7 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
 
     /* Must have a leaf node with enough space to insert a record now */
     HDassert(H5F_addr_defined(leaf_ptr.addr));
-    HDassert(leaf_nrec < shared->split_leaf_nrec); /* node pointer to leaf has already been incremented */
+    HDassert(leaf_nrec < shared->split_leaf_nrec);
 
     /* Look up the B-tree leaf node */
     if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, &leaf_nrec, bt2_shared, H5AC_WRITE)))
@@ -2061,17 +2059,9 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
     if(leaf->nrec==0)
         idx=0;
     else {
-        /* Sanity check for the leaf node being full */
-        HDassert(leaf->nrec!=shared->split_leaf_nrec);
-
         /* Find correct location to insert this record */
-        if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0) {
-            /* Release the B-tree leaf node */
-            if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
-                HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
-
+        if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0)
             HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
-        } /* end if */
         if(cmp > 0)
             idx++;
 
@@ -2081,13 +2071,8 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
     } /* end else */
 
     /* Make callback to store record in native form */
-    if((shared->type->store)(udata,H5B2_LEAF_NREC(leaf,shared,idx))<0) {
-        /* Release the B-tree leaf node */
-        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
-            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
-
+    if((shared->type->store)(H5B2_LEAF_NREC(leaf,shared,idx),udata)<0)
         HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node")
-    } /* end if */
 
     /* Update number of records in node */
     leaf->nrec++;
@@ -2095,14 +2080,16 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
     /* Mark leaf node as dirty also */
     leaf->cache_info.is_dirty = TRUE;
 
+done:
     /* Release the B-tree leaf node */
+    if (leaf) {
 #ifdef H5B2_DEBUG
 H5B2_assert_leaf(shared,leaf);
 #endif /* H5B2_DEBUG */
-    if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
-        HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
+        if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+            HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
+    } /* end if */
 
-done:
     /* Check if we need to decrement the reference count for the B-tree's shared info */
     if(incr_rc)
         H5RC_DEC(bt2_shared);
@@ -2774,6 +2761,213 @@ done:
     FUNC_LEAVE_NOAPI(ret_value)
 } /* H5B2_index() */
 
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_remove
+ *
+ * Purpose:	Removes a record from a B-tree.
+ *              
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 25 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
+           void *udata)
+{
+    H5B2_t	*bt2=NULL;              /* Pointer to the B-tree header */
+    H5RC_t      *bt2_shared=NULL;       /* Pointer to ref-counter for shared B-tree info */
+    H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
+    hbool_t     incr_rc=FALSE;          /* Flag to indicate that we've incremented the B-tree's shared info reference count */
+    H5AC_info_t *parent_cache_info=NULL;/* Parent node's cache info */
+    haddr_t     parent_addr=HADDR_UNDEF;/* Address of parent which contain's node pointer to current node */
+    void        *parent_ptr=NULL;       /* Pointer to parent structure in memory */
+    H5B2_node_ptr_t *curr_node_ptr=NULL;/* Pointer to node pointer info for current node (in parent node) */
+    H5B2_leaf_t *leaf=NULL;             /* Pointer to leaf node */
+    haddr_t     leaf_addr=HADDR_UNDEF;  /* Leaf address on disk */
+    unsigned    leaf_unprotect_flags=H5C__NO_FLAGS_SET; /* Flags for unprotecting leaf node */
+    unsigned    depth;                  /* Depth of B-tree */
+    int         cmp;                    /* Comparison value of records */
+    unsigned    idx;                    /* Location of record which matches key */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5B2_remove, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(type);
+    HDassert(H5F_addr_defined(addr));
+
+    /* Look up the B-tree header */
+    if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_WRITE)))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header")
+
+    /* Safely grab pointer to reference counted shared B-tree info, so we can release the B-tree header if necessary */
+    bt2_shared=bt2->shared;
+    H5RC_INC(bt2_shared);
+    incr_rc=TRUE;
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(bt2_shared);
+    HDassert(shared);
+
+    /* Get B-tree depth */
+    depth = bt2->depth;
+
+    /* Check for empty B-tree */
+    if(bt2->root.all_nrec==0) {
+        /* Release B-tree header node */
+        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info")
+        bt2=NULL;
+
+        /* Indicate error */
+        HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree")
+    } /* end if */
+
+    /* Check for non-trivial B-tree */
+    if(bt2->depth>0) {
+HDfprintf(stderr,"%s: Deleting record in non-trival B-tree!\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree")
+    } /* end if */
+    else {
+        /* Set initial "parent" information to the B-tree header */
+        parent_cache_info=&(bt2->cache_info);
+        parent_addr=addr;
+        parent_ptr=bt2;
+
+        /* Set initial node pointer for "current" node */
+        curr_node_ptr=&(bt2->root);
+    } /* end else */
+
+    /* Must have a leaf node with enough space to insert a record now */
+    HDassert(H5F_addr_defined(curr_node_ptr->addr));
+    /* Root only B-tree must break a few rules */
+    if(depth>0)
+        HDassert(curr_node_ptr->node_nrec > shared->merge_leaf_nrec);
+
+    /* Look up the B-tree leaf node */
+    leaf_addr = curr_node_ptr->addr;
+    if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, leaf_addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE)))
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load 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);
+
+    /* Find correct location to insert this record */
+    if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) != 0)
+        HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree")
+
+    /* Make callback to retrieve record in native form */
+    if((shared->type->retrieve)(udata,H5B2_LEAF_NREC(leaf,shared,idx))<0)
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record into leaf node")
+
+    /* Update number of records in node */
+    leaf->nrec--;
+
+    /* Mark leaf node as dirty also */
+    leaf->cache_info.is_dirty = TRUE;
+
+    if(leaf->nrec>0) {
+        /* Pack record out of leaf */
+        HDmemmove(H5B2_LEAF_NREC(leaf,shared,idx),H5B2_LEAF_NREC(leaf,shared,idx+1),shared->type->nrec_size*(leaf->nrec-idx));
+    } /* end if */
+    else {
+        /* Sanity check - we are only allowed to delete a leaf when it's the root node */
+        HDassert(depth == 0);
+        HDassert(parent_cache_info->type == H5AC_BT2_HDR);
+
+        /* Release space for B-tree node on disk */
+        if (H5MF_xfree(f, H5FD_MEM_BTREE, dxpl_id, leaf_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 */
+        leaf_unprotect_flags = H5C__DELETED_FLAG;
+
+        /* Reset address of parent node pointer */
+        curr_node_ptr->addr = HADDR_UNDEF;
+    } /* end else */
+
+    /* Update record count for parent of leaf node */
+    curr_node_ptr->all_nrec--;
+    curr_node_ptr->node_nrec--;
+
+    /* Mark parent node as dirty */
+    parent_cache_info->is_dirty = TRUE;
+
+done:
+    /* Release parent of leaf node */
+    if(parent_ptr) {
+        /* Unlock parent node (possibly the B-tree header) */
+        if (H5AC_unprotect(f, dxpl_id, parent_cache_info->type, parent_addr, parent_ptr, H5AC__NO_FLAGS_SET) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree info")
+    } /* end if */
+
+    /* Release the B-tree leaf node */
+    if (leaf) {
+#ifdef H5B2_DEBUG
+H5B2_assert_leaf(shared,leaf);
+#endif /* H5B2_DEBUG */
+        if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_addr, leaf, leaf_unprotect_flags) < 0)
+            HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
+    } /* end if */
+
+    /* Check if we need to decrement the reference count for the B-tree's shared info */
+    if(incr_rc)
+        H5RC_DEC(bt2_shared);
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_remove() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_get_nrec
+ *
+ * Purpose:	Retrieves the number of records in a B-tree
+ *              
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 25 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_get_nrec(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
+           hsize_t *nrec)
+{
+    H5B2_t	*bt2=NULL;              /* Pointer to the B-tree header */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5B2_get_nrec, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(type);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(nrec);
+
+    /* Look up the B-tree header */
+    if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_WRITE)))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header")
+
+    /* Get B-tree number of records */
+    *nrec = bt2->root.all_nrec;
+
+done:
+    /* Release B-tree header node */
+    if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_get_nrec() */
+
 #ifdef H5B2_DEBUG
 
 /*-------------------------------------------------------------------------
diff --git a/src/H5B2pkg.h b/src/H5B2pkg.h
index e410f7b..b49ed45 100644
--- a/src/H5B2pkg.h
+++ b/src/H5B2pkg.h
@@ -193,6 +193,10 @@ H5_DLL herr_t H5B2_int_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
 H5_DLL herr_t H5B2_leaf_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
     FILE *stream, int indent, int fwidth, const H5B2_class_t *type,
     haddr_t hdr_addr, unsigned nrec);
+#ifdef H5B2_TESTING
+H5_DLL herr_t H5B2_get_root_addr(H5F_t *f, hid_t dxpl_id,
+    const H5B2_class_t *type, haddr_t addr, haddr_t *root_addr);
+#endif /* H5B2_TESTING */
 
 #endif /* _H5B2pkg_H */
 
diff --git a/src/H5B2private.h b/src/H5B2private.h
index 0608599..358962e 100644
--- a/src/H5B2private.h
+++ b/src/H5B2private.h
@@ -70,8 +70,9 @@ typedef struct H5B2_class_t {
     H5B2_subid_t id;				/*id as found in file*/
     size_t	nrec_size;			/*size of native (memory) record*/
 
-    /* Store record from application to B-tree 'native' form */
-    herr_t (*store)(const void *udata, void *nrecord);                  /*  Store record in native record table */
+    /* Store & retrieve record from application to B-tree 'native' form */
+    herr_t (*store)(void *nrecord, const void *udata);                  /*  Store record in native record table */
+    herr_t (*retrieve)(void *udata, const void *nrecord);               /*  Retrieve record in native record table */
 
     /* Compare records, according to a key */
     herr_t (*compare)(const void *rec1, const void *rec2);              /*  Compare two native records */
@@ -101,6 +102,10 @@ H5_DLL herr_t H5B2_find(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
     haddr_t addr, void *udata, H5B2_found_t op, void *op_data);
 H5_DLL herr_t H5B2_index(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
     haddr_t addr, hsize_t idx, H5B2_found_t op, void *op_data);
+H5_DLL herr_t H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
+    haddr_t addr, void *udata);
+H5_DLL herr_t H5B2_get_nrec(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
+    haddr_t addr, hsize_t *nrec);
 
 #endif /* _H5B2private_H */
 
diff --git a/src/H5B2test.c b/src/H5B2test.c
index ac45377..6180683 100644
--- a/src/H5B2test.c
+++ b/src/H5B2test.c
@@ -24,9 +24,11 @@
 /* Private headers */
 #include "H5private.h"		/* Generic Functions			*/
 #include "H5B2pkg.h"		/* B-trees				*/
+#include "H5Eprivate.h"		/* Error handling		  	*/
 
 /* Static Prototypes */
-static herr_t H5B2_test_store(const void *udata, void *nrecord);
+static herr_t H5B2_test_store(void *nrecord, const void *udata);
+static herr_t H5B2_test_retrieve(void *udata, const void *nrecord);
 static herr_t H5B2_test_compare(const void *rec1, const void *rec2);
 static herr_t H5B2_test_encode(const H5F_t *f, uint8_t *raw,
     const void *nrecord);
@@ -40,6 +42,7 @@ const H5B2_class_t H5B2_TEST[1]={{   /* B-tree class information */
     H5B2_TEST_ID,                   /* Type of B-tree */
     sizeof(hsize_t),                /* Size of native key */
     H5B2_test_store,                /* Record storage callback */
+    H5B2_test_retrieve,             /* Record retrieval callback */
     H5B2_test_compare,              /* Record comparison callback */
     H5B2_test_encode,               /* Record encoding callback */
     H5B2_test_decode,               /* Record decoding callback */
@@ -64,7 +67,7 @@ const H5B2_class_t H5B2_TEST[1]={{   /* B-tree class information */
  *-------------------------------------------------------------------------
  */
 static herr_t
-H5B2_test_store(const void *udata, void *nrecord)
+H5B2_test_store(void *nrecord, const void *udata)
 {
     FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_test_store)
 
@@ -75,6 +78,33 @@ H5B2_test_store(const void *udata, void *nrecord)
 
 
 /*-------------------------------------------------------------------------
+ * Function:	H5B2_test_retrieve
+ *
+ * Purpose:	Retrieve native information from record for B-tree
+ *
+ * Return:	Success:	non-negative
+ *
+ *		Failure:	negative
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, February 25, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_test_retrieve(void *udata, const void *nrecord)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_test_retrieve)
+
+    *(hsize_t *)udata=*(const hsize_t *)nrecord;
+
+    FUNC_LEAVE_NOAPI(SUCCEED);
+} /* H5B2_test_retrieve() */
+
+
+/*-------------------------------------------------------------------------
  * Function:	H5B2_test_compare
  *
  * Purpose:	Compare two native information records, according to some key
@@ -183,3 +213,50 @@ H5B2_test_debug(FILE *stream, const H5F_t UNUSED *f, hid_t UNUSED dxpl_id, int i
     FUNC_LEAVE_NOAPI(SUCCEED);
 } /* H5B2_test_debug() */
 
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_get_root_addr
+ *
+ * Purpose:	Retrieve the root node's address
+ *
+ * Return:	Success:	non-negative
+ *
+ *		Failure:	negative
+ *
+ * Programmer:	Quincey Koziol
+ *              Saturday, February 26, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_get_root_addr(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
+    haddr_t addr, haddr_t *root_addr)
+{
+    H5B2_t	*bt2=NULL;              /* Pointer to the B-tree header */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_get_root_addr)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(type);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(root_addr);
+
+    /* Look up the B-tree header */
+    if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_WRITE)))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree header")
+
+    /* Get B-tree root addr */
+    *root_addr = bt2->root.addr;
+
+done:
+    /* Release B-tree header node */
+    if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_get_root_addr() */
+