From 5d104d60c92428c8460673591ff07437d44a8a36 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Mon, 29 Nov 2004 23:42:40 -0500 Subject: [svn-r9601] Purpose: New feature Description: Allow skip list keys to be strings (needed for property list support) Platforms tested: FreeBSD 4.10 (sleipnir) Too minor to require h5committest --- src/H5SL.c | 60 +++++++++++++++++++++++++---------- src/H5SLprivate.h | 3 +- test/tskiplist.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++----- 3 files changed, 133 insertions(+), 25 deletions(-) diff --git a/src/H5SL.c b/src/H5SL.c index eea4cdc..01a413f 100644 --- a/src/H5SL.c +++ b/src/H5SL.c @@ -76,34 +76,50 @@ /* 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) +/* Define a code template for comparing scalar keys for the "CMP" in the H5SL_FIND macro */ +#define H5SL_FIND_SCALAR_CMP(TYPE,PKEY1,PKEY2) \ + (*(TYPE *)PKEY1<*(TYPE *)PKEY2) + +/* Define a code template for comparing string keys for the "CMP" in the H5SL_FIND macro */ +#define H5SL_FIND_STRING_CMP(TYPE,PKEY1,PKEY2) \ + (HDstrcmp(*(TYPE *)PKEY1,*(TYPE *)PKEY2)<0) + +/* Define a code template for comparing scalar keys for the "EQ" in the H5SL_FIND macro */ +#define H5SL_FIND_SCALAR_EQ(TYPE,PKEY1,PKEY2) \ + (*(TYPE *)PKEY1==*(TYPE *)PKEY2) + +/* Define a code template for comparing string keys for the "EQ" in the H5SL_FIND macro */ +#define H5SL_FIND_STRING_EQ(TYPE,PKEY1,PKEY2) \ + (HDstrcmp(*(TYPE *)PKEY1,*(TYPE *)PKEY2)==0) + /* Macro used to find node for operation */ -#define H5SL_FIND(OP,DOUPDATE,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ +#define H5SL_FIND(OP,DOUPDATE,CMP,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) \ + while(X->forward[I] && H5_GLUE3(H5SL_FIND_,CMP,_CMP)(TYPE,X->forward[I]->key,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) { \ + if(X!=NULL && H5_GLUE3(H5SL_FIND_,CMP,_EQ)(TYPE,X->key,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) +#define H5SL_INSERT(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ + H5SL_FIND(INSERT,YES,CMP,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) +#define H5SL_REMOVE(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ + H5SL_FIND(REMOVE,YES,CMP,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) +#define H5SL_SEARCH(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \ + H5SL_FIND(SEARCH,NO,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) /* Private typedefs & structs */ @@ -288,7 +304,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_HADDR); + HDassert(type>=H5SL_TYPE_INT && type<=H5SL_TYPE_STR); /* Allocate skip list structure */ if((new_slist=H5FL_MALLOC(H5SL_t))==NULL) @@ -411,11 +427,15 @@ H5SL_insert(H5SL_t *slist, void *item, void *key) x=slist->header; switch(slist->type) { case H5SL_TYPE_INT: - H5SL_INSERT(slist,x,update,i,int,item,key,checked) + H5SL_INSERT(SCALAR,slist,x,update,i,int,item,key,checked) break; case H5SL_TYPE_HADDR: - H5SL_INSERT(slist,x,update,i,haddr_t,item,key,checked) + H5SL_INSERT(SCALAR,slist,x,update,i,haddr_t,item,key,checked) + break; + + case H5SL_TYPE_STR: + H5SL_INSERT(STRING,slist,x,update,i,char *,item,key,checked) break; } /* end switch */ @@ -496,11 +516,15 @@ H5SL_search(H5SL_t *slist, void *key) x=slist->header; switch(slist->type) { case H5SL_TYPE_INT: - H5SL_SEARCH(slist,x,-,i,int,-,key,checked) + H5SL_SEARCH(SCALAR,slist,x,-,i,int,-,key,checked) break; case H5SL_TYPE_HADDR: - H5SL_SEARCH(slist,x,-,i,haddr_t,-,key,checked) + H5SL_SEARCH(SCALAR,slist,x,-,i,haddr_t,-,key,checked) + break; + + case H5SL_TYPE_STR: + H5SL_SEARCH(STRING,slist,x,-,i,char *,-,key,checked) break; } /* end switch */ @@ -557,11 +581,15 @@ H5SL_remove(H5SL_t *slist, void *key) x=slist->header; switch(slist->type) { case H5SL_TYPE_INT: - H5SL_REMOVE(slist,x,update,i,int,-,key,checked) + H5SL_REMOVE(SCALAR,slist,x,update,i,int,-,key,checked) break; case H5SL_TYPE_HADDR: - H5SL_REMOVE(slist,x,update,i,haddr_t,-,key,checked) + H5SL_REMOVE(SCALAR,slist,x,update,i,haddr_t,-,key,checked) + break; + + case H5SL_TYPE_STR: + H5SL_REMOVE(STRING,slist,x,update,i,char *,-,key,checked) break; } /* end switch */ diff --git a/src/H5SLprivate.h b/src/H5SLprivate.h index e6f64d8..f2a4e24 100644 --- a/src/H5SLprivate.h +++ b/src/H5SLprivate.h @@ -41,7 +41,8 @@ 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_HADDR, /* Skip list keys are 'haddr_t's */ + H5SL_TYPE_STR /* Skip list keys are 'char *'s (ie. strings) */ } H5SL_type_t; /**********/ diff --git a/test/tskiplist.c b/test/tskiplist.c index dfd73a9..4d29d01 100644 --- a/test/tskiplist.c +++ b/test/tskiplist.c @@ -149,7 +149,7 @@ test_skiplist_insert(void) /* Output message about test being performed */ MESSAGE(7, ("Testing Insertion Into Skip List\n")); - /* Create a Heap */ + /* Create a skip list */ slist=H5SL_create(H5SL_TYPE_INT, 0.5, 16); CHECK(slist, NULL, "H5SL_create"); @@ -210,7 +210,7 @@ test_skiplist_insert_many(void) /* Output message about test being performed */ MESSAGE(7, ("Testing Insertion of Many Items Into Skip List\n")); - /* Create a Heap */ + /* Create a skip list */ slist=H5SL_create(H5SL_TYPE_INT, 0.5, 16); CHECK(slist, NULL, "H5SL_create"); @@ -284,7 +284,7 @@ test_skiplist_remove(void) /* Output message about test being performed */ MESSAGE(7, ("Testing Removal From Skip List\n")); - /* Create a Heap */ + /* Create a skip list */ slist=H5SL_create(H5SL_TYPE_INT, 0.5, 16); CHECK(slist, NULL, "H5SL_create"); @@ -363,7 +363,7 @@ test_skiplist_remove_many(void) /* Output message about test being performed */ MESSAGE(7, ("Testing Removal of Many Items From Skip List\n")); - /* Create a Heap */ + /* Create a skip list */ slist=H5SL_create(H5SL_TYPE_INT, 0.5, 16); CHECK(slist, NULL, "H5SL_create"); @@ -392,7 +392,7 @@ test_skiplist_remove_many(void) 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 & remove again (in sorted order), to check that completely empty skip lists can be added again */ /* Insert many objects into the skip list */ for(u=0; ui,sorted_data[u].i,"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_string() */ + +/**************************************************************** +** ** test_skiplist(): Main H5SL testing routine. ** ****************************************************************/ @@ -518,7 +597,7 @@ test_skiplist(void) 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 */ + test_skiplist_string(); /* Test skip list string keys */ } /* end test_skiplist() */ - -- cgit v0.12