summaryrefslogtreecommitdiffstats
path: root/src/H5B2.c
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2005-02-11 02:40:16 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2005-02-11 02:40:16 (GMT)
commitebfc303556d65d9952304995ce853fe2c3828963 (patch)
tree1a74ec86870e25dd247956eefc7cd40aca2fbd76 /src/H5B2.c
parent479bdb0bbdb3ba2f75cf374ff6086e1f711c624d (diff)
downloadhdf5-ebfc303556d65d9952304995ce853fe2c3828963.zip
hdf5-ebfc303556d65d9952304995ce853fe2c3828963.tar.gz
hdf5-ebfc303556d65d9952304995ce853fe2c3828963.tar.bz2
[svn-r9985] Purpose:
New feature & bug fixes Description: Checkpoint v2 B-tree code after getting preemptive 2->3 node splitting working (for leaf nodes only at the moment, however). Also, correct a problem with redistributing records that was probably causing the failures on mir in yesterday's daily tests. Ran code through purify on shanti and cleared up some warnings. Platforms tested: FreeBSD 4.11 (sleipnir) w/parallel Solaris 2.9 (shanti) w/purify
Diffstat (limited to 'src/H5B2.c')
-rw-r--r--src/H5B2.c231
1 files changed, 209 insertions, 22 deletions
diff --git a/src/H5B2.c b/src/H5B2.c
index 12f7593..c7c0cff 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -53,14 +53,20 @@
/* Local prototypes */
/* Helper functions */
-static herr_t H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr);
+static herr_t H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+ H5B2_node_ptr_t *node_ptr);
+static herr_t H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
+ H5B2_node_ptr_t *node_ptr);
static int H5B2_locate_record(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
unsigned nrec, size_t *rec_off, const uint8_t *native,
const void *udata);
static herr_t H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2,
H5RC_t *bt2_shared);
-static herr_t H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2,
- H5B2_node_ptr_t *node_ptr);
+static herr_t H5B2_redistribute2(H5F_t *f, hid_t dxpl_id, unsigned depth,
+ H5B2_internal_t *internal, unsigned idx);
+static herr_t H5B2_split2(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);
/* Package variables */
@@ -137,6 +143,9 @@ H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type,
/* Allocate "page" for node I/O */
if((shared->page=H5FL_BLK_MALLOC(node_page,shared->node_size))==NULL)
HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
+#ifdef H5_USING_PURIFY
+HDmemset(shared->page,0,shared->node_size);
+#endif /* H5_USING_PURIFY */
/* Create factory for internal node native record storage */
if((shared->int_fac=H5FL_fac_init(type->nkey_size*shared->internal_nrec))==NULL)
@@ -384,7 +393,7 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5RC_t *bt2_shared)
/* Create new leaf node */
new_leaf_ptr.all_nrec=new_leaf_ptr.node_nrec=0;
- if(H5B2_create_leaf(f, dxpl_id, bt2, &new_leaf_ptr)<0)
+ if(H5B2_create_leaf(f, dxpl_id, bt2_shared, &new_leaf_ptr)<0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new leaf node")
/* Determine "middle" record to promote to new root */
@@ -404,7 +413,7 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5RC_t *bt2_shared)
/* Create new internal node */
new_int_ptr.all_nrec=new_int_ptr.node_nrec=0;
- if(H5B2_create_internal(f, dxpl_id, bt2, &new_int_ptr)<0)
+ if(H5B2_create_internal(f, dxpl_id, bt2_shared, &new_int_ptr)<0)
HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node")
/* Protect new internal node */
@@ -497,7 +506,7 @@ H5B2_redistribute2(H5F_t *f, hid_t dxpl_id, unsigned depth, H5B2_internal_t *int
shared=H5RC_GET_OBJ(internal->shared);
HDassert(shared);
- /* Check for the kind of B-tree node to lock */
+ /* Check for the kind of B-tree node to redistribute */
if(depth>1) {
HDfprintf(stderr,"%s: redistributing internal node! (need to handle node_ptrs)\n",FUNC);
HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute records")
@@ -531,7 +540,7 @@ HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute recor
} /* end else */
/* Determine whether to shuffle records left or right */
- if(left_nrec<right_nrec) {
+ if(*left_nrec<*right_nrec) {
/* Moving record from right node to left */
unsigned new_right_nrec = (*left_nrec+*right_nrec)/2; /* New number of records for right child */
@@ -581,6 +590,7 @@ HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute recor
} /* end else */
/* Update # of records in parent node */
+/* Hmm, this value for 'all_rec' wont' be right for internal nodes... */
internal->node_ptrs[idx].all_nrec = internal->node_ptrs[idx].node_nrec = *left_nrec;
internal->node_ptrs[idx+1].all_nrec = internal->node_ptrs[idx+1].node_nrec = *right_nrec;
@@ -596,6 +606,177 @@ done:
/*-------------------------------------------------------------------------
+ * Function: H5B2_split2
+ *
+ * Purpose: Perform a 2->3 node split
+ *
+ * Return: Success: Non-negative
+ *
+ * Failure: Negative
+ *
+ * Programmer: Quincey Koziol
+ * koziol@ncsa.uiuc.edu
+ * Feb 9 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_split2(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)
+{
+ const H5AC_class_t *child_class; /* Pointer to child node's class info */
+ haddr_t left_addr, right_addr; /* Addresses of left & right child nodes */
+ haddr_t middle_addr; /* Addresses of middle child node */
+ void *left_child, *right_child; /* Pointers to left & right child nodes */
+ void *middle_child; /* Pointers to middle child node */
+ unsigned *left_nrec, *right_nrec; /* Pointers to left & right child # of records */
+ unsigned *middle_nrec; /* Pointers to middle child # of records */
+ uint8_t *left_native, *right_native; /* Pointers to left & right children's native records */
+ uint8_t *middle_native; /* Pointers to middle child's native records */
+ H5B2_shared_t *shared; /* B-tree's shared info */
+ herr_t ret_value=SUCCEED; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5B2_split2)
+
+ HDassert(f);
+ HDassert(internal);
+
+ /* Get the pointer to the shared B-tree info */
+ shared=H5RC_GET_OBJ(internal->shared);
+ HDassert(shared);
+
+ /* Slide records in parent node down one space, to make room for promoted record */
+ HDmemmove(H5B2_INT_NREC(internal,shared,idx+2),H5B2_INT_NREC(internal,shared,idx+1),shared->type->nkey_size*(internal->nrec-(idx+1)));
+ HDmemmove(&(internal->node_ptrs[idx+2]),&(internal->node_ptrs[idx+1]),sizeof(H5B2_node_ptr_t)*(internal->nrec-idx));
+
+ /* Check for the kind of B-tree node to split */
+ if(depth>1) {
+HDfprintf(stderr,"%s: splitting internal node! (need to handle node_ptrs)\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split nodes")
+ } /* end if */
+ else {
+ H5B2_leaf_t *left_leaf; /* Pointer to left leaf node */
+ H5B2_leaf_t *right_leaf; /* Pointer to right leaf node */
+ H5B2_leaf_t *middle_leaf; /* Pointer to middle leaf node */
+
+ /* Setup information for unlocking child nodes */
+ child_class = H5AC_BT2_LEAF;
+ left_addr = internal->node_ptrs[idx].addr;
+ right_addr = internal->node_ptrs[idx+2].addr;
+
+ /* Lock left & right B-tree child nodes */
+ if (NULL == (left_leaf = H5AC_protect(f, dxpl_id, child_class, left_addr, &(internal->node_ptrs[idx].node_nrec), internal->shared, H5AC_WRITE)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
+ if (NULL == (right_leaf = H5AC_protect(f, dxpl_id, child_class, right_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
+
+ /* Create new empty "middle" leaf node */
+ internal->node_ptrs[idx+1].all_nrec=internal->node_ptrs[idx+1].node_nrec=0;
+ if(H5B2_create_leaf(f, dxpl_id, internal->shared, &(internal->node_ptrs[idx+1]))<0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new leaf node")
+
+ /* Setup information for unlocking middle child node */
+ middle_addr = internal->node_ptrs[idx+1].addr;
+
+ /* Lock "middle" leaf node */
+ if (NULL == (middle_leaf = H5AC_protect(f, dxpl_id, child_class, middle_addr, &(internal->node_ptrs[idx+1].node_nrec), internal->shared, H5AC_WRITE)))
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
+
+ /* More setup for accessing child node information */
+ left_child = left_leaf;
+ right_child = right_leaf;
+ middle_child = middle_leaf;
+ left_nrec = &(left_leaf->nrec);
+ right_nrec = &(right_leaf->nrec);
+ middle_nrec = &(middle_leaf->nrec);
+ left_native = left_leaf->leaf_native;
+ right_native = right_leaf->leaf_native;
+ middle_native = middle_leaf->leaf_native;
+
+ /* Mark child nodes as dirty now */
+ left_leaf->cache_info.is_dirty = TRUE;
+ right_leaf->cache_info.is_dirty = TRUE;
+ middle_leaf->cache_info.is_dirty = TRUE;
+ } /* end else */
+
+ /* Sanity check */
+ HDassert(*left_nrec==*right_nrec);
+
+ /* Redistribute records */
+ {
+ /* Compute new # of records in each node */
+ unsigned total_nrec = *left_nrec + *right_nrec + 1;
+ unsigned new_middle_nrec = (total_nrec-2)/3;
+ unsigned new_left_nrec = ((total_nrec-2)-new_middle_nrec)/2;
+ unsigned new_right_nrec = (total_nrec-2)-(new_left_nrec+new_middle_nrec);
+
+ /* Fill new middle node */
+ {
+ unsigned curr_middle_idx=0;
+
+ /* Copy record(s) from left node to proper location */
+ if(new_left_nrec<(*left_nrec-1)) {
+ curr_middle_idx=*left_nrec-(new_left_nrec+1);
+ HDmemcpy(H5B2_NAT_NREC(middle_native,shared,0),H5B2_NAT_NREC(left_native,shared,(new_left_nrec+1)),shared->type->nkey_size*curr_middle_idx);
+ } /* end if */
+
+ /* Copy record from parent node to proper location */
+ HDmemcpy(H5B2_NAT_NREC(middle_native,shared,curr_middle_idx),H5B2_INT_NREC(internal,shared,idx),shared->type->nkey_size);
+ curr_middle_idx++;
+
+ /* Copy record(s) from right node to proper location */
+ if(new_right_nrec<(*right_nrec-1))
+ HDmemcpy(H5B2_NAT_NREC(middle_native,shared,curr_middle_idx),H5B2_NAT_NREC(right_native,shared,0),shared->type->nkey_size*(*right_nrec-(new_right_nrec+1)));
+
+ /* Update # of records in middle node */
+ *middle_nrec=new_middle_nrec;
+ } /* end block */
+
+
+ /* Promote records to parent node from left & right nodes */
+ HDmemcpy(H5B2_INT_NREC(internal,shared,idx),H5B2_NAT_NREC(left_native,shared,new_left_nrec),shared->type->nkey_size);
+ HDmemcpy(H5B2_INT_NREC(internal,shared,idx+1),H5B2_NAT_NREC(right_native,shared,(*right_nrec-(new_right_nrec+1))),shared->type->nkey_size);
+
+ /* Update # of records in left node */
+ *left_nrec = new_left_nrec;
+
+ /* Slide records in right node to proper position */
+ HDmemmove(H5B2_NAT_NREC(right_native,shared,0),H5B2_NAT_NREC(right_native,shared,(*right_nrec-new_right_nrec)),shared->type->nkey_size*new_right_nrec);
+
+ /* Update # of records in right node */
+ *right_nrec = new_right_nrec;
+ } /* end block */
+
+ /* Update # of records in parent node */
+/* Hmm, this value for 'all_rec' wont' be right for internal nodes... */
+ internal->node_ptrs[idx].all_nrec = internal->node_ptrs[idx].node_nrec = *left_nrec;
+ internal->node_ptrs[idx+1].all_nrec = internal->node_ptrs[idx+1].node_nrec = *middle_nrec;
+ internal->node_ptrs[idx+2].all_nrec = internal->node_ptrs[idx+2].node_nrec = *right_nrec;
+ internal->nrec++;
+
+ /* Mark parent as dirty */
+ internal->cache_info.is_dirty = TRUE;
+
+ /* Update grandparent info */
+ curr_node_ptr->node_nrec++;
+
+ /* Mark grandparent as dirty */
+ parent_cache_info->is_dirty = TRUE;
+
+ /* Unlock child nodes */
+ if (H5AC_unprotect(f, dxpl_id, child_class, left_addr, left_child, H5AC__NO_FLAGS_SET) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree child node")
+ if (H5AC_unprotect(f, dxpl_id, child_class, right_addr, right_child, H5AC__NO_FLAGS_SET) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree child node")
+ if (H5AC_unprotect(f, dxpl_id, child_class, middle_addr, middle_child, H5AC__NO_FLAGS_SET) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree child node")
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5B2_split2 */
+
+
+/*-------------------------------------------------------------------------
* Function: H5B2_insert
*
* Purpose: Adds a new record to the B-tree. If the root node of
@@ -646,7 +827,7 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
/* 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, &(bt2->root))<0)
+ 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 */
@@ -713,8 +894,8 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
} /* end if */
else {
-HDfprintf(stderr,"%s: left-most child: must split node\n",FUNC);
-HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
+ 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) {
@@ -724,8 +905,8 @@ HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute child node records")
} /* end if */
else {
-HDfprintf(stderr,"%s: right-most child: must split node\n",FUNC);
-HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
+ 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 {
@@ -745,11 +926,8 @@ HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
} /* end else */
} /* end else */
- /* Split children, if can't redistribute */
- /* Update record count info for current node to reflect new # of records (in parent) */
-
-
/* 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((idx=H5B2_locate_record(f,dxpl_id,shared->type,internal->nrec,shared->nat_off,internal->int_native,udata))<0)
HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
@@ -887,7 +1065,7 @@ done:
*-------------------------------------------------------------------------
*/
static herr_t
-H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr)
+H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_t *node_ptr)
{
H5B2_leaf_t *leaf=NULL; /* Pointer to new leaf node created */
H5B2_shared_t *shared; /* Shared B-tree information */
@@ -897,7 +1075,7 @@ H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr
/* Check arguments. */
HDassert(f);
- HDassert(bt2);
+ HDassert(bt2_shared);
HDassert(node_ptr);
/* Allocate memory for leaf information */
@@ -909,7 +1087,7 @@ H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr
leaf->cache_info.is_dirty = TRUE;
/* Share common B-tree information */
- leaf->shared = bt2->shared;
+ leaf->shared = bt2_shared;
H5RC_INC(leaf->shared);
/* Get the pointer to the shared B-tree info */
@@ -919,6 +1097,9 @@ H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr
/* Allocate space for the native keys in memory */
if((leaf->leaf_native=H5FL_FAC_MALLOC(shared->leaf_fac))==NULL)
HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree leaf native keys")
+#ifdef H5_USING_PURIFY
+HDmemset(leaf->leaf_native,0,shared->type->nkey_size*shared->leaf_nrec);
+#endif /* H5_USING_PURIFY */
/* Set number of records */
leaf->nrec=0;
@@ -956,7 +1137,7 @@ done:
*-------------------------------------------------------------------------
*/
static herr_t
-H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr)
+H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared, H5B2_node_ptr_t *node_ptr)
{
H5B2_internal_t *internal=NULL; /* Pointer to new internal node created */
H5B2_shared_t *shared; /* Shared B-tree information */
@@ -966,7 +1147,7 @@ H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node
/* Check arguments. */
HDassert(f);
- HDassert(bt2);
+ HDassert(bt2_shared);
HDassert(node_ptr);
/* Allocate memory for internal node information */
@@ -978,7 +1159,7 @@ H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node
internal->cache_info.is_dirty = TRUE;
/* Share common B-tree information */
- internal->shared = bt2->shared;
+ internal->shared = bt2_shared;
H5RC_INC(internal->shared);
/* Get the pointer to the shared B-tree info */
@@ -988,10 +1169,16 @@ H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node
/* Allocate space for the native keys in memory */
if((internal->int_native=H5FL_FAC_MALLOC(shared->int_fac))==NULL)
HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal native keys")
+#ifdef H5_USING_PURIFY
+HDmemset(internal->int_native,0,shared->type->nkey_size*shared->internal_nrec);
+#endif /* H5_USING_PURIFY */
/* Allocate space for the node pointers in memory */
if((internal->node_ptrs=H5FL_FAC_MALLOC(shared->node_ptr_fac))==NULL)
HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal node pointers")
+#ifdef H5_USING_PURIFY
+HDmemset(internal->node_ptrs,0,sizeof(H5B2_node_ptr_t)*(shared->internal_nrec+1));
+#endif /* H5_USING_PURIFY */
/* Set number of records */
internal->nrec=0;