[svn-r6252] Purpose:

    Lots of performance improvements & a couple new internal API interfaces.

Description:
    Performance Improvements:
        - Cached file offset & length sizes in shared file struct, to avoid
            constantly looking them up in the FCPL.
        - Generic property improvements:
            - Added "revision" number to generic property classes to speed
                up comparisons.
            - Changed method of storing properties from using a hash-table
                to the TBBT routines in the library.
            - Share the propery names between classes and the lists derived
                from them.
            - Removed redundant 'def_value' buffer from each property.
            - Switching code to use a "copy on write" strategy for
                properties in each list, where the properties in each list
                are shared with the properties in the class, until a
                property's value is changed in a list.
        - Fixed error in layout code which was allocating too many buffers.
        - Redefined public macros of the form (H5open()/H5check, <variable>)
            internally to only be (<variable>), avoiding innumerable useless
            calls to H5open() and H5check_version().
        - Reuse already zeroed buffers in H5F_contig_fill instead of
            constantly re-zeroing them.
        - Don't write fill values if writing entire dataset.
        - Use gettimeofday() system call instead of time() system when
            checking the modification time of a dataset.
        - Added reference counted string API and use it for tracking the
            names of objects opening in a file (for the ID->name code).
        - Removed redundant H5P_get() calls in B-tree routines.
        - Redefine H5T datatype macros internally to the library, to avoid
            calling H5check redundantly.
        - Keep dataspace information for dataset locally instead of reading
            from disk each time.  Added new module to track open objects
            in a file, to allow this (which will be useful eventually for
            some FPH5 metadata caching issues).
        - Remove H5AC_find macro which was inlining metadata cache lookups,
            and call function instead.
        - Remove redundant memset() calls from H5G_namei() routine.
        - Remove redundant checking of object type when locating objects
            in metadata cache and rely on the address only.
        - Create default dataset object to use when default dataset creation
            property list is used to create datasets, bypassing querying
            for all the property list values.
        - Use default I/O vector size when performing raw data with the
            default dataset transfer property list, instead of querying for
            I/O vector size.
        - Remove H5P_DEFAULT internally to the library, replacing it with
            more specific default property list based on the type of
            property list needed.
        - Remove redundant memset() calls in object header message (H5O*)
            routines.
        - Remove redunant memset() calls in data I/O routines.
        - Split free-list allocation routines into malloc() and calloc()-
            like routines, instead of one combined routine.
        - Remove lots of indirection in H5O*() routines.
        - Simplify metadata cache entry comparison routine (used when
            flushing entire cache out).
        - Only enable metadata cache statistics when H5AC_DEBUG is turned
            on, instead of always tracking them.
        - Simplify address comparison macro (H5F_addr_eq).
        - Remove redundant metadata cache entry protections during dataset
            creation by protecting the object header once and making all
            the modifications necessary for the dataset creation before
            unprotecting it.
        - Reduce # of "number of element in extent" computations performed
            by computing and storing the value during dataspace creation.
        - Simplify checking for group location's file information, when file
            has not been involving in file-mounting operations.
        - Use binary encoding for modification time, instead of ASCII.
        - Hoist H5HL_peek calls (to get information in a local heap)
            out of loops in many group routine.
        - Use static variable for iterators of selections, instead of
            dynamically allocation them each time.
        - Lookup & insert new entries in one step, avoiding traversing
            group's B-tree twice.
        - Fixed memory leak in H5Gget_objname_idx() routine (tangential to
            performance improvements, but fixed along the way).
        - Use free-list for reference counted strings.
        - Don't bother copying object names into cached group entries,
            since they are re-created when an object is opened.

        The benchmark I used to measure these results created several thousand
        small (2K) datasets in a file and wrote out the data for them.  This is
        Elena's "regular.c" benchmark.

        These changes resulted in approximately ~4.3x speedup of the
        development branch when compared to the previous code in the
        development branch and ~1.4x speedup compared to the release
        branch.

        Additionally, these changes reduce the total memory used (code and
        data) by the development branch by ~800KB, bringing the development
        branch back into the same ballpark as the release branch.

        I'll send out a more detailed description of the benchmark results
        as a followup note.

    New internal API routines:
        Added "reference counted strings" API for tracking strings that get
            used by multiple owners without duplicating the strings.
        Added "ternary search tree" API for text->object mappings.

