Switches the tagged metadata list from a skip list to a hash table (#1925)

5 files changed, 98 insertions, 130 deletions

diff --git a/src/H5C.c b/src/H5C.c
index 51fa334..b0115c8 100644
--- a/src/H5C.c
+++ b/src/H5C.c
@@ -294,8 +294,7 @@ H5C_create(size_t max_cache_size, size_t min_clean_size, int max_type_id,
     if (NULL == (cache_ptr->slist_ptr = H5SL_create(H5SL_TYPE_HADDR, NULL)))
         HGOTO_ERROR(H5E_CACHE, H5E_CANTCREATE, NULL, "can't create skip list")
 
-    if (NULL == (cache_ptr->tag_list = H5SL_create(H5SL_TYPE_HADDR, NULL)))
-        HGOTO_ERROR(H5E_CACHE, H5E_CANTCREATE, NULL, "can't create skip list for tagged entry addresses")
+    cache_ptr->tag_list = NULL;
 
     /* If we get this far, we should succeed.  Go ahead and initialize all
      * the fields.
@@ -513,16 +512,16 @@ done:
             if (cache_ptr->slist_ptr != NULL)
                 H5SL_close(cache_ptr->slist_ptr);
 
-            if (cache_ptr->tag_list != NULL)
-                H5SL_close(cache_ptr->tag_list);
+            HASH_CLEAR(hh, cache_ptr->tag_list);
+            cache_ptr->tag_list = NULL;
 
             if (cache_ptr->log_info != NULL)
                 H5MM_xfree(cache_ptr->log_info);
 
             cache_ptr->magic = 0;
             cache_ptr        = H5FL_FREE(H5C_t, cache_ptr);
-        } /* end if */
-    }     /* end if */
+        }
+    }
 
     FUNC_LEAVE_NOAPI(ret_value)
 } /* H5C_create() */
@@ -662,33 +661,6 @@ H5C_def_auto_resize_rpt_fcn(H5C_t *cache_ptr,
 } /* H5C_def_auto_resize_rpt_fcn() */
 
 /*-------------------------------------------------------------------------
- * Function:    H5C__free_tag_list_cb
- *
- * Purpose:     Callback function to free tag nodes from the skip list.
- *
- * Return:      Non-negative on success/Negative on failure
- *
- * Programmer:  Vailin Choi
- *        January 2014
- *
- *-------------------------------------------------------------------------
- */
-static herr_t
-H5C__free_tag_list_cb(void *_item, void H5_ATTR_UNUSED *key, void H5_ATTR_UNUSED *op_data)
-{
-    H5C_tag_info_t *tag_info = (H5C_tag_info_t *)_item;
-
-    FUNC_ENTER_PACKAGE_NOERR
-
-    HDassert(tag_info);
-
-    /* Release the item */
-    tag_info = H5FL_FREE(H5C_tag_info_t, tag_info);
-
-    FUNC_LEAVE_NOAPI(0)
-} /* H5C__free_tag_list_cb() */
-
-/*-------------------------------------------------------------------------
  *
  * Function:    H5C_prep_for_file_close
  *
@@ -851,28 +823,24 @@ H5C_dest(H5F_t *f)
      *           point?  If no, shouldn't this if statement be an assert?
      */
     if (cache_ptr->slist_ptr != NULL) {
-
         HDassert(cache_ptr->slist_len == 0);
         HDassert(cache_ptr->slist_size == 0);
 
         H5SL_close(cache_ptr->slist_ptr);
 
         cache_ptr->slist_ptr = NULL;
+    }
 
-    } /* end if */
-
-    if (cache_ptr->tag_list != NULL) {
-
-        H5SL_destroy(cache_ptr->tag_list, H5C__free_tag_list_cb, NULL);
-
-        cache_ptr->tag_list = NULL;
-
-    } /* end if */
-
-    if (cache_ptr->log_info != NULL) {
+    H5C_tag_info_t *item = NULL;
+    H5C_tag_info_t *tmp  = NULL;
+    HASH_ITER(hh, cache_ptr->tag_list, item, tmp)
+    {
+        HASH_DELETE(hh, cache_ptr->tag_list, item);
+        item = H5FL_FREE(H5C_tag_info_t, item);
+    }
 
+    if (cache_ptr->log_info != NULL)
         H5MM_xfree(cache_ptr->log_info);
-    }
 
 #ifndef NDEBUG
 #if H5C_DO_SANITY_CHECKS
