[svn-r9928] Purpose:

    New feature

Description:
    Add basic code for new B-tree implementation.  They don't do much yet,
aren't hooked up to anything yet and the format may change, but I'd like to
start getting them into the daily tests.

Platforms tested:
    FreeBSD 4.11 (sleipnir) w/parallel
    Too minor to require h5committest

10 files changed, 1840 insertions, 29 deletions

diff --git a/src/H5ACprivate.h b/src/H5ACprivate.h
index b26bd1e..51f5b5a 100644
--- a/src/H5ACprivate.h
+++ b/src/H5ACprivate.h
@@ -44,7 +44,9 @@
 #define H5AC_LHEAP_ID	2	/*local heap				     */
 #define H5AC_GHEAP_ID	3	/*global heap				     */
 #define H5AC_OHDR_ID	4	/*object header				     */
-#define H5AC_NTYPES	5	
+#define H5AC_BT2_HDR_ID	5	/*v2 B-tree header			     */
+#define H5AC_BT2_LEAF_ID 6	/*v2 B-tree leaf			     */
+#define H5AC_NTYPES	7	
 
 /* H5AC_DUMP_STATS_ON_CLOSE should always be FALSE when 
  * H5C_COLLECT_CACHE_STATS is FALSE.  
diff --git a/src/H5B2.c b/src/H5B2.c
new file mode 100644
index 0000000..1307c07
--- /dev/null
+++ b/src/H5B2.c
@@ -0,0 +1,1176 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*-------------------------------------------------------------------------
+ *
+ * Created:		H5B2.c
+ *			Jan 31 2005
+ *			Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:		Implements a B-tree, with several modifications from
+ *                      the "standard" methods.
+ *
+ *                      Please see the documentation in:
+ *                      doc/html/TechNotes/Btrees.html for a full description
+ *                      of how they work, etc.
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#define H5B2_PACKAGE		/*suppress error about including H5B2pkg  */
+
+/* Private headers */
+#include "H5private.h"		/* Generic Functions			*/
+#include "H5B2pkg.h"		/* B-trees				*/
+#include "H5Eprivate.h"		/* Error handling		  	*/
+#include "H5MFprivate.h"	/* File memory management		*/
+
+/* Local macros */
+
+/* B-tree version #'s */
+#define H5B2_HDR_VERSION 0              /* Header */
+#define H5B2_LEAF_VERSION 0             /* Leaf node */
+
+/* Size of storage for number of records per node (on disk) */
+#define H5B2_SIZEOF_RECORDS_PER_NODE    2
+
+/* Size of a "node pointer" (on disk) */
+#define H5B2_NODE_POINTER_SIZE(f)       (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE+H5F_SIZEOF_SIZE(f))
+
+/* Format overhead for each node (on disk) */
+#define H5B2_OVERHEAD_SIZE              (H5B2_SIZEOF_MAGIC+1)   /* Signature + version # */
+
+/* Number of records that fit into internal node */
+#define H5B2_NUM_INT_REC(f,n,r)         (((n)-(H5B2_OVERHEAD_SIZE+H5B2_NODE_POINTER_SIZE(f)))/((r)+H5B2_NODE_POINTER_SIZE(f)))
+
+/* Number of records that fit into leaf node */
+#define H5B2_NUM_LEAF_REC(n,r)          (((n)-H5B2_OVERHEAD_SIZE)/(r))
+
+/* Size of the B-tree header on disk */
+#define H5B2_HEADER_SIZE(f)     (                                             \
+    4 + /* Signature */                                                       \
+    1 + /* Version */                                                         \
+    1 + /* Tree type */                                                       \
+    4 + /* Node size, in bytes */                                             \
+    2 + /* Key size, in bytes */                                              \
+    2 + /* Depth of tree */                                                   \
+    2 + /* Split % of full (as integer, ie. "98" means 98%) */                \
+    2 + /* Merge % of full (as integer, ie. "98" means 98%) */                \
+    H5B2_NODE_POINTER_SIZE(f))  /* Node pointer to root node in tree */
+
+/* Macro to retrieve pointer to i'th native key for leaf node */
+#define H5B2_INT_NKEY(i,shared,idx)  ((i)->int_native+(shared)->int_nat_off[(idx)])
+#define H5B2_LEAF_NKEY(l,shared,idx)  ((l)->leaf_native+(shared)->leaf_nat_off[(idx)])
+
+
+/* Local typedefs */
+
+/* Local prototypes */
+
+/* Helper functions */
+static herr_t H5B2_shared_free (void *_shared);
+static herr_t H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type,
+    size_t node_size, size_t rkey_size, unsigned split_percent, unsigned merge_percent);
+static herr_t H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, 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);
+
+/* Metadata cache callbacks */
+static H5B2_t *H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata);
+static herr_t H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_t *b);
+static herr_t H5B2_cache_hdr_dest(H5F_t *f, H5B2_t *b);
+static herr_t H5B2_cache_hdr_clear(H5F_t *f, H5B2_t *b, hbool_t destroy);
+static herr_t H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t *bt, size_t *size_ptr);
+static H5B2_leaf_t *H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata);
+static herr_t H5B2_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_leaf_t *l);
+static herr_t H5B2_cache_leaf_dest(H5F_t *f, H5B2_leaf_t *l);
+static herr_t H5B2_cache_leaf_clear(H5F_t *f, H5B2_leaf_t *l, hbool_t destroy);
+static herr_t H5B2_cache_leaf_size(const H5F_t *f, const H5B2_leaf_t *l, size_t *size_ptr);
+
+/* Static variables */
+
+/* H5B2 inherits cache-like properties from H5AC */
+const H5AC_class_t H5AC_BT2_HDR[1] = {{
+    H5AC_BT2_HDR_ID,
+    (H5AC_load_func_t)H5B2_cache_hdr_load,
+    (H5AC_flush_func_t)H5B2_cache_hdr_flush,
+    (H5AC_dest_func_t)H5B2_cache_hdr_dest,
+    (H5AC_clear_func_t)H5B2_cache_hdr_clear,
+    (H5AC_size_func_t)H5B2_cache_hdr_size,
+}};
+
+/* H5B2 inherits cache-like properties from H5AC */
+static const H5AC_class_t H5AC_BT2_LEAF[1] = {{
+    H5AC_BT2_LEAF_ID,
+    (H5AC_load_func_t)H5B2_cache_leaf_load,
+    (H5AC_flush_func_t)H5B2_cache_leaf_flush,
+    (H5AC_dest_func_t)H5B2_cache_leaf_dest,
+    (H5AC_clear_func_t)H5B2_cache_leaf_clear,
+    (H5AC_size_func_t)H5B2_cache_leaf_size,
+}};
+
+
+/* Declare a free list to manage B-tree header data to/from disk */
+H5FL_BLK_DEFINE_STATIC(header_block);
+
+/* Declare a free list to manage B-tree node pages to/from disk */
+H5FL_BLK_DEFINE_STATIC(node_page);
+
+/* Declare a free list to manage the 'H5B2_node_ptr_t' sequence information */
+H5FL_SEQ_DEFINE_STATIC(H5B2_node_ptr_t);
+
+/* Declare a free list to manage the 'size_t' sequence information */
+H5FL_SEQ_DEFINE_STATIC(size_t);
+
+/* Declare a free list to manage the H5B2_t struct */
+H5FL_DEFINE_STATIC(H5B2_t);
+
+/* Declare a free list to manage the H5B2_shared_t struct */
+H5FL_DEFINE_STATIC(H5B2_shared_t);
+
+/* Declare a free list to manage the H5B2_leaf_t struct */
+H5FL_DEFINE_STATIC(H5B2_leaf_t);
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_shared_init
+ *
+ * Purpose:	Allocate & initialize shared B-tree info
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type,
+    size_t node_size, size_t rkey_size,
+    unsigned split_percent, unsigned merge_percent)
+{
+    H5B2_shared_t *shared = NULL;       /* Shared B-tree information */
+    unsigned u;                         /* Local index variable */
+    herr_t ret_value=SUCCEED;           /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_shared_init)
+
+    /* Allocate space for the shared information */
+    if(NULL==(shared = H5FL_CALLOC(H5B2_shared_t)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree shared information")
+
+    /* Assign user's information */
+    shared->split_percent = split_percent;
+    shared->merge_percent = merge_percent;
+    shared->node_size = node_size;
+    shared->rkey_size = rkey_size;
+
+    /* Compute derived information */
+    shared->internal_nrec = H5B2_NUM_INT_REC(f,shared->node_size,shared->rkey_size);
+    shared->split_int_nrec = (shared->internal_nrec * shared->split_percent)/100;
+    shared->merge_int_nrec = (shared->internal_nrec * shared->merge_percent)/100;
+
+    shared->leaf_nrec = H5B2_NUM_LEAF_REC(shared->node_size,shared->rkey_size);
+    shared->split_leaf_nrec = (shared->leaf_nrec * shared->split_percent)/100;
+    shared->merge_leaf_nrec = (shared->leaf_nrec * shared->merge_percent)/100;
+
+    /* Assign common type information */
+    shared->type = 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");
+
+    /* Create factory for internal node native record storage */
+    if((shared->int_fac=H5FL_fac_init(type->nkey_size*shared->internal_nrec))==NULL)
+	HGOTO_ERROR (H5E_RESOURCE, H5E_CANTINIT, NULL, "can't create internal node native key block factory")
+
+    /* Create factory for leaf node native record storage */
+    if((shared->leaf_fac=H5FL_fac_init(type->nkey_size*shared->leaf_nrec))==NULL)
+	HGOTO_ERROR (H5E_RESOURCE, H5E_CANTINIT, NULL, "can't create leaf node native key block factory")
+
+    /* Create factory for internal node node pointer storage */
+    if((shared->node_ptr_fac=H5FL_fac_init(sizeof(H5B2_node_ptr_t)*(shared->internal_nrec+1)))==NULL)
+	HGOTO_ERROR (H5E_RESOURCE, H5E_CANTINIT, NULL, "can't create internal node node pointer block factory")
+
+    /* Allocate array of pointers to internal node native keys */
+    if((shared->int_nat_off=H5FL_SEQ_MALLOC(size_t,shared->internal_nrec))==NULL)
+        HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
+
+    /* Allocate array of pointers to leaf node native keys */
+    if((shared->leaf_nat_off=H5FL_SEQ_MALLOC(size_t,shared->leaf_nrec))==NULL)
+        HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
+
+    /* Allocate array of pointers to internal node node pointers */
+    if((shared->node_ptr_off=H5FL_SEQ_MALLOC(H5B2_node_ptr_t,(shared->internal_nrec+1)))==NULL)
+        HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
+
+    /* Initialize offsets in internal node native key block */
+    for(u=0; u<shared->internal_nrec; u++)
+        shared->int_nat_off[u]=type->nkey_size*u;
+
+    /* Initialize offsets in leaf node native key block */
+    for(u=0; u<shared->leaf_nrec; u++)
+        shared->leaf_nat_off[u]=type->nkey_size*u;
+
+    /* Initialize offsets in internal node node pointer block */
+    for(u=0; u<(shared->internal_nrec+1); u++)
+        shared->node_ptr_off[u]=sizeof(H5B2_node_ptr_t)*u;
+
+    /* Make shared B-tree info reference counted */
+    if(NULL==(bt2->shared=H5RC_create(shared,H5B2_shared_free)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "can't create ref-count wrapper for shared B-tree info")
+
+done:
+    if(ret_value<0)
+        if(shared)
+            H5B2_shared_free(shared);
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_shared_init() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_shared_free
+ *
+ * Purpose:	Free shared B-tree info
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_shared_free (void *_shared)
+{
+    H5B2_shared_t *shared = (H5B2_shared_t *)_shared;
+    herr_t ret_value=SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_shared_free)
+
+    /* Sanity check */
+    HDassert(shared);
+
+    /* Free the B-tree node buffer */
+    if(shared->page)
+        H5FL_BLK_FREE(node_page,shared->page);
+
+    /* Destroy factory for internal node native record storage */
+    if(shared->int_fac)
+        if(H5FL_fac_term(shared->int_fac)<0)
+            HGOTO_ERROR (H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal node native key block factory")
+
+    /* Destroy factory for leaf node native record storage */
+    if(shared->leaf_fac)
+        if(H5FL_fac_term(shared->leaf_fac)<0)
+            HGOTO_ERROR (H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy leaf node native key block factory")
+
+    /* Destroy factory for internal node node pointer storage */
+    if(shared->node_ptr_fac)
+        if(H5FL_fac_term(shared->node_ptr_fac)<0)
+            HGOTO_ERROR (H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal node node pointer block factory")
+
+    /* Free the array of offsets into the internal node native key block */
+    if(shared->int_nat_off)
+        H5FL_SEQ_FREE(size_t,shared->int_nat_off);
+
+    /* Free the array of offsets into the leaf node native key block */
+    if(shared->leaf_nat_off)
+        H5FL_SEQ_FREE(size_t,shared->leaf_nat_off);
+
+    /* Free the array of offsets into the internal node node pointer block */
+    if(shared->node_ptr_off)
+        H5FL_SEQ_FREE(H5B2_node_ptr_t,shared->node_ptr_off);
+
+    /* Free the shared B-tree info itself */
+    H5FL_FREE(H5B2_shared_t,shared);
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_shared_free() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_create
+ *
+ * Purpose:	Creates a new empty B-tree in the file.
+ *
+ * Return:	Success:	Pointer to a new B-tree.
+ *
+ *		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Jan 31 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
+    size_t node_size, size_t rkey_size,
+    unsigned split_percent, unsigned merge_percent, haddr_t *addr_p)
+{
+    H5B2_t *bt2 = NULL;                 /* The new B-tree header information */
+    herr_t ret_value=SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5B2_create, FAIL)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(f);
+    HDassert(type);
+    HDassert(node_size>0);
+    HDassert(rkey_size>0);
+    HDassert(merge_percent>0 && merge_percent<=100);
+    HDassert(split_percent>0 && split_percent<=100);
+    HDassert(merge_percent<(split_percent/2));
+
+    /*
+     * Allocate file and memory data structures.
+     */
+    if (NULL==(bt2 = H5FL_MALLOC(H5B2_t)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree header")
+
+    /* Assign internal information */
+    HDmemset(&bt2->cache_info,0,sizeof(H5AC_info_t));
+    bt2->cache_info.is_dirty = TRUE;
+    bt2->depth = 0;
+    bt2->root.addr = HADDR_UNDEF;
+    bt2->root.node_nrec = bt2->root.all_nrec = 0;
+
+    /* Initialize shared B-tree info */
+    if(H5B2_shared_init(f, bt2, type, node_size, rkey_size, split_percent, merge_percent)<0)
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "can't create shared B-tree info")
+
+    /* Allocate space for the header on disk */
+    if (HADDR_UNDEF==(*addr_p=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)H5B2_HEADER_SIZE(f))))
+	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree header")
+
+    /* Cache the new B-tree node */
+    if (H5AC_set(f, dxpl_id, H5AC_BT2_HDR, *addr_p, bt2, H5AC__NO_FLAGS_SET) < 0)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree header to cache")
+
+done:
+    if (ret_value<0) {
+	if (bt2)
+            (void)H5B2_cache_hdr_dest(f,bt2);
+    } /* end if */
+    
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_create() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_cache_hdr_load
+ *
+ * Purpose:	Loads a B-tree header from the disk.
+ *
+ * Return:	Success:	Pointer to a new B-tree.
+ *
+ *		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 1 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static H5B2_t *
+H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void UNUSED *udata)
+{
+    const H5B2_class_t	*type = (const H5B2_class_t *) _type;
+    size_t node_size, rkey_size;        /* Size info for B-tree */
+    unsigned split_percent, merge_percent;      /* Split & merge info for B-tree */
+    H5B2_t		*bt2 = NULL;
+    size_t		size;
+    uint8_t		*buf = NULL;
+    uint8_t		*p;             /* Pointer into raw data buffer */
+    H5B2_t		*ret_value;
+
+    FUNC_ENTER_NOAPI(H5B2_cache_hdr_load, NULL)
+
+    /* Check arguments */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(type);
+
+    if (NULL==(bt2 = H5FL_MALLOC(H5B2_t)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
+    HDmemset(&bt2->cache_info,0,sizeof(H5AC_info_t));
+
+    /* Compute the size of the B-tree header on disk */
+    size = H5B2_HEADER_SIZE(f);
+
+    /* Allocate temporary buffer */
+    if ((buf=H5FL_BLK_MALLOC(header_block,size))==NULL)
+        HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
+
+    /* Read header from disk */
+    if (H5F_block_read(f, H5FD_MEM_BTREE, addr, size, dxpl_id, buf)<0)
+	HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree header")
+
+    p = buf;
+
+    /* magic number */
+    if (HDmemcmp(p, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header signature")
+    p += H5B2_SIZEOF_MAGIC;
+
+    /* version */
+    if (*p++ != H5B2_HDR_VERSION)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header version")
+
+    /* B-tree type */
+    if (*p++ != (uint8_t)type->id)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type")
+
+    /* node size (in bytes) */
+    UINT32DECODE(p, node_size);
+
+    /* raw key size (in bytes) */
+    UINT16DECODE(p, rkey_size);
+
+    /* depth of tree */
+    UINT16DECODE(p, bt2->depth);
+
+    /* split & merge %s */
+    UINT16DECODE(p, split_percent);
+    UINT16DECODE(p, merge_percent);
+
+    /* root node pointer */
+    H5F_addr_decode(f, (const uint8_t **)&p, &(bt2->root.addr));
+    UINT16DECODE(p, bt2->root.node_nrec);
+    H5F_DECODE_LENGTH(f, p, bt2->root.all_nrec);
+
+    /* Initialize shared B-tree info */
+    if(H5B2_shared_init(f, bt2, type, node_size, rkey_size, split_percent, merge_percent)<0)
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "can't create shared B-tree info")
+
+    /* Set return value */
+    ret_value = bt2;
+
+done:
+    if(buf)
+        H5FL_BLK_FREE(header_block,buf);
+    if (!ret_value && bt2)
+        (void)H5B2_cache_hdr_dest(f,bt2);
+    FUNC_LEAVE_NOAPI(ret_value)
+} /*lint !e818 Can't make udata a pointer to const */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_cache_hdr_flush
+ *
+ * Purpose:	Flushes a dirty B-tree header to disk.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 1 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_t *bt2)
+{
+    herr_t      ret_value = SUCCEED;    /* Return value */
+
+    FUNC_ENTER_NOAPI(H5B2_cache_hdr_flush, FAIL)
+
+    /* check arguments */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(bt2);
+
+    if (bt2->cache_info.is_dirty) {
+        H5B2_shared_t *shared;      /* Shared B-tree information */
+        uint8_t	*buf = NULL;
+        uint8_t *p;                 /* Pointer into raw data buffer */
+        size_t	size;
+
+        /* Get the pointer to the shared B-tree info */
+        shared=H5RC_GET_OBJ(bt2->shared);
+        HDassert(shared);
+
+        /* Compute the size of the B-tree header on disk */
+        size = H5B2_HEADER_SIZE(f);
+
+        /* Allocate temporary buffer */
+        if ((buf=H5FL_BLK_MALLOC(header_block,size))==NULL)
+            HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed");
+
+        p = buf;
+
+        /* magic number */
+        HDmemcpy(p, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC);
+        p += H5B2_SIZEOF_MAGIC;
+
+        /* version # */
+        *p++ = H5B2_HDR_VERSION;
+
+        /* b-tree type */
+        *p++ = shared->type->id;
+
+        /* node size (in bytes) */
+        UINT32ENCODE(p, shared->node_size);
+
+        /* raw key size (in bytes) */
+        UINT16ENCODE(p, shared->rkey_size);
+
+        /* depth of tree */
+        UINT16ENCODE(p, bt2->depth);
+
+        /* split & merge %s */
+        UINT16ENCODE(p, shared->split_percent);
+        UINT16ENCODE(p, shared->merge_percent);
+
+        /* root node pointer */
+        H5F_addr_encode(f, &p, bt2->root.addr);
+        UINT16ENCODE(p, bt2->root.node_nrec);
+        H5F_ENCODE_LENGTH(f, p, bt2->root.all_nrec);
+
+	/* Write the B-tree header. */
+	if (H5F_block_write(f, H5FD_MEM_BTREE, addr, size, dxpl_id, buf) < 0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B-tree header to disk")
+
+        H5FL_BLK_FREE(header_block,buf);
+
+	bt2->cache_info.is_dirty = FALSE;
+    } /* end if */
+
+    if (destroy)
+        if (H5B2_cache_hdr_dest(f,bt2) < 0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header")
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_cache_hdr_flush() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B_cache_hdr_dest
+ *
+ * Purpose:	Destroys a B-tree header in memory.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 1 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+/* ARGSUSED */
+static herr_t
+H5B2_cache_hdr_dest(H5F_t UNUSED *f, H5B2_t *bt2)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_hdr_dest)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(bt2);
+
+    /* Decrement reference count on shared B-tree info */
+    if(bt2->shared)
+        H5RC_DEC(bt2->shared);
+
+    /* Free B-tree header info */
+    H5FL_FREE(H5B2_t,bt2);
+
+    FUNC_LEAVE_NOAPI(SUCCEED)
+} /* end H5B2_cache_hdr_dest() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_cache_hdr_clear
+ *
+ * Purpose:	Mark a B-tree header in memory as non-dirty.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  1 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_cache_hdr_clear(H5F_t *f, H5B2_t *bt2, hbool_t destroy)
+{
+    herr_t ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_hdr_clear)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(bt2);
+
+    /* Reset the dirty flag.  */
+    bt2->cache_info.is_dirty = FALSE;
+ 
+    if (destroy)
+        if (H5B2_cache_hdr_dest(f, bt2) < 0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header")
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_cache_hdr_clear() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_cache_hdr_size
+ *
+ * Purpose:	Compute the size in bytes of a B-tree header
+ *		on disk, and return it in *size_ptr.  On failure, 
+ *		the value of *size_ptr is undefined.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 1 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t UNUSED *bt2, size_t *size_ptr)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_hdr_size)
+
+    /* check arguments */
+    HDassert(f);
+    HDassert(size_ptr);
+
+    /* Set size value */
+    *size_ptr = H5B2_HEADER_SIZE(f);
+
+    FUNC_LEAVE_NOAPI(SUCCEED)
+} /* H5B2_cache_hdr_size() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_locate_record
+ *
+ * Purpose:	Performs a binary search to locate a record in a sorted
+ *              array of records.
+ *
+ * Return:	Success:	Non-negative array index where new record
+ *                              should be inserted
+ *
+ *		Failure:	Negative, if record already is in array of
+ *                              records.
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  3 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+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)
+{
+    unsigned	lo = 0, hi;     /* Low & high index values */
+    int         idx = 0;        /* Final index value */
+    int         cmp = -1;       /* Key comparison value */
+
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_locate_record)
+
+    hi = nrec;
+    while (lo < hi && cmp) {
+	idx = (lo + hi) / 2;
+	if ((cmp = (type->compare)(f, dxpl_id, udata, native+rec_off[idx])) < 0)
+	    hi = idx;
+	else
+	    lo = idx + 1;
+    }
+    if(cmp==0)
+        idx=(-1);
+    else if(cmp>0)
+        idx++;
+
+    FUNC_LEAVE_NOAPI(idx);
+} /* end H5B2_locate_record */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_insert
+ *
+ * Purpose:	Adds a new record to the B-tree.  If the root node of
+ *		the B-tree splits then the B-tree header tracks the new
+ *              root node created.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr,
+           void *udata)
+{
+    H5AC_info_t *cache_info;            /* Parent node's cache info */
+    H5B2_t	*bt2=NULL;              /* Pointer to the B-tree header */
+    H5B2_shared_t *shared;              /* Pointer to B-tree's shared information */
+    H5B2_node_ptr_t *node_ptr;          /* Pointer to node pointer info for current node */
+    unsigned    depth;                  /* Current depth of node */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5B2_insert, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(type);
+    HDassert(H5F_addr_defined(addr));
+
+    /* Look up the b-tree header */
+    if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_WRITE)))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree header")
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(bt2->shared);
+    HDassert(shared);
+
+    /* 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)
+	    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 */
+        bt2->cache_info.is_dirty = TRUE;
+    } /* end if */
+depth=bt2->depth;
+node_ptr=&(bt2->root);
+cache_info=&(bt2->cache_info);
+
+    /* Check if we are inserting in internal or leaf node */
+    if(depth==0) {
+        H5B2_leaf_t *leaf=NULL;      /* Pointer to leaf node */
+        int         idx;             /* Location of record which matches key */
+
+        /* Look up the B-tree leaf node */
+        if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, shared->type, node_ptr, H5AC_WRITE)))
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node")
+
+        /* Check for inserting into empty leaf */
+        if(node_ptr->node_nrec==0)
+            idx=0;
+        else {
+            /* Find correct location to insert this record and make room for it */
+            if((idx=H5B2_locate_record(f,dxpl_id,shared->type,leaf->nrec,shared->leaf_nat_off,leaf->leaf_native,udata))<0) {
+                /* Release the B-tree leaf node */
+                if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+                    HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
+
+                HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree")
+            } /* end if */
+
+            /* Make room for new record */
+            if((unsigned)idx<leaf->nrec)
+                HDmemmove(H5B2_LEAF_NKEY(leaf,shared,idx+1),H5B2_LEAF_NKEY(leaf,shared,idx),shared->type->nkey_size*(leaf->nrec-idx));
+        } /* end else */
+
+        /* Make callback to store record in native form */
+        if((shared->type->store)(f,dxpl_id,udata,H5B2_LEAF_NKEY(leaf,shared,idx))<0) {
+            /* Release the B-tree leaf node */
+            if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
+
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node")
+        } /* end if */
+
+        /* Update record # info in node pointer */
+        node_ptr->all_nrec++;
+        node_ptr->node_nrec++;
+
+        /* Update number of records in node */
+        leaf->nrec++;
+        HDassert(node_ptr->node_nrec==leaf->nrec);
+
+        /* Mark parent's node as dirty now */
+        cache_info->is_dirty = TRUE;
+
+        /* Mark leaf node as dirty also */
+        leaf->cache_info.is_dirty = TRUE;
+
+        /* Release the B-tree leaf node */
+        if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node")
+    } /* end if */
+    else {
+    } /* end else */
+
+done:
+    if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree header")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_insert() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_create_leaf
+ *
+ * Purpose:	Creates empty leaf node of a B-tree and update node pointer
+ *              to point to it.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, 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 */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5B2_create_leaf, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(bt2);
+    HDassert(node_ptr);
+
+    /* Allocate memory for leaf information */
+    if (NULL==(leaf = H5FL_MALLOC(H5B2_leaf_t)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree leaf info")
+
+    /* Set metadata cache info */
+    HDmemset(&leaf->cache_info,0,sizeof(H5AC_info_t));
+    leaf->cache_info.is_dirty = TRUE;
+
+    /* Share common B-tree information */
+    leaf->shared = bt2->shared;
+    H5RC_INC(leaf->shared);
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(leaf->shared);
+    HDassert(shared);
+
+    /* 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")
+
+    /* Set number of records */
+    leaf->nrec=0;
+
+    /* Allocate space on disk for the leaf */
+    if (HADDR_UNDEF==(node_ptr->addr=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size)))
+	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree header")
+
+    /* Cache the new B-tree node */
+    if (H5AC_set(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree leaf to cache")
+
+done:
+    if (ret_value<0) {
+	if (leaf)
+            (void)H5B2_cache_leaf_dest(f,leaf);
+    } /* end if */
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_create_leaf() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_cache_leaf_load
+ *
+ * Purpose:	Loads a B-tree leaf from the disk.
+ *
+ * Return:	Success:	Pointer to a new B-tree leaf node.
+ *
+ *		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static H5B2_leaf_t *
+H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_bt2, void *_node_ptr)
+{
+    const H5B2_t	*bt2 = (const H5B2_t *)_bt2;
+    H5B2_node_ptr_t     *node_ptr = (H5B2_node_ptr_t *)_node_ptr;
+    H5B2_leaf_t		*leaf = NULL;
+    H5B2_shared_t 	*shared;      /* Shared B-tree information */
+    uint8_t		*p;             /* Pointer into raw data buffer */
+    H5B2_leaf_t		*ret_value;
+
+    FUNC_ENTER_NOAPI(H5B2_cache_leaf_load, NULL)
+
+    /* Check arguments */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(bt2);
+
+    if (NULL==(leaf = H5FL_MALLOC(H5B2_leaf_t)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
+    HDmemset(&leaf->cache_info,0,sizeof(H5AC_info_t));
+
+    /* Share common B-tree information */
+    leaf->shared = bt2->shared;
+    H5RC_INC(leaf->shared);
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(leaf->shared);
+    HDassert(shared);
+
+    /* Read header from disk */
+    if (H5F_block_read(f, H5FD_MEM_BTREE, addr, shared->node_size, dxpl_id, shared->page)<0)
+	HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B-tree leaf node")
+
+    p = shared->page;
+
+    /* magic number */
+    if (HDmemcmp(p, H5B2_LEAF_MAGIC, H5B2_SIZEOF_MAGIC))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node signature")
+    p += H5B2_SIZEOF_MAGIC;
+
+    /* version */
+    if (*p++ != H5B2_LEAF_VERSION)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header version")
+
+    /* B-tree type */
+    if (*p++ != (uint8_t)shared->type->id)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type")
+
+    /* 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, NULL, "memory allocation failed for B-tree leaf native keys")
+
+HDfprintf(stderr,"%s: Deserialize leaf node records here!, node_ptr->node_nrec=%u\n",FUNC,node_ptr->node_nrec);
+
+    /* Set return value */
+    ret_value = leaf;
+
+done:
+    if (!ret_value && leaf)
+        (void)H5B2_cache_leaf_dest(f,leaf);
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_cache_leaf_load() */ /*lint !e818 Can't make udata a pointer to const */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_cache_leaf_flush
+ *
+ * Purpose:	Flushes a dirty B-tree leaf node to disk.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_leaf_t *leaf)
+{
+    herr_t      ret_value = SUCCEED;    /* Return value */
+
+    FUNC_ENTER_NOAPI(H5B2_cache_leaf_flush, FAIL)
+
+    /* check arguments */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(leaf);
+
+    if (leaf->cache_info.is_dirty) {
+        H5B2_shared_t *shared;  /* Shared B-tree information */
+        uint8_t *p;             /* Pointer into raw data buffer */
+        uint8_t *native;        /* Pointer to native keys */
+        unsigned u;             /* Local index variable */
+
+        /* Get the pointer to the shared B-tree info */
+        shared=H5RC_GET_OBJ(leaf->shared);
+        HDassert(shared);
+
+        p = shared->page;
+
+        /* magic number */
+        HDmemcpy(p, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC);
+        p += H5B2_SIZEOF_MAGIC;
+
+        /* version # */
+        *p++ = H5B2_LEAF_VERSION;
+
+        /* b-tree type */
+        *p++ = shared->type->id;
+
+        /* Serialize records for leaf node */
+        native=leaf->leaf_native;
+        for(u=0; u<leaf->nrec; u++) {
+            /* Encode record */
+            if((shared->type->encode)(f,p,native)<0)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTENCODE, FAIL, "enable to encode B-tree record");
+
+            /* Move to next record */
+            p += shared->rkey_size;
+            native += shared->type->nkey_size;
+        } /* end for */
+
+	/* Write the B-tree leaf node */
+	if (H5F_block_write(f, H5FD_MEM_BTREE, addr, shared->node_size, dxpl_id, shared->page) < 0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B-tree leaf node to disk")
+
+	leaf->cache_info.is_dirty = FALSE;
+    } /* end if */
+
+    if (destroy)
+        if (H5B2_cache_leaf_dest(f,leaf) < 0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree leaf node")
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5B2_cache_leaf_flush() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B_cache_leaf_dest
+ *
+ * Purpose:	Destroys a B-tree leaf node in memory.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+/* ARGSUSED */
+static herr_t
+H5B2_cache_leaf_dest(H5F_t UNUSED *f, H5B2_leaf_t *leaf)
+{
+    H5B2_shared_t *shared;      /* Shared B-tree information */
+
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_leaf_dest)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(leaf);
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(leaf->shared);
+    HDassert(shared);
+
+    /* Release leaf's native key buffer */
+    if(leaf->leaf_native)
+        H5FL_FAC_FREE(shared->leaf_fac,leaf->leaf_native);
+
+    /* Decrement reference count on shared B-tree info */
+    if(leaf->shared)
+        H5RC_DEC(leaf->shared);
+
+    /* Free B-tree leaf node info */
+    H5FL_FREE(H5B2_leaf_t,leaf);
+
+    FUNC_LEAVE_NOAPI(SUCCEED)
+} /* end H5B2_cache_leaf_dest() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_cache_leaf_clear
+ *
+ * Purpose:	Mark a B-tree leaf node in memory as non-dirty.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_cache_leaf_clear(H5F_t *f, H5B2_leaf_t *leaf, hbool_t destroy)
+{
+    herr_t ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_leaf_clear)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(leaf);
+
+    /* Reset the dirty flag.  */
+    leaf->cache_info.is_dirty = FALSE;
+ 
+    if (destroy)
+        if (H5B2_cache_leaf_dest(f, leaf) < 0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree leaf node")
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_cache_leaf_clear() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_cache_leaf_size
+ *
+ * Purpose:	Compute the size in bytes of a B-tree leaf node
+ *		on disk, and return it in *size_ptr.  On failure, 
+ *		the value of *size_ptr is undefined.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb 2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B2_cache_leaf_size(const H5F_t UNUSED *f, const H5B2_leaf_t *leaf, size_t *size_ptr)
+{
+    H5B2_shared_t *shared;      /* Shared B-tree information */
+
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_leaf_size)
+
+    /* check arguments */
+    HDassert(leaf);
+    HDassert(size_ptr);
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(leaf->shared);
+    HDassert(shared);
+
+    /* Set size value */
+    *size_ptr = shared->node_size;
+
+    FUNC_LEAVE_NOAPI(SUCCEED)
+} /* H5B2_cache_leaf_size() */
+
diff --git a/src/H5B2dbg.c b/src/H5B2dbg.c
new file mode 100644
index 0000000..6e8af60
--- /dev/null
+++ b/src/H5B2dbg.c
@@ -0,0 +1,138 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*-------------------------------------------------------------------------
+ *
+ * Created:		H5B2dbg.c
+ *			Feb  2 2005
+ *			Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:		Dump debugging information about a v2 B-tree.
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#define H5B2_PACKAGE		/*suppress error about including H5B2pkg  */
+
+/* Private headers */
+#include "H5private.h"		/* Generic Functions			*/
+#include "H5B2pkg.h"		/* B-trees				*/
+#include "H5Eprivate.h"		/* Error handling		  	*/
+#include "H5FLprivate.h"	/* Free Lists                           */
+
+/* H5B2 inherits cache-like properties from H5AC */
+extern const H5AC_class_t H5AC_BT2_HDR[1];
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_hdr_debug
+ *
+ * Purpose:	Prints debugging info about a B-tree header.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth,
+    const H5B2_class_t *type)
+{
+    H5B2_t	*bt2 = NULL;
+    H5B2_shared_t 	*shared;      /* Shared B-tree information */
+    herr_t      ret_value=SUCCEED;       /* Return value */
+
+    FUNC_ENTER_NOAPI(H5B2_hdr_debug, FAIL)
+
+    /*
+     * Check arguments.
+     */
+    assert(f);
+    assert(H5F_addr_defined(addr));
+    assert(stream);
+    assert(indent >= 0);
+    assert(fwidth >= 0);
+
+    /*
+     * Load the b-tree header.
+     */
+    if (NULL == (bt2 = H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, addr, type, NULL, H5AC_READ)))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree header")
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(bt2->shared);
+    assert(shared);
+
+    /*
+     * Print the values.
+     */
+    HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth,
+	      "Tree type ID:",
+	      ((shared->type->id)==H5B2_GRP_NAME_ID ? "H5B2_GRP_NAME_ID" : "Unknown!"));
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Size of node:",
+	      shared->node_size);
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Size of raw (disk) key:",
+	      shared->rkey_size);
+    HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth,
+	      "Dirty flag:",
+	      bt2->cache_info.is_dirty ? "True" : "False");
+    HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth,
+	      "Depth:",
+	      bt2->depth);
+    HDfprintf(stream, "%*s%-*s %Hu\n", indent, "", fwidth,
+	      "Number of records in tree:",
+	      bt2->root.all_nrec);
+    HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth,
+	      "Number of records in root node:",
+	      bt2->root.node_nrec);
+    HDfprintf(stream, "%*s%-*s %a\n", indent, "", fwidth,
+	      "Address of root node:",
+	      bt2->root.addr);
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Max. number of records per internal node:",
+	      shared->internal_nrec);
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Max. number of records per leaf node:",
+	      shared->leaf_nrec);
+    HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth,
+	      "Split percent:",
+	      shared->split_percent);
+    HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth,
+	      "Merge percent:",
+	      shared->merge_percent);
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Internal records to split at:",
+	      shared->split_int_nrec);
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Leaf records to split at:",
+	      shared->split_leaf_nrec);
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Internal records to merge at:",
+	      shared->merge_int_nrec);
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Leaf records to merge at:",
+	      shared->merge_leaf_nrec);
+
+done:
+    if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree header")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+}
+
diff --git a/src/H5B2pkg.h b/src/H5B2pkg.h
new file mode 100644
index 0000000..1f98cac
--- /dev/null
+++ b/src/H5B2pkg.h
@@ -0,0 +1,118 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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>
+ *		Monday, January 31, 2005
+ *
+ * Purpose:	This file contains declarations which are visible only within
+ *		the H5B2 package.  Source files outside the H5B2 package should
+ *		include H5B2private.h instead.
+ */
+#ifndef H5B2_PACKAGE
+#error "Do not include this file outside the H5B2 package!"
+#endif
+
+#ifndef _H5B2pkg_H
+#define _H5B2pkg_H
+
+/* Get package's private header */
+#include "H5B2private.h"
+
+/* Other private headers needed by this file */
+#include "H5ACprivate.h"	/* Metadata cache			*/
+#include "H5FLprivate.h"	/* Free Lists                           */
+#include "H5RCprivate.h"	/* Reference counted object functions	*/
+
+/**************************/
+/* Package Private Macros */
+/**************************/
+
+/* Size of signature information (on disk) */
+#define H5B2_SIZEOF_MAGIC               4
+
+/* B-tree signatures */
+#define H5B2_HDR_MAGIC                  "BTHD"          /* Header */
+#define H5B2_LEAF_MAGIC                 "BTLF"          /* Leaf node */
+
+/****************************/
+/* Package Private Typedefs */
+/****************************/
+
+/* A "node pointer" to another B-tree node */
+typedef struct {
+    haddr_t     addr;           /* Address of other node */
+    unsigned    node_nrec;      /* Number of records used in node pointed to */
+    hsize_t     all_nrec;       /* Number of records in node pointed to and all it's children */
+} H5B2_node_ptr_t;
+
+/* Each B-tree has certain information that can be shared across all
+ * the instances of nodes in that B-tree.
+ */
+typedef struct H5B2_shared_t {
+    /* Shared internal data structures */
+    const H5B2_class_t	*type;	 /* Type of tree			     */
+    uint8_t	        *page;	 /* Disk page */
+    H5FL_fac_head_t     *int_fac;       /* Factory for internal node native key blocks */
+    H5FL_fac_head_t     *leaf_fac;      /* Factory for leaf node native key blocks */
+    H5FL_fac_head_t     *node_ptr_fac;  /* Factory for internal node node pointer blocks */
+    size_t              *int_nat_off;   /* Array of offsets of native keys in internal node block */
+    size_t              *leaf_nat_off;  /* Array of offsets of native keys in leaf node block */
+    size_t              *node_ptr_off;  /* Array of offsets of node pointers in internal node block */
+
+    /* Information set by user */
+    unsigned    split_percent;  /* Percent full at which to split the node, when inserting */
+    unsigned    merge_percent;  /* Percent full at which to merge the node, when deleting */
+    size_t      node_size;      /* Size of all nodes, in bytes                */    
+    size_t      rkey_size;      /* Size of "raw" (on disk) key, in bytes      */    
+
+    /* Derived information from user's information */
+    size_t      internal_nrec;  /* Number of records which fit into an internal node */
+    size_t      split_int_nrec; /* Number of records to split an internal node at */
+    size_t      merge_int_nrec; /* Number of records to merge an internal node at */
+    size_t      leaf_nrec;      /* Number of records which fit into a leaf node */
+    size_t      split_leaf_nrec; /* Number of records to split a leaf node at */
+    size_t      merge_leaf_nrec; /* Number of records to merge a leaf node at */
+} H5B2_shared_t;
+
+/* The B-tree information */
+typedef struct H5B2_t {
+    /* Information for H5AC cache functions, _must_ be first field in structure */
+    H5AC_info_t cache_info;
+
+    /* Internal B-tree information */
+    unsigned	depth;		/* B-tree's overall depth                     */
+    H5B2_node_ptr_t root;       /* Node pointer to root node in B-tree        */
+    H5RC_t	*shared;	/* Ref-counted shared info	              */
+} H5B2_t;
+
+/* B-tree leaf information */
+typedef struct H5B2_leaf_t {
+    /* Information for H5AC cache functions, _must_ be first field in structure */
+    H5AC_info_t cache_info;
+
+    /* Internal B-tree information */
+    H5RC_t	*shared;	/* Ref-counted shared info	              */
+    uint8_t     *leaf_native;   /* Pointer to native keys                     */
+    unsigned    nrec;           /* Number of records in leaf node             */
+} H5B2_leaf_t;
+
+/******************************/
+/* Package Private Prototypes */
+/******************************/
+H5_DLL herr_t H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
+    FILE *stream, int indent, int fwidth, const H5B2_class_t *type);
+
+#endif /* _H5B2pkg_H */
+
diff --git a/src/H5B2private.h b/src/H5B2private.h
new file mode 100644
index 0000000..5d8d42a
--- /dev/null
+++ b/src/H5B2private.h
@@ -0,0 +1,91 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*-------------------------------------------------------------------------
+ *
+ * Created:		H5B2private.h
+ *			Jan 31 2005
+ *			Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:		Private header for library accessible B-tree routines.
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#ifndef _H5B2private_H
+#define _H5B2private_H
+
+/* Include package's public header */
+#include "H5B2public.h"
+
+/* Private headers needed by this file */
+#include "H5Fprivate.h"		/* File access				*/
+
+/**************************/
+/* Library Private Macros */
+/**************************/
+
+/*
+ * Feature: Define this constant if you want to check B-tree consistency
+ *	    after each B-tree operation.  Note that this slows down the
+ *	    library considerably! Debugging the B-tree depends on assert()
+ *	    being enabled.
+ */
+/* #define H5B2_DEBUG */
+     
+/****************************/
+/* Library Private Typedefs */
+/****************************/
+
+/* B-tree IDs for various internal things. */
+/* Not really a "public" symbol, but that should be OK -QAK */
+/* Note - if more of these are added, any 'K' values (for internal or leaf
+ * nodes) they use will need to be stored in the file somewhere. -QAK
+ */
+typedef enum H5B2_subid_t {
+    H5B2_GRP_NAME_ID	 = 0,	/* B-tree is for group links, ordered by name	*/
+    H5B2_NUM_BTREE_ID           /* Number of B-tree key IDs (must be last)   */
+} H5B2_subid_t;
+
+/*
+ * Each class of object that can be pointed to by a B-link tree has a
+ * variable of this type that contains class variables and methods.
+ */
+typedef struct H5B2_class_t {
+    H5B2_subid_t id;				/*id as found in file*/
+    size_t	nkey_size;			/*size of native (memory) key*/
+
+    /* Store & retrieve records */
+    herr_t (*store)(const H5F_t *f, hid_t dxpl_id, const void *udata, void *nrecord);  /*  Store record in native key table */
+
+    /* Compare records, according to a key */
+    herr_t (*compare)(const H5F_t *f, hid_t dxpl_id, const void *rec1, const void *rec2);  /*  Compare two native records */
+
+    /* Encode, decode, debug record values */
+    herr_t (*encode)(const H5F_t *f, uint8_t *raw, const void *record);  /*  Store record in native key table */
+
+} H5B2_class_t;
+
+/***************************************/
+/* Library-private Function Prototypes */
+/***************************************/
+H5_DLL herr_t H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
+    size_t node_size, size_t rkey_size,
+    unsigned split_percent, unsigned merge_percent,
+    haddr_t *addr_p);
+H5_DLL herr_t H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type,
+    haddr_t addr, void *udata);
+
+#endif /* _H5B2private_H */
+
diff --git a/src/H5B2public.h b/src/H5B2public.h
new file mode 100644
index 0000000..55a866b
--- /dev/null
+++ b/src/H5B2public.h
@@ -0,0 +1,52 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*-------------------------------------------------------------------------
+ *
+ * Created:             H5B2public.h
+ *                      Jan 31 2005
+ *                      Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:             Public declarations for the H5B2 package.
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef _H5B2public_H
+#define _H5B2public_H
+
+/* Public headers needed by this file */
+#include "H5public.h"
+
+/*****************/
+/* Public Macros */
+/*****************/
+
+/*******************/
+/* Public Typedefs */
+/*******************/
+
+/**********************************/
+/* Public API Function Prototypes */
+/**********************************/
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _H5B2public_H */
+
diff --git a/src/H5FL.c b/src/H5FL.c
index 3041b57..be5ff8d 100644
--- a/src/H5FL.c
+++ b/src/H5FL.c
@@ -105,6 +105,9 @@ static herr_t H5FL_arr_gc_list(H5FL_arr_head_t *head);
 static herr_t H5FL_blk_gc(void);
 static herr_t H5FL_blk_gc_list(H5FL_blk_head_t *head);
 
