[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

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; u<NUM_ELEMS; u++) {
@@ -415,7 +415,7 @@ test_skiplist_remove_many(void)
     num=H5SL_count(slist);
     VERIFY(num, 0, "H5SL_count");
 
-/* Insert & remove again (in reverse sorted order), to check that completely empty heaps can be added again */
+/* Insert & remove again (in reverse sorted order), to check that completely empty skip lists can be added again */
 
     /* Insert many objects into the skip list */
     for(u=0; u<NUM_ELEMS; u++) {
@@ -463,7 +463,7 @@ test_skiplist_iterate(void)
     /* Output message about test being performed */
     MESSAGE(7, ("Testing Iterating Over Skip List\n"));
 
-    /* Create a Heap */
+    /* Create a skip list */
     slist=H5SL_create(H5SL_TYPE_INT, 0.5, 16);
     CHECK(slist, NULL, "H5SL_create");
 
@@ -499,6 +499,85 @@ test_skiplist_iterate(void)
 
 /****************************************************************
 **
+**  test_skiplist_string(): Test H5SL (skip list) code.
+**      Tests using strings for keys in skip lists.
+** 
+****************************************************************/
+static void 
+test_skiplist_string(void)
+{
+    H5SL_t *slist;      /* Skip list created */
+    H5SL_node_t *node;  /* Skip list node */
+    ssize_t num;        /* Number of elements in skip list */
+    size_t u;           /* Local index variable */
+    typedef struct string_node {
+        int i;
+        const char *s;
+    } string_node;
+    string_node data[10]={
+        {10,"10"},
+        {20,"20"},
+        {15,"15"},
+        { 5,"05"},
+        {50,"50"},
+        {30,"30"},
+        {31,"31"},
+        {32,"32"},
+        {80,"80"},
+        {90,"90"}};
+    string_node sorted_data[10]={
+        { 5,"05"},
+        {10,"10"},
+        {15,"15"},
+        {20,"20"},
+        {30,"30"},
+        {31,"31"},
+        {32,"32"},
+        {50,"50"},
+        {80,"80"},
+        {90,"90"}};
+    string_node *found_item;    /* Item found in skip list */
+    herr_t ret;         /* Generic return value */
+
+    /* Output message about test being performed */
+    MESSAGE(7, ("Testing Skip List With String Keys\n"));
+
+    /* Create a skip list */
+    slist=H5SL_create(H5SL_TYPE_STR, 0.5, 16);
+    CHECK(slist, NULL, "H5SL_create");
+
+    /* Check that the skip list has no elements */
+    num=H5SL_count(slist);
+    VERIFY(num, 0, "H5SL_count");
+
+    /* Insert objects into the skip list */
+    for(u=0; u<10; u++) {
+        ret=H5SL_insert(slist,&data[u],&data[u].s);
+        CHECK(ret, FAIL, "H5SL_insert");
+    } /* end for */
+
+    /* Check that the skip list has correct # of elements */
+    num=H5SL_count(slist);
+    VERIFY(num, 10, "H5SL_count");
+
+    /* Iterate over all the nodes in the skip list */
+    node=H5SL_first(slist);
+    u=0;
+    while(node!=NULL) {
+        found_item=H5SL_item(node);
+        VERIFY(found_item->i,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() */
 
-