[svn-r12915] Description:

    Finish adding "delete by index" feature to v2 B-trees.

Tested on:
    FreeBSD/32 4.11 (sleipnir)
    Linux/32 2.4 (heping)
    Linux/64 2.4 (mir)
    AIX/32 5.? (copper)

2 files changed, 210 insertions, 125 deletions

diff --git a/src/H5B2int.c b/src/H5B2int.c
index 4646734..879c12d 100644
--- a/src/H5B2int.c
+++ b/src/H5B2int.c
@@ -2417,6 +2417,9 @@ H5B2_remove_internal(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
             /* (NOTE: These 2-node redistributions should actually get the
              *  record to promote from the node with more records. - QAK)
              */
+            /* (NOTE: This code is the same in both H5B2_remove_internal() and
+             *  H5B2_remove_internal_by_idx(), fix bugs in both places! - QAK)
+             */
             if(idx == 0) {    /* Left-most child */
                 if(retries > 0 && (internal->node_ptrs[idx + 1].node_nrec > merge_nrec)) {
                     if(H5B2_redistribute2(f, dxpl_id, depth, internal, idx) < 0)
@@ -2646,10 +2649,12 @@ H5B2_remove_internal_by_idx(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
     internal_addr = curr_node_ptr->addr;
     if(NULL == (internal = H5B2_protect_internal(f, dxpl_id, bt2_shared, internal_addr, curr_node_ptr->node_nrec, depth, H5AC_WRITE)))
         HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node")
+    HDassert(internal->nrec == curr_node_ptr->node_nrec);
 
     /* Get the pointer to the shared B-tree info */
     shared = H5RC_GET_OBJ(bt2_shared);
     HDassert(shared);
+    HDassert(depth == shared->depth || internal->nrec > 1);
 
     /* Determine the correct number of records to merge at */
     merge_nrec = shared->node_info[depth - 1].merge_nrec;
@@ -2658,6 +2663,7 @@ H5B2_remove_internal_by_idx(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
     /* (The root node is the only internal node allowed to have 1 record) */
     if(internal->nrec == 1 &&
             ((internal->node_ptrs[0].node_nrec + internal->node_ptrs[1].node_nrec) <= ((merge_nrec * 2) + 1))) {
+        HDassert(depth == shared->depth);
 
         /* Merge children of root node */
         if(H5B2_merge2(f, dxpl_id, depth, curr_node_ptr,
@@ -2688,6 +2694,7 @@ H5B2_remove_internal_by_idx(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
     } /* end if */
     /* Merge or redistribute child node pointers, if necessary */
     else {
+        hsize_t orig_n = n;     /* Original index looked for */
         unsigned idx;           /* Location of record which matches key */
         hbool_t found = FALSE;  /* Comparison value of records */
         unsigned retries;       /* Number of times to attempt redistribution */
@@ -2698,18 +2705,19 @@ H5B2_remove_internal_by_idx(H5F_t *f, hid_t dxpl_id, H5RC_t *bt2_shared,
         else {
             /* Search for record with correct index */
             for(idx = 0; idx < internal->nrec; idx++) {
-HDfprintf(stderr, "%s: Check 1.0 - internal->node_ptrs[%u].all_nrec = %Hu\n", FUNC, idx, internal->node_ptrs[idx].all_nrec);
-HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
                 /* Check which child node contains indexed record */
                 if(internal->node_ptrs[idx].all_nrec >= n) {
                     /* Check if record is in this node */
                     if(internal->node_ptrs[idx].all_nrec == n) {
+                        /* Indicate the record was found and that the index
+                         *      in child nodes is zero from now on
+                         */
                         found = TRUE;
                         n = 0;
-                    } /* end if */
 
-                    /* Increment to next record */
-                    idx++;
+                        /* Increment to next record */
+                        idx++;
+                    } /* end if */
 
                     /* Break out of loop early */
                     break;
@@ -2721,8 +2729,6 @@ HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
                 n -= (internal->node_ptrs[idx].all_nrec + 1);
             } /* end for */
         } /* end else */
-HDfprintf(stderr, "%s: Check 1.0 - idx = %u\n", FUNC, idx);
-HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
 
         /* Set the number of redistribution retries */
         /* This takes care of the case where a B-tree node needs to be
@@ -2738,6 +2744,9 @@ HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
             /* (NOTE: These 2-node redistributions should actually get the
              *  record to promote from the node with more records. - QAK)
              */
+            /* (NOTE: This code is the same in both H5B2_remove_internal() and
+             *  H5B2_remove_internal_by_idx(), fix bugs in both places! - QAK)
+             */
             if(idx == 0) {    /* Left-most child */
                 if(retries > 0 && (internal->node_ptrs[idx + 1].node_nrec > merge_nrec)) {
                     if(H5B2_redistribute2(f, dxpl_id, depth, internal, idx) < 0)
@@ -2777,20 +2786,29 @@ HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
             if(swap_loc)
                 idx = 0;
             else {
+                /* Count from the orginal index value again */
+                n = orig_n;
+
+                /* Reset "found" flag - the record may have shifted during the
+                 *      redistribute/merge
+                 */
+                found = FALSE;
+
                 /* Search for record with correct index */
                 for(idx = 0; idx < internal->nrec; idx++) {
-HDfprintf(stderr, "%s: Check 2.0 - internal->node_ptrs[%u].all_nrec = %Hu\n", FUNC, idx, internal->node_ptrs[idx].all_nrec);
-HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
                     /* Check which child node contains indexed record */
                     if(internal->node_ptrs[idx].all_nrec >= n) {
                         /* Check if record is in this node */
                         if(internal->node_ptrs[idx].all_nrec == n) {
+                            /* Indicate the record was found and that the index
+                             *      in child nodes is zero from now on
+                             */
                             found = TRUE;
                             n = 0;
-                        } /* end if */
 
-                        /* Increment to next record */
-                        idx++;
+                            /* Increment to next record */
+                            idx++;
+                        } /* end if */
 
                         /* Break out of loop early */
                         break;
@@ -2802,8 +2820,6 @@ HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
                     n -= (internal->node_ptrs[idx].all_nrec + 1);
                 } /* end for */
             } /* end else */
-HDfprintf(stderr, "%s: Check 2.0 - idx = %u\n", FUNC, idx);
-HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
 
             /* Decrement the number of redistribution retries left */
             retries--;
@@ -2835,7 +2851,7 @@ HDfprintf(stderr, "%s: n = %Hu\n", FUNC, n);
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */
 
-    /* Update record count for node pointer to current node */
+    /* Update record count for node pointer to child node */
     if(!collapsed_root)
         new_node_ptr->all_nrec--;
 
diff --git a/test/btree2.c b/test/btree2.c
index bcbff18..1812dab 100644
--- a/test/btree2.c
+++ b/test/btree2.c
@@ -6354,10 +6354,9 @@ error:
  *
  * Purpose:	Basic tests for the B-tree v2 code.  This test inserts many
  *              records in random order, enough to make at a level 4 B-tree
- *              and then removes them all.
+ *              and then removes them all, by record and by index.
  *
  * Return:	Success:	0
- *
  *		Failure:	1
  *
  * Programmer:	Quincey Koziol
@@ -6368,9 +6367,12 @@ error:
 static int
 test_remove_lots(hid_t fapl)
 {
-    hid_t	file=-1;
+    hid_t	file = -1;
     char	filename[1024];
-    H5F_t	*f=NULL;
+    H5F_t	*f = NULL;
+    int         fd = -1;                /* File descriptor */
+    h5_stat_t	sb;                     /* Stat buffer for file */
+    void        *file_data = NULL;      /* Copy of file data */
     hsize_t     record;                 /* Record to insert into tree */
     hsize_t     rrecord;                /* Record to remove from tree */
     haddr_t     bt2_addr;               /* Address of B-tree created */
@@ -6378,26 +6380,24 @@ test_remove_lots(hid_t fapl)
     time_t      curr_time;              /* Current time, for seeding random number generator */
     hsize_t     *records;               /* Record #'s for random insertion */
     unsigned    u;                      /* Local index variable */
-    unsigned    swap_idx;               /* Location to swap with when shuffling */
-    hsize_t     temp_rec;               /* Temporary record */
+    unsigned    rem_idx;                /* Location to remove */
     H5B2_stat_t bt2_stat;               /* Statistics about B-tree created */
     hsize_t     nrec;                   /* Number of records in B-tree */
 
     /* Initialize random number seed */
-    curr_time=HDtime(NULL);
+    curr_time = HDtime(NULL);
 #ifdef QAK
-curr_time=1109170019;
-HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time);
+curr_time = 1163537969;
+HDfprintf(stderr, "curr_time = %lu\n", (unsigned long)curr_time);
 #endif /* QAK */
     HDsrandom((unsigned long)curr_time);
 
     /*
      * Test removing many records into v2 B-tree
      */
-    TESTING("B-tree remove: create random level 4 B-tree and delete all records");
 
     /* Allocate space for the records */
-    if((records = HDmalloc(sizeof(hsize_t)*INSERT_MANY))==NULL)
+    if(NULL == (records = HDmalloc(sizeof(hsize_t) * INSERT_MANY)))
         TEST_ERROR
 
     /* Initialize record #'s */
@@ -6406,6 +6406,9 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time);
 
     /* Shuffle record #'s */
     for(u = 0; u < INSERT_MANY; u++) {
+        hsize_t     temp_rec;               /* Temporary record */
+        unsigned    swap_idx;               /* Location to swap with when shuffling */
+
         swap_idx = (unsigned)(HDrandom() % (INSERT_MANY - u)) + u;
         temp_rec = records[u];
         records[u] = records[swap_idx];
@@ -6445,6 +6448,35 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time);
     if(H5Fclose(file) < 0)
         STACK_ERROR
 
+
+    /* Make a copy of the file in memory, in order to speed up deletion testing */
+
+    /* Open the file just created */
+    if((fd = HDopen(filename, O_RDONLY, 0)) < 0)
+        TEST_ERROR
+
+    /* Retrieve the file's size */
+    if(HDfstat(fd, &sb) < 0)
+        TEST_ERROR
+
+    /* Allocate space for the file data */
+    if(NULL == (file_data = HDmalloc((size_t)sb.st_size)))
+        TEST_ERROR
+
+    /* Read file's data into memory */
+    if(HDread(fd, file_data, (size_t)sb.st_size) < (ssize_t)sb.st_size)
+        TEST_ERROR
+
+    /* Close the file */
+    if(HDclose(fd) < 0)
+        TEST_ERROR
+    fd = -1;
+
+
+
+    /* Print banner for this test */
+    TESTING("B-tree remove: create random level 4 B-tree and delete all records in random order");
+
     /* Re-open the file */
     if((file = H5Fopen(filename, H5F_ACC_RDWR, fapl)) < 0)
         FAIL_STACK_ERROR
@@ -6455,7 +6487,10 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time);
 
     /* Re-shuffle record #'s */
     for(u = 0; u < INSERT_MANY; u++) {
-        swap_idx = (unsigned)(HDrandom()%(INSERT_MANY - u)) + u;
+        hsize_t     temp_rec;               /* Temporary record */
+        unsigned    swap_idx;               /* Location to swap with when shuffling */
+
+        swap_idx = (unsigned)(HDrandom() % (INSERT_MANY - u)) + u;
         temp_rec = records[u];
         records[u] = records[swap_idx];
         records[swap_idx] = temp_rec;
@@ -6495,115 +6530,159 @@ HDfprintf(stderr,"curr_time=%lu\n",(unsigned long)curr_time);
 
     PASSED();
 
-    HDfree(records);
-
-    return 0;
 
-error:
-    H5E_BEGIN_TRY {
-	H5Fclose(file);
-    } H5E_END_TRY;
-    HDfree(records);
-    return 1;
-} /* test_remove_lots() */
 
-
-/*-------------------------------------------------------------------------
- * Function:	test_remove_by_idx
- *
- * Purpose:	Basic tests for the B-tree v2 code.  This test inserts many
- *              records in random order, enough to make at a level 4 B-tree
- *              and then removes them all, by index.
- *
- * Return:	Success:	0
- *		Failure:	1
- *
- * Programmer:	Quincey Koziol
- *              Tuesday, November 14, 2006
- *
- *-------------------------------------------------------------------------
- */
-static int
-test_remove_by_idx(hid_t fapl)
-{
-    hid_t	file = -1;
-    char	filename[1024];
-    H5F_t	*f = NULL;
-    hsize_t     record;                 /* Record to insert into tree */
-    hsize_t     rrecord;                /* Record to remove from tree */
-    haddr_t     bt2_addr;               /* Address of B-tree created */
-    haddr_t     root_addr;              /* Address of root of B-tree created */
-    time_t      curr_time;              /* Current time, for seeding random number generator */
-    hsize_t     *records;               /* Record #'s for random insertion */
-    unsigned    u;                      /* Local index variable */
-    unsigned    swap_idx;               /* Location to swap with when shuffling */
-    unsigned    rem_idx;                /* Location to remove */
-    hsize_t     temp_rec;               /* Temporary record */
-    H5B2_stat_t bt2_stat;               /* Statistics about B-tree created */
-    hsize_t     nrec;                   /* Number of records in B-tree */
+    /* Re-write the file's data with the copy in memory */
 
-    /* Initialize random number seed */
-    curr_time = HDtime(NULL);
-#ifndef QAK
-curr_time = 1163537969;
-HDfprintf(stderr, "curr_time = %lu\n", (unsigned long)curr_time);
-#endif /* QAK */
-    HDsrandom((unsigned long)curr_time);
+    /* Open the file just created */
+    if((fd = HDopen(filename, O_RDWR|O_CREAT|O_TRUNC, 0666)) < 0)
+        TEST_ERROR
 
-    /*
-     * Test removing many records into v2 B-tree
-     */
-    TESTING("B-tree remove: create random level 4 B-tree and delete all records by index");
+    /* Write file's data from memory */
+    if(HDwrite(fd, file_data, (size_t)sb.st_size) < (ssize_t)sb.st_size)
+        TEST_ERROR
 
-    /* Allocate space for the records */
-    if(NULL == (records = HDmalloc(sizeof(hsize_t) * INSERT_MANY)))
+    /* Close the file */
+    if(HDclose(fd) < 0)
         TEST_ERROR
+    fd = -1;
 
-    /* Initialize record #'s */
-    for(u = 0; u < INSERT_MANY; u++)
-        records[u] = u;
 
-    /* Shuffle record #'s */
+
+    /* Print banner for this test */
+    TESTING("B-tree remove: create random level 4 B-tree and delete all records by index, in random order");
+
+    /* Re-open the file */
+    if((file = H5Fopen(filename, H5F_ACC_RDWR, fapl)) < 0)
+        FAIL_STACK_ERROR
+
+    /* Get a pointer to the internal file object */
+    if(NULL == (f = H5I_object(file)))
+        FAIL_STACK_ERROR
+
+    /* Remove all records */
     for(u = 0; u < INSERT_MANY; u++) {
-        swap_idx = (unsigned)(HDrandom() % (INSERT_MANY - u)) + u;
-        temp_rec = records[u];
-        records[u] = records[swap_idx];
-        records[swap_idx] = temp_rec;
+        /* Pick a record index to remove from randomly */
+        rem_idx = (unsigned)(HDrandom() % (INSERT_MANY - u));
+        rrecord = HSIZET_MAX;
+
+        /* Remove random record */
+        if(H5B2_remove_by_idx(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)rem_idx, remove_cb, &rrecord) < 0)
+            FAIL_STACK_ERROR
+
+        /* Make certain that the record value is correct */
+        if(rrecord >= INSERT_MANY)
+            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)
+            FAIL_STACK_ERROR
+
+        /* Make certain that the # of records is correct */
+        if(nrec != (INSERT_MANY - (u + 1)))
+            TEST_ERROR
     } /* end for */
 
-    h5_fixname(FILENAME[0], fapl, filename, sizeof filename);
+    /* Query the address of the root node in the B-tree */
+    if(H5B2_get_root_addr_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &root_addr) < 0)
+        FAIL_STACK_ERROR
 
-    /* Create the file to work on */
-    if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0)
+    /* Make certain that the address of the root node is defined */
+    if(H5F_addr_defined(root_addr))
+        TEST_ERROR
+
+    /* Close file */
+    if(H5Fclose(file) < 0)
         STACK_ERROR
 
+    PASSED();
+
+
+
+    /* Re-write the file's data with the copy in memory */
+
+    /* Open the file just created */
+    if((fd = HDopen(filename, O_RDWR|O_CREAT|O_TRUNC, 0666)) < 0)
+        TEST_ERROR
+
+    /* Write file's data from memory */
+    if(HDwrite(fd, file_data, (size_t)sb.st_size) < (ssize_t)sb.st_size)
+        TEST_ERROR
+
+    /* Close the file */
+    if(HDclose(fd) < 0)
+        TEST_ERROR
+    fd = -1;
+
+
+
+    /* Print banner for this test */
+    TESTING("B-tree remove: create random level 4 B-tree and delete all records by index, in increasing order");
+
+    /* Re-open the file */
+    if((file = H5Fopen(filename, H5F_ACC_RDWR, fapl)) < 0)
+        FAIL_STACK_ERROR
+
     /* Get a pointer to the internal file object */
     if(NULL == (f = H5I_object(file)))
-        STACK_ERROR
-
-    /*
-     * Create v2 B-tree
-     */
-    if(H5B2_create(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, 512, 8, 100, 40, &bt2_addr/*out*/) < 0)
         FAIL_STACK_ERROR
 
-    /* Insert random records */
+    /* Remove all records */
     for(u = 0; u < INSERT_MANY; u++) {
-        record = records[u];
-        if(H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &record) < 0)
+        /* Remove first record */
+        rrecord = HSIZET_MAX;
+        if(H5B2_remove_by_idx(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)0, remove_cb, &rrecord) < 0)
             FAIL_STACK_ERROR
+
+        /* Make certain that the record value is correct */
+        if(rrecord != u)
+            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)
+            FAIL_STACK_ERROR
+
+        /* Make certain that the # of records is correct */
+        if(nrec != (INSERT_MANY - (u + 1)))
+            TEST_ERROR
     } /* end for */
 
-    /* Check up on B-tree */
-    if(H5B2_stat_info(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &bt2_stat) < 0)
+    /* Query the address of the root node in the B-tree */
+    if(H5B2_get_root_addr_test(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, &root_addr) < 0)
         FAIL_STACK_ERROR
-    if(bt2_stat.depth != 4)
+
+    /* Make certain that the address of the root node is defined */
+    if(H5F_addr_defined(root_addr))
         TEST_ERROR
 
     /* Close file */
     if(H5Fclose(file) < 0)
         STACK_ERROR
 
+    PASSED();
+
+
+
+    /* Re-write the file's data with the copy in memory */
+
+    /* Open the file just created */
+    if((fd = HDopen(filename, O_RDWR|O_CREAT|O_TRUNC, 0666)) < 0)
+        TEST_ERROR
+
+    /* Write file's data from memory */
+    if(HDwrite(fd, file_data, (size_t)sb.st_size) < (ssize_t)sb.st_size)
+        TEST_ERROR
+
+    /* Close the file */
+    if(HDclose(fd) < 0)
+        TEST_ERROR
+    fd = -1;
+
+
+
+    /* Print banner for this test */
+    TESTING("B-tree remove: create random level 4 B-tree and delete all records by index, in decreasing order");
+
     /* Re-open the file */
     if((file = H5Fopen(filename, H5F_ACC_RDWR, fapl)) < 0)
         FAIL_STACK_ERROR
@@ -6614,21 +6693,14 @@ HDfprintf(stderr, "curr_time = %lu\n", (unsigned long)curr_time);
 
     /* Remove all records */
     for(u = 0; u < INSERT_MANY; u++) {
-        /* Pick a record index to remove from randomly */
-        rem_idx = (unsigned)(HDrandom() % (INSERT_MANY - u));
+        /* Remove last record */
         rrecord = HSIZET_MAX;
-        if(H5B2_remove_by_idx(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_INC, (hsize_t)rem_idx, remove_cb, &rrecord) < 0)
+        if(H5B2_remove_by_idx(f, H5P_DATASET_XFER_DEFAULT, H5B2_TEST, bt2_addr, H5_ITER_DEC, (hsize_t)0, remove_cb, &rrecord) < 0)
             FAIL_STACK_ERROR
 
         /* Make certain that the record value is correct */
-        if(rrecord >= INSERT_MANY)
-{
-HDfprintf(stderr, "u = %u\n", u);
-HDfprintf(stderr, "rem_idx = %u\n", rem_idx);
-HDfprintf(stderr, "rrecord = %Hu\n", rrecord);
-HDfprintf(stderr, "curr_time = %lu\n", (unsigned long)curr_time);
+        if(rrecord != (INSERT_MANY - (u + 1)))
             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)
@@ -6654,6 +6726,7 @@ HDfprintf(stderr, "curr_time = %lu\n", (unsigned long)curr_time);
     PASSED();
 
     HDfree(records);
+    HDfree(file_data);
 
     return 0;
 
@@ -6662,10 +6735,13 @@ error:
 	H5Fclose(file);
     } H5E_END_TRY;
 
+    if(fd > 0)
+        HDclose(fd);
     HDfree(records);
+    HDfree(file_data);
 
     return 1;
-} /* test_remove_by_idx() */
+} /* test_remove_lots() */
 
 
 /*-------------------------------------------------------------------------
@@ -7432,13 +7508,6 @@ main(void)
 	else
 	    nerrors += test_remove_lots(fapl);
 
-#ifdef QAK
-        /* Test removing records by index */
-        nerrors += test_remove_by_idx(fapl);
-#else /* QAK */
-HDfprintf(stderr, "Uncomment tests!\n");
-#endif /* QAK */
-
 	/* Test more complex B-tree queries */
 	nerrors += test_find_neighbor(fapl);