[svn-r11031] Purpose:

    New feature

Description:
    Initial checkin of B+ Tree code.

Platforms tested:
    FreeBSD 4.11 (sleipnir)
    h5committest

Misc. update:

13 files changed, 1910 insertions, 12 deletions

diff --git a/src/H5AC.c b/src/H5AC.c
index 116dd94..a7f5aa1 100644
--- a/src/H5AC.c
+++ b/src/H5AC.c
@@ -365,7 +365,9 @@ static const char * H5AC_entry_type_names[H5AC_NTYPES] =
     "v2 B-tree internal nodes",
     "v2 B-tree leaf nodes",
     "block tracker nodes",
-    "segmented heaps"
+    "segmented heaps",
+    "B+ tree headers",
+    "B+ tree leaves"
 };
 
 herr_t
diff --git a/src/H5ACprivate.h b/src/H5ACprivate.h
index 314c96b..3d35028 100644
--- a/src/H5ACprivate.h
+++ b/src/H5ACprivate.h
@@ -49,7 +49,9 @@
 #define H5AC_BT2_LEAF_ID 7	/*v2 B-tree leaf node			     */
 #define H5AC_BLTR_ID	8	/*block tracker				     */
 #define H5AC_SHEAP_ID	9	/*segmented heap			     */
-#define H5AC_NTYPES	10
+#define H5AC_BPT_HDR_ID	10	/*B+ tree header			     */
+#define H5AC_BPT_LEAF_ID 11	/*B+ tree leaf				     */
+#define H5AC_NTYPES	12
 
 /* H5AC_DUMP_STATS_ON_CLOSE should always be FALSE when 
  * H5C_COLLECT_CACHE_STATS is FALSE.  
diff --git a/src/H5B2cache.c b/src/H5B2cache.c
index ddc402b..9f7d9db 100644
--- a/src/H5B2cache.c
+++ b/src/H5B2cache.c
@@ -284,7 +284,7 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B_cache_hdr_dest
+ * Function:	H5B2_cache_hdr_dest
  *
  * Purpose:	Destroys a B-tree header in memory.
  *
@@ -556,7 +556,7 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B_cache_leaf_dest
+ * Function:	H5B2_cache_leaf_dest
  *
  * Purpose:	Destroys a B-tree leaf node in memory.
  *
@@ -874,7 +874,7 @@ done:
 
 
 /*-------------------------------------------------------------------------
- * Function:	H5B_cache_internal_dest
+ * Function:	H5B2_cache_internal_dest
  *
  * Purpose:	Destroys a B-tree internal node in memory.
  *
diff --git a/src/H5BP.c b/src/H5BP.c
new file mode 100644
index 0000000..55d0095
--- /dev/null
+++ b/src/H5BP.c
@@ -0,0 +1,469 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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:		H5BP.c
+ *			Apr 14 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 H5BP_PACKAGE		/*suppress error about including H5BPpkg  */
+
+/* Private headers */
+#include "H5private.h"		/* Generic Functions			*/
+#include "H5BPpkg.h"		/* B+ trees				*/
+#include "H5Eprivate.h"		/* Error handling		  	*/
+#include "H5MFprivate.h"	/* File memory management		*/
+#include "H5MMprivate.h"	/* Memory management			*/
+
+/* Local macros */
+
+/* Uncomment this macro to enable extra sanity checking */
+/* #define H5BP_DEBUG */
+
+
+/* Local typedefs */
+
+/* Local prototypes */
+
+/* Helper functions */
+
+
+/* Package variables */
+
+/* Declare a free list to manage the H5BP_t struct */
+H5FL_DEFINE(H5BP_t);
+
+/* Declare a free list to manage the H5BP_branch_t struct */
+H5FL_DEFINE(H5BP_branch_t);
+
+/* Declare a free list to manage the H5BP_twig_t struct */
+H5FL_DEFINE(H5BP_twig_t);
+
+/* Declare a free list to manage the H5BP_leaf_t struct */
+H5FL_DEFINE(H5BP_leaf_t);
+
+
+/* Static variables */
+
+/* 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 H5BP_shared_t struct */
+H5FL_DEFINE_STATIC(H5BP_shared_t);
+
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_shared_init
+ *
+ * Purpose:	Allocate & initialize shared B-tree info
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Apr 14 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5BP_shared_init (H5BP_t *bpt, const H5BP_class_t *type,
+    size_t node_size, unsigned split_percent, unsigned merge_percent)
+{
+    H5BP_shared_t *shared = NULL;       /* Shared B+ tree information */
+    herr_t ret_value=SUCCEED;           /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT(H5BP_shared_init)
+
+    /* Allocate space for the shared information */
+    if(NULL==(shared = H5FL_CALLOC(H5BP_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;
+
+    /* 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, FAIL, "memory allocation failed")
+#ifdef H5_USING_PURIFY
+HDmemset(shared->page,0,shared->node_size);
+#endif /* H5_USING_PURIFY */
+
+    /* Make shared B-tree info reference counted */
+    if(NULL==(bpt->shared=H5RC_create(shared,H5BP_shared_free)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create ref-count wrapper for shared B+ tree info")
+
+done:
+    if(ret_value<0)
+        if(shared)
+            H5BP_shared_free(shared);
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5BP_shared_init() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_shared_free
+ *
+ * Purpose:	Free shared B+ tree info
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Apr 14 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5BP_shared_free (void *_shared)
+{
+    H5BP_shared_t *shared = (H5BP_shared_t *)_shared;
+    herr_t ret_value=SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_shared_free)
+
+    /* Sanity check */
+    HDassert(shared);
+
+    /* Free the B-tree node buffer */
+    if(shared->page)
+        H5FL_BLK_FREE(node_page,shared->page);
+
+    /* Free the shared B-tree info itself */
+    H5FL_FREE(H5BP_shared_t,shared);
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5BP_shared_free() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_create
+ *
+ * Purpose:	Creates a new empty B+ tree in the file.
+ *
+ * Return:	Non-negative on success (with address of new B-tree
+ *              filled in), negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5BP_create(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type,
+    size_t node_size, unsigned split_percent, unsigned merge_percent,
+    haddr_t *addr_p)
+{
+    H5BP_t *bpt = NULL;                 /* The new B+ tree header information */
+    herr_t ret_value=SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5BP_create, FAIL)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(f);
+    HDassert(type);
+    HDassert(node_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==(bpt = H5FL_MALLOC(H5BP_t)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree header")
+
+    /* Assign internal information */
+    HDmemset(&bpt->cache_info,0,sizeof(H5AC_info_t));
+    bpt->cache_info.is_dirty = TRUE;
+    bpt->depth = 0;
+    bpt->root.addr = HADDR_UNDEF;
+    bpt->root.all_nrec = 0;
+    bpt->root.util = 0;
+
+    /* Initialize shared B-tree info */
+    if(H5BP_shared_init(bpt, type, node_size, split_percent, merge_percent)<0)
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "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)H5BP_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_BPT_HDR, *addr_p, bpt, 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 (bpt)
+            (void)H5BP_cache_hdr_dest(f,bpt);
+    } /* end if */
+    
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5BP_create() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_create_leaf
+ *
+ * Purpose:	Creates empty leaf node of a B+ tree and updates node pointer
+ *              to point to it.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_create_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bpt_shared, H5BP_node_ptr_t *node_ptr)
+{
+    H5BP_leaf_t *leaf=NULL;     /* Pointer to new leaf node created */
+    H5BP_shared_t *shared;      /* Shared B+ tree information */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5BP_create_leaf, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(bpt_shared);
+    HDassert(node_ptr);
+
+    /* Allocate memory for leaf information */
+    if (NULL==(leaf = H5FL_MALLOC(H5BP_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 = bpt_shared;
+    H5RC_INC(leaf->shared);
+
+    /* Get the pointer to the shared B-tree info */
+    shared=H5RC_GET_OBJ(leaf->shared);
+    HDassert(shared);
+
+    /* Create record pool for leaf node */
+    if((leaf->rec_pool = H5MP_create(H5BP_LEAF_POOL_PAGE, H5MP_FLG_DEFAULT)) == NULL)
+        HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "can't allocate memory pool")
+
+    /* Set number of records */
+    leaf->nrec=0;
+    leaf->flags=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 leaf node")
+
+    /* Cache the new B+ tree node */
+    if (H5AC_set(f, dxpl_id, H5AC_BPT_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)H5BP_cache_leaf_dest(f,leaf);
+    } /* end if */
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5BP_create_leaf() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_insert_leaf
+ *
+ * Purpose:	Adds a new record to a B+ tree leaf node.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Apr 22 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_insert_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bpt_shared,
+    H5BP_node_ptr_t *curr_node_ptr, void *udata)
+{
+    H5BP_leaf_t *leaf;                  /* Pointer to leaf node */
+    H5BP_shared_t *shared;              /* Pointer to B+ tree's shared information */
+    int         cmp;                    /* Comparison value of records */
+    unsigned    idx;                    /* Location of record which matches key */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT(H5BP_insert_leaf)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(bpt_shared);
+    HDassert(curr_node_ptr);
+    HDassert(H5F_addr_defined(curr_node_ptr->addr));
+
+if( H5BP_NODE_OVERSIZE(curr_node_ptr->util)) {
+    HDfprintf(stderr,"%s: attempting to insert record into extent node\n",FUNC);
+    HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't handle extent node!")
+}
+    /* Lock B+ tree node */
+    if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BPT_LEAF, curr_node_ptr->addr, &(curr_node_ptr->util), bpt_shared, H5AC_WRITE)))
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B+ tree leaf node")
+
+    /* Get the pointer to the shared B+ tree info */
+    shared=H5RC_GET_OBJ(bpt_shared);
+    HDassert(shared);
+
+#ifndef LATER
+HDfprintf(stderr,"%s: finish record insertion code\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't handle record insertion!")
+#else /* LATER */
+    /* Check for inserting into empty leaf */
+    if(leaf->nrec==0)
+        idx=0;
+    else {
+        /* Find correct location to insert this record */
+        if((cmp = H5BP_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B+ tree")
+        if(cmp > 0)
+            idx++;
+
+        /* Make room for new record */
+        if(idx<leaf->nrec)
+            HDmemmove(H5BP_LEAF_NREC(leaf,shared,idx+1),H5BP_LEAF_NREC(leaf,shared,idx),shared->type->nrec_size*(leaf->nrec-idx));
+    } /* end else */
+
+    /* Make callback to store record in native form */
+    if((shared->type->store)(H5BP_LEAF_NREC(leaf,shared,idx),udata)<0)
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node")
+#endif /* LATER */
+
+    /* Update record count for node pointer to current node */
+    curr_node_ptr->all_nrec++;
+
+    /* Update record count for current node */
+    leaf->nrec++;
+
+done:
+    /* Release the B+ tree leaf node */
+    if (leaf && H5AC_unprotect(f, dxpl_id, H5AC_BPT_LEAF, curr_node_ptr->addr, leaf, H5AC__DIRTIED_FLAG) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release leaf B+ tree node")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5BP_insert_leaf() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_insert
+ *
+ * Purpose:	Adds a new record to the B+ tree.
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5BP_insert(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type, haddr_t addr,
+           void *udata)
+{
+    H5BP_t	*bpt=NULL;              /* Pointer to the B+ tree header */
+    H5BP_shared_t *shared;              /* Pointer to B+ tree's shared information */
+    herr_t	ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI(H5BP_insert, FAIL)
+
+    /* Check arguments. */
+    HDassert(f);
+    HDassert(type);
+    HDassert(H5F_addr_defined(addr));
+
+    /* Look up the B+ tree header */
+    if (NULL == (bpt = H5AC_protect(f, dxpl_id, H5AC_BPT_HDR, addr, type, NULL, H5AC_WRITE)))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B+ tree header")
+
+    /* Get the pointer to the shared B+ tree info */
+    shared=H5RC_GET_OBJ(bpt->shared);
+    HDassert(shared);
+
+    /* Check if the root node is allocated yet */
+    if(!H5F_addr_defined(bpt->root.addr)) {
+        /* Create root node as leaf node in B+ tree */
+        if(H5BP_create_leaf(f, dxpl_id, bpt->shared, &(bpt->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 */
+        bpt->cache_info.is_dirty = TRUE;
+    } /* end if */
+    /* Check if we need to split the root node (equiv. to a 1->2 leaf node split) */
+    else if(H5BP_NODE_OVERSIZE(bpt->root.util) ||
+            (!H5BP_NODE_OVERSIZE(bpt->root.util) && bpt->root.util>=shared->split_percent)) {
+        /* Split root node */
+#ifdef LATER
+        if(H5BP_split_root(f, dxpl_id, bpt, bpt->shared)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node")
+#else /* LATER */
+HDfprintf(stderr,"%s: attempting to split root node\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't split root yet!")
+#endif /* LATER */
+    } /* end if */
+        
+    /* Attempt to insert record into B+ tree */
+    if(bpt->depth>0) {
+#ifdef LATER
+        if(H5BP_insert_internal(f,dxpl_id,bpt->shared,bpt->depth,&(bpt->cache_info),&bpt->root,udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B+ tree internal node")
+#else /* LATER */
+HDfprintf(stderr,"%s: attempting to insert record with internal node\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't insert records yet!")
+#endif /* LATER */
+    } /* end if */
+    else {
+        if(H5BP_insert_leaf(f,dxpl_id,bpt->shared,&bpt->root,udata)<0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B+ tree leaf node")
+    } /* end else */
+
+done:
+    /* Release the B+ tree header info */
+    if (bpt && H5AC_unprotect(f, dxpl_id, H5AC_BPT_HDR, addr, bpt, H5AC__DIRTIED_FLAG) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B+ tree header info")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5BP_insert() */
+
diff --git a/src/H5BPcache.c b/src/H5BPcache.c
new file mode 100644
index 0000000..e511ae2
--- /dev/null
+++ b/src/H5BPcache.c
@@ -0,0 +1,710 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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:		H5BPcache.c
+ *			Apr 19 2005
+ *			Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:		Implement B+ tree metadata cache methods.
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#define H5BP_PACKAGE		/*suppress error about including H5BPpkg  */
+
+/* Private headers */
+#include "H5private.h"		/* Generic Functions			*/
+#include "H5BPpkg.h"		/* B+ trees				*/
+#include "H5Eprivate.h"		/* Error handling		  	*/
+
+/* Local macros */
+
+/* B+ tree format version #'s */
+#define H5BP_HDR_VERSION 0              /* Header */
+#define H5BP_LEAF_VERSION 0             /* Leaf nodes */
+
+
+/* Local typedefs */
+
+/* Local prototypes */
+
+/* Metadata cache callbacks */
+static H5BP_t *H5BP_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata);
+static herr_t H5BP_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BP_t *b);
+static herr_t H5BP_cache_hdr_clear(H5F_t *f, H5BP_t *b, hbool_t destroy);
+static herr_t H5BP_cache_hdr_size(const H5F_t *f, const H5BP_t *bt, size_t *size_ptr);
+static H5BP_leaf_t *H5BP_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nrec, void *_bpt_shared);
+static herr_t H5BP_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BP_leaf_t *l);
+static herr_t H5BP_cache_leaf_clear(H5F_t *f, H5BP_leaf_t *l, hbool_t destroy);
+static herr_t H5BP_cache_leaf_size(const H5F_t *f, const H5BP_leaf_t *l, size_t *size_ptr);
+
+/* Package variables */
+
+/* H5BP headers inherit cache-like properties from H5AC */
+const H5AC_class_t H5AC_BPT_HDR[1] = {{
+    H5AC_BPT_HDR_ID,
+    (H5AC_load_func_t)H5BP_cache_hdr_load,
+    (H5AC_flush_func_t)H5BP_cache_hdr_flush,
+    (H5AC_dest_func_t)H5BP_cache_hdr_dest,
+    (H5AC_clear_func_t)H5BP_cache_hdr_clear,
+    (H5AC_size_func_t)H5BP_cache_hdr_size,
+}};
+
+/* H5BP leaves inherit cache-like properties from H5AC */
+const H5AC_class_t H5AC_BPT_LEAF[1] = {{
+    H5AC_BPT_LEAF_ID,
+    (H5AC_load_func_t)H5BP_cache_leaf_load,
+    (H5AC_flush_func_t)H5BP_cache_leaf_flush,
+    (H5AC_dest_func_t)H5BP_cache_leaf_dest,
+    (H5AC_clear_func_t)H5BP_cache_leaf_clear,
+    (H5AC_size_func_t)H5BP_cache_leaf_size,
+}};
+
+/* Static variables */
+
+/* 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 'void *' array data */
+typedef void *voidp;
+H5FL_SEQ_DEFINE_STATIC(voidp);
+
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static H5BP_t *
+H5BP_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void UNUSED *udata)
+{
+    const H5BP_class_t	*type = (const H5BP_class_t *) _type;
+    size_t node_size;                           /* Size info for B+ tree */
+    unsigned split_percent, merge_percent;      /* Split & merge info for B+ tree */
+    H5BP_t		*bpt = NULL;
+    size_t		size;
+    uint8_t		*buf = NULL;
+    uint8_t		*p;             /* Pointer into raw data buffer */
+    H5BP_t		*ret_value;
+
+    FUNC_ENTER_NOAPI(H5BP_cache_hdr_load, NULL)
+
+    /* Check arguments */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(type);
+
+    if (NULL==(bpt = H5FL_MALLOC(H5BP_t)))
+	HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
+    HDmemset(&bpt->cache_info,0,sizeof(H5AC_info_t));
+
+    /* Compute the size of the B+ tree header on disk */
+    size = H5BP_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, H5BP_HDR_MAGIC, H5BP_SIZEOF_MAGIC))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B+ tree header signature")
+    p += H5BP_SIZEOF_MAGIC;
+
+    /* version */
+    if (*p++ != H5BP_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);
+
+    /* depth of tree */
+    UINT16DECODE(p, bpt->depth);
+
+    /* split & merge %s */
+    UINT16DECODE(p, split_percent);
+    UINT16DECODE(p, merge_percent);
+
+    /* root node pointer */
+    H5F_addr_decode(f, (const uint8_t **)&p, &(bpt->root.addr));
+    H5F_DECODE_LENGTH(f, p, bpt->root.all_nrec);
+    bpt->root.util = *p++;
+
+    /* Initialize shared B+ tree info */
+    if(H5BP_shared_init(bpt, type, node_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 = bpt;
+
+done:
+    if(buf)
+        H5FL_BLK_FREE(header_block,buf);
+    if (!ret_value && bpt)
+        (void)H5BP_cache_hdr_dest(f,bpt);
+    FUNC_LEAVE_NOAPI(ret_value)
+} /*lint !e818 Can't make udata a pointer to const */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BP_t *bpt)
+{
+    herr_t      ret_value = SUCCEED;    /* Return value */
+
+    FUNC_ENTER_NOAPI(H5BP_cache_hdr_flush, FAIL)
+
+    /* check arguments */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(bpt);
+
+    if (bpt->cache_info.is_dirty) {
+        H5BP_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(bpt->shared);
+        HDassert(shared);
+
+        /* Compute the size of the B+ tree header on disk */
+        size = H5BP_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, H5BP_HDR_MAGIC, H5BP_SIZEOF_MAGIC);
+        p += H5BP_SIZEOF_MAGIC;
+
+        /* version # */
+        *p++ = H5BP_HDR_VERSION;
+
+        /* B+ tree type */
+        *p++ = shared->type->id;
+
+        /* node size (in bytes) */
+        UINT32ENCODE(p, shared->node_size);
+
+        /* depth of tree */
+        UINT16ENCODE(p, bpt->depth);
+
+        /* split & merge %s */
+        UINT16ENCODE(p, shared->split_percent);
+        UINT16ENCODE(p, shared->merge_percent);
+
+        /* root node pointer */
+        H5F_addr_encode(f, &p, bpt->root.addr);
+        H5F_ENCODE_LENGTH(f, p, bpt->root.all_nrec);
+        *p++ = bpt->root.util;
+
+	/* 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);
+
+	bpt->cache_info.is_dirty = FALSE;
+    } /* end if */
+
+    if (destroy)
+        if (H5BP_cache_hdr_dest(f, bpt) < 0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B+ tree header")
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5BP_cache_hdr_flush() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+/* ARGSUSED */
+herr_t
+H5BP_cache_hdr_dest(H5F_t UNUSED *f, H5BP_t *bpt)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_cache_hdr_dest)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(bpt);
+
+    /* Decrement reference count on shared B+ tree info */
+    if(bpt->shared)
+        H5RC_DEC(bpt->shared);
+
+    /* Free B+ tree header info */
+    H5FL_FREE(H5BP_t,bpt);
+
+    FUNC_LEAVE_NOAPI(SUCCEED)
+} /* end H5BP_cache_hdr_dest() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_cache_hdr_clear(H5F_t *f, H5BP_t *bpt, hbool_t destroy)
+{
+    herr_t ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT(H5BP_cache_hdr_clear)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(bpt);
+
+    /* Reset the dirty flag.  */
+    bpt->cache_info.is_dirty = FALSE;
+ 
+    if (destroy)
+        if (H5BP_cache_hdr_dest(f, bpt) < 0)
+	    HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B+ tree header")
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5BP_cache_hdr_clear() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_cache_hdr_size(const H5F_t *f, const H5BP_t UNUSED *bpt, size_t *size_ptr)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_cache_hdr_size)
+
+    /* check arguments */
+    HDassert(f);
+    HDassert(size_ptr);
+
+    /* Set size value */
+    *size_ptr = H5BP_HEADER_SIZE(f);
+
+    FUNC_LEAVE_NOAPI(SUCCEED)
+} /* H5BP_cache_hdr_size() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static H5BP_leaf_t *
+H5BP_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nrec, void *_bpt_shared)
+{
+    const unsigned char *nrec = (const unsigned char *)_nrec;
+    H5RC_t 		*bpt_shared=(H5RC_t *)_bpt_shared;        /* Shared B+ tree information */
+    H5BP_shared_t 	*shared;        /* Shared B+ tree information */
+    H5BP_leaf_t		*leaf = NULL;   /* Pointer to new leaf */
+    uint8_t		*p;             /* Pointer into raw data buffer */
+    size_t              rec_size;       /* Size of records */
+    unsigned		u;              /* Local index variable */
+    H5BP_leaf_t		*ret_value;
+
+    FUNC_ENTER_NOAPI(H5BP_cache_leaf_load, NULL)
+
+    /* Check arguments */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(bpt_shared);
+
+    if (NULL==(leaf = H5FL_MALLOC(H5BP_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 = bpt_shared;
+    H5RC_INC(leaf->shared);
+
+    /* Get the pointer to the shared B+ tree info */
+    shared=H5RC_GET_OBJ(leaf->shared);
+    HDassert(shared);
+
+    /* Check if we can use existing buffer for node */
+    /* 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, H5BP_LEAF_MAGIC, H5BP_SIZEOF_MAGIC))
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B+ tree leaf node signature")
+    p += H5BP_SIZEOF_MAGIC;
+
+    /* version */
+    if (*p++ != H5BP_LEAF_VERSION)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B+ tree leaf node version")
+
+    /* B+ tree type */
+    if (*p++ != (uint8_t)shared->type->id)
+	HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B+ tree type")
+
+    /* Set the number of records in the leaf */
+    leaf->nrec = *nrec;
+
+    /* Get the status flags for the leaf */
+    leaf->flags = *p++;
+
+    /* Create record pool for leaf node */
+    if((leaf->rec_pool = H5MP_create(H5BP_LEAF_POOL_PAGE, H5MP_FLG_DEFAULT)) == NULL)
+        HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "can't allocate memory pool")
+
+    /* Retrieve variable-length record information, if present */
+    if(H5BP_LEAF_REC_VARLEN(leaf->flags)) {
+        /* Allocate space for the record pointers */
+        if((leaf->rec_ptr = H5FL_SEQ_MALLOC(voidp, leaf->nrec)) == NULL)
+            HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "can't allocate record pointers for node")
+
+        /* Work through the records on disk and insert them into array for node */
+        for(u = 0; u < leaf->nrec; u++) {
+            size_t  rec_len;        /* Index of current record */
+
+            /* Determine the length of the record */
+            UINT16DECODE(p, rec_len);
+
+            /* Decode the record */
+            if((leaf->rec_ptr[u] = (shared->type->decode)(f, leaf->rec_pool, p, rec_len)) == NULL)
+                HGOTO_ERROR(H5E_BTREE, H5E_CANTDECODE, NULL, "can't decode B+ tree record")
+            p += rec_len;
+        } /* end for */
+    } /* end if */
+    else {
+        /* Retrieve the records' size */
+        UINT16DECODE(p, rec_size);
+
+HDfprintf(stderr,"%s: attempting to decode fixed-size records from leaf node\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, NULL, "Can't decode records yet!")
+    } /* end else */
+
+    /* Set return value */
+    ret_value = leaf;
+
+done:
+    if (!ret_value && leaf)
+        (void)H5BP_cache_leaf_dest(f,leaf);
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5BP_cache_leaf_load() */ /*lint !e818 Can't make udata a pointer to const */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BP_leaf_t *leaf)
+{
+    herr_t      ret_value = SUCCEED;    /* Return value */
+
+    FUNC_ENTER_NOAPI(H5BP_cache_leaf_flush, FAIL)
+
+    /* check arguments */
+    HDassert(f);
+    HDassert(H5F_addr_defined(addr));
+    HDassert(leaf);
+
+    if (leaf->cache_info.is_dirty) {
+        H5BP_shared_t *shared;  /* Shared B+ tree information */
+        uint8_t *p;             /* Pointer into raw data buffer */
+#ifdef LATER
+        uint8_t *native;        /* Pointer to native keys */
+        unsigned u;             /* Local index variable */
+#endif /* LATER */
+
+        /* Get the pointer to the shared B+ tree info */
+        shared=H5RC_GET_OBJ(leaf->shared);
+        HDassert(shared);
+
+        p = shared->page;
+
+        /* magic number */
+        HDmemcpy(p, H5BP_LEAF_MAGIC, H5BP_SIZEOF_MAGIC);
+        p += H5BP_SIZEOF_MAGIC;
+
+        /* version # */
+        *p++ = H5BP_LEAF_VERSION;
+
+        /* B+ tree type */
+        *p++ = shared->type->id;
+
+        /* status flags */
+        *p++ = leaf->flags;
+
+        /* Serialize records */
+        if(H5BP_LEAF_REC_VARLEN(leaf->flags)) {
+            unsigned u;         /* Local index */
+
+            /* Work through the records in memory and encode them to disk */
+            for(u = 0; u < leaf->nrec; u++) {
+                size_t  rec_len;        /* Index of current record */
+                uint8_t *tp;            /* Temporary pointer into raw data buffer */
+
+                /* Save the location for the record length */
+                tp = p;
+
+                /* Skip over the location for the record length */
+                p += 2;
+
+                /* Encode the record */
+                if((shared->type->encode)(f, leaf->rec_ptr[u], p, &rec_len) < 0)
+                    HGOTO_ERROR(H5E_BTREE, H5E_CANTENCODE, NULL, "can't encode B+ tree record")
+                assert(rec_len > 0);
+                p += rec_len;
+
+                /* Encode the record length */
+                UINT16ENCODE(tp, rec_len);
+            } /* end for */
+        } /* end if */
+        else {
+HDfprintf(stderr,"%s: attempting to decode fixed-size records from leaf node\n",FUNC);
+HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, NULL, "Can't decode records yet!")
+        } /* end else */
+
+#ifdef LATER
+        /* 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, "unable to encode B+ tree record")
+
+            /* Move to next record */
+            p += shared->rrec_size;
+            native += shared->type->nrec_size;
+        } /* end for */
+#endif /* LATER */
+
+	/* 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 (H5BP_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)
+} /* H5BP_cache_leaf_flush() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+/* ARGSUSED */
+herr_t
+H5BP_cache_leaf_dest(H5F_t UNUSED *f, H5BP_leaf_t *leaf)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_cache_leaf_dest)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(leaf);
+
+    /* Decrement reference count on shared B+ tree info */
+    if(leaf->shared)
+        H5RC_DEC(leaf->shared);
+
+    /* Release B+ tree leaf node record pointer array */
+    H5FL_SEQ_FREE(voidp, leaf->rec_ptr);
+
+    /* Release B+ tree leaf node record memory pool */
+    H5MP_close(leaf->rec_pool);
+
+    /* Free B+ tree leaf node info */
+    H5FL_FREE(H5BP_leaf_t, leaf);
+
+    FUNC_LEAVE_NOAPI(SUCCEED)
+} /* end H5BP_cache_leaf_dest() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_cache_leaf_clear(H5F_t *f, H5BP_leaf_t *leaf, hbool_t destroy)
+{
+    herr_t ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT(H5BP_cache_leaf_clear)
+
+    /*
+     * Check arguments.
+     */
+    HDassert(leaf);
+
+    /* Reset the dirty flag.  */
+    leaf->cache_info.is_dirty = FALSE;
+ 
+    if (destroy)
+        if (H5BP_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 H5BP_cache_leaf_clear() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_cache_leaf_size(const H5F_t UNUSED *f, const H5BP_leaf_t *leaf, size_t *size_ptr)
+{
+    H5BP_shared_t *shared;      /* Shared B+ tree information */
+
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_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)
+} /* H5BP_cache_leaf_size() */
+
diff --git a/src/H5BPdbg.c b/src/H5BPdbg.c
new file mode 100644
index 0000000..07dd492
--- /dev/null
+++ b/src/H5BPdbg.c
@@ -0,0 +1,120 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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:		H5BPdbg.c
+ *			Apr 19 2005
+ *			Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:		Dump debugging information about a B+ tree.
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#define H5BP_PACKAGE		/*suppress error about including H5BPpkg  */
+
+/* Private headers */
+#include "H5private.h"		/* Generic Functions			*/
+#include "H5BPpkg.h"		/* B+ trees				*/
+#include "H5Eprivate.h"		/* Error handling		  	*/
+#include "H5FLprivate.h"	/* Free Lists                           */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_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
+ *		Apr 19 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5BP_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth,
+    const H5BP_class_t *type)
+{
+    H5BP_t	*bpt = NULL;
+    H5BP_shared_t 	*shared;      /* Shared B+ tree information */
+    herr_t      ret_value=SUCCEED;       /* Return value */
+
+    FUNC_ENTER_NOAPI(H5BP_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 == (bpt = H5AC_protect(f, dxpl_id, H5AC_BPT_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(bpt->shared);
+    assert(shared);
+
+    /*
+     * Print the values.
+     */
+    HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth,
+	      "Tree type ID:",
+	      (shared->type->id == H5BP_TEST_ID ? "H5BP_TEST_ID" :
+              "Unknown!"));
+    HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth,
+	      "Size of node:",
+	      shared->node_size);
+    HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth,
+	      "Dirty flag:",
+	      bpt->cache_info.is_dirty ? "True" : "False");
+    HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth,
+	      "Depth:",
+	      bpt->depth);
+    HDfprintf(stream, "%*s%-*s %Hu\n", indent, "", fwidth,
+	      "Number of records in tree:",
+	      bpt->root.all_nrec);
+    if(H5BP_NODE_OVERSIZE(bpt->root.util))
+        HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth,
+                  "Root node size multiplier:",
+                  (unsigned)(bpt->root.util & 0x7f));
+    else
+        HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth,
+                  "Root node size utilization:",
+                  (unsigned)bpt->root.util);
+    HDfprintf(stream, "%*s%-*s %a\n", indent, "", fwidth,
+	      "Address of root node:",
+	      bpt->root.addr);
+    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);
+
+done:
+    if (bpt && H5AC_unprotect(f, dxpl_id, H5AC_BPT_HDR, addr, bpt, H5AC__NO_FLAGS_SET) < 0)
+        HDONE_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B+ tree header")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5BP_hdr_debug() */
+
diff --git a/src/H5BPpkg.h b/src/H5BPpkg.h
new file mode 100644
index 0000000..3ec5667
--- /dev/null
+++ b/src/H5BPpkg.h
@@ -0,0 +1,212 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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>
+ *		Thursday, April 14, 2005
+ *
+ * Purpose:	This file contains declarations which are visible only within
+ *		the H5BP package.  Source files outside the H5BP package should
+ *		include H5BPprivate.h instead.
+ */
+#ifndef H5BP_PACKAGE
+#error "Do not include this file outside the H5BP package!"
+#endif
+
+#ifndef _H5BPpkg_H
+#define _H5BPpkg_H
+
+/* Get package's private header */
+#include "H5BPprivate.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 H5BP_SIZEOF_MAGIC               4
+
+/* B+ tree signatures */
+#define H5BP_HDR_MAGIC                  "BPHD"          /* Header */
+#define H5BP_INT_MAGIC                  "BPBR"          /* Branch node */
+#define H5BP_TWIG_MAGIC                 "BPTW"          /* Twig node */
+#define H5BP_LEAF_MAGIC                 "BPLF"          /* Leaf node */
+#define H5BP_EXTENT_MAGIC               "BPEX"          /* Extent node */
+
+/* Size of storage for number of separators per node (on disk) */
+#define H5BP_SIZEOF_SEPS_PER_NODE       2
+
+/* Size of storage for "node size multiplier" (on disk) */
+#define H5BP_SIZEOF_NODE_MULT           1
+
+/* Size of a "full" node pointer (on disk) */
+#define H5BP_NODE_POINTER_SIZE(f)       (H5F_SIZEOF_ADDR(f)+H5F_SIZEOF_SIZE(f)+H5BP_SIZEOF_NODE_MULT)
+
+/* Size of the B+ tree header on disk */
+#define H5BP_HEADER_SIZE(f)     (                                             \
+    4 + /* Signature */                                                       \
+    1 + /* Version */                                                         \
+    1 + /* Tree type */                                                       \
+    4 + /* Node 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%) */                \
+    H5BP_NODE_POINTER_SIZE(f))  /* Node pointer to root node in tree */
+
+/* Determine whether a node is oversized */
+/* The high bit is set in utilization field for oversized nodes */
+#define H5BP_NODE_OVERSIZE(u)   ((u) & 0x80)
+
+/* Determine whether a leaf node has variable-length records */
+/* The low bit is set in "flag" field for nodes w/variable-length records */
+#define H5BP_LEAF_REC_VARLEN(u)   ((u) & 0x01)
+
+/* Size of memory pool pages for leaf nodes */
+#define H5BP_LEAF_POOL_PAGE     H5MP_PAGE_SIZE_DEFAULT
+
+
+/****************************/
+/* Package Private Typedefs */
+/****************************/
+
+/* A "node pointer" to another B+ tree node */
+typedef struct {
+    haddr_t     addr;           /* Address of other node */
+    hsize_t     all_nrec;       /* Number of records in node pointed to and all it's children */
+    unsigned char util;         /* Percent utilization/page node multiple */
+} H5BP_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 H5BP_shared_t {
+    /* Shared internal data structures */
+    const H5BP_class_t	*type;	 /* Type of tree			     */
+    uint8_t	        *page;	 /* Disk page */
+
+    /* 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                */
+} H5BP_shared_t;
+
+/* The B+ tree information */
+typedef struct H5BP_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                    */
+    H5BP_node_ptr_t root;       /* Node pointer to root node in B+ tree       */
+    H5RC_t	*shared;	/* Ref-counted shared info	              */
+} H5BP_t;
+
+/* B+ tree internal branch node information */
+typedef struct H5BP_branch_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     *int_native;    /* Pointer to native records                  */
+    H5BP_node_ptr_t *node_ptrs; /* Pointer to node pointers                   */
+    unsigned    nrec;           /* Number of records in node                  */
+} H5BP_branch_t;
+
+/* B+ tree internal twig node information */
+typedef struct H5BP_twig_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     *int_native;    /* Pointer to native records                  */
+    H5BP_node_ptr_t *node_ptrs; /* Pointer to node pointers                   */
+    unsigned    nrec;           /* Number of records in node                  */
+} H5BP_twig_t;
+
+/* B+ tree leaf node information */
+typedef struct H5BP_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	              */
+    H5MP_pool_t *rec_pool;      /* Pool containing records for node           */
+    void        **rec_ptr;      /* Array of pointers to records in pool       */
+    unsigned    nrec;           /* Number of records in node                  */
+    unsigned char flags;        /* Status flags for leaf node                 */
+} H5BP_leaf_t;
+
+#ifdef H5BP_TESTING
+/* Record for testing B+ trees */
+typedef struct {
+    hsize_t     count;
+    char        *name;
+} H5BP_test_rec_t;
+#endif /* H5BP_TESTING */
+
+
+/*****************************/
+/* Package Private Variables */
+/*****************************/
+
+/* H5BP header inherits cache-like properties from H5AC */
+H5_DLLVAR const H5AC_class_t H5AC_BPT_HDR[1];
+
+/* H5BP branch node inherits cache-like properties from H5AC */
+H5_DLLVAR const H5AC_class_t H5AC_BPT_BRANCH[1];
+
+/* H5BP twig node inherits cache-like properties from H5AC */
+H5_DLLVAR const H5AC_class_t H5AC_BPT_TWIG[1];
+
+/* H5BP leaf node inherits cache-like properties from H5AC */
+H5_DLLVAR const H5AC_class_t H5AC_BPT_LEAF[1];
+
+/* Declare a free list to manage the H5BP_t struct */
+H5FL_EXTERN(H5BP_t);
+
+/* Declare a free list to manage the H5BP_branch_t struct */
+H5FL_EXTERN(H5BP_branch_t);
+
+/* Declare a free list to manage the H5BP_twig_t struct */
+H5FL_EXTERN(H5BP_twig_t);
+
+/* Declare a free list to manage the H5BP_leaf_t struct */
+H5FL_EXTERN(H5BP_leaf_t);
+
+/* Internal B+ tree testing class */
+#ifdef H5BP_TESTING
+H5_DLLVAR const H5BP_class_t H5BP_TEST[1];
+#endif /* H5BP_TESTING */
+
+
+/******************************/
+/* Package Private Prototypes */
+/******************************/
+H5_DLL herr_t H5BP_shared_free (void *_shared);
+H5_DLL herr_t H5BP_shared_init (H5BP_t *bpt, const H5BP_class_t *type,
+    size_t node_size, unsigned split_percent, unsigned merge_percent);
+H5_DLL herr_t H5BP_cache_hdr_dest(H5F_t *f, H5BP_t *bpt);
+H5_DLL herr_t H5BP_cache_leaf_dest(H5F_t UNUSED *f, H5BP_leaf_t *leaf);
+H5_DLL herr_t H5BP_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
+    FILE *stream, int indent, int fwidth, const H5BP_class_t *type);
+
+#endif /* _H5BPpkg_H */
+
diff --git a/src/H5BPprivate.h b/src/H5BPprivate.h
new file mode 100644
index 0000000..88048ef
--- /dev/null
+++ b/src/H5BPprivate.h
@@ -0,0 +1,86 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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:		H5BPprivate.h
+ *			Apr 14 2005
+ *			Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:		Private header for library accessible B+ tree routines.
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#ifndef _H5BPprivate_H
+#define _H5BPprivate_H
+
+/* Include package's public header */
+#include "H5BPpublic.h"
+
+/* Private headers needed by this file */
+#include "H5Fprivate.h"		/* File access				*/
+#include "H5MPprivate.h"	/* Memory Pools				*/
+
+/**************************/
+/* Library Private Macros */
+/**************************/
+
+     
+/****************************/
+/* Library Private Typedefs */
+/****************************/
+
+/* B+ tree IDs for various internal things. */
+typedef enum H5BP_subid_t {
+    H5BP_TEST_ID	 = 0,	/* B+ tree is for testing (do not use for actual data) */
+    H5BP_NUM_BTREE_ID           /* Number of B-tree IDs (must be last)   */
+} H5BP_subid_t;
+
+/*
+ * Each class of object that can be pointed to by a B+ tree has a
+ * variable of this type that contains class variables and methods.
+ */
+typedef struct H5BP_class_t {
+    H5BP_subid_t id;				/*id as found in file*/
+
+    /* Copy native application record */
+    void * (*copy)(const void *record);         /* Copy native record */
+
+    /* Compare key */
+    herr_t (*compare)(const void *key1, const void *key2);              /*  Compare two native keys */
+
+    /* Encode & decode record values */
+    /* (i.e. native application form <-> disk form) */
+    herr_t (*raw_len)(const H5F_t *f, const void *record, size_t *len); /*  Determine length of raw (disk) form from native form */
+    herr_t (*encode)(const H5F_t *f, const uint8_t *native, uint8_t *raw, size_t *rec_len); /*  Encode record from native form to disk storage form */
+    void * (*decode)(const H5F_t *f, H5MP_pool_t *pool, const uint8_t *raw, size_t rec_len);               /*  Decode record from disk storage form to native form */
+
+    /* Debug record values */
+    herr_t (*debug) (FILE *stream, const H5F_t *f, hid_t dxpl_id,       /* Print a record for debugging */
+        int indent, int fwidth, const void *record, const void *udata);
+
+} H5BP_class_t;
+
+/***************************************/
+/* Library-private Function Prototypes */
+/***************************************/
+H5_DLL herr_t H5BP_create(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type,
+    size_t node_size, unsigned split_percent, unsigned merge_percent,
+    haddr_t *addr_p);
+H5_DLL herr_t H5BP_insert(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type,
+    haddr_t addr, void *udata);
+
+#endif /* _H5BPprivate_H */
+
diff --git a/src/H5BPpublic.h b/src/H5BPpublic.h
new file mode 100644
index 0000000..8f3dd25
--- /dev/null
+++ b/src/H5BPpublic.h
@@ -0,0 +1,53 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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:             H5BPpublic.h
+ *                      Apr 19 2005
+ *                      Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:             Public declarations for the H5BP package.
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef _H5BPpublic_H
+#define _H5BPpublic_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 /* _H5BPpublic_H */
+
+
diff --git a/src/H5BPtest.c b/src/H5BPtest.c
new file mode 100644
index 0000000..025bdf7
--- /dev/null
+++ b/src/H5BPtest.c
@@ -0,0 +1,237 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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>
+ *              Thursday, April 19, 2005
+ *
+ * Purpose:	B+ tree testing functions.
+ */
+
+#define H5BP_PACKAGE		/*suppress error about including H5BPpkg  */
+#define H5BP_TESTING		/*suppress warning about H5BP testing funcs*/
+
+/* Private headers */
+#include "H5private.h"		/* Generic Functions			*/
+#include "H5BPpkg.h"		/* B+ trees				*/
+#include "H5Eprivate.h"		/* Error handling		  	*/
+#include "H5MMprivate.h"	/* Memory management			*/
+
+/* Static Prototypes */
+static void *H5BP_test_copy(const void *rec);
+static herr_t H5BP_test_compare(const void *rec1, const void *rec2);
+static herr_t H5BP_test_raw_len(const H5F_t *f, const void *record, size_t *len);
+static herr_t H5BP_test_encode(const H5F_t *f, const uint8_t *native,
+    uint8_t *raw, size_t *rec_len);
+static void *H5BP_test_decode(const H5F_t *f, H5MP_pool_t *pool,
+    const uint8_t *raw, size_t rec_len);
+static herr_t H5BP_test_debug(FILE *stream, const H5F_t *f, hid_t dxpl_id,
+    int indent, int fwidth, const void *record, const void *_udata);
+
+/* Package variables */
+const H5BP_class_t H5BP_TEST[1]={{   /* B+ tree class information */
+    H5BP_TEST_ID,                   /* Type of B+ tree */
+    H5BP_test_copy,                 /* Record copy callback */
+    H5BP_test_compare,              /* Record comparison callback */
+    H5BP_test_raw_len,              /* Record 'raw len' callback */
+    H5BP_test_encode,               /* Record encoding callback */
+    H5BP_test_decode,               /* Record decoding callback */
+    H5BP_test_debug                 /* Record debugging callback */
+}};
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_test_copy
+ *
+ * Purpose:	Copy native information record
+ *
+ * Return:	Pointer to new record on success, NULL on failure
+ *
+ * Programmer:	Quincey Koziol
+ *              Monday, April 25, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static void *
+H5BP_test_copy(const void *rec)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_copy)
+
+    /* Copy record */
+    FUNC_LEAVE_NOAPI(HDstrdup(rec));
+} /* H5BP_test_copy() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_test_compare
+ *
+ * Purpose:	Compare two native information records, according to some key
+ *
+ * Return:	<0 if rec1 < rec2
+ *              =0 if rec1 == rec2
+ *              >0 if rec1 > rec2
+ *
+ * Programmer:	Quincey Koziol
+ *              Tuesday, April 19, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_test_compare(const void *rec1, const void *rec2)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_compare)
+
+    FUNC_LEAVE_NOAPI(HDstrcmp(*(const char **)rec1, *(const char **)rec2));
+} /* H5BP_test_compare() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_test_raw_len
+ *
+ * Purpose:	Determine the length of the raw form of a record
+ *
+ * Return:	<0 if rec1 < rec2
+ *              =0 if rec1 == rec2
+ *              >0 if rec1 > rec2
+ *
+ * Programmer:	Quincey Koziol
+ *              Tuesday, April 19, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_test_raw_len(const H5F_t UNUSED *f, const void *record, size_t *len)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_raw_len)
+
+    *len = HDstrlen((const char *)record);
+
+    FUNC_LEAVE_NOAPI(SUCCEED);
+} /* H5BP_test_raw_len() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_test_encode
+ *
+ * Purpose:	Encode native information into raw form for storing on disk
+ *
+ * Return:	Success:	non-negative
+ *
+ *		Failure:	negative
+ *
+ * Programmer:	Quincey Koziol
+ *              Tuesday, April 19, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_test_encode(const H5F_t *f, const uint8_t *native, uint8_t *raw, size_t *rec_len)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_encode)
+
+    /* Sanity check */
+    HDassert(f);
+    HDassert(native);
+    HDassert(raw);
+    HDassert(rec_len);
+
+    /* Get the record length */
+    *rec_len = HDstrlen((const char *)native);
+
+    /* "Encode" the record */
+    HDmemcpy(raw, native, *rec_len);
+
+    FUNC_LEAVE_NOAPI(SUCCEED);
+} /* H5BP_test_encode() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_test_decode
+ *
+ * Purpose:	Decode raw disk form of record into native form
+ *
+ * Return:	Success:	non-negative
+ *
+ *		Failure:	negative
+ *
+ * Programmer:	Quincey Koziol
+ *              Tuesday, April 19, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static void *
+H5BP_test_decode(const H5F_t *f, H5MP_pool_t *pool, const uint8_t *raw, size_t rec_len)
+{
+    void *ret_value;            /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT(H5BP_test_decode)
+
+    /* Sanity check */
+    HDassert(f);
+    HDassert(pool);
+    HDassert(raw);
+    HDassert(rec_len > 0);
+
+    /* Allocate space for the record */
+    if((ret_value = H5MP_malloc(pool, rec_len + 1)) == NULL)
+        HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "Can't allocate space for record")
+
+    /* "Decode" the record */
+    HDmemcpy(ret_value, raw, rec_len);
+    *((unsigned char *)ret_value + rec_len) = '\0';
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* H5BP_test_decode() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5BP_test_debug
+ *
+ * Purpose:	Debug native form of record
+ *
+ * Return:	Success:	non-negative
+ *
+ *		Failure:	negative
+ *
+ * Programmer:	Quincey Koziol
+ *              Tuesday, April 19, 2005
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5BP_test_debug(FILE *stream, const H5F_t UNUSED *f, hid_t UNUSED dxpl_id, int indent, int fwidth,
+		      const void *record, const void UNUSED *_udata)
+{
+    FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_debug)
+
+    HDassert (record);
+
+    HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth, "Record:",
+        *(const char *)record);
+
+    FUNC_LEAVE_NOAPI(SUCCEED);
+} /* H5BP_test_debug() */
+
diff --git a/src/H5Cpkg.h b/src/H5Cpkg.h
index 7d708f8..2ab2e9b 100644
--- a/src/H5Cpkg.h
+++ b/src/H5Cpkg.h
@@ -574,7 +574,7 @@
  ****************************************************************************/
 
 #define H5C__H5C_T_MAGIC	0x005CAC0E