Platforms tested:
    Tested h5committest {arabica (fortran), eirene (fortran, C++)
	modi4 (parallel, fortran)}
    Other platforms/configurations tested?
        FreeBSD 4.7 (sleipnir) serial & parallel
        Solaris 2.6 (baldric) serial

1 files changed, 176 insertions, 16 deletions

diff --git a/src/H5TB.c b/src/H5TB.c
index 391101f..5f04732 100644
--- a/src/H5TB.c
+++ b/src/H5TB.c
@@ -90,7 +90,7 @@
 
 /* Local Function Prototypes */
 static H5TB_NODE * H5TB_end(H5TB_NODE * root, int side);
-static H5TB_NODE *H5TB_ffind(H5TB_NODE * root, void * key, unsigned fast_compare,
+static H5TB_NODE *H5TB_ffind(H5TB_NODE * root, const void * key, unsigned fast_compare,
     H5TB_NODE ** pp);
 static herr_t H5TB_balance(H5TB_NODE ** root, H5TB_NODE * ptr, int side, int added);
 static H5TB_NODE *H5TB_swapkid(H5TB_NODE ** root, H5TB_NODE * ptr, int side);
@@ -105,12 +105,148 @@ static herr_t H5TB_dumpNode(H5TB_NODE *node, void (*key_dump)(void *,void *),
 /* Declare a free list to manage the H5TB_NODE struct */
 H5FL_DEFINE_STATIC(H5TB_NODE);
 
+/* Declare a free list to manage the H5TB_TREE struct */
+H5FL_DEFINE_STATIC(H5TB_TREE);
+
 #define PABLO_MASK	H5TB_mask
 static int		interface_initialize_g = 0;
 #define INTERFACE_INIT	NULL
 
 
 /*-------------------------------------------------------------------------
+ * Function:	H5TB_strcmp
+ *
+ * Purpose:	Key comparison routine for TBBT routines
+ *
+ * Return:	same as strcmp()
+ *
+ * Programmer:	Quincey Koziol
+ *              Wednesday, December 4, 2002
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+H5TB_strcmp(const void *k1, const void *k2, int UNUSED cmparg)
+{
+    FUNC_ENTER_NOINIT(H5TB_strcmp);
+
+    assert(k1);
+    assert(k2);
+
+    FUNC_LEAVE(HDstrcmp(k1,k2));
+} /* end H5TB_strcmp() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5TB_addr_cmp
+ *
+ * Purpose:	Key comparison routine for TBBT routines
+ *
+ * Return:	same as H5F_addr_cmp()
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, December 20, 2002
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+H5TB_addr_cmp(const void *k1, const void *k2, int UNUSED cmparg)
+{
+    FUNC_ENTER_NOINIT(H5TB_addr_cmp);
+
+    assert(k1);
+    assert(k2);
+
+    FUNC_LEAVE(H5F_addr_cmp(*(const haddr_t *)k1,*(const haddr_t *)k2));
+} /* end H5TB_addr_cmp() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5TB_int_cmp
+ *
+ * Purpose:	Key comparison routine for TBBT routines
+ *
+ * Return:	same as comparing two integers
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, December 20, 2002
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+H5TB_int_cmp(const void *k1, const void *k2, int UNUSED cmparg)
+{
+    FUNC_ENTER_NOINIT(H5TB_int_cmp);
+
+    assert(k1);
+    assert(k2);
+
+    FUNC_LEAVE(*(const int *)k1 - *(const int *)k2);
+} /* end H5TB_int_cmp() */
+
+
+/*-------------------------------------------------------------------------
+ * Function:	H5TB_fast_dmake
+ *
+ * Purpose:	Wrapper around H5TB_dmake for callers which want to use
+ *              a "fast comparison" key.
+ *
+ * Return:	Success:	Pointer to a valid H5TB tree
+ * 		Failure:	NULL
+ *
+ * Programmer:	Quincey Koziol
+ *              Friday, December 20, 2002
+ *
+ * Modifications:
+ * 	
+ *-------------------------------------------------------------------------
+ */
+H5TB_TREE  *
+H5TB_fast_dmake(unsigned fast_compare)
+{
+    H5TB_cmp_t  compar;         /* Key comparison function */
+    int cmparg;                 /* Key comparison value */
+    H5TB_TREE  *ret_value;      /* Return value */
+
+    FUNC_ENTER_NOAPI(H5TB_fast_dmake, NULL);
+
+    /* Get the corret fast comparison routine */
+    switch(fast_compare) {
+        case H5TB_FAST_HADDR_COMPARE:
+            compar=H5TB_addr_cmp;
+            cmparg=-1;
+            break;
+
+        case H5TB_FAST_INTN_COMPARE:
+            compar=H5TB_int_cmp;
+            cmparg=-1;
+            break;
+
+        case H5TB_FAST_STR_COMPARE:
+            compar=H5TB_strcmp;
+            cmparg=-1;
+            break;
+
+        default:
+            HGOTO_ERROR (H5E_TBBT, H5E_BADVALUE, NULL, "invalid fast comparison type");
+    } /* end switch */
+
+    /* Set return value */
+    if((ret_value=H5TB_dmake(compar,cmparg,fast_compare))==NULL)
+        HGOTO_ERROR (H5E_TBBT, H5E_CANTCREATE, NULL, "can't create TBBT");
+
+done:
+    FUNC_LEAVE (ret_value);
+}   /* end H5TB_fast_dmake() */
+
+
+/*-------------------------------------------------------------------------
  * Function:	H5TB_dmake
  *
  * Purpose:	Allocates and initializes an empty threaded, balanced, binary tree
@@ -192,7 +328,7 @@ H5TB_dmake(H5TB_cmp_t cmp, int arg, unsigned fast_compare)
 
     FUNC_ENTER_NOAPI(H5TB_dmake, NULL);
 
-    if (NULL == (tree = H5MM_malloc(sizeof(H5TB_TREE))))
+    if (NULL == (tree = H5FL_MALLOC(H5TB_TREE)))
         HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
 
     tree->root = NULL;
@@ -234,7 +370,7 @@ done:
  *-------------------------------------------------------------------------
  */
 H5TB_NODE  *
-H5TB_dfind(H5TB_TREE * tree, void * key, H5TB_NODE ** pp)
+H5TB_dfind(H5TB_TREE * tree, const void * key, H5TB_NODE ** pp)
 {
     H5TB_NODE *ret_value;
 
@@ -242,10 +378,16 @@ H5TB_dfind(H5TB_TREE * tree, void * key, H5TB_NODE ** pp)
 
     assert(tree);
 
-    if(tree->fast_compare!=0)
-        ret_value=H5TB_ffind(tree->root, key, tree->fast_compare, pp);
-    else
-        ret_value=H5TB_find(tree->root, key, tree->compar, tree->cmparg, pp);
+    if(tree->root)
+        if(tree->fast_compare!=0)
+            ret_value=H5TB_ffind(tree->root, key, tree->fast_compare, pp);
+        else
+            ret_value=H5TB_find(tree->root, key, tree->compar, tree->cmparg, pp);
+    else {
+        if (NULL != pp)
+            *pp = NULL;
+        ret_value=NULL;
+    } /* end else */
 
 done:
     FUNC_LEAVE (ret_value);
@@ -280,7 +422,7 @@ done:
  *-------------------------------------------------------------------------
  */
 H5TB_NODE  *
-H5TB_find(H5TB_NODE * root, void * key,
+H5TB_find(H5TB_NODE * root, const void * key,
      H5TB_cmp_t compar, int arg, H5TB_NODE ** pp)
 {
     H5TB_NODE  *ptr = root;
@@ -461,7 +603,7 @@ H5TB_index(H5TB_NODE * root, unsigned indx)
     if (NULL != ptr) {
       /* Termination condition is if the index equals the number of children on
          out left plus the current node */
-        while (ptr != NULL && indx != ((unsigned) LeftCnt(ptr)) + 1 ) {
+        while (ptr != NULL && indx != ((unsigned) LeftCnt(ptr)) ) {
             if (indx <= (unsigned) LeftCnt(ptr)) {
                 ptr = ptr->Lchild;
               } /* end if */
@@ -564,7 +706,7 @@ H5TB_ins(H5TB_NODE ** root, void * item, void * key, H5TB_cmp_t compar, int arg)
 
     if (NULL != H5TB_find(*root, (key ? key : item), compar, arg, &parent))
         HGOTO_ERROR (H5E_TBBT, H5E_EXISTS, NULL, "node already in tree");
-    if (NULL == (ptr = H5FL_ALLOC(H5TB_NODE,0)))
+    if (NULL == (ptr = H5FL_MALLOC(H5TB_NODE)))
         HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
     ptr->data = item;
     ptr->key = key ? key : item;
@@ -760,12 +902,13 @@ H5TB_rem(H5TB_NODE ** root, H5TB_NODE * node, void * *kp)
     H5FL_FREE(H5TB_NODE,leaf);
     H5TB_balance(root, par, side, -1);
 
-    ((H5TB_TREE *) root)->count--;
-
     /* Set return value */
     ret_value=data;
 
 done:
+    if(ret_value)
+        ((H5TB_TREE *) root)->count--;
+
     FUNC_LEAVE(ret_value);
 }   /* end H5TB_rem() */
 
@@ -945,7 +1088,7 @@ H5TB_dfree(H5TB_TREE * tree, void(*fd) (void * /* item */), void(*fk) (void * /*
         H5TB_free(&tree->root, fd, fk);
 
         /* Free the tree root */
-        H5MM_xfree(tree);
+        H5FL_FREE(H5TB_TREE,tree);
     } /* end if */
 
 done:
@@ -1254,7 +1397,7 @@ done:
 /* This routine is based on tbbtfind (fix bugs in both places!) */
 /* Returns a pointer to the found node (or NULL) */
 static H5TB_NODE  *
-H5TB_ffind(H5TB_NODE * root, void * key, unsigned fast_compare, H5TB_NODE ** pp)
+H5TB_ffind(H5TB_NODE * root, const void * key, unsigned fast_compare, H5TB_NODE ** pp)
 {
     H5TB_NODE  *ptr = root;
     H5TB_NODE  *parent = NULL;
@@ -1267,7 +1410,7 @@ H5TB_ffind(H5TB_NODE * root, void * key, unsigned fast_compare, H5TB_NODE ** pp)
     switch(fast_compare) {
         case H5TB_FAST_HADDR_COMPARE:
             if (ptr) {
-                while (0 != (cmp = H5F_addr_cmp(*(haddr_t *)key,*(haddr_t *)ptr->key))) {
+                while (0 != (cmp = H5F_addr_cmp(*(const haddr_t *)key,*(haddr_t *)ptr->key))) {
                       parent = ptr;
                       side = (cmp < 0) ? LEFT : RIGHT;
                       if (!HasChild(ptr, side))
@@ -1284,7 +1427,24 @@ H5TB_ffind(H5TB_NODE * root, void * key, unsigned fast_compare, H5TB_NODE ** pp)
 
         case H5TB_FAST_INTN_COMPARE:
             if (ptr) {
-                while (0 != (cmp = (*(int *)key - *(int *)ptr->key))) {
+                while (0 != (cmp = (*(const int *)key - *(int *)ptr->key))) {
+                      parent = ptr;
+                      side = (cmp < 0) ? LEFT : RIGHT;
+                      if (!HasChild(ptr, side))
+                          break;
+                      ptr = ptr->link[side];
+                  } /* end while */
+              } /* end if */
+            if (NULL != pp)
+                *pp = parent;
+
+            /* Set return value */
+            ret_value= (0 == cmp) ? ptr : NULL;
+            break;
+
+        case H5TB_FAST_STR_COMPARE:
+            if (ptr) {
+                while (0 != (cmp = HDstrcmp(key,ptr->key))) {
                       parent = ptr;
                       side = (cmp < 0) ? LEFT : RIGHT;
                       if (!HasChild(ptr, side))