Brings hash table IDs to 1.12 from develop (#638)

* Brings hash table IDs from develop

* Fixes free callback in tid.c

1 files changed, 108 insertions, 58 deletions

diff --git a/src/H5Iint.c b/src/H5Iint.c
index f0d6120..e512d4b 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__find_id_cb(void *_item, void *_key, void *_udata);
 
@@ -93,6 +92,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 */
 /*****************************/
@@ -128,7 +130,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 */
@@ -136,7 +138,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++;
@@ -193,8 +195,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_ATOM, H5E_CANTCREATE, FAIL, "skip list creation failed")
+        type_info->hash_table   = NULL;
     }
 
     /* Increment the count of the times this type has been initialized */
@@ -202,13 +203,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() */
@@ -308,7 +305,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)
@@ -325,33 +324,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_ATOM, 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_ATOM, 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
 
@@ -367,7 +390,7 @@ H5I__clear_type_cb(void *_info, void H5_ATTR_UNUSED *key, void *_udata)
         /* Check for a 'free' function and call it, if it exists */
         H5_GCC_DIAG_OFF("cast-qual")
         if (udata->type_info->cls->free_func &&
-            (udata->type_info->cls->free_func)((void *)info->object) < 0) { /* (Casting away const OK -QAK) */
+            (udata->type_info->cls->free_func)((void *)info->object) < 0) {
             if (udata->force) {
 #ifdef H5I_DEBUG
                 if (H5DEBUG(I)) {
@@ -379,27 +402,27 @@ 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
@@ -443,9 +466,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_ATOM, 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);
 
@@ -487,7 +509,7 @@ H5I_register(H5I_type_t type, const void *object, hbool_t app_ref)
     type_info = H5I_type_info_array_g[type];
     if ((NULL == type_info) || (type_info->init_count <= 0))
         HGOTO_ERROR(H5E_ATOM, H5E_BADGROUP, H5I_INVALID_HID, "invalid type")
-    if (NULL == (info = H5FL_MALLOC(H5I_id_info_t)))
+    if (NULL == (info = H5FL_CALLOC(H5I_id_info_t)))
         HGOTO_ERROR(H5E_ATOM, H5E_NOSPACE, H5I_INVALID_HID, "memory allocation failed")
 
     /* Create the struct & its ID */
@@ -496,10 +518,10 @@ H5I_register(H5I_type_t type, const void *object, hbool_t app_ref)
     info->count     = 1; /* initial reference count */
     info->app_count = !!app_ref;
     info->object    = object;
+    info->marked    = FALSE;
 
     /* Insert into the type */
-    if (H5SL_insert(type_info->ids, info, &info->id) < 0)
-        HGOTO_ERROR(H5E_ATOM, 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++;
 
@@ -565,7 +587,7 @@ H5I_register_using_existing_id(H5I_type_t type, void *object, hbool_t app_ref, h
         HGOTO_ERROR(H5E_ATOM, H5E_BADRANGE, FAIL, "invalid type for provided ID")
 
     /* Allocate new structure to house this ID */
-    if (NULL == (info = H5FL_MALLOC(H5I_id_info_t)))
+    if (NULL == (info = H5FL_CALLOC(H5I_id_info_t)))
         HGOTO_ERROR(H5E_ATOM, H5E_NOSPACE, FAIL, "memory allocation failed")
 
     /* Create the struct & insert requested ID */
@@ -573,10 +595,10 @@ H5I_register_using_existing_id(H5I_type_t type, void *object, hbool_t app_ref, h
     info->count     = 1; /* initial reference count*/
     info->app_count = !!app_ref;
     info->object    = object;
+    info->marked    = FALSE;
 
     /* Insert into the type */
-    if (H5SL_insert(type_info->ids, info, &info->id) < 0)
-        HGOTO_ERROR(H5E_ATOM, 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 */
@@ -830,9 +852,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_ATOM, 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_ATOM, 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)
@@ -842,7 +872,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)--;
@@ -1324,8 +1355,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;
@@ -1334,8 +1366,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_ATOM, 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_ATOM, H5E_BADITER, FAIL, "iteration failed")
+                if (H5_ITER_STOP == ret)
+                    break;
+            }
+        }
     }
 
 done:
@@ -1359,6 +1399,7 @@ H5I__find_id(hid_t id)
 {
     H5I_type_t       type;             /* ID's type */
     H5I_type_info_t *type_info = NULL; /* Pointer to the type */
+    H5I_id_info_t *  id_info   = NULL; /* ID's info */
     H5I_id_info_t *  ret_value = NULL; /* Return value */
 
     FUNC_ENTER_PACKAGE_NOERR
@@ -1373,15 +1414,17 @@ H5I__find_id(hid_t id)
 
     /* Check for same ID as we have looked up last time */
     if (type_info->last_id_info && type_info->last_id_info->id == id)
-        ret_value = type_info->last_id_info;
+        id_info = type_info->last_id_info;
     else {
-        /* Locate the ID node for the ID */
-        ret_value = (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 = ret_value;
+        type_info->last_id_info = id_info;
     }
 
+    /* Set return value */
+    ret_value = id_info;
+
 done:
     FUNC_LEAVE_NOAPI(ret_value)
 } /* end H5I__find_id() */
@@ -1454,8 +1497,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;
@@ -1463,8 +1507,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_ATOM, 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_ATOM, H5E_BADITER, FAIL, "iteration failed")
+            if (H5_ITER_STOP == ret)
+                break;
+        }
 
         *id = udata.ret_id;
     }