summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2006-11-07 15:25:06 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2006-11-07 15:25:06 (GMT)
commitbc0b7c478f4d4857023baec12763e0fb5cb45222 (patch)
tree214f769be5409eac0cac65d2d4e5324adcf1d241
parenteb36a96a79dd1cd6514794a18baac5f13ce633ae (diff)
downloadhdf5-bc0b7c478f4d4857023baec12763e0fb5cb45222.zip
hdf5-bc0b7c478f4d4857023baec12763e0fb5cb45222.tar.gz
hdf5-bc0b7c478f4d4857023baec12763e0fb5cb45222.tar.bz2
[svn-r12873] Decription:
Add support for reverse index lookup to v2 B-trees (needed for reverse index lookup of links in groups) Tested on: Linux/64 2.6 (chicago2)
-rw-r--r--src/H5B2.c16
-rw-r--r--src/H5B2private.h3
-rw-r--r--src/H5Gdense.c4
-rw-r--r--test/btree2.c79
4 files changed, 73 insertions, 29 deletions
diff --git a/src/H5B2.c b/src/H5B2.c
index 8e66aa3..3dd607e 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -490,7 +490,7 @@ done:
*/
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_iter_order_t order, hsize_t idx, H5B2_found_t op, void *op_data)
{
H5B2_t *bt2=NULL; /* Pointer to the B-tree header */
H5RC_t *bt2_shared=NULL; /* Pointer to ref-counter for shared B-tree info */
@@ -540,6 +540,10 @@ H5B2_index(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
if(idx >= curr_node_ptr.all_nrec)
HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree doesn't have that many records")
+ /* Check for reverse indexing and map requested index to appropriate forward index */
+ if(order == H5_ITER_DEC)
+ idx = curr_node_ptr.all_nrec - (idx + 1);
+
/* Walk down B-tree to find record or leaf node where record is located */
while(depth > 0) {
H5B2_internal_t *internal; /* Pointer to internal node in B-tree */
@@ -618,25 +622,25 @@ H5B2_index(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
H5B2_leaf_t *leaf; /* Pointer to leaf node in B-tree */
/* Lock B-tree leaf node */
- if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr.addr, &(curr_node_ptr.node_nrec), bt2_shared, H5AC_READ)))
+ if(NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr.addr, &(curr_node_ptr.node_nrec), bt2_shared, H5AC_READ)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
/* Sanity check index */
HDassert(idx < leaf->nrec);
/* Make callback for correct record */
- if ((op)(H5B2_LEAF_NREC(leaf,shared,idx), op_data) <0) {
+ if((op)(H5B2_LEAF_NREC(leaf,shared,idx), op_data) < 0) {
/* Unlock current node */
- if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+ if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation")
} /* end if */
/* Unlock current node */
- if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+ if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
- }
+ } /* end block */
done:
/* Check if we need to decrement the reference count for the B-tree's shared info */
diff --git a/src/H5B2private.h b/src/H5B2private.h
index 2ed9555..c262056 100644
--- a/src/H5B2private.h
+++ b/src/H5B2private.h
@@ -129,7 +129,8 @@ H5_DLL herr_t H5B2_iterate(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
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);
+ haddr_t addr, H5_iter_order_t order, hsize_t idx, H5B2_found_t op,
+ void *op_data);
H5_DLL herr_t H5B2_neighbor(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
haddr_t addr, H5B2_compare_t comp, void *udata, H5B2_found_t op,
void *op_data);
diff --git a/src/H5Gdense.c b/src/H5Gdense.c
index 52aa5ce..46ba593 100644
--- a/src/H5Gdense.c
+++ b/src/H5Gdense.c
@@ -971,7 +971,7 @@ H5G_dense_get_name_by_idx(H5F_t *f, hid_t dxpl_id, H5O_linfo_t *linfo,
/* Retrieve the name according to the v2 B-tree's index order */
/* (XXX: using name index currently) */
- if(H5B2_index(f, dxpl_id, H5G_BT2_NAME, linfo->name_bt2_addr, idx,
+ if(H5B2_index(f, dxpl_id, H5G_BT2_NAME, linfo->name_bt2_addr, H5_ITER_INC, idx,
H5G_dense_get_name_by_idx_bt2_cb, &udata) < 0)
HGOTO_ERROR(H5E_SYM, H5E_CANTLIST, FAIL, "can't locate object in v2 B-tree")
@@ -1125,7 +1125,7 @@ H5G_dense_get_type_by_idx(H5F_t *f, hid_t dxpl_id, H5O_linfo_t *linfo,
/* Retrieve the name according to the v2 B-tree's index order */
/* (XXX: using name index currently) */
- if(H5B2_index(f, dxpl_id, H5G_BT2_NAME, linfo->name_bt2_addr, idx,
+ if(H5B2_index(f, dxpl_id, H5G_BT2_NAME, linfo->name_bt2_addr, H5_ITER_INC, idx,
H5G_dense_get_type_by_idx_bt2_cb, &udata) < 0)
HGOTO_ERROR(H5E_SYM, H5E_CANTLIST, FAIL, "can't locate object in v2 B-tree")
diff --git a/test/btree2.c b/test/btree2.c
index c1fb7e9..48692f2 100644
--- a/test/btree2.c
+++ b/test/btree2.c
@@ -98,6 +98,34 @@ find_cb(const void *_record, void *_op_data)
/*-------------------------------------------------------------------------
+ * Function: find_dec_cb
+ *
+ * Purpose: v2 B-tree find callback for indexing in decreasing order
+ *
+ * Note: Currently hard-wired to "insert_lots" test
+ *
+ * Return: Success: 0
+ * Failure: 1
+ *
+ * Programmer: Quincey Koziol
+ * Tuesday, November 7, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+find_dec_cb(const void *_record, void *_op_data)
+{
+ const hsize_t *record = (const hsize_t *)_record;
+ hsize_t *search = (hsize_t *)_op_data;
+
+ if(*record != (INSERT_MANY - (*search + 1)))
+ return(-1);
+
+ return(0);
+} /* end find_dec_cb() */
+
+
+/*-------------------------------------------------------------------------
* Function: neighbor_cb
*
* Purpose: v2 B-tree neighbor callback
@@ -242,7 +270,7 @@ test_insert_basic(hid_t fapl)
/* Attempt to index record in B-tree with no records */
idx = 0;
H5E_BEGIN_TRY {
- ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)0, find_cb, NULL);
+ ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)0, find_cb, NULL);
} H5E_END_TRY;
/* Should fail */
if(ret != FAIL)
@@ -285,7 +313,7 @@ test_insert_basic(hid_t fapl)
/* Attempt to index non-existant record in B-tree with 1 record */
idx = 0;
H5E_BEGIN_TRY {
- ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)1, find_cb, NULL);
+ ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)1, find_cb, NULL);
} H5E_END_TRY;
/* Should fail */
if(ret != FAIL)
@@ -293,7 +321,7 @@ test_insert_basic(hid_t fapl)
/* Attempt to index existing record in B-tree with 1 record */
idx = 42;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)0, find_cb, &idx)<0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)0, find_cb, &idx)<0)
TEST_ERROR
/*
@@ -334,7 +362,7 @@ test_insert_basic(hid_t fapl)
/* Attempt to index non-existant record in B-tree with several records */
idx = 0;
H5E_BEGIN_TRY {
- ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)4, find_cb, NULL);
+ ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)4, find_cb, NULL);
} H5E_END_TRY;
/* Should fail */
if(ret != FAIL)
@@ -342,16 +370,16 @@ test_insert_basic(hid_t fapl)
/* Attempt to index existing record in B-tree with several records */
idx = 34;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)0, find_cb, &idx)<0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)0, find_cb, &idx)<0)
TEST_ERROR
idx = 38;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)1, find_cb, &idx)<0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)1, find_cb, &idx)<0)
TEST_ERROR
idx = 42;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)2, find_cb, &idx)<0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)2, find_cb, &idx)<0)
TEST_ERROR
idx = 56;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)3, find_cb, &idx)<0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)3, find_cb, &idx)<0)
TEST_ERROR
PASSED();
@@ -513,7 +541,7 @@ test_insert_split_root(hid_t fapl)
/* Attempt to index non-existant record in level-1 B-tree */
idx = 0;
H5E_BEGIN_TRY {
- ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)(INSERT_SPLIT_ROOT_NREC+2), find_cb, NULL);
+ ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)(INSERT_SPLIT_ROOT_NREC+2), find_cb, NULL);
} H5E_END_TRY;
/* Should fail */
if(ret != FAIL)
@@ -521,17 +549,17 @@ test_insert_split_root(hid_t fapl)
/* Attempt to index existing record in root of level-1 B-tree */
idx = 33;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)33, find_cb, &idx) < 0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)33, find_cb, &idx) < 0)
FAIL_STACK_ERROR
/* Attempt to index existing record in left leaf of level-1 B-tree */
idx = 0;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)0, find_cb, &idx) < 0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)0, find_cb, &idx) < 0)
FAIL_STACK_ERROR
/* Attempt to index existing record in right leaf of level-1 B-tree */
idx = 50;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)50, find_cb, &idx) < 0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)50, find_cb, &idx) < 0)
FAIL_STACK_ERROR
PASSED();
@@ -1304,7 +1332,7 @@ test_insert_make_level2(hid_t fapl)
/* Attempt to index non-existant record in level-2 B-tree */
idx = 0;
H5E_BEGIN_TRY {
- ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)(INSERT_SPLIT_ROOT_NREC * 30), find_cb, NULL);
+ ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)(INSERT_SPLIT_ROOT_NREC * 30), find_cb, NULL);
} H5E_END_TRY;
/* Should fail */
if(ret != FAIL)
@@ -1312,17 +1340,17 @@ test_insert_make_level2(hid_t fapl)
/* Attempt to index existing record in root of level-2 B-tree */
idx = 948;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)948, find_cb, &idx) < 0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)948, find_cb, &idx) < 0)
FAIL_STACK_ERROR
/* Attempt to index existing record in internal node of level-2 B-tree */
idx = 505;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)505, find_cb, &idx) < 0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)505, find_cb, &idx) < 0)
FAIL_STACK_ERROR
/* Attempt to index existing record in leaf of level-2 B-tree */
idx = 555;
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)555, find_cb, &idx) < 0)
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)555, find_cb, &idx) < 0)
FAIL_STACK_ERROR
/* Close file */
@@ -2827,10 +2855,15 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time);
FAIL_STACK_ERROR
} /* end for */
- /* Attempt to index non-existant record in level-4 B-tree */
- idx = 0;
+ /* Attempt to index non-existant record in level-4 B-tree, in increasing & decreasing order */
H5E_BEGIN_TRY {
- ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, (hsize_t)(INSERT_MANY*3), find_cb, NULL);
+ ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)(INSERT_MANY*3), find_cb, NULL);
+ } H5E_END_TRY;
+ /* Should fail */
+ if(ret != FAIL)
+ TEST_ERROR
+ H5E_BEGIN_TRY {
+ ret = H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_DEC, (hsize_t)(INSERT_MANY*3), find_cb, NULL);
} H5E_END_TRY;
/* Should fail */
if(ret != FAIL)
@@ -2842,7 +2875,13 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time);
idx = (hsize_t)(HDrandom() % INSERT_MANY);
/* Attempt to find existant record in root of level-4 B-tree */
- if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, idx, find_cb, &idx) < 0)
+ /* (in increasing order) */
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, idx, find_cb, &idx) < 0)
+ FAIL_STACK_ERROR
+
+ /* Attempt to find existant record in root of level-4 B-tree */
+ /* (in decreasing order) */
+ if(H5B2_index(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_DEC, idx, find_dec_cb, &idx) < 0)
FAIL_STACK_ERROR
} /* end for */