summaryrefslogtreecommitdiffstats
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/Makefile.in13
-rw-r--r--test/testhdf5.c1
-rw-r--r--test/testhdf5.h1
-rw-r--r--test/tskiplist.c497
4 files changed, 505 insertions, 7 deletions
diff --git a/test/Makefile.in b/test/Makefile.in
index 56ea6fb..bf3a3d4 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -83,9 +83,9 @@ TEST_SRC=big.c bittests.c cache.c cmpd_dset.c dsets.c dtypes.c extend.c \
external.c fillval.c flush1.c flush2.c gheap.c h5test.c hyperslab.c \
istore.c lheap.c links.c mount.c mtime.c ohdr.c stab.c tarray.c \
tattr.c tconfig.c testhdf5.c testmeta.c tfile.c \
- tgenprop.c th5s.c theap.c titerate.c tmeta.c trefer.c trefstr.c \
- tselect.c ttime.c ttbbt.c ttst.c tvltypes.c tvlstr.c tmisc.c tid.c \
- unlink.c enum.c ttsafe.c ttsafe_dcreate.c ttsafe_error.c \
+ tgenprop.c th5s.c theap.c tid.c titerate.c tmeta.c tmisc.c trefer.c \
+ trefstr.c tselect.c tskiplist.c ttime.c ttbbt.c ttst.c tvltypes.c \
+ tvlstr.c unlink.c enum.c ttsafe.c ttsafe_dcreate.c ttsafe_error.c \
ttsafe_cancel.c ttsafe_acreate.c gass_write.c gass_read.c \
gass_append.c srb_read.c srb_write.c srb_append.c stream_test.c \
set_extent.c getname.c file_handle.c ntypes.c dangle.c error_test.c \
@@ -115,10 +115,9 @@ check test _test: $(PROGS)
## How to build the tests... They all depend on the test and hdf5 libraries.
$(PROGS): $(LIB) $(LIBHDF5)
-TESTHDF5_OBJ=testhdf5.lo tarray.lo tattr.lo tconfig.lo tfile.lo \
- tgenprop.lo th5s.lo theap.lo titerate.lo tmeta.lo ttime.lo trefer.lo \
- trefstr.lo tselect.lo ttbbt.lo ttst.lo tvltypes.lo tvlstr.lo tmisc.lo \
- tid.lo
+TESTHDF5_OBJ=testhdf5.lo tarray.lo tattr.lo tconfig.lo tfile.lo tgenprop.lo \
+ th5s.lo theap.lo tid.lo titerate.lo tmeta.lo tmisc.lo trefer.lo trefstr.lo \
+ tselect.lo tskiplist.lo ttbbt.lo ttime.lo ttst.lo tvltypes.lo tvlstr.lo
TTS_OBJ=ttsafe.lo ttsafe_dcreate.lo ttsafe_error.lo \
ttsafe_cancel.lo ttsafe_acreate.lo
diff --git a/test/testhdf5.c b/test/testhdf5.c
index 6234d01..9d86032 100644
--- a/test/testhdf5.c
+++ b/test/testhdf5.c
@@ -48,6 +48,7 @@ main(int argc, char *argv[])
AddTest("tbbt", test_tbbt, NULL, "Threaded, Balanced, Binary Trees", NULL);
AddTest("tst", test_tst, NULL, "Ternary Search Trees", NULL);
AddTest("heap", test_heap, NULL, "Memory Heaps", NULL);
+ AddTest("skiplist", test_skiplist, NULL, "Skip Lists", NULL);
AddTest("refstr", test_refstr, NULL, "Reference Counted Strings", NULL);
AddTest("file", test_file, cleanup_file, "Low-Level File I/O", NULL);
AddTest("h5s", test_h5s, cleanup_h5s, "Dataspaces", NULL);
diff --git a/test/testhdf5.h b/test/testhdf5.h
index e00f56d..61674a8 100644
--- a/test/testhdf5.h
+++ b/test/testhdf5.h
@@ -130,6 +130,7 @@ void test_genprop(void);
void test_configure(void);
void test_misc(void);
void test_ids(void);
+void test_skiplist(void);
/* Prototypes for the cleanup routines */
void cleanup_metadata(void);
diff --git a/test/tskiplist.c b/test/tskiplist.c
new file mode 100644
index 0000000..20bde76
--- /dev/null
+++ b/test/tskiplist.c
@@ -0,0 +1,497 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/*
+ Test HDF Skip List routines.
+
+ REMARKS
+
+ DESIGN
+
+ BUGS/LIMITATIONS
+
+ EXPORTED ROUTINES
+
+ AUTHOR
+ Quincey Koziol
+
+ MODIFICATION HISTORY
+ 11/15/04 - Started coding
+ */
+
+#include <time.h>
+#include <stdlib.h>
+
+#include "testhdf5.h"
+#include "H5SLprivate.h"
+
+/* The number of elements in testing arrays */
+#define NUM_ELEMS 1000
+
+/* Random numbers */
+static int rand_num[NUM_ELEMS];
+static int sort_rand_num[NUM_ELEMS];
+static int rev_sort_rand_num[NUM_ELEMS];
+
+static int tst_sort(const void *i1, const void *i2)
+{
+ return(*(const int *)i1-*(const int *)i2);
+}
+
+static int tst_rev_sort(const void *i1, const void *i2)
+{
+ return(*(const int *)i2-*(const int *)i1);
+}
+
+/****************************************************************
+**
+** test_skiplist_init(): Test H5SL (skiplist) code.
+** Initialize data for skip list testing
+**
+****************************************************************/
+static void
+test_skiplist_init(void)
+{
+ time_t curr_time; /* Current time, for seeding random number generator */
+ int new_val; /* New value to insert */
+ unsigned found; /* Flag to indicate value was inserted already */
+ size_t u,v; /* Local index variables */
+
+ /* Initialize random number seed */
+ curr_time=time(NULL);
+ HDsrandom((unsigned long)curr_time);
+
+ /* Create randomized set of numbers */
+ for(u=0; u<NUM_ELEMS; u++) {
+ do {
+ /* Reset flag */
+ found=0;
+
+ /* Generate random numbers from -5000 to 5000 */
+ new_val=(int)(HDrandom()%10001)-5001;
+
+ /* Check if the value is already in the array */
+ for(v=0; v<u; v++)
+ if(rand_num[v]==new_val)
+ found=1;
+ } while(found);
+
+ /* Set unique value in array */
+ rand_num[u]=new_val;
+ } /* end for */
+
+ /* Copy random values to sorted array */
+ HDmemcpy(sort_rand_num,rand_num,sizeof(int)*NUM_ELEMS);
+
+ /* Sort random numbers */
+ HDqsort(sort_rand_num,NUM_ELEMS,sizeof(int),tst_sort);
+
+ /* Copy random values to reverse sorted array */
+ HDmemcpy(rev_sort_rand_num,rand_num,sizeof(int)*NUM_ELEMS);
+
+ /* Sort random numbers */
+ HDqsort(rev_sort_rand_num,NUM_ELEMS,sizeof(int),tst_rev_sort);
+} /* end test_tst_init() */
+
+/****************************************************************
+**
+** test_skiplist_create(): Test basic H5SL (skiplist) code.
+** Tests creating and closing skip lists.
+**
+****************************************************************/
+static void
+test_skiplist_create(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(6, ("Testing Creating & Closing Skip Lists\n"));
+
+ /* Try creating a skip list */
+ slist=H5SL_create(H5SL_TYPE_INT, 0.5,16);
+ CHECK(slist, NULL, "H5SL_create");
+
+ /* Try closing the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_create() */
+
+/****************************************************************
+**
+** test_skiplist_insert(): Test H5SL (skip list) code.
+** Tests inserting single object into skip list.
+**
+****************************************************************/
+static void
+test_skiplist_insert(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ int key, /* Key of item to insert */
+ item; /* Item to insert */
+ int search_key; /* Key of item to search for in skip list */
+ int *found_item; /* Item found in skip list */
+ ssize_t num; /* Number of elements in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Insertion Into Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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");
+
+ /* Try searching for item in empty skip list */
+ key=37;
+ found_item=H5SL_search(slist,&key);
+ VERIFY(found_item, NULL, "H5SL_search");
+
+ /* Insert an object into the skip list */
+ key=2; item=10;
+ ret=H5SL_insert(slist,&item,&key);
+ CHECK(ret, FAIL, "H5SL_insert");
+
+ /* Check that the skip list has one element */
+ num=H5SL_count(slist);
+ VERIFY(num, 1, "H5SL_count");
+
+ /* Search for the item just inserted */
+ found_item=H5SL_search(slist,&key);
+ CHECK(found_item, NULL, "H5SL_search");
+ VERIFY(*found_item,item,"H5SL_search");
+
+ /* Search for an item not in list */
+ search_key=37;
+ found_item=H5SL_search(slist,&search_key);
+ VERIFY(found_item, NULL, "H5SL_search");
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_insert() */
+
+/****************************************************************
+**
+** test_skiplist_insert_many(): Test H5SL (skip list) code.
+** Tests inserting many objects into skip list.
+**
+****************************************************************/
+static void
+test_skiplist_insert_many(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ ssize_t num; /* Number of elements in skip list */
+ size_t u; /* Local index variable */
+ int *found_item; /* Item found in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Insertion of Many Items Into Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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 many 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 */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "H5SL_count");
+
+ /* Search for all objects in the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ found_item=H5SL_search(slist,&rand_num[u]);
+ CHECK(found_item, NULL, "H5SL_search");
+ VERIFY(*found_item,rand_num[u],"H5SL_search");
+ } /* end for */
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_insert_many() */
+
+/****************************************************************
+**
+** test_skiplist_remove(): Test H5SL (skip list) code.
+** Tests basic object removal from skip list.
+**
+****************************************************************/
+static void
+test_skiplist_remove(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ int key1, /* Key of 1st item to insert */
+ key2, /* Key of 2nd item to insert */
+ key3; /* Key of 3rd item to insert */
+ int search_key; /* Key of item to search for in skip list */
+ int *found_item; /* Item found in skip list */
+ ssize_t num; /* Number of elements in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Removal From Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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");
+
+ /* Try removing an item in empty skip list */
+ search_key=37;
+ found_item=H5SL_remove(slist,&search_key);
+ VERIFY(found_item, NULL, "H5SL_remove");
+
+ /* Insert three objects into the skip list */
+ key1=15;
+ ret=H5SL_insert(slist,&key1,&key1);
+ CHECK(ret, FAIL, "H5SL_insert");
+
+ key2=10;
+ ret=H5SL_insert(slist,&key2,&key2);
+ CHECK(ret, FAIL, "H5SL_insert");
+
+ key3=20;
+ ret=H5SL_insert(slist,&key3,&key3);
+ CHECK(ret, FAIL, "H5SL_insert");
+
+ /* Check that the skip list has three elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 3, "H5SL_count");
+
+ /* Try removing items from skip list */
+ search_key=key1;
+ found_item=H5SL_remove(slist,&search_key);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(found_item, &key1, "H5SL_remove");
+
+ search_key=key2;
+ found_item=H5SL_remove(slist,&search_key);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(found_item, &key2, "H5SL_remove");
+
+ search_key=key3;
+ found_item=H5SL_remove(slist,&search_key);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(found_item, &key3, "H5SL_remove");
+
+ /* Check that the skip list has no elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 0, "H5SL_count");
+
+ /* Try removing items from empty skip list (after its been worked on) */
+ search_key=key1;
+ found_item=H5SL_remove(slist,&search_key);
+ VERIFY(found_item, NULL, "H5SL_remove");
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_remove() */
+
+/****************************************************************
+**
+** test_skiplist_remove_many(): Test H5SL (skip list) code.
+** Tests removing many objects from skip list.
+**
+****************************************************************/
+static void
+test_skiplist_remove_many(void)
+{
+ H5SL_t *slist; /* Skip list created */
+ ssize_t num; /* Number of elements in skip list */
+ size_t u; /* Local index variable */
+ int *found_item; /* Item found in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Removal of Many Items From Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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 many 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 */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "H5SL_count");
+
+ /* Remove all objects from the skip list (in random order) */
+ for(u=0; u<NUM_ELEMS; u++) {
+ found_item=H5SL_remove(slist,&rand_num[u]);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(*found_item,rand_num[u],"H5SL_remove");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ 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 many 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 */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "H5SL_count");
+
+ /* Remove all objects from the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ found_item=H5SL_remove(slist,&sort_rand_num[u]);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(*found_item,sort_rand_num[u],"H5SL_remove");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ 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 many 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 */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "H5SL_count");
+
+ /* Remove all objects from the skip list */
+ for(u=0; u<NUM_ELEMS; u++) {
+ found_item=H5SL_remove(slist,&rev_sort_rand_num[u]);
+ CHECK(found_item, NULL, "H5SL_remove");
+ VERIFY(*found_item,rev_sort_rand_num[u],"H5SL_remove");
+ } /* end for */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, 0, "H5SL_count");
+
+ /* Close the skip list */
+ ret=H5SL_close(slist);
+ CHECK(ret, FAIL, "H5SL_close");
+
+} /* end test_skiplist_remove_many() */
+
+/****************************************************************
+**
+** test_skiplist_iterate(): Test H5SL (skip list) code.
+** Tests iterating over nodes in skip list.
+**
+****************************************************************/
+static void
+test_skiplist_iterate(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 */
+ int *found_item; /* Item found in skip list */
+ herr_t ret; /* Generic return value */
+
+ /* Output message about test being performed */
+ MESSAGE(7, ("Testing Iterating Over Skip List\n"));
+
+ /* Create a Heap */
+ slist=H5SL_create(H5SL_TYPE_INT, 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 many 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 */
+
+ /* Check that the skip list has correct # of elements */
+ num=H5SL_count(slist);
+ VERIFY(num, NUM_ELEMS, "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,sort_rand_num[u],"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_iterate() */
+
+/****************************************************************
+**
+** test_skiplist(): Main H5SL testing routine.
+**
+****************************************************************/
+void
+test_skiplist(void)
+{
+ /* Output message about test being performed */
+ MESSAGE(5, ("Testing Skip Lists\n"));
+
+ /* Initialize skip list testing data */
+ test_skiplist_init();
+
+ /* Actual skip list tests */
+ test_skiplist_create(); /* Test skip list creation */
+ test_skiplist_insert(); /* Test basic skip list insertion */
+ test_skiplist_insert_many(); /* Test insertion of many items into skip list */
+ 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 */
+
+} /* end test_skiplist() */
+
+