summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/H5B2.c238
-rw-r--r--src/H5B2pkg.h4
-rw-r--r--src/H5B2private.h9
-rw-r--r--src/H5B2test.c81
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() */
+