Hash table replacement for skip lists in ID code (#600)

* Committing clang-format changes

* Brings over hash table code from Bitbucket

* Can be switched between skip list and hash table implementation
  with H5_USE_ID_HASH_TABLE #define
* Not yet updated to use iterate-safe delete

* Fixes a warning and changes where the problematic test is
commented out.

* Adds mark-and-sweep flags and members

* Final fixes for hash table ID code

* Removes skip list ID code

* Committing clang-format changes

* Formatted source

* Adds a comment about the mark-and-sweep scheme.

Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>

1 files changed, 101 insertions, 55 deletions

diff --git a/src/H5Iint.c b/src/H5Iint.c
index 41c6316..164fafc 100644
--- a/src/H5Iint.c
+++ b/src/H5Iint.c
@@ -29,7 +29,6 @@
 #include "H5FLprivate.h" /* Free Lists                               */
 #include "H5Ipkg.h"      /* IDs                                      */
 #include "H5MMprivate.h" /* Memory management                        */
-#include "H5SLprivate.h" /* Skip Lists                               */
 #include "H5Tprivate.h"  /* Datatypes                                */
 #include "H5VLprivate.h" /* Virtual Object Layer                     */
 
@@ -75,7 +74,7 @@ typedef struct {
 /********************/
 
 static void * H5I__unwrap(void *object, H5I_type_t type);
-static htri_t H5I__clear_type_cb(void *_id, void *key, void *udata);
+static herr_t H5I__mark_node(void *_id, void *key, void *udata);
 static void * H5I__remove_common(H5I_type_info_t *type_info, hid_t id);
 static int    H5I__dec_ref(hid_t id, void **request);
 static int    H5I__dec_app_ref(hid_t id, void **request);
@@ -96,6 +95,9 @@ int              H5I_next_type_g = (int)H5I_NTYPES;
 /* Declare a free list to manage the H5I_id_info_t struct */
 H5FL_DEFINE_STATIC(H5I_id_info_t);
 
+/* Whether deletes are actually marks (for mark-and-sweep) */
+hbool_t H5I_marking_g = FALSE;
+
 /*****************************/
 /* Library Private Variables */
 /*****************************/
@@ -131,7 +133,7 @@ H5I_term_package(void)
 
         /* Count the number of types still in use */
         for (i = 0; i < H5I_next_type_g; i++)
-            if ((type_info = H5I_type_info_array_g[i]) && type_info->ids)
+            if ((type_info = H5I_type_info_array_g[i]) && type_info->hash_table)
                 in_use++;
 
         /* If no types are still being used then clean up */
@@ -139,7 +141,7 @@ H5I_term_package(void)
             for (i = 0; i < H5I_next_type_g; i++) {
                 type_info = H5I_type_info_array_g[i];
                 if (type_info) {
-                    HDassert(NULL == type_info->ids);
+                    HDassert(NULL == type_info->hash_table);
                     type_info                = H5MM_xfree(type_info);
                     H5I_type_info_array_g[i] = NULL;
                     in_use++;
@@ -196,8 +198,7 @@ H5I_register_type(const H5I_class_t *cls)
         type_info->id_count     = 0;
         type_info->nextid       = cls->reserved;
         type_info->last_id_info = NULL;
-        if (NULL == (type_info->ids = H5SL_create(H5SL_TYPE_HID, NULL)))
-            HGOTO_ERROR(H5E_ID, H5E_CANTCREATE, FAIL, "skip list creation failed")
+        type_info->hash_table   = NULL;
     }
 
     /* Increment the count of the times this type has been initialized */
@@ -205,13 +206,9 @@ H5I_register_type(const H5I_class_t *cls)
 
 done:
     /* Clean up on error */
-    if (ret_value < 0) {
-        if (type_info) {
-            if (type_info->ids)
-                H5SL_close(type_info->ids);
+    if (ret_value < 0)
+        if (type_info)
             H5MM_free(type_info);
-        }
-    }
 
     FUNC_LEAVE_NOAPI(ret_value)
 } /* end H5I_register_type() */
@@ -311,7 +308,9 @@ H5I__unwrap(void *object, H5I_type_t type)
 herr_t
 H5I_clear_type(H5I_type_t type, hbool_t force, hbool_t app_ref)
 {
-    H5I_clear_type_ud_t udata;               /* udata struct for callback */
+    H5I_clear_type_ud_t udata; /* udata struct for callback */
+    H5I_id_info_t *     item      = NULL;
+    H5I_id_info_t *     tmp       = NULL;
     herr_t              ret_value = SUCCEED; /* Return value */
 
     FUNC_ENTER_NOAPI(FAIL)
@@ -328,33 +327,57 @@ H5I_clear_type(H5I_type_t type, hbool_t force, hbool_t app_ref)
     udata.force   = force;
     udata.app_ref = app_ref;
 
-    /* Attempt to free all ids in the type */
-    if (H5SL_try_free_safe(udata.type_info->ids, H5I__clear_type_cb, &udata) < 0)
-        HGOTO_ERROR(H5E_ID, H5E_CANTDELETE, FAIL, "can't free ids in type")
+    /* Clearing a type is done in two phases (mark-and-sweep). This is because
+     * the type's free callback can free other IDs, potentially corrupting
+     * the data structure during the traversal.
+     */
+
+    /* Set marking flag */
+    H5I_marking_g = TRUE;
+
+    /* Mark nodes for deletion */
+    HASH_ITER(hh, udata.type_info->hash_table, item, tmp)
+    {
+        if (!item->marked)
+            if (H5I__mark_node((void *)item, NULL, (void *)&udata) < 0)
+                HGOTO_ERROR(H5E_ID, H5E_BADITER, FAIL, "iteration failed while clearing the ID type")
+    }
+
+    /* Unset marking flag */
+    H5I_marking_g = FALSE;
+
+    /* Perform sweep */
+    HASH_ITER(hh, udata.type_info->hash_table, item, tmp)
+    {
+        if (item->marked) {
+            HASH_DELETE(hh, udata.type_info->hash_table, item);
+            item = H5FL_FREE(H5I_id_info_t, item);
+        }
+    }
 
 done:
     FUNC_LEAVE_NOAPI(ret_value)
 } /* end H5I_clear_type() */
 
 /*-------------------------------------------------------------------------
- * Function:    H5I__clear_type_cb
+ * Function:    H5I__mark_node
  *
- * Purpose:     Attempts to free the specified ID, calling the free
- *              function for the object.
+ * Purpose:     Attempts to mark the node for freeing and calls the free
+ *              function for the object, if any
  *
- * Return:      TRUE/FALSE/FAIL
+ * Return:      SUCCEED/FAIL
  *
  * Programmer:  Neil Fortner
  *              Friday, July 10, 2015
  *
  *-------------------------------------------------------------------------
  */
-static htri_t
-H5I__clear_type_cb(void *_info, void H5_ATTR_UNUSED *key, void *_udata)
+static herr_t
+H5I__mark_node(void *_info, void H5_ATTR_UNUSED *key, void *_udata)
 {
-    H5I_id_info_t *      info      = (H5I_id_info_t *)_info;        /* Current ID info being worked with */
-    H5I_clear_type_ud_t *udata     = (H5I_clear_type_ud_t *)_udata; /* udata struct */
-    htri_t               ret_value = FALSE;                         /* Return value */
+    H5I_id_info_t *      info  = (H5I_id_info_t *)_info;        /* Current ID info being worked with */
+    H5I_clear_type_ud_t *udata = (H5I_clear_type_ud_t *)_udata; /* udata struct */
+    hbool_t              mark  = FALSE;
 
     FUNC_ENTER_STATIC_NOERR
 
@@ -383,12 +406,12 @@ H5I__clear_type_cb(void *_info, void H5_ATTR_UNUSED *key, void *_udata)
 #endif /* H5I_DEBUG */
 
                     /* Indicate node should be removed from list */
-                    ret_value = TRUE;
+                    mark = TRUE;
                 }
             }
             else {
                 /* Indicate node should be removed from list */
-                ret_value = TRUE;
+                mark = TRUE;
             }
         }
         else {
@@ -406,28 +429,28 @@ H5I__clear_type_cb(void *_info, void H5_ATTR_UNUSED *key, void *_udata)
 #endif /* H5I_DEBUG */
 
                     /* Indicate node should be removed from list */
-                    ret_value = TRUE;
+                    mark = TRUE;
                 }
             }
             else {
                 /* Indicate node should be removed from list */
-                ret_value = TRUE;
+                mark = TRUE;
             }
         }
         H5_GCC_DIAG_ON("cast-qual")
 
         /* Remove ID if requested */
