diff options
| -rw-r--r-- | src/H5B2.c | 176 | ||||
| -rw-r--r-- | src/H5B2private.h | 18 | ||||
| -rw-r--r-- | test/btree2.c | 52 |
3 files changed, 239 insertions, 7 deletions
@@ -69,6 +69,9 @@ static herr_t H5B2_split2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *internal, unsigned idx); static herr_t H5B2_redistribute3(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *internal, unsigned idx); +static herr_t H5B2_iterate_node(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, + unsigned depth, const H5B2_node_ptr_t *curr_node, H5B2_operator_t op, + void *op_data); /* Package variables */ @@ -1630,3 +1633,176 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* H5B2_create_internal() */ + +/*------------------------------------------------------------------------- + * Function: H5B2_iterate_node + * + * Purpose: Iterate over all the records from a B-tree node, in "in-order" + * order, making a callback for each record. + * + * If the callback returns non-zero, the iteration breaks out + * without finishing all the records. + * + * Return: Value from callback, non-negative on success, negative on error + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Feb 11 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5B2_iterate_node(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, unsigned depth, + const H5B2_node_ptr_t *curr_node, H5B2_operator_t op, void *op_data) +{ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ + const H5AC_class_t *curr_node_class=NULL; /* Pointer to current node's class info */ + void *node=NULL; /* Pointers to current node */ + uint8_t *native; /* Pointers to node's native records */ + H5B2_node_ptr_t *node_ptrs=NULL; /* Pointers to node's node pointers */ + unsigned u; /* Local index */ + herr_t ret_value = H5B2_ITER_CONT; + + FUNC_ENTER_NOAPI(H5B2_iterate_node, FAIL) + + /* Check arguments. */ + HDassert(f); + HDassert(bt2_shared); + HDassert(curr_node); + HDassert(op); + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2_shared); + HDassert(shared); + + if(depth>0) { + H5B2_internal_t *internal; /* Pointer to internal node */ + + /* Lock the current B-tree node */ + if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node->addr, &(curr_node->node_nrec), shared, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node") + + /* Set up information about current node */ + curr_node_class = H5AC_BT2_INT; + node = internal; + native = internal->int_native; + node_ptrs = internal->node_ptrs; + } /* end if */ + else { + H5B2_leaf_t *leaf; /* Pointer to leaf node */ + + /* Lock the current B-tree node */ + if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, curr_node->addr, &(curr_node->node_nrec), shared, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node") + + /* Set up information about current node */ + curr_node_class = H5AC_BT2_LEAF; + node = leaf; + native = leaf->leaf_native; + } /* end else */ + + /* Iterate through records */ + for(u=0, ret_value; u<curr_node->node_nrec && !ret_value; u++) { + /* Descend into child node, if current node is an internal node */ + if(depth>0) { + if((ret_value = H5B2_iterate_node(f,dxpl_id,bt2_shared,depth-1,&(node_ptrs[u]),op,op_data))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "node iteration failed") + } /* end if */ + + /* Make callback for current record */ + if ((ret_value = (op)(H5B2_NAT_NREC(native,shared,u), op_data)) <0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "iterator function failed") + } /* end for */ + + /* Descend into last child node, if current node is an internal node */ + if(depth>0) { + if((ret_value = H5B2_iterate_node(f,dxpl_id,bt2_shared,depth-1,&(node_ptrs[u]),op,op_data))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "node iteration failed") + } /* end if */ + +done: + /* Unlock current node */ + if(node) + if (H5AC_unprotect(f, dxpl_id, curr_node_class, curr_node->addr, node, H5AC__NO_FLAGS_SET) < 0) + HDONE_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree node") + + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_iterate_node() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_iterate + * + * Purpose: Iterate over all the records in the B-tree, in "in-order" + * order, making a callback for each record. + * + * If the callback returns non-zero, the iteration breaks out + * without finishing all the records. + * + * Return: Value from callback, non-negative on success, negative on error + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Feb 11 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5B2_iterate(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, + H5B2_operator_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 */ + hbool_t incr_rc=FALSE; /* Flag to indicate that we've incremented the B-tree's shared info reference count */ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ + H5B2_node_ptr_t root_ptr; /* Node pointer info for root node */ + unsigned depth; /* Current depth of the tree */ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI(H5B2_iterate, FAIL) + + /* Check arguments. */ + HDassert(f); + HDassert(type); + HDassert(H5F_addr_defined(addr)); + HDassert(op); + + /* 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_CANTLOAD, FAIL, "unable to load B-tree header") + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2->shared); + HDassert(shared); + + /* 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; + + /* Make copy of the root node pointer */ + root_ptr = bt2->root; + + /* Current depth of the tree */ + depth=bt2->depth; + + /* Release header */ + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree header info") + bt2=NULL; + + /* Iterate through records */ + if(root_ptr.node_nrec>0) { + /* Iterate through nodes */ + if((ret_value=H5B2_iterate_node(f,dxpl_id,bt2_shared,depth,&root_ptr,op,op_data))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "node iteration failed") + } /* 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); + + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_iterate() */ + diff --git a/src/H5B2private.h b/src/H5B2private.h index 51b5c2d..457d12a 100644 --- a/src/H5B2private.h +++ b/src/H5B2private.h @@ -36,13 +36,17 @@ /* Library Private Macros */ /**************************/ -/* - * Feature: Define this constant if you want to check B-tree consistency - * after each B-tree operation. Note that this slows down the - * library considerably! Debugging the B-tree depends on assert() - * being enabled. +/* Define return values from operator callback function for H5B2_iterate */ +/* (Actually, any positive value will cause the iterator to stop and pass back + * that positive value to the function that called the iterator) */ -/* #define H5B2_DEBUG */ +#define H5B2_ITER_ERROR (-1) +#define H5B2_ITER_CONT (0) +#define H5B2_ITER_STOP (1) + +/* Define the operator callback function pointer for H5B2_iterate() */ +typedef int (*H5B2_operator_t)(const void *record, void *op_data); + /****************************/ /* Library Private Typedefs */ @@ -88,6 +92,8 @@ H5_DLL herr_t H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t *addr_p); H5_DLL herr_t H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, void *udata); +H5_DLL herr_t H5B2_iterate(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, + haddr_t addr, H5B2_operator_t op, void *op_data); #endif /* _H5B2private_H */ diff --git a/test/btree2.c b/test/btree2.c index 365dacf..9593dc9 100644 --- a/test/btree2.c +++ b/test/btree2.c @@ -37,6 +37,36 @@ const char *FILENAME[] = { /*------------------------------------------------------------------------- + * Function: iter_cb + * + * Purpose: v2 B-tree iterator callback + * + * Return: Success: 0 + * + * Failure: 1 + * + * Programmer: Quincey Koziol + * Wednesday, February 16, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static int +iter_cb(const void *_record, void *_op_data) +{ + const hsize_t *record = (const hsize_t *)_record; + hsize_t *idx = (hsize_t *)_op_data; + + if(*record != *idx) + return(H5B2_ITER_ERROR); + + (*idx)++; + return(H5B2_ITER_CONT); +} + + +/*------------------------------------------------------------------------- * Function: test_insert_basic * * Purpose: Basic tests for the B-tree v2 code @@ -59,6 +89,7 @@ test_insert_basic(hid_t fapl) char filename[1024]; H5F_t *f=NULL; hsize_t record; /* Record to insert into tree */ + hsize_t idx; /* Index within B-tree, for iterator */ haddr_t bt2_addr; /* Address of B-tree created */ h5_fixname(FILENAME[0], fapl, filename, sizeof filename); @@ -83,6 +114,16 @@ test_insert_basic(hid_t fapl) } PASSED(); + /* Attempt to iterate over a B-tree with no records */ + idx = 0; + if(H5B2_iterate(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, iter_cb, &idx)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + /* Make certain that the index hasn't changed */ + if(idx != 0) TEST_ERROR; + /* * Test inserting record into v2 B-tree */ @@ -163,6 +204,7 @@ test_insert_split_root(hid_t fapl) char filename[1024]; H5F_t *f=NULL; hsize_t record; /* Record to insert into tree */ + hsize_t idx; /* Index within B-tree, for iterator */ haddr_t bt2_addr; /* Address of B-tree created */ unsigned u; /* Local index variable */ @@ -192,7 +234,7 @@ test_insert_split_root(hid_t fapl) TESTING("B-tree many - split root"); for(u=0; u<INSERT_SPLIT_ROOT_NREC; u++) { - record=u+10; + record=u+2; if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { H5_FAILED(); H5Eprint_stack(H5E_DEFAULT, stdout); @@ -212,6 +254,14 @@ test_insert_split_root(hid_t fapl) goto error; } + /* Iterate over B-tree to check records have been inserted correctly */ + idx = 0; + if(H5B2_iterate(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, iter_cb, &idx)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + PASSED(); if (H5Fclose(file)<0) TEST_ERROR; |