[svn-r9995] Purpose:

    New feature & bug fix

Description:
    Allow root node to split, forming a level 2 B-tree

    Fix error where wrong record was being copied up to parent node for a 2
node redistribution on the "right" side of the B-tree.

Platforms tested:
    FreeBSD 4.11 (sleipnir) w/parallel
    Solaris 2.9 (shanti)

1 files changed, 130 insertions, 57 deletions

diff --git a/src/H5B2.c b/src/H5B2.c
index 32b3b83..d24f6eb 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -372,7 +372,16 @@ H5B2_locate_record(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
 static herr_t
 H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5RC_t *bt2_shared)
 {
+    const H5AC_class_t *child_class;    /* Pointer to child node's class info */
+    H5B2_internal_t *new_root;          /* Pointer to new root node */
+    haddr_t left_addr, right_addr;      /* Addresses of left & right child nodes */
+    void *left_child, *right_child;     /* Pointers to child nodes */
+    unsigned *left_nrec, *right_nrec;   /* Pointers to child # of records */
+    uint8_t *left_native, *right_native;/* Pointers to childs' native records */
+    H5B2_node_ptr_t *left_node_ptrs=NULL, *right_node_ptrs=NULL;/* Pointers to childs' node pointer info */
     H5B2_shared_t *shared;              /* B-tree's shared info */
+    unsigned mid_record;                /* Index of "middle" record in current node */
+    unsigned old_root_nrec;             /* Number of records in root node */
     herr_t ret_value=SUCCEED;           /* Return value */
 
     FUNC_ENTER_NOAPI_NOINIT(H5B2_split_root)
@@ -385,89 +394,153 @@ H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5RC_t *bt2_shared)
     shared=H5RC_GET_OBJ(bt2_shared);
     HDassert(shared);
 
-    if(bt2->depth==0) {
-        H5B2_internal_t *new_int=NULL;  /* Pointer to new internal node */
+    if(bt2->depth>0) {
+        H5B2_internal_t *old_int=NULL, *new_int=NULL;       /* Pointers to old & new internal nodes */
+        H5B2_node_ptr_t new_int_ptr;   /* Node pointer to manage new internal node */
+
+        /* Create new internal node */
+        new_int_ptr.all_nrec=new_int_ptr.node_nrec=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")
+
+        /* Setup information for unlocking child nodes */
+        child_class = H5AC_BT2_INT;
+        left_addr = bt2->root.addr;
+        right_addr = new_int_ptr.addr;
+
+        /* Protect both leafs */
+        if (NULL == (old_int = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, left_addr, &(bt2->root.node_nrec), bt2_shared, H5AC_WRITE)))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node")
+        if (NULL == (new_int = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, right_addr, &(new_int_ptr.node_nrec), bt2_shared, H5AC_WRITE)))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node")
+
+        /* More setup for child nodes */
+        left_child = old_int;
+        right_child = new_int;
+        left_nrec = &(old_int->nrec);
+        right_nrec = &(new_int->nrec);
+        left_native = old_int->int_native;
+        right_native = new_int->int_native;
+        left_node_ptrs = old_int->node_ptrs;
+        right_node_ptrs = new_int->node_ptrs;
+
+        /* Mark child nodes as dirty now */
+        old_int->cache_info.is_dirty = TRUE;
+        new_int->cache_info.is_dirty = TRUE;
+    } /* end if */
+    else {
         H5B2_leaf_t *old_leaf=NULL, *new_leaf=NULL;       /* Pointers to old & new leaf nodes */
-        H5B2_node_ptr_t new_int_ptr;    /* Node pointer to manage new internal node */
         H5B2_node_ptr_t new_leaf_ptr;   /* Node pointer to manage new leaf node */
-        H5B2_node_ptr_t old_leaf_ptr;   /* Node pointer to manage old leaf node */
-        unsigned mid_record;            /* Index of "middle" record in current node */
 
         /* Create new leaf node */
         new_leaf_ptr.all_nrec=new_leaf_ptr.node_nrec=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 */
-        mid_record = shared->split_leaf_nrec/2;
-
-        /* Set "old" leaf pointer to root node */
-        old_leaf_ptr = bt2->root;
+        /* Setup information for unlocking child nodes */
+        child_class = H5AC_BT2_LEAF;
+        left_addr = bt2->root.addr;
+        right_addr = new_leaf_ptr.addr;
 
         /* Protect both leafs */
-        if (NULL == (old_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, old_leaf_ptr.addr, &(old_leaf_ptr.node_nrec), bt2_shared, H5AC_WRITE)))
+        if (NULL == (old_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, left_addr, &(bt2->root.node_nrec), bt2_shared, H5AC_WRITE)))
             HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
