summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--MANIFEST3
-rw-r--r--src/H5Edefin.h8
-rw-r--r--src/H5Einit.h24
-rw-r--r--src/H5Epubgen.h12
-rw-r--r--src/H5Eterm.h8
-rw-r--r--src/H5HP.c16
-rw-r--r--src/H5SL.c715
-rw-r--r--src/H5SLprivate.h66
-rw-r--r--src/H5err.txt10
-rw-r--r--src/Makefile.in6
-rw-r--r--test/Makefile.in13
-rw-r--r--test/testhdf5.c1
-rw-r--r--test/testhdf5.h1
-rw-r--r--test/tskiplist.c497
14 files changed, 1353 insertions, 27 deletions
diff --git a/MANIFEST b/MANIFEST
index 3f07edc..dc5dee0 100644
--- a/MANIFEST
+++ b/MANIFEST
@@ -918,6 +918,8 @@
./src/H5Spublic.h
./src/H5Sselect.c
./src/H5Stest.c
+./src/H5SL.c
+./src/H5SLprivate.h
./src/H5ST.c
./src/H5STprivate.h
./src/H5T.c
@@ -1045,6 +1047,7 @@
./test/trefer.c
./test/trefstr.c
./test/tselect.c
+./test/tskiplist.c
./test/ttbbt.c
./test/ttst.c
./test/ttsafe.c
diff --git a/src/H5Edefin.h b/src/H5Edefin.h
index fc629bb..983a615 100644
--- a/src/H5Edefin.h
+++ b/src/H5Edefin.h
@@ -41,6 +41,7 @@ hid_t H5E_TBBT_g = FAIL; /* Threaded, Balanced, Binary Trees */
hid_t H5E_ATOM_g = FAIL; /* Object atom */
hid_t H5E_ATTR_g = FAIL; /* Attribute */
hid_t H5E_IO_g = FAIL; /* Low-level I/O */
+hid_t H5E_SLIST_g = FAIL; /* Skip Lists */
hid_t H5E_EFL_g = FAIL; /* External file list */
hid_t H5E_TST_g = FAIL; /* Ternary Search Trees */
hid_t H5E_ARGS_g = FAIL; /* Invalid arguments to routine */
@@ -50,6 +51,9 @@ hid_t H5E_CACHE_g = FAIL; /* Object cache */
/* Minor error IDs */
+/* Threaded, balanced binary tree errors */
+hid_t H5E_CANTMAKETREE_g = FAIL; /* Can't create a binary tree node */
+
/* Generic low-level file I/O errors */
hid_t H5E_SEEKERROR_g = FAIL; /* Seek failed */
hid_t H5E_READERROR_g = FAIL; /* Read failed */
@@ -68,6 +72,9 @@ hid_t H5E_CANTUNLOCK_g = FAIL; /* Unable to unlock object */
hid_t H5E_CANTGC_g = FAIL; /* Unable to garbage collect */
hid_t H5E_CANTGETSIZE_g = FAIL; /* Unable to compute size */
+/* Heap errors */
+hid_t H5E_CANTRESTORE_g = FAIL; /* Can't restore condition */
+
/* Function entry/exit interface errors */
hid_t H5E_CANTINIT_g = FAIL; /* Unable to initialize object */
hid_t H5E_ALREADYINIT_g = FAIL; /* Object already initialized */
@@ -86,7 +93,6 @@ hid_t H5E_BADMESG_g = FAIL; /* Unrecognized message */
hid_t H5E_CANTDELETE_g = FAIL; /* Can't delete message */
/* FPHDF5 errors */
-hid_t H5E_CANTMAKETREE_g = FAIL; /* Can't create a binary tree node */
hid_t H5E_CANTRECV_g = FAIL; /* Can't receive messages from processes */
hid_t H5E_CANTSENDMDATA_g = FAIL; /* Can't send metadata message */
hid_t H5E_CANTCHANGE_g = FAIL; /* Can't register change with server */
diff --git a/src/H5Einit.h b/src/H5Einit.h
index 0e43071..065a4d1 100644
--- a/src/H5Einit.h
+++ b/src/H5Einit.h
@@ -128,6 +128,11 @@ if((msg = H5E_create_msg(cls, H5E_MAJOR, "Low-level I/O"))==NULL)
HGOTO_ERROR(H5E_ERROR, H5E_CANTINIT, FAIL, "error message initialization failed")
if((H5E_IO_g = H5I_register(H5I_ERROR_MSG, msg))<0)
HGOTO_ERROR(H5E_ERROR, H5E_CANTREGISTER, FAIL, "can't register error message")
+assert(H5E_SLIST_g==(-1));
+if((msg = H5E_create_msg(cls, H5E_MAJOR, "Skip Lists"))==NULL)
+ HGOTO_ERROR(H5E_ERROR, H5E_CANTINIT, FAIL, "error message initialization failed")
+if((H5E_SLIST_g = H5I_register(H5I_ERROR_MSG, msg))<0)
+ HGOTO_ERROR(H5E_ERROR, H5E_CANTREGISTER, FAIL, "can't register error message")
assert(H5E_EFL_g==(-1));
if((msg = H5E_create_msg(cls, H5E_MAJOR, "External file list"))==NULL)
HGOTO_ERROR(H5E_ERROR, H5E_CANTINIT, FAIL, "error message initialization failed")
@@ -164,6 +169,13 @@ if((H5E_CACHE_g = H5I_register(H5I_ERROR_MSG, msg))<0)
/*********************/
+/* Threaded, balanced binary tree errors */
+assert(H5E_CANTMAKETREE_g==(-1));
+if((msg = H5E_create_msg(cls, H5E_MINOR, "Can't create a binary tree node"))==NULL)
+ HGOTO_ERROR(H5E_ERROR, H5E_CANTINIT, FAIL, "error message initialization failed")
+if((H5E_CANTMAKETREE_g = H5I_register(H5I_ERROR_MSG, msg))<0)
+ HGOTO_ERROR(H5E_ERROR, H5E_CANTREGISTER, FAIL, "can't register error message")
+
/* Generic low-level file I/O errors */
assert(H5E_SEEKERROR_g==(-1));
if((msg = H5E_create_msg(cls, H5E_MINOR, "Seek failed"))==NULL)
@@ -238,6 +250,13 @@ if((msg = H5E_create_msg(cls, H5E_MINOR, "Unable to compute size"))==NULL)
if((H5E_CANTGETSIZE_g = H5I_register(H5I_ERROR_MSG, msg))<0)
HGOTO_ERROR(H5E_ERROR, H5E_CANTREGISTER, FAIL, "can't register error message")
+/* Heap errors */
+assert(H5E_CANTRESTORE_g==(-1));
+if((msg = H5E_create_msg(cls, H5E_MINOR, "Can't restore condition"))==NULL)
+ HGOTO_ERROR(H5E_ERROR, H5E_CANTINIT, FAIL, "error message initialization failed")
+if((H5E_CANTRESTORE_g = H5I_register(H5I_ERROR_MSG, msg))<0)
+ HGOTO_ERROR(H5E_ERROR, H5E_CANTREGISTER, FAIL, "can't register error message")
+
/* Function entry/exit interface errors */
assert(H5E_CANTINIT_g==(-1));
if((msg = H5E_create_msg(cls, H5E_MINOR, "Unable to initialize object"))==NULL)
@@ -300,11 +319,6 @@ if((H5E_CANTDELETE_g = H5I_register(H5I_ERROR_MSG, msg))<0)
HGOTO_ERROR(H5E_ERROR, H5E_CANTREGISTER, FAIL, "can't register error message")
/* FPHDF5 errors */
-assert(H5E_CANTMAKETREE_g==(-1));
-if((msg = H5E_create_msg(cls, H5E_MINOR, "Can't create a binary tree node"))==NULL)
- HGOTO_ERROR(H5E_ERROR, H5E_CANTINIT, FAIL, "error message initialization failed")
-if((H5E_CANTMAKETREE_g = H5I_register(H5I_ERROR_MSG, msg))<0)
- HGOTO_ERROR(H5E_ERROR, H5E_CANTREGISTER, FAIL, "can't register error message")
assert(H5E_CANTRECV_g==(-1));
if((msg = H5E_create_msg(cls, H5E_MINOR, "Can't receive messages from processes"))==NULL)
HGOTO_ERROR(H5E_ERROR, H5E_CANTINIT, FAIL, "error message initialization failed")
diff --git a/src/H5Epubgen.h b/src/H5Epubgen.h
index e59e53b..f2a4a42 100644
--- a/src/H5Epubgen.h
+++ b/src/H5Epubgen.h
@@ -44,6 +44,7 @@
#define H5E_ATOM (H5OPEN H5E_ATOM_g)
#define H5E_ATTR (H5OPEN H5E_ATTR_g)
#define H5E_IO (H5OPEN H5E_IO_g)
+#define H5E_SLIST (H5OPEN H5E_SLIST_g)
#define H5E_EFL (H5OPEN H5E_EFL_g)
#define H5E_TST (H5OPEN H5E_TST_g)
#define H5E_ARGS (H5OPEN H5E_ARGS_g)
@@ -71,6 +72,7 @@ H5_DLLVAR hid_t H5E_TBBT_g; /* Threaded, Balanced, Binary Trees */
H5_DLLVAR hid_t H5E_ATOM_g; /* Object atom */
H5_DLLVAR hid_t H5E_ATTR_g; /* Attribute */
H5_DLLVAR hid_t H5E_IO_g; /* Low-level I/O */
+H5_DLLVAR hid_t H5E_SLIST_g; /* Skip Lists */
H5_DLLVAR hid_t H5E_EFL_g; /* External file list */
H5_DLLVAR hid_t H5E_TST_g; /* Ternary Search Trees */
H5_DLLVAR hid_t H5E_ARGS_g; /* Invalid arguments to routine */
@@ -82,6 +84,10 @@ H5_DLLVAR hid_t H5E_CACHE_g; /* Object cache */
/* Minor error codes */
/*********************/
+/* Threaded, balanced binary tree errors */
+#define H5E_CANTMAKETREE (H5OPEN H5E_CANTMAKETREE_g)
+H5_DLLVAR hid_t H5E_CANTMAKETREE_g; /* Can't create a binary tree node */
+
/* Generic low-level file I/O errors */
#define H5E_SEEKERROR (H5OPEN H5E_SEEKERROR_g)
#define H5E_READERROR (H5OPEN H5E_READERROR_g)
@@ -114,6 +120,10 @@ H5_DLLVAR hid_t H5E_CANTUNLOCK_g; /* Unable to unlock object */
H5_DLLVAR hid_t H5E_CANTGC_g; /* Unable to garbage collect */
H5_DLLVAR hid_t H5E_CANTGETSIZE_g; /* Unable to compute size */
+/* Heap errors */
+#define H5E_CANTRESTORE (H5OPEN H5E_CANTRESTORE_g)
+H5_DLLVAR hid_t H5E_CANTRESTORE_g; /* Can't restore condition */
+
/* Function entry/exit interface errors */
#define H5E_CANTINIT (H5OPEN H5E_CANTINIT_g)
#define H5E_ALREADYINIT (H5OPEN H5E_ALREADYINIT_g)
@@ -143,12 +153,10 @@ H5_DLLVAR hid_t H5E_BADMESG_g; /* Unrecognized message */
H5_DLLVAR hid_t H5E_CANTDELETE_g; /* Can't delete message */
/* FPHDF5 errors */
-#define H5E_CANTMAKETREE (H5OPEN H5E_CANTMAKETREE_g)
#define H5E_CANTRECV (H5OPEN H5E_CANTRECV_g)
#define H5E_CANTSENDMDATA (H5OPEN H5E_CANTSENDMDATA_g)
#define H5E_CANTCHANGE (H5OPEN H5E_CANTCHANGE_g)
#define H5E_CANTALLOC (H5OPEN H5E_CANTALLOC_g)
-H5_DLLVAR hid_t H5E_CANTMAKETREE_g; /* Can't create a binary tree node */
H5_DLLVAR hid_t H5E_CANTRECV_g; /* Can't receive messages from processes */
H5_DLLVAR hid_t H5E_CANTSENDMDATA_g;/* Can't send metadata message */
H5_DLLVAR hid_t H5E_CANTCHANGE_g; /* Can't register change with server */
diff --git a/src/H5Eterm.h b/src/H5Eterm.h
index 4f5bda9..49db49d 100644
--- a/src/H5Eterm.h
+++ b/src/H5Eterm.h
@@ -42,6 +42,7 @@ H5E_TBBT_g=
H5E_ATOM_g=
H5E_ATTR_g=
H5E_IO_g=
+H5E_SLIST_g=
H5E_EFL_g=
H5E_TST_g=
H5E_ARGS_g=
@@ -52,6 +53,9 @@ H5E_CACHE_g= (-1);
/* Reset minor error IDs */
+/* Threaded, balanced binary tree errors */
+H5E_CANTMAKETREE_g=
+
/* Generic low-level file I/O errors */
H5E_SEEKERROR_g=
H5E_READERROR_g=
@@ -70,6 +74,9 @@ H5E_CANTUNLOCK_g=
H5E_CANTGC_g=
H5E_CANTGETSIZE_g=
+/* Heap errors */
+H5E_CANTRESTORE_g=
+
/* Function entry/exit interface errors */
H5E_CANTINIT_g=
H5E_ALREADYINIT_g=
@@ -88,7 +95,6 @@ H5E_BADMESG_g=
H5E_CANTDELETE_g=
/* FPHDF5 errors */
-H5E_CANTMAKETREE_g=
H5E_CANTRECV_g=
H5E_CANTSENDMDATA_g=
H5E_CANTCHANGE_g=
diff --git a/src/H5HP.c b/src/H5HP.c
index b377593..5b35924 100644
--- a/src/H5HP.c
+++ b/src/H5HP.c
@@ -700,21 +700,21 @@ H5HP_change(H5HP_t *heap, int val, void *_obj)
if(val<old_val) {
if(heap->type==H5HP_MAX_HEAP) {
if(H5HP_sink_max(heap,obj_loc)<0)
- HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
} /* end if */
else {
if(H5HP_swim_min(heap,obj_loc)<0)
- HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
} /* end else */
} /* end if */
else {
if(heap->type==H5HP_MAX_HEAP) {
if(H5HP_swim_max(heap,obj_loc)<0)
- HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
} /* end if */
else {
if(H5HP_sink_min(heap,obj_loc)<0)
- HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
} /* end else */
} /* end else */
@@ -783,11 +783,11 @@ H5HP_incr(H5HP_t *heap, unsigned amt, void *_obj)
/* Restore heap condition */
if(heap->type==H5HP_MAX_HEAP) {
if(H5HP_swim_max(heap,obj_loc)<0)
- HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
} /* end if */
else {
if(H5HP_sink_min(heap,obj_loc)<0)
- HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
} /* end else */
done:
@@ -855,11 +855,11 @@ H5HP_decr(H5HP_t *heap, unsigned amt, void *_obj)
/* Restore heap condition */
if(heap->type==H5HP_MAX_HEAP) {
if(H5HP_sink_max(heap,obj_loc)<0)
- HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
} /* end if */
else {
if(H5HP_swim_min(heap,obj_loc)<0)
- HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
} /* end else */
done:
diff --git a/src/H5SL.c b/src/H5SL.c
new file mode 100644
index 0000000..4e2e646
--- /dev/null
+++ b/src/H5SL.c
@@ -0,0 +1,715 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have *
+ * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*
+ * Purpose: Provides a skip list abstract data type.
+ *
+ * (See "Skip Lists: A Probabilistic Alternative to Balanced Trees"
+ * by William Pugh for additional information)
+ *
+ * (This implementation has the optimization for reducing key
+ * key comparisons mentioned in section 3.5 of "A Skip List
+ * Cookbook" by William Pugh)
+ *
+ * (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)
+ *
+ */
+
+/* Interface initialization */
+#define H5_INTERFACE_INIT_FUNC H5SL_init_interface
+
+/* Pablo information */
+/* (Put before include files to avoid problems with inline functions) */
+#define PABLO_MASK H5SL_mask
+
+/* Private headers needed */
+#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 insertions for the "OP" in the H5SL_FIND macro */
+#define H5SL_FIND_INSERT_FOUND(SLIST,X,UPDATE,I,ITEM) \
+ X->item=ITEM; \
+ HGOTO_DONE(SUCCEED);
+
+/* Define the code template for removals for the "OP" in the H5SL_FIND macro */
+#define H5SL_FIND_REMOVE_FOUND(SLIST,X,UPDATE,I,ITEM) \
+ void *tmp; \
+ \
+ for(I=0; I<=(int)SLIST->curr_level; I++) { \
+ if(*UPDATE[I]!=X) \
+ break; \
+ *UPDATE[I]=X->forward[I]; \
+ } /* end for */ \
+ tmp=X->item; \
+ H5MM_xfree(X); \
+ while(SLIST->curr_level>0 && SLIST->header->forward[SLIST->curr_level]==NULL) \
+ SLIST->curr_level--; \
+ SLIST->nobjs--; \
+ HGOTO_DONE(tmp);
+
+/* Define the code template for searches for the "OP" in the H5SL_FIND macro */
+#define H5SL_FIND_SEARCH_FOUND(SLIST,X,UPDATE,I,ITEM) \
+ HGOTO_DONE(X->item);
+
+/* Define a code template for updating the "update" vector for the "DOUPDATE" in the H5SL_FIND macro */
+#define H5SL_FIND_YES_UPDATE(X,UPDATE,I) \
+ UPDATE[I]=&X->forward[I];
+
+/* Define a code template for _NOT_ updating the "update" vector for the "DOUPDATE" in the H5SL_FIND macro */
+#define H5SL_FIND_NO_UPDATE(X,UPDATE,I)
+
+/* Macro used to find node for operation */
+#define H5SL_FIND(OP,DOUPDATE,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
+ CHECKED=NULL; \
+ for(I=(int)SLIST->curr_level; I>=0; I--) { \
+ if(X->forward[I]!=CHECKED) { \
+ while(X->forward[I] && *(TYPE *)X->forward[I]->key<*(TYPE *)KEY) \
+ X=X->forward[I]; \
+ CHECKED=X->forward[I]; \
+ } /* end if */ \
+ H5_GLUE3(H5SL_FIND_,DOUPDATE,_UPDATE)(X,UPDATE,I) \
+ } /* end for */ \
+ X=X->forward[0]; \
+ if(X!=NULL && *(TYPE *)X->key==*(TYPE *)key) { \
+ /* What to do when a node is found */ \
+ H5_GLUE3(H5SL_FIND_,OP,_FOUND)(SLIST,X,UPDATE,I,ITEM) \
+ } /* end if */
+
+/* Macro used to insert node */
+#define H5SL_INSERT(SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
+ H5SL_FIND(INSERT,YES,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
+
+/* Macro used to remove node */
+#define H5SL_REMOVE(SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
+ H5SL_FIND(REMOVE,YES,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
+
+/* Macro used to search for node */
+#define H5SL_SEARCH(SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
+ H5SL_FIND(SEARCH,NO,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
+
+
+/* Private typedefs & structs */
+
+/* Skip list node data structure */
+struct H5SL_node_t {
+ 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[1]; /* Array of forward pointers from this node */
+};
+
+/* Main skip list data structure */
+struct H5SL_t {
+ /* Static values for each list */
+ H5SL_type_t type; /* Type of skip list */
+ double p; /* Probability of using a higher level [0..1) */
+ size_t max_level; /* Maximum number of levels */
+
+ /* 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 */
+};
+
+/* Static functions */
+static size_t H5SL_random_level(double p, size_t max_level);
+static H5SL_node_t * H5SL_new_node(size_t lvl, void *item, void *key);
+
+/* Declare a free list to manage the H5SL_t struct */
+H5FL_DEFINE_STATIC(H5SL_t);
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_init_interface
+ PURPOSE
+ Initialize interface-specific information
+ USAGE
+ herr_t H5SL_init_interface()
+
+ RETURNS
+ Non-negative on success/Negative on failure
+ DESCRIPTION
+ Initializes any interface-specific data or routines.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static herr_t
+H5SL_init_interface(void)
+{
+ time_t curr_time; /* Current time, for seeding random number generator */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_init_interface)
+
+ /* Create randomized set of numbers */
+ curr_time=HDtime(NULL);
+ HDsrandom((unsigned long)curr_time);
+
+ FUNC_LEAVE_NOAPI(SUCCEED)
+} /* end H5SL_init_interface() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_random_level
+ PURPOSE
+ Generate a random level
+ USAGE
+ size_t H5SL_random_level(p,max_level)
+ double p; IN: probability distribution
+ size_t max_level; IN: Maximum level for node height
+
+ RETURNS
+ Returns non-negative level value
+ DESCRIPTION
+ Count elements in a skip list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ Do we really need a 'random' value, or is a series of nodes with the
+ correct heights "good enough". We could track the state of the nodes
+ allocated for this list and issue node heights appropriately (i.e. 1,2,
+ 1,4,1,2,1,8,...) (or would that be 1,1,2,1,1,2,4,... ?)
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static size_t
+H5SL_random_level(double p, size_t max_level)
+{
+ size_t lvl; /* Level generated */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_random_level);
+
+ lvl=0;
+ while((((double)HDrandom())/((double)LONG_MAX))<p && lvl < max_level)
+ lvl++;
+
+ FUNC_LEAVE_NOAPI(lvl);
+} /* end H5SL_random_level() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_new_node
+ PURPOSE
+ Create a new skip list node
+ USAGE
+ H5SL_node_t *H5SL_new_node(lvl,item,key)
+ size_t lvl; IN: Level for node height
+ void *item; IN: Pointer to item info for node
+ void *key; IN: Pointer to key info for node
+
+ RETURNS
+ Returns a pointer to a skip list node on success, NULL on failure.
+ DESCRIPTION
+ Create a new skip list node of the specified height, setting the item
+ and key values internally.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ This routine does _not_ initialize the 'forward' pointers
+
+ We should set up a custom free-list for allocating & freeing these sort
+ of nodes.
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static H5SL_node_t *
+H5SL_new_node(size_t lvl, void *item, void *key)
+{
+ H5SL_node_t *ret_value; /* New skip list node */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5SL_new_node);
+
+ /* Allocate the node */
+ if((ret_value=H5MM_malloc(sizeof(H5SL_node_t)+(sizeof(H5SL_node_t *)*lvl)))==NULL)
+ HGOTO_ERROR(H5E_SLIST,H5E_NOSPACE,NULL,"memory allocation failed");
+
+ /* Initialize node */
+ ret_value->key=key;
+ ret_value->item=item;
+ ret_value->level=lvl;
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_new_node() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_create
+ PURPOSE
+ Create a skip list
+ USAGE
+ H5SL_t *H5SL_create(void)
+
+ RETURNS
+ Returns a pointer to a skip list on success, NULL on failure.
+ DESCRIPTION
+ Create a skip list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5SL_t *
+H5SL_create(H5SL_type_t type, double p, size_t max_level)
+{
+ H5SL_t *new_slist=NULL; /* Pointer to new skip list object created */
+ H5SL_node_t *header; /* Pointer to skip list header node */
+ size_t u; /* Local index variable */
+ H5SL_t *ret_value; /* Return value */
+
+ FUNC_ENTER_NOAPI(H5SL_create,NULL);
+
+ /* 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_HADDR);
+
+ /* Allocate skip list structure */
+ if((new_slist=H5FL_MALLOC(H5SL_t))==NULL)
+ HGOTO_ERROR(H5E_SLIST,H5E_NOSPACE,NULL,"memory allocation failed");
+
+ /* Set the static internal fields */
+ new_slist->type=type;
+ new_slist->p=p;
+ new_slist->max_level=max_level;
+
+ /* Set the dynamic internal fields */
+ new_slist->curr_level=-1;
+ new_slist->nobjs=0;
+
+ /* Allocate the header node */
+ if((header=H5SL_new_node(max_level-1,NULL,NULL))==NULL)
+ HGOTO_ERROR(H5E_SLIST,H5E_NOSPACE,NULL,"memory allocation failed");
+
+ /* Initialize header node's forward pointers */
+ for(u=0; u<max_level; u++)
+ header->forward[u]=NULL;
+
+ /* Attach the header */
+ new_slist->header=header;
+
+ /* Set the return value */
+ ret_value=new_slist;
+
+done:
+ /* Error cleanup */
+ if(ret_value==NULL) {
+ if(new_slist!=NULL) {
+ H5FL_FREE(H5SL_t,new_slist);
+ } /* end if */
+ } /* end if */
+
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_create() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_count
+ PURPOSE
+ Count the number of objects in a skip list
+ USAGE
+ ssize_t H5SL_count(slist)
+ H5SL_t *slist; IN: Pointer to skip list to count
+
+ RETURNS
+ Returns non-negative on success, negative on failure.
+ DESCRIPTION
+ Count elements in a skip list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+ssize_t
+H5SL_count(H5SL_t *slist)
+{
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_count);
+
+ /* Check args */
+ assert(slist);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ FUNC_LEAVE_NOAPI(slist->nobjs);
+} /* end H5SL_count() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_insert
+ PURPOSE
+ Insert an objects into a skip list
+ USAGE
+ herr_t H5SL_insert(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
+
+ RETURNS
+ Returns non-negative on success, negative on failure.
+ DESCRIPTION
+ Insert element into a skip list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ Inserting an item with the same key as an existing object replaces
+ the existing object's item pointer with the new item pointer.
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5SL_insert(H5SL_t *slist, void *item, void *key)
+{
+ H5SL_node_t **update[H5SL_LEVEL_MAX]; /* 'update' vector */
+ H5SL_node_t *checked; /* Pointer to last node checked */
+ H5SL_node_t *x; /* Current node to examine */
+ size_t lvl; /* Level of new node */
+ int i; /* Local index value */
+ herr_t ret_value=SUCCEED; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5SL_insert);
+
+ /* Check args */
+ assert(slist);
+ assert(key);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Insert item into skip list */
+
+ /* 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) {
+ case H5SL_TYPE_INT:
+ H5SL_INSERT(slist,x,update,i,int,item,key,checked)
+ break;
+
+ case H5SL_TYPE_HADDR:
+ H5SL_INSERT(slist,x,update,i,haddr_t,item,key,checked)
+ break;
+ } /* end switch */
+
+ /* 'key' must not have been found in existing list, if we get here */
+
+ /* Generate level for new node */
+ lvl=H5SL_random_level(slist->p,slist->max_level);
+ if((int)lvl>slist->curr_level) {
+ /* Cap the increase in the current level to just one greater */
+ lvl=slist->curr_level+1;
+
+ /* Set the update pointer correctly */
+ update[lvl]=&slist->header->forward[lvl];
+
+ /* Increase the maximum level of the list */
+ slist->curr_level=lvl;
+ } /* end if */
+
+ /* Create new node of proper level */
+ if((x=H5SL_new_node(lvl,item,key))==NULL)
+ HGOTO_ERROR(H5E_SLIST,H5E_NOSPACE,NULL,"can't create new skip list node");
+
+ /* Link the new node into the existing list */
+ for(i=0; i<=(int)lvl; i++) {
+ x->forward[i]=*update[i];
+ *update[i]=x;
+ } /* end for */
+
+ /* Increment the number of nodes in the skip list */
+ slist->nobjs++;
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_insert() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_search
+ PURPOSE
+ Search for objects into a skip list
+ USAGE
+ void *H5SL_search(slist,key)
+ H5SL_t *slist; IN/OUT: Pointer to skip list
+ void *key; IN: Key for item to search for
+
+ RETURNS
+ Returns pointer to item on success, NULL on failure
+ DESCRIPTION
+ Search for an object in a skip list, according to it's key
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+void *
+H5SL_search(H5SL_t *slist, void *key)
+{
+ H5SL_node_t *checked; /* Pointer to last node checked */
+ H5SL_node_t *x; /* Current node to examine */
+ int i; /* Local index value */
+ void *ret_value; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_search);
+
+ /* Check args */
+ assert(slist);
+ assert(key);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Insert item into skip list */
+
+ /* 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) {
+ case H5SL_TYPE_INT:
+ H5SL_SEARCH(slist,x,-,i,int,-,key,checked)
+ break;
+
+ case H5SL_TYPE_HADDR:
+ H5SL_SEARCH(slist,x,-,i,haddr_t,-,key,checked)
+ break;
+ } /* end switch */
+
+ /* 'key' must not have been found in existing list, if we get here */
+ ret_value=NULL;
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_search() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_remove
+ PURPOSE
+ Removes an object from a skip list
+ USAGE
+ void *H5SL_remove(slist,key)
+ H5SL_t *slist; IN/OUT: Pointer to skip list
+ void *key; IN: Key for item to remove
+
+ RETURNS
+ Returns pointer to item removed on success, NULL on failure.
+ DESCRIPTION
+ Remove element from a skip list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+void *
+H5SL_remove(H5SL_t *slist, void *key)
+{
+ H5SL_node_t **update[H5SL_LEVEL_MAX]; /* 'update' vector */
+ H5SL_node_t *checked; /* Pointer to last node checked */
+ H5SL_node_t *x; /* Current node to examine */
+ int i; /* Local index value */
+ void *ret_value=NULL; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_remove);
+
+ /* Check args */
+ assert(slist);
+ assert(key);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Remove item from skip list */
+
+ /* Work through the forward pointers for a node, finding the node at each
+ * level that is before the location to remove
+ */
+ x=slist->header;
+ switch(slist->type) {
+ case H5SL_TYPE_INT:
+ H5SL_REMOVE(slist,x,update,i,int,-,key,checked)
+ break;
+
+ case H5SL_TYPE_HADDR:
+ H5SL_REMOVE(slist,x,update,i,haddr_t,-,key,checked)
+ break;
+ } /* end switch */
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_remove() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_first
+ PURPOSE
+ Gets a pointer to the first node in a skip list
+ USAGE
+ H5SL_node_t *H5SL_first(slist)
+ H5SL_t *slist; IN: Pointer to skip list
+
+ RETURNS
+ Returns pointer to first node in skip list on success, NULL on failure.
+ DESCRIPTION
+ Retrieves a pointer to the first node in a skip list, for iterating over
+ the list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5SL_node_t *
+H5SL_first(H5SL_t *slist)
+{
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_first);
+
+ /* Check args */
+ assert(slist);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ FUNC_LEAVE_NOAPI(slist->header->forward[0]);
+} /* end H5SL_first() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_next
+ PURPOSE
+ Gets a pointer to the next node in a skip list
+ USAGE
+ H5SL_node_t *H5SL_next(slist_node)
+ H5SL_node_t *slist_node; IN: Pointer to skip list node
+
+ RETURNS
+ Returns pointer to node after slist_node in skip list on success, NULL on failure.
+ DESCRIPTION
+ Retrieves a pointer to the next node in a skip list, for iterating over
+ the list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5SL_node_t *
+H5SL_next(H5SL_node_t *slist_node)
+{
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_next);
+
+ /* Check args */
+ assert(slist_node);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ FUNC_LEAVE_NOAPI(slist_node->forward[0]);
+} /* end H5SL_next() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_item
+ PURPOSE
+ Gets pointer to the 'item' for a skip list node
+ USAGE
+ void *H5SL_item(slist_node)
+ H5SL_node_t *slist_node; IN: Pointer to skip list node
+
+ RETURNS
+ Returns pointer to node 'item' on success, NULL on failure.
+ DESCRIPTION
+ Retrieves a node's 'item'
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+void *
+H5SL_item(H5SL_node_t *slist_node)
+{
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_item);
+
+ /* Check args */
+ assert(slist_node);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ FUNC_LEAVE_NOAPI(slist_node->item);
+} /* end H5SL_item() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_close
+ PURPOSE
+ Close a skip list, deallocating it.
+ USAGE
+ herr_t H5SL_close(slist)
+ H5SL_t *slist; IN/OUT: Pointer to skip list to close
+
+ RETURNS
+ Returns non-negative on success, negative on failure.
+ DESCRIPTION
+ Close a skip list, freeing all internal information. Any objects left in
+ the skip list are not deallocated.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5SL_close(H5SL_t *slist)
+{
+ H5SL_node_t *node, *next_node; /* Pointers to skip list nodes */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_close);
+
+ /* Check args */
+ assert(slist);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Free skip list nodes */
+ node=slist->header;
+ while(node!=NULL) {
+ next_node=node->forward[0];
+ H5MM_xfree(node);
+ node=next_node;
+ } /* end while */
+
+ /* Free skip list object */
+ H5FL_FREE(H5SL_t,slist);
+
+ FUNC_LEAVE_NOAPI(SUCCEED);
+} /* end H5SL_close() */
+
diff --git a/src/H5SLprivate.h b/src/H5SLprivate.h
new file mode 100644
index 0000000..94e2b4d
--- /dev/null
+++ b/src/H5SLprivate.h
@@ -0,0 +1,66 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have *
+ * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*
+ * This file contains private information about the H5SL module
+ */
+#ifndef _H5SLprivate_H
+#define _H5SLprivate_H
+
+/**************************************/
+/* Public headers needed by this file */
+/**************************************/
+#ifdef LATER
+#include "H5SLpublic.h"
+#endif /* LATER */
+
+/***************************************/
+/* Private headers needed by this file */
+/***************************************/
+#include "H5private.h"
+
+/************/
+/* Typedefs */
+/************/
+
+/* Typedefs for skip list struct (defined in H5SL.c) */
+typedef struct H5SL_t H5SL_t;
+typedef struct H5SL_node_t H5SL_node_t;
+
+/* Typedef for kinds of skip lists supported */
+typedef enum {
+ H5SL_TYPE_INT, /* Skip list keys are 'int's */
+ H5SL_TYPE_HADDR /* Skip list keys are 'haddr_t's */
+} H5SL_type_t;
+
+/**********/
+/* Macros */
+/**********/
+#define H5SL_LEVEL_MAX 32 /* (for now) */
+
+/********************/
+/* Private routines */
+/********************/
+H5_DLL H5SL_t *H5SL_create(H5SL_type_t type, double p, size_t max_level);
+H5_DLL ssize_t H5SL_count(H5SL_t *slist);
+H5_DLL herr_t H5SL_insert(H5SL_t *slist, void *item, void *key);
+H5_DLL void *H5SL_remove(H5SL_t *slist, void *key);
+H5_DLL void *H5SL_search(H5SL_t *slist, void *key);
+H5_DLL H5SL_node_t *H5SL_first(H5SL_t *slist);
+H5_DLL H5SL_node_t *H5SL_next(H5SL_node_t *slist_node);
+H5_DLL void *H5SL_item(H5SL_node_t *slist_node);
+H5_DLL herr_t H5SL_close(H5SL_t *slist);
+
+#endif /* _H5HPprivate_H */
+
diff --git a/src/H5err.txt b/src/H5err.txt
index 8b42b3c..82bd041 100644
--- a/src/H5err.txt
+++ b/src/H5err.txt
@@ -71,6 +71,7 @@ MAJOR, H5E_FPHDF5, Flexible Parallel HDF5
MAJOR, H5E_TST, Ternary Search Trees
MAJOR, H5E_RS, Reference Counted Strings
MAJOR, H5E_ERROR, Error API
+MAJOR, H5E_SLIST, Skip Lists
# Sections (for grouping minor errors)
SECTION, ARGS, Argument errors
@@ -87,6 +88,8 @@ SECTION, TYPECONV, Datatype conversion errors
SECTION, DSPACE, Dataspace errors
SECTION, PLIST, Property list errors
SECTION, MPI, Parallel MPI errors
+SECTION, HEAP, Heap errors
+SECTION, TBBT, Threaded, balanced binary tree errors
SECTION, FPH5, FPHDF5 errors
SECTION, PIPELINE, I/O pipeline errors
@@ -198,8 +201,13 @@ MINOR, PLIST, H5E_DUPCLASS, Duplicate class name in parent class
MINOR, MPI, H5E_MPI, Some MPI function failed
MINOR, MPI, H5E_MPIERRSTR, MPI Error String
+# Heap errors
+MINOR, HEAP, H5E_CANTRESTORE, Can't restore condition
+
+# TBBT errors
+MINOR, TBBT, H5E_CANTMAKETREE, Can't create a binary tree node
+
# FPHDF5 errors
-MINOR, FPH5, H5E_CANTMAKETREE, Can't create a binary tree node
MINOR, FPH5, H5E_CANTRECV, Can't receive messages from processes
MINOR, FPH5, H5E_CANTSENDMDATA, Can't send metadata message
MINOR, FPH5, H5E_CANTCHANGE, Can't register change with server
diff --git a/src/Makefile.in b/src/Makefile.in
index c980764..685c916 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -42,7 +42,8 @@ LIB_SRC=H5.c H5A.c H5AC.c H5B.c H5C.c H5D.c H5Dcontig.c H5Dcompact.c H5Defl.c \
H5Omtime.c H5Oname.c H5Onull.c H5Opline.c H5Osdspace.c H5Oshared.c \
H5Ostab.c H5P.c H5Pdcpl.c H5Pdxpl.c H5Pfapl.c H5Pfcpl.c H5Ptest.c \
H5R.c H5RC.c H5RS.c H5S.c H5Sall.c H5Shyper.c H5Smpio.c H5Snone.c \
- H5Spoint.c H5Sselect.c H5Stest.c H5ST.c H5T.c H5Tarray.c H5Tbit.c \
+ H5Spoint.c H5Sselect.c H5Stest.c H5SL.c H5ST.c H5T.c H5Tarray.c \
+ H5Tbit.c \
H5Tcommit.c H5Tcompound.c H5Tconv.c H5Tcset.c H5Tenum.c H5Tfields.c \
H5Tfixed.c H5Tfloat.c H5Tinit.c H5Tnative.c H5Toffset.c H5Topaque.c \
H5Torder.c H5Tpad.c H5Tprecis.c H5Tstrpad.c H5Tvlen.c H5TB.c H5TS.c \
@@ -71,7 +72,8 @@ PRIVATE_HDR=H5private.h H5Aprivate.h H5Apkg.h H5ACprivate.h H5Bprivate.h \
H5FSprivate.h H5Gprivate.h H5Gpkg.h H5HGprivate.h H5HGpkg.h \
H5HLprivate.h H5HLpkg.h H5HPprivate.h H5Iprivate.h H5MFprivate.h \
H5MMprivate.h H5Oprivate.h H5Opkg.h H5Pprivate.h H5Ppkg.h \
- H5Rprivate.h H5RCprivate.h H5RSprivate.h H5Sprivate.h H5STprivate.h \
+ H5Rprivate.h H5RCprivate.h H5RSprivate.h H5Sprivate.h H5SLprivate.h \
+ H5STprivate.h \
H5Tprivate.h H5TBprivate.h H5Tpkg.h H5TSprivate.h H5Vprivate.h \
H5Zprivate.h H5Zpkg.h H5config.h
diff --git a/test/Makefile.in b/test/Makefile.in
index 56ea6fb..bf3a3d4 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -83,9 +83,9 @@ TEST_SRC=big.c bittests.c cache.c cmpd_dset.c dsets.c dtypes.c extend.c \
external.c fillval.c flush1.c flush2.c gheap.c h5test.c hyperslab.c \
istore.c lheap.c links.c mount.c mtime.c ohdr.c stab.c tarray.c \
tattr.c tconfig.c testhdf5.c testmeta.c tfile.c \
- tgenprop.c th5s.c theap.c titerate.c tmeta.c trefer.c trefstr.c \
- tselect.c ttime.c ttbbt.c ttst.c tvltypes.c tvlstr.c tmisc.c tid.c \
- unlink.c enum.c ttsafe.c ttsafe_dcreate.c ttsafe_error.c \
+ tgenprop.c th5s.c theap.c tid.c titerate.c tmeta.c tmisc.c trefer.c \
+ trefstr.c tselect.c tskiplist.c ttime.c ttbbt.c ttst.c tvltypes.c \
+ tvlstr.c unlink.c enum.c ttsafe.c ttsafe_dcreate.c ttsafe_error.c \
ttsafe_cancel.c ttsafe_acreate.c gass_write.c gass_read.c \
gass_append.c srb_read.c srb_write.c srb_append.c stream_test.c \
set_extent.c getname.c file_handle.c ntypes.c dangle.c error_test.c \
@@ -115,10 +115,9 @@ check test _test: $(PROGS)
## How to build the tests... They all depend on the test and hdf5 libraries.
$(PROGS): $(LIB) $(LIBHDF5)
-TESTHDF5_OBJ=testhdf5.lo tarray.lo tattr.lo tconfig.lo tfile.lo \
- tgenprop.lo th5s.lo theap.lo titerate.lo tmeta.lo ttime.lo trefer.lo \
- trefstr.lo tselect.lo ttbbt.lo ttst.lo tvltypes.lo tvlstr.lo tmisc.lo \
- tid.lo
+TESTHDF5_OBJ=testhdf5.lo tarray.lo tattr.lo tconfig.lo tfile.lo tgenprop.lo \
+ th5s.lo theap.lo tid.lo titerate.lo tmeta.lo tmisc.lo trefer.lo trefstr.lo \
+ tselect.lo tskiplist.lo ttbbt.lo ttime.lo ttst.lo tvltypes.lo tvlstr.lo
TTS_OBJ=ttsafe.lo ttsafe_dcreate.lo ttsafe_error.lo \
ttsafe_cancel.lo ttsafe_acreate.lo
diff --git a/test/testhdf5.c b/test/testhdf5.c
index 6234d01..9d86032 100644
--- a/test/testhdf5.c
+++ b/test/testhdf5.c
@@ -48,6 +48,7 @@ main(int argc, char *argv[])
AddTest("tbbt", test_tbbt, NULL, "Threaded, Balanced, Binary Trees", NULL);
AddTest("tst", test_tst, NULL, "Ternary Search Trees", NULL);
AddTest("heap", test_heap, NULL, "Memory Heaps", NULL);
+ AddTest("skiplist", test_skiplist, NULL, "Skip Lists", NULL);
AddTest("refstr", test_refstr, NULL, "Reference Counted Strings", NULL);
AddTest("file", test_file, cleanup_file, "Low-Level File I/O", NULL);
AddTest("h5s", test_h5s, cleanup_h5s, "Dataspaces", NULL);
diff --git a/test/testhdf5.h b/test/testhdf5.h
index e00f56d..61674a8 100644
--- a/test/testhdf5.h
+++ b/test/testhdf5.h
@@ -130,6 +130,7 @@ void test_genprop(void);
void test_configure(void);
void test_misc(void);
void test_ids(void);
+void test_skiplist(void);
/* Prototypes for the cleanup routines */
void cleanup_metadata(void);
diff --git a/test/tskiplist.c b/test/tskiplist.c
new file mode 100644
index 0000000..20bde76
--- /dev/null
+++ b/test/tskiplist.c
@@ -0,0 +1,497 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have *
+ * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*
+ Test HDF Skip List routines.
+
+ REMARKS
+
+ DESIGN
+
+ BUGS/LIMITATIONS
+
+ EXPORTED ROUTINES
+
+ AUTHOR
+ Quincey Koziol
+
+ MODIFICATION HISTORY
+ 11/15/04 - Started coding
+ */
+
+#include <time.h>
+#include <stdlib.h>
+
+#include "testhdf5.h"
+#include "H5SLprivate.h"
+
+/* The number of elements in testing arrays */
+#define NUM_ELEMS 1000
+
+/* Random numbers */
+static int rand_num[NUM_ELEMS];
+static int sort_rand_num[NUM_ELEMS];
+static int rev_sort_rand_num[NUM_ELEMS];
+
+static int tst_sort(const void *i1, const void *i2)
+{
+ return(*(const int *)i1-*(const int *)i2);
+}
+
+static int tst_rev_sort(const void *i1, const void *i2)
+{
+ return(*(const int *)i2-*(const int *)i1);
+}
+
+/****************************************************************
+**
+** test_skiplist_init(): Test H5SL (skiplist) code.
+** Initialize data for skip list testing
+**
+****************************************************************/
+static void
+test_skiplist_init(void)
+{
+ time_t curr_time; /* Current time, for seeding random number generator */
+ int new_val; /* New value to insert */
+ unsigned found; /* Flag to indicate value was inserted already */
+ size_t u,v; /* Local index variables */
+
+ /* Initialize random number seed */
+ curr_time=time(NULL);
+ HDsrandom((unsigned long)curr_time);
+
+ /* Create randomized set of numbers */
+ for(u=0; u<NUM_ELEMS; u++) {
+ do {
+ /* Reset flag */
+ found=0;
+
+ /* Generate random numbers from -5000 to 5000 */
+ new_val=(int)(HDrandom()%10001)-5001;
+
+ /* Check if the value is already in the array */
+ for(v=0; v<u; v++)
+ if(rand_num[v]==new_val)
+ found=1;
+ } while(found);
+
+ /* Set unique value in array */
+ rand_num[u]=new_val;
+ } /* end for */
+
+ /* Copy random values to sorted array */
+ HDmemcpy(sort_rand_num,rand_num,sizeof(int)*NUM_ELEMS);
+
+ /* Sort random numbers */
+ HDqsort(sort_rand_num,NUM_ELEMS,sizeof(int),tst_sort);
+
+ /* Copy random values to reverse sorted array */
+ HDmemcpy(rev_sort_rand_num,rand_num,sizeof(int)*NUM_ELEMS);
+
+ /* Sort random numbers */
+ HDqsort(rev_sort_rand_num,NUM_ELEMS,sizeof(int),tst_rev_sort);
+} /* end test_tst_init() */
+
+/****************************************************************
+**
+** test_skiplist_create(): Test basic H5SL (skiplist) code.
+** Tests creating and closing skip lists.
+**
+****************************************************************/
+static void
+test_skiplist_create(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(6, ("Testing Creating & Closing Skip Lists\n"));
+
+ /* Try creating a skip list */
+ slist=H5SL_create(H5SL_TYPE_INT, 0.5,16);
+ CHECK(slist, NULL, "H5SL_create");
+
+ /* Try closing the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_create() */
+
+/****************************************************************
+**
+** test_skiplist_insert(): Test H5SL (skip list) code.
+** Tests inserting single object into skip list.
+**
+****************************************************************/
+static void
+test_skiplist_insert(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ int key, /* Key of item to insert */
+ item; /* Item to insert */
+ int search_key; /* Key of item to search for in skip list */
+ int *found_item; /* Item found in skip list */
+ ssize_t num; /* Number of elements in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Insertion Into Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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");
+
+ /* Try searching for item in empty skip list */
+ key=37;
+ found_item=H5SL_search(slist,&key);
+ VERIFY(found_item, NULL, "H5SL_search");
+
+ /* Insert an object into the skip list */
+ key=2; item=10;
+ ret=H5SL_insert(slist,&item,&key);
+ CHECK(ret, FAIL, "H5SL_insert");
+
+ /* Check that the skip list has one element */
+ num=H5SL_count(slist);
+ VERIFY(num, 1, "H5SL_count");
+
+ /* Search for the item just inserted */
+ found_item=H5SL_search(slist,&key);
+ CHECK(found_item, NULL, "H5SL_search");
+ VERIFY(*found_item,item,"H5SL_search");
+
+ /* Search for an item not in list */
+ search_key=37;
+ found_item=H5SL_search(slist,&search_key);
+ VERIFY(found_item, NULL, "H5SL_search");
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_insert() */
+
+/****************************************************************
+**
+** test_skiplist_insert_many(): Test H5SL (skip list) code.
+** Tests inserting many objects into skip list.
+**
+****************************************************************/
+static void
+test_skiplist_insert_many(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ ssize_t num; /* Number of elements in skip list */
+ size_t u; /* Local index variable */
+ int *found_item; /* Item found in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Insertion of Many Items Into Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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 many objects into the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ ret=H5SL_insert(slist,&rand_num[u],&rand_num[u]);
+ CHECK(ret, FAIL, "H5SL_insert");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "H5SL_count");
+
+ /* Search for all objects in the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ found_item=H5SL_search(slist,&rand_num[u]);
+ CHECK(found_item, NULL, "H5SL_search");
+ VERIFY(*found_item,rand_num[u],"H5SL_search");
+ } /* end for */
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_insert_many() */
+
+/****************************************************************
+**
+** test_skiplist_remove(): Test H5SL (skip list) code.
+** Tests basic object removal from skip list.
+**
+****************************************************************/
+static void
+test_skiplist_remove(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ int key1, /* Key of 1st item to insert */
+ key2, /* Key of 2nd item to insert */
+ key3; /* Key of 3rd item to insert */
+ int search_key; /* Key of item to search for in skip list */
+ int *found_item; /* Item found in skip list */
+ ssize_t num; /* Number of elements in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Removal From Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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");
+
+ /* Try removing an item in empty skip list */
+ search_key=37;
+ found_item=H5SL_remove(slist,&search_key);
+ VERIFY(found_item, NULL, "H5SL_remove");
+
+ /* Insert three objects into the skip list */
+ key1=15;
+ ret=H5SL_insert(slist,&key1,&key1);
+ CHECK(ret, FAIL, "H5SL_insert");
+
+ key2=10;
+ ret=H5SL_insert(slist,&key2,&key2);
+ CHECK(ret, FAIL, "H5SL_insert");
+
+ key3=20;
+ ret=H5SL_insert(slist,&key3,&key3);
+ CHECK(ret, FAIL, "H5SL_insert");
+
+ /* Check that the skip list has three elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 3, "H5SL_count");
+
+ /* Try removing items from skip list */
+ search_key=key1;
+ found_item=H5SL_remove(slist,&search_key);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(found_item, &key1, "H5SL_remove");
+
+ search_key=key2;
+ found_item=H5SL_remove(slist,&search_key);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(found_item, &key2, "H5SL_remove");
+
+ search_key=key3;
+ found_item=H5SL_remove(slist,&search_key);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(found_item, &key3, "H5SL_remove");
+
+ /* Check that the skip list has no elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 0, "H5SL_count");
+
+ /* Try removing items from empty skip list (after its been worked on) */
+ search_key=key1;
+ found_item=H5SL_remove(slist,&search_key);
+ VERIFY(found_item, NULL, "H5SL_remove");
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_remove() */
+
+/****************************************************************
+**
+** test_skiplist_remove_many(): Test H5SL (skip list) code.
+** Tests removing many objects from skip list.
+**
+****************************************************************/
+static void
+test_skiplist_remove_many(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ ssize_t num; /* Number of elements in skip list */
+ size_t u; /* Local index variable */
+ int *found_item; /* Item found in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Removal of Many Items From Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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 many objects into the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ ret=H5SL_insert(slist,&rand_num[u],&rand_num[u]);
+ CHECK(ret, FAIL, "H5SL_insert");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "H5SL_count");
+
+ /* Remove all objects from the skip list (in random order) */
+ for(u=0; u<NUM_ELEMS; u++) {
+ found_item=H5SL_remove(slist,&rand_num[u]);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(*found_item,rand_num[u],"H5SL_remove");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 0, "H5SL_count");
+
+/* Insert & remove again (in sorted order), to check that completely empty heaps can be added again */
+
+ /* Insert many objects into the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ ret=H5SL_insert(slist,&rand_num[u],&rand_num[u]);
+ CHECK(ret, FAIL, "H5SL_insert");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "H5SL_count");
+
+ /* Remove all objects from the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ found_item=H5SL_remove(slist,&sort_rand_num[u]);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(*found_item,sort_rand_num[u],"H5SL_remove");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 0, "H5SL_count");
+
+/* Insert & remove again (in reverse sorted order), to check that completely empty heaps can be added again */
+
+ /* Insert many objects into the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ ret=H5SL_insert(slist,&rand_num[u],&rand_num[u]);
+ CHECK(ret, FAIL, "H5SL_insert");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "H5SL_count");
+
+ /* Remove all objects from the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ found_item=H5SL_remove(slist,&rev_sort_rand_num[u]);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(*found_item,rev_sort_rand_num[u],"H5SL_remove");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 0, "H5SL_count");
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_remove_many() */
+
+/****************************************************************
+**
+** test_skiplist_iterate(): Test H5SL (skip list) code.
+** Tests iterating over nodes in skip list.
+**
+****************************************************************/
+static void
+test_skiplist_iterate(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ H5SL_node_t *node; /* Skip list node */
+ ssize_t num; /* Number of elements in skip list */
+ size_t u; /* Local index variable */
+ int *found_item; /* Item found in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Iterating Over Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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 many objects into the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ ret=H5SL_insert(slist,&rand_num[u],&rand_num[u]);
+ CHECK(ret, FAIL, "H5SL_insert");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "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,sort_rand_num[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_iterate() */
+
+/****************************************************************
+**
+** test_skiplist(): Main H5SL testing routine.
+**
+****************************************************************/
+void
+test_skiplist(void)
+{
+ /* Output message about test being performed */
+ MESSAGE(5, ("Testing Skip Lists\n"));
+
+ /* Initialize skip list testing data */
+ test_skiplist_init();
+
+ /* Actual skip list tests */
+ test_skiplist_create(); /* Test skip list creation */
+ test_skiplist_insert(); /* Test basic skip list insertion */
+ test_skiplist_insert_many(); /* Test insertion of many items into skip list */
+ test_skiplist_remove(); /* Test basic skip list removal */
+ test_skiplist_remove_many(); /* Test removal of many items from skip list */
+ test_skiplist_iterate(); /* Test iteration over skip list nodes */
+
+} /* end test_skiplist() */
+
+
generated by cgit v0.12 at 2024-11-03 04:53:30 (GMT)