[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, 400 insertions, 0 deletions

diff --git a/test/ttst.c b/test/ttst.c
new file mode 100644
index 0000000..eb9ebef
--- /dev/null
+++ b/test/ttst.c
@@ -0,0 +1,400 @@
+/****************************************************************************
+ * NCSA HDF                                                                 *
+ * Software Development Group                                               *
+ * National Center for Supercomputing Applications                          *
+ * University of Illinois at Urbana-Champaign                               *
+ * 605 E. Springfield, Champaign IL 61820                                   *
+ *                                                                          *
+ * For conditions of distribution and use, see the accompanying             *
+ * hdf/COPYING file.                                                        *
+ *                                                                          *
+ ****************************************************************************/
+
+/* $Id$ */
+
+/*
+   FILE
+       tst.c
+   Test HDF Ternary Search Tree (tst) routines.
+
+   REMARKS
+
+   DESIGN
+
+   BUGS/LIMITATIONS
+
+   EXPORTED ROUTINES
+
+   AUTHOR
+       Quincey Koziol
+
+   MODIFICATION HISTORY
+       12/9/02 - Started coding
+ */
+
+#include <time.h>
+
+#include "testhdf5.h"
+#include "H5STprivate.h"
+
+/* Test words to insert into s TST */
+static const char *words[]={
+    "We", "hold", "these", "truths", "to", "be", "self-evident,", "that",
+    "all", "men", "are", "created", "equal,", "that", "they", "are", "endowed",
+    "by", "their", "Creator", "with", "certain", "unalienable", "Rights,",
+    "that", "among", "these", "are", "Life,", "Liberty", "and", "the",
+    "pursuit", "of", "Happiness."
+};
+/* Number of words in test words set */
+size_t num_words;
+
+/* Number of unique words in test word set */
+size_t num_uniq_words;
+/* Unique words in test word set */
+char **uniq_words;
+/* Randomized order version of words in test word set */
+char **rand_uniq_words;
+/* Sorted order version of words in test word set */
+char **sort_uniq_words;
+
+static int tst_strcmp(const void *_s1, const void *_s2)
+{
+    return(HDstrcmp(*(const char **)_s1,*(const char **)_s2));
+}
+
+/****************************************************************
+**
+**  test_tst_init(): Test basic H5ST (ternary search tree) selection code.
+**      Initialize data for TST testing
+** 
+****************************************************************/
+static void 
+test_tst_init(void)
+{
+    time_t curr_time;   /* Current time, for seeding random number generator */
+    char *tmp_word=NULL;/* Temporary pointer to word in word set */
+    size_t u,v,w;       /* Local index variables */
+
+    /* Compute the number of words in the test set */
+    num_words=sizeof(words)/sizeof(words[0]);
+
+    /* Determine the number of unique words in test set */
+    /* (Not particularly efficient, be careful if many words are added to set) */
+    num_uniq_words=0;
+    for(u=0; u<num_words; u++) {
+        /* Assume word is unique */
+        num_uniq_words++;
+        for(v=0; v<u; v++)
+            /* If word is already found in words looked at, decrement unique count */
+            if(!HDstrcmp(words[u],words[v])) {
+                num_uniq_words--;
+                break;
+            } /* end if */
+    } /* end for */
+
+    /* Allocate space for the array of unique words */
+    uniq_words=HDmalloc(sizeof(char *)*num_uniq_words);
+
+    /* Allocate space for the array of randomized order unique words also */
+    rand_uniq_words=HDmalloc(sizeof(char *)*num_uniq_words);
+
+    /* Allocate space for the array of sorted order unique words also */
+    sort_uniq_words=HDmalloc(sizeof(char *)*num_uniq_words);
+
+    /* Insert unique words from test set into unique word set */
+    w=0;
+    for(u=0; u<num_words; u++) {
+        /* Assume word is unique */
+        tmp_word=(char *)words[u];
+        for(v=0; v<u; v++)
+            /* If word is already found in words looked at, decrement unique count */
+            if(!HDstrcmp(words[u],words[v])) {
+                tmp_word=NULL;
+                break;
+            } /* end if */
+
+        /* Check if word was actually unique */
+        if(tmp_word!=NULL)
+            uniq_words[w++]=tmp_word;
+    } /* end for */
+
+    /* Create randomized set of unique words */
+    for(u=0; u<num_uniq_words; u++)
+        rand_uniq_words[u]=uniq_words[u];
+    curr_time=time(NULL);
+    srandom((unsigned long)curr_time);
+    for(u=0; u<num_uniq_words; u++) {
+        v=u+(random()%(num_uniq_words-u));
+        if(u!=v) {
+            tmp_word=rand_uniq_words[u];
+            rand_uniq_words[u]=rand_uniq_words[v];
+            rand_uniq_words[v]=tmp_word;
+        } /* end if */
+    } /* end for */
+
+    /* Create sorted set of unique words */
+    for(u=0; u<num_uniq_words; u++)
+        sort_uniq_words[u]=uniq_words[u];
+    HDqsort(sort_uniq_words,num_uniq_words,sizeof(char *),tst_strcmp);
+} /* end test_tst_init() */
+
+/****************************************************************
+**
+**  test_tst_create(): Test basic H5ST (ternary search tree) selection code.
+**      Tests creating and closing TSTs.
+** 
+****************************************************************/
+static void 
+test_tst_create(void)
+{
+    H5ST_tree_t *tree;   /* TST created */
+    herr_t ret;         /* Generic return value */
+
+    /* Output message about test being performed */
+    MESSAGE(5, ("Testing Creating & Closing TSTs\n"));
+
+    /* Try closing a NULL tree */
+    tree=NULL;
+    ret=H5ST_close(tree);
+    VERIFY(ret, FAIL, "H5ST_close");
+
+    /* Try creating a TST */
+    tree=H5ST_create();
+    CHECK(tree, NULL, "H5ST_create");
+
+    /* Try closing a real tree */
+    ret=H5ST_close(tree);
+    CHECK(ret, FAIL, "H5ST_close");
+
+} /* end test_tst_create() */
+
+/****************************************************************
+**
+**  test_tst_insert(): Test basic H5ST (ternary search tree) selection code.
+**      Tests inserting key/value pairs into TST
+** 
+****************************************************************/
+static void 
+test_tst_insert(void)
+{
+    H5ST_tree_t *tree;  /* TST created */
+    H5ST_ptr_t found;   /* Pointer to TST node found */
+    void *obj;          /* Pointer to object located in TST */
+    size_t u;           /* Local index counter */
+    htri_t check;       /* Is string in TST? */
+    herr_t ret;         /* Generic return value */
+
+    /* Output message about test being performed */
+    MESSAGE(5, ("Testing Inserting Values into TSTs\n"));
+
+    /* Create the TST */
+    tree=H5ST_create();
+    CHECK(tree, NULL, "H5ST_create");
+
+    /* Insert unique words into TST, in random order */
+    for(u=0; u<num_uniq_words; u++) {
+        ret=H5ST_insert(tree,rand_uniq_words[u],rand_uniq_words[u]);
+        CHECK(ret, FAIL, "H5ST_insert");
+    } /* end for */
+
+    /* Verify that all words were inserted into TST properly */
+    for(u=0; u<num_uniq_words; u++) {
+        /* Check that the word is present */
+        check=H5ST_search(tree,uniq_words[u]);
+        VERIFY(check, TRUE, "H5ST_search");
+
+        /* Check that the value "payloads" are correct */
+        found=H5ST_find(tree,uniq_words[u]);
+        CHECK(found, NULL, "H5ST_find");
+
+        if(HDstrcmp((const char *)found->eqkid,uniq_words[u])) {
+            num_errs++;
+            printf("%d: TST node values don't match!, found->eqkid=%s, uniq_words[%u]=%s\n",__LINE__,(char *)found->eqkid,(unsigned)u,uniq_words[u]);
+        } /* end if */
+
+        obj=H5ST_locate(tree,uniq_words[u]);
+        CHECK(obj, NULL, "H5ST_locate");
+
+        if(HDstrcmp((const char *)obj,uniq_words[u])) {
+            num_errs++;
+            printf("%d: TST objects don't match!, obj=%s, uniq_words[%u]=%s\n",__LINE__,(char *)obj,(unsigned)u,uniq_words[u]);
+        } /* end if */
+    } /* end for */
+
+    /* Verify that words not in the TST aren't found */
+    check=H5ST_search(tree,"foo");
+    VERIFY(check, FALSE, "H5ST_search");
+    check=H5ST_search(tree,"bar");
+    VERIFY(check, FALSE, "H5ST_search");
+    check=H5ST_search(tree,"baz");
+    VERIFY(check, FALSE, "H5ST_search");
+
+    /* Close the TST */
+    ret=H5ST_close(tree);
+    CHECK(ret, FAIL, "H5ST_close");
+} /* end test_tst_insert() */
+
+/****************************************************************
+**
+**  test_tst_iterate(): Test basic H5ST (ternary search tree) code.
+**      Tests iterating through key/value pairs in TST
+** 
+****************************************************************/
+static void 
+test_tst_iterate(void)
+{
+    H5ST_tree_t *tree;  /* TST created */
+    H5ST_ptr_t found;   /* Pointer to TST node found */
+    size_t u;           /* Local index counter */
+    herr_t ret;         /* Generic return value */
+
+    /* Output message about test being performed */
+    MESSAGE(5, ("Testing Iterating Over TSTs\n"));
+
+    /* Create the TST */
+    tree=H5ST_create();
+    CHECK(tree, NULL, "H5ST_create");
+
+    /* Insert unique words into TST, in random order */
+    for(u=0; u<num_uniq_words; u++) {
+        ret=H5ST_insert(tree,rand_uniq_words[u],rand_uniq_words[u]);
+        CHECK(ret, FAIL, "H5ST_insert");
+    } /* end for */
+
+    /* Use findfirst/findnext calls to iterate through TST */
+    found=H5ST_findfirst(tree);
+    CHECK(found, NULL, "H5ST_findfirst");
+    u=0;
+    do {
+        /* Check that the strings in the TST are in the correct order */
+        if(HDstrcmp((const char *)found->eqkid,sort_uniq_words[u])) {
+            num_errs++;
+            printf("%d: TST node values don't match!, found->eqkid=%s, sort_uniq_words[%u]=%s\n",__LINE__,(char *)found->eqkid,(unsigned)u,sort_uniq_words[u]);
+        } /* end if */
+
+        /* Advance to next string in TST */
+        found=H5ST_findnext(found);
+        u++;
+    } while(found!=NULL);
+
+    /* Close the TST */
+    ret=H5ST_close(tree);
+    CHECK(ret, FAIL, "H5ST_close");
+} /* end test_tst_iterate() */
+
+/****************************************************************
+**
+**  test_tst_remove(): Test basic H5ST (ternary search tree) code.
+**      Tests removing key/value pairs by string value in TST
+** 
+****************************************************************/
+static void 
+test_tst_remove(void)
+{
+    H5ST_tree_t *tree;  /* TST created */
+    H5ST_ptr_t found;   /* Pointer to TST node found */
+    void *obj;          /* Pointer to object removed from TST */
+    htri_t check;       /* Is string in TST? */
+    size_t u;           /* Local index counter */
+    herr_t ret;         /* Generic return value */
+
+    /* Output message about test being performed */
+    MESSAGE(5, ("Testing Removing String Values from TSTs\n"));
+
+    /* Create the TST */
+    tree=H5ST_create();
+    CHECK(tree, NULL, "H5ST_create");
+
+    /* Insert unique words into TST, in random order */
+    for(u=0; u<num_uniq_words; u++) {
+        ret=H5ST_insert(tree,rand_uniq_words[u],rand_uniq_words[u]);
+        CHECK(ret, FAIL, "H5ST_insert");
+    } /* end for */
+
+    /* Remove strings from TST in random order */
+    for(u=0; u<num_uniq_words; u++) {
+        obj=H5ST_remove(tree,rand_uniq_words[u]);
+        CHECK(obj, NULL, "H5ST_remove");
+
+        /* Check that the correct string was removed from TST */
+        if(HDstrcmp((const char *)obj,rand_uniq_words[u])) {
+            num_errs++;
+            printf("%d: TST node values don't match!, obj=%s, rand_uniq_words[%u]=%s\n",__LINE__,(char *)obj,(unsigned)u,rand_uniq_words[u]);
+        } /* end if */
+
+        /* Check that the string can't be found in the TST any longer */
+        check=H5ST_search(tree,rand_uniq_words[u]);
+        VERIFY(check, FALSE, "H5ST_search");
+    } /* end for */
+
+    /* Re-insert unique words into TST, in random order */
+    for(u=0; u<num_uniq_words; u++) {
+        ret=H5ST_insert(tree,rand_uniq_words[u],rand_uniq_words[u]);
+        CHECK(ret, FAIL, "H5ST_insert");
+    } /* end for */
+
+    /* Remove TST nodes from TST in random order */
+    for(u=0; u<num_uniq_words; u++) {
+        /* Get the pointer to the node to delete */
+        found=H5ST_find(tree,rand_uniq_words[u]);
+        CHECK(found, NULL, "H5ST_find");
+
+        /* Check that the correct object will be removed from TST */
+        if(HDstrcmp((const char *)found->eqkid,rand_uniq_words[u])) {
+            num_errs++;
+            printf("%d: TST node values don't match!, found->eqkid=%s, rand_uniq_words[%u]=%s\n",__LINE__,(char *)found->eqkid,(unsigned)u,rand_uniq_words[u]);
+        } /* end if */
+
+        /* Remove the node */
+        ret=H5ST_delete(tree,found);
+        CHECK(ret, FAIL, "H5ST_delete");
+
+        /* Check that the string can't be found in the TST any longer */
+        check=H5ST_search(tree,rand_uniq_words[u]);
+        VERIFY(check, FALSE, "H5ST_search");
+    } /* end for */
+
+    /* Close the TST */
+    ret=H5ST_close(tree);
+    CHECK(ret, FAIL, "H5ST_close");
+} /* end test_tst_remove() */
+
+/****************************************************************
+**
+**  test_tst_finalize(): Test basic H5ST (ternary search tree) selection code.
+**      Wrap up data for TST testing
+** 
+****************************************************************/
+static void 
+test_tst_finalize(void)
+{
+    /* Release memory for unordered, randomized and sorted order unique words */
+    HDfree(uniq_words);
+    HDfree(rand_uniq_words);
+    HDfree(sort_uniq_words);
+} /* end test_tst_finalize() */
+
+/****************************************************************
+**
+**  test_tst(): Main H5ST selection testing routine.
+** 
+****************************************************************/
+void
+test_tst(void)
+{
+    /* Output message about test being performed */
+    MESSAGE(5, ("Testing Ternary Search Trees\n"));
+
+    /* Initialize TST testing data */
+    test_tst_init();
+
+    /* Actual TST tests */
+    test_tst_create();          /* Test TST creation */
+    test_tst_insert();          /* Test TST insertion */
+    test_tst_iterate();         /* Test TST iteration */
+    test_tst_remove();          /* Test TST deletion */
+
+    /* Finalize TST testing data */
+    test_tst_finalize();
+}   /* end test_tst() */
+