[svn-r9596] Purpose:

    Code optimization

Description:
    Retarget metadata cache code from using TBBT routines to using new skiplist
routines, for a reasonable speedup (when dealing with dirty metadata)

Platforms tested:
    FreeBSD 4.10 (sleipnir) w/parallel
    Solaris 2.7  (arabica)
    Too minor to require h5committest

5 files changed, 170 insertions, 218 deletions

diff --git a/src/H5C.c b/src/H5C.c
index 8c9c74b..120e2c1 100644
--- a/src/H5C.c
+++ b/src/H5C.c
@@ -33,6 +33,10 @@
  *
  * Modifications:
  *
+ *              QAK - 11/27/2004
+ *              Switched over to using skip list routines instead of TBBT
+ *              routines.
+ *
  *-------------------------------------------------------------------------
  */
 
@@ -65,9 +69,9 @@
  *
  *	 - Create MPI type for dirty objects when flushing in parallel.
  *
- *	 - Fix TBBT routines so deletions don't move nodes in memory and
- *         point directly to the TBBT node from the LRU list, eliminating
- *         binary tree lookups when evicting objects from the cache.
+ *	 - Now that TBBT routines aren't used, fix nodes in memory to
+ *         point directly to the skip list node from the LRU list, eliminating
+ *         skip list lookups when evicting objects from the cache.
  *
  *	Tests:
  *
@@ -93,7 +97,7 @@
 #include "H5Iprivate.h"		/* IDs			  		*/
 #include "H5MMprivate.h"	/* Memory management			*/
 #include "H5Pprivate.h"         /* Property lists                       */
-#include "H5TBprivate.h"        /* Threaded, Balanced, Binary Trees     */
+#include "H5SLprivate.h"	/* Skip lists				*/
 
 
 /****************************************************************************
@@ -422,10 +426,10 @@ if ( ( (entry_ptr) == NULL ) ||                                                \
 	    (cache_ptr)->max_index_len = (cache_ptr)->index_len;     \
         if ( (cache_ptr)->index_size > (cache_ptr)->max_index_size ) \
 	    (cache_ptr)->max_index_size = (cache_ptr)->index_size;   \
-        if ( (cache_ptr)->tree_len > (cache_ptr)->max_tree_len )     \
-	    (cache_ptr)->max_tree_len = (cache_ptr)->tree_len;       \
-        if ( (cache_ptr)->tree_size > (cache_ptr)->max_tree_size )   \
-	    (cache_ptr)->max_tree_size = (cache_ptr)->tree_size;     \
+        if ( (cache_ptr)->slist_len > (cache_ptr)->max_slist_len )   \
+	    (cache_ptr)->max_slist_len = (cache_ptr)->slist_len;     \
+        if ( (cache_ptr)->slist_size > (cache_ptr)->max_slist_size ) \
+	    (cache_ptr)->max_slist_size = (cache_ptr)->slist_size;   \
         if ( (entry_ptr)->size >                                     \
              ((cache_ptr)->max_size)[(entry_ptr)->type->id] ) {      \
             ((cache_ptr)->max_size)[(entry_ptr)->type->id]           \
@@ -433,10 +437,10 @@ if ( ( (entry_ptr) == NULL ) ||                                                \
         }
 
 #define H5C__UPDATE_STATS_FOR_UNPROTECT(cache_ptr)                   \
-        if ( (cache_ptr)->tree_len > (cache_ptr)->max_tree_len )     \
-	    (cache_ptr)->max_tree_len = (cache_ptr)->tree_len;       \
-        if ( (cache_ptr)->tree_size > (cache_ptr)->max_tree_size )   \
-	    (cache_ptr)->max_tree_size = (cache_ptr)->tree_size; 
+        if ( (cache_ptr)->slist_len > (cache_ptr)->max_slist_len )   \
+	    (cache_ptr)->max_slist_len = (cache_ptr)->slist_len;     \
+        if ( (cache_ptr)->slist_size > (cache_ptr)->max_slist_size ) \
+	    (cache_ptr)->max_slist_size = (cache_ptr)->slist_size; 
 
 #define H5C__UPDATE_STATS_FOR_RENAME(cache_ptr, entry_ptr) \
 	(((cache_ptr)->renames)[(entry_ptr)->type->id])++;
@@ -750,7 +754,7 @@ if ( ( (cache_ptr) == NULL ) ||                                        \
 
 /**************************************************************************
  *
- * Tree insertion and deletion macros:  
+ * Skip list insertion and deletion macros:  
  *
  * These used to be functions, but I converted them to macros to avoid some
  * function call overhead.
@@ -759,10 +763,10 @@ if ( ( (cache_ptr) == NULL ) ||                                        \
 
 /*-------------------------------------------------------------------------
  *
- * Macro:	H5C__INSERT_ENTRY_IN_TREE
+ * Macro:	H5C__INSERT_ENTRY_IN_SLIST
  *
  * Purpose:     Insert the specified instance of H5C_cache_entry_t into 
- *		the tree in the specified instance of H5C_t.  Update
+ *		the skip list in the specified instance of H5C_t.  Update
  *		the associated length and size fields.
  *
  * Return:      N/A
@@ -786,45 +790,42 @@ if ( ( (cache_ptr) == NULL ) ||                                        \
  *		wringing a little more speed out of the cache.
  *
  *		Note that we don't bother to check if the entry is already
- *		in the tree -- if it is, H5TB_dins() will fail.
+ *		in the tree -- if it is, H5SL_insert() will fail.
+ *
+ *		QAK -- 11/27/04
+ *		Switched over to using skip list routines.
  *
  *-------------------------------------------------------------------------
  */
 
