diff options
Diffstat (limited to 'src/H5SL.c')
| -rw-r--r-- | src/H5SL.c | 606 |
1 files changed, 445 insertions, 161 deletions
@@ -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. |