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

diff --git a/src/H5ST.c b/src/H5ST.c
new file mode 100644
index 0000000..35b6ab8
--- /dev/null
+++ b/src/H5ST.c
@@ -0,0 +1,795 @@
+/****************************************************************************
+ * 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.							    *
+ *									    *
+ ****************************************************************************/
+
+/* TERNARY SEARCH TREE ALGS
+  This code is described in "Ternary Search Trees" by Jon
+Bentley and Robert Sedgewick in the April, 1998, Dr. Dobb's Journal.
+*/
+
+#include "H5Eprivate.h"		/* Error handling		  	*/
+#include "H5FLprivate.h"	/* Free lists                           */
+#include "H5STprivate.h"        /* Ternary search trees                 */
+
+#define PABLO_MASK	H5ST_mask
+static int		interface_initialize_g = 0;
+#define INTERFACE_INIT	NULL
+
+/* Declare a free list to manage the H5ST_node_t struct */
+H5FL_DEFINE_STATIC(H5ST_node_t);
+
+/* Declare a free list to manage the H5ST_tree_t struct */
+H5FL_DEFINE_STATIC(H5ST_tree_t);
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_create
+ PURPOSE
+    Create a TST
+ USAGE
+    H5ST_ptr_t H5ST_create()
+
+ RETURNS
+    Returns a pointer to the new TST tree on success, NULL on failure.
+ DESCRIPTION
+    Create a TST.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5ST_tree_t *
+H5ST_create(void)
+{
+    H5ST_tree_t *ret_value=NULL;   /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_create,NULL);
+
+    /* Allocate wrapper for TST */
+    if((ret_value=H5FL_MALLOC(H5ST_tree_t))==NULL)
+        HGOTO_ERROR(H5E_RESOURCE,H5E_NOSPACE,NULL,"memory allocation failed");
+
+    /* Set the internal fields */
+    ret_value->root=NULL;
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_create() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_close_internal
+ PURPOSE
+    Close a TST, deallocating it.
+ USAGE
+    herr_t H5ST_close(p)
+        H5ST_ptr_t p;        IN/OUT: Root of TST to free
+
+ RETURNS
+    Returns non-negative on success, negative on failure.
+ DESCRIPTION
+    Close a TST, freeing all nodes.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static herr_t
+H5ST_close_internal(H5ST_ptr_t p)
+{
+    FUNC_ENTER_NOINIT(H5ST_close_internal);
+
+    /* Recursively free TST */
+    if(p) {
+        H5ST_close_internal(p->lokid);
+        if (p->splitchar)
+            H5ST_close_internal(p->eqkid);
+        H5ST_close_internal(p->hikid);
+        H5FL_FREE(H5ST_node_t,p);
+    } /* end if */
+
+    FUNC_LEAVE(SUCCEED);
+} /* end H5ST_close_internal() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_close
+ PURPOSE
+    Close a TST, deallocating it.
+ USAGE
+    herr_t H5ST_close(tree)
+        H5ST_tree_t *tree;        IN/OUT: TST tree to free
+
+ RETURNS
+    Returns non-negative on success, negative on failure.
+ DESCRIPTION
+    Close a TST, freeing all nodes.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5ST_close(H5ST_tree_t *tree)
+{
+    herr_t ret_value=SUCCEED;   /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_close,FAIL);
+
+    /* Check arguments */
+    if(tree==NULL)
+        HGOTO_ERROR(H5E_ARGS,H5E_BADVALUE,FAIL,"invalid TST");
+
+    /* Free the TST itself */
+    if(H5ST_close_internal(tree->root)<0)
+        HGOTO_ERROR(H5E_TST,H5E_CANTFREE,FAIL,"can't free TST");
+
+    /* Free root node itself */
+    H5FL_FREE(H5ST_tree_t,tree);
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_close() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_insert
+ PURPOSE
+    Insert a string/object pair into a TST
+ USAGE
+    herr_t H5ST_insert(tree,s,obj)
+        H5ST_tree_t *tree;      IN/OUT: TST to insert string into
+        const char *s;          IN: String to use as key for object
+        void *obj;              IN: Pointer to object to insert
+
+ RETURNS
+    Returns non-negative on success, negative on failure.
+ DESCRIPTION
+    Insert a key (string)/object pair into a TST
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5ST_insert(H5ST_tree_t *tree, const char *s, void *obj)
+{
+    int d;                      /* Comparison value */
+    H5ST_ptr_t pp, *p;          /* Pointer to current node and pointer to that */
+    H5ST_ptr_t parent=NULL;     /* Pointer to parent node */
+    H5ST_ptr_t up=NULL;         /* Pointer to up node */
+    herr_t ret_value=SUCCEED;   /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_insert,FAIL);
+
+    /* Find the correct location to insert object */
+    p = &tree->root;
+    while((pp = *p)) {
+        /* If this node matches the character in the key, then drop down to the lower tree */
+        if ((d = *s - pp->splitchar) == 0) {
+            if (*s++ == 0)
+                HGOTO_ERROR(H5E_TST,H5E_EXISTS,FAIL,"key already in tree");
+            up=pp;
+            p = &(pp->eqkid);
+        } /* end if */
+        else {
+            /* Walk through the current tree, searching for the matching character */
+            parent=pp;
+            if (d < 0)
+                p = &(pp->lokid);
+            else
+                p = &(pp->hikid);
+        } /* end else */
+    } /* end while */
+
+    /* Finish walking through the key string, adding nodes until the end */
+    for (;;) {
+        if((*p = H5FL_MALLOC(H5ST_node_t))==NULL)
+            HGOTO_ERROR(H5E_RESOURCE,H5E_NOSPACE,FAIL,"memory allocation failed");
+        pp = *p;
+        pp->splitchar = *s;
+        pp->up = up;
+        pp->parent = parent;
+        pp->lokid = pp->eqkid = pp->hikid = NULL;
+
+        /* If this is the end of the key string, break out */
+        if (*s++ == 0) {
+            pp->eqkid = (H5ST_ptr_t) obj;
+            break;
+        } /* end if */
+
+        /* Continue to next character */
+        parent=NULL;
+        up=pp;
+        p = &(pp->eqkid);
+    } /* end for */
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_insert() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_search
+ PURPOSE
+    Determine if a key is in the TST
+ USAGE
+    hbool_t H5ST_search(tree,s)
+        H5ST_tree_t *tree;      IN: TST to find string in
+        const char *s;          IN: String to use as key to locate
+
+ RETURNS
+    Success: TRUE if key string in TST, FALSE if not
+    Failure: negative
+ DESCRIPTION
+    Locate a key (string) in a TST
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+htri_t
+H5ST_search(H5ST_tree_t *tree, const char *s)
+{
+    H5ST_ptr_t p;               /* Temporary pointer to TST node */
+    htri_t ret_value=FALSE;     /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_search,FAIL);
+
+    p = tree->root;
+    while (p) {
+        if (*s < p->splitchar)
+            p = p->lokid;
+        else if (*s == p->splitchar)  {
+            if (*s++ == 0)
+                HGOTO_DONE(TRUE);
+            p = p->eqkid;
+        } else
+            p = p->hikid;
+    } /* end while */
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_search() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_find_internal
+ PURPOSE
+    Find the node matching a particular key string
+ USAGE
+    H5ST_ptr_t H5ST_find(p,s)
+        H5ST_ptr_t p;           IN: TST to find string in
+        const char *s;          IN: String to use as key to locate
+
+ RETURNS
+    Success: Non-NULL
+    Failure: NULL
+ DESCRIPTION
+    Locate a key (string) in a TST
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static H5ST_ptr_t
+H5ST_find_internal(H5ST_ptr_t p, const char *s)
+{
+    H5ST_ptr_t ret_value=NULL;  /* Return value */
+
+    FUNC_ENTER_NOINIT(H5ST_find_internal);
+
+    while (p) {
+        if (*s < p->splitchar)
+            p = p->lokid;
+        else if (*s == p->splitchar)  {
+            if (*s++ == 0)
+                HGOTO_DONE(p);
+            p = p->eqkid;
+        } else
+            p = p->hikid;
+    } /* end while */
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_find_internal() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_find
+ PURPOSE
+    Find the node matching a particular key string
+ USAGE
+    H5ST_ptr_t H5ST_find(tree,s)
+        H5ST_tree_t *tree;      IN: TST to find string in
+        const char *s;          IN: String to use as key to locate
+
+ RETURNS
+    Success: Non-NULL
+    Failure: NULL
+ DESCRIPTION
+    Locate a key (string) in a TST
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5ST_ptr_t
+H5ST_find(H5ST_tree_t *tree, const char *s)
+{
+    H5ST_ptr_t ret_value=NULL;  /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_find,NULL);
+
+    if((ret_value=H5ST_find_internal(tree->root,s))==NULL)
+        HGOTO_ERROR(H5E_TST,H5E_NOTFOUND,NULL,"key not found in TST");
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_find() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_locate
+ PURPOSE
+    Find an object in a TST
+ USAGE
+    void *H5ST_locate(tree,s)
+        H5ST_tree_t *tree;  IN: TST to locate object within
+        const char *s;      IN: String of key for object to locate
+ RETURNS
+    Success: Non-NULL, pointer to object stored for key
+    Failure: Negative
+ DESCRIPTION
+    Locate a node in a TST, returning the object from the node.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+void *
+H5ST_locate(H5ST_tree_t *tree, const char *s)
+{
+    H5ST_ptr_t node;    /* Pointer to node located */
+    void *ret_value;    /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_locate,NULL);
+
+    /* Locate the node to remove */
+    if((node=H5ST_find_internal(tree->root,s))==NULL)
+        HGOTO_ERROR(H5E_TST,H5E_NOTFOUND,NULL,"key not found in TST");
+
+    /* Get the pointer to the object to return */
+    ret_value=node->eqkid;
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* H5ST_locate() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_findfirst_internal
+ PURPOSE
+    Find the first node in a TST
+ USAGE
+    H5ST_ptr_t H5ST_findfirst_internal(p)
+        H5ST_ptr_t p;      IN: TST to locate first node within
+ RETURNS
+    Success: Non-NULL
+    Failure: NULL
+ DESCRIPTION
+    Get the first (lexicographically) node in a TST
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static H5ST_ptr_t
+H5ST_findfirst_internal(H5ST_ptr_t p)
+{   
+    H5ST_ptr_t ret_value=NULL;  /* Return value */
+
+    FUNC_ENTER_NOINIT(H5ST_findfirst_internal);
+
+    while(p) {
+        /* Find least node in current tree */
+        while(p->lokid)
+            p=p->lokid;
+
+        /* Is least node '\0'? */
+        if(p->splitchar=='\0') {
+            /* Return it */
+            HGOTO_DONE(p);
+        } /* end if */
+        else {
+            /* Go down to next level of tree */
+            p=p->eqkid;
+        } /* end else */
+    } /* end while */
+            
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_findfirst_internal() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_findfirst
+ PURPOSE
+    Find the first node in a TST
+ USAGE
+    H5ST_ptr_t H5ST_findfirst(tree)
+        H5ST_tree_t *tree;      IN: TST to locate first node within
+ RETURNS
+    Success: Non-NULL
+    Failure: NULL
+ DESCRIPTION
+    Get the first (lexicographically) node in a TST
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5ST_ptr_t
+H5ST_findfirst(H5ST_tree_t *tree)
+{   
+    H5ST_ptr_t ret_value;       /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_findfirst,NULL);
+
+    if((ret_value=H5ST_findfirst_internal(tree->root))==NULL)
+        HGOTO_ERROR(H5E_TST,H5E_NOTFOUND,NULL,"no nodes in TST");
+            
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_findfirst() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_getnext
+ PURPOSE
+    Internal routine to find the next node in a given level of a TST
+ USAGE
+    H5ST_ptr_t H5ST_getnext(p)
+        H5ST_ptr_t *p;       IN: Pointer to node to find next node from
+ RETURNS
+    Success: Non-NULL
+    Failure: NULL
+ DESCRIPTION
+    Get the next (lexicographically) node in the current level of a TST
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static H5ST_ptr_t
+H5ST_getnext(H5ST_ptr_t p)
+{
+    H5ST_ptr_t ret_value=NULL;  /* Return value */
+
+    FUNC_ENTER_NOINIT(H5ST_getnext);
+
+    /* If the node to continue from has higher-valued nodes attached */
+    if(p->hikid) {
+        /* Go to first higher-valued node */
+        p=p->hikid;
+
+        /* Find least node from here */
+        while(p->lokid)
+            p=p->lokid;
+        HGOTO_DONE(p);
+    } /* end if */
+    else {
+        H5ST_ptr_t q;           /* Temporary TST node pointer */
+
+        /* Go up one level in current tree */
+        q=p->parent;
+        if(q==NULL)
+            HGOTO_DONE(NULL);
+
+        /* While the previous node was the higher-valued node, keep backing up the tree */
+        while(q->hikid==p) {
+            p=q;
+            q=p->parent;
+            if(q==NULL)
+                HGOTO_DONE(NULL);
+        } /* end while */
+        HGOTO_DONE(q);
+    } /* end else */
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_getnext() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_findnext
+ PURPOSE
+    Find the next node from a node in a TST
+ USAGE
+    H5ST_ptr_t H5ST_findnext(p)
+        H5ST_ptr_t p;       IN: Current node to continue from
+ RETURNS
+    Success: Non-NULL
+    Failure: NULL
+ DESCRIPTION
+    Get the next (lexicographically) node in a TST
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5ST_ptr_t
+H5ST_findnext(H5ST_ptr_t p)
+{   
+    H5ST_ptr_t q;               /* Temporary pointer to TST node */
+    H5ST_ptr_t ret_value=NULL;  /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_findnext,NULL);
+
+    /* Find the next node at the current level, or go back up the tree */
+    do {
+        q=H5ST_getnext(p);
+        if(q) {
+            HGOTO_DONE(H5ST_findfirst_internal(q->eqkid));
+        } /* end if */
+        else
+            p=p->up;
+    } while(p);
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_findnext() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_delete_internal
+ PURPOSE
+    Delete a node from a TST
+ USAGE
+    herr_t H5ST_delete_internal(root,p)
+        H5ST_ptr_t *root;       IN/OUT: Root of TST to delete node from
+        H5ST_ptr_t p;       IN: Node to delete
+ RETURNS
+    Success: Non-negative
+    Failure: Negative
+ DESCRIPTION
+    Delete a node from a TST.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+    This should be the final node for a string.
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static herr_t
+H5ST_delete_internal(H5ST_ptr_t *root, H5ST_ptr_t p)
+{   
+    H5ST_ptr_t q,               /* Temporary pointer to TST node */
+        newp;                   /* Pointer to node which will replace deleted node in tree */
+
+    FUNC_ENTER_NOINIT(H5ST_delete_internal);
+
+    /* Find node to replace one being deleted */
+    if(p->lokid) {
+        /* If the deleted node has lo & hi kids, attach them together */
+        if(p->hikid) {
+            q=p->lokid;
+            while(q->hikid)
+                q=q->hikid;
+            q->hikid=p->hikid;
+            p->hikid->parent=q;
+        } /* end if */
+        newp=p->lokid;
+    } /* end if */
+    else if(p->hikid) {
+        newp=p->hikid;
+    } /* end if */
+    else {
+        newp=NULL;
+    } /* end else */
+
+    /* Deleted node is in middle of tree */
+    if(p->parent) {
+        /* Attach new node to correct side of parent */
+        if(p==p->parent->lokid)
+            p->parent->lokid=newp;
+        else
+            p->parent->hikid=newp;
+        if(newp)
+            newp->parent=p->parent;
+    } /* end if */
+    else {
+        if(newp)
+            newp->parent=p->parent;
+        if(p->up) {
+            p->up->eqkid=newp;
+            /* If we deleted the last node in the TST, delete the upper node also */
+            if(newp==NULL)
+                H5ST_delete_internal(root,p->up);
+        } /* end if */
+        else /* Deleted last node at top level of tree */
+            *root=newp;
+    } /* end else */
+
+    H5FL_FREE(H5ST_node_t,p);
+
+    FUNC_LEAVE(SUCCEED);
+} /* end H5ST_delete_internal() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_delete
+ PURPOSE
+    Delete a node from a TST
+ USAGE
+    herr_t H5ST_delete(tree,p)
+        H5ST_tree_t *tree;  IN/OUT: TST to delete node from
+        H5ST_ptr_t p;       IN: Node to delete
+ RETURNS
+    Success: Non-negative
+    Failure: Negative
+ DESCRIPTION
+    Delete a node from a TST.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+    This should be the final node for a string.
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5ST_delete(H5ST_tree_t *tree, H5ST_ptr_t p)
+{   
+    herr_t ret_value=SUCCEED;   /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_delete,FAIL);
+
+    if(H5ST_delete_internal(&tree->root,p)<0)
+        HGOTO_ERROR(H5E_TST,H5E_CANTDELETE,FAIL,"can't delete node from TST");
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_delete() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_remove
+ PURPOSE
+    Remove a node from a TST
+ USAGE
+    void *H5ST_remove(tree,s)
+        H5ST_tree_t *tree;  IN/OUT: TST to remove node from
+        const char *s;      IN: String of key for node to remove
+ RETURNS
+    Success: Non-NULL, pointer to object stored for key
+    Failure: Negative
+ DESCRIPTION
+    Remove a node from a TST, returning the object from the node.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+void *
+H5ST_remove(H5ST_tree_t *tree, const char *s)
+{
+    H5ST_ptr_t node;    /* Pointer to node to remove */
+    void *ret_value;    /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_remove,NULL);
+
+    /* Locate the node to remove */
+    if((node=H5ST_find_internal(tree->root,s))==NULL)
+        HGOTO_ERROR(H5E_TST,H5E_NOTFOUND,NULL,"key not found in TST");
+
+    /* Get the pointer to the object to return */
+    ret_value=node->eqkid;
+
+    /* Remove the node from the TST */
+    if(H5ST_delete_internal(&tree->root,node)<0)
+        HGOTO_ERROR(H5E_TST,H5E_CANTDELETE,NULL,"can't delete node from TST");
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* H5ST_remove() */
+
+#ifdef H5ST_DEBUG
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_dump_internal
+ PURPOSE
+    Dump all the nodes of a TST
+ USAGE
+    herr_t H5ST_dump(p)
+        H5ST_ptr_t p;   IN: Root of TST to dump
+ RETURNS
+    Success: Non-negative
+    Failure: Negative
+ DESCRIPTION
+    Dump information for a TST.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5ST_dump_internal(H5ST_ptr_t p)
+{
+    FUNC_ENTER_NOINIT(H5ST_dump_internal);
+
+    if (p) {
+        printf("p=%p\n",p);
+        printf("\tp->up=%p\n",p->up);
+        printf("\tp->parent=%p\n",p->parent);
+        printf("\tp->lokid=%p\n",p->lokid);
+        printf("\tp->hikid=%p\n",p->hikid);
+        printf("\tp->eqkid=%p\n",p->eqkid);
+        printf("\tp->splitchar=%c\n",p->splitchar);
+
+        H5ST_dump_internal(p->lokid);
+        if (p->splitchar)
+            H5ST_dump_internal(p->eqkid);
+        else
+            printf("%s\n", (char *) p->eqkid);
+        H5ST_dump_internal(p->hikid);
+    } /* end if */
+
+done:
+    FUNC_LEAVE(SUCCEED);
+} /* end H5ST_dump_internal() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+    H5ST_dump
+ PURPOSE
+    Dump all the nodes of a TST
+ USAGE
+    herr_t H5ST_dump(tree)
+        H5ST_tree_t *tree;      IN: TST to dump
+ RETURNS
+    Success: Non-negative
+    Failure: Negative
+ DESCRIPTION
+    Dump information for a TST.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5ST_dump(H5ST_tree_t *tree)
+{
+    herr_t ret_value=SUCCEED;  /* Return value */
+
+    FUNC_ENTER_NOAPI(H5ST_dump,NULL);
+
+    /* Dump the tree */
+    H5ST_dump_internal(tree->root);
+
+done:
+    FUNC_LEAVE(ret_value);
+} /* end H5ST_dump() */
+#endif /* H5ST_DEBUG */