[svn-r9597] 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

4 files changed, 195 insertions, 248 deletions

diff --git a/src/H5C.c b/src/H5C.c
index fe821b2..0d58339 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				*/
 
 /* Interface initialization? */
 #define INTERFACE_INIT NULL
@@ -143,7 +147,7 @@ if ( ( (head_ptr) == NULL ) ||                                               \
        )                                                                     \
      )                                                                       \
    ) {                                                                       \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, (fv), "DLL pre remove SC failed")   \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, (fv), "DLL pre remove SC failed")     \
 }
 
 #define H5C__DLL_SC(head_ptr, tail_ptr, len, Size, fv)                   \
@@ -163,7 +167,7 @@ if ( ( ( ( (head_ptr) == NULL ) || ( (tail_ptr) == NULL ) ) &&           \
        )                                                                 \
      )                                                                   \
    ) {                                                                   \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, (fv), "DLL sanity check failed") \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, (fv), "DLL sanity check failed")  \
 }
 
 #define H5C__DLL_PRE_INSERT_SC(entry_ptr, head_ptr, tail_ptr, len, Size, fv) \
@@ -185,7 +189,7 @@ if ( ( (entry_ptr) == NULL ) ||                                              \
        )                                                                     \
      )                                                                       \
    ) {                                                                       \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, (fv), "DLL pre insert SC failed")   \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, (fv), "DLL pre insert SC failed")     \
 }
 
 #else /* H5C_DO_SANITY_CHECKS */
@@ -286,7 +290,7 @@ if ( ( (hd_ptr) == NULL ) ||                                                   \
        )                                                                       \
      )                                                                         \
    ) {                                                                         \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, (fv), "aux DLL pre remove SC failed") \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, (fv), "aux DLL pre remove SC failed")   \
 }
 
 #define H5C__AUX_DLL_SC(head_ptr, tail_ptr, len, Size, fv)                  \
@@ -306,7 +310,7 @@ if ( ( ( ( (head_ptr) == NULL ) || ( (tail_ptr) == NULL ) ) &&              \
        )                                                                    \
      )                                                                      \
    ) {                                                                      \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, (fv), "AUX DLL sanity check failed") \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, (fv), "AUX DLL sanity check failed") \
 }
 
 #define H5C__AUX_DLL_PRE_INSERT_SC(entry_ptr, hd_ptr, tail_ptr, len, Size, fv) \
@@ -328,7 +332,7 @@ if ( ( (entry_ptr) == NULL ) ||                                                \
        )                                                                       \
      )                                                                         \
    ) {                                                                         \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, (fv), "AUX DLL pre insert SC failed") \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, (fv), "AUX DLL pre insert SC failed")   \
 }
 
 #else /* H5C_DO_SANITY_CHECKS */
@@ -426,10 +430,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]           \
@@ -437,10 +441,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])++;
@@ -599,7 +603,7 @@ if ( ( (cache_ptr) == NULL ) ||                               \
      ( (entry_ptr)->size <= 0 ) ||                            \
      ( (k = H5C__HASH_FCN((entry_ptr)->addr)) < 0 ) ||        \
      ( k >= H5C__HASH_TABLE_LEN ) ) {                         \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, fail_val,            \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, fail_val,              \
                "Pre HT insert SC failed")                     \
 }
 
@@ -621,7 +625,7 @@ if ( ( (cache_ptr) == NULL ) ||                                         \
      ( ( ((cache_ptr)->index)[(H5C__HASH_FCN((entry_ptr)->addr))] ==    \
          (entry_ptr) ) &&                                               \
        ( (entry_ptr)->ht_prev != NULL ) ) ) {                           \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, FAIL, "Pre HT remove SC failed") \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL, "Pre HT remove SC failed") \
 }
 
 #define H5C__PRE_HT_SEARCH_SC(cache_ptr, Addr, fail_val)                    \
@@ -630,7 +634,7 @@ if ( ( (cache_ptr) == NULL ) ||                                             \
      ( ! H5F_addr_defined(Addr) ) ||                                        \
      ( H5C__HASH_FCN(Addr) < 0 ) ||                                         \
      ( H5C__HASH_FCN(Addr) >= H5C__HASH_TABLE_LEN ) ) {                     \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, fail_val, "Pre HT search SC failed") \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, fail_val, "Pre HT search SC failed") \
 }
 
 #define H5C__POST_SUC_HT_SEARCH_SC(cache_ptr, entry_ptr, Addr, k, fail_val) \
@@ -650,7 +654,7 @@ if ( ( (cache_ptr) == NULL ) ||                                             \
        ( (entry_ptr)->ht_prev->ht_next != (entry_ptr) ) ) ||                \
      ( ( (entry_ptr)->ht_next != NULL ) &&                                  \
        ( (entry_ptr)->ht_next->ht_prev != (entry_ptr) ) ) ) {               \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, fail_val,                          \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, fail_val,                            \
                 "Post successful HT search SC failed")                      \
 }
 