-#define H5C__INSERT_ENTRY_IN_TREE(cache_ptr, entry_ptr)                        \
+#define H5C__INSERT_ENTRY_IN_SLIST(cache_ptr, entry_ptr)                       \
 {                                                                              \
-    H5TB_NODE *	loc_node_ptr = NULL;                                           \
-                                                                               \
     HDassert( (cache_ptr) );                                                   \
     HDassert( (cache_ptr)->magic == H5C__H5C_T_MAGIC );                        \
     HDassert( (entry_ptr) );                                                   \
     HDassert( (entry_ptr)->size > 0 );                                         \
     HDassert( H5F_addr_defined((entry_ptr)->addr) );                           \
-    HDassert( !((entry_ptr)->in_tree) );                                       \
+    HDassert( !((entry_ptr)->in_slist) );                                      \
                                                                                \
-    loc_node_ptr = H5TB_dins((cache_ptr)->tree_ptr, (void *)(entry_ptr), NULL);\
+    if ( H5SL_insert((cache_ptr)->slist_ptr, &entry_ptr->addr, entry_ptr) < 0 ) \
+        HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, FAIL, "Can't insert entry in skip list") \
                                                                                \
-    if ( loc_node_ptr == NULL ) {                                              \
+    (entry_ptr)->in_slist = TRUE;                                              \
+    (cache_ptr)->slist_len++;                                                  \
+    (cache_ptr)->slist_size += (entry_ptr)->size;                              \
                                                                                \
-        HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL, "Can't insert entry in tree") \
-    }                                                                          \
+    HDassert( (cache_ptr)->slist_len > 0 );                                    \
+    HDassert( (cache_ptr)->slist_size > 0 );                                   \
                                                                                \
-    (entry_ptr)->in_tree = TRUE;                                               \
-    (cache_ptr)->tree_len++;                                                   \
-    (cache_ptr)->tree_size += (entry_ptr)->size;                               \
-                                                                               \
-    HDassert( (cache_ptr)->tree_len > 0 );                                     \
-    HDassert( (cache_ptr)->tree_size > 0 );                                    \
-                                                                               \
-} /* H5C__INSERT_ENTRY_IN_TREE */
+} /* H5C__INSERT_ENTRY_IN_SLIST */
 
 
 /*-------------------------------------------------------------------------
  *
- * Function:    H5C__REMOVE_ENTRY_FROM_TREE
+ * Function:    H5C__REMOVE_ENTRY_FROM_SLIST
  *
  * Purpose:     Remove the specified instance of H5C_cache_entry_t from the 
- *		index tree in the specified instance of H5C_t.  Update
+ *		index skip list in the specified instance of H5C_t.  Update
  *		the associated length and size fields.
  *
  * Return:      N/A
@@ -841,37 +842,34 @@ if ( ( (cache_ptr) == NULL ) ||                                        \
  *		to the macro H5C__REMOVE_ENTRY_FROM_TREE in the hopes of
  *		wringing a little more performance out of the cache.
  *
+ *		QAK -- 11/27/04
+ *		Switched over to using skip list routines.
+ *
  *-------------------------------------------------------------------------
  */
 
-#define H5C__REMOVE_ENTRY_FROM_TREE(cache_ptr, entry_ptr, node_ptr) \
+#define H5C__REMOVE_ENTRY_FROM_SLIST(cache_ptr, entry_ptr)          \
 {                                                                   \
     HDassert( (cache_ptr) );                                        \
     HDassert( (cache_ptr)->magic == H5C__H5C_T_MAGIC );             \
     HDassert( (entry_ptr) );                                        \
     HDassert( !((entry_ptr)->is_protected) );                       \
-    HDassert( (node_ptr) );                                         \
-    HDassert( (node_ptr)->data == (entry_ptr) );                    \
     HDassert( (entry_ptr)->size > 0 );                              \
-    HDassert( (entry_ptr)->in_tree );                               \
-    HDassert( (cache_ptr)->tree_ptr );                              \
-    HDassert( (cache_ptr)->tree_ptr->root );                        \
+    HDassert( (entry_ptr)->in_slist );                              \
+    HDassert( (cache_ptr)->slist_ptr );                             \
                                                                     \
-    if ( H5TB_rem(&((cache_ptr)->tree_ptr->root), (node_ptr), NULL) \
-         != (entry_ptr) ) {                                         \
+    if ( H5SL_remove((cache_ptr)->slist_ptr, &(entry_ptr)->addr)    \
+         != (entry_ptr) )                                           \
                                                                     \
-        HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL,                    \
-                    "Can't delete entry from tree.")                \
+        HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, FAIL,                  \
+                    "Can't delete entry from skip list.")           \
                                                                     \
