Cleanup: add some structure to the test directory

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

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;
+}