[svn-r17649] Description:

	Refactor v2 B-trees to pin the B-tree header in the cache instead of
using separate reference counted data structure.

Tested on:
        FreeBSD/32 6.3 (duty) in debug mode
        FreeBSD/64 6.3 (liberty) w/C++ & FORTRAN, in debug mode
        Linux/32 2.6 (jam) w/PGI compilers, w/default API=1.8.x,
                w/C++ & FORTRAN, w/threadsafe, in debug mode
        Linux/64-amd64 2.6 (smirom) w/Intel compilers, w/default API=1.6.x,
                w/C++ & FORTRAN, in production mode
        Solaris/32 2.10 (linew) w/deprecated symbols disabled, w/C++ & FORTRAN,
                w/szip filter, in production mode
        Linux/64-ia64 2.6 (cobalt) w/Intel compilers, w/C++ & FORTRAN,
                in production mode
        Linux/64-ia64 2.4 (tg-login3) w/parallel, w/FORTRAN, in debug mode
        Linux/64-amd64 2.6 (abe) w/parallel, w/FORTRAN, in production mode
        Mac OS X/32 10.6.1 (amazon) in debug mode
        Mac OS X/32 10.6.1 (amazon) w/C++ & FORTRAN, w/threadsafe,
                in production mode

1 files changed, 363 insertions, 0 deletions

