diff options
| -rw-r--r-- | src/H5B2.c | 67 | ||||
| -rw-r--r-- | test/btree2.c | 213 |
2 files changed, 249 insertions, 31 deletions
@@ -48,7 +48,7 @@ #define H5B2_NUM_LEAF_REC(n,r) (((n)-H5B2_OVERHEAD_SIZE)/(r)) /* Uncomment this macro to enable extra sanity checking */ -/* #define H5B2_DEBUG */ +#define H5B2_DEBUG /* Local typedefs */ @@ -77,15 +77,15 @@ static herr_t H5B2_merge2(H5F_t *f, hid_t dxpl_id, unsigned depth, static herr_t H5B2_merge3(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *curr_node_ptr, H5AC_info_t *parent_cache_info, H5B2_internal_t *internal, unsigned idx); -static herr_t H5B2_swap_child(H5F_t *f, hid_t dxpl_id, unsigned depth, - H5B2_internal_t *internal, unsigned idx); +static herr_t H5B2_swap_leaf(H5F_t *f, hid_t dxpl_id, unsigned depth, + H5B2_internal_t *internal, unsigned idx, void *swap_loc); static herr_t H5B2_insert_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, unsigned depth, H5AC_info_t *parent_cache_info, H5B2_node_ptr_t *curr_node_ptr, void *udata); static herr_t H5B2_insert_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_t *curr_node_ptr, void *udata); static herr_t H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, - hbool_t *depth_decreased, unsigned depth, H5AC_info_t *parent_cache_info, + hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info, H5B2_node_ptr_t *curr_node_ptr, void *udata); static herr_t H5B2_remove_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_t *curr_node_ptr, void *udata); @@ -2207,9 +2207,9 @@ done: /*------------------------------------------------------------------------- - * Function: H5B2_swap_child + * Function: H5B2_swap_leaf * - * Purpose: Swap a record in a node with a record in a child node + * Purpose: Swap a record in a node with a record in a leaf node * * Return: Success: Non-negative * @@ -2222,8 +2222,8 @@ done: *------------------------------------------------------------------------- */ static herr_t -H5B2_swap_child(H5F_t *f, hid_t dxpl_id, unsigned depth, - H5B2_internal_t *internal, unsigned idx) +H5B2_swap_leaf(H5F_t *f, hid_t dxpl_id, unsigned depth, + H5B2_internal_t *internal, unsigned idx, void *swap_loc) { const H5AC_class_t *child_class; /* Pointer to child node's class info */ haddr_t child_addr; /* Address of child node */ @@ -2233,10 +2233,11 @@ H5B2_swap_child(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_shared_t *shared; /* B-tree's shared info */ herr_t ret_value=SUCCEED; /* Return value */ - FUNC_ENTER_NOAPI_NOINIT(H5B2_swap_child) + FUNC_ENTER_NOAPI_NOINIT(H5B2_swap_leaf) HDassert(f); HDassert(internal); + HDassert(idx <= internal->nrec); /* Get the pointer to the shared B-tree info */ shared=H5RC_GET_OBJ(internal->shared); @@ -2248,10 +2249,8 @@ H5B2_swap_child(H5F_t *f, hid_t dxpl_id, unsigned depth, /* Setup information for unlocking child node */ child_class = H5AC_BT2_INT; - child_addr = child_internal->node_ptrs[idx].addr; + child_addr = internal->node_ptrs[idx].addr; -HDfprintf(stderr,"%s: Swapping with internal node in B-tree, untested!\n",FUNC); -HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") /* Lock B-tree child nodes */ if (NULL == (child_internal = H5AC_protect(f, dxpl_id, child_class, child_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") @@ -2286,8 +2285,8 @@ HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") /* Swap records (use disk page as temporary buffer) */ HDmemcpy(shared->page, H5B2_NAT_NREC(child_native,shared,0), shared->type->nrec_size); - HDmemcpy(H5B2_NAT_NREC(child_native,shared,0), H5B2_INT_NREC(internal,shared,idx-1), shared->type->nrec_size); - HDmemcpy(H5B2_INT_NREC(internal,shared,idx-1), shared->page, shared->type->nrec_size); + HDmemcpy(H5B2_NAT_NREC(child_native,shared,0), swap_loc, shared->type->nrec_size); + HDmemcpy(swap_loc, shared->page, shared->type->nrec_size); /* Mark parent as dirty */ internal->cache_info.is_dirty = TRUE; @@ -2306,7 +2305,7 @@ HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") done: FUNC_LEAVE_NOAPI(ret_value); -} /* end H5B2_swap_child */ +} /* end H5B2_swap_leaf */ /*------------------------------------------------------------------------- @@ -3374,8 +3373,8 @@ done: */ static herr_t H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, - hbool_t *depth_decreased, unsigned depth, H5AC_info_t *parent_cache_info, - H5B2_node_ptr_t *curr_node_ptr, void *udata) + hbool_t *depth_decreased, void *swap_loc, unsigned depth, + H5AC_info_t *parent_cache_info, H5B2_node_ptr_t *curr_node_ptr, void *udata) { H5AC_info_t *new_cache_info; /* Pointer to new cache info */ H5B2_node_ptr_t *new_node_ptr; /* Pointer to new node pointer */ @@ -3450,9 +3449,13 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, unsigned retries; /* Number of times to attempt redistribution */ /* Locate node pointer for child */ - cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx); - if(cmp >= 0) - idx++; + if(swap_loc) + idx = 0; + else { + cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx); + if(cmp >= 0) + idx++; + } /* end else */ /* Set the number of redistribution retries */ /* This takes care of the case where a B-tree node needs to be @@ -3498,10 +3501,14 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, } /* end else */ /* Locate node pointer for child (after merge/redistribute) */ + if(swap_loc) + idx = 0; + else { /* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */ - cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx); - if(cmp >= 0) - idx++; + cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx); + if(cmp >= 0) + idx++; + } /* end else */ /* Decrement the number of redistribution retries left */ retries--; @@ -3509,11 +3516,15 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, /* Handle deleting a record from an internal node */ if(cmp==0) { - /* Swap record to delete with record from child */ - if(H5B2_swap_child(f,dxpl_id,depth,internal,idx) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTSWAP, FAIL, "Can't swap records in B-tree") + HDassert(swap_loc==NULL); + swap_loc = H5B2_INT_NREC(internal,shared,idx-1); } /* end if */ + /* Swap record to delete with record from leaf, if we are the last internal node */ + if(swap_loc && depth==1) + if(H5B2_swap_leaf(f,dxpl_id,depth,internal,idx,swap_loc) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTSWAP, FAIL, "Can't swap records in B-tree") + /* Set pointers for advancing to child node */ new_cache_info = &internal->cache_info; new_node_ptr = &internal->node_ptrs[idx]; @@ -3521,7 +3532,7 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, /* Attempt to remove node */ if(depth>1) { - if(H5B2_remove_internal(f,dxpl_id,bt2_shared,depth_decreased,depth-1,new_cache_info,new_node_ptr,udata)<0) + if(H5B2_remove_internal(f,dxpl_id,bt2_shared,depth_decreased, swap_loc, depth-1,new_cache_info,new_node_ptr,udata)<0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree internal node") } /* end if */ else { @@ -3593,7 +3604,7 @@ H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, if(bt2->depth>0) { hbool_t depth_decreased=FALSE; /* Flag to indicate whether the depth of the B-tree decreased */ - if(H5B2_remove_internal(f,dxpl_id,bt2->shared, &depth_decreased, bt2->depth,&(bt2->cache_info),&bt2->root,udata)<0) + if(H5B2_remove_internal(f,dxpl_id,bt2->shared, &depth_decreased, NULL, bt2->depth,&(bt2->cache_info),&bt2->root,udata)<0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree internal node") bt2->depth -= depth_decreased; diff --git a/test/btree2.c b/test/btree2.c index 86ed020..fb7214c 100644 --- a/test/btree2.c +++ b/test/btree2.c @@ -3616,7 +3616,7 @@ test_remove_level1_collapse(hid_t fapl) /* Attempt to remove records from B-tree to force a single leaf for the B-tree */ TESTING("B-tree remove: collapse level-1 B-tree back to level-0"); - for(u=0; u < 29; u++) { + for(u=0; u < 30; u++) { record = INSERT_SPLIT_ROOT_NREC - (u+1); if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { H5_FAILED(); @@ -3653,6 +3653,212 @@ error: /*------------------------------------------------------------------------- + * Function: test_remove_level2_promote + * + * Purpose: Basic tests for the B-tree v2 code + * + * Return: Success: 0 + * + * Failure: 1 + * + * Programmer: Quincey Koziol + * Friday, March 4, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static int +test_remove_level2_promote(hid_t fapl) +{ + hid_t file=-1; + char filename[1024]; + H5F_t *f=NULL; + hsize_t record; /* Record to insert into tree */ + hsize_t nrec; /* Number of records in B-tree */ + haddr_t bt2_addr; /* Address of B-tree created */ + haddr_t root_addr; /* Address of root of B-tree created */ + unsigned u; /* Local index variable */ + + h5_fixname(FILENAME[0], fapl, filename, sizeof filename); + + /* Create the file to work on */ + if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR; + + /* Get a pointer to the internal file object */ + if (NULL==(f=H5I_object(file))) { + H5Eprint_stack(H5E_DEFAULT, stdout); + TEST_ERROR; + } + + /* + * Test v2 B-tree creation + */ + if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + + /* Create level-2 B-tree with 3 internal nodes */ + for(u=0; u<INSERT_SPLIT_ROOT_NREC*21; u++) { + record=u; + if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + } + + /* Query the number of records in the B-tree */ + if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the # of records is correct */ + if(nrec != (INSERT_SPLIT_ROOT_NREC*21)) TEST_ERROR; + + /* Query the address of the root node in the B-tree */ + if (H5B2_get_root_addr(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &root_addr)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the address of the root node is defined */ + if(!H5F_addr_defined(root_addr)) TEST_ERROR; + + /* Attempt to remove record from right internal node of a level-2 B-tree to force promotion */ + TESTING("B-tree remove: promote from right internal of level-2 B-tree"); + record = 1632; + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the record value is correct */ + if(record != 1632) TEST_ERROR; + + /* Query the number of records in the B-tree */ + if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the # of records is correct */ + if(nrec != (INSERT_SPLIT_ROOT_NREC*21)-1) TEST_ERROR; + + PASSED(); + + /* Attempt to remove record from left internal node of a level-2 B-tree to force promotion */ + TESTING("B-tree remove: promote from left internal of level-2 B-tree"); + record = 1117; + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the record value is correct */ + if(record != 1117) TEST_ERROR; + + /* Query the number of records in the B-tree */ + if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the # of records is correct */ + if(nrec != (INSERT_SPLIT_ROOT_NREC*21)-2) TEST_ERROR; + + PASSED(); + + /* Attempt to remove record from middle internal node of a level-2 B-tree to force promotion */ + TESTING("B-tree remove: promote from middle internal of level-2 B-tree"); + record = 1246; + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the record value is correct */ + if(record != 1246) TEST_ERROR; + + /* Query the number of records in the B-tree */ + if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the # of records is correct */ + if(nrec != (INSERT_SPLIT_ROOT_NREC*21)-3) TEST_ERROR; + + PASSED(); + + /* Attempt to remove record from root node of a level-2 B-tree to force promotion */ + TESTING("B-tree remove: promote from root of level-2 B-tree"); + record = 1074; + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the record value is correct */ + if(record != 1074) TEST_ERROR; + + /* Query the number of records in the B-tree */ + if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the # of records is correct */ + if(nrec != (INSERT_SPLIT_ROOT_NREC*21)-4) TEST_ERROR; + + record = 558; + if(H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the record value is correct */ + if(record != 558) TEST_ERROR; + + /* Query the number of records in the B-tree */ + if (H5B2_get_nrec(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &nrec)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Make certain that the # of records is correct */ + if(nrec != (INSERT_SPLIT_ROOT_NREC*21)-5) TEST_ERROR; + + PASSED(); + + if (H5Fclose(file)<0) TEST_ERROR; + + return 0; + +error: + H5E_BEGIN_TRY { + H5Fclose(file); + } H5E_END_TRY; + return 1; +} /* test_remove_level2_promote() */ + + +/*------------------------------------------------------------------------- * Function: main * * Purpose: Test the B-tree v2 code @@ -3680,7 +3886,7 @@ main(void) /* Test B-tree record insertion */ /* Iteration, find & index routines tested in these routines as well */ -#ifndef QAK +#ifdef QAK nerrors += test_insert_basic(fapl); nerrors += test_insert_split_root(fapl); nerrors += test_insert_level1_2leaf_redistrib(fapl); @@ -3713,13 +3919,14 @@ HDfprintf(stderr,"Uncomment tests!\n"); nerrors += test_remove_level1_promote_2leaf_merge(fapl); nerrors += test_remove_level1_promote_3leaf_merge(fapl); nerrors += test_remove_level1_collapse(fapl); + nerrors += test_remove_level2_promote(fapl); #else /* QAK */ HDfprintf(stderr,"Uncomment tests!\n"); #endif /* QAK */ if (nerrors) goto error; puts("All v2 B-tree tests passed."); -#ifndef QAK +#ifdef QAK h5_cleanup(FILENAME, fapl); #else /* QAK */ HDfprintf(stderr,"Uncomment cleanup!\n"); |