summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-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
9 files changed, 845 insertions, 20 deletions
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