@@ -658,7 +662,7 @@ if ( ( (cache_ptr) == NULL ) ||                                             \
 if ( ( (cache_ptr) == NULL ) ||                                        \
      ( ((cache_ptr)->index)[k] != (entry_ptr) ) ||                     \
      ( (entry_ptr)->ht_prev != NULL ) ) {                              \
-    HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, fail_val,                     \
+    HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, fail_val,                       \
                "Post HT shift to front SC failed")                     \
 }
 
@@ -754,7 +758,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.
@@ -763,10 +767,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
@@ -790,45 +794,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_BADVALUE, 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
@@ -845,37 +846,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_BADVALUE, FAIL,                  \
-                    "Can't delete entry from tree.")                \
+                    "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 */
 
 
 /**************************************************************************
@@ -1593,6 +1591,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"
@@ -1684,23 +1687,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:
  *
@@ -1917,10 +1920,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
@@ -2001,9 +2004,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;
@@ -2046,8 +2049,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;
@@ -2088,9 +2091,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,
@@ -2171,10 +2173,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
@@ -2194,8 +2196,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++ )
     {
@@ -2236,13 +2238,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);
@@ -2303,13 +2300,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;
@@ -2354,18 +2348,15 @@ H5C_dest_empty(H5C_t * cache_ptr)
          ( cache_ptr->magic != H5C__H5C_T_MAGIC ) || 
          ( cache_ptr->index_len != 0 ) ) {
 
-        HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, FAIL, \
+        HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL, \
                     "Bad cache_ptr or non-empty cache on entry.")
     }
 
 
-    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;
@@ -2422,11 +2413,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)
@@ -2434,29 +2425,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 ) {
@@ -2475,7 +2465,6 @@ H5C_flush_cache(H5F_t *  f,
                                             NULL, 
                                             entry_ptr->addr, 
                                             flags, 
-                                            node_ptr, 
                                             &first_flush, 
                                             FALSE);
             if ( status < 0 ) {
@@ -2488,23 +2477,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
@@ -2525,7 +2522,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) );
@@ -2533,7 +2530,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, 
@@ -2542,7 +2539,6 @@ H5C_flush_cache(H5F_t *  f,
                                                     NULL, 
                                                     entry_ptr->addr, 
                                                     flags, 
-                                                    NULL, 
                                                     &first_flush, 
                                                     FALSE);
                     if ( status < 0 ) {
@@ -2571,13 +2567,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;
             }
@@ -2664,13 +2660,13 @@ H5C_insert_entry(H5F_t * 	     f,
 
     if ( (type->size)(f, thing, &(entry_ptr->size)) < 0 ) {
 
-        HGOTO_ERROR(H5E_RESOURCE, H5E_BADSIZE, FAIL, \
+        HGOTO_ERROR(H5E_RESOURCE, H5E_CANTGETSIZE, FAIL, \
                     "Can't get size of thing")
     }
 
     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;
@@ -2695,7 +2691,7 @@ H5C_insert_entry(H5F_t * 	     f,
 
             if ( result < 0 ) {
 
-                HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, \
+                HGOTO_ERROR(H5E_CACHE, H5E_CANTINS, FAIL, \
                             "Can't get write_permitted")
             }
         }
@@ -2738,7 +2734,7 @@ H5C_insert_entry(H5F_t * 	     f,
 
         if ( result < 0 ) {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTINS, FAIL, \
                         "H5C_make_space_in_cache failed.")
         }
     }
@@ -2753,12 +2749,12 @@ H5C_insert_entry(H5F_t * 	     f,
 
         if ( test_entry_ptr == entry_ptr ) {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTINS, FAIL, \
                         "entry already in cache.")
 
         } else {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTINS, FAIL, \
                         "duplicate entry in cache.")
         }
     }
@@ -2775,7 +2771,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)
@@ -2817,10 +2813,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)
 
@@ -2834,30 +2828,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)
 
@@ -2865,18 +2843,18 @@ H5C_rename_entry(H5F_t *	     f,
         
         if ( test_entry_ptr->type == type ) {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTLOAD, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTRENAME, FAIL, \
                         "Target already renamed & reinserted???.")
 
         } else {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTLOAD, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTRENAME, FAIL, \
                         "New address already in use?.")
         }
     }
 
     /* 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
@@ -2887,9 +2865,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;
@@ -2898,7 +2878,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)
@@ -3016,7 +2996,7 @@ H5C_protect(H5F_t *	       f,
 
                 if ( result < 0 ) {
 
-                    HGOTO_ERROR(H5E_CACHE, H5E_PROTECT, NULL, \
+                    HGOTO_ERROR(H5E_CACHE, H5E_CANTPROTECT, NULL, \
                                "Can't get write_permitted")
                 }
             }
@@ -3056,13 +3036,13 @@ H5C_protect(H5F_t *	       f,
 
             if ( result < 0 ) {
 
-                HGOTO_ERROR(H5E_CACHE, H5E_PROTECT, NULL, \
+                HGOTO_ERROR(H5E_CACHE, H5E_CANTPROTECT, NULL, \
                             "H5C_make_space_in_cache failed.")
             }
         }
 
         /* 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)
 
@@ -3079,7 +3059,7 @@ H5C_protect(H5F_t *	       f,
 
     if ( entry_ptr->is_protected ) {
 
-        HGOTO_ERROR(H5E_CACHE, H5E_PROTECT, NULL, \
+        HGOTO_ERROR(H5E_CACHE, H5E_CANTPROTECT, NULL, \
                     "Target already protected?!?.")
     }
 
@@ -3137,8 +3117,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.
  *
  *-------------------------------------------------------------------------
  */
