[svn-r10421] Purpose:

    New feature & code cleanup

Description:
    Add feature to find first block >= a certain size (useful for allocating
space)

    Cleaned up various comments, etc.

Platforms tested:
    FreeBSD 4.11 (sleipnir)
    Solaris 2.9 (shanti)

6 files changed, 231 insertions, 11 deletions

diff --git a/src/H5BT.c b/src/H5BT.c
index acbb9f3..2373b9e 100644
--- a/src/H5BT.c
+++ b/src/H5BT.c
@@ -41,6 +41,12 @@
 
 /* Local typedefs */
 
+/* Struct for locating blocks */
+typedef struct {
+    hsize_t search_size;        /* Size of block to search for */
+    H5BT_blk_info_t found;      /* Information for block found */
+} H5BT_locate_t;
+
 /* Local prototypes */
 
 /* Package variables */
@@ -97,7 +103,7 @@ H5BT_create(H5F_t *f, hid_t dxpl_id, haddr_t *addr_p)
     if (H5B2_create(f, dxpl_id, H5B2_BLKTRK, H5BT_BT2_NODE_SIZE, H5BT_BT2_RREC_SIZE(f), H5BT_BT2_SPLIT_PERC, H5BT_BT2_MERGE_PERC, &bt->bt2_addr/*out*/)<0)
 	HGOTO_ERROR(H5E_BLKTRK, H5E_CANTINIT, FAIL, "can't create B-tree for storing block info")
 
-    /* Cache the new B-tree node */
+    /* Cache the new block tracker node */
     if (H5AC_set(f, dxpl_id, H5AC_BLTR, *addr_p, bt, H5AC__NO_FLAGS_SET) < 0)
 	HGOTO_ERROR(H5E_BLKTRK, H5E_CANTINIT, FAIL, "can't add block tracker info to cache")
 
