[svn-r11967] Purpose:

    New feature

Description:
    Check in initial "fractal heap" code, for supporting the group redesign.

    Also, remove some remnants of the segmented heap/block tracker/B+tree code
which I didn't find during the last pass.

Platforms tested:
    FreeBSD 4.11 (sleipnir)
    Mac OSX (amazon)
    Linux 2.4

3 files changed, 290 insertions, 31 deletions

diff --git a/test/Makefile.am b/test/Makefile.am
index 8e22514..c924995 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -32,7 +32,7 @@ SCRIPT_DEPEND = error_test$(EXEEXT) err_compat$(EXEEXT)
 # executed, generally most specific tests to least specific tests.
 # As an exception, long-running tests should occur earlier in the list.
 # This gives them more time to run when tests are executing in parallel.
-TEST_PROG=testhdf5 lheap ohdr stab gheap btree2 cache cache_api \
+TEST_PROG=testhdf5 lheap fheap ohdr stab gheap btree2 cache cache_api \
            pool hyperslab istore bittests dt_arith \
            dtypes dsets cmpd_dset extend external objcopy links unlink big mtime     \
            fillval mount flush1 flush2 enum \
@@ -94,7 +94,7 @@ flush2.chkexe_: flush1.chkexe_
 # prefix or low-level driver with environment variables will influence 
 # the temporary file name in ways that the makefile is not aware of.
 CHECK_CLEANFILES+=cmpd_dset.h5 compact_dataset.h5 dataset.h5 extend.h5 istore.h5\
-            tfile[1-4].h5 th5s[1-3].h5 lheap.h5 ohdr.h5 stab[1-2].h5 \
+            tfile[1-4].h5 th5s[1-3].h5 lheap.h5 fheap.h5 ohdr.h5 stab[1-2].h5 \
             extern_[1-3].h5 extern_[1-4][ab].raw gheap[0-4].h5 dt_arith[1-2]\
             links.h5 links[1-3].h5 big.data big[0-9][0-9][0-9][0-9][0-9].h5  \
             dtypes[1-8].h5 dt_arith[1-2].h5 tattr.h5 tselect.h5 mtime.h5 \
diff --git a/test/Makefile.in b/test/Makefile.in
index 2be16e9..7be578d 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -31,7 +31,7 @@
 #
 
 
-SOURCES = $(libh5test_la_SOURCES) big.c bittests.c btree2.c cache.c cache_api.c cmpd_dset.c dangle.c dsets.c dt_arith.c dtransform.c dtypes.c enum.c err_compat.c error_test.c extend.c external.c fillval.c flush1.c flush2.c gen_deflate.c gen_filters.c gen_new_array.c gen_new_fill.c gen_new_group.c gen_new_mtime.c gen_new_super.c gen_noencoder.c gen_nullspace.c getname.c gheap.c hyperslab.c istore.c lheap.c links.c mount.c mtime.c ntypes.c objcopy.c ohdr.c pool.c reserved.c set_extent.c space_overflow.c stab.c stream_test.c $(testhdf5_SOURCES) testmeta.c $(ttsafe_SOURCES) unlink.c vfd.c
+SOURCES = $(libh5test_la_SOURCES) big.c bittests.c btree2.c cache.c cache_api.c cmpd_dset.c dangle.c dsets.c dt_arith.c dtransform.c dtypes.c enum.c err_compat.c error_test.c extend.c external.c fheap.c fillval.c flush1.c flush2.c gen_deflate.c gen_filters.c gen_new_array.c gen_new_fill.c gen_new_group.c gen_new_mtime.c gen_new_super.c gen_noencoder.c gen_nullspace.c getname.c gheap.c hyperslab.c istore.c lheap.c links.c mount.c mtime.c ntypes.c objcopy.c ohdr.c pool.c reserved.c set_extent.c space_overflow.c stab.c stream_test.c $(testhdf5_SOURCES) testmeta.c $(ttsafe_SOURCES) unlink.c vfd.c
 
 srcdir = @srcdir@
 top_srcdir = @top_srcdir@
@@ -73,14 +73,14 @@ LTLIBRARIES = $(noinst_LTLIBRARIES)
 libh5test_la_LIBADD =
 am_libh5test_la_OBJECTS = h5test.lo testframe.lo cache_common.lo
 libh5test_la_OBJECTS = $(am_libh5test_la_OBJECTS)
