diff options
Diffstat (limited to 'tests/libutil')
| -rw-r--r-- | tests/libutil/Makemodule.am | 16 | ||||
| -rw-r--r-- | tests/libutil/rbtree.c | 173 | ||||
| -rw-r--r-- | tests/libutil/str_table.c | 84 | ||||
| -rw-r--r-- | tests/libutil/words.txt | 1000 | ||||
| -rw-r--r-- | tests/libutil/xxhash.c | 65 |
5 files changed, 1338 insertions, 0 deletions
diff --git a/tests/libutil/Makemodule.am b/tests/libutil/Makemodule.am new file mode 100644 index 0000000..1153db4 --- /dev/null +++ b/tests/libutil/Makemodule.am @@ -0,0 +1,16 @@ +test_str_table_SOURCES = tests/libutil/str_table.c tests/test.h +test_str_table_LDADD = libutil.a libfstream.a libcompat.a +test_str_table_CPPFLAGS = $(AM_CPPFLAGS) -DTESTPATH=$(top_srcdir)/tests/libutil + +test_rbtree_SOURCES = tests/libutil/rbtree.c tests/test.h +test_rbtree_LDADD = libutil.a libcompat.a + +test_xxhash_SOURCES = tests/libutil/xxhash.c +test_xxhash_LDADD = libutil.a libcompat.a + +LIBUTIL_TESTS = \ + test_str_table test_rbtree test_xxhash + +check_PROGRAMS += $(LIBUTIL_TESTS) +TESTS += $(LIBUTIL_TESTS) +EXTRA_DIST += $(top_srcdir)/tests/libutil/words.txt diff --git a/tests/libutil/rbtree.c b/tests/libutil/rbtree.c new file mode 100644 index 0000000..173df1c --- /dev/null +++ b/tests/libutil/rbtree.c @@ -0,0 +1,173 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * rbtree.c + * + * Copyright (C) 2020 David Oberhollenzer <goliath@infraroot.at> + */ +#include "config.h" + +#include "rbtree.h" +#include "../test.h" + +static int key_compare(const void *a, const void *b) +{ + return *((sqfs_s32 *)a) - *((sqfs_s32 *)b); +} + +static size_t count_nodes_dfs(rbtree_node_t *n) +{ + return 1 + (n->left == NULL ? 0 : count_nodes_dfs(n->left)) + + (n->right == NULL ? 0 : count_nodes_dfs(n->right)); +} + +static size_t min_depth(rbtree_node_t *n) +{ + size_t lhs, rhs; + + if (n == NULL) + return 0; + + lhs = min_depth(n->left) + 1; + rhs = min_depth(n->right) + 1; + + return lhs < rhs ? lhs : rhs; +} + +static size_t max_depth(rbtree_node_t *n) +{ + size_t lhs, rhs; + + if (n == NULL) + return 0; + + lhs = min_depth(n->left) + 1; + rhs = min_depth(n->right) + 1; + + return lhs > rhs ? lhs : rhs; +} + +static size_t get_ref_black_depth(rbtree_t *rb) +{ + rbtree_node_t *n; + size_t count = 0; + + for (n = rb->root; n != NULL; n = n->left) { + if (!n->is_red) + count += 1; + } + + return count; +} + +static void check_binary_tree_dfs(rbtree_node_t *n) +{ + const void *key = rbtree_node_key(n); + const void *cmp; + + if (n->left != NULL) { + cmp = rbtree_node_key(n->left); + TEST_ASSERT(key_compare(cmp, key) < 0); + + check_binary_tree_dfs(n->left); + } + + if (n->right != NULL) { + cmp = rbtree_node_key(n->right); + TEST_ASSERT(key_compare(cmp, key) > 0); + + check_binary_tree_dfs(n->right); + } +} + +static void check_colors_dfs(rbtree_node_t *n) +{ + if (n->is_red) { + TEST_ASSERT(n->left == NULL || !n->left->is_red); + TEST_ASSERT(n->right == NULL || !n->right->is_red); + } + + if (n->left != NULL) + check_colors_dfs(n->left); + + if (n->right != NULL) + check_colors_dfs(n->right); +} + +static void check_black_depth_dfs(rbtree_node_t *n, size_t ref, + size_t counter) +{ + if (!n->is_red) + counter += 1; + + if (n->left == NULL || n->right == NULL) + TEST_EQUAL_UI(counter, ref); + + if (n->left != NULL) + check_black_depth_dfs(n->left, ref, counter); + + if (n->right != NULL) + check_black_depth_dfs(n->right, ref, counter); +} + +int main(void) +{ + size_t count, blkdepth, mind, maxd; + sqfs_s32 key, key2; + rbtree_node_t *n; + sqfs_u64 value; + rbtree_t rb; + + TEST_ASSERT(rbtree_init(&rb, sizeof(sqfs_s32), + sizeof(sqfs_u64), key_compare) == 0); + + count = 0; + + for (key = -1000; key < 1000; ++key) { + /* lookup of current key must fail prior to insert */ + TEST_NULL(rbtree_lookup(&rb, &key)); + + /* previous key/value pairs must still be there */ + for (key2 = -1000; key2 < key; ++key2) { + n = rbtree_lookup(&rb, &key2); + TEST_NOT_NULL(n); + value = *((sqfs_u64 *)rbtree_node_value(n)); + TEST_EQUAL_UI((sqfs_u64)(key2 + 10000), value); + } + + /* insert key value pair */ + value = key + 10000; + TEST_ASSERT(rbtree_insert(&rb, &key, &value) == 0); + count += 1; + + /* check if the tree has the right number of nodes */ + TEST_EQUAL_UI(count_nodes_dfs(rb.root), count); + + /* check if it is still a binary tree */ + check_binary_tree_dfs(rb.root); + + /* root node must be black. Every red node + must have black children. */ + TEST_ASSERT(!rb.root->is_red); + check_colors_dfs(rb.root); + + /* every path from the root to a leave must have + the same number of black nodes. */ + blkdepth = get_ref_black_depth(&rb); + check_black_depth_dfs(rb.root, blkdepth, 0); + + /* longest root to leaf path must be at most + twice as long as the shortest. */ + mind = min_depth(rb.root); + maxd = max_depth(rb.root); + TEST_ASSERT(maxd <= mind * 2); + + /* lookup of current key must work after insert */ + n = rbtree_lookup(&rb, &key); + TEST_NOT_NULL(n); + value = *((sqfs_u64 *)rbtree_node_value(n)); + TEST_EQUAL_UI((sqfs_u64)(key + 10000), value); + } + + rbtree_cleanup(&rb); + return EXIT_SUCCESS; +} diff --git a/tests/libutil/str_table.c b/tests/libutil/str_table.c new file mode 100644 index 0000000..83526af --- /dev/null +++ b/tests/libutil/str_table.c @@ -0,0 +1,84 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * str_table.c + * + * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at> + */ +#include "config.h" + +#include "str_table.h" +#include "fstream.h" +#include "compat.h" +#include "../test.h" + +static char *strings[1000]; + +static int read_strings(void) +{ + istream_t *fp; + ssize_t ret; + char *line; + int i; + + fp = istream_open_file("words.txt"); + TEST_NOT_NULL(fp); + + for (i = 0; i < 1000; ++i) { + ret = istream_get_line(fp, &line, NULL, 0); + TEST_EQUAL_I(ret, 0); + + strings[i] = line; + } + + sqfs_destroy(fp); + return 0; +} + +int main(void) +{ + str_table_t table; + size_t i, j, idx; + const char *str; + + TEST_ASSERT(chdir(TEST_PATH) == 0); + + if (read_strings()) + return EXIT_FAILURE; + + TEST_ASSERT(str_table_init(&table, 64) == 0); + + for (i = 0; i < 1000; ++i) { + TEST_ASSERT(str_table_get_index(&table, strings[i], &idx) == 0); + + TEST_EQUAL_UI(idx, i); + + for (j = 0; j <= i; ++j) { + str = str_table_get_string(&table, j); + + TEST_NOT_NULL(str); + TEST_ASSERT(str != strings[i]); + TEST_STR_EQUAL(str, strings[j]); + } + + for (; j < 1000; ++j) + TEST_NULL(str_table_get_string(&table, j)); + } + + for (i = 0; i < 1000; ++i) { + TEST_ASSERT(str_table_get_index(&table, strings[i], &idx) == 0); + TEST_EQUAL_UI(idx, i); + + str = str_table_get_string(&table, i); + + TEST_NOT_NULL(str); + TEST_ASSERT(str != strings[i]); + TEST_STR_EQUAL(str, strings[i]); + } + + str_table_cleanup(&table); + + for (i = 0; i < 1000; ++i) + free(strings[i]); + + return EXIT_SUCCESS; +} diff --git a/tests/libutil/words.txt b/tests/libutil/words.txt new file mode 100644 index 0000000..9496e14 --- /dev/null +++ b/tests/libutil/words.txt @@ -0,0 +1,1000 @@ +a +ability +able +about +above +accept +according +account +across +act +action +activity +actually +add +address +administration +admit +adult +affect +after +again +against +age +agency +agent +ago +agree +agreement +ahead +air +all +allow +almost +alone +along +already +also +although +always +American +among +amount +analysis +and +animal +another +answer +any +anyone +anything +appear +apply +approach +area +argue +arm +around +arrive +art +article +artist +as +ask +assume +at +attack +attention +attorney +audience +author +authority +available +avoid +away +baby +back +bad +bag +ball +bank +bar +base +be +beat +beautiful +because +become +bed +before +begin +behavior +behind +believe +benefit +best +better +between +beyond +big +bill +billion +bit +black +blood +blue +board +body +book +born +both +box +boy +break +bring +brother +budget +build +building +business +but +buy +by +call +camera +campaign +can +cancer +candidate +capital +car +card +care +career +carry +case +catch +cause +cell +center +central +century +certain +certainly +chair +challenge +chance +change +character +charge +check +child +choice +choose +church +citizen +city +civil +claim +class +clear +clearly +close +coach +cold +collection +college +color +come +commercial +common +community +company +compare +computer +concern +condition +conference +Congress +consider +consumer +contain +continue +control +cost +could +country +couple +course +court +cover +create +crime +cultural +culture +cup +current +customer +cut +dark +data +daughter +day +dead +deal +death +debate +decade +decide +decision +deep +defense +degree +Democrat +democratic +describe +design +despite +detail +determine +develop +development +die +difference +different +difficult +dinner +direction +director +discover +discuss +discussion +disease +do +doctor +dog +door +down +draw +dream +drive +drop +drug +during +each +early +east +easy +eat +economic +economy +edge +education +effect +effort +eight +either +election +else +employee +end +energy +enjoy +enough +enter +entire +environment +environmental +especially +establish +even +evening +event +ever +every +everybody +everyone +everything +evidence +exactly +example +executive +exist +expect +experience +expert +explain +eye +face +fact +factor +fail +fall +family +far +fast +father +fear +federal +feel +feeling +few +field +fight +figure +fill +film +final +finally +financial +find +fine +finger +finish +fire +firm +first +fish +five +floor +fly +focus +follow +food +foot +for +force +foreign +forget +form +former +forward +four +free +friend +from +front +full +fund +future +game +garden +gas +general +generation +get +girl +give +glass +go +goal +good +government +great +green +ground +group +grow +growth +guess +gun +guy +hair +half +hand +hang +happen +happy +hard +have +he +head +health +hear +heart +heat +heavy +help +her +here +herself +high +him +himself +his +history +hit +hold +home +hope +hospital +hot +hotel +hour +house +how +however +huge +human +hundred +husband +I +idea +identify +if +image +imagine +impact +important +improve +in +include +including +increase +indeed +indicate +individual +industry +information +inside +instead +institution +interest +interesting +international +interview +into +investment +involve +issue +it +item +its +itself +job +join +just +keep +key +kid +kill +kind +kitchen +know +knowledge +land +language +large +last +late +later +laugh +law +lawyer +lay +lead +leader +learn +least +leave +left +leg +legal +less +let +letter +level +lie +life +light +like +likely +line +list +listen +little +live +local +long +look +lose +loss +lot +love +low +machine +magazine +main +maintain +major +majority +make +man +manage +management +manager +many +market +marriage +material +matter +may +maybe +me +mean +measure +media +medical +meet +meeting +member +memory +mention +message +method +middle +might +military +million +mind +minute +miss +mission +model +modern +moment +money +month +more +morning +most +mother +mouth +move +movement +movie +Mr +Mrs +much +music +must +my +myself +name +nation +national +natural +nature +near +nearly +necessary +need +network +never +new +news +newspaper +next +nice +night +no +none +nor +north +not +note +nothing +notice +now +n't +number +occur +of +off +offer +office +officer +official +often +oh +oil +ok +old +on +once +one +only +onto +open +operation +opportunity +option +or +order +organization +other +others +our +out +outside +over +own +owner +page +pain +painting +paper +parent +part +participant +particular +particularly +partner +party +pass +past +patient +pattern +pay +peace +people +per +perform +performance +perhaps +period +person +personal +phone +physical +pick +picture +piece +place +plan +plant +play +player +PM +point +police +policy +political +politics +poor +popular +population +position +positive +possible +power +practice +prepare +present +president +pressure +pretty +prevent +price +private +probably +problem +process +produce +product +production +professional +professor +program +project +property +protect +prove +provide +public +pull +purpose +push +put +quality +question +quickly +quite +race +radio +raise +range +rate +rather +reach +read +ready +real +reality +realize +really +reason +receive +recent +recently +recognize +record +red +reduce +reflect +region +relate +relationship +religious +remain +remember +remove +report +represent +Republican +require +research +resource +respond +response +responsibility +rest +result +return +reveal +rich +right +rise +risk +road +rock +role +room +rule +run +safe +same +save +say +scene +school +science +scientist +score +sea +season +seat +second +section +security +see +seek +seem +sell +send +senior +sense +series +serious +serve +service +set +seven +several +sex +sexual +shake +share +she +shoot +short +shot +should +shoulder +show +side +sign +significant +similar +simple +simply +since +sing +single +sister +sit +site +situation +six +size +skill +skin +small +smile +so +social +society +soldier +some +somebody +someone +something +sometimes +son +song +soon +sort +sound +source +south +southern +space +speak +special +specific +speech +spend +sport +spring +staff +stage +stand +standard +star +start +state +statement +station +stay +step +still +stock +stop +store +story +strategy +street +strong +structure +student +study +stuff +style +subject +success +successful +such +suddenly +suffer +suggest +summer +support +sure +surface +system +table +take +talk +task +tax +teach +teacher +team +technology +television +tell +ten +tend +term +test +than +thank +that +the +their +them +themselves +then +theory +there +these +they +thing +think +third +this +those +though +thought +thousand +threat +three +through +throughout +throw +thus +time +to +today +together +tonight +too +top +total +tough +toward +town +trade +traditional +training +travel +treat +treatment +tree +trial +trip +trouble +true +truth +try +turn +TV +two +type +under +understand +unit +until +up +upon +us +use +usually +value +various +very +victim +view +violence +visit +voice +vote +wait +walk +wall +want +war +watch +water +way +we +weapon +wear +week +weight +well +west +western +what +whatever +when +where +whether +which +while +white +who +whole +whom +whose +why +wide +wife +will +win +wind +window +wish +with +within +without +woman +wonder +word +work +worker +world +worry +would +write +writer +wrong +yard +yeah +year +yes +yet +you +young +your +yourself diff --git a/tests/libutil/xxhash.c b/tests/libutil/xxhash.c new file mode 100644 index 0000000..6e17097 --- /dev/null +++ b/tests/libutil/xxhash.c @@ -0,0 +1,65 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * xxhash.c + * + * Copyright (C) 2020 David Oberhollenzer <goliath@infraroot.at> + */ +#include "config.h" + +#include "util.h" +#include "../test.h" + +static const struct { + const char *plaintext; + size_t psize; + sqfs_u32 digest; +} test_vectors[] = { + { + .plaintext = "\x9e", + .psize = 1, + .digest = 0xB85CBEE5, + }, + { + .plaintext = "\x9e\xff\x1f\x4b\x5e\x53\x2f\xdd" + "\xb5\x54\x4d\x2a\x95\x2b", + .psize = 14, + .digest = 0xE5AA0AB4, + }, + { + .plaintext = "\x9e\xff\x1f\x4b\x5e\x53\x2f\xdd" + "\xb5\x54\x4d\x2a\x95\x2b\x57\xae" + "\x5d\xba\x74\xe9\xd3\xa6\x4c\x98" + "\x30\x60\xc0\x80\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00", + .psize = 101, + .digest = 0x018F52BC, + }, +}; + +int main(void) +{ + sqfs_u32 hash; + size_t i; + + for (i = 0; i < sizeof(test_vectors) / sizeof(test_vectors[0]); ++i) { + hash = xxh32(test_vectors[i].plaintext, test_vectors[i].psize); + + if (hash != test_vectors[i].digest) { + fprintf(stderr, "Test case " PRI_SZ " failed!\n", i); + fprintf(stderr, "Expected result: 0x%08X\n", + test_vectors[i].digest); + fprintf(stderr, "Actual result: 0x%08X\n", hash); + return EXIT_FAILURE; + } + } + + return EXIT_SUCCESS; +} |