-        if (NULL == (new_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, new_leaf_ptr.addr, &(new_leaf_ptr.node_nrec), bt2_shared, H5AC_WRITE)))
+        if (NULL == (new_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, right_addr, &(new_leaf_ptr.node_nrec), bt2_shared, H5AC_WRITE)))
             HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
 
-        /* Copy "upper half" of records to new leaf */
-        HDmemcpy(new_leaf->leaf_native,H5B2_LEAF_NREC(old_leaf,shared,mid_record+1),shared->type->nrec_size*(shared->split_leaf_nrec-(mid_record+1)));
+        /* More setup for child nodes */
+        left_child = old_leaf;
+        right_child = new_leaf;
+        left_nrec = &(old_leaf->nrec);
+        right_nrec = &(new_leaf->nrec);
+        left_native = old_leaf->leaf_native;
+        right_native = new_leaf->leaf_native;
 
-        /* Create new internal node */
-        new_int_ptr.all_nrec=new_int_ptr.node_nrec=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")
+        /* Mark child nodes as dirty now */
+        old_leaf->cache_info.is_dirty = TRUE;
+        new_leaf->cache_info.is_dirty = TRUE;
+    } /* end if */
 
-        /* Protect new internal node */
-        if (NULL == (new_int = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, new_int_ptr.addr, &(new_int_ptr.node_nrec), bt2_shared, H5AC_WRITE)))
-            HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node")
+    /* Set the old number of records in root node */
+    old_root_nrec = bt2->root.node_nrec;
 
-        /* Copy "middle" record to new internal node */
-        HDmemcpy(new_int->int_native,H5B2_LEAF_NREC(old_leaf,shared,mid_record),shared->type->nrec_size);
+    /* Determine "middle" record to promote to new root */
+    mid_record = old_root_nrec/2;
 
-        /* Update record counts in leaf nodes */
-        old_leaf_ptr.all_nrec = old_leaf_ptr.node_nrec = old_leaf->nrec = mid_record;
-        new_leaf_ptr.all_nrec = new_leaf_ptr.node_nrec = new_leaf->nrec = shared->split_leaf_nrec-(mid_record+1);
+    /* Copy "upper half" of records to new child */
+    HDmemcpy(H5B2_NAT_NREC(right_native,shared,0),H5B2_NAT_NREC(left_native,shared,mid_record+1),shared->type->nrec_size*(old_root_nrec-(mid_record+1)));
 
-        /* Mark leaf nodes as dirty */
-        old_leaf->cache_info.is_dirty = TRUE;
-        new_leaf->cache_info.is_dirty = TRUE;
+    /* Copy "upper half" of format root's node pointers, if the children of the root are internal nodes */
+    if(bt2->depth>0)
+        HDmemcpy(&(right_node_ptrs[0]),&(left_node_ptrs[mid_record+1]),sizeof(H5B2_node_ptr_t)*(old_root_nrec-mid_record));
 
-        /* Release leaf nodes */
-        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, old_leaf_ptr.addr, old_leaf, H5AC__NO_FLAGS_SET) < 0)
-            HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
-        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, new_leaf_ptr.addr, new_leaf, H5AC__NO_FLAGS_SET) < 0)
-            HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
+    /* Create new internal node to use as root */
+    if(H5B2_create_internal(f, dxpl_id, bt2_shared, &(bt2->root))<0)
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node")
 
-        /* Set internal node pointers to leaf nodes */
-        new_int->node_ptrs[0] = old_leaf_ptr;
-        new_int->node_ptrs[1] = new_leaf_ptr;
+    /* Protect new internal node */
+    if (NULL == (new_root = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, bt2->root.addr, &(bt2->root.node_nrec), bt2_shared, H5AC_WRITE)))
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node")
 
-        /* Update record count in new internal node */
-        new_int->nrec = 1;
+    /* Copy "middle" record to new internal node */
+    HDmemcpy(H5B2_INT_NREC(new_root,shared,0),H5B2_NAT_NREC(left_native,shared,mid_record),shared->type->nrec_size);
 
-        /* Mark new internal node as dirty */
-        new_int->cache_info.is_dirty = TRUE;
+    /* Set internal node pointers to child nodes */
+    new_root->node_ptrs[0].addr = left_addr;
+    new_root->node_ptrs[1].addr = right_addr;
+
+    /* Update record counts in child nodes */
+    new_root->node_ptrs[0].node_nrec = *left_nrec = mid_record;
+    new_root->node_ptrs[1].node_nrec = *right_nrec = old_root_nrec-(mid_record+1);
 