+/* Declare a free list to manage the H5FL_fac_head_t struct */
+H5FL_DEFINE(H5FL_fac_head_t);
+
 /* Declare a free list to manage the H5FL_blk_node_t struct */
 H5FL_DEFINE(H5FL_blk_node_t);
 
@@ -1775,6 +1778,191 @@ done:
 
 
 /*-------------------------------------------------------------------------
+ * Function:	H5FL_fac_init
+ *
+ * Purpose:	Initialize a block factory
+ *
+ * Return:	Success:	Pointer to factory object
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Wednesday, February 2, 2005
+ *
+ * Modifications:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+H5FL_fac_head_t *
+H5FL_fac_init(size_t size)
+{
+    H5FL_fac_head_t *factory;      /* Pointer to new block factory */
+    H5FL_fac_head_t *ret_value;    /* Return value */
+
+    FUNC_ENTER_NOAPI(H5FL_fac_init, NULL)
+
+    /* Sanity check */
+    HDassert(size>0);
+
+    /* Allocate room for the new factory */
+    if(NULL==(factory=H5FL_MALLOC(H5FL_fac_head_t)))
+        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for factory object")
+    
+    /* Initialize block header information */
+    HDmemset(&(factory->queue),0,sizeof(H5FL_blk_head_t));
+
+    /* Set size of blocks for factory */
+    factory->size=size;
+
+    /* Set return value */
+    ret_value=factory;
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+}   /* end H5FL_fac_init() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5FL_fac_free
+ *
+ * Purpose:	Release a block back to a factory & put on free list
+ *
+ * Return:	Success:	Non-negative
+ * 		Failure:	Negative
+ *
+ * Programmer:	Quincey Koziol
+ *              Wednesday, February 2, 2005
+ *
+ * Modifications:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+void *
+H5FL_fac_free(H5FL_fac_head_t *head, void *obj)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5FL_fac_free)
+
+    /* Double check parameters */
+    assert(head);
+    assert(obj);
+
+    /* Make certain that the free list is initialized */
+    assert(head->queue.init);
+
+    /* Use block routine */
+    H5FL_blk_free(&(head->queue),obj);
+
+    FUNC_LEAVE_NOAPI(NULL)
+}   /* end H5FL_fac_free() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5FL_fac_malloc
+ *
+ * Purpose:	Allocate a block from a factory
+ *
+ * Return:	Success:	Pointer to a valid sequence object
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Wednesday, February 2, 2005
+ *
+ * Modifications:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+void *
+H5FL_fac_malloc(H5FL_fac_head_t *head)
+{
+    void *ret_value;        /* Pointer to object to return */
+
+    FUNC_ENTER_NOAPI(H5FL_fac_malloc, NULL)
+
+    /* Double check parameters */
+    assert(head);
+
+    /* Use block routine */
+    ret_value=H5FL_blk_malloc(&(head->queue),head->size);
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+}   /* end H5FL_fac_malloc() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5FL_fac_calloc
+ *
+ * Purpose:	Allocate a block from a factory and clear it to zeros
+ *
+ * Return:	Success:	Pointer to a valid array object
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Wednesday, February 2, 2005
+ *
+ * Modifications:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+void *
+H5FL_fac_calloc(H5FL_fac_head_t *head)
+{
+    void *ret_value;        /* Pointer to object to return */
+
+    FUNC_ENTER_NOAPI(H5FL_fac_calloc, NULL)
+
+    /* Double check parameters */
+    assert(head);
+
+    /* Use block routine */
+    ret_value=H5FL_blk_calloc(&(head->queue),head->size);
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+}   /* end H5FL_fac_calloc() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5FL_fac_term
+ *
+ * Purpose:	Terminate a block factory
+ *
+ * Return:	Success:	non-negative
+ * 		Failure:	negative
+ *
+ * Programmer:	Quincey Koziol
+ *              Wednesday, February 2, 2005
+ *
+ * Modifications:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5FL_fac_term(H5FL_fac_head_t *factory)
+{
+    herr_t ret_value=SUCCEED;    /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT(H5FL_fac_term)
+
+    /* Sanity check */
+    HDassert(factory);
+
+    /* Garbage collect all the blocks in the factory's free list */
+    if(H5FL_blk_gc_list(&(factory->queue))<0)
+        HGOTO_ERROR(H5E_RESOURCE, H5E_CANTGC, FAIL, "garbage collection of factory failed")
+
+    /* Verify that all the blocks have been freed */
+    if(factory->queue.allocated>0)
+        HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "factory still has objects allocated")
+
+    /* Free factory info */
+    H5FL_FREE(H5FL_fac_head_t,factory);
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+}   /* end H5FL_fac_term() */
+
+
+/*-------------------------------------------------------------------------
  * Function:	H5FL_garbage_coll
  *
  * Purpose:	Garbage collect on all the free lists
diff --git a/src/H5FLprivate.h b/src/H5FLprivate.h
index 641a630..cc19d99 100644
--- a/src/H5FLprivate.h
+++ b/src/H5FLprivate.h
@@ -41,6 +41,7 @@
 #define H5_NO_ARR_FREE_LISTS
 #define H5_NO_SEQ_FREE_LISTS
 #define H5_NO_BLK_FREE_LISTS
+#define H5_NO_FAC_FREE_LISTS
 #endif /* H5_NO_FREE_LISTS */
 
 /*
@@ -297,6 +298,35 @@ typedef struct H5FL_seq_head_t {
 #define H5FL_SEQ_REALLOC(t,obj,new_elem) H5MM_realloc(obj,(new_elem)*sizeof(t))
 #endif /* H5_NO_SEQ_FREE_LISTS */
 
