summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDana Robinson <derobins@hdfgroup.org>2015-09-12 15:26:07 (GMT)
committerDana Robinson <derobins@hdfgroup.org>2015-09-12 15:26:07 (GMT)
commit806a3bfa7357d314d9736740c059deb5a89cad20 (patch)
treea4c78f47d568b3831057bc65a14661727fc5360a
parent801f6a504c1092aa7abb12983ee56a783759ae68 (diff)
downloadhdf5-806a3bfa7357d314d9736740c059deb5a89cad20.zip
hdf5-806a3bfa7357d314d9736740c059deb5a89cad20.tar.gz
hdf5-806a3bfa7357d314d9736740c059deb5a89cad20.tar.bz2
[svn-r27764] Merges r27415 from trunk:
Fix potential error with H5I_clear_type which could occur when a callback closed a different ID in the same type. Added a new skiplist routine, H5SL_try_free_safe, which iterates over items, freeing some of them, and which intercepts and defers attempts to remove from the list outside of the main iteration. Changed H5I_clear_type to use this function. Tested on: ostrich and koala (h5committest)
-rw-r--r--src/H5I.c138
-rw-r--r--src/H5SL.c606
-rw-r--r--src/H5SLprivate.h6
-rw-r--r--test/tid.c199
-rw-r--r--test/tskiplist.c203
5 files changed, 935 insertions, 217 deletions
diff --git a/src/H5I.c b/src/H5I.c
index 5547f12..dbb4abf 100644
--- a/src/H5I.c
+++ b/src/H5I.c
@@ -99,6 +99,13 @@ typedef struct {
hbool_t app_ref; /* Whether this is an appl. ref. call */
} H5I_iterate_ud_t;
+/* User data for H5I__clear_type_cb */
+typedef struct {
+ H5I_id_type_t *type_ptr; /* Pointer to the type being cleard */
+ hbool_t force; /* Whether to always remove the id */
+ hbool_t app_ref; /* Whether this is an appl. ref. call */
+} H5I_clear_type_ud_t;
+
/*-------------------- Locally scoped variables -----------------------------*/
/* Array of pointers to atomic types */
@@ -122,6 +129,7 @@ H5FL_DEFINE_STATIC(H5I_id_type_t);
H5FL_DEFINE_STATIC(H5I_class_t);
/*--------------------- Local function prototypes ---------------------------*/
+static htri_t H5I__clear_type_cb(void *_id, void *key, void *udata);
static int H5I__destroy_type(H5I_type_t type);
static void *H5I__remove_verify(hid_t id, H5I_type_t id_type);
static void *H5I__remove_common(H5I_id_type_t *type_ptr, hid_t id);
@@ -528,80 +536,98 @@ done:
herr_t
H5I_clear_type(H5I_type_t type, hbool_t force, hbool_t app_ref)
{
- H5I_id_type_t *type_ptr; /* ptr to the atomic type */
- H5SL_node_t *curr_node; /* Current skip list node ptr */
- H5SL_node_t *next_node; /* Next skip list node ptr */
- int ret_value = SUCCEED; /* Return value */
+ H5I_clear_type_ud_t udata; /* udata struct for callback */
+ int ret_value = SUCCEED; /* Return value */
FUNC_ENTER_NOAPI(FAIL)
if(type <= H5I_BADID || type >= H5I_next_type)
- HGOTO_ERROR(H5E_ARGS, H5E_BADRANGE, FAIL, "invalid type number")
+ HGOTO_ERROR(H5E_ARGS, H5E_BADRANGE, FAIL, "invalid type number")
- type_ptr = H5I_id_type_list_g[type];
- if(type_ptr == NULL || type_ptr->init_count <= 0)
- HGOTO_ERROR(H5E_ATOM, H5E_BADGROUP, FAIL, "invalid type")
+ udata.type_ptr = H5I_id_type_list_g[type];
+ if(udata.type_ptr == NULL || udata.type_ptr->init_count <= 0)
+ HGOTO_ERROR(H5E_ATOM, H5E_BADGROUP, FAIL, "invalid type")
- /*
- * Call free method for all objects in type regardless of their reference
- * counts. Ignore the return value from from the free method and remove
- * object from type regardless if FORCE is non-zero.
- */
- for(curr_node = H5SL_first(type_ptr->ids); curr_node; curr_node = next_node) {
- H5I_id_info_t *cur; /* Current ID being worked with */
- hbool_t delete_node; /* Flag to indicate node should be removed from linked list */
+ /* Finish constructing udata */
+ udata.force = force;
+ udata.app_ref = app_ref;
- /* Get ID for this node */
- if(NULL == (cur = (H5I_id_info_t *)H5SL_item(curr_node)))
- HGOTO_ERROR(H5E_ATOM, H5E_CANTGET, FAIL, "can't get ID info for node")
+ /* Attempt to free all ids in the type */
+ if(H5SL_try_free_safe(udata.type_ptr->ids, H5I__clear_type_cb, &udata) < 0)
+ HGOTO_ERROR(H5E_ATOM, H5E_CANTDELETE, FAIL, "can't free ids in type")
- /*
- * Do nothing to the object if the reference count is larger than
- * one and forcing is off.
- */
- if(!force && (cur->count - (!app_ref * cur->app_count)) > 1)
- delete_node = FALSE;
- else {
- /* Check for a 'free' function and call it, if it exists */
- /* (Casting away const OK -QAK) */
- if(type_ptr->cls->free_func && (type_ptr->cls->free_func)((void *)cur->obj_ptr) < 0) {
- if(force) {
+done:
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5I_clear_type() */
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5I__clear_type_cb
+ *
+ * Purpose: Attempts to free the specified ID , calling the free
+ * function for the object.
+ *
+ * Return: Success: Non-negative
+ * Failure: negative
+ *
+ * Programmer: Neil Fortner
+ * Friday, July 10, 2015
+ *
+ *-------------------------------------------------------------------------
+ */
+static htri_t
+H5I__clear_type_cb(void *_id, void H5_ATTR_UNUSED *key, void *_udata)
+{
+ H5I_id_info_t *id = (H5I_id_info_t *)_id; /* Current ID being worked with */
+ H5I_clear_type_ud_t *udata = (H5I_clear_type_ud_t *)_udata; /* udata struct */
+ htri_t ret_value = FALSE; /* Return value */
+
+ FUNC_ENTER_STATIC_NOERR
+
+ HDassert(id);
+ HDassert(udata);
+ HDassert(udata->type_ptr);
+
+ /*
+ * Do nothing to the object if the reference count is larger than
+ * one and forcing is off.
+ */
+ if(udata->force || (id->count - (!udata->app_ref * id->app_count)) <= 1) {
+ /* Check for a 'free' function and call it, if it exists */
+ /* (Casting away const OK -QAK) */
+ if(udata->type_ptr->cls->free_func && (udata->type_ptr->cls->free_func)((void *)id->obj_ptr) < 0) {
+ if(udata->force) {
#ifdef H5I_DEBUG
- if(H5DEBUG(I)) {
- fprintf(H5DEBUG(I), "H5I: free type=%d obj=0x%08lx "
- "failure ignored\n", (int)type,
- (unsigned long)(cur->obj_ptr));
- } /* end if */
+ if(H5DEBUG(I)) {
+ fprintf(H5DEBUG(I), "H5I: free type=%d obj=0x%08lx "
+ "failure ignored\n",
+ (int)udata->type_ptr->cls->type_id,
+ (unsigned long)(id->obj_ptr));
+ } /* end if */
#endif /*H5I_DEBUG*/
- /* Indicate node should be removed from list */
- delete_node = TRUE;
- } /* end if */
- else {
- /* Indicate node should _NOT_ be remove from list */
- delete_node = FALSE;
- } /* end else */
- } /* end if */
- else {
/* Indicate node should be removed from list */
- delete_node = TRUE;
- } /* end else */
+ ret_value = TRUE;
+ } /* end if */
+ } /* end if */
+ else {
+ /* Indicate node should be removed from list */
+ ret_value = TRUE;
} /* end else */
- /* Get the next node in the list */
- next_node = H5SL_next(curr_node);
+ /* Remove ID if requested */
+ if(ret_value) {
+ /* Free ID info */
+ id = H5FL_FREE(H5I_id_info_t, id);
- /* Check if we should delete this node or not */
- if(delete_node) {
- /* Remove the node from the type */
- if(NULL == H5I__remove_common(type_ptr, cur->id))
- HGOTO_ERROR(H5E_ATOM, H5E_CANTDELETE, FAIL, "can't remove ID node")
+ /* Decrement the number of IDs in the type */
+ udata->type_ptr->id_count--;
} /* end if */
- } /* end for */
+ } /* end if */
+
-done:
FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5I_clear_type() */
+} /* end H5I__clear_type_cb() */
/*-------------------------------------------------------------------------
diff --git a/src/H5SL.c b/src/H5SL.c
index 2e72819..d766066 100644
--- a/src/H5SL.c
+++ b/src/H5SL.c
@@ -74,11 +74,26 @@
/* Define the code template for searches for the "OP" in the H5SL_LOCATE macro */
#define H5SL_LOCATE_SEARCH_FOUND(SLIST, X, I) \
- HGOTO_DONE(X->item);
+{ \
+ HDassert(!X->removed); \
+ HGOTO_DONE(X->item); \
+} /* end block */
+
+/* Define the code template for deferred removals for the "OP" in the
+ * H5SL_LOCATE macro */
+#define H5SL_LOCATE_SEARCH_DEFER_REMOVE_FOUND(SLIST, X, I) \
+{ \
+ HDassert(!X->removed); \
+ X->removed = TRUE; \
+ HGOTO_DONE(X->item); \
+} /* end block */
/* Define the code template for finds for the "OP" in the H5SL_LOCATE macro */
#define H5SL_LOCATE_FIND_FOUND(SLIST, X, I) \
- HGOTO_DONE(X);
+{ \
+ HDassert(!X->removed); \
+ HGOTO_DONE(X); \
+} /* end block */
/* Define a code template for comparing scalar keys for the "CMP" in the H5SL_LOCATE macro */
@@ -133,8 +148,8 @@
#define H5SL_LOCATE_GENERIC_HASHINIT(KEY, HASHVAL)
-/* Macro used to find node for operation */
-#define H5SL_LOCATE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
+/* Macro used to find node for operation, if all keys are valid */
+#define H5SL_LOCATE_OPT(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
{ \
int _i; /* Local index variable */ \
unsigned _count; /* Num nodes searched at this height */ \
@@ -150,15 +165,53 @@
} /* end for */ \
X = X->forward[0]; \
if(X != NULL && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, X, KEY, HASHVAL) ) { \
- /* What to do when a node is found */ \
+ /* What to do when a node is found */ \
H5_GLUE3(H5SL_LOCATE_,OP,_FOUND)(SLIST, X, _i) \
} /* end if */ \
}
+/* Macro used to find node for operation, if there may be "removed" nodes in the
+ * list (whose keys cannot be read) */
+#define H5SL_LOCATE_SAFE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
+{ \
+ int _i; /* Local index variable */ \
+ H5SL_node_t *_low = X; \
+ H5SL_node_t *_high = NULL; \
+ \
+ H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \
+ for(_i = (int)SLIST->curr_level; _i >= 0; _i--) { \
+ X = _low->forward[_i]; \
+ while(X != _high) { \
+ if(!X->removed) { \
+ if(H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X, KEY, HASHVAL)) \
+ _low = X; \
+ else \
+ break; \
+ } /* end if */ \
+ X = X->forward[_i]; \
+ } /* end while */ \
+ _high = X; \
+ if(X != NULL && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, X, KEY, HASHVAL) ) { \
+ /* What to do when a node is found */ \
+ H5_GLUE3(H5SL_LOCATE_,OP,_FOUND)(SLIST, X, _i) \
+ break; \
+ } /* end if */ \
+ } /* end for */ \
+}
+
+/* Macro used to find node for operation */
+#define H5SL_LOCATE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
+{ \
+ if((SLIST)->safe_iterating) \
+ H5SL_LOCATE_SAFE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
+ else \
+ H5SL_LOCATE_OPT(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
+}
+
/* Macro used to grow a node by 1. Does not update pointers. LVL is the current
* level of X. Does not update LVL but does update X->lvl. */
-#define H5SL_GROW(X, LVL) \
+#define H5SL_GROW(X, LVL, ERR) \
{ \
/* Check if we need to increase allocation of forward pointers */ \
if(LVL + 1 >= 1u << X->log_nalloc) { \
@@ -176,8 +229,10 @@
HDassert(H5SL_fac_nused_g == H5SL_fac_nalloc_g); \
/* Double the size of the array of factory pointers */ \
H5SL_fac_nalloc_g *= 2; \
- H5SL_fac_g = (H5FL_fac_head_t **)H5MM_realloc((void *)H5SL_fac_g, \
- H5SL_fac_nalloc_g * sizeof(H5FL_fac_head_t *)); \
+ if(NULL == (H5SL_fac_g = (H5FL_fac_head_t **)H5MM_realloc( \
+ (void *)H5SL_fac_g, H5SL_fac_nalloc_g \
+ * sizeof(H5FL_fac_head_t *)))) \
+ HGOTO_ERROR(H5E_SLIST, H5E_CANTALLOC, ERR, "memory allocation failed") \
} /* end if */ \
\
/* Create the new factory */ \
@@ -187,7 +242,7 @@
\
/* Allocate space for new forward pointers */ \
if(NULL == (_tmp = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[X->log_nalloc]))) \
- HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "memory allocation failed") \
+ HGOTO_ERROR(H5E_SLIST, H5E_CANTALLOC, ERR, "memory allocation failed") \
HDmemcpy((void *)_tmp, (const void *)X->forward, (LVL + 1) * sizeof(H5SL_node_t *)); \
X->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[X->log_nalloc-1], (void *)X->forward); \
X->forward = _tmp; \
@@ -222,16 +277,16 @@
/* Macro used to grow the level of a node by 1, with appropriate changes to the
* head node if necessary. PREV is the previous node of the height that X is to
* grow to. */
-#define H5SL_PROMOTE(SLIST, X, PREV) \
+#define H5SL_PROMOTE(SLIST, X, PREV, ERR) \
{ \
size_t _lvl = X->level; \
\
- H5SL_GROW(X, _lvl); \
+ H5SL_GROW(X, _lvl, ERR); \
\
if(_lvl == (size_t) SLIST->curr_level) { \
HDassert(PREV == SLIST->header); \
/* Grow the head */ \
- H5SL_GROW(PREV, _lvl); \
+ H5SL_GROW(PREV, _lvl, ERR) \
SLIST->curr_level++; \
X->forward[_lvl+1] = NULL; \
} else { \
@@ -298,7 +353,7 @@
/* Promote the middle node if necessary */ \
if(_count == 3) { \
HDassert(X == _last->forward[_i]->forward[_i]); \
- H5SL_PROMOTE(SLIST, X, _last) \
+ H5SL_PROMOTE(SLIST, X, _last, NULL) \
} \
\
/* Prepare to drop down */ \
@@ -314,161 +369,167 @@
/* Macro used to remove node */
#define H5SL_REMOVE(CMP, SLIST, X, TYPE, KEY, HASHVAL) \
{ \
- H5SL_node_t *_last = X; /* Lowest node in the current gap */ \
- H5SL_node_t *_llast = X; /* Lowest node in the previous gap */ \
- H5SL_node_t *_next = NULL; /* Highest node in the currect gap */ \
- H5SL_node_t *_drop = NULL; /* Low node of the gap to drop into */ \
- H5SL_node_t *_ldrop = NULL; /* Low node of gap before the one to drop into */ \
- H5SL_node_t *_head = SLIST->header; /* Head of the skip list */ \
- int _count; /* Number of nodes in the current gap */ \
- int _i = (int)SLIST->curr_level; \
+ /* Check for deferred removal */ \
+ if(SLIST->safe_iterating) \
+ H5SL_LOCATE(SEARCH_DEFER_REMOVE, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
+ else { \
+ H5SL_node_t *_last = X; /* Lowest node in the current gap */ \
+ H5SL_node_t *_llast = X; /* Lowest node in the previous gap */ \
+ H5SL_node_t *_next = NULL; /* Highest node in the currect gap */ \
+ H5SL_node_t *_drop = NULL; /* Low node of the gap to drop into */ \
+ H5SL_node_t *_ldrop = NULL; /* Low node of gap before the one to drop into */ \
+ H5SL_node_t *_head = SLIST->header; /* Head of the skip list */ \
+ int _count; /* Number of nodes in the current gap */ \
+ int _i = (int)SLIST->curr_level; \
\
- if(_i < 0) \
- HGOTO_DONE(NULL); \
+ if(_i < 0) \
+ HGOTO_DONE(NULL); \
\
- H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \
+ H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \
\
- /* Find the gap to drop in to at the highest level */ \
- while(X && (!X->key || H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X, KEY, HASHVAL))) { \
- _llast = _last; \
- _last = X; \
- X = X->forward[_i]; \
- } \
- _next = X; \
+ /* Find the gap to drop in to at the highest level */ \
+ while(X && (!X->key || H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X, KEY, HASHVAL))) { \
+ _llast = _last; \
+ _last = X; \
+ X = X->forward[_i]; \
+ } \
+ _next = X; \
\
- /* Main loop */ \
- for(_i--; _i >= 0; _i--) { \
- /* Search for the node to drop into, also count the number of nodes */ \
- /* of height _i in this gap and keep track of of the node before */ \
- /* the one to drop into (_ldrop will become _llast, _drop will */ \
- /* become _last). */ \
- X = _ldrop = _last; \
- _drop = NULL; \
- for(_count = 0; ; _count++) { \
- /* Terminate if this is the last node in the gap */ \
- if(X->forward[_i] == _next) { \
- if(!_drop) \
- _drop = X; \
- break; \
- } /* end if */ \
+ /* Main loop */ \
+ for(_i--; _i >= 0; _i--) { \
+ /* Search for the node to drop into, also count the number of */ \
+ /* nodes of height _i in this gap and keep track of of the node */ \
+ /* before the one to drop into (_ldrop will become _llast, */ \
+ /* _drop will become _last). */ \
+ X = _ldrop = _last; \
+ _drop = NULL; \
+ for(_count = 0; ; _count++) { \
+ /* Terminate if this is the last node in the gap */ \
+ if(X->forward[_i] == _next) { \
+ if(!_drop) \
+ _drop = X; \
+ break; \
+ } /* end if */ \
\
- /* If we have already found the node to drop into and there is */ \
- /* more than one node in this gap, we can stop searching */ \
- if(_drop) { \
- HDassert(_count >= 1); \
- _count = 2; \
- break; \
- } else { /* !_drop */ \
- /* Check if this node is the start of the next gap */ \
- if (!H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL)) { \
- _drop = X; \
- /* Again check if we can stop searching */ \
- if(_count) { \
- _count = 2; \
- break; \
+ /* If we have already found the node to drop into and there */ \
+ /* is more than one node in this gap, we can stop searching */ \
+ if(_drop) { \
+ HDassert(_count >= 1); \
+ _count = 2; \
+ break; \
+ } else { /* !_drop */ \
+ /* Check if this node is the start of the next gap */ \
+ if (!H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL)) { \
+ _drop = X; \
+ /* Again check if we can stop searching */ \
+ if(_count) { \
+ _count = 2; \
+ break; \
+ } /* end if */ \
} /* end if */ \
- } /* end if */ \
- else \
- _ldrop = X; \
- } /* end else */ \
+ else \
+ _ldrop = X; \
+ } /* end else */ \
\
- /* No need to check the last node in the gap if there are 3, as */ \
- /* there cannot be a fourth */ \
- if(_count == 2) { \
- if(!_drop) \
- _drop = X->forward[_i]; \
- break; \
- } /* end if */ \
- X = X->forward[_i]; \
- } /* end for */ \
- HDassert(_count >= 1 && _count <= 3); \
- HDassert(!_drop->forward[_i] || \
- !H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, _drop->forward[_i], KEY, HASHVAL)); \
+ /* No need to check the last node in the gap if there are */ \
+ /* 3, as there cannot be a fourth */ \
+ if(_count == 2) { \
+ if(!_drop) \
+ _drop = X->forward[_i]; \
+ break; \
+ } /* end if */ \
+ X = X->forward[_i]; \
+ } /* end for */ \
+ HDassert(_count >= 1 && _count <= 3); \
+ HDassert(!_drop->forward[_i] || \
+ !H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, _drop->forward[_i], KEY, HASHVAL)); \
\
- /* Check if we need to adjust node heights */ \
- if(_count == 1) { \
- /* Check if we are in the first gap */ \
- if(_llast == _last) { \
- /* We are in the first gap, count the number of nodes of */ \
- /* height _i in the next gap. We need only check one node */ \
- /* to see if we should promote the first node in the next */ \
- /* gap */ \
- _llast = _next->forward[_i+1]; \
+ /* Check if we need to adjust node heights */ \
+ if(_count == 1) { \
+ /* Check if we are in the first gap */ \
+ if(_llast == _last) { \
+ /* We are in the first gap, count the number of nodes */ \
+ /* of height _i in the next gap. We need only check */ \
+ /* onenode to see if we should promote the first node */ \
+ /* in the next gap */ \
+ _llast = _next->forward[_i+1]; \
\
- /* Demote the separator node */ \
- H5SL_DEMOTE(_next, _last) \
+ /* Demote the separator node */ \
+ H5SL_DEMOTE(_next, _last) \
\
- /* If there are 2 or more nodes, promote the first */ \
- if(_next->forward[_i]->forward[_i] != _llast) { \
- X = _next->forward[_i]; \
- H5SL_PROMOTE(SLIST, X, _last) \
- } else if(!_head->forward[_i+1]) { \
- /* shrink the header */ \
- HDassert(_i == SLIST->curr_level - 1); \
- HDassert((size_t) SLIST->curr_level == _head->level); \
+ /* If there are 2 or more nodes, promote the first */ \
+ if(_next->forward[_i]->forward[_i] != _llast) { \
+ X = _next->forward[_i]; \
+ H5SL_PROMOTE(SLIST, X, _last, NULL) \
+ } else if(!_head->forward[_i+1]) { \
+ /* shrink the header */ \
+ HDassert(_i == SLIST->curr_level - 1); \
+ HDassert((size_t) SLIST->curr_level == _head->level); \
\
- H5SL_SHRINK(_head, (size_t) (_i+1)) \
- SLIST->curr_level--; \
- } /* end else */ \
- } else { \
- /* We are not in the first gap, count the number of nodes */ \
- /* of height _i in the previous gap. Note we "look ahead" */ \
- /* in this loop so X has the value of the last node in the */ \
- /* previous gap. */ \
- X = _llast->forward[_i]; \
- for(_count = 1; _count < 3 && X->forward[_i] != _last; _count++) \
- X = X->forward[_i]; \
- HDassert(X->forward[_i] == _last); \
+ H5SL_SHRINK(_head, (size_t) (_i+1)) \
+ SLIST->curr_level--; \
+ } /* end else */ \
+ } else { \
+ /* We are not in the first gap, count the number of */ \
+ /* nodes of height _i in the previous gap. Note we */ \
+ /* "look ahead" in this loop so X has the value of the */ \
+ /* last node in the previous gap. */ \
+ X = _llast->forward[_i]; \
+ for(_count = 1; _count < 3 && X->forward[_i] != _last; _count++) \
+ X = X->forward[_i]; \
+ HDassert(X->forward[_i] == _last); \
\
- /* Demote the separator node */ \
- H5SL_DEMOTE(_last, _llast) \
+ /* Demote the separator node */ \
+ H5SL_DEMOTE(_last, _llast) \
\
- /* If there are 2 or more nodes, promote the last */ \
- if(_count >= 2) \
- H5SL_PROMOTE(SLIST, X, _llast) \
- else if(!_head->forward[_i+1]) { \
- /* shrink the header */ \
- HDassert(_i == SLIST->curr_level - 1); \
- HDassert((size_t) SLIST->curr_level == _head->level); \
+ /* If there are 2 or more nodes, promote the last */ \
+ if(_count >= 2) \
+ H5SL_PROMOTE(SLIST, X, _llast, NULL) \
+ else if(!_head->forward[_i+1]) { \
+ /* shrink the header */ \
+ HDassert(_i == SLIST->curr_level - 1); \
+ HDassert((size_t) SLIST->curr_level == _head->level); \
\
- H5SL_SHRINK(_head, (size_t) (_i+1)) \
- SLIST->curr_level--; \
+ H5SL_SHRINK(_head, (size_t) (_i+1)) \
+ SLIST->curr_level--; \
+ } /* end else */ \
} /* end else */ \
- } /* end else */ \
- } /* end if */ \
+ } /* end if */ \
\
- /* Prepare to drop down */ \
- _llast = _ldrop; \
- _last = _drop; \
- _next = _drop->forward[_i]; \
- } /* end for */ \
+ /* Prepare to drop down */ \
+ _llast = _ldrop; \
+ _last = _drop; \
+ _next = _drop->forward[_i]; \
+ } /* end for */ \
\
- /* Check if we've found the node */ \
- if(_next && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, _next, KEY, HASHVAL)) { \
- void *tmp = _next->item; \
- X = _next; \
+ /* Check if we've found the node */ \
+ if(_next && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, _next, KEY, HASHVAL)) { \
+ void *tmp = _next->item; \
+ X = _next; \
\
- /* If the node has a height > 0, swap it with its (lower) neighbor */ \
- if(X->level) { \
- X = X->backward; \
- _next->key = X->key; \
- _next->item = X->item; \
- _next->hashval = X->hashval; \
- } /* end if */ \
- HDassert(!X->level); \
+ /* If the node has a height > 0, swap it with its (lower) */ \
+ /* neighbor */ \
+ if(X->level) { \
+ X = X->backward; \
+ _next->key = X->key; \
+ _next->item = X->item; \
+ _next->hashval = X->hashval; \
+ } /* end if */ \
+ HDassert(!X->level); \
\
- /* Remove the node */ \
- X->backward->forward[0] = X->forward[0]; \
- if(SLIST->last == X) \
- SLIST->last = X->backward; \
- else \
- X->forward[0]->backward = X->backward; \
- SLIST->nobjs--; \
- X->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[0], X->forward); \
- X = H5FL_FREE(H5SL_node_t, X); \
+ /* Remove the node */ \
+ X->backward->forward[0] = X->forward[0]; \
+ if(SLIST->last == X) \
+ SLIST->last = X->backward; \
+ else \
+ X->forward[0]->backward = X->backward; \
+ SLIST->nobjs--; \
+ X->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[0], X->forward); \
+ X = H5FL_FREE(H5SL_node_t, X); \
\
- HGOTO_DONE(tmp); \
- } /* end if */ \
+ HGOTO_DONE(tmp); \
+ } /* end if */ \
+ } /* end else */ \
}
@@ -490,6 +551,7 @@ struct H5SL_node_t {
size_t level; /* The level of this node */
size_t log_nalloc; /* log2(Number of slots allocated in forward) */
uint32_t hashval; /* Hash value for key (only for strings, currently) */
+ hbool_t removed; /* Whether the node is "removed" (actual removal deferred) */
struct H5SL_node_t **forward; /* Array of forward pointers from this node */
struct H5SL_node_t *backward; /* Backward pointer from this node */
};
@@ -505,6 +567,7 @@ struct H5SL_t {
size_t nobjs; /* Number of active objects in skip list */
H5SL_node_t *header; /* Header for nodes in skip list */
H5SL_node_t *last; /* Pointer to last node in skip list */
+ hbool_t safe_iterating; /* Whether a routine is "safely" iterating over the list and removals should be deferred */
};
/* Static functions */
@@ -599,6 +662,7 @@ H5SL_new_node(void *item, const void *key, uint32_t hashval)
ret_value->item = item;
ret_value->level = 0;
ret_value->hashval = hashval;
+ ret_value->removed = FALSE;
if(NULL == (ret_value->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0]))) {
ret_value = H5FL_FREE(H5SL_node_t, ret_value);
HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "memory allocation failed")
@@ -712,7 +776,7 @@ H5SL_insert_common(H5SL_t *slist, void *item, const void *key)
if(x->forward[0])
x->forward[0]->backward = x;
else {
- HDassert(slist->last);
+ HDassert(slist->last == prev);
slist->last = x;
}
@@ -766,14 +830,14 @@ H5SL_release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data)
/* (Pre-condition) */
/* Free skip list nodes */
- node=slist->header->forward[0];
- while(node!=NULL) {
- next_node=node->forward[0];
+ node = slist->header->forward[0];
+ while(node) {
+ next_node = node->forward[0];
/* Call callback, if one is given */
- if(op!=NULL)
+ if(op)
/* Casting away const OK -QAK */
- (void)(op)(node->item,(void *)node->key,op_data);
+ (void)(op)(node->item, (void *)node->key, op_data);
node->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[node->log_nalloc], node->forward);
node = H5FL_FREE(H5SL_node_t, node);
@@ -782,18 +846,18 @@ H5SL_release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data)
/* Reset the header pointers */
slist->header->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[slist->header->log_nalloc], slist->header->forward);
- if(NULL == (slist->header->forward = (H5SL_node_t **) H5FL_FAC_MALLOC(H5SL_fac_g[0])))
+ if(NULL == (slist->header->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0])))
HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, FAIL, "memory allocation failed")
slist->header->forward[0] = NULL;
slist->header->log_nalloc = 0;
slist->header->level = 0;
/* Reset the last pointer */
- slist->last=slist->header;
+ slist->last = slist->header;
/* Reset the dynamic internal fields */
- slist->curr_level=-1;
- slist->nobjs=0;
+ slist->curr_level = -1;
+ slist->nobjs = 0;
done:
FUNC_LEAVE_NOAPI(ret_value)
@@ -893,6 +957,7 @@ H5SL_create(H5SL_type_t type, H5SL_cmp_t cmp)
/* Set the dynamic internal fields */
new_slist->curr_level = -1;
new_slist->nobjs = 0;
+ new_slist->safe_iterating = FALSE;
/* Allocate the header node */
if(NULL == (header = H5SL_new_node(NULL, NULL, (uint32_t)ULONG_MAX)))
@@ -948,6 +1013,9 @@ H5SL_count(H5SL_t *slist)
/* Check args */
HDassert(slist);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -987,6 +1055,9 @@ H5SL_insert(H5SL_t *slist, void *item, const void *key)
HDassert(slist);
HDassert(key);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1034,6 +1105,9 @@ H5SL_add(H5SL_t *slist, void *item, const void *key)
HDassert(slist);
HDassert(key);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1166,6 +1240,9 @@ H5SL_remove_first(H5SL_t *slist)
/* Check args */
HDassert(slist);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1211,7 +1288,7 @@ H5SL_remove_first(H5SL_t *slist)
HDassert(tmp->forward[i]->forward[i]->forward[i] == next ||
tmp->forward[i]->forward[i]->forward[i]->forward[i] == next);
tmp = tmp->forward[i];
- H5SL_PROMOTE(slist, tmp, head);
+ H5SL_PROMOTE(slist, tmp, head, NULL);
/* In this case, since there is a node of height = i+1 here
* now (tmp), we know the skip list must be valid and can
* break */
@@ -1358,6 +1435,9 @@ H5SL_less(H5SL_t *slist, const void *key)
HDassert(slist);
HDassert(key);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1464,6 +1544,9 @@ H5SL_greater(H5SL_t *slist, const void *key)
HDassert(slist);
HDassert(key);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1848,6 +1931,9 @@ H5SL_first(H5SL_t *slist)
/* Check args */
HDassert(slist);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1882,6 +1968,9 @@ H5SL_next(H5SL_node_t *slist_node)
/* Check args */
HDassert(slist_node);
+ /* Not currently supported */
+ HDassert(!slist_node->removed);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1916,6 +2005,9 @@ H5SL_prev(H5SL_node_t *slist_node)
/* Check args */
HDassert(slist_node);
+ /* Not currently supported */
+ HDassert(!slist_node->removed);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1951,6 +2043,9 @@ H5SL_last(H5SL_t *slist)
/* Check args */
HDassert(slist);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -1985,6 +2080,9 @@ H5SL_item(H5SL_node_t *slist_node)
/* Check args */
HDassert(slist_node);
+ /* Not currently supported */
+ HDassert(!slist_node->removed);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -2048,8 +2146,9 @@ H5SL_iterate(H5SL_t *slist, H5SL_operator_t op, void *op_data)
/* Call the iterator callback */
/* Casting away const OK -QAK */
- if((ret_value = (op)(node->item, (void *)node->key, op_data)) != 0)
- break;
+ if(!node->removed)
+ if((ret_value = (op)(node->item, (void *)node->key, op_data)) != 0)
+ break;
/* Advance to next node */
node = next;
@@ -2087,6 +2186,9 @@ H5SL_release(H5SL_t *slist)
/* Check args */
HDassert(slist);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -2133,6 +2235,9 @@ H5SL_free(H5SL_t *slist, H5SL_operator_t op, void *op_data)
/* Check args */
HDassert(slist);
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
/* Check internal consistency */
/* (Pre-condition) */
@@ -2145,6 +2250,185 @@ H5SL_free(H5SL_t *slist, H5SL_operator_t op, void *op_data)
/*--------------------------------------------------------------------------
NAME
+ H5SL_try_free_safe
+ PURPOSE
+ Makes the supplied callback on all nodes in the skip list, freeing each
+ node that the callback returns TRUE for.
+ USAGE
+ herr_t PURPOSE(slist,op,opdata)
+ H5SL_t *slist; IN/OUT: Pointer to skip list to release nodes
+ H5SL_try_free_op_t op; IN: Callback function to try to free item & key
+ void *op_data; IN/OUT: Pointer to application data for callback
+
+ RETURNS
+ Returns non-negative on success, negative on failure.
+ DESCRIPTION
+ Makes the supplied callback on all nodes in the skip list, freeing each
+ node that the callback returns TRUE for. The iteration is performed in
+ a safe manner, such that the callback can call H5SL_remove(),
+ H5SL_search(), H5SL_find(), and H5SL_iterate() on nodes in this
+ skiplist, except H5SL_remove() may not be call on *this* node.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ This function is written to be most efficient when most nodes are
+ removed from the skiplist, as it rebuilds the nodes afterwards.
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5SL_try_free_safe(H5SL_t *slist, H5SL_try_free_op_t op, void *op_data)
+{
+ H5SL_node_t *node, *next_node, *last_node; /* Pointers to skip list nodes */
+ htri_t op_ret;
+ herr_t ret_value = SUCCEED;
+
+ FUNC_ENTER_NOAPI_NOINIT
+
+ /* Check args */
+ HDassert(slist);
+ HDassert(op);
+
+ /* Not currently supported */
+ HDassert(!slist->safe_iterating);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Mark skip list as safe iterating, so nodes aren't freed out from under
+ * us */
+ slist->safe_iterating = TRUE;
+
+ /* Iterate over skip list nodes, making the callback for each and marking
+ * them as removed if requested by the callback */
+ node = slist->header->forward[0];
+ while(node) {
+ /* Check if the node was already removed */
+ if(!node->removed) {
+ /* Call callback */
+ /* Casting away const OK -NAF */
+ if((op_ret = (op)(node->item , (void *)node->key, op_data)) < 0)
+ HGOTO_ERROR(H5E_SLIST, H5E_CALLBACK, FAIL, "callback operation failed")
+
+ /* Check if op indicated that the node should be removed */
+ if(op_ret)
+ /* Mark the node as removed */
+ node->removed = TRUE;
+ } /* end if */
+
+ /* Advance node */
+ node = node->forward[0];
+ } /* end while */
+
+ /* Reset safe_iterating */
+ slist->safe_iterating = FALSE;
+
+ /* Iterate over nodes, freeing ones marked as removed */
+ node = slist->header->forward[0];
+ last_node = slist->header;
+ while(node) {
+ /* Save next node */
+ next_node = node->forward[0];
+
+ /* Check if the node was marked as removed */
+ if(node->removed) {
+ /* Remove the node */
+ node->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[node->log_nalloc], node->forward);
+ node = H5FL_FREE(H5SL_node_t, node);
+ slist->nobjs--;
+ } /* end if */
+ else {
+ /* Update backwards and forwards[0] pointers, and set the level to
+ * 0. Since the list is flattened we must rebuild the skiplist
+ * afterwards. */
+ /* Set level to 0. Note there is no need to preserve
+ * node->forward[0] since it was cached above and will always be
+ * updated later. */
+ if(node->level > 0) {
+ node->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[node->log_nalloc], (void *)node->forward);
+ if(NULL == (node->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0])))
+ HGOTO_ERROR(H5E_SLIST, H5E_CANTALLOC, FAIL, "memory allocation failed")
+ node->log_nalloc = 0;
+ node->level = 0;
+ } /* end if */
+
+ /* Update pointers */
+ last_node->forward[0] = node;
+ node->backward = last_node;
+ last_node = node;
+ } /* end else */
+
+ /* Advance node */
+ node = next_node;
+ } /* end while */
+
+ /* Final pointer update */
+ last_node->forward[0] = NULL;
+ slist->last = last_node;
+
+ /* Demote skip list to level 0 */
+ if(slist->curr_level > 0) {
+ HDassert(slist->header->level == (size_t)slist->curr_level);
+
+ node = slist->header->forward[0];
+ slist->header->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[slist->header->log_nalloc], (void *)slist->header->forward);
+ if(NULL == (slist->header->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0])))
+ HGOTO_ERROR(H5E_SLIST, H5E_CANTALLOC, FAIL, "memory allocation failed")
+ slist->header->forward[0] = node;
+ slist->header->log_nalloc = 0;
+ slist->header->level = 0;
+ } /* end if */
+
+ /* Check if there are any nodes left */
+ if(slist->nobjs > 0) {
+ int i;
+
+ HDassert(slist->header->forward[0]);
+
+ /* Set skiplist level to 0 */
+ slist->curr_level = 0;
+
+ /* Rebuild the forward arrays */
+ for(i = 0; slist->curr_level >= i; i++) {
+ HDassert(slist->curr_level == i);
+
+ /* Promote every third node this level until we run out of nodes */
+ node = last_node = slist->header;
+ while(1) {
+ /* Check second node in gap, if not present, no need to promote
+ * further this level. */
+ HDassert(node->forward[i]);
+ node = node->forward[i]->forward[i];
+ if(!node)
+ break;
+
+ /* Check third and fourth node in gap, if either is not present,
+ * no need to promote further this level. */
+ node = node->forward[i];
+ if(!node || !node->forward[i])
+ break;
+
+ /* Promote the third node in the gap */
+ H5SL_PROMOTE(slist, node, last_node, FAIL)
+ last_node = node;
+ } /* end while */
+ } /* end for */
+ } /* end if */
+ else {
+ HDassert(!slist->header->forward[0]);
+ HDassert(slist->last == slist->header);
+ HDassert(slist->nobjs == 0);
+
+ /* Reset the skiplist level */
+ slist->curr_level = -1;
+ } /* end else */
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* end H5SL_try_free_safe() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
H5SL_destroy
PURPOSE
Close a skip list, deallocating it and freeing all its nodes.
diff --git a/src/H5SLprivate.h b/src/H5SLprivate.h
index ce2f091..856099b 100644
--- a/src/H5SLprivate.h
+++ b/src/H5SLprivate.h
@@ -63,6 +63,10 @@ typedef int (*H5SL_cmp_t)(const void *key1, const void *key2);
typedef herr_t (*H5SL_operator_t)(void *item, void *key,
void *operator_data/*in,out*/);
+/* Typedef for H5SL_try_free_safe operation callback */
+typedef htri_t (*H5SL_try_free_op_t)(void *item, void *key,
+ void *operator_data/*in,out*/);
+
/********************/
/* Private routines */
/********************/
@@ -86,6 +90,8 @@ H5_DLL void *H5SL_item(H5SL_node_t *slist_node);
H5_DLL herr_t H5SL_iterate(H5SL_t *slist, H5SL_operator_t op, void *op_data);
H5_DLL herr_t H5SL_release(H5SL_t *slist);
H5_DLL herr_t H5SL_free(H5SL_t *slist, H5SL_operator_t op, void *op_data);
+H5_DLL herr_t H5SL_try_free_safe(H5SL_t *slist, H5SL_try_free_op_t op,
+ void *op_data);
H5_DLL herr_t H5SL_close(H5SL_t *slist);
H5_DLL herr_t H5SL_destroy(H5SL_t *slist, H5SL_operator_t op, void *op_data);
H5_DLL int H5SL_term_interface(void);
diff --git a/test/tid.c b/test/tid.c
index 85d26c9..68cebf3 100644
--- a/test/tid.c
+++ b/test/tid.c
@@ -533,12 +533,211 @@ out:
return -1;
}
+ /* Test removing ids in callback for H5Iclear_type */
+
+/* There was a rare bug where, if an id free callback being called by
+ * H5I_clear_type() removed another id in that type, a segfault could occur.
+ * This test tests for that error (and freeing ids "out of order" within
+ * H5Iclear_type() in general). */
+/* Macro definitions */
+#define TEST_RCT_MAX_NOBJS 25
+#define TEST_RCT_MIN_NOBJS 5
+#define TEST_RCT_NITER 50
+
+/* Structure to hold the list of objects */
+typedef struct {
+ struct test_rct_obj_t *list; /* List of objects */
+ long nobjs; /* Number of objects in list */
+ long nobjs_rem; /* Number of objects in list that have not been freed */
+} test_rct_list_t;
+
+/* Structure for an object */
+typedef struct test_rct_obj_t {
+ hid_t id; /* ID for this object */
+ int nfrees; /* Number of times this object has been freed */
+ hbool_t freeing; /* Whether we are currently freeing this object directly (through H5Idec_ref()) */
+ test_rct_list_t *obj_list; /* List of all objects */
+} test_rct_obj_t;
+
+/* Free callback */
+static herr_t test_rct_free(void *_obj) {
+ test_rct_obj_t *obj = (test_rct_obj_t *)_obj;
+ long rem_idx, i;
+ herr_t ret; /* return value */
+
+ /* Mark this object as freed */
+ obj->nfrees++;
+ obj->obj_list->nobjs_rem--;
+
+ /* Check freeing and nobjs_rem */
+ if(!obj->freeing && (obj->obj_list->nobjs_rem > 0)) {
+ /* Remove a random object from the list */
+ rem_idx = HDrandom() % obj->obj_list->nobjs_rem;
+
+ /* Scan the list, finding the rem_idx'th object that has not been
+ * freed */
+ for(i = 0; i < obj->obj_list->nobjs; i++)
+ if(obj->obj_list->list[i].nfrees == 0) {
+ if(rem_idx == 0)
+ break;
+ else
+ rem_idx--;
+ } /* end if */
+ if(i == obj->obj_list->nobjs) {
+ ERROR("invalid obj_list");
+ goto out;
+ } /* end if */
+ else {
+ /* Remove the object. Mark as "freeing" so its own callback does
+ * not free another object. */
+ obj->obj_list->list[i].freeing = TRUE;
+ ret = H5Idec_ref(obj->obj_list->list[i].id);
+ CHECK(ret, FAIL, "H5Idec_ref");
+ if(ret == FAIL)
+ goto out;
+ obj->obj_list->list[i].freeing = FALSE;
+ } /* end else */
+ } /* end if */
+
+ /* Verify nobjs_rem is non-negative */
+ if(obj->obj_list->nobjs_rem < 0) {
+ ERROR("invalid nobjs_rem");
+ goto out;
+ } /* end if */
+
+ return 0;
+
+out:
+ return -1;
+} /* end test_rct_free() */
+
+/* Test function */
+static int test_remove_clear_type(void)
+{
+ H5I_type_t obj_type;
+ test_rct_list_t obj_list;
+ test_rct_obj_t list[TEST_RCT_MAX_NOBJS];
+ long i, j;
+ long nobjs_found;
+ hsize_t nmembers;
+ herr_t ret; /* return value */
+
+ /* Register type */
+ obj_type = H5Iregister_type((size_t)8, 0, test_rct_free);
+ CHECK(obj_type, H5I_BADID, "H5Iregister_type");
+ if(obj_type == H5I_BADID)
+ goto out;
+
+ /* Init obj_list.list */
+ obj_list.list = list;
+
+ for(i = 0; i < TEST_RCT_NITER; i++) {
+ /* Build object list */
+ obj_list.nobjs = obj_list.nobjs_rem = TEST_RCT_MIN_NOBJS + (HDrandom() % (long)(TEST_RCT_MAX_NOBJS - TEST_RCT_MIN_NOBJS + 1));
+ for(j = 0; j < obj_list.nobjs; j++) {
+ list[j].nfrees = 0;
+ list[j].freeing = FALSE;
+ list[j].obj_list = &obj_list;
+ list[j].id = H5Iregister(obj_type, &list[j]);
+ CHECK(list[j].id, FAIL, "H5Iregister");
+ if(list[j].id == FAIL)
+ goto out;
+ if(HDrandom() % 2) {
+ ret = H5Iinc_ref(list[j].id);
+ CHECK(ret, FAIL, "H5Iinc_ref");
+ if(ret == FAIL)
+ goto out;
+ } /* end if */
+ } /* end for */
+
+ /* Clear the type */
+ ret = H5Iclear_type(obj_type, FALSE);
+ CHECK(ret, FAIL, "H5Iclear_type");
+ if(ret == FAIL)
+ goto out;
+
+ /* Verify list */
+ nobjs_found = 0;
+ for(j = 0; j < obj_list.nobjs; j++) {
+ if(list[j].nfrees == 0)
+ nobjs_found++;
+ else {
+ VERIFY(list[j].nfrees, (long)1, "list[j].nfrees");
+ if(list[j].nfrees != (long)1)
+ goto out;
+ } /* end else */
+ VERIFY(list[j].freeing, FALSE, "list[j].freeing");
+ if(list[j].freeing != FALSE)
+ goto out;
+ } /* end for */
+
+ /* Verify number of objects */
+ VERIFY(obj_list.nobjs_rem, nobjs_found, "obj_list.nobjs_rem");
+ if(obj_list.nobjs_rem != nobjs_found)
+ goto out;
+ ret = H5Inmembers(obj_type, &nmembers);
+ CHECK(ret, FAIL, "H5Inmembers");
+ if(ret == FAIL)
+ goto out;
+ VERIFY(nmembers, (size_t)nobjs_found, "H5Inmembers");
+ if(nmembers != (size_t)nobjs_found)
+ goto out;
+
+ /* Clear the type with force set to TRUE */
+ ret = H5Iclear_type(obj_type, TRUE);
+ CHECK(ret, FAIL, "H5Iclear_type");
+ if(ret == FAIL)
+ goto out;
+
+ /* Verify list */
+ for(j = 0; j < obj_list.nobjs; j++) {
+ VERIFY(list[j].nfrees, (long)1, "list[j].nfrees");
+ if(list[j].nfrees != (long)1)
+ goto out;
+ VERIFY(list[j].freeing, FALSE, "list[j].freeing");
+ if(list[j].freeing != FALSE)
+ goto out;
+ } /* end for */
+
+ /* Verify number of objects is 0 */
+ VERIFY(obj_list.nobjs_rem, (long)0, "obj_list.nobjs_rem");
+ if(obj_list.nobjs_rem != (long)0)
+ goto out;
+ ret = H5Inmembers(obj_type, &nmembers);
+ CHECK(ret, FAIL, "H5Inmembers");
+ if(ret == FAIL)
+ goto out;
+ VERIFY(nmembers, (size_t)0, "H5Inmembers");
+ if(nmembers != (size_t)0)
+ goto out;
+ } /* end for */
+
+ /* Destroy type */
+ ret = H5Idestroy_type(obj_type);
+ CHECK(ret, FAIL, "H5Idestroy_type");
+ if(ret == FAIL)
+ goto out;
+
+ return 0;
+
+out:
+ /* Cleanup. For simplicity, just destroy the types and ignore errors. */
+ H5E_BEGIN_TRY
+ H5Idestroy_type(obj_type);
+ H5E_END_TRY
+ return -1;
+} /* end test_remove_clear_type() */
+
void test_ids(void)
{
+ /* Set the random # seed */
+ HDsrandom((unsigned)HDtime(NULL));
+
if (basic_id_test() < 0) TestErrPrintf("Basic ID test failed\n");
if (id_predefined_test() < 0) TestErrPrintf("Predefined ID type test failed\n");
if (test_is_valid() < 0) TestErrPrintf("H5Iis_valid test failed\n");
if (test_get_type() < 0) TestErrPrintf("H5Iget_type test failed\n");
if (test_id_type_list() < 0) TestErrPrintf("ID type list test failed\n");
+ if (test_remove_clear_type() < 0) TestErrPrintf("ID remove during H5Iclear_type test failed\n");
}
diff --git a/test/tskiplist.c b/test/tskiplist.c
index 07e63fd..62c5f8e 100644
--- a/test/tskiplist.c
+++ b/test/tskiplist.c
@@ -1171,6 +1171,208 @@ test_skiplist_free(void)
/****************************************************************
**
+** test_skiplist_try_free_safe(): Test H5SL (skip list) code.
+** Tests 'try_free_safe' operation in skip lists.
+**
+****************************************************************/
+/* Macro definitions */
+#define TEST_TFS_MAX_NOBJS 100
+#define TEST_TFS_MIN_NOBJS 5
+#define TEST_TFS_NITER 50
+
+/* Structure to hold the list of objects */
+typedef struct {
+ H5SL_t *slist; /* Skiplist holding the objects */
+ struct test_tfs_obj_t *list; /* Linear list of objects */
+ int nobjs; /* Number of objects in list */
+ int nobjs_rem; /* Number of objects in list that have not been freed */
+} test_tfs_list_t;
+
+/* Structure for an object */
+typedef struct test_tfs_obj_t {
+ int idx; /* Index (key) for this object */
+ int nfrees; /* Number of times this object has been freed */
+} test_tfs_obj_t;
+
+/* op_data struct for H5SL_iterate() */
+typedef struct test_tfs_it_ud_t {
+ test_tfs_list_t *obj_list; /* List of objects */
+ int last_idx; /* Index of last object visited in iteration */
+ int ncalls; /* Number of times this callback was called */
+} test_tfs_it_ud_t;
+
+/* iterate callback */
+static herr_t test_tfs_iter(void *_obj, void *key, void *_udata) {
+ test_tfs_obj_t *obj = (test_tfs_obj_t *)_obj;
+ test_tfs_it_ud_t *udata = (test_tfs_it_ud_t *)_udata;
+
+ /* Check consistency */
+ VERIFY((void *)&obj->idx, key, "obj->idx");
+ VERIFY(obj, &udata->obj_list->list[obj->idx], "obj_list->list[obj->idx]");
+
+ /* Increment number of calls */
+ udata->ncalls++;
+
+ /* Verify we were given the correct object */
+ do {
+ udata->last_idx++;
+ } while(udata->obj_list->list[udata->last_idx].nfrees != 0);
+ VERIFY(udata->last_idx, obj->idx, "H5SL_iterate");
+
+ return 0;
+} /* end test_tfs_iter() */
+
+/* try_free_safe callback */
+static htri_t test_tfs_free(void *_obj, void *key, void *_obj_list) {
+ test_tfs_obj_t *obj = (test_tfs_obj_t *)_obj;
+ test_tfs_list_t *obj_list = (test_tfs_list_t *)_obj_list;
+ test_tfs_it_ud_t iter_ud;
+ int nrems, rem_idx, i, j;
+ test_tfs_obj_t *obj_ret;
+ herr_t ret; /* return value */
+ htri_t ret_value;
+
+ /* Check consistency */
+ VERIFY((void *)&obj->idx, key, "obj->idx");
+ VERIFY(obj, &obj_list->list[obj->idx], "obj_list->list[obj->idx]");
+
+ /* Mark this object as freed (to make sure it isn't recursively freed, that
+ * is not something we support, we will undo this if we decide later not to
+ * free the object) */
+ obj->nfrees++;
+ obj_list->nobjs_rem--;
+
+ /* Decide how many objects to remove */
+ nrems = (int)(HDrandom() % (long)3);
+
+ /* Remove objects */
+ for(i = 0; i < nrems; i++)
+ /* Check nobjs_rem */
+ if(obj_list->nobjs_rem > 0) {
+ /* Remove a random object from the list */
+ rem_idx = (int)(HDrandom() % (long)obj_list->nobjs_rem);
+
+ /* Scan the list, finding the rem_idx'th object that has not been
+ * freed */
+ for(j = 0; j < obj_list->nobjs; j++)
+ if(obj_list->list[j].nfrees == 0) {
+ if(rem_idx == 0)
+ break;
+ else
+ rem_idx--;
+ } /* end if */
+ if(j == obj_list->nobjs)
+ ERROR("invalid obj_list");
+ else {
+ /* Remove the object */
+ obj_ret = (test_tfs_obj_t *)H5SL_remove(obj_list->slist, &j);
+ CHECK(obj_ret, NULL, "H5SL_remove");
+ obj_ret->nfrees++;
+ obj_list->nobjs_rem--;
+ } /* end else */
+ } /* end if */
+
+ /* Mark this object as not freed so we know to expect it in the iterate call
+ */
+ obj->nfrees--;
+ obj_list->nobjs_rem++;
+
+ /* Iterate over skip list (maybe) */
+ if(HDrandom() % (long)5) {
+ iter_ud.obj_list = obj_list;
+ iter_ud.last_idx = -1;
+ iter_ud.ncalls = 0;
+ ret = H5SL_iterate(obj_list->slist, test_tfs_iter, &iter_ud);
+ CHECK(ret, FAIL, "H5SL_iterate");
+ VERIFY(iter_ud.ncalls, obj_list->nobjs_rem, "H5SL_iterate");
+ } /* end if */
+
+ /* Verify nobjs_rem is non-negative */
+ if(obj_list->nobjs_rem < 0)
+ ERROR("invalid nobjs_rem");
+
+ /* Decide whether this object should be freed */
+ if(HDrandom() % (long)2) {
+ /* Free the object */
+ ret_value = TRUE;
+ obj->nfrees++;
+ obj_list->nobjs_rem--;
+ } /* end if */
+ else
+ /* Do not free the object */
+ ret_value = FALSE;
+
+ return ret_value;
+} /* end test_tfs_free() */
+
+/* Test function */
+static void
+test_skiplist_try_free_safe(void)
+{
+ test_tfs_list_t obj_list;
+ test_tfs_obj_t list[TEST_TFS_MAX_NOBJS];
+ int i, j;
+ int nobjs_found;
+ hsize_t count;
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Skip List 'Try Free Safe' Operation\n"));
+
+ /* Create a skip list */
+ obj_list.slist = H5SL_create(H5SL_TYPE_INT, NULL);
+ CHECK(obj_list.slist, NULL, "H5SL_create");
+
+ /* Init obj_list.list */
+ obj_list.list = list;
+ for(j = 0; j < TEST_TFS_MAX_NOBJS; j++)
+ list[j].idx = j;
+
+ for(i = 0; i < TEST_TFS_NITER; i++) {
+ /* Build object list */
+ obj_list.nobjs = obj_list.nobjs_rem = (int)(TEST_TFS_MIN_NOBJS + (HDrandom() % (long)(TEST_TFS_MAX_NOBJS - TEST_TFS_MIN_NOBJS + 1)));
+ for(j = 0; j < obj_list.nobjs; j++) {
+ list[j].nfrees = 0;
+ ret = H5SL_insert(obj_list.slist, &list[j], &list[j].idx);
+ CHECK(ret, FAIL, "H5SL_insert");
+ } /* end for */
+
+ /* Call H5S_try_free_safe() - free most of the items in the skip list in
+ * a safe manner */
+ ret = H5SL_try_free_safe(obj_list.slist, test_tfs_free, &obj_list);
+ CHECK(ret, FAIL, "H5SL_try_free_safe");
+
+ /* Verify list */
+ nobjs_found = 0;
+ for(j = 0; j < obj_list.nobjs; j++)
+ if(list[j].nfrees == 0)
+ nobjs_found++;
+ else
+ VERIFY(list[j].nfrees, (long)1, "list[j].nfrees");
+
+ /* Verify number of objects */
+ VERIFY(obj_list.nobjs_rem, nobjs_found, "obj_list.nobjs_rem");
+ count = H5SL_count(obj_list.slist);
+ VERIFY(count, (size_t)nobjs_found, "H5SL_count");
+
+ /* Release the skip list, forcibly freeing all nodes (will not make
+ * callbacks) */
+ ret = H5SL_release(obj_list.slist);
+ CHECK(ret, FAIL, "H5SL_release");
+
+ /* Verify number of objects is 0 */
+ count = H5SL_count(obj_list.slist);
+ VERIFY(count, (size_t)0, "H5SL_count");
+ } /* end for */
+
+ /* Close the skip list */
+ ret = H5SL_close(obj_list.slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_try_free_safe() */
+
+/****************************************************************
+**
** test_skiplist_less(): Test H5SL (skip list) code.
** Tests 'less' operation in skip lists.
**
@@ -1577,6 +1779,7 @@ test_skiplist(void)
test_skiplist_add(); /* Test 'add' operation */
test_skiplist_destroy(); /* Test 'destroy' operation */
test_skiplist_free(); /* Test 'free' operation */
+ test_skiplist_try_free_safe(); /* Test 'try_free_safe' operation */
test_skiplist_less(); /* Test 'less' operation */
test_skiplist_greater(); /* Test 'greater' operation */
test_skiplist_below(); /* Test 'below' operation */