-am__EXEEXT_1 = testhdf5$(EXEEXT) lheap$(EXEEXT) ohdr$(EXEEXT) \
-	stab$(EXEEXT) gheap$(EXEEXT) btree2$(EXEEXT) cache$(EXEEXT) \
-	cache_api$(EXEEXT) pool$(EXEEXT) hyperslab$(EXEEXT) \
-	istore$(EXEEXT) bittests$(EXEEXT) dt_arith$(EXEEXT) \
-	dtypes$(EXEEXT) dsets$(EXEEXT) cmpd_dset$(EXEEXT) \
-	extend$(EXEEXT) external$(EXEEXT) objcopy$(EXEEXT) \
-	links$(EXEEXT) unlink$(EXEEXT) big$(EXEEXT) mtime$(EXEEXT) \
-	fillval$(EXEEXT) mount$(EXEEXT) flush1$(EXEEXT) \
+am__EXEEXT_1 = testhdf5$(EXEEXT) lheap$(EXEEXT) fheap$(EXEEXT) \
+	ohdr$(EXEEXT) stab$(EXEEXT) gheap$(EXEEXT) btree2$(EXEEXT) \
+	cache$(EXEEXT) cache_api$(EXEEXT) pool$(EXEEXT) \
+	hyperslab$(EXEEXT) istore$(EXEEXT) bittests$(EXEEXT) \
+	dt_arith$(EXEEXT) dtypes$(EXEEXT) dsets$(EXEEXT) \
+	cmpd_dset$(EXEEXT) extend$(EXEEXT) external$(EXEEXT) \
+	objcopy$(EXEEXT) links$(EXEEXT) unlink$(EXEEXT) big$(EXEEXT) \
+	mtime$(EXEEXT) fillval$(EXEEXT) mount$(EXEEXT) flush1$(EXEEXT) \
 	flush2$(EXEEXT) enum$(EXEEXT) set_extent$(EXEEXT) \
 	ttsafe$(EXEEXT) stream_test$(EXEEXT) getname$(EXEEXT) \
 	vfd$(EXEEXT) ntypes$(EXEEXT) dangle$(EXEEXT) \
@@ -161,6 +161,10 @@ external_SOURCES = external.c
 external_OBJECTS = external.$(OBJEXT)
 external_LDADD = $(LDADD)
 external_DEPENDENCIES = libh5test.la $(am__DEPENDENCIES_1)
+fheap_SOURCES = fheap.c
+fheap_OBJECTS = fheap.$(OBJEXT)
+fheap_LDADD = $(LDADD)
+fheap_DEPENDENCIES = libh5test.la $(am__DEPENDENCIES_1)
 fillval_SOURCES = fillval.c
 fillval_OBJECTS = fillval.$(OBJEXT)
 fillval_LDADD = $(LDADD)
@@ -320,25 +324,25 @@ LINK = $(LIBTOOL) --tag=CC --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) \
 SOURCES = $(libh5test_la_SOURCES) big.c bittests.c btree2.c cache.c \
 	cache_api.c cmpd_dset.c dangle.c dsets.c dt_arith.c \
 	dtransform.c dtypes.c enum.c err_compat.c error_test.c \
-	extend.c external.c fillval.c flush1.c flush2.c gen_deflate.c \
-	gen_filters.c gen_new_array.c gen_new_fill.c gen_new_group.c \
-	gen_new_mtime.c gen_new_super.c gen_noencoder.c \
-	gen_nullspace.c getname.c gheap.c hyperslab.c istore.c lheap.c \
-	links.c mount.c mtime.c ntypes.c objcopy.c ohdr.c pool.c \
-	reserved.c set_extent.c space_overflow.c stab.c stream_test.c \
-	$(testhdf5_SOURCES) testmeta.c $(ttsafe_SOURCES) unlink.c \
-	vfd.c
+	extend.c external.c fheap.c fillval.c flush1.c flush2.c \
+	gen_deflate.c gen_filters.c gen_new_array.c gen_new_fill.c \
+	gen_new_group.c gen_new_mtime.c gen_new_super.c \
+	gen_noencoder.c gen_nullspace.c getname.c gheap.c hyperslab.c \
+	istore.c lheap.c links.c mount.c mtime.c ntypes.c objcopy.c \
+	ohdr.c pool.c reserved.c set_extent.c space_overflow.c stab.c \
+	stream_test.c $(testhdf5_SOURCES) testmeta.c $(ttsafe_SOURCES) \
+	unlink.c vfd.c
 DIST_SOURCES = $(libh5test_la_SOURCES) big.c bittests.c btree2.c \
 	cache.c cache_api.c cmpd_dset.c dangle.c dsets.c dt_arith.c \
 	dtransform.c dtypes.c enum.c err_compat.c error_test.c \
