diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/H5Edefin.h | 8 | ||||
| -rw-r--r-- | src/H5Einit.h | 24 | ||||
| -rw-r--r-- | src/H5Epubgen.h | 12 | ||||
| -rw-r--r-- | src/H5Eterm.h | 8 | ||||
| -rw-r--r-- | src/H5HP.c | 16 | ||||
| -rw-r--r-- | src/H5SL.c | 715 | ||||
| -rw-r--r-- | src/H5SLprivate.h | 66 | ||||
| -rw-r--r-- | src/H5err.txt | 10 | ||||
| -rw-r--r-- | src/Makefile.in | 6 |
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= @@ -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 |