diff --git a/src/H5B2hdr.c b/src/H5B2hdr.c
new file mode 100644
index 0000000..7180d99
--- /dev/null
+++ b/src/H5B2hdr.c
@@ -0,0 +1,363 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * Copyright by The HDF Group.                                               *
+ * 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://hdfgroup.org/HDF5/doc/Copyright.html.  If you do not have          *
+ * access to either file, you may request a copy from help@hdfgroup.org.     *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*-------------------------------------------------------------------------
+ *
+ * Created:		H5B2int.c
+ *			Feb 27 2006
+ *			Quincey Koziol <koziol@ncsa.uiuc.edu>
+ *
+ * Purpose:		Internal routines for managing v2 B-trees.
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/****************/
+/* Module Setup */
+/****************/
+
+#define H5B2_PACKAGE		/*suppress error about including H5B2pkg  */
+
+/***********/
+/* Headers */
+/***********/
+#include "H5private.h"		/* Generic Functions			*/
+#include "H5B2pkg.h"		/* v2 B-trees				*/
+#include "H5Eprivate.h"		/* Error handling		  	*/
+#include "H5MFprivate.h"	/* File memory management		*/
+#include "H5Vprivate.h"		/* Vectors and arrays 			*/
+
+/****************/
+/* Local Macros */
+/****************/
+
+/* Number of records that fit into leaf node */
+#define H5B2_NUM_LEAF_REC(n, r) \
+    (((n) - H5B2_LEAF_PREFIX_SIZE) / (r))
+
+/* Uncomment this macro to enable extra sanity checking */
+/* #define H5B2_DEBUG */
+
+/******************/
+/* Local Typedefs */
+/******************/
+
+
+/********************/
+/* Package Typedefs */
+/********************/
+
+
+/********************/
+/* Local Prototypes */
+/********************/
+
+
+/*********************/
+/* Package Variables */
+/*********************/
+
+
+/*****************************/
+/* Library Private Variables */
+/*****************************/
+
+
+/*******************/
+/* Local 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 'size_t' sequence information */
+H5FL_SEQ_DEFINE_STATIC(size_t);
+
+/* Declare a free list to manage the 'H5B2_node_info_t' sequence information */
+H5FL_SEQ_DEFINE(H5B2_node_info_t);
+
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_hdr_init
+ *
+ * Purpose:	Allocate & initialize B-tree header info
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_hdr_init(H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type,
+    unsigned depth, size_t node_size, size_t rrec_size,
+    unsigned split_percent, unsigned merge_percent)
+{
+    size_t sz_max_nrec;                 /* Temporary variable for range checking */
+    unsigned u_max_nrec_size;           /* Temporary variable for range checking */
+    unsigned u;                         /* Local index variable */
+    herr_t ret_value = SUCCEED;         /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_hdr_init)
+
+    /* Initialize basic information */
+    bt2->f = f;
+    bt2->rc = 0;
+
+    /* Assign dynamic information */
+    bt2->depth = depth;
+
+    /* Assign user's information */
+    bt2->split_percent = split_percent;
+    bt2->merge_percent = merge_percent;
+    bt2->node_size = node_size;
+    bt2->rrec_size = rrec_size;
+
+    /* Assign common type information */
+    bt2->type = type;
+
+    /* Allocate "page" for node I/O */
+    if(NULL == (bt2->page = H5FL_BLK_MALLOC(node_page, bt2->node_size)))
+        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed")
+#ifdef H5_CLEAR_MEMORY
+HDmemset(bt2->page, 0, bt2->node_size);
+#endif /* H5_CLEAR_MEMORY */
+
+    /* Allocate array of node info structs */
+    if(NULL == (bt2->node_info = H5FL_SEQ_MALLOC(H5B2_node_info_t, (size_t)(bt2->depth + 1))))
+        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed")
+
+    /* Initialize leaf node info */
+    sz_max_nrec = H5B2_NUM_LEAF_REC(bt2->node_size, bt2->rrec_size);
+    H5_ASSIGN_OVERFLOW(/* To: */ bt2->node_info[0].max_nrec, /* From: */ sz_max_nrec, /* From: */ size_t, /* To: */ unsigned)
+    bt2->node_info[0].split_nrec = (bt2->node_info[0].max_nrec * bt2->split_percent) / 100;
+    bt2->node_info[0].merge_nrec = (bt2->node_info[0].max_nrec * bt2->merge_percent) / 100;
+    bt2->node_info[0].cum_max_nrec = bt2->node_info[0].max_nrec;
+    bt2->node_info[0].cum_max_nrec_size = 0;
+    if(NULL == (bt2->node_info[0].nat_rec_fac = H5FL_fac_init(type->nrec_size * bt2->node_info[0].max_nrec)))
+	HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create node native key block factory")
+    bt2->node_info[0].node_ptr_fac = NULL;
+
+    /* Allocate array of pointers to internal node native keys */
+    /* (uses leaf # of records because its the largest) */
+    if(NULL == (bt2->nat_off = H5FL_SEQ_MALLOC(size_t, (size_t)bt2->node_info[0].max_nrec)))
+        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed")
+
+    /* Initialize offsets in native key block */
+    /* (uses leaf # of records because its the largest) */
+    for(u = 0; u < bt2->node_info[0].max_nrec; u++)
+        bt2->nat_off[u] = type->nrec_size * u;
+
+    /* Compute size to store # of records in each node */
+    /* (uses leaf # of records because its the largest) */
+    u_max_nrec_size = H5V_limit_enc_size((uint64_t)bt2->node_info[0].max_nrec);
+    H5_ASSIGN_OVERFLOW(/* To: */ bt2->max_nrec_size, /* From: */ u_max_nrec_size, /* From: */ unsigned, /* To: */ uint8_t)
+    HDassert(bt2->max_nrec_size <= H5B2_SIZEOF_RECORDS_PER_NODE);
+
+    /* Initialize internal node info */
+    if(depth > 0) {
+        for(u = 1; u < (depth + 1); u++) {
+            sz_max_nrec = H5B2_NUM_INT_REC(f, bt2, u);
+            H5_ASSIGN_OVERFLOW(/* To: */ bt2->node_info[u].max_nrec, /* From: */ sz_max_nrec, /* From: */ size_t, /* To: */ unsigned)
+            HDassert(bt2->node_info[u].max_nrec <= bt2->node_info[u - 1].max_nrec);
+
+            bt2->node_info[u].split_nrec = (bt2->node_info[u].max_nrec * bt2->split_percent) / 100;
+            bt2->node_info[u].merge_nrec = (bt2->node_info[u].max_nrec * bt2->merge_percent) / 100;
+
+            bt2->node_info[u].cum_max_nrec = ((bt2->node_info[u].max_nrec + 1) *
+                bt2->node_info[u - 1].cum_max_nrec) + bt2->node_info[u].max_nrec;
+            u_max_nrec_size = H5V_limit_enc_size((uint64_t)bt2->node_info[u].cum_max_nrec);
+            H5_ASSIGN_OVERFLOW(/* To: */ bt2->node_info[u].cum_max_nrec_size, /* From: */ u_max_nrec_size, /* From: */ unsigned, /* To: */ uint8_t)
+
+            if(NULL == (bt2->node_info[u].nat_rec_fac = H5FL_fac_init(bt2->type->nrec_size * bt2->node_info[u].max_nrec)))
+                HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create node native key block factory")
+            if(NULL == (bt2->node_info[u].node_ptr_fac = H5FL_fac_init(sizeof(H5B2_node_ptr_t) * (bt2->node_info[u].max_nrec + 1))))
+                HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create internal 'branch' node node pointer block factory")
+        } /* end for */
+    } /* end if */
+
+done:
+    if(ret_value < 0)
+        if(H5B2_hdr_free(bt2) < 0)
+            HDONE_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to free shared v2 B-tree info")
+
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_hdr_init() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_hdr_free
+ *
+ * Purpose:	Free B-tree header info
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@ncsa.uiuc.edu
+ *		Feb  2 2005
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_hdr_free(H5B2_t *bt2)
+{
+    herr_t ret_value = SUCCEED;
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_hdr_free)
+
+    /* Sanity check */
+    HDassert(bt2);
+
+    /* Free the B-tree node buffer */
+    if(bt2->page)
+        (void)H5FL_BLK_FREE(node_page, bt2->page);
+
+    /* Free the array of offsets into the native key block */
+    if(bt2->nat_off)
+        bt2->nat_off = H5FL_SEQ_FREE(size_t, bt2->nat_off);
+
+    /* Release the node info */
+    if(bt2->node_info) {
+        unsigned u;             /* Local index variable */
+
+        /* Destroy free list factories */
+        for(u = 0; u < (bt2->depth + 1); u++) {
+            if(bt2->node_info[u].nat_rec_fac)
+                if(H5FL_fac_term(bt2->node_info[u].nat_rec_fac) < 0)
+                    HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy node's native record block factory")
+            if(bt2->node_info[u].node_ptr_fac)
+                if(H5FL_fac_term(bt2->node_info[u].node_ptr_fac) < 0)
+                    HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy node's node pointer block factory")
+        } /* end for */
+
+        /* Free the array of node info structs */
+        bt2->node_info = H5FL_SEQ_FREE(H5B2_node_info_t, bt2->node_info);
+    } /* end if */
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_hdr_free() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_hdr_incr
+ *
+ * Purpose:	Increment reference count on B-tree header
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@hdfgroup.org
+ *		Oct 13 2009
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_hdr_incr(H5B2_t *bt2)
+{
+    herr_t ret_value = SUCCEED;         /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_hdr_incr)
+
+    /* Sanity checks */
+    HDassert(bt2);
+    HDassert(bt2->f);
+
+    /* Mark header as un-evictable when a B-tree node is depending on it */
+    if(bt2->rc == 0)
+        if(H5AC_pin_protected_entry(bt2->f, bt2) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTPIN, FAIL, "unable to pin v2 B-tree header")
+
+    /* Increment reference count on B-tree header */
+    bt2->rc++;
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_incr_hdr() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_hdr_decr
+ *
+ * Purpose:	Decrement reference count on B-tree header
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@hdfgroup.org
+ *		Oct 13 2009
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_hdr_decr(H5B2_t *bt2)
+{
+    herr_t ret_value = SUCCEED;         /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_hdr_decr)
+
+    /* Sanity check */
+    HDassert(bt2);
+    HDassert(bt2->f);
+    HDassert(bt2->rc > 0);
+
+    /* Decrement reference count on B-tree header */
+    bt2->rc--;
+
+    /* Mark header as evictable again when no nodes depend on it */
+    if(bt2->rc == 0)
+        if(H5AC_unpin_entry(bt2->f, bt2) < 0)
+            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin v2 B-tree header")
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_hdr_decr() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5B2_hdr_dirty
+ *
+ * Purpose:	Mark B-tree header as dirty
+ *
+ * Return:	Non-negative on success/Negative on failure
+ *
+ * Programmer:	Quincey Koziol
+ *		koziol@hdfgroup.org
+ *		Oct 13 2009
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B2_hdr_dirty(H5B2_t *bt2)
+{
+    herr_t ret_value = SUCCEED;         /* Return value */
+
+    FUNC_ENTER_NOAPI_NOINIT(H5B2_hdr_dirty)
+
+    /* Sanity check */
+    HDassert(bt2);
+    HDassert(bt2->f);
+
+    /* Mark B-tree header as dirty in cache */
+    if(H5AC_mark_pinned_or_protected_entry_dirty(bt2->f, bt2) < 0)
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTMARKDIRTY, FAIL, "unable to mark v2 B-tree header as dirty")
+
+done:
+    FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5B2_hdr_dirty() */
+