+/* Data structure for free list block factory */
+typedef struct H5FL_fac_head_t {
+    H5FL_blk_head_t queue;      /* Priority queue of blocks */
+    size_t size;                /* Size of the blocks managed */
+} H5FL_fac_head_t;
+
+/*
+ * Macros for defining & using free list factories
+ *
+ * Factories are dynamically created free list managers for blocks of
+ *      a particular size.
+ *
+ */
+#ifndef H5_NO_FAC_FREE_LISTS
+/* Allocate a block from a factory */
+#define H5FL_FAC_MALLOC(t) H5FL_fac_malloc(t)
+
+/* Allocate a block from a factory and clear it to all zeros */
+#define H5FL_FAC_CALLOC(t) H5FL_fac_calloc(t)
+
+/* Return a block to a factory */
+#define H5FL_FAC_FREE(t,obj) H5FL_fac_free(t,obj)
+
+#else /* H5_NO_FAC_FREE_LISTS */
+#define H5FL_FAC_MALLOC(t) H5MM_malloc(t->size)
+#define H5FL_FAC_CALLOC(t) H5MM_calloc(t->size)
+#define H5FL_FAC_FREE(t,obj) H5MM_xfree(obj)
+#endif /* H5_NO_FAC_FREE_LISTS */
+
 /*
  * Library prototypes.
  */