-        /* Release new internal node */
-        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, new_int_ptr.addr, new_int, H5AC__NO_FLAGS_SET) < 0)
-            HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree internal node")
+    /* Determine total number of records in new child nodes */
+    if(bt2->depth>0) {
+        unsigned u;             /* Local index variable */
+        unsigned new_left_all_nrec;     /* New total number of records in left child */
+        unsigned new_right_all_nrec;    /* New total number of records in right child */
 
-        /* Update depth of B-tree */
-        bt2->depth++;
+        /* Compute total of all records in each child node */
+        new_left_all_nrec = new_root->node_ptrs[0].node_nrec;
+        for(u=0; u<(*left_nrec+1); u++)
+            new_left_all_nrec += left_node_ptrs[u].all_nrec;
 
-        /* Update pointer to B-tree's root node to pointer to new internal node */
-        bt2->root.addr = new_int_ptr.addr;
-        bt2->root.node_nrec = 1;
+        new_right_all_nrec = new_root->node_ptrs[1].node_nrec;
+        for(u=0; u<(*right_nrec+1); u++)
+            new_right_all_nrec += right_node_ptrs[u].all_nrec;
 
-        /* Mark B-tree header as dirty */
-        bt2->cache_info.is_dirty = TRUE;
+        new_root->node_ptrs[0].all_nrec = new_left_all_nrec;
+        new_root->node_ptrs[1].all_nrec = new_right_all_nrec;
     } /* end if */
     else {
-HDfprintf(stderr,"%s: Need to split internal root! shared->split_int_nrec=%Zu\n",FUNC,shared->split_int_nrec);
-HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split internal root node yet")
+        new_root->node_ptrs[0].all_nrec = new_root->node_ptrs[0].node_nrec;
+        new_root->node_ptrs[1].all_nrec = new_root->node_ptrs[1].node_nrec;
     } /* end else */
 
+    /* Update record count in new internal node */
+    new_root->nrec = 1;
+
+    /* Mark new internal node as dirty */
+    new_root->cache_info.is_dirty = TRUE;
+
+    /* Release new internal node */
+    if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, bt2->root.addr, new_root, H5AC__NO_FLAGS_SET) < 0)
+        HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree internal node")
+
+    /* Release 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 leaf 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 leaf node")
+
+    /* Update depth of B-tree */
+    bt2->depth++;
+
+    /* Update pointer to B-tree's root node to pointer to new internal node */
+    bt2->root.node_nrec = 1;
+
+    /* Mark B-tree header as dirty */
+    bt2->cache_info.is_dirty = TRUE;
+
 done:
     FUNC_LEAVE_NOAPI(ret_value);
 } /* end H5B2_split_root */
@@ -556,7 +629,7 @@ HGOTO_ERROR(H5E_BTREE, H5E_CANTREDISTRIBUTE, FAIL, "unable to redistribute recor
             HDmemcpy(H5B2_NAT_NREC(left_native,shared,(*left_nrec+1)),H5B2_NAT_NREC(right_native,shared,0),shared->type->nrec_size*(move_nrec-1));
 
         /* Move record from right node into parent node */
-        HDmemcpy(H5B2_INT_NREC(internal,shared,idx),H5B2_NAT_NREC(right_native,shared,move_nrec),shared->type->nrec_size);
+        HDmemcpy(H5B2_INT_NREC(internal,shared,idx),H5B2_NAT_NREC(right_native,shared,(move_nrec-1)),shared->type->nrec_size);
 
         /* Slide records in right node down */
         HDmemmove(H5B2_NAT_NREC(right_native,shared,0),H5B2_NAT_NREC(right_native,shared,move_nrec),shared->type->nrec_size*new_right_nrec);
@@ -1245,7 +1318,7 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
             if((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) {
+                if(idx==0) {    /* Left-most child */
                     if((depth==1 && internal->node_ptrs[idx+1].node_nrec<shared->split_leaf_nrec) ||
                             (depth>1 && internal->node_ptrs[idx+1].node_nrec<shared->split_int_nrec)) {
                         if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)idx)<0)
@@ -1256,7 +1329,7 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
                             HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
                     } /* end else */
                 } /* end if */
-                else if((unsigned)idx==internal->nrec) {
+                else if((unsigned)idx==internal->nrec) { /* Right-most child */
                     if((depth==1 && internal->node_ptrs[idx-1].node_nrec<shared->split_leaf_nrec) ||
                             (depth>1 && internal->node_ptrs[idx-1].node_nrec<shared->split_int_nrec)) {
                         if(H5B2_redistribute2(f,dxpl_id,depth,internal,(unsigned)(idx-1))<0)
@@ -1267,7 +1340,7 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
                             HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node")
                     } /* end else */
                 } /* end if */
-                else {
+                else { /* Middle child */
                     if((depth==1 &&
                                 ((internal->node_ptrs[idx+1].node_nrec<shared->split_leaf_nrec) ||
                                 (internal->node_ptrs[idx-1].node_nrec<shared->split_leaf_nrec))) ||