diff options
| -rw-r--r-- | src/H5SL.c | 258 | ||||
| -rw-r--r-- | src/H5SLprivate.h | 5 | ||||
| -rw-r--r-- | test/tskiplist.c | 112 |
3 files changed, 334 insertions, 41 deletions
@@ -57,11 +57,12 @@ /* Local Macros */ /* Define the code template for insertions for the "OP" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_INSERT_FOUND(SLIST,X,UPDATE,I,ITEM) \ +#define H5SL_LOCATE_INSERT_FOUND(SLIST,X,UPDATE,I) \ HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,NULL,"can't insert duplicate key"); /* Define the code template for removals for the "OP" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_REMOVE_FOUND(SLIST,X,UPDATE,I,ITEM) \ +/* (NOTE: the code in H5SL_remove_first() is largely the same, fix bugs in both places) */ +#define H5SL_LOCATE_REMOVE_FOUND(SLIST,X,UPDATE,I) \ void *tmp; \ \ for(I=0; I<=(int)SLIST->curr_level; I++) { \ @@ -81,11 +82,11 @@ HGOTO_DONE(tmp); /* Define the code template for searches for the "OP" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_SEARCH_FOUND(SLIST,X,UPDATE,I,ITEM) \ +#define H5SL_LOCATE_SEARCH_FOUND(SLIST,X,UPDATE,I) \ HGOTO_DONE(X->item); /* Define the code template for finds for the "OP" in the H5SL_LOCATE macro */ -#define H5SL_LOCATE_FIND_FOUND(SLIST,X,UPDATE,I,ITEM) \ +#define H5SL_LOCATE_FIND_FOUND(SLIST,X,UPDATE,I) \ HGOTO_DONE(X); /* Define a code template for updating the "update" vector for the "DOUPDATE" in the H5SL_LOCATE macro */ @@ -112,7 +113,7 @@ (HDstrcmp(PKEY1,PKEY2)==0) /* Macro used to find node for operation */ -#define H5SL_LOCATE(OP,DOUPDATE,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ +#define H5SL_LOCATE(OP,DOUPDATE,CMP,SLIST,X,UPDATE,I,TYPE,KEY,CHECKED) \ CHECKED=NULL; \ for(I=(int)SLIST->curr_level; I>=0; I--) { \ if(X->forward[I]!=CHECKED) { \ @@ -125,24 +126,24 @@ X=X->forward[0]; \ if(X!=NULL && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(TYPE,X->key,KEY) ) { \ /* What to do when a node is found */ \ - H5_GLUE3(H5SL_LOCATE_,OP,_FOUND)(SLIST,X,UPDATE,I,ITEM) \ + H5_GLUE3(H5SL_LOCATE_,OP,_FOUND)(SLIST,X,UPDATE,I) \ } /* end if */ /* Macro used to insert node */ -#define H5SL_INSERT(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ - H5SL_LOCATE(INSERT,YES,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) +#define H5SL_INSERT(CMP, SLIST, X, UPDATE, I, TYPE, KEY, CHECKED) \ + H5SL_LOCATE(INSERT, YES, CMP, SLIST, X, UPDATE, I, TYPE, KEY, CHECKED) /* Macro used to remove node */ -#define H5SL_REMOVE(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ - H5SL_LOCATE(REMOVE,YES,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) +#define H5SL_REMOVE(CMP, SLIST, X, UPDATE, I, TYPE, KEY, CHECKED) \ + H5SL_LOCATE(REMOVE, YES, CMP, SLIST, X, UPDATE, I, TYPE, KEY, CHECKED) /* Macro used to search for node */ -#define H5SL_SEARCH(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ - H5SL_LOCATE(SEARCH,NO,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) +#define H5SL_SEARCH(CMP, SLIST, X, UPDATE, I, TYPE, KEY, CHECKED) \ + H5SL_LOCATE(SEARCH, NO, CMP, SLIST, X, UPDATE, I, TYPE, KEY, CHECKED) /* Macro used to find a node */ -#define H5SL_FIND(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ - H5SL_LOCATE(FIND,NO,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) +#define H5SL_FIND(CMP, SLIST, X, UPDATE, I, TYPE, KEY, CHECKED) \ + H5SL_LOCATE(FIND, NO, CMP, SLIST, X, UPDATE, I, TYPE, KEY, CHECKED) /* Private typedefs & structs */ @@ -363,23 +364,27 @@ H5SL_insert_common(H5SL_t *slist, void *item, const void *key) x=slist->header; switch(slist->type) { case H5SL_TYPE_INT: - H5SL_INSERT(SCALAR,slist,x,update,i,const int,item,key,checked) + H5SL_INSERT(SCALAR, slist, x, update, i, const int, key, checked) break; case H5SL_TYPE_HADDR: - H5SL_INSERT(SCALAR,slist,x,update,i,const haddr_t,item,key,checked) + H5SL_INSERT(SCALAR, slist, x, update, i, const haddr_t, key, checked) break; case H5SL_TYPE_STR: - H5SL_INSERT(STRING,slist,x,update,i,char *,item,key,checked) + H5SL_INSERT(STRING, slist, x, update, i, char *, key, checked) break; case H5SL_TYPE_HSIZE: - H5SL_INSERT(SCALAR,slist,x,update,i,const hsize_t,item,key,checked) + H5SL_INSERT(SCALAR, slist, x, update, i, const hsize_t, key, checked) break; case H5SL_TYPE_UNSIGNED: - H5SL_INSERT(SCALAR,slist,x,update,i,const unsigned,item,key,checked) + H5SL_INSERT(SCALAR, slist, x, update, i, const unsigned, key, checked) + break; + + case H5SL_TYPE_SIZE: + H5SL_INSERT(SCALAR, slist, x, update, i, const size_t, key, checked) break; } /* end switch */ @@ -574,7 +579,7 @@ H5SL_create(H5SL_type_t type, double p, size_t max_level) /* Check args */ HDassert(p>0.0 && p<1.0); HDassert(max_level>0 && max_level<=H5SL_LEVEL_MAX); - HDassert(type>=H5SL_TYPE_INT && type<=H5SL_TYPE_UNSIGNED); + HDassert(type>=H5SL_TYPE_INT && type<=H5SL_TYPE_SIZE); /* Allocate skip list structure */ if((new_slist=H5FL_MALLOC(H5SL_t))==NULL) @@ -789,23 +794,27 @@ H5SL_remove(H5SL_t *slist, const void *key) x=slist->header; switch(slist->type) { case H5SL_TYPE_INT: - H5SL_REMOVE(SCALAR,slist,x,update,i,const int,-,key,checked) + H5SL_REMOVE(SCALAR, slist, x, update, i, const int, key, checked) break; case H5SL_TYPE_HADDR: - H5SL_REMOVE(SCALAR,slist,x,update,i,const haddr_t,-,key,checked) + H5SL_REMOVE(SCALAR, slist, x, update, i, const haddr_t, key, checked) break; case H5SL_TYPE_STR: - H5SL_REMOVE(STRING,slist,x,update,i,char *,-,key,checked) + H5SL_REMOVE(STRING, slist, x, update, i, char *, key, checked) break; case H5SL_TYPE_HSIZE: - H5SL_REMOVE(SCALAR,slist,x,update,i,const hsize_t,-,key,checked) + H5SL_REMOVE(SCALAR, slist, x, update, i, const hsize_t, key, checked) break; case H5SL_TYPE_UNSIGNED: - H5SL_REMOVE(SCALAR,slist,x,update,i,const unsigned,-,key,checked) + H5SL_REMOVE(SCALAR, slist, x, update, i, const unsigned, key, checked) + break; + + case H5SL_TYPE_SIZE: + H5SL_REMOVE(SCALAR, slist, x, update, i, const size_t, key, checked) break; } /* end switch */ @@ -816,6 +825,80 @@ done: /*-------------------------------------------------------------------------- NAME + H5SL_remove_first + PURPOSE + Removes the first object from a skip list + USAGE + void *H5SL_remove_first(slist) + H5SL_t *slist; IN/OUT: Pointer to skip list + + RETURNS + Returns pointer to item removed on success, NULL on failure. + DESCRIPTION + Remove first element from a skip list. + GLOBAL VARIABLES + COMMENTS, BUGS, ASSUMPTIONS + This algorithm is basically the same as the one in the + H5SL_LOCATE_REMOVE_FOUND macro, fix bugs in both places + EXAMPLES + REVISION LOG +--------------------------------------------------------------------------*/ +void * +H5SL_remove_first(H5SL_t *slist) +{ + void *ret_value = NULL; /* Return value */ + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_remove_first) + + /* Check args */ + HDassert(slist); + + /* Check internal consistency */ + /* (Pre-condition) */ + + /* Remove item from skip list */ + + /* Check for empty list */ + if(slist->last != slist->header) { + H5SL_node_t *x; /* Current node to examine */ + int i; /* Local index value */ + + /* Get pointer to first node on the list */ + x = slist->header->forward[0]; + + /* Patch forward pointers in list header around node to remove */ + for(i = 0; i <= (int)slist->curr_level; i++) { + if(slist->header->forward[i] != x) + break; + slist->header->forward[i] = x->forward[i]; + } /* end for */ + + /* Update tail/backward pointer */ + if(slist->last == x) + slist->last = x->backward; + else + x->forward[0]->backward = x->backward; + + /* Get the item to return */ + ret_value = x->item; + + /* Free the skip list node */ + H5FL_ARR_FREE(H5SL_node_ptr_t, x); + + /* Lower the level of the list, if we removed the tallest node */ + while(slist->curr_level > 0 && slist->header->forward[slist->curr_level] == NULL) + slist->curr_level--; + + /* Decrement the # of objects in the list */ + slist->nobjs--; + } /* end if */ + + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5SL_remove_first() */ + + +/*-------------------------------------------------------------------------- + NAME H5SL_search PURPOSE Search for object in a skip list @@ -858,23 +941,27 @@ H5SL_search(H5SL_t *slist, const void *key) x=slist->header; switch(slist->type) { case H5SL_TYPE_INT: - H5SL_SEARCH(SCALAR,slist,x,-,i,const int,-,key,checked) + H5SL_SEARCH(SCALAR, slist, x, -, i, const int, key, checked) break; case H5SL_TYPE_HADDR: - H5SL_SEARCH(SCALAR,slist,x,-,i,const haddr_t,-,key,checked) + H5SL_SEARCH(SCALAR, slist, x, -, i, const haddr_t, key, checked) break; case H5SL_TYPE_STR: - H5SL_SEARCH(STRING,slist,x,-,i,char *,-,key,checked) + H5SL_SEARCH(STRING, slist, x, -, i, char *, key, checked) break; case H5SL_TYPE_HSIZE: - H5SL_SEARCH(SCALAR,slist,x,-,i,const hsize_t,-,key,checked) + H5SL_SEARCH(SCALAR, slist, x, -, i, const hsize_t, key, checked) break; case H5SL_TYPE_UNSIGNED: - H5SL_SEARCH(SCALAR,slist,x,-,i,const unsigned,-,key,checked) + H5SL_SEARCH(SCALAR, slist, x, -, i, const unsigned, key, checked) + break; + + case H5SL_TYPE_SIZE: + H5SL_SEARCH(SCALAR, slist, x, -, i, const size_t, key, checked) break; } /* end switch */ @@ -933,23 +1020,27 @@ H5SL_less(H5SL_t *slist, const void *key) x=slist->header; switch(slist->type) { case H5SL_TYPE_INT: - H5SL_SEARCH(SCALAR,slist,x,-,i,const int,-,key,checked) + H5SL_SEARCH(SCALAR, slist, x, -, i, const int, key, checked) break; case H5SL_TYPE_HADDR: - H5SL_SEARCH(SCALAR,slist,x,-,i,const haddr_t,-,key,checked) + H5SL_SEARCH(SCALAR, slist, x, -, i, const haddr_t, key, checked) break; case H5SL_TYPE_STR: - H5SL_SEARCH(STRING,slist,x,-,i,char *,-,key,checked) + H5SL_SEARCH(STRING, slist, x, -, i, char *, key, checked) break; case H5SL_TYPE_HSIZE: - H5SL_SEARCH(SCALAR,slist,x,-,i,const hsize_t,-,key,checked) + H5SL_SEARCH(SCALAR, slist, x, -, i, const hsize_t, key, checked) break; case H5SL_TYPE_UNSIGNED: - H5SL_SEARCH(SCALAR,slist,x,-,i,const unsigned,-,key,checked) + H5SL_SEARCH(SCALAR, slist, x, -, i, const unsigned, key, checked) + break; + + case H5SL_TYPE_SIZE: + H5SL_SEARCH(SCALAR, slist, x, -, i, const size_t, key, checked) break; } /* end switch */ @@ -976,6 +1067,89 @@ done: /*-------------------------------------------------------------------------- NAME + H5SL_greater + PURPOSE + Search for object in a skip list that is greater than or equal to 'key' + USAGE + void *H5SL_greater(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 who key is greater than or equal to 'key' on success, + NULL on failure + DESCRIPTION + Search for an object in a skip list, according to it's key, returning the + object itself (for an exact match), or the object with the next lowest + key that is greater than 'key' + GLOBAL VARIABLES + COMMENTS, BUGS, ASSUMPTIONS + EXAMPLES + REVISION LOG +--------------------------------------------------------------------------*/ +void * +H5SL_greater(H5SL_t *slist, const 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_greater); + + /* Check args */ + HDassert(slist); + HDassert(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(SCALAR, slist, x, -, i, const int, key, checked) + break; + + case H5SL_TYPE_HADDR: + H5SL_SEARCH(SCALAR, slist, x, -, i, const haddr_t, key, checked) + break; + + case H5SL_TYPE_STR: + H5SL_SEARCH(STRING, slist, x, -, i, char *, key, checked) + break; + + case H5SL_TYPE_HSIZE: + H5SL_SEARCH(SCALAR, slist, x, -, i, const hsize_t, key, checked) + break; + + case H5SL_TYPE_UNSIGNED: + H5SL_SEARCH(SCALAR, slist, x, -, i, const unsigned, key, checked) + break; + + case H5SL_TYPE_SIZE: + H5SL_SEARCH(SCALAR, slist, x, -, i, const size_t, key, checked) + break; + } /* end switch */ + + /* An exact match for 'key' must not have been found in list, if we get here */ + /* ('x' must be the next node with a key greater than the 'key', or NULL) */ + if(x) + ret_value = x->item; + else + ret_value = NULL; + +done: + FUNC_LEAVE_NOAPI(ret_value); +} /* end H5SL_greater() */ + + +/*-------------------------------------------------------------------------- + NAME H5SL_find PURPOSE Search for _node_ in a skip list @@ -1020,23 +1194,27 @@ H5SL_find(H5SL_t *slist, const void *key) x=slist->header; switch(slist->type) { case H5SL_TYPE_INT: - H5SL_FIND(SCALAR,slist,x,-,i,const int,-,key,checked) + H5SL_FIND(SCALAR, slist, x, -, i, const int, key, checked) break; case H5SL_TYPE_HADDR: - H5SL_FIND(SCALAR,slist,x,-,i,const haddr_t,-,key,checked) + H5SL_FIND(SCALAR, slist, x, -, i, const haddr_t, key, checked) break; case H5SL_TYPE_STR: - H5SL_FIND(STRING,slist,x,-,i,char *,-,key,checked) + H5SL_FIND(STRING, slist, x, -, i, char *, key, checked) break; case H5SL_TYPE_HSIZE: - H5SL_FIND(SCALAR,slist,x,-,i,const hsize_t,-,key,checked) + H5SL_FIND(SCALAR, slist, x, -, i, const hsize_t, key, checked) break; case H5SL_TYPE_UNSIGNED: - H5SL_FIND(SCALAR,slist,x,-,i,const unsigned,-,key,checked) + H5SL_FIND(SCALAR, slist, x, -, i, const unsigned, key, checked) + break; + + case H5SL_TYPE_SIZE: + H5SL_FIND(SCALAR, slist, x, -, i, const size_t, key, checked) break; } /* end switch */ diff --git a/src/H5SLprivate.h b/src/H5SLprivate.h index bf8d3b7..d37f130 100644 --- a/src/H5SLprivate.h +++ b/src/H5SLprivate.h @@ -44,7 +44,8 @@ typedef enum { H5SL_TYPE_HADDR, /* Skip list keys are 'haddr_t's */ H5SL_TYPE_STR, /* Skip list keys are 'char *'s (ie. strings) */ H5SL_TYPE_HSIZE, /* Skip list keys are 'hsize_t's */ - H5SL_TYPE_UNSIGNED /* Skip list keys are 'unsigned's */ + H5SL_TYPE_UNSIGNED, /* Skip list keys are 'unsigned's */ + H5SL_TYPE_SIZE /* Skip list keys are 'size_t's */ } H5SL_type_t; /**********/ @@ -64,8 +65,10 @@ H5_DLL size_t H5SL_count(H5SL_t *slist); H5_DLL herr_t H5SL_insert(H5SL_t *slist, void *item, const void *key); H5_DLL H5SL_node_t *H5SL_add(H5SL_t *slist, void *item, const void *key); H5_DLL void *H5SL_remove(H5SL_t *slist, const void *key); +H5_DLL void *H5SL_remove_first(H5SL_t *slist); H5_DLL void *H5SL_search(H5SL_t *slist, const void *key); H5_DLL void *H5SL_less(H5SL_t *slist, const void *key); +H5_DLL void *H5SL_greater(H5SL_t *slist, const void *key); H5_DLL H5SL_node_t *H5SL_find(H5SL_t *slist, const void *key); H5_DLL H5SL_node_t *H5SL_first(H5SL_t *slist); H5_DLL H5SL_node_t *H5SL_next(H5SL_node_t *slist_node); diff --git a/test/tskiplist.c b/test/tskiplist.c index 9a29c95..c76b79c 100644 --- a/test/tskiplist.c +++ b/test/tskiplist.c @@ -1099,6 +1099,116 @@ test_skiplist_less(void) /**************************************************************** ** +** test_skiplist_greater(): Test H5SL (skip list) code. +** Tests 'greater' operation in skip lists. +** +****************************************************************/ +static void +test_skiplist_greater(void) +{ + H5SL_t *slist; /* Skip list created */ + size_t u; /* Local index variable */ + unsigned data[10]={ 10, 20, 15, 5, 50, 30, 31, 32, 80, 90}; + /* unsigned sorted_data[10]={ 5, 10, 15, 20, 30, 31, 32, 50, 80, 90}; */ + unsigned *found_item; /* Item found in skip list */ + unsigned find_item; /* Item to add to skip list */ + herr_t ret; /* Generic return value */ + + /* Output message about test being performed */ + MESSAGE(7, ("Testing Skip List 'Greater' Operation\n")); + + /* Create a skip list */ + slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, 16); + CHECK(slist, NULL, "H5SL_create"); + + /* Insert objects into the skip list */ + for(u = 0; u < 10; u++) { + ret = H5SL_insert(slist, &data[u], &data[u]); + CHECK(ret, FAIL, "H5SL_insert"); + } /* end for */ + + /* Check for exact match of items in various positions */ + find_item = 20; + found_item = H5SL_greater(slist, &find_item); + VERIFY(*found_item, find_item, "H5SL_greater"); + find_item = 90; + found_item = H5SL_greater(slist, &find_item); + VERIFY(*found_item, find_item, "H5SL_greater"); + find_item = 5; + found_item = H5SL_greater(slist, &find_item); + VERIFY(*found_item, find_item, "H5SL_greater"); + + /* Find item greater than a missing key, in various positions */ + find_item = 19; + found_item = H5SL_greater(slist,&find_item); + VERIFY(*found_item, 20, "H5SL_greater"); + find_item = 89; + found_item = H5SL_greater(slist, &find_item); + VERIFY(*found_item, 90, "H5SL_greater"); + find_item = 100; + found_item = H5SL_greater(slist, &find_item); + VERIFY(found_item, NULL, "H5SL_greater"); + find_item = 6; + found_item = H5SL_greater(slist, &find_item); + VERIFY(*found_item, 10, "H5SL_greater"); + find_item = 4; + found_item = H5SL_greater(slist, &find_item); + VERIFY(*found_item, 5, "H5SL_greater"); + + /* Close the skip list */ + ret = H5SL_close(slist); + CHECK(ret, FAIL, "H5SL_close"); + +} /* end test_skiplist_greater() */ + +/**************************************************************** +** +** test_skiplist_remote_first(): Test H5SL (skip list) code. +** Tests 'remove first' operation in skip lists. +** +****************************************************************/ +static void +test_skiplist_remove_first(void) +{ + H5SL_t *slist; /* Skip list created */ + size_t u; /* Local index variable */ + unsigned data[10]={ 10, 20, 15, 5, 50, 30, 31, 32, 80, 90}; + unsigned sorted_data[10]={ 5, 10, 15, 20, 30, 31, 32, 50, 80, 90}; + unsigned *found_item; /* Item found in skip list */ + unsigned find_item; /* Item to add to skip list */ + herr_t ret; /* Generic return value */ + + /* Output message about test being performed */ + MESSAGE(7, ("Testing Skip List 'Greater' Operation\n")); + + /* Create a skip list */ + slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, 16); + CHECK(slist, NULL, "H5SL_create"); + + /* Insert objects into the skip list */ + for(u = 0; u < 10; u++) { + ret = H5SL_insert(slist, &data[u], &data[u]); + CHECK(ret, FAIL, "H5SL_insert"); + } /* end for */ + + /* Remove objects from the skip list */ + for(u = 0; u < 10; u++) { + found_item = H5SL_remove_first(slist); + VERIFY(*found_item, sorted_data[u], "H5SL_remove_first"); + } /* end for */ + + /* Check for removing object from empty list */ + found_item = H5SL_remove_first(slist); + VERIFY(found_item, NULL, "H5SL_remove_first"); + + /* Close the skip list */ + ret = H5SL_close(slist); + CHECK(ret, FAIL, "H5SL_close"); + +} /* end test_skiplist_remove_first() */ + +/**************************************************************** +** ** test_skiplist(): Main H5SL testing routine. ** ****************************************************************/ @@ -1128,6 +1238,8 @@ test_skiplist(void) test_skiplist_destroy(); /* Test 'destroy' operation */ test_skiplist_free(); /* Test 'free' operation */ test_skiplist_less(); /* Test 'less' operation */ + test_skiplist_greater(); /* Test 'greater' operation */ + test_skiplist_remove_first(); /* Test 'remove first' operation */ } /* end test_skiplist() */ |