diff options
Diffstat (limited to 'test')
| -rw-r--r-- | test/Makefile.in | 13 | ||||
| -rw-r--r-- | test/testhdf5.c | 1 | ||||
| -rw-r--r-- | test/testhdf5.h | 1 | ||||
| -rw-r--r-- | test/tskiplist.c | 497 |
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() */ + + |