-#define H5C__MAX_NUM_TYPE_IDS	10
+#define H5C__MAX_NUM_TYPE_IDS	12
 
 struct H5C_t
 {
diff --git a/src/Makefile.am b/src/Makefile.am
index 0349292..4ab403a 100755
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -42,7 +42,8 @@ DISTCLEAN=libhdf5.settings
 
 # library sources
 libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c      \
-        H5B2test.c H5BT.c H5BTbtree2.c H5BTcache.c H5BTdbg.c H5BTtest.c H5C.c \
+        H5B2test.c H5BP.c H5BPcache.c H5BPdbg.c H5BPtest.c \
+        H5BT.c H5BTbtree2.c H5BTcache.c H5BTdbg.c H5BTtest.c H5C.c \
         H5D.c \
         H5Dcontig.c \
         H5Dcompact.c \
@@ -72,7 +73,7 @@ libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c      \
 
 # Public headers
 include_HEADERS =H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5B2public.h \
-        H5BTpublic.h H5Cpublic.h H5Dpublic.h  \
+        H5BPpublic.h H5BTpublic.h H5Cpublic.h H5Dpublic.h  \
         H5Epubgen.h H5Epublic.h H5Fpublic.h H5FDpublic.h H5FDcore.h H5FDfamily.h          \
         H5FDfphdf5.h H5FDlog.h H5FDmpi.h H5FDmpio.h H5FDmpiposix.h              \
         H5FDmulti.h H5FDsec2.h  H5FDstdio.h H5FDstream.h H5FPpublic.h             \
diff --git a/src/Makefile.in b/src/Makefile.in
index f22db4c..dbb59a7 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -83,8 +83,9 @@ libLTLIBRARIES_INSTALL = $(INSTALL)
 LTLIBRARIES = $(lib_LTLIBRARIES)
 libhdf5_la_LIBADD =
 am_libhdf5_la_OBJECTS = H5.lo H5A.lo H5AC.lo H5B.lo H5B2.lo \
-	H5B2cache.lo H5B2dbg.lo H5B2test.lo H5BT.lo H5BTbtree2.lo \
-	H5BTcache.lo H5BTdbg.lo H5BTtest.lo H5C.lo H5D.lo H5Dcontig.lo \
+	H5B2cache.lo H5B2dbg.lo H5B2test.lo H5BP.lo H5BPcache.lo \
+	H5BPdbg.lo H5BPtest.lo H5BT.lo H5BTbtree2.lo H5BTcache.lo \
+	H5BTdbg.lo H5BTtest.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 H5Fmount.lo \
 	H5Fsuper.lo H5FD.lo H5FDcore.lo H5FDfamily.lo H5FDfphdf5.lo \
@@ -362,7 +363,8 @@ DISTCLEAN = libhdf5.settings
 
 # library sources
 libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c      \
-        H5B2test.c H5BT.c H5BTbtree2.c H5BTcache.c H5BTdbg.c H5BTtest.c H5C.c \
+        H5B2test.c H5BP.c H5BPcache.c H5BPdbg.c H5BPtest.c \
+        H5BT.c H5BTbtree2.c H5BTcache.c H5BTdbg.c H5BTtest.c H5C.c \
         H5D.c \
         H5Dcontig.c \
         H5Dcompact.c \
@@ -392,7 +394,7 @@ libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c      \
 
 # Public headers
 include_HEADERS = H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5B2public.h \
-        H5BTpublic.h H5Cpublic.h H5Dpublic.h  \
+        H5BPpublic.h H5BTpublic.h H5Cpublic.h H5Dpublic.h  \
         H5Epubgen.h H5Epublic.h H5Fpublic.h H5FDpublic.h H5FDcore.h H5FDfamily.h          \
         H5FDfphdf5.h H5FDlog.h H5FDmpi.h H5FDmpio.h H5FDmpiposix.h              \
         H5FDmulti.h H5FDsec2.h  H5FDstdio.h H5FDstream.h H5FPpublic.h             \
@@ -529,6 +531,10 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2cache.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2dbg.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2test.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BP.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BPcache.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BPdbg.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BPtest.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BT.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BTbtree2.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BTcache.Plo@am__quote@