@@ -316,6 +346,11 @@ H5_DLL void * H5FL_seq_malloc(H5FL_seq_head_t *head, size_t elem);
 H5_DLL void * H5FL_seq_calloc(H5FL_seq_head_t *head, size_t elem);
 H5_DLL void * H5FL_seq_free(H5FL_seq_head_t *head, void *obj);
 H5_DLL void * H5FL_seq_realloc(H5FL_seq_head_t *head, void *obj, size_t new_elem);
+H5_DLL H5FL_fac_head_t *H5FL_fac_init(size_t size);
+H5_DLL void * H5FL_fac_malloc(H5FL_fac_head_t *head);
+H5_DLL void * H5FL_fac_calloc(H5FL_fac_head_t *head);
+H5_DLL void * H5FL_fac_free(H5FL_fac_head_t *head, void *obj);
+H5_DLL herr_t H5FL_fac_term(H5FL_fac_head_t *head);
 H5_DLL herr_t H5FL_garbage_coll(void);
 H5_DLL herr_t H5FL_set_free_list_limits(int reg_global_lim, int reg_list_lim,
     int arr_global_lim, int arr_list_lim, int blk_global_lim, int blk_list_lim);
diff --git a/src/Makefile.am b/src/Makefile.am
index b3ade6d..112b9e9 100755
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -39,7 +39,9 @@ MOSTLYCLEANFILES=H5detect.o H5detect.lo H5detect H5Tinit.o H5Tinit.lo H5Tinit.c
 DISTCLEAN=libhdf5.settings
 
 # library sources
-libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5C.c H5D.c H5Dcontig.c H5Dcompact.c \
+libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2dbg.c H5C.c H5D.c      \
+        H5Dcontig.c \
+        H5Dcompact.c \
         H5Defl.c H5Dio.c H5Distore.c H5Dmpio.c H5Dselect.c H5Dtest.c H5E.c H5F.c \
         H5Fdbg.c H5FD.c H5FDcore.c  \
         H5FDfamily.c H5FDfphdf5.c H5FDgass.c H5FDlog.c H5FDmpi.c H5FDmpio.c     \
@@ -61,7 +63,8 @@ libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5C.c H5D.c H5Dcontig.c H5Dcompact.c
 
 
 # Public headers
-include_HEADERS =H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5Cpublic.h H5Dpublic.h  \
+include_HEADERS =H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5B2public.h \
+        H5Cpublic.h H5Dpublic.h  \
         H5Epubgen.h H5Epublic.h H5Fpublic.h H5FDpublic.h H5FDcore.h H5FDfamily.h          \
         H5FDfphdf5.h H5FDgass.h H5FDlog.h H5FDmpi.h H5FDmpio.h H5FDmpiposix.h              \
         H5FDmulti.h H5FDsec2.h H5FDsrb.h H5FDstdio.h H5FDstream.h H5FPpublic.h             \