@@ -8104,7 +8072,7 @@ done:
 herr_t
 H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked)
 {
-    H5C_tag_info_t *tag_info; /* Points to a tag info struct */
+    H5C_tag_info_t *tag_info  = NULL;
     herr_t          ret_value = SUCCEED;
 
     FUNC_ENTER_NOAPI_NOINIT
@@ -8115,7 +8083,7 @@ H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked)
     HDassert(action == H5C__SET_CORK || action == H5C__UNCORK || action == H5C__GET_CORKED);
 
     /* Search the list of corked object addresses in the cache */
-    tag_info = (H5C_tag_info_t *)H5SL_search(cache_ptr->tag_list, &obj_addr);
+    HASH_FIND(hh, cache_ptr->tag_list, &obj_addr, sizeof(haddr_t), tag_info);
 
     if (H5C__GET_CORKED == action) {
         HDassert(corked);
@@ -8123,7 +8091,7 @@ H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked)
             *corked = TRUE;
         else
             *corked = FALSE;
-    } /* end if */
+    }
     else {
         /* Sanity check */
         HDassert(H5C__SET_CORK == action || H5C__UNCORK == action);
@@ -8139,25 +8107,24 @@ H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked)
                 /* Set the tag for all entries */
                 tag_info->tag = obj_addr;
 
-                /* Insert tag info into skip list */
-                if (H5SL_insert(cache_ptr->tag_list, tag_info, &(tag_info->tag)) < 0)
-                    HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, "can't insert tag info in skip list")
-            } /* end if */
+                /* Insert tag info into hash table */
+                HASH_ADD(hh, cache_ptr->tag_list, tag, sizeof(haddr_t), tag_info);
+            }
             else {
                 /* Check for object already corked */
                 if (tag_info->corked)
                     HGOTO_ERROR(H5E_CACHE, H5E_CANTCORK, FAIL, "object already corked")
                 HDassert(tag_info->entry_cnt > 0 && tag_info->head);
-            } /* end else */
+            }
 
             /* Set the corked status for the entire object */
             tag_info->corked = TRUE;
             cache_ptr->num_objs_corked++;
-
-        } /* end if */
+        }
         else {
             /* Sanity check */
-            HDassert(tag_info);
+            if (NULL == tag_info)
+                HGOTO_ERROR(H5E_CACHE, H5E_CANTUNCORK, FAIL, "tag info pointer is NULL")
 
             /* Check for already uncorked */
             if (!tag_info->corked)
@@ -8172,16 +8139,15 @@ H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked)
                 /* Sanity check */
                 HDassert(NULL == tag_info->head);
 
-                if (H5SL_remove(cache_ptr->tag_list, &(tag_info->tag)) != tag_info)
-                    HGOTO_ERROR(H5E_CACHE, H5E_CANTREMOVE, FAIL, "can't remove tag info from list")
+                HASH_DELETE(hh, cache_ptr->tag_list, tag_info);
 
                 /* Release the tag info */
                 tag_info = H5FL_FREE(H5C_tag_info_t, tag_info);
-            } /* end if */
+            }
             else
                 HDassert(NULL != tag_info->head);
-        } /* end else */
-    }     /* end else */
+        }
+    }
 
 done:
     FUNC_LEAVE_NOAPI(ret_value)
