From 4bcd59d351122d16ec1214c4257bc6020ffe5e0b Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Mon, 7 Mar 2005 15:12:57 -0500 Subject: [svn-r10159] Purpose: Bug fix Description: Corrected errors in record removal code to handle removing records in higher nodes in the B-tree. Platforms tested: FreebSD 4.11 (sleipnir) Solaris 2.9 (shanti) --- src/H5B2.c | 67 ++++++++++-------- test/btree2.c | 213 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 249 insertions(+), 31 deletions(-) diff --git a/src/H5B2.c b/src/H5B2.c index 22894f2..60f170d 100644 --- a/src/H5B2.c +++ b/src/H5B2.c @@ -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