-        if (ret_value) {
-            /* Free ID info */
-            info = H5FL_FREE(H5I_id_info_t, info);
+        if (mark) {
+            /* Mark ID for deletion */
+            info->marked = TRUE;
 
             /* Decrement the number of IDs in the type */
             udata->type_info->id_count--;
         }
     }
 
-    FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5I__clear_type_cb() */
+    FUNC_LEAVE_NOAPI(SUCCEED)
+} /* end H5I__mark_node() */
 
 /*-------------------------------------------------------------------------
  * Function:    H5I__destroy_type
@@ -471,9 +494,8 @@ H5I__destroy_type(H5I_type_t type)
         if (type_info->cls->flags & H5I_CLASS_IS_APPLICATION)
             type_info->cls = H5MM_xfree_const(type_info->cls);
 
-    if (H5SL_close(type_info->ids) < 0)
-        HGOTO_ERROR(H5E_ID, H5E_CANTCLOSEOBJ, FAIL, "can't close skip list")
-    type_info->ids = NULL;
+    HASH_CLEAR(hh, type_info->hash_table);
+    type_info->hash_table = NULL;
 
     type_info = H5MM_xfree(type_info);
 
@@ -531,10 +553,10 @@ H5I__register(H5I_type_t type, const void *object, hbool_t app_ref, H5I_future_r
     info->is_future  = (NULL != realize_cb);
     info->realize_cb = realize_cb;
     info->discard_cb = discard_cb;
+    info->marked     = FALSE;
 
     /* Insert into the type */