@@ -647,6 +653,100 @@ done:
 
 
 /*-------------------------------------------------------------------------
+ * Function:	H5BT_locate_cb
+ *
+ * Purpose:	v2 B-tree find callback
+ *
+ * Return:	Success:	0
+ *
+ *		Failure:	1
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, March 11, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+H5BT_locate_cb(const void *_record, void *_op_data)
+{
+    const H5BT_blk_info_t *record = (const H5BT_blk_info_t *)_record;
+    H5BT_locate_t *search = (H5BT_locate_t *)_op_data;
+    int ret_value;              /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BT_locate_cb)
+
+    /* Check if we've found a block that's big enough */
+    if (record->len >= search->search_size) {
+        search->found = *record;
+        ret_value = H5B2_ITER_STOP;
+    } /* end if */
+    else
+        ret_value = H5B2_ITER_CONT;
+
+    FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5BT_locate_cb() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BT_locate
+ *
+ * Purpose:	Locate first block that is at least a certain size
+ *
+ * Return:	Non-negative on success, negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Mar 24 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+htri_t
+H5BT_locate(H5F_t *f, hid_t dxpl_id, haddr_t addr, hsize_t size, haddr_t *locate_addr, hsize_t *locate_size)
+{
+    H5BT_t *bt = NULL;                  /* The new B-tree header information */
+    H5BT_locate_t found;                /* Block info found */
+    htri_t ret_value=TRUE;
+
+    FUNC_ENTER_NOAPI(H5BT_locate, FAIL)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+
+    /* Look up the block tracker header */
+    if (NULL == (bt = H5AC_protect(f, dxpl_id, H5AC_BLTR, addr, NULL, NULL, H5AC_WRITE)))
+	HGOTO_ERROR(H5E_BLKTRK, H5E_CANTPROTECT, FAIL, "unable to load block tracker info")
+
+    /* Iterate through blocks, looking for first one that is large enough */
+    found.search_size = size;
+    found.found.addr = HADDR_UNDEF;
+    if (H5B2_iterate(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, H5BT_locate_cb, &found) < 0)
+	HGOTO_ERROR(H5E_BLKTRK, H5E_NOTFOUND, FAIL, "unable to locate block")
+
+    /* Update user's information, if block was found */
+    if(H5F_addr_defined(found.found.addr)) {
+        if(locate_addr)
+            *locate_addr = found.found.addr;
+        if(locate_size)
+            *locate_size = found.found.len;
+    } /* end if */
+    else
+        ret_value = FALSE;
+
+done:
+    /* Release the block tracker info */
+    if (bt && H5AC_unprotect(f, dxpl_id, H5AC_BLTR, addr, bt, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BLKTRK, H5E_CANTUNPROTECT, FAIL, "unable to release block tracker info")
+    
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5BT_locate() */
+
+
+/*-------------------------------------------------------------------------
  * Function:	H5BT_delete
  *
  * Purpose:	Delete a block tracker from a file
diff --git a/src/H5BTcache.c b/src/H5BTcache.c
index 60c31b3..f5f6a4e 100644
--- a/src/H5BTcache.c
+++ b/src/H5BTcache.c
@@ -23,7 +23,7 @@
  *-------------------------------------------------------------------------
  */
 
-#define H5BT_PACKAGE		/*suppress error about including H5B2pkg  */
+#define H5BT_PACKAGE		/*suppress error about including H5SHpkg  */
 
 /* Private headers */
 #include "H5private.h"		/* Generic Functions			*/
@@ -99,7 +99,7 @@ H5BT_cache_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void UNUSED *udata1
 	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
     HDmemset(&bt->cache_info,0,sizeof(H5AC_info_t));
 
-    /* Compute the size of the B-tree header on disk */
+    /* Compute the size of the block tracker on disk */
     size = H5BT_SIZE(f);
 
     /* Allocate temporary buffer */
@@ -180,7 +180,7 @@ H5BT_cache_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BT_t
         uint8_t *p;                 /* Pointer into raw data buffer */
         size_t	size;
 
-        /* Compute the size of the B-tree header on disk */
+        /* Compute the size of the block tracker info on disk */
         size = H5BT_SIZE(f);
 
         /* Allocate temporary buffer */
@@ -232,7 +232,7 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B_cache_dest
+ * Function:	H5BT_cache_dest
  *
  * Purpose:	Destroys a block tracker in memory.
  *
diff --git a/src/H5BTdbg.c b/src/H5BTdbg.c
index a926801..16c497b 100644
--- a/src/H5BTdbg.c
+++ b/src/H5BTdbg.c
@@ -27,7 +27,7 @@
 
 /* Private headers */
 #include "H5private.h"		/* Generic Functions			*/
-#include "H5BTpkg.h"		/* B-trees				*/
+#include "H5BTpkg.h"		/* Block tracker			*/
 #include "H5Eprivate.h"		/* Error handling		  	*/
 
 
@@ -100,5 +100,5 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release block tracker info")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5BT_debug() */
+} /* end H5BT_hdr_debug() */
 
diff --git a/src/H5BTpkg.h b/src/H5BTpkg.h
index 5ceb904..e9140ec 100644
--- a/src/H5BTpkg.h
+++ b/src/H5BTpkg.h
@@ -28,7 +28,7 @@
 #define _H5BTpkg_H
 
 /* Get package's private header */
-#include "H5BTprivate.h"
+#include "H5BTprivate.h"	/* Block tracker 			*/
 
 /* Other private headers needed by this file */
 #include "H5ACprivate.h"	/* Metadata cache			*/
diff --git a/src/H5BTprivate.h b/src/H5BTprivate.h
index b98aac1..f6470e5 100644
--- a/src/H5BTprivate.h
+++ b/src/H5BTprivate.h
@@ -52,8 +52,9 @@ H5_DLL herr_t H5BT_remove(H5F_t *f, hid_t dxpl_id, haddr_t addr, haddr_t offset,
     hsize_t length);
 H5_DLL herr_t H5BT_get_total_size(H5F_t *f, hid_t dxpl_id, haddr_t addr,
     hsize_t *tot_size);
+H5_DLL herr_t H5BT_locate(H5F_t *f, hid_t dxpl_id, haddr_t addr, hsize_t size,
+    haddr_t *locate_addr, hsize_t *locate_size);
 H5_DLL herr_t H5BT_delete(H5F_t *f, hid_t dxpl_id, haddr_t addr);
 
 #endif /* _H5BTprivate_H */
 
-
diff --git a/test/blocktrack.c b/test/blocktrack.c
index 99586b0..d78f5b5 100644
--- a/test/blocktrack.c
+++ b/test/blocktrack.c
@@ -1430,6 +1430,122 @@ error:
 
 
 /*-------------------------------------------------------------------------
+ * Function:	test_locate
+ *
+ * Purpose:	Basic tests for the block tracker code
+ *
+ * Return:	Success:	0
+ *
+ *		Failure:	1
+ *
+ * Programmer:	Quincey Koziol
+ *              Monday, March 24, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+test_locate(hid_t fapl)
+{
+    hid_t	file=-1;
+    char	filename[1024];
+    H5F_t	*f=NULL;
+    haddr_t     bt_addr;                /* Address of block tracker created */
+    haddr_t     block_addr;             /* Address of block to insert */
+    hsize_t     block_size;             /* Size of block to insert */
+    hsize_t     search_size;            /* Size of block to search for */
+    unsigned    u;                      /* Local index variable */
+
+    h5_fixname(FILENAME[0], fapl, filename, sizeof filename);
+
+    /* Create the file to work on */
+    if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR;
+	
+    /* Get a pointer to the internal file object */
+    if (NULL==(f=H5I_object(file))) {
+	H5Eprint_stack(H5E_DEFAULT, stdout);
+	TEST_ERROR;
+    } /* end if */
+
+    if (H5BT_create(f, H5P_DATASET_XFER_DEFAULT, &bt_addr/*out*/)<0) {
+	H5_FAILED();
+	H5Eprint_stack(H5E_DEFAULT, stdout);
+	goto error;
+    } /* end if */
+
+    /* Insert blocks */
+    block_addr = 2048;
+    block_size = 8;
+    for(u = 0; u < 10; u++) {
+        if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, block_addr, block_size)<0) {
+            H5_FAILED();
+            H5Eprint_stack(H5E_DEFAULT, stdout);
+            goto error;
+        } /* end if */
+
+        /* Increment block address & size for next insertion */
+        block_addr *= 2;
+        block_size *= 2;
+    } /* end for */
+
+    TESTING("attempt to locate too large of a block");
+
+    search_size = block_size * 2;
+    block_addr = HADDR_UNDEF;
+    if (H5BT_locate(f, H5P_DATASET_XFER_DEFAULT, bt_addr, search_size, &block_addr, &block_size)<0) {
+        H5_FAILED();
+        H5Eprint_stack(H5E_DEFAULT, stdout);
+        goto error;
+    } /* end if */
+    if(H5F_addr_defined(block_addr)) TEST_ERROR;
+
+    PASSED();
+
+    TESTING("locate blocks");
+
+    search_size = 8;
+    if (H5BT_locate(f, H5P_DATASET_XFER_DEFAULT, bt_addr, search_size, &block_addr, &block_size)<0) {
+        H5_FAILED();
+        H5Eprint_stack(H5E_DEFAULT, stdout);
+        goto error;
+    } /* end if */
+    if(block_addr != 2048) TEST_ERROR;
+    if(block_size != 8) TEST_ERROR;
+
+    search_size = 10;
+    if (H5BT_locate(f, H5P_DATASET_XFER_DEFAULT, bt_addr, search_size, &block_addr, &block_size)<0) {
+        H5_FAILED();
+        H5Eprint_stack(H5E_DEFAULT, stdout);
+        goto error;
+    } /* end if */
+    if(block_addr != 4096) TEST_ERROR;
+    if(block_size != 16) TEST_ERROR;
+
+    search_size = 100;
+    if (H5BT_locate(f, H5P_DATASET_XFER_DEFAULT, bt_addr, search_size, &block_addr, &block_size)<0) {
+        H5_FAILED();
+        H5Eprint_stack(H5E_DEFAULT, stdout);
+        goto error;
+    } /* end if */
+    if(block_addr != 32768) TEST_ERROR;
+    if(block_size != 128) TEST_ERROR;
+
+    PASSED();
+
+    if (H5Fclose(file)<0) TEST_ERROR;
+
+    return 0;
+
+error:
+    H5E_BEGIN_TRY {
+	H5Fclose(file);
+    } H5E_END_TRY;
+    return 1;
+} /* test_locate() */
+
+
+/*-------------------------------------------------------------------------
  * Function:	test_delete
  *
  * Purpose:	Basic tests for the block tracker code
@@ -1469,7 +1585,7 @@ test_delete(hid_t fapl)
     /* Get the size of an empty file */
     if((empty_size=h5_get_file_size(filename))==0) TEST_ERROR;
 
-    TESTING("delete: delete empty block tracker");
+    TESTING("delete empty block tracker");
 
     /* Create the file to work on */
     if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR;
@@ -1505,7 +1621,7 @@ test_delete(hid_t fapl)
 
     PASSED();
 
-    TESTING("delete: delete block tracker with many blocks");
+    TESTING("delete block tracker with many blocks");
 
     /* Create the file to work on */
     if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR;
@@ -1600,6 +1716,9 @@ main(void)
     nerrors += test_remove_whole(fapl);
     nerrors += test_remove_partial_begin(fapl);
 
+    /* Test block tracker locate */
+    nerrors += test_locate(fapl);
+
     /* Test block tracker deletion */
     nerrors += test_delete(fapl);