@@ -70,7 +73,8 @@ include_HEADERS =H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5Cpublic.h H5D
         H5Tpublic.h H5Zpublic.h H5pubconf.h hdf5.h H5api_adpt.h
 
 # Private headers
-#noinst_HEADERS =H5private.h H5Aprivate.h H5Apkg.h H5ACprivate.h H5Bprivate.h      \
+#noinst_HEADERS =H5private.h H5Aprivate.h H5Apkg.h H5ACprivate.h H5Bprivate.h  \
+#        H5B2private.h \
 #        H5Dprivate.h H5Eprivate.h H5Fprivate.h H5FDprivate.h H5FLprivate.h    \
 #        H5FOprivate.h H5FSprivate.h H5Gprivate.h H5Gpkg.h                     \
 #        H5HGprivate.h H5HLprivate.h H5HPprivate.h H5Iprivate.h H5MFprivate.h  \
diff --git a/src/Makefile.in b/src/Makefile.in
index a2a53b9..b42082d 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -219,7 +219,9 @@ MOSTLYCLEANFILES = H5detect.o H5detect.lo H5detect H5Tinit.o H5Tinit.lo H5Tinit.
 DISTCLEAN = libhdf5.settings
 
 # library sources
-libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5C.c H5D.c H5Dcontig.c H5Dcompact.c \
+libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2dbg.c H5C.c H5D.c      \
+        H5Dcontig.c \
+        H5Dcompact.c \
         H5Defl.c H5Dio.c H5Distore.c H5Dmpio.c H5Dselect.c H5Dtest.c H5E.c H5F.c \
         H5Fdbg.c H5FD.c H5FDcore.c  \
         H5FDfamily.c H5FDfphdf5.c H5FDgass.c H5FDlog.c H5FDmpi.c H5FDmpio.c     \