-    } else {                                                        \
-                                                                    \
-        HDassert( (cache_ptr)->tree_len > 0 );                      \
-        (cache_ptr)->tree_len--;                                    \
-        HDassert( (cache_ptr)->tree_size >= (entry_ptr)->size );    \
-        (cache_ptr)->tree_size -= (entry_ptr)->size;                \
-        (entry_ptr)->in_tree = FALSE;                               \
-    }                                                               \
-} /* H5C__REMOVE_ENTRY_FROM_TREE */
+    HDassert( (cache_ptr)->slist_len > 0 );                         \
+    (cache_ptr)->slist_len--;                                       \
+    HDassert( (cache_ptr)->slist_size >= (entry_ptr)->size );       \
+    (cache_ptr)->slist_size -= (entry_ptr)->size;                   \
+    (entry_ptr)->in_slist = FALSE;                                  \
+} /* H5C__REMOVE_ENTRY_FROM_SLIST */
 
 
 /**************************************************************************
@@ -1589,6 +1587,11 @@ if ( ( (cache_ptr) == NULL ) ||                                        \
  *
  *						JRM - 7/19/04
  *
+ * Note that the dirty entries are now stored in a skip list, instead of
+ * the threaded, balanced binary tree (TBBT).
+ *
+ *						QAK - 11/27/04
+ *
  *           *********************************************
  *
  * WARNING:  A copy of H5C_t is in tst/cache.c (under the name "local_H5C_t"
@@ -1680,23 +1683,23 @@ if ( ( (cache_ptr) == NULL ) ||                                        \
  *
  *
  * When we flush the cache, we need to write entries out in increasing
- * address order.  An instance of TBBT is used to store dirty entries in
+ * address order.  An instance of a skip list is used to store dirty entries in
  * sorted order.  Whether it is cheaper to sort the dirty entries as needed,
- * or to maintain the tree is an open question.  At a guess, it depends
+ * or to maintain the list is an open question.  At a guess, it depends
  * on how frequently the cache is flushed.  We will see how it goes.
  *
- * For now at least, I will not remove dirty entries from the tree as they
+ * For now at least, I will not remove dirty entries from the list as they
  * are flushed.
  *
- * tree_len:    Number of entries currently in the threaded binary B-tree
+ * slist_len:    Number of entries currently in the skip list
  *              used to maintain a sorted list of dirty entries in the 
  *		cache.
  *
- * tree_size:   Number of bytes of cache entries currently stored in the
- *              threaded binary B-tree used to maintain a sorted list of
+ * slist_size:   Number of bytes of cache entries currently stored in the
+ *              skip list used to maintain a sorted list of
  *		dirty entries in the cache.
  *
- * tree_ptr:	pointer to the instance of H5TB_TREE used maintain a sorted
+ * slist_ptr:	pointer to the instance of H5SL_t used maintain a sorted
  *		list of dirty entries in the cache.  This sorted list has
  *		two uses:
  *
@@ -1913,10 +1916,10 @@ if ( ( (cache_ptr) == NULL ) ||                                        \
  * max_index_size:  Largest value attained by the index_size field in the
  *              current epoch.
  *
- * max_tree_len:  Largest value attained by the tree_len field in the
+ * max_slist_len:  Largest value attained by the slist_len field in the
  *              current epoch.
  *
- * max_tree_size:  Largest value attained by the tree_size field in the
+ * max_slist_size:  Largest value attained by the slist_size field in the
  *              current epoch.
  *
  * max_pl_len:  Largest value attained by the pl_len field in the
@@ -1997,9 +2000,9 @@ struct H5C_t
     H5C_cache_entry_t *		(index[H5C__HASH_TABLE_LEN]);
 
 
-    int32_t                     tree_len;
-    size_t                      tree_size;
-    H5TB_TREE *                 tree_ptr;
+    int32_t                     slist_len;
+    size_t                      slist_size;
+    H5SL_t *                    slist_ptr;
 
     int32_t                     pl_len;
     size_t                      pl_size;
@@ -2042,8 +2045,8 @@ struct H5C_t
     int32_t                     max_index_len;
     size_t                      max_index_size;
 
-    int32_t                     max_tree_len;
-    size_t                      max_tree_size;
+    int32_t                     max_slist_len;
+    size_t                      max_slist_size;
 
     int32_t                     max_pl_len;
     size_t                      max_pl_size;
@@ -2084,9 +2087,8 @@ static herr_t H5C_flush_single_entry(H5F_t *             f,
                                      const H5C_class_t * type_ptr,
                                      haddr_t             addr,
                                      unsigned            flags,
-                                     H5TB_NODE *         tgt_node_ptr,
                                      hbool_t *           first_flush_ptr,
-                                     hbool_t    del_entry_from_tree_on_destroy);
+                                     hbool_t    del_entry_from_slist_on_destroy);
 
 static void * H5C_load_entry(H5F_t *             f,
                              hid_t               dxpl_id,
@@ -2167,10 +2169,10 @@ H5C_create(size_t		      max_cache_size,
                     "memory allocation failed")
     }
 
-    if ( (cache_ptr->tree_ptr = H5TB_fast_dmake(H5TB_FAST_HADDR_COMPARE)) 
+    if ( (cache_ptr->slist_ptr = H5SL_create(H5SL_TYPE_HADDR,0.5,16)) 
          == NULL ) {
 
-        HGOTO_ERROR(H5E_CACHE, H5E_CANTCREATE, NULL, "can't create TBBT.")
+        HGOTO_ERROR(H5E_CACHE, H5E_CANTCREATE, NULL, "can't create skip list.")
     }
 
     /* If we get this far, we should succeed.  Go ahead and initialize all
@@ -2190,8 +2192,8 @@ H5C_create(size_t		      max_cache_size,
     cache_ptr->index_len		= 0;
     cache_ptr->index_size		= (size_t)0;
 
-    cache_ptr->tree_len			= 0;
-    cache_ptr->tree_size		= (size_t)0;
+    cache_ptr->slist_len			= 0;
+    cache_ptr->slist_size		= (size_t)0;
 
     for ( i = 0; i < H5C__HASH_TABLE_LEN; i++ )
     {
@@ -2232,13 +2234,8 @@ done:
 
         if ( cache_ptr != NULL ) {
 
-            if ( cache_ptr->tree_ptr != NULL ) {
-
-                /* the index tree should be empty, so we can pass in
-                 * NULL for the fd & fk parameters.
-                 */
-                H5TB_dfree(cache_ptr->tree_ptr, NULL, NULL);
-            }
+            if ( cache_ptr->slist_ptr != NULL )
+                H5SL_close(cache_ptr->slist_ptr);
 
             cache_ptr->magic = 0;
             H5FL_FREE(H5C_t, cache_ptr);
