From 84ffc9d1c1318ae3f31becddb279179507faf0e5 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Thu, 3 Mar 2005 16:39:57 -0500 Subject: [svn-r10135] Purpose: Bug fix & new feature Description: Fix problem with inserting existing keys into B-tree corrupting record counts along the path to the failed insertion. Add more support for removing records, it's now handling removing records from leaves of level-1 B-trees. Platforms tested: FreeBSD 4.11 (sleipnir) w/parallel Solaris 2.9 (shanti) --- src/H5B2.c | 980 +++++++++++++++++++++++++++++++++++++++++----------------- test/btree2.c | 349 ++++++++++++++++++++- 2 files changed, 1052 insertions(+), 277 deletions(-) diff --git a/src/H5B2.c b/src/H5B2.c index 6dbb52c..04109ad 100644 --- a/src/H5B2.c +++ b/src/H5B2.c @@ -71,6 +71,11 @@ 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_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_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); @@ -1798,301 +1803,298 @@ done: /*------------------------------------------------------------------------- - * Function: H5B2_insert + * Function: H5B2_insert_leaf * - * Purpose: Adds a new record to the B-tree. + * Purpose: Adds a new record to a B-tree leaf node. * * Return: Non-negative on success/Negative on failure * * Programmer: Quincey Koziol * koziol@ncsa.uiuc.edu - * Feb 2 2005 + * Mar 3 2005 * *------------------------------------------------------------------------- */ -herr_t -H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, - 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) { - 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_leaf_t *leaf; /* Pointer to leaf node */ H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ - H5B2_node_ptr_t leaf_ptr; /* Node pointer info for leaf node */ - H5B2_leaf_t *leaf=NULL; /* Pointer to leaf node */ - unsigned leaf_nrec; /* Number of records in leaf to modify */ int cmp; /* Comparison value of records */ unsigned idx; /* Location of record which matches key */ herr_t ret_value = SUCCEED; - FUNC_ENTER_NOAPI(H5B2_insert, FAIL) + FUNC_ENTER_NOAPI(H5B2_insert_leaf, FAIL) /* Check arguments. */ HDassert(f); - HDassert(type); - HDassert(H5F_addr_defined(addr)); + HDassert(bt2_shared); + HDassert(curr_node_ptr); + HDassert(H5F_addr_defined(curr_node_ptr->addr)); - /* 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_CANTPROTECT, FAIL, "unable to load B-tree header") + /* Lock current B-tree node */ + if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node") /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(bt2->shared); + 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; - - /* Check if the root node is allocated yet */ - if(!H5F_addr_defined(bt2->root.addr)) { - /* Create root node as leaf node in B-tree */ - if(H5B2_create_leaf(f, dxpl_id, bt2_shared, &(bt2->root))<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create root node") - - /* Mark B-tree header as dirty, since we updated the address of the root node */ - bt2->cache_info.is_dirty = TRUE; - } /* end if */ - /* Check if we need to split the root node */ - else if((bt2->depth==0 && bt2->root.node_nrec==shared->split_leaf_nrec) || - (bt2->depth>0 && bt2->root.node_nrec==shared->split_int_nrec)) { - /* Split root node */ - if(H5B2_split_root(f, dxpl_id, bt2, bt2_shared)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node") - } /* end if */ - - /* Check for non-trivial B-tree */ - if(bt2->depth>0) { - H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ - H5AC_info_t *parent_cache_info; /* Parent node's cache info */ - haddr_t parent_addr; /* Address of parent which contain's node pointer to current node */ - void *parent_ptr; /* Pointer to parent structure in memory */ - H5AC_info_t *curr_cache_info=NULL; /* Current node's cache info */ - H5B2_node_ptr_t *curr_node_ptr; /* Pointer to node pointer info for current node (in parent node) */ - haddr_t curr_addr=HADDR_UNDEF; /* Address of current node */ - void *curr_ptr=NULL; /* Pointer to current structure in memory */ - H5B2_node_ptr_t *child_node_ptr=NULL; /* Pointer to node pointer info for child node */ - unsigned depth; /* Depth of current node */ - - /* Track the depth of current node (leaves are depth 0) */ - depth=bt2->depth; - - /* Set initial "parent" information to the B-tree header */ - parent_cache_info=&(bt2->cache_info); - parent_addr=addr; - parent_ptr=bt2; + /* Must have a leaf node with enough space to insert a record now */ + HDassert(curr_node_ptr->node_nrec < shared->split_leaf_nrec); - /* Set initial node pointer for "current" node */ - curr_node_ptr=&(bt2->root); + /* Sanity check number of records */ + HDassert(curr_node_ptr->all_nrec == curr_node_ptr->node_nrec); + HDassert(leaf->nrec == curr_node_ptr->node_nrec); - /* Find correct leaf to insert node into */ - while(depth>0) { - unsigned retries; + /* Check for inserting into empty leaf */ + if(leaf->nrec==0) + idx=0; + else { + /* Find correct location to insert this record */ + if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0) + HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") + if(cmp > 0) + idx++; - /* Lock B-tree current node */ - if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") + /* Make room for new record */ + if((unsigned)idxnrec) + HDmemmove(H5B2_LEAF_NREC(leaf,shared,idx+1),H5B2_LEAF_NREC(leaf,shared,idx),shared->type->nrec_size*(leaf->nrec-idx)); + } /* end else */ -#ifdef H5B2_DEBUG - H5B2_assert_internal((hsize_t)0,shared,internal); -#endif /* H5B2_DEBUG */ + /* Make callback to store record in native form */ + if((shared->type->store)(H5B2_LEAF_NREC(leaf,shared,idx),udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node") - /* Set information for current (root) node */ - curr_cache_info=&(internal->cache_info); - curr_addr=curr_node_ptr->addr; - curr_ptr=internal; + /* Update record count for node pointer to current node */ + curr_node_ptr->all_nrec++; + curr_node_ptr->node_nrec++; - /* Locate node pointer for child */ - if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0) - HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") - if(cmp>0) - idx++; + /* Update record count for current node */ + leaf->nrec++; - /* Get node pointer for child */ - child_node_ptr=&(internal->node_ptrs[idx]); + /* Mark node as dirty */ + leaf->cache_info.is_dirty = TRUE; - /* Set the number of redistribution retries */ - /* This takes care of the case where a B-tree node needs to be - * redistributed, but redistributing the node causes the index - * for insertion to move to another node, which also needs to be - * redistributed. Now, we loop trying to redistribute and then - * eventually force a split */ - retries = 2; +done: + /* Release the B-tree leaf node */ + if (leaf && H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) + HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release leaf B-tree node") - /* Preemptively split/redistribute a node we will enter */ - while((depth==1 && child_node_ptr->node_nrec==shared->split_leaf_nrec) || - (depth>1 && child_node_ptr->node_nrec==shared->split_int_nrec)) { - /* Attempt to redistribute records among children */ - if(idx==0) { /* Left-most child */ - if(retries>0 && ((depth==1 && internal->node_ptrs[idx+1].node_nrecsplit_leaf_nrec) || - (depth>1 && internal->node_ptrs[idx+1].node_nrecsplit_int_nrec))) { - if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") - } /* end if */ - else { - if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)idx)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node") - } /* end else */ - } /* end if */ - else if((unsigned)idx==internal->nrec) { /* Right-most child */ - if(retries>0 && ((depth==1 && internal->node_ptrs[idx-1].node_nrecsplit_leaf_nrec) || - (depth>1 && internal->node_ptrs[idx-1].node_nrecsplit_int_nrec))) { - if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") - } /* end if */ - else { - if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)(idx-1))<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node") - } /* end else */ - } /* end if */ - else { /* Middle child */ - if(retries>0 && ((depth==1 && - ((internal->node_ptrs[idx+1].node_nrecsplit_leaf_nrec) || - (internal->node_ptrs[idx-1].node_nrecsplit_leaf_nrec))) || - (depth>1 && - ((internal->node_ptrs[idx+1].node_nrecsplit_int_nrec) || - (internal->node_ptrs[idx-1].node_nrecsplit_int_nrec))))) { - if(H5B2_redistribute3(f,dxpl_id,depth,internal,(unsigned)idx)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") - } /* end if */ - else { - if(H5B2_split3(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)idx)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node") - } /* end else */ - } /* end else */ + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_insert_leaf() */ - /* Locate node pointer for child (after split redistribute) */ -/* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */ - if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0) - HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") - if(cmp > 0) - idx++; + +/*------------------------------------------------------------------------- + * Function: H5B2_insert_internal + * + * Purpose: Adds a new record to a B-tree node. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Mar 2 2005 + * + *------------------------------------------------------------------------- + */ +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) +{ + H5B2_internal_t *internal; /* Pointer to internal node */ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ + unsigned idx; /* Location of record which matches key */ + herr_t ret_value = SUCCEED; - /* Update child_node_ptr (to reflect change in location from split/redistribution) */ - child_node_ptr=&(internal->node_ptrs[idx]); + FUNC_ENTER_NOAPI(H5B2_insert_internal, FAIL) - /* Decrement the number of redistribution retries left */ - retries--; - } /* end if */ + /* Check arguments. */ + HDassert(f); + HDassert(bt2_shared); + HDassert(depth>0); + HDassert(parent_cache_info); + HDassert(curr_node_ptr); + HDassert(H5F_addr_defined(curr_node_ptr->addr)); - /* Update record count (in parent) */ - curr_node_ptr->all_nrec++; + /* Lock current B-tree node */ + if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") - /* Mark parent node as dirty */ - parent_cache_info->is_dirty = TRUE; + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2_shared); + HDassert(shared); -#ifdef H5B2_DEBUG - if(parent_cache_info->type==H5AC_BT2_INT) - H5B2_assert_internal((hsize_t)0,shared,parent_ptr); -#endif /* H5B2_DEBUG */ +/* Split or redistribute child node pointers, if necessary */ + { + int cmp; /* Comparison value of records */ + unsigned retries; /* Number of times to attempt redistribution */ - /* Unlock parent node (possibly the B-tree header) */ - if (H5AC_unprotect(f, dxpl_id, parent_cache_info->type, parent_addr, parent_ptr, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree info") + /* Locate node pointer for child */ + if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0) + HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") + if(cmp>0) + idx++; - /* Transition "current" info into "parent" info */ - parent_cache_info = curr_cache_info; - parent_addr = curr_addr; - parent_ptr = curr_ptr; + /* Set the number of redistribution retries */ + /* This takes care of the case where a B-tree node needs to be + * redistributed, but redistributing the node causes the index + * for insertion to move to another node, which also needs to be + * redistributed. Now, we loop trying to redistribute and then + * eventually force a split */ + retries = 2; + + /* Preemptively split/redistribute a node we will enter */ + while((depth==1 && internal->node_ptrs[idx].node_nrec==shared->split_leaf_nrec) || + (depth>1 && internal->node_ptrs[idx].node_nrec==shared->split_int_nrec)) { + /* Attempt to redistribute records among children */ + if(idx==0) { /* Left-most child */ + if(retries>0 && ((depth==1 && internal->node_ptrs[idx+1].node_nrecsplit_leaf_nrec) || + (depth>1 && internal->node_ptrs[idx+1].node_nrecsplit_int_nrec))) { + if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { + if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)idx)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node") + } /* end else */ + } /* end if */ + else if((unsigned)idx==internal->nrec) { /* Right-most child */ + if(retries>0 && ((depth==1 && internal->node_ptrs[idx-1].node_nrecsplit_leaf_nrec) || + (depth>1 && internal->node_ptrs[idx-1].node_nrecsplit_int_nrec))) { + if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { + if(H5B2_split2(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)(idx-1))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node") + } /* end else */ + } /* end if */ + else { /* Middle child */ + if(retries>0 && ((depth==1 && + ((internal->node_ptrs[idx+1].node_nrecsplit_leaf_nrec) || + (internal->node_ptrs[idx-1].node_nrecsplit_leaf_nrec))) || + (depth>1 && + ((internal->node_ptrs[idx+1].node_nrecsplit_int_nrec) || + (internal->node_ptrs[idx-1].node_nrecsplit_int_nrec))))) { + if(H5B2_redistribute3(f,dxpl_id,depth,internal,(unsigned)idx)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { + if(H5B2_split3(f,dxpl_id,depth,curr_node_ptr,parent_cache_info,internal,(unsigned)idx)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node") + } /* end else */ + } /* end else */ - /* Transition "child" node pointer to "current" node pointer */ - curr_node_ptr = child_node_ptr; + /* Locate node pointer for child (after split/redistribute) */ +/* Actually, this can be easily updated (for 2-node redistrib.) and shouldn't require re-searching */ + if((cmp=H5B2_locate_record(shared->type,internal->nrec,shared->nat_off,internal->int_native,udata,&idx)) == 0) + HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") + if(cmp > 0) + idx++; - /* Decrement depth of current node */ - depth--; + /* Decrement the number of redistribution retries left */ + retries--; } /* end while */ + } /* end block */ - /* Update record count for leaf (in current node) */ - HDassert(curr_node_ptr); - curr_node_ptr->all_nrec++; - curr_node_ptr->node_nrec++; - - /* Mark parent node as dirty */ - curr_cache_info->is_dirty = TRUE; - - /* Copy node pointer info for leaf */ - leaf_ptr = *curr_node_ptr; - -#ifdef H5B2_DEBUG - if(curr_cache_info->type==H5AC_BT2_INT) - H5B2_assert_internal((hsize_t)0,shared,curr_ptr); -#endif /* H5B2_DEBUG */ - - /* Release current node */ - if (H5AC_unprotect(f, dxpl_id, curr_cache_info->type, curr_addr, curr_ptr, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node") + /* Attempt to insert node */ + if(depth>1) { + if(H5B2_insert_internal(f,dxpl_id,bt2_shared,depth-1,&internal->cache_info,&internal->node_ptrs[idx],udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node") } /* end if */ else { - /* Update record count for root node */ - bt2->root.all_nrec++; - bt2->root.node_nrec++; + if(H5B2_insert_leaf(f,dxpl_id,bt2_shared,&internal->node_ptrs[idx],udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node") + } /* end else */ - /* Mark parent node as dirty */ - bt2->cache_info.is_dirty = TRUE; + /* Update record count for node pointer to current node */ + curr_node_ptr->all_nrec++; - /* Copy node pointer info for leaf */ - leaf_ptr = bt2->root; + /* Mark node as dirty */ + internal->cache_info.is_dirty = TRUE; - /* Release parent node */ - if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info") - bt2=NULL; - } /* end else */ +done: + /* Release the B-tree internal node */ + if (internal && H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0) + HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release internal B-tree node") - /* Get the actual # of records in leaf */ - leaf_nrec = leaf_ptr.node_nrec - 1; + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_insert_internal() */ - /* Must have a leaf node with enough space to insert a record now */ - HDassert(H5F_addr_defined(leaf_ptr.addr)); - HDassert(leaf_nrec < shared->split_leaf_nrec); + +/*------------------------------------------------------------------------- + * Function: H5B2_insert + * + * Purpose: Adds a new record to the B-tree. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, + void *udata) +{ + H5B2_t *bt2=NULL; /* Pointer to the B-tree header */ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ + herr_t ret_value = SUCCEED; - /* Look up the B-tree leaf node */ - if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, &leaf_nrec, bt2_shared, H5AC_WRITE))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node") + FUNC_ENTER_NOAPI(H5B2_insert, FAIL) - /* Sanity check number of records */ - HDassert(leaf_ptr.all_nrec == leaf_ptr.node_nrec); - HDassert(leaf->nrec == leaf_nrec); + /* Check arguments. */ + HDassert(f); + HDassert(type); + HDassert(H5F_addr_defined(addr)); - /* Check for inserting into empty leaf */ - if(leaf->nrec==0) - idx=0; - else { - /* Find correct location to insert this record */ - if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0) - HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") - if(cmp > 0) - idx++; + /* 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_CANTPROTECT, FAIL, "unable to load B-tree header") - /* Make room for new record */ - if((unsigned)idxnrec) - HDmemmove(H5B2_LEAF_NREC(leaf,shared,idx+1),H5B2_LEAF_NREC(leaf,shared,idx),shared->type->nrec_size*(leaf->nrec-idx)); - } /* end else */ + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2->shared); + HDassert(shared); - /* Make callback to store record in native form */ - if((shared->type->store)(H5B2_LEAF_NREC(leaf,shared,idx),udata)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node") + /* Check if the root node is allocated yet */ + if(!H5F_addr_defined(bt2->root.addr)) { + /* Create root node as leaf node in B-tree */ + if(H5B2_create_leaf(f, dxpl_id, bt2->shared, &(bt2->root))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create root node") - /* Update number of records in node */ - leaf->nrec++; + /* Mark B-tree header as dirty, since we updated the address of the root node */ + bt2->cache_info.is_dirty = TRUE; + } /* end if */ + /* Check if we need to split the root node (equiv. to a 1->2 leaf node split) */ + else if((bt2->depth==0 && bt2->root.node_nrec==shared->split_leaf_nrec) || + (bt2->depth>0 && bt2->root.node_nrec==shared->split_int_nrec)) { + /* Split root node */ + if(H5B2_split_root(f, dxpl_id, bt2, bt2->shared)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node") + } /* end if */ + + /* Attempt to insert record into B-tree */ + if(bt2->depth>0) { + if(H5B2_insert_internal(f,dxpl_id,bt2->shared,bt2->depth,&(bt2->cache_info),&bt2->root,udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node") + } /* end if */ + else { + if(H5B2_insert_leaf(f,dxpl_id,bt2->shared,&bt2->root,udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node") + } /* end else */ - /* Mark leaf node as dirty also */ - leaf->cache_info.is_dirty = TRUE; + /* Mark parent node as dirty */ + bt2->cache_info.is_dirty = TRUE; done: - /* Release the B-tree leaf node */ - if (leaf) { -#ifdef H5B2_DEBUG -H5B2_assert_leaf(shared,leaf); -#endif /* H5B2_DEBUG */ - if(H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) - HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node") - } /* end if */ - - /* Check if we need to decrement the reference count for the B-tree's shared info */ - if(incr_rc) - H5RC_DEC(bt2_shared); + /* Release the B-tree header info */ + if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) + HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info") FUNC_LEAVE_NOAPI(ret_value) } /* H5B2_insert() */ @@ -2266,7 +2268,7 @@ done: * *------------------------------------------------------------------------- */ -herr_t +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) { @@ -2761,6 +2763,7 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* H5B2_index() */ +#ifdef OLD_WAY /*------------------------------------------------------------------------- * Function: H5B2_remove @@ -2795,58 +2798,184 @@ H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, unsigned idx; /* Location of record which matches key */ herr_t ret_value = SUCCEED; - FUNC_ENTER_NOAPI(H5B2_remove, FAIL) + FUNC_ENTER_NOAPI(H5B2_remove, FAIL) + + /* Check arguments. */ + HDassert(f); + HDassert(type); + HDassert(H5F_addr_defined(addr)); + + /* 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_CANTPROTECT, FAIL, "unable to load B-tree header") + + /* 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; + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2_shared); + HDassert(shared); + + /* Get B-tree depth */ + depth = bt2->depth; + + /* Check for empty B-tree */ + if(bt2->root.all_nrec==0) { + /* Release B-tree header node */ + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info") + bt2=NULL; + + /* Indicate error */ + HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree") + } /* end if */ + + /* Set initial "parent" information to the B-tree header */ + parent_cache_info=&(bt2->cache_info); + parent_addr=addr; + parent_ptr=bt2; + + /* Set initial node pointer for "current" node */ + curr_node_ptr=&(bt2->root); + + /* Check for non-trivial B-tree */ + if(depth>0) { + H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ + H5AC_info_t *curr_cache_info=NULL; /* Current node's cache info */ + haddr_t curr_addr=HADDR_UNDEF; /* Address of current node */ + void *curr_ptr=NULL; /* Pointer to current structure in memory */ + H5B2_node_ptr_t *child_node_ptr=NULL; /* Pointer to node pointer info for child node */ + + /* Find correct leaf to remove node from */ + while(depth>0) { + unsigned retries; /* Number of times to attempt redistribution */ + + /* Lock B-tree current node */ + if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") + +#ifdef H5B2_DEBUG + H5B2_assert_internal((hsize_t)0,shared,internal); +#endif /* H5B2_DEBUG */ + + /* Set information for current (root) node */ + curr_cache_info=&(internal->cache_info); + curr_addr=curr_node_ptr->addr; + curr_ptr=internal; + + /* 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++; + + /* Handle deleting a record from an internal node */ + if(cmp==0) { +HDfprintf(stderr,"%s: Deleting record in internal node of non-trival B-tree!\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + } /* end if */ + + /* Get node pointer for child */ + child_node_ptr=&(internal->node_ptrs[idx]); + + /* Set the number of redistribution retries */ + /* This takes care of the case where a B-tree node needs to be + * redistributed, but redistributing the node causes the index + * for insertion to move to another node, which also needs to be + * redistributed. Now, we loop trying to redistribute and then + * eventually force a merge */ + retries = 2; + + /* Preemptively merge/redistribute a node we will enter */ + while((depth==1 && child_node_ptr->node_nrec==shared->merge_leaf_nrec) || + (depth>1 && child_node_ptr->node_nrec==shared->merge_int_nrec)) { + /* Attempt to redistribute records among children */ + if(idx==0) { /* Left-most child */ + if(retries>0 && ((depth==1 && internal->node_ptrs[idx+1].node_nrec>shared->merge_leaf_nrec) || + (depth>1 && internal->node_ptrs[idx+1].node_nrec>shared->merge_int_nrec))) { +HDfprintf(stderr,"%s: Performing 2 node redistribution in B-tree!\n",FUNC); + if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { +HDfprintf(stderr,"%s: Need to perform 2->1 node merge in B-tree!\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + } /* end else */ + } /* end if */ + else if((unsigned)idx==internal->nrec) { /* Right-most child */ + if(retries>0 && ((depth==1 && internal->node_ptrs[idx-1].node_nrec>shared->merge_leaf_nrec) || + (depth>1 && internal->node_ptrs[idx-1].node_nrec>shared->merge_int_nrec))) { +HDfprintf(stderr,"%s: Performing 2 node redistribution in B-tree!\n",FUNC); + if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { +HDfprintf(stderr,"%s: Need to perform 2->1 node merge in B-tree!\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + } /* end else */ + } /* end if */ + else { /* Middle child */ + if(retries>0 && ((depth==1 && + ((internal->node_ptrs[idx+1].node_nrec>shared->merge_leaf_nrec) || + (internal->node_ptrs[idx-1].node_nrec>shared->merge_leaf_nrec))) || + (depth>1 && + ((internal->node_ptrs[idx+1].node_nrec>shared->merge_int_nrec) || + (internal->node_ptrs[idx-1].node_nrec>shared->merge_int_nrec))))) { +HDfprintf(stderr,"%s: Performing 3 node redistribution in B-tree!\n",FUNC); + if(H5B2_redistribute3(f,dxpl_id,depth,internal,(unsigned)idx)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { +HDfprintf(stderr,"%s: Need to perform 3->2 node merge in B-tree!\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + } /* end else */ + } /* end else */ + + /* Locate node pointer for child (after merge/redistribute) */ +/* 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++; + + /* Update child_node_ptr (to reflect change in location from merge/redistribution) */ + child_node_ptr=&(internal->node_ptrs[idx]); - /* Check arguments. */ - HDassert(f); - HDassert(type); - HDassert(H5F_addr_defined(addr)); + /* Decrement the number of redistribution retries left */ + retries--; + } /* end while */ - /* 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_CANTPROTECT, FAIL, "unable to load B-tree header") + /* Update record count (in parent) */ + curr_node_ptr->all_nrec--; - /* 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; + /* Mark parent node as dirty */ + parent_cache_info->is_dirty = TRUE; - /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(bt2_shared); - HDassert(shared); +#ifdef H5B2_DEBUG + if(parent_cache_info->type==H5AC_BT2_INT) + H5B2_assert_internal((hsize_t)0,shared,parent_ptr); +#endif /* H5B2_DEBUG */ - /* Get B-tree depth */ - depth = bt2->depth; + /* Unlock parent node (possibly the B-tree header) */ + if (H5AC_unprotect(f, dxpl_id, parent_cache_info->type, parent_addr, parent_ptr, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree info") - /* Check for empty B-tree */ - if(bt2->root.all_nrec==0) { - /* Release B-tree header node */ - if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info") - bt2=NULL; + /* Transition "current" info into "parent" info */ + parent_cache_info = curr_cache_info; + parent_addr = curr_addr; + parent_ptr = curr_ptr; - /* Indicate error */ - HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree") - } /* end if */ + /* Transition "child" node pointer to "current" node pointer */ + curr_node_ptr = child_node_ptr; - /* Check for non-trivial B-tree */ - if(bt2->depth>0) { -HDfprintf(stderr,"%s: Deleting record in non-trival B-tree!\n",FUNC); -HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + /* Decrement depth of current node */ + depth--; + } /* end while */ } /* end if */ - else { - /* Set initial "parent" information to the B-tree header */ - parent_cache_info=&(bt2->cache_info); - parent_addr=addr; - parent_ptr=bt2; - - /* Set initial node pointer for "current" node */ - curr_node_ptr=&(bt2->root); - } /* end else */ /* Must have a leaf node with enough space to insert a record now */ HDassert(H5F_addr_defined(curr_node_ptr->addr)); - /* Root only B-tree must break a few rules */ + /* "Root only" B-tree allowed to have less records in it's node */ if(depth>0) HDassert(curr_node_ptr->node_nrec > shared->merge_leaf_nrec); @@ -2923,6 +3052,305 @@ H5B2_assert_leaf(shared,leaf); FUNC_LEAVE_NOAPI(ret_value) } /* H5B2_remove() */ +#else /* OLD_WAY */ + +/*------------------------------------------------------------------------- + * Function: H5B2_remove_leaf + * + * Purpose: Removes a record from a B-tree leaf node. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Mar 3 2005 + * + *------------------------------------------------------------------------- + */ +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) +{ + H5B2_leaf_t *leaf; /* Pointer to leaf node */ + haddr_t leaf_addr=HADDR_UNDEF; /* Leaf address on disk */ + unsigned leaf_unprotect_flags=H5C__NO_FLAGS_SET; /* Flags for unprotecting leaf node */ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ + int cmp; /* Comparison value of records */ + unsigned idx; /* Location of record which matches key */ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI(H5B2_remove_leaf, FAIL) + + /* Check arguments. */ + HDassert(f); + HDassert(bt2_shared); + HDassert(curr_node_ptr); + HDassert(H5F_addr_defined(curr_node_ptr->addr)); + + /* Lock current B-tree node */ + leaf_addr = curr_node_ptr->addr; + if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, leaf_addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree leaf node") + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2_shared); + HDassert(shared); + + /* Sanity check number of records */ + HDassert(curr_node_ptr->all_nrec == curr_node_ptr->node_nrec); + HDassert(leaf->nrec == curr_node_ptr->node_nrec); + + /* Find correct location to remove this record */ + if((cmp = H5B2_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) != 0) + HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree") + + /* Make callback to retrieve record in native form */ + if((shared->type->retrieve)(udata,H5B2_LEAF_NREC(leaf,shared,idx))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record into leaf node") + + /* Update number of records in node */ + leaf->nrec--; + + /* Mark leaf node as dirty also */ + leaf->cache_info.is_dirty = TRUE; + + if(leaf->nrec > 0) { + /* Pack record out of leaf */ + HDmemmove(H5B2_LEAF_NREC(leaf,shared,idx),H5B2_LEAF_NREC(leaf,shared,idx+1),shared->type->nrec_size*(leaf->nrec-idx)); + } /* end if */ + else { + /* Release space for B-tree node on disk */ + if (H5MF_xfree(f, H5FD_MEM_BTREE, dxpl_id, leaf_addr, (hsize_t)shared->node_size)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to free B-tree leaf node") + + /* Let the cache know that the object is deleted */ + leaf_unprotect_flags = H5C__DELETED_FLAG; + + /* Reset address of parent node pointer */ + curr_node_ptr->addr = HADDR_UNDEF; + } /* end else */ + + /* Update record count for parent of leaf node */ + curr_node_ptr->all_nrec--; + curr_node_ptr->node_nrec--; + +done: + /* Release the B-tree leaf node */ + if (leaf && H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_addr, leaf, leaf_unprotect_flags) < 0) + HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release leaf B-tree node") + + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_remove_leaf() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_remove_internal + * + * Purpose: Removes a record from a B-tree node. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Mar 3 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_remove_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) +{ + H5B2_internal_t *internal; /* Pointer to internal node */ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ + unsigned idx; /* Location of record which matches key */ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI(H5B2_remove_internal, FAIL) + + /* Check arguments. */ + HDassert(f); + HDassert(bt2_shared); + HDassert(depth>0); + HDassert(parent_cache_info); + HDassert(curr_node_ptr); + HDassert(H5F_addr_defined(curr_node_ptr->addr)); + + /* Lock current B-tree node */ + if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, &(curr_node_ptr->node_nrec), bt2_shared, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node") + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2_shared); + HDassert(shared); + +/* Merge or redistribute child node pointers, if necessary */ + { + int cmp; /* Comparison value of records */ + 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++; + + /* Handle deleting a record from an internal node */ + if(cmp==0) { +HDfprintf(stderr,"%s: Deleting record in internal node of non-trival B-tree!\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + } /* end if */ + + + /* Set the number of redistribution retries */ + /* This takes care of the case where a B-tree node needs to be + * redistributed, but redistributing the node causes the index + * for removal to move to another node, which also needs to be + * redistributed. Now, we loop trying to redistribute and then + * eventually force a merge */ + retries = 2; + + /* Preemptively merge/redistribute a node we will enter */ + while((depth==1 && internal->node_ptrs[idx].node_nrec==shared->merge_leaf_nrec) || + (depth>1 && internal->node_ptrs[idx].node_nrec==shared->merge_int_nrec)) { + /* Attempt to redistribute records among children */ + if(idx==0) { /* Left-most child */ + if(retries>0 && ((depth==1 && internal->node_ptrs[idx+1].node_nrec>shared->merge_leaf_nrec) || + (depth>1 && internal->node_ptrs[idx+1].node_nrec>shared->merge_int_nrec))) { +HDfprintf(stderr,"%s: Performing 2 node redistribution in B-tree!\n",FUNC); + if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { +HDfprintf(stderr,"%s: Need to perform 2->1 node merge in B-tree!\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + } /* end else */ + } /* end if */ + else if((unsigned)idx==internal->nrec) { /* Right-most child */ + if(retries>0 && ((depth==1 && internal->node_ptrs[idx-1].node_nrec>shared->merge_leaf_nrec) || + (depth>1 && internal->node_ptrs[idx-1].node_nrec>shared->merge_int_nrec))) { +HDfprintf(stderr,"%s: Performing 2 node redistribution in B-tree!\n",FUNC); + if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { +HDfprintf(stderr,"%s: Need to perform 2->1 node merge in B-tree!\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + } /* end else */ + } /* end if */ + else { /* Middle child */ + if(retries>0 && ((depth==1 && + ((internal->node_ptrs[idx+1].node_nrec>shared->merge_leaf_nrec) || + (internal->node_ptrs[idx-1].node_nrec>shared->merge_leaf_nrec))) || + (depth>1 && + ((internal->node_ptrs[idx+1].node_nrec>shared->merge_int_nrec) || + (internal->node_ptrs[idx-1].node_nrec>shared->merge_int_nrec))))) { +HDfprintf(stderr,"%s: Performing 3 node redistribution in B-tree!\n",FUNC); + if(H5B2_redistribute3(f,dxpl_id,depth,internal,(unsigned)idx)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records") + } /* end if */ + else { +HDfprintf(stderr,"%s: Need to perform 3->2 node merge in B-tree!\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "Can't delete record in B-tree") + } /* end else */ + } /* end else */ + + /* Locate node pointer for child (after merge/redistribute) */ +/* 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++; + + /* Decrement the number of redistribution retries left */ + retries--; + } /* end while */ + } /* end block */ + + /* Attempt to remove node */ + if(depth>1) { + if(H5B2_remove_internal(f,dxpl_id,bt2_shared,depth-1,&internal->cache_info,&internal->node_ptrs[idx],udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree internal node") + } /* end if */ + else { + if(H5B2_remove_leaf(f,dxpl_id,bt2_shared,&internal->node_ptrs[idx],udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree leaf node") + } /* end else */ + + /* Update record count for node pointer to current node */ + curr_node_ptr->all_nrec--; + + /* Mark node as dirty */ + internal->cache_info.is_dirty = TRUE; + +done: + /* Release the B-tree internal node */ + if (internal && H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0) + HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release internal B-tree node") + + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_remove_internal() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_remove + * + * Purpose: Removes a record from a B-tree. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Feb 25 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5B2_remove(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, + void *udata) +{ + H5B2_t *bt2=NULL; /* Pointer to the B-tree header */ + H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI(H5B2_remove, FAIL) + + /* Check arguments. */ + HDassert(f); + HDassert(type); + HDassert(H5F_addr_defined(addr)); + + /* 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_CANTPROTECT, FAIL, "unable to load B-tree header") + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(bt2->shared); + HDassert(shared); + + /* Check for empty B-tree */ + if(bt2->root.all_nrec==0) + HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree") + + /* Attempt to remove record from B-tree */ + if(bt2->depth>0) { + if(H5B2_remove_internal(f,dxpl_id,bt2->shared,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") + } /* end if */ + else { + if(H5B2_remove_leaf(f,dxpl_id,bt2->shared,&bt2->root,udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to remove record from B-tree leaf node") + } /* end else */ + + /* Mark parent node as dirty */ + bt2->cache_info.is_dirty = TRUE; + +done: + /* Release the B-tree header info */ + if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) + HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree header info") + + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_remove() */ +#endif /* OLD_WAY */ /*------------------------------------------------------------------------- diff --git a/test/btree2.c b/test/btree2.c index 25783b9..54a5da7 100644 --- a/test/btree2.c +++ b/test/btree2.c @@ -1721,6 +1721,7 @@ test_insert_lots(hid_t fapl) unsigned u; /* Local index variable */ unsigned swap_idx; /* Location to swap with when shuffling */ hsize_t temp_rec; /* Temporary record */ + hsize_t nrec; /* Number of records in B-tree */ herr_t ret; /* Generic error return value */ /* Initialize random number seed */ @@ -1834,6 +1835,27 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time); PASSED(); + TESTING("B-tree insert: attempt duplicate record in level 4 B-tree"); + + record=INSERT_MANY/2; + H5E_BEGIN_TRY { + ret = H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record); + } H5E_END_TRY; + /* Should fail */ + if(ret != FAIL) 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_MANY) TEST_ERROR; + + PASSED(); + if (H5Fclose(file)<0) TEST_ERROR; HDfree(records); @@ -1872,7 +1894,6 @@ test_remove_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 */ 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 */ @@ -1992,6 +2013,181 @@ test_remove_basic(hid_t fapl) PASSED(); + /* Attempt to insert records into B-tree which had records removed */ + TESTING("B-tree remove: adding records to B-tree after removal"); + /* Insert several records into B-tree again */ + record=42; + if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + record=34; + if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + record=56; + if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + record=38; + 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 != 4) TEST_ERROR; + + PASSED(); + + /* Attempt to remove a non-existant record from a level-0 B-tree with mult. record */ + TESTING("B-tree remove: non-existant record from level-0 B-tree"); + record = 0; + H5E_BEGIN_TRY { + ret = H5B2_remove(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record); + } H5E_END_TRY; + /* Should fail */ + if(ret != FAIL) TEST_ERROR; + + PASSED(); + + /* Attempt to remove a record from a level-0 B-tree with mult. record */ + TESTING("B-tree remove: mult. existant records from level-0 B-tree"); + record = 42; + 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 != 42) 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 != 3) 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 root node has not been freed */ + if(!H5F_addr_defined(root_addr)) TEST_ERROR; + + record = 34; + 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 != 34) 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 != 2) 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 root node has not been freed */ + if(!H5F_addr_defined(root_addr)) TEST_ERROR; + + record = 56; + 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 != 56) 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 != 1) 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 root node has not been freed */ + if(!H5F_addr_defined(root_addr)) TEST_ERROR; + + record = 38; + 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 != 38) 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 != 0) 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 root node has been freed */ + if(H5F_addr_defined(root_addr)) TEST_ERROR; + + PASSED(); + if (H5Fclose(file)<0) TEST_ERROR; return 0; @@ -2005,6 +2201,152 @@ error: /*------------------------------------------------------------------------- + * Function: test_remove_level1_noredistrib + * + * Purpose: Basic tests for the B-tree v2 code + * + * Return: Success: 0 + * + * Failure: 1 + * + * Programmer: Quincey Koziol + * Friday, February 25, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static int +test_remove_level1_noredistrib(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 */ + herr_t ret; /* Generic error return value */ + + 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-1 B-tree with 3 leaves */ + for(u=0; u