[svn-r16699] Purpose: Fix bug 503

Description:
Changed Skip list package to use a deterministic skip list.  This allows the
skip list package to avoid calling rand() and srand(), even on machines without
rand_r().  There is no longer a p-value or maximum level for skip lists.

Tested: jam, smirom, linew (h5committest)

1 files changed, 69 insertions, 23 deletions

diff --git a/test/tskiplist.c b/test/tskiplist.c
index 289df0b..7b3dcef 100644
--- a/test/tskiplist.c
+++ b/test/tskiplist.c
@@ -121,7 +121,7 @@ test_skiplist_create(void)
     MESSAGE(6, ("Testing Creating & Closing Skip Lists\n"));
 
     /* Try creating a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Try closing the skip list */
@@ -151,7 +151,7 @@ test_skiplist_insert(void)
     MESSAGE(7, ("Testing Insertion Into Skip List\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -212,7 +212,7 @@ test_skiplist_insert_many(void)
     MESSAGE(7, ("Testing Insertion of Many Items Into Skip List\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -286,7 +286,7 @@ test_skiplist_remove(void)
     MESSAGE(7, ("Testing Removal From Skip List\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -365,7 +365,7 @@ test_skiplist_remove_many(void)
     MESSAGE(7, ("Testing Removal of Many Items From Skip List\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -465,7 +465,7 @@ test_skiplist_firstnext(void)
     MESSAGE(7, ("Testing Iterating Over Skip List With First/Next\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -558,7 +558,7 @@ test_skiplist_string(void)
     MESSAGE(7, ("Testing Skip List With String Keys\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_STR, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_STR);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -620,7 +620,7 @@ test_skiplist_iterate(void)
     MESSAGE(7, ("Testing Iterating Over Skip List\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -670,7 +670,7 @@ test_skiplist_hsize(void)
     MESSAGE(7, ("Testing Skip List With hsize_t Keys\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_HSIZE, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_HSIZE);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -725,7 +725,7 @@ test_skiplist_unsigned(void)
     MESSAGE(7, ("Testing Skip List With unsigned Keys\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_UNSIGNED);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -778,7 +778,7 @@ test_skiplist_lastprev(void)
     MESSAGE(7, ("Testing Iterating Over Skip List With Last/Prev\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Check that the skip list has no elements */
@@ -846,7 +846,7 @@ test_skiplist_find(void)
     MESSAGE(7, ("Testing Skip List 'Find' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_UNSIGNED);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -902,7 +902,7 @@ test_skiplist_add(void)
     MESSAGE(7, ("Testing Skip List 'Add' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_UNSIGNED);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -964,7 +964,7 @@ test_skiplist_destroy(void)
     MESSAGE(7, ("Testing Skip List 'Destroy' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -1000,7 +1000,7 @@ test_skiplist_free(void)
     MESSAGE(7, ("Testing Skip List 'Free' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_INT, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_INT);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -1056,7 +1056,7 @@ test_skiplist_less(void)
     MESSAGE(7, ("Testing Skip List 'Less' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_UNSIGNED);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -1120,7 +1120,7 @@ test_skiplist_greater(void)
     MESSAGE(7, ("Testing Skip List 'Greater' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_UNSIGNED);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -1182,10 +1182,10 @@ test_skiplist_below(void)
     herr_t ret;         /* Generic return value */
 
     /* Output message about test being performed */
-    MESSAGE(7, ("Testing Skip List 'Less' Operation\n"));
+    MESSAGE(7, ("Testing Skip List 'Below' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_UNSIGNED);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -1261,10 +1261,10 @@ test_skiplist_above(void)
     herr_t ret;         /* Generic return value */
 
     /* Output message about test being performed */
-    MESSAGE(7, ("Testing Skip List 'Greater' Operation\n"));
+    MESSAGE(7, ("Testing Skip List 'Above' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_UNSIGNED);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -1338,10 +1338,10 @@ test_skiplist_remove_first(void)
     herr_t ret;         /* Generic return value */
 
     /* Output message about test being performed */
-    MESSAGE(7, ("Testing Skip List 'Greater' Operation\n"));
+    MESSAGE(7, ("Testing Skip List 'Remove First' Operation\n"));
 
     /* Create a skip list */
-    slist = H5SL_create(H5SL_TYPE_UNSIGNED, 0.5, (size_t)16);
+    slist = H5SL_create(H5SL_TYPE_UNSIGNED);
     CHECK(slist, NULL, "H5SL_create");
 
     /* Insert objects into the skip list */
@@ -1368,6 +1368,51 @@ test_skiplist_remove_first(void)
 
 /****************************************************************
 **
+**  test_skiplist_remote_first_many(): Test H5SL (skip list) code.
+**      Tests 'remove first' operation in large skip lists.
+**
+****************************************************************/
+static void
+test_skiplist_remove_first_many(void)
+{
+    H5SL_t  *slist;         /* Skip list created */
+    size_t  u;              /* Local index variable */
+    int     *found_item;    /* Item found in skip list */
+    int     prev_item = INT_MIN; /* Previously found item in skip list */
+    herr_t  ret;            /* Generic return value */
+
+    /* Output message about test being performed */
+    MESSAGE(7, ("Testing Skip List 'Remove First' Operation\n"));
+
+    /* Create a skip list */
+    slist = H5SL_create(H5SL_TYPE_INT);
+    CHECK(slist, NULL, "H5SL_create");
+
+    /* Insert objects into the skip list */
+    for(u = 0; u < NUM_ELEMS; u++) {
+        ret = H5SL_insert(slist, &rand_num[u], &rand_num[u]);
+        CHECK(ret, FAIL, "H5SL_insert");
+    } /* end for */
+
+    /* Remove objects from the skip list */
+    for(u = 0; u < NUM_ELEMS; u++) {
+        found_item = (int *)H5SL_remove_first(slist);
+        VERIFY(*found_item > prev_item, TRUE, "H5SL_remove_first");
+        prev_item = *found_item;
+    } /* end for */
+
+    /* Check for removing object from empty list */
+    found_item = (int *)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.
 **
 ****************************************************************/
@@ -1401,6 +1446,7 @@ test_skiplist(void)
     test_skiplist_below();      /* Test 'below' operation */
     test_skiplist_above();      /* Test 'above' operation */
     test_skiplist_remove_first();   /* Test 'remove first' operation */
+    test_skiplist_remove_first_many();  /* Test 'remove first' operation on large skip lists */
 
 }   /* end test_skiplist() */