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

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