@@ -2299,13 +2296,10 @@ H5C_dest(H5F_t * f,
         HGOTO_ERROR(H5E_CACHE, H5E_CANTFLUSH, FAIL, "unable to flush cache")
     }
 
-    if ( cache_ptr->tree_ptr != NULL ) {
+    if ( cache_ptr->slist_ptr != NULL ) {
 
-        /* the index tree should be empty, so we can pass in
-         * NULL for the fd & fk parameters.
-         */
-        H5TB_dfree(cache_ptr->tree_ptr, NULL, NULL);
-        cache_ptr->tree_ptr = NULL;
+        H5SL_close(cache_ptr->slist_ptr);
+        cache_ptr->slist_ptr = NULL;
     }
 
     cache_ptr->magic = 0;
@@ -2355,13 +2349,10 @@ H5C_dest_empty(H5C_t * cache_ptr)
     }
 
 
-    if ( cache_ptr->tree_ptr != NULL ) {
+    if ( cache_ptr->slist_ptr != NULL ) {
 
-        /* the tree should be empty, so we can pass in
-         * NULL for the fd & fk parameters.
-         */
-        H5TB_dfree(cache_ptr->tree_ptr, NULL, NULL);
-        cache_ptr->tree_ptr = NULL;
+        H5SL_close(cache_ptr->slist_ptr);
+        cache_ptr->slist_ptr = NULL;
     }
 
     cache_ptr->magic = 0;
@@ -2418,11 +2409,11 @@ H5C_flush_cache(H5F_t *  f,
     hbool_t		first_flush = TRUE;
     int32_t		protected_entries = 0;
     int32_t		i;
-    H5TB_NODE * 	node_ptr;
+    H5SL_node_t * 	node_ptr;
     H5C_cache_entry_t *	entry_ptr;
 #if H5C_DO_SANITY_CHECKS
-    int32_t		actual_tree_len = 0;
-    size_t              actual_tree_size = 0;
+    int32_t		actual_slist_len = 0;
+    size_t              actual_slist_size = 0;
 #endif /* H5C_DO_SANITY_CHECKS */
 
     FUNC_ENTER_NOAPI(H5C_flush_cache, FAIL)
@@ -2430,29 +2421,28 @@ H5C_flush_cache(H5F_t *  f,
     HDassert( cache_ptr );
     HDassert( cache_ptr->magic == H5C__H5C_T_MAGIC );
     HDassert( cache_ptr->skip_file_checks || f );
-    HDassert( cache_ptr->tree_ptr );
+    HDassert( cache_ptr->slist_ptr );
 
-    if ( cache_ptr->tree_ptr->root == NULL ) {
+    if ( cache_ptr->slist_len == 0 ) {
 
         node_ptr = NULL;
-        HDassert( cache_ptr->tree_len == 0 );
-        HDassert( cache_ptr->tree_size == 0 );
+        HDassert( cache_ptr->slist_size == 0 );
 
     } else {
 
-        node_ptr = H5TB_first(cache_ptr->tree_ptr->root);
+        node_ptr = H5SL_first(cache_ptr->slist_ptr);
     }
 
     while ( node_ptr != NULL )
     {
-        entry_ptr = (H5C_cache_entry_t *)(node_ptr->data);
+        entry_ptr = (H5C_cache_entry_t *)H5SL_item(node_ptr);
 
         HDassert( entry_ptr != NULL );
-        HDassert( entry_ptr->in_tree );
+        HDassert( entry_ptr->in_slist );
 
 #if H5C_DO_SANITY_CHECKS
-        actual_tree_len++;
-        actual_tree_size += entry_ptr->size;
+        actual_slist_len++;
+        actual_slist_size += entry_ptr->size;
 #endif /* H5C_DO_SANITY_CHECKS */
 
         if ( entry_ptr->is_protected ) {
@@ -2471,7 +2461,6 @@ H5C_flush_cache(H5F_t *  f,
                                             NULL, 
                                             entry_ptr->addr, 
                                             flags, 
-                                            node_ptr, 
                                             &first_flush, 
                                             FALSE);
             if ( status < 0 ) {
@@ -2484,23 +2473,31 @@ H5C_flush_cache(H5F_t *  f,
             }
         }
 
-        node_ptr = H5TB_next(node_ptr);
+        node_ptr = H5SL_next(node_ptr);
 
     } /* while */
 
 #if H5C_DO_SANITY_CHECKS
-    HDassert( actual_tree_len == cache_ptr->tree_len );
-    HDassert( actual_tree_size == cache_ptr->tree_size );
+    HDassert( actual_slist_len == cache_ptr->slist_len );
+    HDassert( actual_slist_size == cache_ptr->slist_size );
 #endif /* H5C_DO_SANITY_CHECKS */
 
     if ( destroy ) {
 
-        /* don't pass in any key or data free functions, as all
-         * unprotected entries should have already been destroyed.
-         */
-        H5TB_free(&(cache_ptr->tree_ptr->root), NULL, NULL);
-        cache_ptr->tree_len = 0;
-        cache_ptr->tree_size = 0;
+        if(cache_ptr->slist_ptr) {
+
+            /* XXX: Replace this with call to H5SL_free() when its implemented... */
+            H5SL_close(cache_ptr->slist_ptr);
+
+            /* XXX: ...and remove this call */
+            if ( (cache_ptr->slist_ptr = H5SL_create(H5SL_TYPE_HADDR,0.5,16)) 
+                 == NULL ) {
+
+                HGOTO_ERROR(H5E_CACHE, H5E_CANTCREATE, FAIL, "can't create skip list.")
+            }
+        }
+        cache_ptr->slist_len = 0;
+        cache_ptr->slist_size = 0;
 
         /* Since we are doing a destroy, we must make a pass through
          * the hash table and flush all entries that remain.  Note that
@@ -2521,7 +2518,7 @@ H5C_flush_cache(H5F_t *  f,
                     
                     H5C__DELETE_FROM_INDEX(cache_ptr, entry_ptr)
 
-                    if ( !entry_ptr->in_tree ) {
+                    if ( !entry_ptr->in_slist ) {
 
 	                protected_entries++;
                         HDassert( !(entry_ptr->is_dirty) );
@@ -2529,7 +2526,7 @@ H5C_flush_cache(H5F_t *  f,
                 } else {
 
                     HDassert( !(entry_ptr->is_dirty) );
-                    HDassert( !(entry_ptr->in_tree) );
+                    HDassert( !(entry_ptr->in_slist) );
 
                     status = H5C_flush_single_entry(f, 
                                                     primary_dxpl_id, 
@@ -2538,7 +2535,6 @@ H5C_flush_cache(H5F_t *  f,
                                                     NULL, 
                                                     entry_ptr->addr, 
                                                     flags, 
-                                                    NULL, 
                                                     &first_flush, 
                                                     FALSE);
                     if ( status < 0 ) {
@@ -2567,13 +2563,13 @@ H5C_flush_cache(H5F_t *  f,
 
             while ( entry_ptr != NULL )
             {
-                entry_ptr->in_tree = FALSE;
+                entry_ptr->in_slist = FALSE;
 
                 H5C__INSERT_IN_INDEX(cache_ptr, entry_ptr, FAIL)
 
                 if ( entry_ptr->is_dirty ) {
 
-                    H5C__INSERT_ENTRY_IN_TREE(cache_ptr, entry_ptr)
+                    H5C__INSERT_ENTRY_IN_SLIST(cache_ptr, entry_ptr)
                 }
                 entry_ptr = entry_ptr->next;
             }
@@ -2666,7 +2662,7 @@ H5C_insert_entry(H5F_t * 	     f,
 
     HDassert( entry_ptr->size < H5C_MAX_ENTRY_SIZE ); 
 
-    entry_ptr->in_tree = FALSE;
+    entry_ptr->in_slist = FALSE;
 
     entry_ptr->ht_next = NULL;
     entry_ptr->ht_prev = NULL;
@@ -2771,7 +2767,7 @@ H5C_insert_entry(H5F_t * 	     f,
 
     if ( entry_ptr->is_dirty ) {
 
-        H5C__INSERT_ENTRY_IN_TREE(cache_ptr, entry_ptr)
+        H5C__INSERT_ENTRY_IN_SLIST(cache_ptr, entry_ptr)
     }
 
     H5C__UPDATE_RP_FOR_INSERTION(cache_ptr, entry_ptr, FAIL)
@@ -2813,10 +2809,8 @@ H5C_rename_entry(H5F_t *	     f,
 	         haddr_t 	     new_addr)
 {
     herr_t		ret_value = SUCCEED;      /* Return value */
-    H5TB_NODE *		old_node_ptr = NULL;
     H5C_cache_entry_t *	entry_ptr = NULL;
     H5C_cache_entry_t *	test_entry_ptr = NULL;
-    H5C_cache_entry_t	search_target;
 
     FUNC_ENTER_NOAPI(H5C_rename_entry, FAIL)
 
@@ -2830,30 +2824,14 @@ H5C_rename_entry(H5F_t *	     f,
 
     H5C__SEARCH_INDEX(cache_ptr, old_addr, entry_ptr, FAIL)
 
-    if ( ( entry_ptr == NULL ) || ( entry_ptr->type != type ) ) {
+    if ( ( entry_ptr == NULL ) || ( entry_ptr->type != type ) )
 
         /* the old item doesn't exist in the cache, so we are done. */
         HGOTO_DONE(SUCCEED)
 
-    } else {
-
-        HDassert( entry_ptr->addr == old_addr );
-        HDassert( entry_ptr->type == type );
-        HDassert( !(entry_ptr->is_protected) );
-
-        if ( entry_ptr->in_tree ) {
-
-            HDassert( cache_ptr->tree_ptr );
-            search_target.addr = old_addr;
-
-            old_node_ptr = H5TB_dfind(cache_ptr->tree_ptr, 
-                                      (void *)(&search_target), 
-                                      NULL);
-
-            HDassert( old_node_ptr != NULL );
-            HDassert( old_node_ptr->key == (void *)entry_ptr );
-        }
-    }
+    HDassert( entry_ptr->addr == old_addr );
+    HDassert( entry_ptr->type == type );
+    HDassert( !(entry_ptr->is_protected) );
 
     H5C__SEARCH_INDEX(cache_ptr, new_addr, test_entry_ptr, FAIL)
 
@@ -2872,7 +2850,7 @@ H5C_rename_entry(H5F_t *	     f,
     }
 
     /* If we get this far, we have work to do.  Remove *entry_ptr from
-     * the hash table (and tree if necessary), change its address to the 
+     * the hash table (and skip list if necessary), change its address to the 
      * new address, and then re-insert.
      *
      * Update the replacement policy for a hit to avoid an eviction before
@@ -2883,9 +2861,11 @@ H5C_rename_entry(H5F_t *	     f,
      */
     H5C__DELETE_FROM_INDEX(cache_ptr, entry_ptr)
 
-    if ( old_node_ptr ) {
+    if ( entry_ptr->in_slist ) {
 
-        H5C__REMOVE_ENTRY_FROM_TREE(cache_ptr, entry_ptr, old_node_ptr)
+        HDassert( cache_ptr->slist_ptr );
+
+        H5C__REMOVE_ENTRY_FROM_SLIST(cache_ptr, entry_ptr)
     }
 
     entry_ptr->addr = new_addr;
@@ -2894,7 +2874,7 @@ H5C_rename_entry(H5F_t *	     f,
 
     if ( entry_ptr->is_dirty ) {
 
-        H5C__INSERT_ENTRY_IN_TREE(cache_ptr, entry_ptr)
+        H5C__INSERT_ENTRY_IN_SLIST(cache_ptr, entry_ptr)
     }
 
     H5C__UPDATE_RP_FOR_RENAME(cache_ptr, entry_ptr, FAIL)
@@ -3058,7 +3038,7 @@ H5C_protect(H5F_t *	       f,
         }
 
         /* Insert the entry in the hash table.  It can't be dirty yet, so 
-         * we don't even check to see if it should go in the tree.
+         * we don't even check to see if it should go in the skip list.
          */
         H5C__INSERT_IN_INDEX(cache_ptr, entry_ptr, NULL)
 
@@ -3133,8 +3113,8 @@ done:
  *
  *		JRM - 7/21/04
  *		Updated the function for the addition of the hash table.
- *		In particular, we now add dirty entries to the tree if
- *		they aren't in the tree already.
+ *		In particular, we now add dirty entries to the skip list if
+ *		they aren't in the list already.
  *
  *-------------------------------------------------------------------------
  */
@@ -3178,13 +3158,13 @@ H5C_unprotect(H5F_t *		  f,
 
     entry_ptr->is_protected = FALSE;    
 
-    /* add the entry to the tree if it is dirty, and it isn't already in
-     * the tree.
+    /* add the entry to the skip list if it is dirty, and it isn't already in
+     * the list.
      */
 
-    if ( ( entry_ptr->is_dirty ) && ( ! (entry_ptr->in_tree) ) ) {
+    if ( ( entry_ptr->is_dirty ) && ( ! (entry_ptr->in_slist) ) ) {
 
-        H5C__INSERT_ENTRY_IN_TREE(cache_ptr, entry_ptr)
+        H5C__INSERT_ENTRY_IN_SLIST(cache_ptr, entry_ptr)
     }
 
     /* this implementation of the "deleted" option is a bit inefficient, as
@@ -3227,7 +3207,6 @@ H5C_unprotect(H5F_t *		  f,
                                     type, 
                                     addr, 
                                     (H5F_FLUSH_CLEAR_ONLY|H5F_FLUSH_INVALIDATE),
-                                    NULL, 
                                     &dummy_first_flush, 
                                     TRUE) < 0 ) {
 
@@ -3382,11 +3361,11 @@ H5C_stats(H5C_t * cache_ptr,
               (long)(cache_ptr->max_index_len));
 
     HDfprintf(stdout, 
-              "  current (max) tree size / length   = %ld (%ld) / %ld (%ld)\n",
-              (long)(cache_ptr->tree_size),
-              (long)(cache_ptr->max_tree_size),
-              (long)(cache_ptr->tree_len),
-              (long)(cache_ptr->max_tree_len));
+              "  current (max) skip list size / length   = %ld (%ld) / %ld (%ld)\n",
+              (long)(cache_ptr->slist_size),
+              (long)(cache_ptr->max_slist_size),
+              (long)(cache_ptr->slist_len),
+              (long)(cache_ptr->max_slist_len));
 
     HDfprintf(stdout, 
               "  current (max) PL size / length     = %ld (%ld) / %ld (%ld)\n",
@@ -3559,8 +3538,8 @@ H5C_stats__reset(H5C_t * cache_ptr)
     cache_ptr->max_index_len			= 0;
     cache_ptr->max_index_size			= (size_t)0;
 
-    cache_ptr->max_tree_len			= 0;
-    cache_ptr->max_tree_size			= (size_t)0;
+    cache_ptr->max_slist_len			= 0;
+    cache_ptr->max_slist_size			= (size_t)0;
 
     cache_ptr->max_pl_len			= 0;
     cache_ptr->max_pl_size			= (size_t)0;
@@ -3682,6 +3661,9 @@ done:
  *		JRM -- 7/21/04
  *		Updated function for the addition of the hash table.
  *
+ *		QAK -- 11/26/04
+ *		Updated function for the switch from TBBTs to skip lists.
+ *
  *-------------------------------------------------------------------------
  */
 static herr_t
@@ -3692,17 +3674,14 @@ H5C_flush_single_entry(H5F_t *		   f,
                        const H5C_class_t * type_ptr, 
                        haddr_t		   addr, 
                        unsigned		   flags,
-                       H5TB_NODE *	   tgt_node_ptr,
                        hbool_t *	   first_flush_ptr,
-                       hbool_t		   del_entry_from_tree_on_destroy)
+                       hbool_t		   del_entry_from_slist_on_destroy)
 {
     hbool_t		destroy = ( (flags & H5F_FLUSH_INVALIDATE) != 0 );
     hbool_t		clear_only = ( (flags & H5F_FLUSH_CLEAR_ONLY) != 0);  
     herr_t		ret_value = SUCCEED;      /* Return value */
     herr_t		status;
-    H5TB_NODE *		node_ptr;
     H5C_cache_entry_t *	entry_ptr = NULL;
-    H5C_cache_entry_t	search_target;
 
     FUNC_ENTER_NOAPI_NOINIT(H5C_flush_single_entry)
 
@@ -3715,37 +3694,17 @@ H5C_flush_single_entry(H5F_t *		   f,
     /* attempt to find the target entry in the hash table */
     H5C__SEARCH_INDEX(cache_ptr, addr, entry_ptr, FAIL)
 
-    /* If tgt_node_ptr is NULL, look up the target entry in the tree. */
-
-    if ( tgt_node_ptr == NULL ) {
-
-        HDassert( cache_ptr->tree_ptr );
-        search_target.addr = addr;
-
-        node_ptr = H5TB_dfind(cache_ptr->tree_ptr, 
-                              (void *)&search_target, 
-                              NULL);
-
-    } else {
-
-        node_ptr = tgt_node_ptr;
-    }
-
 #if H5C_DO_SANITY_CHECKS
-    if ( node_ptr != NULL ) {
+    if ( entry_ptr->in_slist ) {
 
-        if ( ( entry_ptr == NULL ) ||
-             ( entry_ptr != (H5C_cache_entry_t *)(node_ptr->data) ) ||
-             ( ! (entry_ptr->in_tree) ) ||
-             ( entry_ptr->addr != addr ) ||
-             ( node_ptr->data != node_ptr->key ) ) {
+        if ( ( entry_ptr->addr != addr ) ) {
 
             HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL, \
-                        "Hash table and tree out of sync.")
+                        "Hash table and skip list out of sync.")
         }
     } else if ( entry_ptr != NULL ) {
 
-        if ( ( entry_ptr->in_tree ) ||
+        if ( ( entry_ptr->in_slist ) ||
              ( entry_ptr->is_dirty ) ||
              ( entry_ptr->addr != addr ) ) {
 
@@ -3820,9 +3779,9 @@ H5C_flush_single_entry(H5F_t *		   f,
         }
 
         /* Always remove the entry from the hash table on a destroy.  On a 
-         * flush with destroy, it is cheaper to discard the tree all at once
+         * flush with destroy, it is cheaper to discard the skip list all at once
          * rather than remove the entries one by one, so we only delete from
-         * the tree if requested.
+         * the list if requested.
          *
          * We must do deletions now as the callback routines will free the 
          * entry if destroy is true.
@@ -3831,9 +3790,9 @@ H5C_flush_single_entry(H5F_t *		   f,
 
             H5C__DELETE_FROM_INDEX(cache_ptr, entry_ptr)
 
-            if ( ( node_ptr ) && ( del_entry_from_tree_on_destroy ) ) {
+            if ( ( entry_ptr->in_slist ) && ( del_entry_from_slist_on_destroy ) ) {
 
-                H5C__REMOVE_ENTRY_FROM_TREE(cache_ptr, entry_ptr, node_ptr)
+                H5C__REMOVE_ENTRY_FROM_SLIST(cache_ptr, entry_ptr)
             }
         }
 
@@ -3948,7 +3907,7 @@ H5C_load_entry(H5F_t *             f,
     entry_ptr->addr = addr;
     entry_ptr->type = type;
     entry_ptr->is_protected = FALSE;
-    entry_ptr->in_tree = FALSE;
+    entry_ptr->in_slist = FALSE;
 
     if ( (type->size)(f, thing, &(entry_ptr->size)) < 0 ) {
 
@@ -4069,7 +4028,6 @@ H5C_make_space_in_cache(H5F_t *	f,
                                                 entry_ptr->type, 
                                                 entry_ptr->addr, 
                                                 (unsigned)0, 
-                                                NULL, 
                                                 &first_flush, 
                                                 FALSE);
             } else {
@@ -4081,7 +4039,6 @@ H5C_make_space_in_cache(H5F_t *	f,
                                                 entry_ptr->type, 
                                                 entry_ptr->addr, 
                                                 H5F_FLUSH_INVALIDATE,
-                                                NULL, 
                                                 &first_flush, 
                                                 TRUE);
             }
@@ -4107,7 +4064,7 @@ H5C_make_space_in_cache(H5F_t *	f,
         {
             HDassert( ! (entry_ptr->is_protected) );
             HDassert( entry_ptr->is_dirty );
-            HDassert( entry_ptr->in_tree );
+            HDassert( entry_ptr->in_slist );
 
             prev_ptr = entry_ptr->aux_prev;
 
@@ -4118,7 +4075,6 @@ H5C_make_space_in_cache(H5F_t *	f,
                                             entry_ptr->type, 
                                             entry_ptr->addr, 
                                             (unsigned)0, 
-                                            NULL, 
                                             &first_flush, 
                                             FALSE);
 
@@ -4162,7 +4118,6 @@ H5C_make_space_in_cache(H5F_t *	f,
                                             entry_ptr->type, 
                                             entry_ptr->addr, 
                                             H5F_FLUSH_INVALIDATE,
-                                            NULL, 
                                             &first_flush, 
                                             TRUE);
 
diff --git a/src/H5Cprivate.h b/src/H5Cprivate.h
index 4c14c4c..7ae6b58 100644
--- a/src/H5Cprivate.h
+++ b/src/H5Cprivate.h
@@ -158,20 +158,14 @@ typedef herr_t (*H5C_write_permitted_func_t)(H5F_t *f,
  * structure H5C_cache_entry_t
  *
  * Instances of the H5C_cache_entry_t structure are used to store cache 
- * entries in a hash table and sometimes in a threaded balanced binary tree.  
- * See H5TB.c for the particulars of the tree.
+ * entries in a hash table and sometimes in a skip list.  
+ * See H5SL.c for the particulars of the skip list.
  *
  * In typical application, this structure is the first field in a 
  * structure to be cached.  For historical reasons, the external module
  * is responsible for managing the is_dirty field.  All other fields are
  * managed by the cache.
  *
- * Note that our current implementation of a threaded balanced binary tree 
- * will occasionaly change the node a particular datum is associated with.  
- * Thus this structure does not have a back pointer to its tree node.  If we
- * ever modify the threaded balanced binary tree code to fix this, a back 
- * pointer would save us a few tree traversals.
- *
  * The fields of this structure are discussed individually below:
  *
  *						JRM - 4/26/04
@@ -214,10 +208,10 @@ typedef herr_t (*H5C_write_permitted_func_t)(H5F_t *f,
  *		Note that protected entries are removed from the LRU lists
  *		and inserted on the protected list.
  *
- * in_tree:	Boolean flag indicating whether the entry is in the threaded
- *		balanced binary tree.  As a general rule, entries are placed
- *		in the tree when they are marked dirty.  However they may
- *		remain in the tree after being flushed.
+ * in_slist:	Boolean flag indicating whether the entry is in the skip list
+ *		As a general rule, entries are placed in the list when they
+ *              are marked dirty.  However they may remain in the list after
+ *              being flushed.
  *
  *
  * Fields supporting the hash table:
@@ -322,7 +316,7 @@ typedef struct H5C_cache_entry_t
     const H5C_class_t *	type;
     hbool_t		is_dirty;
     hbool_t		is_protected;
-    hbool_t		in_tree;
+    hbool_t		in_slist;
 
     /* fields supporting the hash table: */
 
diff --git a/src/H5FOprivate.h b/src/H5FOprivate.h
index a752a75..8217907 100644
--- a/src/H5FOprivate.h
+++ b/src/H5FOprivate.h
@@ -25,7 +25,7 @@
 /* Private headers needed by this file */
 #include "H5private.h"		/* Generic Functions			*/
 #include "H5Fprivate.h"		/* File access				*/
-#include "H5SLprivate.h"	/* Skip list routines			*/
+#include "H5SLprivate.h"	/* Skip lists				*/
 
 /* Typedefs */
 
diff --git a/src/H5SL.c b/src/H5SL.c
index bf00071..9370ba7 100644
--- a/src/H5SL.c
+++ b/src/H5SL.c
@@ -47,8 +47,7 @@
 
 /* Define the code template for insertions for the "OP" in the H5SL_FIND macro */
 #define H5SL_FIND_INSERT_FOUND(SLIST,X,UPDATE,I,ITEM)                   \
-        X->item=ITEM;                                                   \
-        HGOTO_DONE(SUCCEED);
+        HGOTO_DONE(FAIL);
 
 /* Define the code template for removals for the "OP" in the H5SL_FIND macro */
 #define H5SL_FIND_REMOVE_FOUND(SLIST,X,UPDATE,I,ITEM)                   \
@@ -381,8 +380,7 @@ H5SL_count(H5SL_t *slist)
     Insert element into a skip list.
  GLOBAL VARIABLES
  COMMENTS, BUGS, ASSUMPTIONS
-    Inserting an item with the same key as an existing object replaces
-    the existing object's item pointer with the new item pointer.
+    Inserting an item with the same key as an existing object fails.
  EXAMPLES
  REVISION LOG
 --------------------------------------------------------------------------*/
diff --git a/test/tskiplist.c b/test/tskiplist.c
index 20bde76..cf88daf 100644
--- a/test/tskiplist.c
+++ b/test/tskiplist.c
@@ -181,6 +181,11 @@ test_skiplist_insert(void)
     found_item=H5SL_search(slist,&search_key);
     VERIFY(found_item, NULL, "H5SL_search");
 
+    /* Attempt to insert duplicate key (should fail) */
+    search_key=2;
+    ret=H5SL_insert(slist,&search_key,&search_key);
+    VERIFY(ret, FAIL, "H5SL_insert");
+
     /* Close the skip list */
     ret=H5SL_close(slist);
     CHECK(ret, FAIL, "H5SL_close");