diff --git a/src/H5Cpkg.h b/src/H5Cpkg.h
index 61c3afc..5caa051 100644
--- a/src/H5Cpkg.h
+++ b/src/H5Cpkg.h
@@ -3566,15 +3566,17 @@ if ( ( (entry_ptr) == NULL ) ||                                                \
  *
  * The fields of this structure are discussed individually below:
  *
- * tag:    Address (i.e. "tag") of the object header for all the entries
+ * tag:         Address (i.e. "tag") of the object header for all the entries
  *              corresponding to parts of that object.
  *
- * head: Head of doubly-linked list of all entries belonging to the tag.
+ * head:        Head of doubly-linked list of all entries belonging to the tag.
  *
- * entry_cnt: Number of entries on linked list of entries for this tag.
+ * entry_cnt:   Number of entries on linked list of entries for this tag.
  *
- * corked: Boolean flag indicating whether entries for this object can be
- *         evicted.
+ * corked:      Boolean flag indicating whether entries for this object can be
+ *              evicted.
+ *
+ * hh:          uthash hash table handle (must be last)
  *
  ****************************************************************************/
 typedef struct H5C_tag_info_t {
@@ -3582,6 +3584,9 @@ typedef struct H5C_tag_info_t {
     H5C_cache_entry_t *head;    /* Head of the list of entries for this tag */
     size_t entry_cnt;           /* Number of entries on list */
     hbool_t corked;             /* Whether this object is corked */
+
+    /* Hash table fields */
+    UT_hash_handle hh; /* Hash table handle (must be LAST) */
 } H5C_tag_info_t;
 
 
@@ -3974,17 +3979,17 @@ typedef struct H5C_tag_info_t {
  *
  * The following fields are maintained to facilitate this.
  *
- * tag_list: A skip list to track entries that belong to an object.
- *                Each H5C_tag_info_t struct on the tag list corresponds to
- *                a particular object in the file.  Tagged entries can be
- *                flushed or evicted as a group, or corked to prevent entries
- *                from being evicted from the cache.
+ * tag_list:        A collection to track entries that belong to an object.
+ *                  Each H5C_tag_info_t struct on the tag list corresponds to
+ *                  a particular object in the file.  Tagged entries can be
+ *                  flushed or evicted as a group, or corked to prevent entries
+ *                  from being evicted from the cache.
  *
- *                "Global" entries, like the superblock and the file's
- *                freelist, as well as shared entries like global
- *                heaps and shared object header messages, are not tagged.
+ *                  "Global" entries, like the superblock and the file's
+ *                  freelist, as well as shared entries like global
+ *                  heaps and shared object header messages, are not tagged.
  *
- * ignore_tags:    Boolean flag to disable tag validation during entry insertion.
+ * ignore_tags:     Boolean flag to disable tag validation during entry insertion.
  *
  * num_objs_corked: Unsigned integer field containing the number of objects
  *                  that are "corked".  The "corked" status of an object is
@@ -4863,7 +4868,7 @@ struct H5C_t {
 #endif /* H5C_DO_SANITY_CHECKS */
 
     /* Fields for maintaining list of tagged entries */
-    H5SL_t *                    tag_list;
+    H5C_tag_info_t *            tag_list;
     hbool_t                     ignore_tags;
     uint32_t                    num_objs_corked;
 
diff --git a/src/H5Ctag.c b/src/H5Ctag.c
index 92f7dcd..08141a8 100644
--- a/src/H5Ctag.c
+++ b/src/H5Ctag.c
@@ -82,7 +82,7 @@ typedef struct {
 /********************/
 /* Local Prototypes */
 /********************/
-static herr_t H5C__mark_tagged_entries(H5C_t *cache_ptr, haddr_t tag);
+static herr_t H5C__mark_tagged_entries(H5C_t *cache, haddr_t tag);
 
 /*********************/
 /* Package Variables */
@@ -122,16 +122,16 @@ H5FL_EXTERN(H5C_tag_info_t);
  *-------------------------------------------------------------------------
  */
 herr_t
-H5C_ignore_tags(H5C_t *cache_ptr)
+H5C_ignore_tags(H5C_t *cache)
 {
     FUNC_ENTER_NOAPI_NOERR
 
     /* Assertions */
-    HDassert(cache_ptr != NULL);
-    HDassert(cache_ptr->magic == H5C__H5C_T_MAGIC);
+    HDassert(cache != NULL);
+    HDassert(cache->magic == H5C__H5C_T_MAGIC);
 
     /* Set variable to ignore tag values upon assignment */
-    cache_ptr->ignore_tags = TRUE;
+    cache->ignore_tags = TRUE;
 
     FUNC_LEAVE_NOAPI(SUCCEED)
 } /* H5C_ignore_tags */
@@ -150,16 +150,16 @@ H5C_ignore_tags(H5C_t *cache_ptr)
  *-------------------------------------------------------------------------
  */
 hbool_t
-H5C_get_ignore_tags(const H5C_t *cache_ptr)
+H5C_get_ignore_tags(const H5C_t *cache)
 {
     FUNC_ENTER_NOAPI_NOERR
 
     /* Sanity checks */
-    HDassert(cache_ptr);
-    HDassert(cache_ptr->magic == H5C__H5C_T_MAGIC);
+    HDassert(cache);
+    HDassert(cache->magic == H5C__H5C_T_MAGIC);
 
     /* Return ignore tag value */
-    FUNC_LEAVE_NOAPI(cache_ptr->ignore_tags)
+    FUNC_LEAVE_NOAPI(cache->ignore_tags)
 } /* H5C_get_ignore_tags */
 
 /*-------------------------------------------------------------------------
@@ -175,16 +175,16 @@ H5C_get_ignore_tags(const H5C_t *cache_ptr)
  *-------------------------------------------------------------------------
  */
 uint32_t
-H5C_get_num_objs_corked(const H5C_t *cache_ptr)
+H5C_get_num_objs_corked(const H5C_t *cache)
 {
     FUNC_ENTER_NOAPI_NOERR
 
     /* Sanity checks */
-    HDassert(cache_ptr);
-    HDassert(cache_ptr->magic == H5C__H5C_T_MAGIC);
+    HDassert(cache);
+    HDassert(cache->magic == H5C__H5C_T_MAGIC);
 
     /* Return value for num_objs_corked */
-    FUNC_LEAVE_NOAPI(cache_ptr->num_objs_corked)
+    FUNC_LEAVE_NOAPI(cache->num_objs_corked)
 } /* H5C_get_num_objs_corked */
 
 /*-------------------------------------------------------------------------
@@ -230,17 +230,17 @@ H5C__tag_entry(H5C_t *cache, H5C_cache_entry_t *entry)
            additional checking for correctness. */
         if (!H5F_addr_defined(tag))
             tag = H5AC__IGNORE_TAG;
-    } /* end if */
+    }
 #if H5C_DO_TAGGING_SANITY_CHECKS
     else {
         /* Perform some sanity checks to ensure that a correct tag is being applied */
         if (H5C_verify_tag(entry->type->id, tag) < 0)
             HGOTO_ERROR(H5E_CACHE, H5E_CANTTAG, FAIL, "tag verification failed")
-    } /* end else */
+    }
 #endif
 
     /* Search the list of tagged object addresses in the cache */
-    tag_info = (H5C_tag_info_t *)H5SL_search(cache->tag_list, &tag);
+    HASH_FIND(hh, cache->tag_list, &tag, sizeof(haddr_t), tag_info);
 
     /* Check if this is the first entry for this tagged object */
     if (NULL == tag_info) {
@@ -251,10 +251,9 @@ H5C__tag_entry(H5C_t *cache, H5C_cache_entry_t *entry)
         /* Set the tag for all entries */
         tag_info->tag = tag;
 
-        /* Insert tag info into skip list */
-        if (H5SL_insert(cache->tag_list, tag_info, &(tag_info->tag)) < 0)
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, "can't insert tag info in skip list")
-    } /* end if */
+        /* Insert tag info into the hash table */
+        HASH_ADD(hh, cache->tag_list, tag, sizeof(haddr_t), tag_info);
+    }
     else
         HDassert(tag_info->corked || (tag_info->entry_cnt > 0 && tag_info->head));
 
