From bc0b7c478f4d4857023baec12763e0fb5cb45222 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Tue, 7 Nov 2006 10:25:06 -0500 Subject: [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) --- src/H5B2.c | 16 ++++++----- src/H5B2private.h | 3 ++- src/H5Gdense.c | 4 +-- test/btree2.c | 79 +++++++++++++++++++++++++++++++++++++++++-------------- 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 */ -- cgit v0.12