@@ -241,7 +243,8 @@ libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5C.c H5D.c H5Dcontig.c H5Dcompact.
 
 
 # Public headers
-include_HEADERS = H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5Cpublic.h H5Dpublic.h  \
+include_HEADERS = H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5B2public.h \
+        H5Cpublic.h H5Dpublic.h  \
         H5Epubgen.h H5Epublic.h H5Fpublic.h H5FDpublic.h H5FDcore.h H5FDfamily.h          \
         H5FDfphdf5.h H5FDgass.h H5FDlog.h H5FDmpi.h H5FDmpio.h H5FDmpiposix.h              \
         H5FDmulti.h H5FDsec2.h H5FDsrb.h H5FDstdio.h H5FDstream.h H5FPpublic.h             \
@@ -251,7 +254,8 @@ include_HEADERS = H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5Cpublic.h H5
 
 
 # Private headers
-#noinst_HEADERS =H5private.h H5Aprivate.h H5Apkg.h H5ACprivate.h H5Bprivate.h      \
+#noinst_HEADERS =H5private.h H5Aprivate.h H5Apkg.h H5ACprivate.h H5Bprivate.h  \
+#        H5B2private.h \
 #        H5Dprivate.h H5Eprivate.h H5Fprivate.h H5FDprivate.h H5FLprivate.h    \
 #        H5FOprivate.h H5FSprivate.h H5Gprivate.h H5Gpkg.h                     \
 #        H5HGprivate.h H5HLprivate.h H5HPprivate.h H5Iprivate.h H5MFprivate.h  \