@@ -295,7 +294,7 @@ H5C__untag_entry(H5C_t *cache, H5C_cache_entry_t *entry)
     H5C_tag_info_t *tag_info;            /* Points to a tag info struct */
     herr_t          ret_value = SUCCEED; /* Return value */
 
-    FUNC_ENTER_PACKAGE
+    FUNC_ENTER_PACKAGE_NOERR
 
     /* Assertions */
     HDassert(cache != NULL);
@@ -323,17 +322,14 @@ H5C__untag_entry(H5C_t *cache, H5C_cache_entry_t *entry)
             /* Sanity check */
             HDassert(NULL == tag_info->head);
 
-            if (H5SL_remove(cache->tag_list, &(tag_info->tag)) != tag_info)
-                HGOTO_ERROR(H5E_CACHE, H5E_CANTREMOVE, FAIL, "can't remove tag info from list")
-
             /* Release the tag info */
+            HASH_DELETE(hh, cache->tag_list, tag_info);
             tag_info = H5FL_FREE(H5C_tag_info_t, tag_info);
-        } /* end if */
+        }
         else
             HDassert(tag_info->corked || NULL != tag_info->head);
-    } /* end if */
+    }
 
-done:
     FUNC_LEAVE_NOAPI(ret_value)
 } /* H5C__untag_entry */
 
@@ -364,7 +360,7 @@ H5C__iter_tagged_entries_real(H5C_t *cache, haddr_t tag, H5C_tag_iter_cb_t cb, v
     HDassert(cache->magic == H5C__H5C_T_MAGIC);
 
     /* Search the list of tagged object addresses in the cache */
-    tag_info = (H5C_tag_info_t *)H5SL_search(cache->tag_list, &tag);
+    HASH_FIND(hh, cache->tag_list, &tag, sizeof(haddr_t), tag_info);
 
     /* If there's any entries for this tag, iterate over them */
     if (tag_info) {
@@ -387,8 +383,8 @@ H5C__iter_tagged_entries_real(H5C_t *cache, haddr_t tag, H5C_tag_iter_cb_t cb, v
 
             /* Advance to next entry */
             entry = next_entry;
-        } /* end while */
-    }     /* end if */
+        }
+    }
 
 done:
     FUNC_LEAVE_NOAPI(ret_value)