-	extend.c external.c fillval.c flush1.c flush2.c gen_deflate.c \
-	gen_filters.c gen_new_array.c gen_new_fill.c gen_new_group.c \
-	gen_new_mtime.c gen_new_super.c gen_noencoder.c \
-	gen_nullspace.c getname.c gheap.c hyperslab.c istore.c lheap.c \
-	links.c mount.c mtime.c ntypes.c objcopy.c ohdr.c pool.c \
-	reserved.c set_extent.c space_overflow.c stab.c stream_test.c \
-	$(testhdf5_SOURCES) testmeta.c $(ttsafe_SOURCES) unlink.c \
-	vfd.c
+	extend.c external.c fheap.c fillval.c flush1.c flush2.c \
+	gen_deflate.c gen_filters.c gen_new_array.c gen_new_fill.c \
+	gen_new_group.c gen_new_mtime.c gen_new_super.c \
+	gen_noencoder.c gen_nullspace.c getname.c gheap.c hyperslab.c \
+	istore.c lheap.c links.c mount.c mtime.c ntypes.c objcopy.c \
+	ohdr.c pool.c reserved.c set_extent.c space_overflow.c stab.c \
+	stream_test.c $(testhdf5_SOURCES) testmeta.c $(ttsafe_SOURCES) \
+	unlink.c vfd.c
 ETAGS = etags
 CTAGS = ctags
 DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST)
@@ -586,9 +590,9 @@ TRACE = perl $(top_srcdir)/bin/trace
 # the temporary file name in ways that the makefile is not aware of.
 CHECK_CLEANFILES = *.chkexe *.chklog *.clog cmpd_dset.h5 \
 	compact_dataset.h5 dataset.h5 extend.h5 istore.h5 \
-	tfile[1-4].h5 th5s[1-3].h5 lheap.h5 ohdr.h5 stab[1-2].h5 \
-	extern_[1-3].h5 extern_[1-4][ab].raw gheap[0-4].h5 \
-	dt_arith[1-2] links.h5 links[1-3].h5 big.data \
+	tfile[1-4].h5 th5s[1-3].h5 lheap.h5 fheap.h5 ohdr.h5 \
+	stab[1-2].h5 extern_[1-3].h5 extern_[1-4][ab].raw \
+	gheap[0-4].h5 dt_arith[1-2] links.h5 links[1-3].h5 big.data \
 	big[0-9][0-9][0-9][0-9][0-9].h5 dtypes[1-8].h5 \
 	dt_arith[1-2].h5 tattr.h5 tselect.h5 mtime.h5 unlink.h5 \
 	unicode.h5 fillval_[0-9].h5 fillval.raw mount_[0-9].h5 \
@@ -612,7 +616,7 @@ SCRIPT_DEPEND = error_test$(EXEEXT) err_compat$(EXEEXT)
 # executed, generally most specific tests to least specific tests.
 # As an exception, long-running tests should occur earlier in the list.
 # This gives them more time to run when tests are executing in parallel.
-TEST_PROG = testhdf5 lheap ohdr stab gheap btree2 cache cache_api \
+TEST_PROG = testhdf5 lheap fheap ohdr stab gheap btree2 cache cache_api \
            pool hyperslab istore bittests dt_arith \
            dtypes dsets cmpd_dset extend external objcopy links unlink big mtime     \
            fillval mount flush1 flush2 enum \
@@ -773,6 +777,9 @@ extend$(EXEEXT): $(extend_OBJECTS) $(extend_DEPENDENCIES)
 external$(EXEEXT): $(external_OBJECTS) $(external_DEPENDENCIES) 
 	@rm -f external$(EXEEXT)
 	$(LINK) $(external_LDFLAGS) $(external_OBJECTS) $(external_LDADD) $(LIBS)