@@ -284,27 +288,27 @@ LTLIBRARIES = $(lib_LTLIBRARIES)
 
 libhdf5_la_LDFLAGS =
 libhdf5_la_LIBADD =
-am_libhdf5_la_OBJECTS = H5.lo H5A.lo H5AC.lo H5B.lo H5C.lo H5D.lo \
-	H5Dcontig.lo H5Dcompact.lo H5Defl.lo H5Dio.lo H5Distore.lo \
-	H5Dmpio.lo H5Dselect.lo H5Dtest.lo H5E.lo H5F.lo H5Fdbg.lo \
-	H5FD.lo H5FDcore.lo H5FDfamily.lo H5FDfphdf5.lo H5FDgass.lo \
-	H5FDlog.lo H5FDmpi.lo H5FDmpio.lo H5FDmpiposix.lo H5FDmulti.lo \
-	H5FDsec2.lo H5FDsrb.lo H5FDstdio.lo H5FDstream.lo H5FL.lo \
-	H5FO.lo H5FP.lo H5FPclient.lo H5FPserver.lo H5FS.lo H5G.lo \
-	H5Gent.lo H5Gnode.lo H5Gstab.lo H5HG.lo H5HGdbg.lo H5HL.lo \
-	H5HLdbg.lo H5HP.lo H5I.lo H5MF.lo H5MM.lo H5O.lo H5Oattr.lo \
-	H5Obogus.lo H5Ocont.lo H5Odtype.lo H5Oefl.lo H5Ofill.lo \
-	H5Olayout.lo H5Omtime.lo H5Oname.lo H5Onull.lo H5Opline.lo \
-	H5Osdspace.lo H5Oshared.lo H5Ostab.lo H5P.lo H5Pdcpl.lo \
-	H5Pdxpl.lo H5Pfapl.lo H5Pfcpl.lo H5Ptest.lo H5R.lo H5RC.lo \
-	H5RS.lo H5S.lo H5Sall.lo H5Shyper.lo H5Smpio.lo H5Snone.lo \
-	H5Spoint.lo H5Sselect.lo H5Stest.lo H5SL.lo H5ST.lo H5T.lo \
-	H5Tarray.lo H5Tbit.lo H5Tcommit.lo H5Tcompound.lo H5Tconv.lo \
-	H5Tcset.lo H5Tenum.lo H5Tfields.lo H5Tfixed.lo H5Tfloat.lo \
-	H5Tinit.lo H5Tnative.lo H5Toffset.lo H5Topaque.lo H5Torder.lo \
-	H5Tpad.lo H5Tprecis.lo H5Tstrpad.lo H5Tvlen.lo H5TS.lo H5V.lo \
-	H5Z.lo H5Zdeflate.lo H5Zfletcher32.lo H5Znbit.lo H5Zshuffle.lo \
-	H5Zszip.lo H5Ztrans.lo
+am_libhdf5_la_OBJECTS = H5.lo H5A.lo H5AC.lo H5B.lo H5B2.lo H5B2dbg.lo \
+	H5C.lo H5D.lo H5Dcontig.lo H5Dcompact.lo H5Defl.lo H5Dio.lo \
+	H5Distore.lo H5Dmpio.lo H5Dselect.lo H5Dtest.lo H5E.lo H5F.lo \
+	H5Fdbg.lo H5FD.lo H5FDcore.lo H5FDfamily.lo H5FDfphdf5.lo \
+	H5FDgass.lo H5FDlog.lo H5FDmpi.lo H5FDmpio.lo H5FDmpiposix.lo \
+	H5FDmulti.lo H5FDsec2.lo H5FDsrb.lo H5FDstdio.lo H5FDstream.lo \
+	H5FL.lo H5FO.lo H5FP.lo H5FPclient.lo H5FPserver.lo H5FS.lo \
+	H5G.lo H5Gent.lo H5Gnode.lo H5Gstab.lo H5HG.lo H5HGdbg.lo \
+	H5HL.lo H5HLdbg.lo H5HP.lo H5I.lo H5MF.lo H5MM.lo H5O.lo \
+	H5Oattr.lo H5Obogus.lo H5Ocont.lo H5Odtype.lo H5Oefl.lo \
+	H5Ofill.lo H5Olayout.lo H5Omtime.lo H5Oname.lo H5Onull.lo \
+	H5Opline.lo H5Osdspace.lo H5Oshared.lo H5Ostab.lo H5P.lo \
+	H5Pdcpl.lo H5Pdxpl.lo H5Pfapl.lo H5Pfcpl.lo H5Ptest.lo H5R.lo \
+	H5RC.lo H5RS.lo H5S.lo H5Sall.lo H5Shyper.lo H5Smpio.lo \
+	H5Snone.lo H5Spoint.lo H5Sselect.lo H5Stest.lo H5SL.lo H5ST.lo \
+	H5T.lo H5Tarray.lo H5Tbit.lo H5Tcommit.lo H5Tcompound.lo \
+	H5Tconv.lo H5Tcset.lo H5Tenum.lo H5Tfields.lo H5Tfixed.lo \
+	H5Tfloat.lo H5Tinit.lo H5Tnative.lo H5Toffset.lo H5Topaque.lo \
+	H5Torder.lo H5Tpad.lo H5Tprecis.lo H5Tstrpad.lo H5Tvlen.lo \
+	H5TS.lo H5V.lo H5Z.lo H5Zdeflate.lo H5Zfletcher32.lo H5Znbit.lo \
+	H5Zshuffle.lo H5Zszip.lo H5Ztrans.lo
 libhdf5_la_OBJECTS = $(am_libhdf5_la_OBJECTS)
 noinst_PROGRAMS = H5detect$(EXEEXT)
 PROGRAMS = $(noinst_PROGRAMS)
@@ -323,6 +327,7 @@ depcomp = $(SHELL) $(top_srcdir)/bin/depcomp
 am__depfiles_maybe = depfiles
 @AMDEP_TRUE@DEP_FILES = ./$(DEPDIR)/H5.Plo ./$(DEPDIR)/H5A.Plo \
 @AMDEP_TRUE@	./$(DEPDIR)/H5AC.Plo ./$(DEPDIR)/H5B.Plo \
+@AMDEP_TRUE@	./$(DEPDIR)/H5B2.Plo ./$(DEPDIR)/H5B2dbg.Plo \
 @AMDEP_TRUE@	./$(DEPDIR)/H5C.Plo ./$(DEPDIR)/H5D.Plo \
 @AMDEP_TRUE@	./$(DEPDIR)/H5Dcompact.Plo \
 @AMDEP_TRUE@	./$(DEPDIR)/H5Dcontig.Plo ./$(DEPDIR)/H5Defl.Plo \
@@ -405,7 +410,7 @@ all: H5config.h
 .SUFFIXES: .c .lo .o .obj
 $(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ Makefile.am $(top_srcdir)/config/commence.am $(top_srcdir)/config/conclude.am $(top_srcdir)/configure.in $(ACLOCAL_M4)
 	cd $(top_srcdir) && \
-	  $(AUTOMAKE) --foreign  src/Makefile
+	  $(AUTOMAKE) --gnu  src/Makefile
 Makefile: @MAINTAINER_MODE_TRUE@ $(srcdir)/Makefile.in  $(top_builddir)/config.status
 	cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)
 
@@ -478,6 +483,8 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5A.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5AC.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2dbg.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5C.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5D.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5Dcompact.Plo@am__quote@