@@ -3174,7 +3154,7 @@ H5C_unprotect(H5F_t *		  f,
 
     if ( ! (entry_ptr->is_protected) ) {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTFLUSH, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTUNPROTECT, FAIL, \
                         "Entry already unprotected??")
     }
 
@@ -3182,13 +3162,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
@@ -3215,12 +3195,12 @@ H5C_unprotect(H5F_t *		  f,
 
         if ( test_entry_ptr == NULL ) {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTFLUSH, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTUNPROTECT, FAIL, \
                         "entry not in hash table?!?.")
         }
         else if ( test_entry_ptr != entry_ptr ) {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTFLUSH, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTUNPROTECT, FAIL, \
                         "hash table contains multiple entries for addr?!?.")
         }
 
@@ -3231,11 +3211,10 @@ H5C_unprotect(H5F_t *		  f,
                                     type, 
                                     addr, 
                                     (H5F_FLUSH_CLEAR_ONLY|H5F_FLUSH_INVALIDATE),
-                                    NULL, 
                                     &dummy_first_flush, 
                                     TRUE) < 0 ) {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTFLUSH, FAIL, "Can't flush.")
+            HGOTO_ERROR(H5E_CACHE, H5E_CANTUNPROTECT, FAIL, "Can't flush.")
         }
     }
 
@@ -3305,7 +3284,7 @@ H5C_stats(H5C_t * cache_ptr,
          ( cache_ptr->magic != H5C__H5C_T_MAGIC ) || 
          ( !cache_name ) ) {
 
-        HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, FAIL, "Bad cache_ptr or cache_name")
+        HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL, "Bad cache_ptr or cache_name")
     }
 
 #if H5C_COLLECT_CACHE_STATS
@@ -3386,11 +3365,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",
@@ -3563,8 +3542,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;
@@ -3621,7 +3600,7 @@ H5C_set_skip_flags(H5C_t * cache_ptr,
      */
     if ( ( ! cache_ptr ) || ( cache_ptr->magic != H5C__H5C_T_MAGIC ) ) {
 
-        HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, FAIL, "Bad cache_ptr")
+        HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL, "Bad cache_ptr")
     }
 
     cache_ptr->skip_file_checks    = skip_file_checks;
@@ -3686,6 +3665,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
@@ -3696,17 +3678,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)
 
@@ -3719,41 +3698,21 @@ 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_BADVALUE, FAIL, \
-                        "Hash table and tree out of sync.")
+            HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL, \
+                        "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 ) ) {
 
-            HGOTO_ERROR(H5E_CACHE, H5E_BADVALUE, FAIL, \
+            HGOTO_ERROR(H5E_CACHE, H5E_SYSTEM, FAIL, \
                         "entry failed sanity checks.")
         }
     }
@@ -3824,9 +3783,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.
@@ -3835,9 +3794,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)
             }
         }
 
@@ -3952,11 +3911,11 @@ 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 ) {
 
-        HGOTO_ERROR(H5E_RESOURCE, H5E_BADSIZE, NULL, \
+        HGOTO_ERROR(H5E_RESOURCE, H5E_CANTGETSIZE, NULL, \
                     "Can't get size of thing")
     }
 
@@ -4073,7 +4032,6 @@ H5C_make_space_in_cache(H5F_t *	f,
                                                 entry_ptr->type, 
                                                 entry_ptr->addr, 
                                                 (unsigned)0, 
-                                                NULL, 
                                                 &first_flush, 
                                                 FALSE);
             } else {
@@ -4085,7 +4043,6 @@ H5C_make_space_in_cache(H5F_t *	f,
                                                 entry_ptr->type, 
                                                 entry_ptr->addr, 
                                                 H5F_FLUSH_INVALIDATE,
-                                                NULL, 
                                                 &first_flush, 
                                                 TRUE);
             }
@@ -4111,7 +4068,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;
 
@@ -4122,7 +4079,6 @@ H5C_make_space_in_cache(H5F_t *	f,
                                             entry_ptr->type, 
                                             entry_ptr->addr, 
                                             (unsigned)0, 
-                                            NULL, 
                                             &first_flush, 
                                             FALSE);
 
@@ -4166,7 +4122,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 1382f21..c238a63 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)                   \
@@ -386,8 +385,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
 --------------------------------------------------------------------------*/