+fheap$(EXEEXT): $(fheap_OBJECTS) $(fheap_DEPENDENCIES) 
+	@rm -f fheap$(EXEEXT)
+	$(LINK) $(fheap_LDFLAGS) $(fheap_OBJECTS) $(fheap_LDADD) $(LIBS)
 fillval$(EXEEXT): $(fillval_OBJECTS) $(fillval_DEPENDENCIES) 
 	@rm -f fillval$(EXEEXT)
 	$(LINK) $(fillval_LDFLAGS) $(fillval_OBJECTS) $(fillval_LDADD) $(LIBS)
@@ -899,6 +906,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/error_test.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/extend.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/external.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fheap.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fillval.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/flush1.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/flush2.Po@am__quote@
diff --git a/test/fheap.c b/test/fheap.c
new file mode 100644
index 0000000..b1fce69
--- /dev/null
+++ b/test/fheap.c
@@ -0,0 +1,251 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * Copyright by the Board of Trustees of the University of Illinois.         *
+ * All rights reserved.                                                      *
+ *                                                                           *
+ * This file is part of HDF5.  The full HDF5 copyright notice, including     *
+ * terms governing use, modification, and redistribution, is contained in    *
+ * the files COPYING and Copyright.html.  COPYING can be found at the root   *
+ * of the source code distribution tree; Copyright.html can be found at the  *
+ * root level of an installed copy of the electronic HDF5 document set and   *
+ * is linked from the top-level documents page.  It can also be found at     *
+ * http://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html.  If you do not have     *
+ * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/* Programmer:  Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *              Friday, February 24, 2006
+ */
+#include "h5test.h"
+
+/*
+ * This file needs to access private datatypes from the H5HF package.
+ * This file also needs to access the fractal heap testing code.
+ */
+#define H5HF_PACKAGE
+#define H5HF_TESTING
+#include "H5HFpkg.h"
+
+/* Other private headers that this test requires */
+#include "H5Iprivate.h"
+
+const char *FILENAME[] = {
+    "fheap",
+    NULL
+};
+
+
+/*-------------------------------------------------------------------------
+ * Function:	test_create
+ *
+ * Purpose:	Create fractal heap
+ *
+ * Return:	Success:	0
+ *
+ *		Failure:	1
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, February 24, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+test_create(hid_t fapl)
+{
+    hid_t	file = -1;              /* File ID */
+    char	filename[1024];         /* Filename to use */
+    H5F_t	*f = NULL;              /* Internal file object pointer */
+    H5HF_type_t heap_type, test_heap_type; /* Type of address mapping for fractal heap */
+    haddr_t     fh_addr;                /* Address of fractal heap created */
+
+    /* Set the filename to use for this test (dependent on fapl) */
+    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)))
+        STACK_ERROR
+
+    /*
+     * Test fractal heap creation (w/absolute address mapping)
+     */
+    TESTING("Fractal heap creation (w/absolute address mapping)");
+    heap_type = H5HF_ABSOLUTE;
+    if(H5HF_create(f, H5P_DATASET_XFER_DEFAULT, heap_type, &fh_addr/*out*/) < 0)
+        FAIL_STACK_ERROR
+    if(!H5F_addr_defined(fh_addr))
+        FAIL_STACK_ERROR
+    PASSED()
+
+    /* Query the type of address mapping */
+    TESTING("Query absolute address mapping setting");
+    test_heap_type = H5HF_MAPPED;
+    if(H5HF_get_addrmap_test(f, H5P_DATASET_XFER_DEFAULT, fh_addr, &test_heap_type) < 0)
+        FAIL_STACK_ERROR
+    if(test_heap_type != heap_type)
+        FAIL_STACK_ERROR
+    PASSED()
+
+    /*
+     * Test fractal heap creation (w/mapped address mapping)
+     */
+    TESTING("Fractal heap creation (w/mapped address mapping)");
+    heap_type = H5HF_MAPPED;
+    if(H5HF_create(f, H5P_DATASET_XFER_DEFAULT, heap_type, &fh_addr/*out*/) < 0)
+        FAIL_STACK_ERROR
+    if(!H5F_addr_defined(fh_addr))
+        FAIL_STACK_ERROR
+    PASSED()
+
+    /* Query the type of address mapping */
+    TESTING("Query mapped address mapping setting");
+    test_heap_type = H5HF_ABSOLUTE;
+    if(H5HF_get_addrmap_test(f, H5P_DATASET_XFER_DEFAULT, fh_addr, &test_heap_type) < 0)
+        FAIL_STACK_ERROR
+    if(test_heap_type != heap_type)
+        FAIL_STACK_ERROR
+    PASSED()
+
+    /* Close the file */
+    if(H5Fclose(file) < 0)
+        TEST_ERROR
+
+    /* All tests passed */
+    return(0);
+
+error:
+    H5E_BEGIN_TRY {
+	H5Fclose(file);
+    } H5E_END_TRY;
+    return(1);
+} /* test_create() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	test_abs_insert_first
+ *
+ * Purpose:	Test inserting first object into absolute heap
+ *
+ * Return:	Success:	0
+ *
+ *		Failure:	1
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, February 24, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+test_abs_insert_first(hid_t fapl)
+{
+    hid_t	file = -1;              /* File ID */
+    hid_t       dxpl = H5P_DATASET_XFER_DEFAULT;     /* DXPL to use */
+    char	filename[1024];         /* Filename to use */
+    H5F_t	*f = NULL;              /* Internal file object pointer */
+    haddr_t     fh_addr;                /* Address of fractal heap created */
+    unsigned char obj[10];              /* Buffer for object to insert */
+    haddr_t     heap_id;                /* Heap ID for object inserted */
+    unsigned    u;                      /* Local index variable */
+    herr_t      ret;                    /* Generic error return value */
+
+    /* Set the filename to use for this test (dependent on fapl) */
+    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)))
+        STACK_ERROR
+
+    /* Create absolute heap */
+    if(H5HF_create(f, dxpl, H5HF_ABSOLUTE, &fh_addr/*out*/) < 0)
+        FAIL_STACK_ERROR
+    if(!H5F_addr_defined(fh_addr))
+        FAIL_STACK_ERROR
+#ifdef QAK
+HDfprintf(stdout, "Fractal heap header address = %a\n", fh_addr);
+#endif /* QAK */
+
+    /* Initialize object buffer */
+    for(u = 0; u < sizeof(obj); u++)
+        obj[u] = u;
+
+    /*
+     * Test inserting first (small) object into absolute heap
+     */
+    TESTING("Inserting first (small) object into absolute heap");
+    heap_id = HADDR_UNDEF;
+    if(H5HF_insert(f, dxpl, fh_addr, sizeof(obj), obj, &heap_id) < 0)
+        FAIL_STACK_ERROR
+#ifdef QAK
+HDfprintf(stdout, "heap_id = %a\n", heap_id);
+#endif /* QAK */
+    PASSED()
+
+    /* Close the file */
+    if(H5Fclose(file) < 0)
+        TEST_ERROR
+
+    /* All tests passed */
+    return(0);
+
+error:
+    H5E_BEGIN_TRY {
+	H5Fclose(file);
+    } H5E_END_TRY;
+    return(1);
+} /* test_abs_insert_first() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	main
+ *
+ * Purpose:	Test the fractal heap code
+ *
+ * Return:	Success:
+ *
+ *		Failure:
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, February 24, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+int
+main(void)
+{
+    hid_t	fapl = -1;              /* File access property list for data files */
+    unsigned	nerrors = 0;            /* Cumulative error count */
+
+    /* Reset library */
+    h5_reset();
+    fapl = h5_fileaccess();
+
+    /* Test fractal heap creation */
+    nerrors += test_create(fapl);
+
+    /* Test fractal heap object insertion */
+    nerrors += test_abs_insert_first(fapl);
+
+    if(nerrors)
+        goto error;
+    puts("All fractal heap tests passed.");
+#ifndef QAK
+    h5_cleanup(FILENAME, fapl);
+#else /* QAK */
+HDfprintf(stderr, "Uncomment cleanup!\n");
+#endif /* QAK */
+    return 0;
+
+error:
+    puts("*** TESTS FAILED ***");
+    H5E_BEGIN_TRY {
+	H5Pclose(fapl);
+    } H5E_END_TRY;
+    return 1;
+}
+