@@ -724,7 +720,7 @@ herr_t
 H5C_flush_tagged_entries(H5F_t *f, haddr_t tag)
 {
     /* Variable Declarations */
-    H5C_t *cache_ptr = NULL;
+    H5C_t *cache     = NULL;
     herr_t ret_value = SUCCEED;
 
     FUNC_ENTER_NOAPI(FAIL)
@@ -734,10 +730,10 @@ H5C_flush_tagged_entries(H5F_t *f, haddr_t tag)
     HDassert(f->shared);
 
     /* Get cache pointer */
-    cache_ptr = f->shared->cache;
+    cache = f->shared->cache;
 
     /* Mark all entries with specified tag */
-    if (H5C__mark_tagged_entries(cache_ptr, tag) < 0)
+    if (H5C__mark_tagged_entries(cache, tag) < 0)
         HGOTO_ERROR(H5E_CACHE, H5E_CANTFLUSH, FAIL, "Can't mark tagged entries")
 
     /* Flush all marked entries */
@@ -756,7 +752,7 @@ done:
  *              value specified by src_tag and changes it to the value
  *              specified by dest_tag.
  *
- * Return:      SUCCEED or FAIL.
+ * Return:      SUCCEED/FAIL
  *
  * Programmer:  Mike McGreevy
  *              March 17, 2010
@@ -766,27 +762,28 @@ done:
 herr_t
 H5C_retag_entries(H5C_t *cache, haddr_t src_tag, haddr_t dest_tag)
 {
-    H5C_tag_info_t *tag_info;            /* Points to a tag info struct */
-    herr_t          ret_value = SUCCEED; /* Return value */
+    H5C_tag_info_t *tag_info = NULL;
 
     /* Function enter macro */
-    FUNC_ENTER_NOAPI(FAIL)
+    FUNC_ENTER_NOAPI_NOERR
 
     /* Sanity check */
     HDassert(cache);
 
     /* Remove tag info from tag list */
-    if (NULL != (tag_info = (H5C_tag_info_t *)H5SL_remove(cache->tag_list, &src_tag))) {
+    HASH_FIND(hh, cache->tag_list, &src_tag, sizeof(haddr_t), tag_info);
+    if (NULL != tag_info) {
+        /* Remove info with old tag */
+        HASH_DELETE(hh, cache->tag_list, tag_info);
+
         /* Change to new tag */
         tag_info->tag = dest_tag;
 
-        /* Re-insert tag info into skip list */
-        if (H5SL_insert(cache->tag_list, tag_info, &(tag_info->tag)) < 0)
-            HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, "can't insert tag info in skip list")
-    } /* end if */
+        /* Re-insert tag info into tag list */
+        HASH_ADD(hh, cache->tag_list, tag, sizeof(haddr_t), tag_info);
+    }
 
-done:
-    FUNC_LEAVE_NOAPI(ret_value)
+    FUNC_LEAVE_NOAPI(SUCCEED)
 } /* H5C_retag_entries() */
 
 /*-------------------------------------------------------------------------
diff --git a/src/H5Ipkg.h b/src/H5Ipkg.h
index e93ec74..34e6174 100644
--- a/src/H5Ipkg.h
+++ b/src/H5Ipkg.h
@@ -29,15 +29,6 @@
 /* Get package's private header */
 #include "H5Iprivate.h"
 
-/* uthash is an external, header-only hash table implementation.
- *
- * We include the file directly in src/ and #define a few functions
- * to use our internal memory calls.
- */
-#define uthash_malloc(sz)    H5MM_malloc(sz)
-#define uthash_free(ptr, sz) H5MM_free(ptr) /* Ignoring sz is intentional */
-#include "uthash.h"
-
 /**************************/
 /* Package Private Macros */
 /**************************/
diff --git a/src/H5private.h b/src/H5private.h
index 415855a..53ed809 100644
--- a/src/H5private.h
+++ b/src/H5private.h
@@ -139,6 +139,15 @@
 #define R_OK 04
 #endif
 
+/* uthash is an external, header-only hash table implementation.
+ *
+ * We include the file directly in src/ and #define a few functions
+ * to use our internal memory calls.
+ */
+#define uthash_malloc(sz)    H5MM_malloc(sz)
+#define uthash_free(ptr, sz) H5MM_free(ptr) /* Ignoring sz is intentional */
+#include "uthash.h"
+
 /*
  * MPE Instrumentation support
  */