diff options
Diffstat (limited to 'src/H5SL.c')
| -rw-r--r-- | src/H5SL.c | 1349 |
1 files changed, 675 insertions, 674 deletions
@@ -1,16 +1,13 @@ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Copyright by The HDF Group. * - * Copyright by the Board of Trustees of the University of Illinois. * * All rights reserved. * * * * This file is part of HDF5. The full HDF5 copyright notice, including * * terms governing use, modification, and redistribution, is contained in * - * the files COPYING and Copyright.html. COPYING can be found at the root * - * of the source code distribution tree; Copyright.html can be found at the * - * root level of an installed copy of the electronic HDF5 document set and * - * is linked from the top-level documents page. It can also be found at * - * http://hdfgroup.org/HDF5/doc/Copyright.html. If you do not have * - * access to either file, you may request a copy from help@hdfgroup.org. * + * the COPYING file, which can be found at the root of the source code * + * distribution tree, or in https://www.hdfgroup.org/licenses. * + * If you do not have access to either file, you may request a copy from * + * help@hdfgroup.org. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* @@ -38,13 +35,6 @@ * skip list. The implementation in that document hurts * performance, at least for integer keys. -NAF) * - * (Also, this implementation has a couple of home-grown - * optimizations, including setting the "update" vector to the - * actual 'forward' pointer to update, instead of the node - * containing the forward pointer -QAK - * -No longer uses update vector, as insertions/deletions are now - * always at level 0. -NAF) - * * (Note: This implementation does not have the information for * implementing the "Linear List Operations" (like insert/delete/ * search by position) in section 3.4 of "A Skip List Cookbook", @@ -59,459 +49,465 @@ * */ -/* Interface initialization */ -#define H5_INTERFACE_INIT_FUNC H5SL_init_interface - +#include "H5SLmodule.h" /* This source code file is part of the H5SL module */ /* Private headers needed */ -#include "H5private.h" /* Generic Functions */ -#include "H5Eprivate.h" /* Error handling */ -#include "H5FLprivate.h" /* Free Lists */ -#include "H5SLprivate.h" /* Skip list routines */ -#include "H5MMprivate.h" /* Memory management */ +#include "H5private.h" /* Generic Functions */ +#include "H5Eprivate.h" /* Error handling */ +#include "H5FLprivate.h" /* Free Lists */ +#include "H5MMprivate.h" /* Memory management */ +#include "H5SLprivate.h" /* Skip list routines */ /* Local Macros */ /* 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); +#define H5SL_LOCATE_SEARCH_FOUND(SLIST, X, I) \ + { \ + HGOTO_DONE(X->item); \ + } /* 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); - +#define H5SL_LOCATE_FIND_FOUND(SLIST, X, I) \ + { \ + HGOTO_DONE(X); \ + } /* Define a code template for comparing scalar keys for the "CMP" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_SCALAR_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ - (*(TYPE *)((PNODE)->key) < *(TYPE *)PKEY) +#define H5SL_LOCATE_SCALAR_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) (*(TYPE *)((PNODE)->key) < *(TYPE *)PKEY) /* Define a code template for comparing string keys for the "CMP" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_STRING_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ - (((PNODE)->hashval == HASHVAL) ? \ - (HDstrcmp((const char *)(PNODE)->key, (const char *)PKEY) < 0) : \ - ((PNODE)->hashval < HASHVAL)) +#define H5SL_LOCATE_STRING_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ + (((PNODE)->hashval == HASHVAL) ? (HDstrcmp((const char *)(PNODE)->key, (const char *)PKEY) < 0) \ + : ((PNODE)->hashval < HASHVAL)) /* Define a code template for comparing H5_obj_t keys for the "CMP" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_OBJ_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ - ((((TYPE *)((PNODE)->key))->fileno == ((TYPE *)PKEY)->fileno) \ - ? (((TYPE *)((PNODE)->key))->addr < ((TYPE *)PKEY)->addr) \ - : (((TYPE *)((PNODE)->key))->fileno < ((TYPE *)PKEY)->fileno)) +#define H5SL_LOCATE_OBJ_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ + ((((TYPE *)((PNODE)->key))->fileno == ((TYPE *)PKEY)->fileno) \ + ? (((TYPE *)((PNODE)->key))->addr < ((TYPE *)PKEY)->addr) \ + : (((TYPE *)((PNODE)->key))->fileno < ((TYPE *)PKEY)->fileno)) /* Define a code template for comparing generic keys for the "CMP" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_GENERIC_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ - ((SLIST)->cmp((TYPE *)((PNODE)->key), (TYPE *)PKEY) < 0) - +#define H5SL_LOCATE_GENERIC_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ + ((SLIST)->cmp((TYPE *)((PNODE)->key), (TYPE *)PKEY) < 0) /* Define a code template for comparing scalar keys for the "EQ" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_SCALAR_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ - (*(TYPE *)((PNODE)->key) == *(TYPE *)PKEY) +#define H5SL_LOCATE_SCALAR_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) (*(TYPE *)((PNODE)->key) == *(TYPE *)PKEY) /* Define a code template for comparing string keys for the "EQ" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_STRING_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ - (((PNODE)->hashval == HASHVAL) && (HDstrcmp((const char *)(PNODE)->key, (const char *)PKEY) == 0)) +#define H5SL_LOCATE_STRING_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ + (((PNODE)->hashval == HASHVAL) && (HDstrcmp((const char *)(PNODE)->key, (const char *)PKEY) == 0)) /* Define a code template for comparing H5_obj_t keys for the "EQ" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_OBJ_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ - ((((TYPE *)((PNODE)->key))->fileno == ((TYPE *)PKEY)->fileno) && (((TYPE *)((PNODE)->key))->addr == ((TYPE *)PKEY)->addr)) +#define H5SL_LOCATE_OBJ_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ + ((((TYPE *)((PNODE)->key))->fileno == ((TYPE *)PKEY)->fileno) && \ + (((TYPE *)((PNODE)->key))->addr == ((TYPE *)PKEY)->addr)) /* Define a code template for comparing generic keys for the "EQ" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_GENERIC_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ - ((SLIST)->cmp((TYPE *)((PNODE)->key), (TYPE *)PKEY) == 0) +#define H5SL_LOCATE_GENERIC_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \ + ((SLIST)->cmp((TYPE *)((PNODE)->key), (TYPE *)PKEY) == 0) - -/* Define a code template for initializing the hash value for scalar keys for the "HASHINIT" in the H5SL_LOCATE macro */ +/* Define a code template for initializing the hash value for scalar keys for the "HASHINIT" in the + * H5SL_LOCATE macro */ #define H5SL_LOCATE_SCALAR_HASHINIT(KEY, HASHVAL) -/* Define a code template for initializing the hash value for string keys for the "HASHINIT" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_STRING_HASHINIT(KEY, HASHVAL) \ - HASHVAL = H5_hash_string((const char *)KEY); +/* Define a code template for initializing the hash value for string keys for the "HASHINIT" in the + * H5SL_LOCATE macro */ +#define H5SL_LOCATE_STRING_HASHINIT(KEY, HASHVAL) HASHVAL = H5_hash_string((const char *)KEY); -/* Define a code template for initializing the hash value for H5_obj_t keys for the "HASHINIT" in the H5SL_LOCATE macro */ +/* Define a code template for initializing the hash value for H5_obj_t keys for the "HASHINIT" in the + * H5SL_LOCATE macro */ #define H5SL_LOCATE_OBJ_HASHINIT(KEY, HASHVAL) -/* Define a code template for initializing the hash value for generic keys for the "HASHINIT" in the H5SL_LOCATE macro */ +/* Define a code template for initializing the hash value for generic keys for the "HASHINIT" in the + * H5SL_LOCATE macro */ #define H5SL_LOCATE_GENERIC_HASHINIT(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 */ \ + \ + H5_GLUE3(H5SL_LOCATE_, CMP, _HASHINIT) \ + (KEY, HASHVAL) for (_i = (int)SLIST->curr_level; _i >= 0; _i--) \ + { \ + _count = 0; \ + while (_count < 3 && X->forward[_i] && \ + H5_GLUE3(H5SL_LOCATE_, CMP, _CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL)) { \ + X = X->forward[_i]; \ + _count++; \ + } \ + } \ + 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 */ \ + H5_GLUE3(H5SL_LOCATE_, OP, _FOUND)(SLIST, X, _i) \ + } \ + } /* Macro used to find node for operation */ -#define H5SL_LOCATE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \ -{ \ - int _i; /* Local index variable */ \ - unsigned _count; /* Num nodes searched at this height */ \ - \ - H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \ - for(_i = (int)SLIST->curr_level; _i >= 0; _i--) { \ - _count = 0; \ - while(_count < 3 && X->forward[_i] && \ - H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL) ) { \ - X = X->forward[_i]; \ - _count++; \ - } /* end while */ \ - } /* 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 */ \ - H5_GLUE3(H5SL_LOCATE_,OP,_FOUND)(SLIST, X, _i) \ - } /* end if */ \ -} - +#define H5SL_LOCATE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \ + { \ + 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) \ -{ \ - /* Check if we need to increase allocation of forward pointers */ \ - if(LVL + 1 >= 1u << X->log_nalloc) { \ - H5SL_node_t **_tmp; \ - HDassert(LVL + 1 == 1u << X->log_nalloc); \ - /* Double the amount of allocated space */ \ - X->log_nalloc++; \ - \ - /* Check if we need to create a new factory */ \ - if(X->log_nalloc >= H5SL_fac_nused_g) { \ - HDassert(X->log_nalloc == H5SL_fac_nused_g); \ - \ - /* Check if we need to allocate space for the factory pointer*/ \ - if(H5SL_fac_nused_g >= H5SL_fac_nalloc_g) { \ - 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 *)); \ - } /* end if */ \ - \ - /* Create the new factory */ \ - H5SL_fac_g[H5SL_fac_nused_g] = H5FL_fac_init((1u << H5SL_fac_nused_g) * sizeof(H5SL_node_t *)); \ - H5SL_fac_nused_g++; \ - } /* end if */ \ - \ - /* 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") \ - 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; \ - } /* end if */ \ - \ - X->level++; \ -} - +#define H5SL_GROW(X, LVL, ERR) \ + { \ + /* Check if we need to increase allocation of forward pointers */ \ + if (LVL + 1 >= 1u << X->log_nalloc) { \ + H5SL_node_t **_tmp; \ + HDassert(LVL + 1 == 1U << X->log_nalloc); \ + /* Double the amount of allocated space */ \ + X->log_nalloc++; \ + \ + /* Check if we need to create a new factory */ \ + if (X->log_nalloc >= H5SL_fac_nused_g) { \ + HDassert(X->log_nalloc == H5SL_fac_nused_g); \ + \ + /* Check if we need to allocate space for the factory pointer*/ \ + if (H5SL_fac_nused_g >= H5SL_fac_nalloc_g) { \ + HDassert(H5SL_fac_nused_g == H5SL_fac_nalloc_g); \ + /* Double the size of the array of factory pointers */ \ + H5SL_fac_nalloc_g *= 2; \ + 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") \ + } \ + \ + /* Create the new factory */ \ + H5SL_fac_g[H5SL_fac_nused_g] = \ + H5FL_fac_init((1u << H5SL_fac_nused_g) * sizeof(H5SL_node_t *)); \ + H5SL_fac_nused_g++; \ + } \ + \ + /* 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_CANTALLOC, ERR, "memory allocation failed") \ + H5MM_memcpy((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; \ + } \ + \ + X->level++; \ + } /* Macro used to shrink a node by 1. Does not update pointers. LVL is the * current level of X. Does not update LVL but does update X->level. */ -#define H5SL_SHRINK(X, LVL) \ -{ \ - /* Check if we can reduce the allocation of forward pointers */ \ - if(LVL <= 1u << (X->log_nalloc - 1)) { \ - H5SL_node_t **_tmp; \ - HDassert(LVL == 1u << (X->log_nalloc - 1)); \ - X->log_nalloc--; \ - \ - /* 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") \ - HDmemcpy((void *)_tmp, (const void *)X->forward, (LVL) * 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; \ - } /* end if */ \ - \ - X->level--; \ -} - +#define H5SL_SHRINK(X, LVL) \ + { \ + /* Check if we can reduce the allocation of forward pointers */ \ + if (LVL <= 1u << (X->log_nalloc - 1)) { \ + H5SL_node_t **_tmp; \ + HDassert(LVL == 1U << (X->log_nalloc - 1)); \ + X->log_nalloc--; \ + \ + /* 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") \ + H5MM_memcpy((void *)_tmp, (const void *)X->forward, (LVL) * 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; \ + } \ + \ + X->level--; \ + } /* 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) \ -{ \ - size_t _lvl = X->level; \ - \ - H5SL_GROW(X, _lvl); \ - \ - if(_lvl == (size_t) SLIST->curr_level) { \ - HDassert(PREV == SLIST->header); \ - /* Grow the head */ \ - H5SL_GROW(PREV, _lvl); \ - SLIST->curr_level++; \ - X->forward[_lvl+1] = NULL; \ - } else { \ - HDassert(_lvl < (size_t) SLIST->curr_level); \ - X->forward[_lvl+1] = PREV->forward[_lvl+1]; \ - } /* end else */ \ - PREV->forward[_lvl+1] = X; \ -} - +#define H5SL_PROMOTE(SLIST, X, PREV, ERR) \ + { \ + size_t _lvl = X->level; \ + \ + H5SL_GROW(X, _lvl, ERR); \ + \ + if (_lvl == (size_t)SLIST->curr_level) { \ + HDassert(PREV == SLIST->header); \ + /* Grow the head */ \ + H5SL_GROW(PREV, _lvl, ERR) \ + SLIST->curr_level++; \ + X->forward[_lvl + 1] = NULL; \ + } \ + else { \ + HDassert(_lvl < (size_t)SLIST->curr_level); \ + X->forward[_lvl + 1] = PREV->forward[_lvl + 1]; \ + } \ + PREV->forward[_lvl + 1] = X; \ + } /* Macro used to reduce the level of a node by 1. Does not update the head node - * "current level". PREV is the previous node of the currrent height of X. */ -#define H5SL_DEMOTE(X, PREV) \ -{ \ - size_t _lvl = X->level; \ - \ - HDassert(PREV->forward[_lvl] == X); \ - PREV->forward[_lvl] = X->forward[_lvl]; \ - H5SL_SHRINK(X, _lvl); \ -} - + * "current level". PREV is the previous node of the current height of X. */ +#define H5SL_DEMOTE(X, PREV) \ + { \ + size_t _lvl = X->level; \ + \ + HDassert(PREV->forward[_lvl] == X); \ + PREV->forward[_lvl] = X->forward[_lvl]; \ + H5SL_SHRINK(X, _lvl); \ + } /* Macro used to insert node. Does not actually insert the node. After running * this macro, X will contain the node before where the new node should be * inserted (at level 0). */ -#define H5SL_INSERT(CMP, SLIST, X, TYPE, KEY, HASHVAL) \ -{ \ - H5SL_node_t *_last = X; /* Lowest node in the current gap */ \ - H5SL_node_t *_next = NULL; /* Highest node in the currect gap */ \ - H5SL_node_t *_drop; /* Low node of the gap to drop into */ \ - int _count; /* Number of nodes in the current gap */ \ - int _i; \ - \ - H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \ - for(_i = (int)SLIST->curr_level; _i >= 0; _i--) { \ - /* Search for the node to drop into, also count the number of nodes */ \ - /* of height _i in this gap */ \ - _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 */ \ - \ - /* Check if this node is the start of the next gap */ \ - if(!_drop && !H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL)) \ - _drop = X; \ - \ - /* 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]; \ - _count = 3; \ - break; \ - } \ - X = X->forward[_i]; \ - } /* end for */ \ - HDassert(!_drop->forward[_i] || \ - !H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, _drop->forward[_i], KEY, HASHVAL)); \ - \ - /* Promote the middle node if necessary */ \ - if(_count == 3) { \ - HDassert(X == _last->forward[_i]->forward[_i]); \ - H5SL_PROMOTE(SLIST, X, _last) \ - } \ - \ - /* Prepare to drop down */ \ - X = _last = _drop; \ - _next = _drop->forward[_i]; \ - } /* end for */ \ - \ - if(_next && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, _next, KEY, HASHVAL)) \ - HGOTO_ERROR(H5E_SLIST, H5E_CANTINSERT, NULL, "can't insert duplicate key") \ -} - +#define H5SL_INSERT(CMP, SLIST, X, TYPE, KEY, HASHVAL) \ + { \ + H5SL_node_t *_last = X; /* Lowest node in the current gap */ \ + H5SL_node_t *_next = NULL; /* Highest node in the current gap */ \ + H5SL_node_t *_drop; /* Low node of the gap to drop into */ \ + int _count; /* Number of nodes in the current gap */ \ + int _i; \ + \ + H5_GLUE3(H5SL_LOCATE_, CMP, _HASHINIT) \ + (KEY, HASHVAL) for (_i = (int)SLIST->curr_level; _i >= 0; _i--) \ + { \ + /* Search for the node to drop into, also count the number of nodes */ \ + /* of height _i in this gap */ \ + _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; \ + } \ + \ + /* Check if this node is the start of the next gap */ \ + if (!_drop && !H5_GLUE3(H5SL_LOCATE_, CMP, _CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL)) \ + _drop = X; \ + \ + /* 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]; \ + _count = 3; \ + break; \ + } \ + X = X->forward[_i]; \ + } \ + HDassert(!_drop->forward[_i] || \ + !H5_GLUE3(H5SL_LOCATE_, CMP, _CMP)(SLIST, TYPE, _drop->forward[_i], KEY, HASHVAL)); \ + \ + /* Promote the middle node if necessary */ \ + if (_count == 3) { \ + HDassert(X == _last->forward[_i]->forward[_i]); \ + H5SL_PROMOTE(SLIST, X, _last, NULL) \ + } \ + \ + /* Prepare to drop down */ \ + X = _last = _drop; \ + _next = _drop->forward[_i]; \ + } \ + \ + if (_next && H5_GLUE3(H5SL_LOCATE_, CMP, _EQ)(SLIST, TYPE, _next, KEY, HASHVAL)) \ + HGOTO_ERROR(H5E_SLIST, H5E_CANTINSERT, NULL, "can't insert duplicate key") \ + } /* 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; \ - \ - if(_i < 0) \ - HGOTO_DONE(NULL); \ - \ - 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; \ - \ - /* 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; \ - } /* end if */ \ - } /* end if */ \ - 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)); \ - \ - /* 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]; \ - \ - /* 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); \ - \ - 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) \ - \ - /* 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); \ - \ - H5SL_SHRINK(_head, (size_t) (_i+1)) \ - SLIST->curr_level--; \ - } /* end else */ \ - } /* end else */ \ - } /* end if */ \ - \ - /* 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; \ - \ - /* 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); \ - \ - HGOTO_DONE(tmp); \ - } /* end if */ \ -} - +#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 current 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); \ + \ + 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; \ + \ + /* 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; \ + } \ + \ + /* 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; \ + } \ + } \ + else \ + _ldrop = X; \ + } \ + \ + /* 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; \ + } \ + X = X->forward[_i]; \ + } \ + 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 */ \ + /* 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) \ + \ + /* 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--; \ + } \ + } \ + 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) \ + \ + /* 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--; \ + } \ + } \ + } \ + \ + /* Prepare to drop down */ \ + _llast = _ldrop; \ + _last = _drop; \ + _next = _drop->forward[_i]; \ + } \ + \ + /* 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; \ + } \ + 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); \ + \ + HGOTO_DONE(tmp); \ + } \ + } /* Macro used to search for node */ -#define H5SL_SEARCH(CMP, SLIST, X, TYPE, KEY, HASHVAL) \ - H5SL_LOCATE(SEARCH, CMP, SLIST, X, TYPE, KEY, HASHVAL) +#define H5SL_SEARCH(CMP, SLIST, X, TYPE, KEY, HASHVAL) H5SL_LOCATE(SEARCH, CMP, SLIST, X, TYPE, KEY, HASHVAL) /* Macro used to find a node */ -#define H5SL_FIND(CMP, SLIST, X, TYPE, KEY, HASHVAL) \ - H5SL_LOCATE(FIND, CMP, SLIST, X, TYPE, KEY, HASHVAL) - +#define H5SL_FIND(CMP, SLIST, X, TYPE, KEY, HASHVAL) H5SL_LOCATE(FIND, CMP, SLIST, X, TYPE, KEY, HASHVAL) /* Private typedefs & structs */ /* Skip list node data structure */ struct H5SL_node_t { - const void *key; /* Pointer to node's key */ - void *item; /* Pointer to node's item */ - 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) */ - struct H5SL_node_t **forward; /* Array of forward pointers from this node */ - struct H5SL_node_t *backward; /* Backward pointer from this node */ + const void *key; /* Pointer to node's key */ + void *item; /* Pointer to node's item */ + 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) */ + struct H5SL_node_t **forward; /* Array of forward pointers from this node */ + struct H5SL_node_t *backward; /* Backward pointer from this node */ }; /* Main skip list data structure */ struct H5SL_t { /* Static values for each list */ - H5SL_type_t type; /* Type of skip list */ - H5SL_cmp_t cmp; /* Comparison callback, if type is H5SL_TYPE_GENERIC */ + H5SL_type_t type; /* Type of skip list */ + H5SL_cmp_t cmp; /* Comparison callback, if type is H5SL_TYPE_GENERIC */ /* Dynamic values for each list */ - int curr_level; /* Current top level used in list */ - 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 */ + int curr_level; /* Current top level used in list */ + 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 */ }; /* Static functions */ -static H5SL_node_t * H5SL_new_node(void *item, const void *key, uint32_t hashval); -static H5SL_node_t *H5SL_insert_common(H5SL_t *slist, void *item, const void *key); -static herr_t H5SL_release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data); -static herr_t H5SL_close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data); +static H5SL_node_t *H5SL__new_node(void *item, const void *key, uint32_t hashval); +static H5SL_node_t *H5SL__insert_common(H5SL_t *slist, void *item, const void *key); +static herr_t H5SL__release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data); +static herr_t H5SL__close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data); /* Declare a free list to manage the H5SL_t struct */ H5FL_DEFINE_STATIC(H5SL_t); @@ -521,53 +517,96 @@ H5FL_DEFINE_STATIC(H5SL_node_t); /* Global variables */ static H5FL_fac_head_t **H5SL_fac_g; -static size_t H5SL_fac_nused_g; -static size_t H5SL_fac_nalloc_g; +static size_t H5SL_fac_nused_g; +static size_t H5SL_fac_nalloc_g; + +/*------------------------------------------------------------------------- + * Function: H5SL_init + * + * Purpose: Initialize the interface from some other layer. + * + * Return: Success: non-negative + * Failure: negative + *------------------------------------------------------------------------- + */ +herr_t +H5SL_init(void) +{ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI_NOERR + + /* Allocate space for array of factories */ + H5SL_fac_g = (H5FL_fac_head_t **)H5MM_malloc(sizeof(H5FL_fac_head_t *)); + HDassert(H5SL_fac_g); + H5SL_fac_nalloc_g = 1; + + /* Initialize first factory */ + H5SL_fac_g[0] = H5FL_fac_init(sizeof(H5SL_node_t *)); + HDassert(H5SL_fac_g[0]); + H5SL_fac_nused_g = 1; + + FUNC_LEAVE_NOAPI(ret_value) +} - /*-------------------------------------------------------------------------- NAME - H5SL_init_interface + H5SL_term_package PURPOSE - Initialize interface-specific information + Terminate all the H5FL factories used in this package, and clear memory USAGE - herr_t H5SL_init_interface() - + int H5SL_term_package() RETURNS - Non-negative on success/Negative on failure + Success: Positive if any action might have caused a change in some + other interface; zero otherwise. + Failure: Negative DESCRIPTION - Initializes any interface-specific data or routines. + Release any resources allocated. GLOBAL VARIABLES COMMENTS, BUGS, ASSUMPTIONS + Can't report errors... EXAMPLES REVISION LOG --------------------------------------------------------------------------*/ -static herr_t -H5SL_init_interface(void) +int +H5SL_term_package(void) { + int n = 0; + FUNC_ENTER_NOAPI_NOINIT_NOERR - /* Allocate space for array of factories */ - H5SL_fac_g = (H5FL_fac_head_t **)H5MM_malloc(sizeof(H5FL_fac_head_t *)); - HDassert(H5SL_fac_g); - H5SL_fac_nalloc_g = 1; + /* Terminate all the factories */ + if (H5SL_fac_nused_g > 0) { + size_t i; + herr_t H5_ATTR_NDEBUG_UNUSED ret; - /* Initialize first factory */ - H5SL_fac_g[0] = H5FL_fac_init(sizeof(H5SL_node_t *)); - HDassert(H5SL_fac_g[0]); - H5SL_fac_nused_g = 1; + for (i = 0; i < H5SL_fac_nused_g; i++) { + ret = H5FL_fac_term(H5SL_fac_g[i]); + HDassert(ret >= 0); + } + H5SL_fac_nused_g = 0; - FUNC_LEAVE_NOAPI(SUCCEED) -} /* end H5SL_init_interface() */ + n++; + } + + /* Free the list of factories */ + if (H5SL_fac_g) { + H5SL_fac_g = (H5FL_fac_head_t **)H5MM_xfree((void *)H5SL_fac_g); + H5SL_fac_nalloc_g = 0; + + n++; + } + + FUNC_LEAVE_NOAPI(n) +} /* H5SL_term_package() */ - /*-------------------------------------------------------------------------- NAME - H5SL_new_node + H5SL__new_node PURPOSE Create a new skip list node of level 0 USAGE - H5SL_node_t *H5SL_new_node(item,key,hasval) + H5SL_node_t *H5SL__new_node(item,key,hasval) void *item; IN: Pointer to item info for node void *key; IN: Pointer to key info for node uint32_t hashval; IN: Hash value for node @@ -584,39 +623,38 @@ H5SL_init_interface(void) REVISION LOG --------------------------------------------------------------------------*/ static H5SL_node_t * -H5SL_new_node(void *item, const void *key, uint32_t hashval) +H5SL__new_node(void *item, const void *key, uint32_t hashval) { - H5SL_node_t *ret_value; /* New skip list node */ + H5SL_node_t *ret_value = NULL; /* New skip list node */ - FUNC_ENTER_NOAPI_NOINIT + FUNC_ENTER_PACKAGE /* Allocate the node */ - if(NULL == (ret_value = (H5SL_node_t *)H5FL_MALLOC(H5SL_node_t))) + if (NULL == (ret_value = (H5SL_node_t *)H5FL_MALLOC(H5SL_node_t))) HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "memory allocation failed") /* Initialize node */ - ret_value->key = key; - ret_value->item = item; - ret_value->level = 0; + ret_value->key = key; + ret_value->item = item; + ret_value->level = 0; ret_value->hashval = hashval; - if(NULL == (ret_value->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0]))) { + 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") - } /* end if */ + } ret_value->log_nalloc = 0; done: FUNC_LEAVE_NOAPI(ret_value) -} /* end H5SL_new_node() */ +} /* end H5SL__new_node() */ - /*-------------------------------------------------------------------------- NAME - H5SL_insert_common + H5SL__insert_common PURPOSE Common code for inserting an object into a skip list USAGE - H5SL_node_t *H5SL_insert_common(slist,item,key) + H5SL_node_t *H5SL__insert_common(slist,item,key) H5SL_t *slist; IN/OUT: Pointer to skip list void *item; IN: Item to insert void *key; IN: Key for item to insert @@ -632,14 +670,14 @@ done: REVISION LOG --------------------------------------------------------------------------*/ static H5SL_node_t * -H5SL_insert_common(H5SL_t *slist, void *item, const void *key) +H5SL__insert_common(H5SL_t *slist, void *item, const void *key) { - H5SL_node_t *x; /* Current node to examine */ - H5SL_node_t *prev; /* Node before the new node */ - uint32_t hashval = 0; /* Hash value for key */ - H5SL_node_t *ret_value; /* Return value */ + H5SL_node_t *x; /* Current node to examine */ + H5SL_node_t *prev; /* Node before the new node */ + uint32_t hashval = 0; /* Hash value for key */ + H5SL_node_t *ret_value = NULL; /* Return value */ - FUNC_ENTER_NOAPI_NOINIT + FUNC_ENTER_PACKAGE /* Check args */ HDassert(slist); @@ -653,8 +691,8 @@ H5SL_insert_common(H5SL_t *slist, void *item, const void *key) /* Work through the forward pointers for a node, finding the node at each * level that is before the location to insert */ - prev=slist->header; - switch(slist->type) { + prev = slist->header; + switch (slist->type) { case H5SL_TYPE_INT: H5SL_INSERT(SCALAR, slist, prev, const int, key, -) break; @@ -693,26 +731,25 @@ H5SL_insert_common(H5SL_t *slist, void *item, const void *key) default: HDassert(0 && "Unknown skiplist type!"); - } /* end switch */ - + } /* 'key' must not have been found in existing list, if we get here */ - if(slist->curr_level < 0) + if (slist->curr_level < 0) slist->curr_level = 0; /* Create new node of level 0 */ - if(NULL == (x = H5SL_new_node(item, key, hashval))) - HGOTO_ERROR(H5E_SLIST ,H5E_NOSPACE, NULL, "can't create new skip list node") + if (NULL == (x = H5SL__new_node(item, key, hashval))) + HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "can't create new skip list node") /* Update the links */ - x->backward = prev; - x->forward[0] = prev->forward[0]; + x->backward = prev; + x->forward[0] = prev->forward[0]; prev->forward[0] = x; - if(x->forward[0]) + if (x->forward[0]) x->forward[0]->backward = x; else { - HDassert(slist->last); + HDassert(slist->last == prev); slist->last = x; } @@ -720,20 +757,19 @@ H5SL_insert_common(H5SL_t *slist, void *item, const void *key) slist->nobjs++; /* Set return value */ - ret_value=x; + ret_value = x; done: FUNC_LEAVE_NOAPI(ret_value) -} /* end H5SL_insert_common() */ +} /* end H5SL__insert_common() */ - /*-------------------------------------------------------------------------- NAME - H5SL_release_common + H5SL__release_common PURPOSE Release all nodes from a skip list, optionally calling a 'free' operator USAGE - herr_t H5SL_release_common(slist,op,opdata) + herr_t H5SL__release_common(slist,op,opdata) H5SL_t *slist; IN/OUT: Pointer to skip list to release nodes H5SL_operator_t op; IN: Callback function to free item & key void *op_data; IN/OUT: Pointer to application data for callback @@ -752,12 +788,12 @@ done: REVISION LOG --------------------------------------------------------------------------*/ static herr_t -H5SL_release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data) +H5SL__release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data) { - H5SL_node_t *node, *next_node; /* Pointers to skip list nodes */ - herr_t ret_value = SUCCEED; + H5SL_node_t *node, *next_node; /* Pointers to skip list nodes */ + herr_t ret_value = SUCCEED; - FUNC_ENTER_NOAPI_NOINIT + FUNC_ENTER_PACKAGE /* Check args */ HDassert(slist); @@ -766,47 +802,54 @@ 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]; - - /* Call callback, if one is given */ - if(op!=NULL) - /* Casting away const OK -QAK */ - (void)(op)(node->item,(void *)node->key,op_data); + node = slist->header->forward[0]; + while (node) { + next_node = node->forward[0]; + + /* Call callback, if one is given. + * + * Ignoring const here is fine as we only need the value to be const + * with respect to the list code, which should never modify the + * elements. The library code that is making use of the skip list + * container can do what it likes with the elements. + */ + H5_GCC_CLANG_DIAG_OFF("cast-qual") + if (op) + (void)(op)(node->item, (void *)node->key, op_data); + H5_GCC_CLANG_DIAG_ON("cast-qual") node->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[node->log_nalloc], node->forward); - node = H5FL_FREE(H5SL_node_t, node); - node = next_node; - } /* end while */ + node = H5FL_FREE(H5SL_node_t, node); + node = next_node; + } /* 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]))) + 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]))) HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, FAIL, "memory allocation failed") slist->header->forward[0] = NULL; slist->header->log_nalloc = 0; - slist->header->level = 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) -} /* end H5SL_release_common() */ +} /* end H5SL__release_common() */ - /*-------------------------------------------------------------------------- NAME - H5SL_close_common + H5SL__close_common PURPOSE Close a skip list, deallocating it and potentially freeing all its nodes. USAGE - herr_t H5SL_close_common(slist,op,opdata) + herr_t H5SL__close_common(slist,op,opdata) H5SL_t *slist; IN/OUT: Pointer to skip list to close H5SL_operator_t op; IN: Callback function to free item & key void *op_data; IN/OUT: Pointer to application data for callback @@ -824,11 +867,11 @@ done: REVISION LOG --------------------------------------------------------------------------*/ static herr_t -H5SL_close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data) +H5SL__close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data) { herr_t ret_value = SUCCEED; - FUNC_ENTER_NOAPI_NOINIT + FUNC_ENTER_PACKAGE /* Check args */ HDassert(slist); @@ -837,11 +880,12 @@ H5SL_close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data) /* (Pre-condition) */ /* Free skip list nodes */ - if(H5SL_release_common(slist, op, op_data) < 0) + if (H5SL__release_common(slist, op, op_data) < 0) HGOTO_ERROR(H5E_SLIST, H5E_CANTFREE, FAIL, "can't release skip list nodes") /* Release header node */ - slist->header->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[slist->header->log_nalloc], slist->header->forward); + slist->header->forward = + (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[slist->header->log_nalloc], slist->header->forward); slist->header = H5FL_FREE(H5SL_node_t, slist->header); /* Free skip list object */ @@ -849,9 +893,8 @@ H5SL_close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data) done: FUNC_LEAVE_NOAPI(ret_value) -} /* end H5SL_close_common() */ +} /* end H5SL__close_common() */ - /*-------------------------------------------------------------------------- NAME H5SL_create @@ -872,9 +915,9 @@ done: H5SL_t * H5SL_create(H5SL_type_t type, H5SL_cmp_t cmp) { - H5SL_t *new_slist = NULL; /* Pointer to new skip list object created */ - H5SL_node_t *header; /* Pointer to skip list header node */ - H5SL_t *ret_value; /* Return value */ + H5SL_t *new_slist = NULL; /* Pointer to new skip list object created */ + H5SL_node_t *header; /* Pointer to skip list header node */ + H5SL_t *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI(NULL) @@ -882,7 +925,7 @@ H5SL_create(H5SL_type_t type, H5SL_cmp_t cmp) HDassert(type >= H5SL_TYPE_INT && type <= H5SL_TYPE_GENERIC); /* Allocate skip list structure */ - if(NULL == (new_slist = H5FL_MALLOC(H5SL_t))) + if (NULL == (new_slist = H5FL_MALLOC(H5SL_t))) HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "memory allocation failed") /* Set the static internal fields */ @@ -892,11 +935,11 @@ 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->nobjs = 0; /* Allocate the header node */ - if(NULL == (header = H5SL_new_node(NULL, NULL, (uint32_t)ULONG_MAX))) - HGOTO_ERROR(H5E_SLIST ,H5E_NOSPACE, NULL, "can't create new skip list node") + if (NULL == (header = H5SL__new_node(NULL, NULL, (uint32_t)ULONG_MAX))) + HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "can't create new skip list node") /* Initialize header node's forward pointer */ header->forward[0] = NULL; @@ -906,22 +949,21 @@ H5SL_create(H5SL_type_t type, H5SL_cmp_t cmp) /* Attach the header */ new_slist->header = header; - new_slist->last = header; + new_slist->last = header; /* Set the return value */ ret_value = new_slist; done: /* Error cleanup */ - if(ret_value == NULL) { - if(new_slist != NULL) + if (ret_value == NULL) { + if (new_slist != NULL) new_slist = H5FL_FREE(H5SL_t, new_slist); - } /* end if */ + } FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_create() */ - /*-------------------------------------------------------------------------- NAME H5SL_count @@ -954,7 +996,6 @@ H5SL_count(H5SL_t *slist) FUNC_LEAVE_NOAPI(slist->nobjs) } /* end H5SL_count() */ - /*-------------------------------------------------------------------------- NAME H5SL_insert @@ -979,7 +1020,7 @@ H5SL_count(H5SL_t *slist) herr_t H5SL_insert(H5SL_t *slist, void *item, const void *key) { - herr_t ret_value=SUCCEED; /* Return value */ + herr_t ret_value = SUCCEED; /* Return value */ FUNC_ENTER_NOAPI_NOINIT @@ -991,14 +1032,13 @@ H5SL_insert(H5SL_t *slist, void *item, const void *key) /* (Pre-condition) */ /* Insert item into skip list */ - if(H5SL_insert_common(slist,item,key)==NULL) - HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,FAIL,"can't create new skip list node") + if (NULL == H5SL__insert_common(slist, item, key)) + HGOTO_ERROR(H5E_SLIST, H5E_CANTINSERT, FAIL, "can't create new skip list node") done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_insert() */ - /*-------------------------------------------------------------------------- NAME H5SL_add @@ -1026,7 +1066,7 @@ done: H5SL_node_t * H5SL_add(H5SL_t *slist, void *item, const void *key) { - H5SL_node_t *ret_value; /* Return value */ + H5SL_node_t *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI_NOINIT @@ -1038,14 +1078,13 @@ H5SL_add(H5SL_t *slist, void *item, const void *key) /* (Pre-condition) */ /* Insert item into skip list */ - if((ret_value=H5SL_insert_common(slist,item,key))==NULL) - HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,NULL,"can't create new skip list node") + if (NULL == (ret_value = H5SL__insert_common(slist, item, key))) + HGOTO_ERROR(H5E_SLIST, H5E_CANTINSERT, NULL, "can't create new skip list node") done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_add() */ - /*-------------------------------------------------------------------------- NAME H5SL_remove @@ -1068,9 +1107,9 @@ done: void * H5SL_remove(H5SL_t *slist, const void *key) { - H5SL_node_t *x; /* Current node to examine */ - uint32_t hashval = 0; /* Hash value for key */ - void *ret_value = NULL; /* Return value */ + H5SL_node_t *x; /* Current node to examine */ + uint32_t hashval = 0; /* Hash value for key */ + void *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI_NOINIT @@ -1087,7 +1126,7 @@ H5SL_remove(H5SL_t *slist, const void *key) * level that is before the location to remove */ x = slist->header; - switch(slist->type) { + switch (slist->type) { case H5SL_TYPE_INT: H5SL_REMOVE(SCALAR, slist, x, const int, key, -) break; @@ -1126,13 +1165,12 @@ H5SL_remove(H5SL_t *slist, const void *key) default: HDassert(0 && "Unknown skiplist type!"); - } /* end switch */ + } done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_remove() */ - /*-------------------------------------------------------------------------- NAME H5SL_remove_first @@ -1154,25 +1192,29 @@ done: void * H5SL_remove_first(H5SL_t *slist) { - void *ret_value = NULL; /* Return value */ - H5SL_node_t *head = slist->header; /* Skip list header */ - H5SL_node_t *tmp = slist->header->forward[0]; /* Temporary node pointer */ - H5SL_node_t *next; /* Next node to search for */ - size_t level = slist->curr_level; /* Skip list level */ - size_t i; /* Index */ + void *ret_value = NULL; /* Return value */ + H5SL_node_t *head = slist->header; /* Skip list header */ + H5SL_node_t *tmp = slist->header->forward[0]; /* Temporary node pointer */ + H5SL_node_t *next; /* Next node to search for */ + size_t level; /* Skip list level */ + size_t i; /* Index */ FUNC_ENTER_NOAPI_NOINIT /* Check args */ HDassert(slist); + /* Assign level */ + H5_CHECK_OVERFLOW(slist->curr_level, int, size_t); + level = (size_t)slist->curr_level; + /* Check internal consistency */ /* (Pre-condition) */ /* Remove item from skip list */ /* Check for empty list */ - if(slist->last != slist->header) { + if (slist->last != slist->header) { /* Assign return value */ ret_value = tmp->item; @@ -1181,58 +1223,59 @@ H5SL_remove_first(H5SL_t *slist) /* Remove the first node */ head->forward[0] = tmp->forward[0]; - if(slist->last == tmp) + if (slist->last == tmp) slist->last = head; else tmp->forward[0]->backward = head; slist->nobjs--; /* Free memory */ tmp->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[0], tmp->forward); - tmp = H5FL_FREE(H5SL_node_t, tmp); + tmp = H5FL_FREE(H5SL_node_t, tmp); /* Reshape the skip list as necessary to maintain 1-2-3 condition */ - for(i=0; i < level; i++) { - next = head->forward[i+1]; + for (i = 0; i < level; i++) { + next = head->forward[i + 1]; HDassert(next); /* Check if head->forward[i] == head->forward[i+1] (illegal) */ - if(head->forward[i] == next) { - tmp = next; - next = next->forward[i+1]; + if (head->forward[i] == next) { + tmp = next; + next = next->forward[i + 1]; - HDassert(tmp->level == i+1); + HDassert(tmp->level == i + 1); /* Demote head->forward[i] */ H5SL_DEMOTE(tmp, head) /* Check if we need to promote the following node to maintain * 1-2-3 condition */ - if(tmp->forward[i]->forward[i] != next) { + if (tmp->forward[i]->forward[i] != next) { HDassert(tmp->forward[i]->forward[i]->forward[i] == next || - tmp->forward[i]->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 */ break; - } else if(!head->forward[i+1]) { + } + else if (!head->forward[i + 1]) { /* We just shrunk the largest node, shrink the header */ HDassert(i == level - 1); H5SL_SHRINK(head, level) slist->curr_level--; - } /* end else */ - } else + } + } + else break; - } /* end for */ - } /* end if */ + } + } done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_remove_first() */ - /*-------------------------------------------------------------------------- NAME H5SL_search @@ -1255,9 +1298,9 @@ done: void * H5SL_search(H5SL_t *slist, const void *key) { - H5SL_node_t *x; /* Current node to examine */ - uint32_t hashval = 0; /* Hash value for key */ - void *ret_value; /* Return value */ + H5SL_node_t *x; /* Current node to examine */ + uint32_t hashval = 0; /* Hash value for key */ + void *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI_NOINIT_NOERR @@ -1273,8 +1316,8 @@ H5SL_search(H5SL_t *slist, const void *key) /* Work through the forward pointers for a node, finding the node at each * level that is before the location to insert */ - x=slist->header; - switch(slist->type) { + x = slist->header; + switch (slist->type) { case H5SL_TYPE_INT: H5SL_SEARCH(SCALAR, slist, x, const int, key, -) break; @@ -1313,16 +1356,15 @@ H5SL_search(H5SL_t *slist, const void *key) default: HDassert(0 && "Unknown skiplist type!"); - } /* end switch */ + } /* 'key' must not have been found in list, if we get here */ - ret_value=NULL; + ret_value = NULL; done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_search() */ - /*-------------------------------------------------------------------------- NAME H5SL_less @@ -1348,9 +1390,9 @@ done: void * H5SL_less(H5SL_t *slist, const void *key) { - H5SL_node_t *x; /* Current node to examine */ - uint32_t hashval = 0; /* Hash value for key */ - void *ret_value; /* Return value */ + H5SL_node_t *x; /* Current node to examine */ + uint32_t hashval = 0; /* Hash value for key */ + void *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI_NOINIT_NOERR @@ -1366,8 +1408,8 @@ H5SL_less(H5SL_t *slist, const void *key) /* Work through the forward pointers for a node, finding the node at each * level that is before the location to insert */ - x=slist->header; - switch(slist->type) { + x = slist->header; + switch (slist->type) { case H5SL_TYPE_INT: H5SL_SEARCH(SCALAR, slist, x, const int, key, -) break; @@ -1406,29 +1448,28 @@ H5SL_less(H5SL_t *slist, const void *key) default: HDassert(0 && "Unknown skiplist type!"); - } /* end switch */ + } /* An exact match for 'key' must not have been found in list, if we get here */ /* Check for a node with a key that is less than the given 'key' */ - if(x==NULL) { + if (x == NULL) { /* Check for walking off the list */ - if(slist->last!=slist->header) - ret_value=slist->last->item; + if (slist->last != slist->header) + ret_value = slist->last->item; else - ret_value=NULL; - } /* end if */ + ret_value = NULL; + } else { - if(x->backward!=slist->header) - ret_value=x->backward->item; + if (x->backward != slist->header) + ret_value = x->backward->item; else - ret_value=NULL; - } /* end else */ + ret_value = NULL; + } done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_less() */ - /*-------------------------------------------------------------------------- NAME H5SL_greater @@ -1454,9 +1495,9 @@ done: void * H5SL_greater(H5SL_t *slist, const void *key) { - H5SL_node_t *x; /* Current node to examine */ - uint32_t hashval = 0; /* Hash value for key */ - void *ret_value; /* Return value */ + H5SL_node_t *x; /* Current node to examine */ + uint32_t hashval = 0; /* Hash value for key */ + void *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI_NOINIT_NOERR @@ -1473,7 +1514,7 @@ H5SL_greater(H5SL_t *slist, const void *key) * level that is before the location to insert */ x = slist->header; - switch(slist->type) { + switch (slist->type) { case H5SL_TYPE_INT: H5SL_SEARCH(SCALAR, slist, x, const int, key, -) break; @@ -1512,11 +1553,11 @@ H5SL_greater(H5SL_t *slist, const void *key) default: HDassert(0 && "Unknown skiplist type!"); - } /* end switch */ + } /* An exact match for 'key' must not have been found in list, if we get here */ /* ('x' must be the next node with a key greater than the 'key', or NULL) */ - if(x) + if (x) ret_value = x->item; else ret_value = NULL; @@ -1525,7 +1566,6 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_greater() */ - /*-------------------------------------------------------------------------- NAME H5SL_find @@ -1550,9 +1590,9 @@ done: H5SL_node_t * H5SL_find(H5SL_t *slist, const void *key) { - H5SL_node_t *x; /* Current node to examine */ - uint32_t hashval = 0; /* Hash value for key */ - H5SL_node_t *ret_value; /* Return value */ + H5SL_node_t *x; /* Current node to examine */ + uint32_t hashval = 0; /* Hash value for key */ + H5SL_node_t *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI_NOINIT_NOERR @@ -1568,8 +1608,8 @@ H5SL_find(H5SL_t *slist, const void *key) /* Work through the forward pointers for a node, finding the node at each * level that is before the location to insert */ - x=slist->header; - switch(slist->type) { + x = slist->header; + switch (slist->type) { case H5SL_TYPE_INT: H5SL_FIND(SCALAR, slist, x, const int, key, -) break; @@ -1608,16 +1648,15 @@ H5SL_find(H5SL_t *slist, const void *key) default: HDassert(0 && "Unknown skiplist type!"); - } /* end switch */ + } /* 'key' must not have been found in list, if we get here */ - ret_value=NULL; + ret_value = NULL; done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_find() */ - /*-------------------------------------------------------------------------- NAME H5SL_below @@ -1643,9 +1682,9 @@ done: H5SL_node_t * H5SL_below(H5SL_t *slist, const void *key) { - H5SL_node_t *x; /* Current node to examine */ - uint32_t hashval = 0; /* Hash value for key */ - H5SL_node_t *ret_value; /* Return value */ + H5SL_node_t *x; /* Current node to examine */ + uint32_t hashval = 0; /* Hash value for key */ + H5SL_node_t *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI_NOINIT_NOERR @@ -1662,7 +1701,7 @@ H5SL_below(H5SL_t *slist, const void *key) * level that is before the location to insert */ x = slist->header; - switch(slist->type) { + switch (slist->type) { case H5SL_TYPE_INT: H5SL_FIND(SCALAR, slist, x, const int, key, -) break; @@ -1701,29 +1740,28 @@ H5SL_below(H5SL_t *slist, const void *key) default: HDassert(0 && "Unknown skiplist type!"); - } /* end switch */ + } /* An exact match for 'key' must not have been found in list, if we get here */ /* Check for a node with a key that is less than the given 'key' */ - if(NULL == x) { + if (NULL == x) { /* Check for walking off the list */ - if(slist->last != slist->header) + if (slist->last != slist->header) ret_value = slist->last; else ret_value = NULL; - } /* end if */ + } else { - if(x->backward != slist->header) + if (x->backward != slist->header) ret_value = x->backward; else ret_value = NULL; - } /* end else */ + } done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_below() */ - /*-------------------------------------------------------------------------- NAME H5SL_above @@ -1749,9 +1787,9 @@ done: H5SL_node_t * H5SL_above(H5SL_t *slist, const void *key) { - H5SL_node_t *x; /* Current node to examine */ - uint32_t hashval = 0; /* Hash value for key */ - H5SL_node_t *ret_value; /* Return value */ + H5SL_node_t *x; /* Current node to examine */ + uint32_t hashval = 0; /* Hash value for key */ + H5SL_node_t *ret_value = NULL; /* Return value */ FUNC_ENTER_NOAPI_NOINIT_NOERR @@ -1768,7 +1806,7 @@ H5SL_above(H5SL_t *slist, const void *key) * level that is before the location to insert */ x = slist->header; - switch(slist->type) { + switch (slist->type) { case H5SL_TYPE_INT: H5SL_FIND(SCALAR, slist, x, const int, key, -) break; @@ -1807,11 +1845,11 @@ H5SL_above(H5SL_t *slist, const void *key) default: HDassert(0 && "Unknown skiplist type!"); - } /* end switch */ + } /* An exact match for 'key' must not have been found in list, if we get here */ /* ('x' must be the next node with a key greater than the 'key', or NULL) */ - if(x) + if (x) ret_value = x; else ret_value = NULL; @@ -1820,7 +1858,6 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_above() */ - /*-------------------------------------------------------------------------- NAME H5SL_first @@ -1854,7 +1891,6 @@ H5SL_first(H5SL_t *slist) FUNC_LEAVE_NOAPI(slist->header->forward[0]) } /* end H5SL_first() */ - /*-------------------------------------------------------------------------- NAME H5SL_next @@ -1888,12 +1924,11 @@ H5SL_next(H5SL_node_t *slist_node) FUNC_LEAVE_NOAPI(slist_node->forward[0]) } /* end H5SL_next() */ - /*-------------------------------------------------------------------------- NAME H5SL_prev PURPOSE - Gets a pointer to the previos node in a skip list + Gets a pointer to the previous node in a skip list USAGE H5SL_node_t *H5SL_prev(slist_node) H5SL_node_t *slist_node; IN: Pointer to skip list node @@ -1920,10 +1955,9 @@ H5SL_prev(H5SL_node_t *slist_node) /* (Pre-condition) */ /* Walk backward, detecting the header node (which has it's key set to NULL) */ - FUNC_LEAVE_NOAPI(slist_node->backward->key==NULL ? NULL : slist_node->backward) + FUNC_LEAVE_NOAPI(slist_node->backward->key == NULL ? NULL : slist_node->backward) } /* end H5SL_prev() */ - /*-------------------------------------------------------------------------- NAME H5SL_last @@ -1955,10 +1989,9 @@ H5SL_last(H5SL_t *slist) /* (Pre-condition) */ /* Find last node, avoiding the header node */ - FUNC_LEAVE_NOAPI(slist->last==slist->header ? NULL : slist->last) + FUNC_LEAVE_NOAPI(slist->last == slist->header ? NULL : slist->last) } /* end H5SL_last() */ - /*-------------------------------------------------------------------------- NAME H5SL_item @@ -1991,7 +2024,6 @@ H5SL_item(H5SL_node_t *slist_node) FUNC_LEAVE_NOAPI(slist_node->item) } /* end H5SL_item() */ - /*-------------------------------------------------------------------------- NAME H5SL_iterate @@ -2028,9 +2060,9 @@ H5SL_item(H5SL_node_t *slist_node) herr_t H5SL_iterate(H5SL_t *slist, H5SL_operator_t op, void *op_data) { - H5SL_node_t *node; /* Pointer to current skip list node */ - H5SL_node_t *next; /* Pointer to next skip list node */ - herr_t ret_value = 0; /* Return value */ + H5SL_node_t *node; /* Pointer to current skip list node */ + H5SL_node_t *next; /* Pointer to next skip list node */ + herr_t ret_value = 0; /* Return value */ FUNC_ENTER_NOAPI_NOINIT_NOERR @@ -2042,23 +2074,29 @@ H5SL_iterate(H5SL_t *slist, H5SL_operator_t op, void *op_data) /* Free skip list nodes */ node = slist->header->forward[0]; - while(node != NULL) { + while (node != NULL) { /* Protect against the node being deleted by the callback */ next = node->forward[0]; - /* Call the iterator callback */ - /* Casting away const OK -QAK */ - if((ret_value = (op)(node->item, (void *)node->key, op_data)) != 0) + /* Call the iterator callback + * + * Ignoring const here is fine as we only need the value to be const + * with respect to the list code, which should never modify the + * elements. The library code that is making use of the skip list + * container can do what it likes with the elements. + */ + H5_GCC_CLANG_DIAG_OFF("cast-qual") + if ((ret_value = (op)(node->item, (void *)node->key, op_data)) != 0) break; + H5_GCC_CLANG_DIAG_ON("cast-qual") /* Advance to next node */ node = next; - } /* end while */ + } FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_iterate() */ - /*-------------------------------------------------------------------------- NAME H5SL_release @@ -2082,7 +2120,9 @@ H5SL_iterate(H5SL_t *slist, H5SL_operator_t op, void *op_data) herr_t H5SL_release(H5SL_t *slist) { - FUNC_ENTER_NOAPI_NOINIT_NOERR + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI(FAIL) /* Check args */ HDassert(slist); @@ -2091,12 +2131,13 @@ H5SL_release(H5SL_t *slist) /* (Pre-condition) */ /* Free skip list nodes */ - H5SL_release_common(slist,NULL,NULL); /* always succeeds */ + if (H5SL__release_common(slist, NULL, NULL) < 0) + HGOTO_ERROR(H5E_SLIST, H5E_CANTFREE, FAIL, "can't release skip list nodes") - FUNC_LEAVE_NOAPI(SUCCEED) +done: + FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_release() */ - /*-------------------------------------------------------------------------- NAME H5SL_free @@ -2128,7 +2169,9 @@ H5SL_release(H5SL_t *slist) herr_t H5SL_free(H5SL_t *slist, H5SL_operator_t op, void *op_data) { - FUNC_ENTER_NOAPI_NOINIT_NOERR + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI(FAIL) /* Check args */ HDassert(slist); @@ -2137,12 +2180,13 @@ H5SL_free(H5SL_t *slist, H5SL_operator_t op, void *op_data) /* (Pre-condition) */ /* Free skip list nodes */ - H5SL_release_common(slist,op,op_data); /* always succeeds */ + if (H5SL__release_common(slist, op, op_data) < 0) + HGOTO_ERROR(H5E_SLIST, H5E_CANTFREE, FAIL, "can't release skip list nodes") - FUNC_LEAVE_NOAPI(SUCCEED) +done: + FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_free() */ - /*-------------------------------------------------------------------------- NAME H5SL_destroy @@ -2172,9 +2216,9 @@ H5SL_free(H5SL_t *slist, H5SL_operator_t op, void *op_data) herr_t H5SL_destroy(H5SL_t *slist, H5SL_operator_t op, void *op_data) { - herr_t ret_value=SUCCEED; /* Return value */ + herr_t ret_value = SUCCEED; /* Return value */ - FUNC_ENTER_NOAPI_NOINIT_NOERR + FUNC_ENTER_NOAPI_NOINIT /* Check args */ HDassert(slist); @@ -2183,12 +2227,13 @@ H5SL_destroy(H5SL_t *slist, H5SL_operator_t op, void *op_data) /* (Pre-condition) */ /* Close skip list */ - (void)H5SL_close_common(slist,op,op_data); /* always succeeds */ + if (H5SL__close_common(slist, op, op_data) < 0) + HGOTO_ERROR(H5E_SLIST, H5E_CANTCLOSEOBJ, FAIL, "can't close skip list") +done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_destroy() */ - /*-------------------------------------------------------------------------- NAME H5SL_close @@ -2211,7 +2256,9 @@ H5SL_destroy(H5SL_t *slist, H5SL_operator_t op, void *op_data) herr_t H5SL_close(H5SL_t *slist) { - FUNC_ENTER_NOAPI_NOINIT_NOERR + herr_t ret_value = SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI_NOINIT /* Check args */ HDassert(slist); @@ -2220,55 +2267,9 @@ H5SL_close(H5SL_t *slist) /* (Pre-condition) */ /* Close skip list */ - (void)H5SL_close_common(slist,NULL,NULL); /* always succeeds */ + if (H5SL__close_common(slist, NULL, NULL) < 0) + HGOTO_ERROR(H5E_SLIST, H5E_CANTCLOSEOBJ, FAIL, "can't close skip list") - FUNC_LEAVE_NOAPI(SUCCEED) +done: + FUNC_LEAVE_NOAPI(ret_value) } /* end H5SL_close() */ - - -/*-------------------------------------------------------------------------- - NAME - H5SL_term_interface - PURPOSE - Terminate all the H5FL factories used in this package, and clear memory - USAGE - int H5SL_term_interface() - RETURNS - Success: Positive if any action might have caused a change in some - other interface; zero otherwise. - Failure: Negative - DESCRIPTION - Release any resources allocated. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - Can't report errors... - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -int H5SL_term_interface(void) -{ - size_t i; - herr_t ret; - int n = H5_interface_initialize_g ? 1 : 0; - - FUNC_ENTER_NOAPI_NOINIT_NOERR - - if(n) { - /* Terminate all the factories */ - for(i=0; i<H5SL_fac_nused_g; i++) { - ret = H5FL_fac_term(H5SL_fac_g[i]); - HDassert(ret >= 0); - } - H5SL_fac_nused_g = 0; - - /* Free the list of factories */ - H5SL_fac_g = (H5FL_fac_head_t **)H5MM_xfree((void *)H5SL_fac_g); - H5SL_fac_nalloc_g = 0; - - /* Mark the interface as uninitialized */ - H5_interface_initialize_g = 0; - } /* end if */ - - FUNC_LEAVE_NOAPI(n) -} /* H5SL_term_interface() */ - |