diff options
Diffstat (limited to 'test/ttst.c')
| -rw-r--r-- | test/ttst.c | 400 |
1 files changed, 400 insertions, 0 deletions
diff --git a/test/ttst.c b/test/ttst.c new file mode 100644 index 0000000..eb9ebef --- /dev/null +++ b/test/ttst.c @@ -0,0 +1,400 @@ +/**************************************************************************** + * NCSA HDF * + * Software Development Group * + * National Center for Supercomputing Applications * + * University of Illinois at Urbana-Champaign * + * 605 E. Springfield, Champaign IL 61820 * + * * + * For conditions of distribution and use, see the accompanying * + * hdf/COPYING file. * + * * + ****************************************************************************/ + +/* $Id$ */ + +/* + FILE + tst.c + Test HDF Ternary Search Tree (tst) routines. + + REMARKS + + DESIGN + + BUGS/LIMITATIONS + + EXPORTED ROUTINES + + AUTHOR + Quincey Koziol + + MODIFICATION HISTORY + 12/9/02 - Started coding + */ + +#include <time.h> + +#include "testhdf5.h" +#include "H5STprivate.h" + +/* Test words to insert into s TST */ +static const char *words[]={ + "We", "hold", "these", "truths", "to", "be", "self-evident,", "that", + "all", "men", "are", "created", "equal,", "that", "they", "are", "endowed", + "by", "their", "Creator", "with", "certain", "unalienable", "Rights,", + "that", "among", "these", "are", "Life,", "Liberty", "and", "the", + "pursuit", "of", "Happiness." +}; +/* Number of words in test words set */ +size_t num_words; + +/* Number of unique words in test word set */ +size_t num_uniq_words; +/* Unique words in test word set */ +char **uniq_words; +/* Randomized order version of words in test word set */ +char **rand_uniq_words; +/* Sorted order version of words in test word set */ +char **sort_uniq_words; + +static int tst_strcmp(const void *_s1, const void *_s2) +{ + return(HDstrcmp(*(const char **)_s1,*(const char **)_s2)); +} + +/**************************************************************** +** +** test_tst_init(): Test basic H5ST (ternary search tree) selection code. +** Initialize data for TST testing +** +****************************************************************/ +static void +test_tst_init(void) +{ + time_t curr_time; /* Current time, for seeding random number generator */ + char *tmp_word=NULL;/* Temporary pointer to word in word set */ + size_t u,v,w; /* Local index variables */ + + /* Compute the number of words in the test set */ + num_words=sizeof(words)/sizeof(words[0]); + + /* Determine the number of unique words in test set */ + /* (Not particularly efficient, be careful if many words are added to set) */ + num_uniq_words=0; + for(u=0; u<num_words; u++) { + /* Assume word is unique */ + num_uniq_words++; + for(v=0; v<u; v++) + /* If word is already found in words looked at, decrement unique count */ + if(!HDstrcmp(words[u],words[v])) { + num_uniq_words--; + break; + } /* end if */ + } /* end for */ + + /* Allocate space for the array of unique words */ + uniq_words=HDmalloc(sizeof(char *)*num_uniq_words); + + /* Allocate space for the array of randomized order unique words also */ + rand_uniq_words=HDmalloc(sizeof(char *)*num_uniq_words); + + /* Allocate space for the array of sorted order unique words also */ + sort_uniq_words=HDmalloc(sizeof(char *)*num_uniq_words); + + /* Insert unique words from test set into unique word set */ + w=0; + for(u=0; u<num_words; u++) { + /* Assume word is unique */ + tmp_word=(char *)words[u]; + for(v=0; v<u; v++) + /* If word is already found in words looked at, decrement unique count */ + if(!HDstrcmp(words[u],words[v])) { + tmp_word=NULL; + break; + } /* end if */ + + /* Check if word was actually unique */ + if(tmp_word!=NULL) + uniq_words[w++]=tmp_word; + } /* end for */ + + /* Create randomized set of unique words */ + for(u=0; u<num_uniq_words; u++) + rand_uniq_words[u]=uniq_words[u]; + curr_time=time(NULL); + srandom((unsigned long)curr_time); + for(u=0; u<num_uniq_words; u++) { + v=u+(random()%(num_uniq_words-u)); + if(u!=v) { + tmp_word=rand_uniq_words[u]; + rand_uniq_words[u]=rand_uniq_words[v]; + rand_uniq_words[v]=tmp_word; + } /* end if */ + } /* end for */ + + /* Create sorted set of unique words */ + for(u=0; u<num_uniq_words; u++) + sort_uniq_words[u]=uniq_words[u]; + HDqsort(sort_uniq_words,num_uniq_words,sizeof(char *),tst_strcmp); +} /* end test_tst_init() */ + +/**************************************************************** +** +** test_tst_create(): Test basic H5ST (ternary search tree) selection code. +** Tests creating and closing TSTs. +** +****************************************************************/ +static void +test_tst_create(void) +{ + H5ST_tree_t *tree; /* TST created */ + herr_t ret; /* Generic return value */ + + /* Output message about test being performed */ + MESSAGE(5, ("Testing Creating & Closing TSTs\n")); + + /* Try closing a NULL tree */ + tree=NULL; + ret=H5ST_close(tree); + VERIFY(ret, FAIL, "H5ST_close"); + + /* Try creating a TST */ + tree=H5ST_create(); + CHECK(tree, NULL, "H5ST_create"); + + /* Try closing a real tree */ + ret=H5ST_close(tree); + CHECK(ret, FAIL, "H5ST_close"); + +} /* end test_tst_create() */ + +/**************************************************************** +** +** test_tst_insert(): Test basic H5ST (ternary search tree) selection code. +** Tests inserting key/value pairs into TST +** +****************************************************************/ +static void +test_tst_insert(void) +{ + H5ST_tree_t *tree; /* TST created */ + H5ST_ptr_t found; /* Pointer to TST node found */ + void *obj; /* Pointer to object located in TST */ + size_t u; /* Local index counter */ + htri_t check; /* Is string in TST? */ + herr_t ret; /* Generic return value */ + + /* Output message about test being performed */ + MESSAGE(5, ("Testing Inserting Values into TSTs\n")); + + /* Create the TST */ + tree=H5ST_create(); + CHECK(tree, NULL, "H5ST_create"); + + /* Insert unique words into TST, in random order */ + for(u=0; u<num_uniq_words; u++) { + ret=H5ST_insert(tree,rand_uniq_words[u],rand_uniq_words[u]); + CHECK(ret, FAIL, "H5ST_insert"); + } /* end for */ + + /* Verify that all words were inserted into TST properly */ + for(u=0; u<num_uniq_words; u++) { + /* Check that the word is present */ + check=H5ST_search(tree,uniq_words[u]); + VERIFY(check, TRUE, "H5ST_search"); + + /* Check that the value "payloads" are correct */ + found=H5ST_find(tree,uniq_words[u]); + CHECK(found, NULL, "H5ST_find"); + + if(HDstrcmp((const char *)found->eqkid,uniq_words[u])) { + num_errs++; + printf("%d: TST node values don't match!, found->eqkid=%s, uniq_words[%u]=%s\n",__LINE__,(char *)found->eqkid,(unsigned)u,uniq_words[u]); + } /* end if */ + + obj=H5ST_locate(tree,uniq_words[u]); + CHECK(obj, NULL, "H5ST_locate"); + + if(HDstrcmp((const char *)obj,uniq_words[u])) { + num_errs++; + printf("%d: TST objects don't match!, obj=%s, uniq_words[%u]=%s\n",__LINE__,(char *)obj,(unsigned)u,uniq_words[u]); + } /* end if */ + } /* end for */ + + /* Verify that words not in the TST aren't found */ + check=H5ST_search(tree,"foo"); + VERIFY(check, FALSE, "H5ST_search"); + check=H5ST_search(tree,"bar"); + VERIFY(check, FALSE, "H5ST_search"); + check=H5ST_search(tree,"baz"); + VERIFY(check, FALSE, "H5ST_search"); + + /* Close the TST */ + ret=H5ST_close(tree); + CHECK(ret, FAIL, "H5ST_close"); +} /* end test_tst_insert() */ + +/**************************************************************** +** +** test_tst_iterate(): Test basic H5ST (ternary search tree) code. +** Tests iterating through key/value pairs in TST +** +****************************************************************/ +static void +test_tst_iterate(void) +{ + H5ST_tree_t *tree; /* TST created */ + H5ST_ptr_t found; /* Pointer to TST node found */ + size_t u; /* Local index counter */ + herr_t ret; /* Generic return value */ + + /* Output message about test being performed */ + MESSAGE(5, ("Testing Iterating Over TSTs\n")); + + /* Create the TST */ + tree=H5ST_create(); + CHECK(tree, NULL, "H5ST_create"); + + /* Insert unique words into TST, in random order */ + for(u=0; u<num_uniq_words; u++) { + ret=H5ST_insert(tree,rand_uniq_words[u],rand_uniq_words[u]); + CHECK(ret, FAIL, "H5ST_insert"); + } /* end for */ + + /* Use findfirst/findnext calls to iterate through TST */ + found=H5ST_findfirst(tree); + CHECK(found, NULL, "H5ST_findfirst"); + u=0; + do { + /* Check that the strings in the TST are in the correct order */ + if(HDstrcmp((const char *)found->eqkid,sort_uniq_words[u])) { + num_errs++; + printf("%d: TST node values don't match!, found->eqkid=%s, sort_uniq_words[%u]=%s\n",__LINE__,(char *)found->eqkid,(unsigned)u,sort_uniq_words[u]); + } /* end if */ + + /* Advance to next string in TST */ + found=H5ST_findnext(found); + u++; + } while(found!=NULL); + + /* Close the TST */ + ret=H5ST_close(tree); + CHECK(ret, FAIL, "H5ST_close"); +} /* end test_tst_iterate() */ + +/**************************************************************** +** +** test_tst_remove(): Test basic H5ST (ternary search tree) code. +** Tests removing key/value pairs by string value in TST +** +****************************************************************/ +static void +test_tst_remove(void) +{ + H5ST_tree_t *tree; /* TST created */ + H5ST_ptr_t found; /* Pointer to TST node found */ + void *obj; /* Pointer to object removed from TST */ + htri_t check; /* Is string in TST? */ + size_t u; /* Local index counter */ + herr_t ret; /* Generic return value */ + + /* Output message about test being performed */ + MESSAGE(5, ("Testing Removing String Values from TSTs\n")); + + /* Create the TST */ + tree=H5ST_create(); + CHECK(tree, NULL, "H5ST_create"); + + /* Insert unique words into TST, in random order */ + for(u=0; u<num_uniq_words; u++) { + ret=H5ST_insert(tree,rand_uniq_words[u],rand_uniq_words[u]); + CHECK(ret, FAIL, "H5ST_insert"); + } /* end for */ + + /* Remove strings from TST in random order */ + for(u=0; u<num_uniq_words; u++) { + obj=H5ST_remove(tree,rand_uniq_words[u]); + CHECK(obj, NULL, "H5ST_remove"); + + /* Check that the correct string was removed from TST */ + if(HDstrcmp((const char *)obj,rand_uniq_words[u])) { + num_errs++; + printf("%d: TST node values don't match!, obj=%s, rand_uniq_words[%u]=%s\n",__LINE__,(char *)obj,(unsigned)u,rand_uniq_words[u]); + } /* end if */ + + /* Check that the string can't be found in the TST any longer */ + check=H5ST_search(tree,rand_uniq_words[u]); + VERIFY(check, FALSE, "H5ST_search"); + } /* end for */ + + /* Re-insert unique words into TST, in random order */ + for(u=0; u<num_uniq_words; u++) { + ret=H5ST_insert(tree,rand_uniq_words[u],rand_uniq_words[u]); + CHECK(ret, FAIL, "H5ST_insert"); + } /* end for */ + + /* Remove TST nodes from TST in random order */ + for(u=0; u<num_uniq_words; u++) { + /* Get the pointer to the node to delete */ + found=H5ST_find(tree,rand_uniq_words[u]); + CHECK(found, NULL, "H5ST_find"); + + /* Check that the correct object will be removed from TST */ + if(HDstrcmp((const char *)found->eqkid,rand_uniq_words[u])) { + num_errs++; + printf("%d: TST node values don't match!, found->eqkid=%s, rand_uniq_words[%u]=%s\n",__LINE__,(char *)found->eqkid,(unsigned)u,rand_uniq_words[u]); + } /* end if */ + + /* Remove the node */ + ret=H5ST_delete(tree,found); + CHECK(ret, FAIL, "H5ST_delete"); + + /* Check that the string can't be found in the TST any longer */ + check=H5ST_search(tree,rand_uniq_words[u]); + VERIFY(check, FALSE, "H5ST_search"); + } /* end for */ + + /* Close the TST */ + ret=H5ST_close(tree); + CHECK(ret, FAIL, "H5ST_close"); +} /* end test_tst_remove() */ + +/**************************************************************** +** +** test_tst_finalize(): Test basic H5ST (ternary search tree) selection code. +** Wrap up data for TST testing +** +****************************************************************/ +static void +test_tst_finalize(void) +{ + /* Release memory for unordered, randomized and sorted order unique words */ + HDfree(uniq_words); + HDfree(rand_uniq_words); + HDfree(sort_uniq_words); +} /* end test_tst_finalize() */ + +/**************************************************************** +** +** test_tst(): Main H5ST selection testing routine. +** +****************************************************************/ +void +test_tst(void) +{ + /* Output message about test being performed */ + MESSAGE(5, ("Testing Ternary Search Trees\n")); + + /* Initialize TST testing data */ + test_tst_init(); + + /* Actual TST tests */ + test_tst_create(); /* Test TST creation */ + test_tst_insert(); /* Test TST insertion */ + test_tst_iterate(); /* Test TST iteration */ + test_tst_remove(); /* Test TST deletion */ + + /* Finalize TST testing data */ + test_tst_finalize(); +} /* end test_tst() */ + |