-    if (H5SL_insert(type_info->ids, info, &info->id) < 0)
-        HGOTO_ERROR(H5E_ID, H5E_CANTINSERT, H5I_INVALID_HID, "can't insert ID node into skip list")
+    HASH_ADD(hh, type_info->hash_table, id, sizeof(hid_t), info);
     type_info->id_count++;
     type_info->nextid++;
 
@@ -643,10 +665,10 @@ H5I_register_using_existing_id(H5I_type_t type, void *object, hbool_t app_ref, h
     info->is_future  = FALSE;
     info->realize_cb = NULL;
     info->discard_cb = NULL;
+    info->marked     = FALSE;
 
     /* Insert into the type */
-    if (H5SL_insert(type_info->ids, info, &info->id) < 0)
-        HGOTO_ERROR(H5E_ID, H5E_CANTINSERT, FAIL, "can't insert ID node into skip list")
+    HASH_ADD(hh, type_info->hash_table, id, sizeof(hid_t), info);
     type_info->id_count++;
 
     /* Set the most recent ID to this object */
@@ -900,9 +922,17 @@ H5I__remove_common(H5I_type_info_t *type_info, hid_t id)
     /* Sanity check */
     HDassert(type_info);
 
-    /* Get the ID node for the ID */
-    if (NULL == (info = (H5I_id_info_t *)H5SL_remove(type_info->ids, &id)))
-        HGOTO_ERROR(H5E_ID, H5E_CANTDELETE, NULL, "can't remove ID node from skip list")
+    /* Delete or mark the node */
+    HASH_FIND(hh, type_info->hash_table, &id, sizeof(hid_t), info);
+    if (info) {
+        HDassert(!info->marked);
+        if (!H5I_marking_g)
+            HASH_DELETE(hh, type_info->hash_table, info);
+        else
+            info->marked = TRUE;
+    }
+    else
+        HGOTO_ERROR(H5E_ID, H5E_CANTDELETE, NULL, "can't remove ID node from hash table")
 
     /* Check if this ID was the last one accessed */
     if (type_info->last_id_info == info)
@@ -912,7 +942,8 @@ H5I__remove_common(H5I_type_info_t *type_info, hid_t id)
     ret_value = (void *)info->object; /* (Casting away const OK -QAK) */
     H5_GCC_DIAG_ON("cast-qual")
 
-    info = H5FL_FREE(H5I_id_info_t, info);
+    if (!H5I_marking_g)
+        info = H5FL_FREE(H5I_id_info_t, info);
 
     /* Decrement the number of IDs in the type */
     (type_info->id_count)--;
@@ -1555,8 +1586,9 @@ H5I_iterate(H5I_type_t type, H5I_search_func_t func, void *udata, hbool_t app_re
 
     /* Only iterate through ID list if it is initialized and there are IDs in type */
     if (type_info && type_info->init_count > 0 && type_info->id_count > 0) {
-        H5I_iterate_ud_t iter_udata;  /* User data for iteration callback */
-        herr_t           iter_status; /* Iteration status */
+        H5I_iterate_ud_t iter_udata; /* User data for iteration callback */
+        H5I_id_info_t *  item = NULL;
+        H5I_id_info_t *  tmp  = NULL;
 
         /* Set up iterator user data */
         iter_udata.user_func  = func;
@@ -1565,8 +1597,16 @@ H5I_iterate(H5I_type_t type, H5I_search_func_t func, void *udata, hbool_t app_re
         iter_udata.obj_type   = type;
 
         /* Iterate over IDs */
-        if ((iter_status = H5SL_iterate(type_info->ids, H5I__iterate_cb, &iter_udata)) < 0)
-            HGOTO_ERROR(H5E_ID, H5E_BADITER, FAIL, "iteration failed")
+        HASH_ITER(hh, type_info->hash_table, item, tmp)
+        {
+            if (!item->marked) {
+                int ret = H5I__iterate_cb((void *)item, NULL, (void *)&iter_udata);
+                if (H5_ITER_ERROR == ret)
+                    HGOTO_ERROR(H5E_ID, H5E_BADITER, FAIL, "iteration failed")
+                if (H5_ITER_STOP == ret)
+                    break;
+            }
+        }
     }
 
 done:
@@ -1607,8 +1647,7 @@ H5I__find_id(hid_t id)
     if (type_info->last_id_info && type_info->last_id_info->id == id)
         id_info = type_info->last_id_info;
     else {
-        /* Locate the ID node for the ID */
-        id_info = (H5I_id_info_t *)H5SL_search(type_info->ids, &id);
+        HASH_FIND(hh, type_info->hash_table, &id, sizeof(hid_t), id_info);
 
         /* Remember this ID */
         type_info->last_id_info = id_info;
@@ -1724,8 +1763,9 @@ H5I_find_id(const void *object, H5I_type_t type, hid_t *id)
 
     /* Only iterate through ID list if it is initialized and there are IDs in type */
     if (type_info->init_count > 0 && type_info->id_count > 0) {
-        H5I_get_id_ud_t udata;       /* User data */
-        herr_t          iter_status; /* Iteration status */
+        H5I_get_id_ud_t udata; /* User data */
+        H5I_id_info_t * item = NULL;
+        H5I_id_info_t * tmp  = NULL;
 
         /* Set up iterator user data */
         udata.object   = object;
@@ -1733,8 +1773,14 @@ H5I_find_id(const void *object, H5I_type_t type, hid_t *id)
         udata.ret_id   = H5I_INVALID_HID;
 
         /* Iterate over IDs for the ID type */
-        if ((iter_status = H5SL_iterate(type_info->ids, H5I__find_id_cb, &udata)) < 0)
-            HGOTO_ERROR(H5E_ID, H5E_BADITER, FAIL, "iteration failed")
+        HASH_ITER(hh, type_info->hash_table, item, tmp)
+        {
+            int ret = H5I__find_id_cb((void *)item, NULL, (void *)&udata);
+            if (H5_ITER_ERROR == ret)
+                HGOTO_ERROR(H5E_ID, H5E_BADITER, FAIL, "iteration failed")
+            if (H5_ITER_STOP == ret)
+                break;
+        }
 
         *id = udata.ret_id;
     }