summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2004-12-30 16:26:45 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2004-12-30 16:26:45 (GMT)
commit7fae6be03c428a29bdeb9586663a3193e2268bf5 (patch)
treeda94aadd11293e088ef8af6741b2f0bffc6f0b59
parenta56a1205d25b9184d628a30886ed4a0801d3ec94 (diff)
downloadhdf5-7fae6be03c428a29bdeb9586663a3193e2268bf5.zip
hdf5-7fae6be03c428a29bdeb9586663a3193e2268bf5.tar.gz
hdf5-7fae6be03c428a29bdeb9586663a3193e2268bf5.tar.bz2
[svn-r9734] Purpose:
Code cleanup Description: Convert chunk iteration code to use skip lists instead of threaded, balanced binary trees. Platforms tested: FreeBSD 4.10 (sleipnir) w/parallel & szip Too minor to require h5committest
-rw-r--r--src/H5Dio.c203
-rw-r--r--src/H5P.c4
-rw-r--r--src/H5SL.c33
-rw-r--r--src/H5SLprivate.h5
-rw-r--r--test/cache.c1
-rw-r--r--test/tskiplist.c58
6 files changed, 183 insertions, 121 deletions
diff --git a/src/H5Dio.c b/src/H5Dio.c
index 7e8e1a0..24302b2 100644
--- a/src/H5Dio.c
+++ b/src/H5Dio.c
@@ -25,7 +25,7 @@
#include "H5Iprivate.h" /* IDs */
#include "H5MMprivate.h" /* Memory management */
#include "H5Sprivate.h" /* Dataspace functions */
-#include "H5TBprivate.h" /* Threaded, balanced, binary trees (TBBTs) */
+#include "H5SLprivate.h" /* Skip lists */
#include "H5Vprivate.h" /* Vector and array functions */
/*#define H5D_DEBUG*/
@@ -35,13 +35,16 @@
# include "H5Rpublic.h"
#endif /*H5_HAVE_PARALLEL*/
+/* Local macros */
+#define H5D_DEFAULT_SKIPLIST_HEIGHT 8
+
/* Local typedefs */
/* Information for mapping between file space and memory space */
/* Structure holding information about a chunk's selection for mapping */
typedef struct H5D_chunk_info_t {
- hsize_t index; /* "Index" of chunk in dataset (must be first for TBBT routines) */
+ hsize_t index; /* "Index" of chunk in dataset */
size_t chunk_points; /* Number of elements selected in chunk */
H5S_t *fspace; /* Dataspace describing chunk & selection in it */
hsize_t coords[H5O_LAYOUT_NDIMS]; /* Coordinates of chunk in file dataset's dataspace */
@@ -51,7 +54,7 @@ typedef struct H5D_chunk_info_t {
/* Main structure holding the mapping between file chunks and memory */
typedef struct fm_map {
- H5TB_TREE *fsel; /* TBBT containing file dataspaces for all chunks */
+ H5SL_t *fsel; /* Skip list containing file dataspaces for all chunks */
hsize_t last_index; /* Index of last chunk operated on */
H5D_chunk_info_t *last_chunk_info; /* Pointer to last chunk's info */
const H5S_t *file_space; /* Pointer to the file dataspace */
@@ -120,7 +123,7 @@ H5D_ioinfo_init(H5D_t *dset, const H5D_dxpl_cache_t *dxpl_cache, hid_t dxpl_id,
static herr_t H5D_create_chunk_map(const H5D_t *dataset, const H5T_t *mem_type,
const H5S_t *file_space, const H5S_t *mem_space, fm_map *fm);
static herr_t H5D_destroy_chunk_map(const fm_map *fm);
-static void H5D_free_chunk_info(void *chunk_info);
+static herr_t H5D_free_chunk_info(void *item, void UNUSED *key, void UNUSED *opdata);
static herr_t H5D_create_chunk_file_map_hyper(const fm_map *fm);
static herr_t H5D_create_chunk_mem_map_hyper(const fm_map *fm);
static herr_t H5D_chunk_file_cb(void *elem, hid_t type_id, unsigned ndims,
@@ -1630,7 +1633,7 @@ H5D_chunk_read(H5D_io_info_t *io_info, hsize_t nelmts,
H5D_t *dataset=io_info->dset; /* Local pointer to dataset info */
const H5D_dxpl_cache_t *dxpl_cache=io_info->dxpl_cache; /* Local pointer to dataset transfer info */
fm_map fm; /* File<->memory mapping */
- H5TB_NODE *chunk_node; /* Current node in chunk TBBT */
+ H5SL_node_t *chunk_node; /* Current node in chunk skip list */
herr_t status; /*function return status*/
#ifdef H5S_DEBUG
H5_timer_t timer;
@@ -1677,15 +1680,15 @@ H5D_chunk_read(H5D_io_info_t *io_info, hsize_t nelmts,
|| dataset->shared->efl.nused>0 || 0 == nelmts
|| dataset->shared->layout.type==H5D_COMPACT);
- /* Get first node in chunk tree */
- chunk_node=H5TB_first(fm.fsel->root);
+ /* Get first node in chunk skip list */
+ chunk_node=H5SL_first(fm.fsel);
/* Iterate through chunks to be operated on */
while(chunk_node) {
H5D_chunk_info_t *chunk_info; /* chunk information */
- /* Get the actual chunk information from the tree node */
- chunk_info=chunk_node->data;
+ /* Get the actual chunk information from the skip list node */
+ chunk_info=H5SL_item(chunk_node);
/* Pass in chunk's coordinates in a union. */
store.chunk.offset = chunk_info->coords;
@@ -1701,8 +1704,8 @@ H5D_chunk_read(H5D_io_info_t *io_info, hsize_t nelmts,
if (status<0)
HGOTO_ERROR(H5E_DATASET, H5E_READERROR, FAIL, "optimized read failed")
- /* Get the next chunk node in the tree */
- chunk_node=H5TB_next(chunk_node);
+ /* Get the next chunk node in the skip list */
+ chunk_node=H5SL_next(chunk_node);
} /* end while */
#ifdef H5S_DEBUG
@@ -1775,15 +1778,15 @@ H5D_chunk_read(H5D_io_info_t *io_info, hsize_t nelmts,
/* Loop over all the chunks, performing I/O on each */
- /* Get first node in chunk tree */
- chunk_node=H5TB_first(fm.fsel->root);
+ /* Get first node in chunk skip list */
+ chunk_node=H5SL_first(fm.fsel);
/* Iterate through chunks to be operated on */
while(chunk_node) {
H5D_chunk_info_t *chunk_info; /* chunk information */
- /* Get the actual chunk information from the tree nodes */
- chunk_info=chunk_node->data;
+ /* Get the actual chunk information from the skip list nodes */
+ chunk_info=H5SL_item(chunk_node);
/* initialize selection iterator */
if (H5S_select_iter_init(&file_iter, chunk_info->fspace, src_type_size)<0)
@@ -1890,8 +1893,8 @@ H5D_chunk_read(H5D_io_info_t *io_info, hsize_t nelmts,
bkg_iter_init=0;
} /* end if */
- /* Get the next chunk node in the tree */
- chunk_node=H5TB_next(chunk_node);
+ /* Get the next chunk node in the skip list */
+ chunk_node=H5SL_next(chunk_node);
} /* end while */
done:
@@ -1949,7 +1952,7 @@ H5D_chunk_write(H5D_io_info_t *io_info, hsize_t nelmts,
H5D_t *dataset=io_info->dset; /* Local pointer to dataset info */
const H5D_dxpl_cache_t *dxpl_cache=io_info->dxpl_cache; /* Local pointer to dataset transfer info */
fm_map fm; /* File<->memory mapping */
- H5TB_NODE *chunk_node; /* Current node in chunk TBBT */
+ H5SL_node_t *chunk_node; /* Current node in chunk skip list */
herr_t status; /*function return status*/
#ifdef H5S_DEBUG
H5_timer_t timer;
@@ -1990,15 +1993,15 @@ H5D_chunk_write(H5D_io_info_t *io_info, hsize_t nelmts,
#ifdef H5S_DEBUG
H5_timer_begin(&timer);
#endif
- /* Get first node in chunk tree */
- chunk_node=H5TB_first(fm.fsel->root);
+ /* Get first node in chunk skip list */
+ chunk_node=H5SL_first(fm.fsel);
/* Iterate through chunks to be operated on */
while(chunk_node) {
H5D_chunk_info_t *chunk_info; /* chunk information */
- /* Get the actual chunk information from the tree node */
- chunk_info=chunk_node->data;
+ /* Get the actual chunk information from the skip list node */
+ chunk_info=H5SL_item(chunk_node);
/* Pass in chunk's coordinates in a union. */
store.chunk.offset = chunk_info->coords;
@@ -2014,8 +2017,8 @@ H5D_chunk_write(H5D_io_info_t *io_info, hsize_t nelmts,
if (status<0)
HGOTO_ERROR(H5E_DATASET, H5E_WRITEERROR, FAIL, "optimized write failed")
- /* Get the next chunk node in the tree */
- chunk_node=H5TB_next(chunk_node);
+ /* Get the next chunk node in the skip list */
+ chunk_node=H5SL_next(chunk_node);
} /* end while */
#ifdef H5S_DEBUG
@@ -2092,15 +2095,15 @@ H5D_chunk_write(H5D_io_info_t *io_info, hsize_t nelmts,
/* Loop over all the chunks, performing I/O on each */
- /* Get first node in chunk tree */
- chunk_node=H5TB_first(fm.fsel->root);
+ /* Get first node in chunk skip list */
+ chunk_node=H5SL_first(fm.fsel);
/* Iterate through chunks to be operated on */
while(chunk_node) {
H5D_chunk_info_t *chunk_info; /* chunk information */
- /* Get the actual chunk information from the tree node */
- chunk_info=chunk_node->data;
+ /* Get the actual chunk information from the skip list node */
+ chunk_info=H5SL_item(chunk_node);
/* initialize selection iterator */
if (H5S_select_iter_init(&file_iter, chunk_info->fspace, dst_type_size)<0)
@@ -2206,8 +2209,8 @@ H5D_chunk_write(H5D_io_info_t *io_info, hsize_t nelmts,
bkg_iter_init=0;
} /* end if */
- /* Get the next chunk node in the tree */
- chunk_node=H5TB_next(chunk_node);
+ /* Get the next chunk node in the skip list */
+ chunk_node=H5SL_next(chunk_node);
} /* end while */
done:
@@ -2362,7 +2365,7 @@ H5D_create_chunk_map(const H5D_t *dataset, const H5T_t *mem_type, const H5S_t *f
hbool_t iter_init=0; /* Selection iteration info has been initialized */
unsigned f_ndims; /* The number of dimensions of the file's dataspace */
int sm_ndims; /* The number of dimensions of the memory buffer's dataspace (signed) */
- H5TB_NODE *curr_node; /* Current node in TBBT */
+ H5SL_node_t *curr_node; /* Current node in skip list */
H5S_sel_type fsel_type; /* Selection type on disk */
char bogus; /* "bogus" buffer to pass to selection iterator */
unsigned u; /* Local index variable */
@@ -2417,9 +2420,9 @@ H5D_create_chunk_map(const H5D_t *dataset, const H5T_t *mem_type, const H5S_t *f
if(H5V_array_down(f_ndims,fm->chunks,fm->down_chunks)<0)
HGOTO_ERROR (H5E_INTERNAL, H5E_BADVALUE, FAIL, "can't compute 'down' sizes")
- /* Initialize TBBT for chunk selections */
- if((fm->fsel=H5TB_fast_dmake(H5TB_FAST_HSIZE_COMPARE))==NULL)
- HGOTO_ERROR(H5E_DATASET,H5E_CANTMAKETREE,FAIL,"can't create TBBT for chunk selections")
+ /* Initialize skip list for chunk selections */
+ if((fm->fsel=H5SL_create(H5SL_TYPE_HSIZE,0.5,H5D_DEFAULT_SKIPLIST_HEIGHT))==NULL)
+ HGOTO_ERROR(H5E_DATASET,H5E_CANTMAKETREE,FAIL,"can't create skip list for chunk selections")
/* Initialize "last chunk" information */
fm->last_index=(hsize_t)-1;
@@ -2456,20 +2459,20 @@ H5D_create_chunk_map(const H5D_t *dataset, const H5T_t *mem_type, const H5S_t *f
HGOTO_ERROR (H5E_DATASET, H5E_CANTINIT, FAIL, "unable to create file chunk selections")
/* Clean file chunks' hyperslab span "scratch" information */
- curr_node=H5TB_first(fm->fsel->root);
+ curr_node=H5SL_first(fm->fsel);
while(curr_node) {
H5D_chunk_info_t *chunk_info; /* Pointer chunk information */
/* Get pointer to chunk's information */
- chunk_info=curr_node->data;
+ chunk_info=H5SL_item(curr_node);
assert(chunk_info);
/* Clean hyperslab span's "scratch" information */
if(H5S_hyper_reset_scratch(chunk_info->fspace)<0)
HGOTO_ERROR (H5E_DATASET, H5E_CANTFREE, FAIL, "unable to reset span scratch info")
- /* Get the next chunk node in the TBBT */
- curr_node=H5TB_next(curr_node);
+ /* Get the next chunk node in the skip list */
+ curr_node=H5SL_next(curr_node);
} /* end while */
} /* end else */
@@ -2518,20 +2521,20 @@ H5D_create_chunk_map(const H5D_t *dataset, const H5T_t *mem_type, const H5S_t *f
/* Clean up hyperslab stuff, if necessary */
if(fm->msel_type!=H5S_SEL_POINTS) {
/* Clean memory chunks' hyperslab span "scratch" information */
- curr_node=H5TB_first(fm->fsel->root);
+ curr_node=H5SL_first(fm->fsel);
while(curr_node) {
H5D_chunk_info_t *chunk_info; /* Pointer chunk information */
/* Get pointer to chunk's information */
- chunk_info=curr_node->data;
+ chunk_info=H5SL_item(curr_node);
assert(chunk_info);
/* Clean hyperslab span's "scratch" information */
if(H5S_hyper_reset_scratch(chunk_info->mspace)<0)
HGOTO_ERROR (H5E_DATASET, H5E_CANTFREE, FAIL, "unable to reset span scratch info")
- /* Get the next chunk node in the TBBT */
- curr_node=H5TB_next(curr_node);
+ /* Get the next chunk node in the skip list */
+ curr_node=H5SL_next(curr_node);
} /* end while */
} /* end if */
} /* end else */
@@ -2573,24 +2576,23 @@ done:
NAME
H5D_free_chunk_info
PURPOSE
- Internal routine to destroy a chunk info node (Wrapper for compatibility
- with H5TB_dfree)
+ Internal routine to destroy a chunk info node
USAGE
void H5D_free_chunk_info(chunk_info)
void *chunk_info; IN: Pointer to chunk info to destroy
RETURNS
No return value
DESCRIPTION
- Releases all the memory for a chunk info node.
+ Releases all the memory for a chunk info node. Called by H5SL_iterate
GLOBAL VARIABLES
COMMENTS, BUGS, ASSUMPTIONS
EXAMPLES
REVISION LOG
--------------------------------------------------------------------------*/
-static void
-H5D_free_chunk_info(void *_chunk_info)
+static herr_t
+H5D_free_chunk_info(void *item, void UNUSED *key, void UNUSED *opdata)
{
- H5D_chunk_info_t *chunk_info=(H5D_chunk_info_t *)_chunk_info;
+ H5D_chunk_info_t *chunk_info=(H5D_chunk_info_t *)item;
FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5D_free_chunk_info)
@@ -2606,7 +2608,7 @@ H5D_free_chunk_info(void *_chunk_info)
/* Free the actual chunk info */
H5FL_FREE(H5D_chunk_info_t,chunk_info);
- FUNC_LEAVE_NOAPI_VOID
+ FUNC_LEAVE_NOAPI(0);
} /* H5D_free_chunk_info() */
@@ -2631,9 +2633,14 @@ H5D_destroy_chunk_map(const fm_map *fm)
FUNC_ENTER_NOAPI_NOINIT(H5D_destroy_chunk_map)
- /* Free the chunk info tree */
- if(fm->fsel)
- H5TB_dfree(fm->fsel,H5D_free_chunk_info,NULL);
+ /* Free the chunk info skip list */
+ if(fm->fsel) {
+ if(H5SL_count(fm->fsel)>0)
+ if(H5SL_iterate(fm->fsel,H5D_free_chunk_info,NULL)<0)
+ HGOTO_ERROR(H5E_PLIST,H5E_CANTNEXT,FAIL,"can't iterate over chunks")
+
+ H5SL_close(fm->fsel);
+ } /* end if */
/* Free the memory chunk dataspace template */
if(fm->mchunk_tmpl)
@@ -2705,7 +2712,7 @@ H5D_create_chunk_file_map_hyper(const fm_map *fm)
/* (Casting away const OK - QAK) */
if(H5S_hyper_intersect_block((H5S_t *)fm->file_space,coords,end)==TRUE) {
H5S_t *tmp_fchunk; /* Temporary file dataspace */
- H5D_chunk_info_t *new_chunk_info; /* chunk information to insert into tree */
+ H5D_chunk_info_t *new_chunk_info; /* chunk information to insert into skip list */
hssize_t schunk_points; /* Number of elements in chunk selection */
/* Create "temporary" chunk for selection operations (copy file space) */
@@ -2767,10 +2774,10 @@ H5D_create_chunk_file_map_hyper(const fm_map *fm)
new_chunk_info->coords[u]=coords[u];
new_chunk_info->coords[fm->f_ndims]=0;
- /* Insert the new chunk into the TBBT tree */
- if(H5TB_dins(fm->fsel,new_chunk_info,new_chunk_info)==NULL) {
- H5D_free_chunk_info(new_chunk_info);
- HGOTO_ERROR(H5E_DATASPACE,H5E_CANTINSERT,FAIL,"can't insert chunk into TBBT")
+ /* Insert the new chunk into the skip list */
+ if(H5SL_insert(fm->fsel,new_chunk_info,&new_chunk_info->index)<0) {
+ H5D_free_chunk_info(new_chunk_info,NULL,NULL);
+ HGOTO_ERROR(H5E_DATASPACE,H5E_CANTINSERT,FAIL,"can't insert chunk into skip list")
} /* end if */
/* Get number of elements selected in chunk */
@@ -2845,10 +2852,10 @@ done:
static herr_t
H5D_create_chunk_mem_map_hyper(const fm_map *fm)
{
- H5TB_NODE *curr_node; /* Current node in TBBT */
- hsize_t file_sel_start[H5O_LAYOUT_NDIMS]; /* Offset of low bound of file selection */
- hsize_t file_sel_end[H5O_LAYOUT_NDIMS]; /* Offset of high bound of file selection */
- hsize_t mem_sel_start[H5O_LAYOUT_NDIMS]; /* Offset of low bound of file selection */
+ H5SL_node_t *curr_node; /* Current node in skip list */
+ hsize_t file_sel_start[H5O_LAYOUT_NDIMS]; /* Offset of low bound of file selection */
+ hsize_t file_sel_end[H5O_LAYOUT_NDIMS]; /* Offset of high bound of file selection */
+ hsize_t mem_sel_start[H5O_LAYOUT_NDIMS]; /* Offset of low bound of file selection */
hsize_t mem_sel_end[H5O_LAYOUT_NDIMS]; /* Offset of high bound of file selection */
hssize_t adjust[H5O_LAYOUT_NDIMS]; /* Adjustment to make to all file chunks */
hssize_t chunk_adjust[H5O_LAYOUT_NDIMS]; /* Adjustment to make to a particular chunk */
@@ -2861,14 +2868,14 @@ H5D_create_chunk_mem_map_hyper(const fm_map *fm)
assert(fm->f_ndims>0);
/* Check for all I/O going to a single chunk */
- if(H5TB_count(fm->fsel)==1) {
+ if(H5SL_count(fm->fsel)==1) {
H5D_chunk_info_t *chunk_info; /* Pointer to chunk information */
/* Get the node */
- curr_node=H5TB_first(fm->fsel->root);
+ curr_node=H5SL_first(fm->fsel);
/* Get pointer to chunk's information */
- chunk_info=curr_node->data;
+ chunk_info=H5SL_item(curr_node);
assert(chunk_info);
/* Check if it's OK to share dataspace */
@@ -2904,12 +2911,12 @@ H5D_create_chunk_mem_map_hyper(const fm_map *fm)
} /* end for */
/* Iterate over each chunk in the chunk list */
- curr_node=H5TB_first(fm->fsel->root);
+ curr_node=H5SL_first(fm->fsel);
while(curr_node) {
H5D_chunk_info_t *chunk_info; /* Pointer to chunk information */
/* Get pointer to chunk's information */
- chunk_info=curr_node->data;
+ chunk_info=H5SL_item(curr_node);
assert(chunk_info);
/* Copy the information */
@@ -2936,8 +2943,8 @@ H5D_create_chunk_mem_map_hyper(const fm_map *fm)
if(H5S_hyper_adjust_s(chunk_info->mspace,chunk_adjust)<0) /*lint !e772 The chunk_adjust array will always be initialized */
HGOTO_ERROR(H5E_DATASPACE, H5E_CANTSELECT, FAIL, "can't adjust chunk selection")
- /* Get the next chunk node in the TBBT */
- curr_node=H5TB_next(curr_node);
+ /* Get the next chunk node in the skip list */
+ curr_node=H5SL_next(curr_node);
} /* end while */
} /* end else */
@@ -2977,7 +2984,7 @@ H5D_chunk_file_cb(void UNUSED *elem, hid_t UNUSED type_id, unsigned ndims, const
if(H5V_chunk_index(ndims,coords,fm->layout->u.chunk.dim,fm->down_chunks,&chunk_index)<0)
HGOTO_ERROR (H5E_DATASPACE, H5E_BADRANGE, FAIL, "can't get chunk index")
- /* Find correct chunk in file & memory TBBTs */
+ /* Find correct chunk in file & memory skip list */
if(chunk_index==fm->last_index) {
/* If the chunk index is the same as the last chunk index we used,
* get the cached info to operate on.
@@ -2985,67 +2992,58 @@ H5D_chunk_file_cb(void UNUSED *elem, hid_t UNUSED type_id, unsigned ndims, const
chunk_info=fm->last_chunk_info;
} /* end if */
else {
- H5TB_NODE *chunk_node; /* TBBT node holding chunk information */
-
/* If the chunk index is not the same as the last chunk index we used,
- * find the chunk in the tree.
+ * find the chunk in the skip list.
*/
- /* Get the chunk node from the TBBT */
- if((chunk_node=H5TB_dfind(fm->fsel,&chunk_index,NULL))==NULL) {
- H5D_chunk_info_t *new_chunk_info; /* Chunk information to insert into tree */
+ /* Get the chunk node from the skip list */
+ if((chunk_info=H5SL_search(fm->fsel,&chunk_index))==NULL) {
H5S_t *fspace; /* Memory chunk's dataspace */
/* Allocate the file & memory chunk information */
- if (NULL==(new_chunk_info = H5FL_MALLOC (H5D_chunk_info_t)))
+ if (NULL==(chunk_info = H5FL_MALLOC (H5D_chunk_info_t)))
HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't allocate chunk info")
/* Initialize the chunk information */
/* Set the chunk index */
- new_chunk_info->index=chunk_index;
+ chunk_info->index=chunk_index;
/* Create a dataspace for the chunk */
if((fspace = H5S_create_simple(fm->f_ndims,fm->chunk_dim,NULL))==NULL) {
- H5FL_FREE(H5D_chunk_info_t,new_chunk_info);
+ H5FL_FREE(H5D_chunk_info_t,chunk_info);
HGOTO_ERROR (H5E_DATASPACE, H5E_CANTCREATE, FAIL, "unable to create dataspace for chunk")
} /* end if */
/* De-select the chunk space */
if(H5S_select_none(fspace)<0) {
(void)H5S_close(fspace);
- H5FL_FREE(H5D_chunk_info_t,new_chunk_info);
+ H5FL_FREE(H5D_chunk_info_t,chunk_info);
HGOTO_ERROR (H5E_DATASPACE, H5E_CANTINIT, FAIL, "unable to de-select dataspace")
} /* end if */
/* Set the file chunk dataspace */
- new_chunk_info->fspace=fspace;
+ chunk_info->fspace=fspace;
/* Set the memory chunk dataspace */
- new_chunk_info->mspace=NULL;
- new_chunk_info->mspace_shared=0;
+ chunk_info->mspace=NULL;
+ chunk_info->mspace_shared=0;
/* Set the number of selected elements in chunk to zero */
- new_chunk_info->chunk_points=0;
+ chunk_info->chunk_points=0;
/* Compute the chunk's coordinates */
for(u=0; u<fm->f_ndims; u++) {
H5_CHECK_OVERFLOW(fm->layout->u.chunk.dim[u],hsize_t,hssize_t);
- new_chunk_info->coords[u]=(coords[u]/(hssize_t)fm->layout->u.chunk.dim[u])*(hssize_t)fm->layout->u.chunk.dim[u];
+ chunk_info->coords[u]=(coords[u]/(hssize_t)fm->layout->u.chunk.dim[u])*(hssize_t)fm->layout->u.chunk.dim[u];
} /* end for */
- new_chunk_info->coords[fm->f_ndims]=0;
+ chunk_info->coords[fm->f_ndims]=0;
- /* Insert the new chunk into the TBBT tree */
- if(H5TB_dins(fm->fsel,new_chunk_info,new_chunk_info)==NULL) {
- H5D_free_chunk_info(new_chunk_info);
- HGOTO_ERROR(H5E_DATASPACE,H5E_CANTINSERT,FAIL,"can't insert chunk into TBBT")
+ /* Insert the new chunk into the skip list */
+ if(H5SL_insert(fm->fsel,chunk_info,&chunk_info->index)<0) {
+ H5D_free_chunk_info(chunk_info,NULL,NULL);
+ HGOTO_ERROR(H5E_DATASPACE,H5E_CANTINSERT,FAIL,"can't insert chunk into skip list")
} /* end if */
-
- /* Save the chunk info pointer */
- chunk_info=new_chunk_info;
} /* end if */
- else
- /* Get the information from the node */
- chunk_info=(H5D_chunk_info_t *)(chunk_node->data);
/* Update the "last chunk seen" information */
fm->last_index=chunk_index;
@@ -3101,7 +3099,7 @@ H5D_chunk_mem_cb(void UNUSED *elem, hid_t UNUSED type_id, unsigned ndims, const
if(H5V_chunk_index(ndims,coords,fm->layout->u.chunk.dim,fm->down_chunks,&chunk_index)<0)
HGOTO_ERROR (H5E_DATASPACE, H5E_BADRANGE, FAIL, "can't get chunk index")
- /* Find correct chunk in file & memory TBBTs */
+ /* Find correct chunk in file & memory skip list */
if(chunk_index==fm->last_index) {
/* If the chunk index is the same as the last chunk index we used,
* get the cached spaces to operate on.
@@ -3109,17 +3107,12 @@ H5D_chunk_mem_cb(void UNUSED *elem, hid_t UNUSED type_id, unsigned ndims, const
chunk_info=fm->last_chunk_info;
} /* end if */
else {
- H5TB_NODE *chunk_node; /* TBBT node holding chunk information */
-
/* If the chunk index is not the same as the last chunk index we used,
- * find the chunk in the tree.
+ * find the chunk in the skip list.
*/
- /* Get the chunk node from the TBBT */
- if((chunk_node=H5TB_dfind(fm->fsel,&chunk_index,NULL))==NULL)
- HGOTO_ERROR(H5E_DATASPACE,H5E_NOTFOUND,FAIL,"can't locate chunk in TBBT")
-
- /* Get the chunk info pointer */
- chunk_info=(H5D_chunk_info_t *)(chunk_node->data);
+ /* Get the chunk node from the skip list */
+ if((chunk_info=H5SL_search(fm->fsel,&chunk_index))==NULL)
+ HGOTO_ERROR(H5E_DATASPACE,H5E_NOTFOUND,FAIL,"can't locate chunk in skip list")
/* Check if the chunk already has a memory space */
if(chunk_info->mspace==NULL) {
diff --git a/src/H5P.c b/src/H5P.c
index 9deed9f..05622d8 100644
--- a/src/H5P.c
+++ b/src/H5P.c
@@ -1105,10 +1105,10 @@ H5P_free_prop(H5P_genprop_t *prop)
REVISION LOG
--------------------------------------------------------------------------*/
static herr_t
-H5P_free_all_prop_cb(void *item, void UNUSED *key, void *_make_cb)
+H5P_free_all_prop_cb(void *item, void UNUSED *key, void *op_data)
{
H5P_genprop_t *tprop=(H5P_genprop_t *)item; /* Temporary pointer to property */
- unsigned make_cb=*(unsigned *)_make_cb; /* Whether to make property 'close' callback */
+ unsigned make_cb=*(unsigned *)op_data; /* Whether to make property 'close' callback */
FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5P_free_all_prop_cb);
diff --git a/src/H5SL.c b/src/H5SL.c
index 1100a49..7a54b14 100644
--- a/src/H5SL.c
+++ b/src/H5SL.c
@@ -131,7 +131,7 @@
/* Skip list node data structure */
struct H5SL_node_t {
- void *key; /* Pointer to node's key */
+ const void *key; /* Pointer to node's key */
void *item; /* Pointer to node's item */
size_t level; /* The level of this node */
struct H5SL_node_t **forward; /* Array of forward pointers from this node */
@@ -153,7 +153,7 @@ struct H5SL_t {
/* Static functions */
static size_t H5SL_random_level(int p1, size_t max_level);
-static H5SL_node_t * H5SL_new_node(size_t lvl, void *item, void *key);
+static H5SL_node_t * H5SL_new_node(size_t lvl, void *item, const void *key);
/* Declare a free list to manage the H5SL_t struct */
H5FL_DEFINE_STATIC(H5SL_t);
@@ -258,7 +258,7 @@ H5SL_random_level(int p1, size_t max_level)
REVISION LOG
--------------------------------------------------------------------------*/
static H5SL_node_t *
-H5SL_new_node(size_t lvl, void *item, void *key)
+H5SL_new_node(size_t lvl, void *item, const void *key)
{
H5SL_node_t *ret_value; /* New skip list node */
@@ -309,7 +309,7 @@ H5SL_create(H5SL_type_t type, double p, size_t max_level)
/* Check args */
HDassert(p>0.0 && p<1.0);
HDassert(max_level>0 && max_level<=H5SL_LEVEL_MAX);
- HDassert(type>=H5SL_TYPE_INT && type<=H5SL_TYPE_STR);
+ HDassert(type>=H5SL_TYPE_INT && type<=H5SL_TYPE_HSIZE);
/* Allocate skip list structure */
if((new_slist=H5FL_MALLOC(H5SL_t))==NULL)
@@ -406,7 +406,7 @@ H5SL_count(H5SL_t *slist)
REVISION LOG
--------------------------------------------------------------------------*/
herr_t
-H5SL_insert(H5SL_t *slist, void *item, void *key)
+H5SL_insert(H5SL_t *slist, void *item, const void *key)
{
H5SL_node_t **update[H5SL_LEVEL_MAX]; /* 'update' vector */
H5SL_node_t *checked; /* Pointer to last node checked */
@@ -432,16 +432,20 @@ H5SL_insert(H5SL_t *slist, void *item, void *key)
x=slist->header;
switch(slist->type) {
case H5SL_TYPE_INT:
- H5SL_INSERT(SCALAR,slist,x,update,i,int,item,key,checked)
+ H5SL_INSERT(SCALAR,slist,x,update,i,const int,item,key,checked)
break;
case H5SL_TYPE_HADDR:
- H5SL_INSERT(SCALAR,slist,x,update,i,haddr_t,item,key,checked)
+ H5SL_INSERT(SCALAR,slist,x,update,i,const haddr_t,item,key,checked)
break;
case H5SL_TYPE_STR:
H5SL_INSERT(STRING,slist,x,update,i,char *,item,key,checked)
break;
+
+ case H5SL_TYPE_HSIZE:
+ H5SL_INSERT(SCALAR,slist,x,update,i,const hsize_t,item,key,checked)
+ break;
} /* end switch */
/* 'key' must not have been found in existing list, if we get here */
@@ -531,6 +535,10 @@ H5SL_search(H5SL_t *slist, const void *key)
case H5SL_TYPE_STR:
H5SL_SEARCH(STRING,slist,x,-,i,char *,-,key,checked)
break;
+
+ case H5SL_TYPE_HSIZE:
+ H5SL_SEARCH(SCALAR,slist,x,-,i,const hsize_t,-,key,checked)
+ break;
} /* end switch */
/* 'key' must not have been found in existing list, if we get here */
@@ -586,16 +594,20 @@ H5SL_remove(H5SL_t *slist, const void *key)
x=slist->header;
switch(slist->type) {
case H5SL_TYPE_INT:
- H5SL_REMOVE(SCALAR,slist,x,update,i,int,-,key,checked)
+ H5SL_REMOVE(SCALAR,slist,x,update,i,const int,-,key,checked)
break;
case H5SL_TYPE_HADDR:
- H5SL_REMOVE(SCALAR,slist,x,update,i,haddr_t,-,key,checked)
+ H5SL_REMOVE(SCALAR,slist,x,update,i,const haddr_t,-,key,checked)
break;
case H5SL_TYPE_STR:
H5SL_REMOVE(STRING,slist,x,update,i,char *,-,key,checked)
break;
+
+ case H5SL_TYPE_HSIZE:
+ H5SL_REMOVE(SCALAR,slist,x,update,i,const hsize_t,-,key,checked)
+ break;
} /* end switch */
done:
@@ -755,7 +767,8 @@ H5SL_iterate(H5SL_t *slist, H5SL_operator_t op, void *op_data)
node=slist->header->forward[0];
while(node!=NULL) {
/* Call the iterator callback */
- if((ret_value=(op)(node->item,node->key,op_data))!=0)
+ /* Casting away const OK -QAK */
+ if((ret_value=(op)(node->item,(void *)node->key,op_data))!=0)
break;
node=node->forward[0];
diff --git a/src/H5SLprivate.h b/src/H5SLprivate.h
index 43367fb..f3944f4 100644
--- a/src/H5SLprivate.h
+++ b/src/H5SLprivate.h
@@ -42,7 +42,8 @@ typedef struct H5SL_node_t H5SL_node_t;
typedef enum {
H5SL_TYPE_INT, /* Skip list keys are 'int's */
H5SL_TYPE_HADDR, /* Skip list keys are 'haddr_t's */
- H5SL_TYPE_STR /* Skip list keys are 'char *'s (ie. strings) */
+ H5SL_TYPE_STR, /* Skip list keys are 'char *'s (ie. strings) */
+ H5SL_TYPE_HSIZE /* Skip list keys are 'hsize_t's */
} H5SL_type_t;
/**********/
@@ -59,7 +60,7 @@ typedef herr_t (*H5SL_operator_t)(void *item, void *key,
/********************/
H5_DLL H5SL_t *H5SL_create(H5SL_type_t type, double p, size_t max_level);
H5_DLL size_t H5SL_count(H5SL_t *slist);
-H5_DLL herr_t H5SL_insert(H5SL_t *slist, void *item, void *key);
+H5_DLL herr_t H5SL_insert(H5SL_t *slist, void *item, const void *key);
H5_DLL void *H5SL_remove(H5SL_t *slist, const void *key);
H5_DLL void *H5SL_search(H5SL_t *slist, const void *key);
H5_DLL H5SL_node_t *H5SL_first(H5SL_t *slist);
diff --git a/test/cache.c b/test/cache.c
index 36dda3b..ffc4248 100644
--- a/test/cache.c
+++ b/test/cache.c
@@ -28,7 +28,6 @@ const char *FILENAME[] = {
#define H5C_PACKAGE /*suppress error about including H5Cpkg */
-#include "H5TBprivate.h"
#include "H5Cpkg.h"
/* with apologies for the abuse of terminology... */
diff --git a/test/tskiplist.c b/test/tskiplist.c
index 85eba86..e6d090b 100644
--- a/test/tskiplist.c
+++ b/test/tskiplist.c
@@ -631,7 +631,62 @@ test_skiplist_iterate(void)
ret=H5SL_close(slist);
CHECK(ret, FAIL, "H5SL_close");
-} /* end test_skiplist_firstnext() */
+} /* end test_skiplist_iterate() */
+
+/****************************************************************
+**
+** test_skiplist_hsize(): Test H5SL (skip list) code.
+** Tests using hsize_t for keys in skip lists.
+**
+****************************************************************/
+static void
+test_skiplist_hsize(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ H5SL_node_t *node; /* Skip list node */
+ size_t num; /* Number of elements in skip list */
+ size_t u; /* Local index variable */
+ hsize_t data[10]={ 10, 20, 15, 5, 50, 30, 31, 32, 80, 90};
+ hsize_t sorted_data[10]={ 5, 10, 15, 20, 30, 31, 32, 50, 80, 90};
+ hsize_t *found_item; /* Item found in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Skip List With hsize_t Keys\n"));
+
+ /* Create a skip list */
+ slist=H5SL_create(H5SL_TYPE_HSIZE, 0.5, 16);
+ CHECK(slist, NULL, "H5SL_create");
+
+ /* Check that the skip list has no elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 0, "H5SL_count");
+
+ /* Insert objects into the skip list */
+ for(u=0; u<10; u++) {
+ ret=H5SL_insert(slist,&data[u],&data[u]);
+ CHECK(ret, FAIL, "H5SL_insert");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 10, "H5SL_count");
+
+ /* Iterate over all the nodes in the skip list */
+ node=H5SL_first(slist);
+ u=0;
+ while(node!=NULL) {
+ found_item=H5SL_item(node);
+ VERIFY(*found_item,sorted_data[u],"H5SL_next");
+ u++;
+ node=H5SL_next(node);
+ } /* end while */
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_hsize() */
/****************************************************************
**
@@ -656,6 +711,7 @@ test_skiplist(void)
test_skiplist_firstnext(); /* Test iteration over skip list nodes with first/next */
test_skiplist_string(); /* Test skip list string keys */
test_skiplist_iterate(); /* Test iteration over skip list nodes with callback */
+ test_skiplist_hsize(); /* Test skip list hsize_t keys */
} /* end test_skiplist() */