summaryrefslogtreecommitdiff
path: root/triehash/tests
diff options
context:
space:
mode:
Diffstat (limited to 'triehash/tests')
-rw-r--r--triehash/tests/framework.sh84
-rwxr-xr-xtriehash/tests/run-tests.sh22
-rwxr-xr-xtriehash/tests/test-basic245
-rwxr-xr-xtriehash/tests/test-case-insensitive109
-rwxr-xr-xtriehash/tests/test-enum-include-name-flags129
-rwxr-xr-xtriehash/tests/test-multi-byte-level427
6 files changed, 1016 insertions, 0 deletions
diff --git a/triehash/tests/framework.sh b/triehash/tests/framework.sh
new file mode 100644
index 000000000..51d4580a6
--- /dev/null
+++ b/triehash/tests/framework.sh
@@ -0,0 +1,84 @@
+#!/bin/sh
+# Simple integration test framework
+
+set -e
+
+
+cleanup() {
+ rm -f test.output test.c test.h test.tree
+}
+
+dumpone() {
+ if [ -e "$@" ]; then
+ echo "Content of $@:"
+ cat "$@" | sed "s#^#\t#g"
+ fi
+
+}
+
+dump() {
+ dumpone test.output
+ dumpone test.c
+ dumpone test.h
+ dumpone test.tree
+ return 1
+}
+
+testsuccess() {
+ [ "$INNER" ] || cleanup
+ [ "$INNER" ] || echo "Testing success of $@"
+ if ! "$@" > test.output 2>&1; then
+ echo "ERROR: Running $@ failed with error $?, messages were:" >&2
+ dump
+ return 1
+ fi
+}
+
+testfailure() {
+ [ "$INNER" ] || cleanup
+ [ "$INNER" ] || echo "Testing failure of $@"
+ if "$@" > test.output 2>&1; then
+ echo "ERROR: Running $@ unexpectedly succeeded, messages were:" >&2
+ dump
+ return 1
+ fi
+}
+
+testfileequal() {
+ [ "$INNER" ] || echo "Testing output of $2"
+ printf "%b\n" "$1" > expected
+ if ! diff -u "expected" "$2" > test.diff; then
+ echo "ERROR: Differences between expected output and and $2:" >&2
+ cat test.diff | sed "s#^#\t#g"
+ dump
+ return 1
+ fi
+}
+
+testgrep() {
+ [ "$INNER" ] || echo "Testing grep $@"
+ INNER=1 testsuccess grep "$@"
+ unset INNER
+}
+
+testsuccessequal() {
+ expect="$1"
+ shift
+ cleanup
+ echo "Testing success and output of $@"
+ INNER=1 testsuccess "$@"
+ INNER=1 testfileequal "$expect" test.output
+ unset INNER
+}
+
+
+WORDS="Word-_0
+Word = 42
+VeryLongWord
+Label ~ Word2
+= -9"
+
+triehash() {
+ printf "%b\n" "$WORDS" | perl -MDevel::Cover=-summary,0,-silent,1 $(dirname $(dirname $(readlink -f $0)))/triehash.pl "$@" || return $?
+ return $?
+}
diff --git a/triehash/tests/run-tests.sh b/triehash/tests/run-tests.sh
new file mode 100755
index 000000000..b9c1ec309
--- /dev/null
+++ b/triehash/tests/run-tests.sh
@@ -0,0 +1,22 @@
+#!/bin/sh
+DIR=$(dirname $(readlink -f $0))
+
+# Let's go into triehash.pl's dir
+cd $(dirname "$DIR")
+
+rm -rf cover_db
+
+count=$(cd "$DIR" && echo test-* | wc -w)
+i=1
+
+for test in $DIR/test-*; do
+ echo "[$i/$count] Running testcase $test"
+ if ! $test > test.summary 2>&1; then
+ cat test.summary
+ exit 1
+ fi
+ i=$((i + 1))
+done
+
+
+cover
diff --git a/triehash/tests/test-basic b/triehash/tests/test-basic
new file mode 100755
index 000000000..19cb08684
--- /dev/null
+++ b/triehash/tests/test-basic
@@ -0,0 +1,245 @@
+#!/bin/sh
+. $(dirname $(readlink -f $0))/framework.sh
+
+# Check for non-existing files
+testfailure triehash -C /does/not/exist1 -H /does/not/exist1 /does/not/exist/input
+
+# Check that we can specify - for -C and -H
+testsuccessequal "#ifndef TRIE_HASH_PerfectHash
+#define TRIE_HASH_PerfectHash
+#include <stddef.h>
+#include <stdint.h>
+enum PerfectKey {
+ Unknown = -1,
+};
+static enum PerfectKey PerfectHash(const char *string, size_t length);
+static enum PerfectKey PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ default:
+ return Unknown;
+ }
+}
+#endif /* TRIE_HASH_PerfectHash */" triehash --multi-byte=0 -C - -H -
+
+# Check that split files work
+testsuccess triehash -C test.c -H test.h --multi-byte=0
+testfileequal "#include \"test.h\"
+ enum PerfectKey PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ default:
+ return Unknown;
+ }
+}" test.c
+testfileequal "#ifndef TRIE_HASH_PerfectHash
+#define TRIE_HASH_PerfectHash
+#include <stddef.h>
+#include <stdint.h>
+enum PerfectKey {
+ Unknown = -1,
+};
+ enum PerfectKey PerfectHash(const char *string, size_t length);
+#endif /* TRIE_HASH_PerfectHash */" test.h
+
+
+# Check the C code generator
+testsuccess triehash -C test.c -H test.c /dev/stdin
+testfileequal "#ifndef TRIE_HASH_PerfectHash
+#define TRIE_HASH_PerfectHash
+#include <stddef.h>
+#include <stdint.h>
+enum PerfectKey {
+ VeryLongWord = 43,
+ Word = 42,
+ Word___0 = 0,
+ Label = 44,
+ Unknown = -9,
+};
+static enum PerfectKey PerfectHash(const char *string, size_t length);
+#ifdef __GNUC__
+typedef uint16_t __attribute__((aligned (1))) triehash_uu16;
+typedef char static_assert16[__alignof__(triehash_uu16) == 1 ? 1 : -1];
+typedef uint32_t __attribute__((aligned (1))) triehash_uu32;
+typedef char static_assert32[__alignof__(triehash_uu32) == 1 ? 1 : -1];
+typedef uint64_t __attribute__((aligned (1))) triehash_uu64;
+typedef char static_assert64[__alignof__(triehash_uu64) == 1 ? 1 : -1];
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+#define onechar(c, s, l) (((uint64_t)(c)) << (s))
+#else
+#define onechar(c, s, l) (((uint64_t)(c)) << (l-8-s))
+#endif
+#if (!defined(__ARM_ARCH) || defined(__ARM_FEATURE_UNALIGNED)) && !defined(TRIE_HASH_NO_MULTI_BYTE)
+#define TRIE_HASH_MULTI_BYTE
+#endif
+#endif /*GNUC */
+#ifdef TRIE_HASH_MULTI_BYTE
+static enum PerfectKey PerfectHash4(const char *string)
+{
+ switch(*((triehash_uu32*) &string[0])) {
+ case 0| onechar('W', 0, 32)| onechar('o', 8, 32)| onechar('r', 16, 32)| onechar('d', 24, 32):
+ return Word;
+ }
+ return Unknown;
+}
+static enum PerfectKey PerfectHash5(const char *string)
+{
+ switch(*((triehash_uu32*) &string[0])) {
+ case 0| onechar('W', 0, 32)| onechar('o', 8, 32)| onechar('r', 16, 32)| onechar('d', 24, 32):
+ switch(string[4]) {
+ case 0| onechar('2', 0, 8):
+ return Label;
+ }
+ }
+ return Unknown;
+}
+static enum PerfectKey PerfectHash7(const char *string)
+{
+ switch(*((triehash_uu32*) &string[0])) {
+ case 0| onechar('W', 0, 32)| onechar('o', 8, 32)| onechar('r', 16, 32)| onechar('d', 24, 32):
+ switch(string[4]) {
+ case 0| onechar('-', 0, 8):
+ switch(string[5]) {
+ case 0| onechar('_', 0, 8):
+ switch(string[6]) {
+ case 0| onechar('0', 0, 8):
+ return Word___0;
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+static enum PerfectKey PerfectHash12(const char *string)
+{
+ switch(*((triehash_uu64*) &string[0])) {
+ case 0| onechar('V', 0, 64)| onechar('e', 8, 64)| onechar('r', 16, 64)| onechar('y', 24, 64)| onechar('L', 32, 64)| onechar('o', 40, 64)| onechar('n', 48, 64)| onechar('g', 56, 64):
+ switch(*((triehash_uu32*) &string[8])) {
+ case 0| onechar('W', 0, 32)| onechar('o', 8, 32)| onechar('r', 16, 32)| onechar('d', 24, 32):
+ return VeryLongWord;
+ }
+ }
+ return Unknown;
+}
+#else
+static enum PerfectKey PerfectHash4(const char *string)
+{
+ switch(string[0]) {
+ case 'W':
+ switch(string[1]) {
+ case 'o':
+ switch(string[2]) {
+ case 'r':
+ switch(string[3]) {
+ case 'd':
+ return Word;
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+static enum PerfectKey PerfectHash5(const char *string)
+{
+ switch(string[0]) {
+ case 'W':
+ switch(string[1]) {
+ case 'o':
+ switch(string[2]) {
+ case 'r':
+ switch(string[3]) {
+ case 'd':
+ switch(string[4]) {
+ case '2':
+ return Label;
+ }
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+static enum PerfectKey PerfectHash7(const char *string)
+{
+ switch(string[0]) {
+ case 'W':
+ switch(string[1]) {
+ case 'o':
+ switch(string[2]) {
+ case 'r':
+ switch(string[3]) {
+ case 'd':
+ switch(string[4]) {
+ case '-':
+ switch(string[5]) {
+ case '_':
+ switch(string[6]) {
+ case '0':
+ return Word___0;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+static enum PerfectKey PerfectHash12(const char *string)
+{
+ switch(string[0]) {
+ case 'V':
+ switch(string[1]) {
+ case 'e':
+ switch(string[2]) {
+ case 'r':
+ switch(string[3]) {
+ case 'y':
+ switch(string[4]) {
+ case 'L':
+ switch(string[5]) {
+ case 'o':
+ switch(string[6]) {
+ case 'n':
+ switch(string[7]) {
+ case 'g':
+ switch(string[8]) {
+ case 'W':
+ switch(string[9]) {
+ case 'o':
+ switch(string[10]) {
+ case 'r':
+ switch(string[11]) {
+ case 'd':
+ return VeryLongWord;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+#endif /* TRIE_HASH_MULTI_BYTE */
+static enum PerfectKey PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ case 4:
+ return PerfectHash4(string);
+ case 5:
+ return PerfectHash5(string);
+ case 7:
+ return PerfectHash7(string);
+ case 12:
+ return PerfectHash12(string);
+ default:
+ return Unknown;
+ }
+}
+#endif /* TRIE_HASH_PerfectHash */" test.c
diff --git a/triehash/tests/test-case-insensitive b/triehash/tests/test-case-insensitive
new file mode 100755
index 000000000..25ab2dd78
--- /dev/null
+++ b/triehash/tests/test-case-insensitive
@@ -0,0 +1,109 @@
+#!/bin/sh
+. $(dirname $(readlink -f $0))/framework.sh
+
+WORDS="Halllo\nH-lllo\nHalll1"
+
+# Case-insensitive test
+testsuccessequal "#include \"/dev/null\"
+#ifdef __GNUC__
+typedef uint16_t __attribute__((aligned (1))) triehash_uu16;
+typedef char static_assert16[__alignof__(triehash_uu16) == 1 ? 1 : -1];
+typedef uint32_t __attribute__((aligned (1))) triehash_uu32;
+typedef char static_assert32[__alignof__(triehash_uu32) == 1 ? 1 : -1];
+typedef uint64_t __attribute__((aligned (1))) triehash_uu64;
+typedef char static_assert64[__alignof__(triehash_uu64) == 1 ? 1 : -1];
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+#define onechar(c, s, l) (((uint64_t)(c)) << (s))
+#else
+#define onechar(c, s, l) (((uint64_t)(c)) << (l-8-s))
+#endif
+#if (!defined(__ARM_ARCH) || defined(__ARM_FEATURE_UNALIGNED)) && !defined(TRIE_HASH_NO_MULTI_BYTE)
+#define TRIE_HASH_MULTI_BYTE
+#endif
+#endif /*GNUC */
+#ifdef TRIE_HASH_MULTI_BYTE
+static enum PerfectKey PerfectHash6(const char *string)
+{
+ switch(string[0] | 0x20) {
+ case 0| onechar('h', 0, 8):
+ switch(string[1]) {
+ case 0| onechar('-', 0, 8):
+ switch(*((triehash_uu32*) &string[2]) | 0x20202020) {
+ case 0| onechar('l', 0, 32)| onechar('l', 8, 32)| onechar('l', 16, 32)| onechar('o', 24, 32):
+ return H_lllo;
+ }
+ break;
+ case 0| onechar('a', 0, 8):
+ case 0| onechar('A', 0, 8):
+ switch(*((triehash_uu16*) &string[2]) | 0x2020) {
+ case 0| onechar('l', 0, 16)| onechar('l', 8, 16):
+ switch(string[4] | 0x20) {
+ case 0| onechar('l', 0, 8):
+ switch(string[5]) {
+ case 0| onechar('1', 0, 8):
+ return Halll1;
+ break;
+ case 0| onechar('o', 0, 8):
+ case 0| onechar('O', 0, 8):
+ return Halllo;
+ }
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+#else
+static enum PerfectKey PerfectHash6(const char *string)
+{
+ switch(string[0] | 0x20) {
+ case 'h':
+ switch(string[1]) {
+ case '-':
+ switch(string[2] | 0x20) {
+ case 'l':
+ switch(string[3] | 0x20) {
+ case 'l':
+ switch(string[4] | 0x20) {
+ case 'l':
+ switch(string[5] | 0x20) {
+ case 'o':
+ return H_lllo;
+ }
+ }
+ }
+ }
+ break;
+ case 'a':
+ case 'A':
+ switch(string[2] | 0x20) {
+ case 'l':
+ switch(string[3] | 0x20) {
+ case 'l':
+ switch(string[4] | 0x20) {
+ case 'l':
+ switch(string[5]) {
+ case '1':
+ return Halll1;
+ break;
+ case 'o':
+ case 'O':
+ return Halllo;
+ }
+ }
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+#endif /* TRIE_HASH_MULTI_BYTE */
+ enum PerfectKey PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ case 6:
+ return PerfectHash6(string);
+ default:
+ return Unknown;
+ }
+}" triehash --multi-byte=3210 --ignore-case -H /dev/null /dev/stdin
diff --git a/triehash/tests/test-enum-include-name-flags b/triehash/tests/test-enum-include-name-flags
new file mode 100755
index 000000000..33bd97c0f
--- /dev/null
+++ b/triehash/tests/test-enum-include-name-flags
@@ -0,0 +1,129 @@
+#!/bin/sh
+. $(dirname $(readlink -f $0))/framework.sh
+
+# Need a short word, we really just need to check if the labels work
+WORDS=w
+
+testsuccessequal "\
+#ifndef TRIE_HASH_PerfectHash
+#define TRIE_HASH_PerfectHash
+#include <stddef.h>
+#include <stdint.h>
+#include <foo.h>
+enum PerfectKey {
+ w = 0,
+ Unknown = -1,
+};
+ enum PerfectKey PerfectHash(const char *string, size_t length);
+#endif /* TRIE_HASH_PerfectHash */" triehash --multi-byte=0 -C /dev/null --include="<foo.h>" /dev/stdin
+
+# Check for --enum-class support
+testsuccessequal "\
+#ifndef TRIE_HASH_PerfectHash
+#define TRIE_HASH_PerfectHash
+#include <stddef.h>
+#include <stdint.h>
+enum class PerfectKey {
+ w = 0,
+ Unknown = -1,
+};
+static enum PerfectKey PerfectHash(const char *string, size_t length);
+static enum PerfectKey PerfectHash1(const char *string)
+{
+ switch(string[0]) {
+ case 'w':
+ return PerfectKey::w;
+ }
+ return PerfectKey::Unknown;
+}
+static enum PerfectKey PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ case 1:
+ return PerfectHash1(string);
+ default:
+ return PerfectKey::Unknown;
+ }
+}
+#endif /* TRIE_HASH_PerfectHash */" triehash --multi-byte=0 --enum-class /dev/stdin
+
+# Check for --enum-name support
+testsuccessequal "\
+#ifndef TRIE_HASH_PerfectHash
+#define TRIE_HASH_PerfectHash
+#include <stddef.h>
+#include <stdint.h>
+enum Foo {
+ Unknown = -1,
+};
+static enum Foo PerfectHash(const char *string, size_t length);
+static enum Foo PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ default:
+ return Unknown;
+ }
+}
+#endif /* TRIE_HASH_PerfectHash */\
+" triehash --multi-byte=0 --enum-name="Foo"
+
+# Check for --enum-class support
+testsuccessequal "\
+#ifndef TRIE_HASH_PerfectHash
+#define TRIE_HASH_PerfectHash
+#include <stddef.h>
+#include <stdint.h>
+enum class Foo::Bar {
+ Unknown = -1,
+};
+static enum Foo::Bar PerfectHash(const char *string, size_t length);
+static enum Foo::Bar PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ default:
+ return Foo::Bar::Unknown;
+ }
+}
+#endif /* TRIE_HASH_PerfectHash */\
+" triehash --multi-byte=0 --enum-class --enum-name="Foo::Bar"
+
+# Check for --function-name support
+testsuccessequal "\
+#ifndef TRIE_HASH_NonSense
+#define TRIE_HASH_NonSense
+#include <stddef.h>
+#include <stdint.h>
+enum PerfectKey {
+ Unknown = -1,
+};
+static enum PerfectKey NonSense(const char *string, size_t length);
+static enum PerfectKey NonSense(const char *string, size_t length)
+{
+ switch (length) {
+ default:
+ return Unknown;
+ }
+}
+#endif /* TRIE_HASH_NonSense */\
+" triehash --multi-byte=0 --function-name="NonSense"
+
+# Check for --counter-name support
+testsuccessequal "\
+#ifndef TRIE_HASH_PerfectHash
+#define TRIE_HASH_PerfectHash
+#include <stddef.h>
+#include <stdint.h>
+enum { MyCounter = 0 };
+enum PerfectKey {
+ Unknown = -1,
+};
+static enum PerfectKey PerfectHash(const char *string, size_t length);
+static enum PerfectKey PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ default:
+ return Unknown;
+ }
+}
+#endif /* TRIE_HASH_PerfectHash */\
+" triehash --multi-byte=0 --counter-name="MyCounter"
diff --git a/triehash/tests/test-multi-byte-level b/triehash/tests/test-multi-byte-level
new file mode 100755
index 000000000..ddfb8cd1b
--- /dev/null
+++ b/triehash/tests/test-multi-byte-level
@@ -0,0 +1,427 @@
+#!/bin/sh
+. $(dirname $(readlink -f $0))/framework.sh
+
+# Check that building a single-byte trie works
+testsuccessequal "\
+┌────────────────────────────────────────────────────┐
+│ Initial trie │
+└────────────────────────────────────────────────────┘
+
+├── V
+│ ├── e
+│ │ ├── r
+│ │ │ ├── y
+│ │ │ │ ├── L
+│ │ │ │ │ ├── o
+│ │ │ │ │ │ ├── n
+│ │ │ │ │ │ │ ├── g
+│ │ │ │ │ │ │ │ ├── W
+│ │ │ │ │ │ │ │ │ ├── o
+│ │ │ │ │ │ │ │ │ │ ├── r
+│ │ │ │ │ │ │ │ │ │ │ ├── d → VeryLongWord
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d → Word
+│ │ │ │ ├── -
+│ │ │ │ │ ├── _
+│ │ │ │ │ │ ├── 0 → Word-_0
+│ │ │ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Rebuilt trie │
+└────────────────────────────────────────────────────┘
+
+├── V
+│ ├── e
+│ │ ├── r
+│ │ │ ├── y
+│ │ │ │ ├── L
+│ │ │ │ │ ├── o
+│ │ │ │ │ │ ├── n
+│ │ │ │ │ │ │ ├── g
+│ │ │ │ │ │ │ │ ├── W
+│ │ │ │ │ │ │ │ │ ├── o
+│ │ │ │ │ │ │ │ │ │ ├── r
+│ │ │ │ │ │ │ │ │ │ │ ├── d → VeryLongWord
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d → Word
+│ │ │ │ ├── -
+│ │ │ │ │ ├── _
+│ │ │ │ │ │ ├── 0 → Word-_0
+│ │ │ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 4 │
+└────────────────────────────────────────────────────┘
+
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d → Word
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 5 │
+└────────────────────────────────────────────────────┘
+
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d
+│ │ │ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 7 │
+└────────────────────────────────────────────────────┘
+
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d
+│ │ │ │ ├── -
+│ │ │ │ │ ├── _
+│ │ │ │ │ │ ├── 0 → Word-_0
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 12 │
+└────────────────────────────────────────────────────┘
+
+├── V
+│ ├── e
+│ │ ├── r
+│ │ │ ├── y
+│ │ │ │ ├── L
+│ │ │ │ │ ├── o
+│ │ │ │ │ │ ├── n
+│ │ │ │ │ │ │ ├── g
+│ │ │ │ │ │ │ │ ├── W
+│ │ │ │ │ │ │ │ │ ├── o
+│ │ │ │ │ │ │ │ │ │ ├── r
+│ │ │ │ │ │ │ │ │ │ │ ├── d → VeryLongWord" triehash --multi-byte=0 -l tree /dev/stdin
+
+# Two byte optimization
+testsuccessequal "\
+┌────────────────────────────────────────────────────┐
+│ Initial trie │
+└────────────────────────────────────────────────────┘
+
+├── Ve
+│ ├── ry
+│ │ ├── Lo
+│ │ │ ├── ng
+│ │ │ │ ├── Wo
+│ │ │ │ │ ├── rd → VeryLongWord
+├── Wo
+│ ├── rd → Word
+│ │ ├── -_
+│ │ │ ├── 0 → Word-_0
+│ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Rebuilt trie │
+└────────────────────────────────────────────────────┘
+
+├── Ve
+│ ├── ry
+│ │ ├── Lo
+│ │ │ ├── ng
+│ │ │ │ ├── Wo
+│ │ │ │ │ ├── rd → VeryLongWord
+├── Wo
+│ ├── rd → Word
+│ │ ├── -
+│ │ │ ├── _0 → Word-_0
+│ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 4 │
+└────────────────────────────────────────────────────┘
+
+├── Wo
+│ ├── rd → Word
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 5 │
+└────────────────────────────────────────────────────┘
+
+├── Wo
+│ ├── rd
+│ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 7 │
+└────────────────────────────────────────────────────┘
+
+├── Wo
+│ ├── rd
+│ │ ├── -_
+│ │ │ ├── 0 → Word-_0
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 12 │
+└────────────────────────────────────────────────────┘
+
+├── Ve
+│ ├── ry
+│ │ ├── Lo
+│ │ │ ├── ng
+│ │ │ │ ├── Wo
+│ │ │ │ │ ├── rd → VeryLongWord" triehash --multi-byte=1 -l tree /dev/stdin
+# Four byte optimization
+testsuccessequal "\
+┌────────────────────────────────────────────────────┐
+│ Initial trie │
+└────────────────────────────────────────────────────┘
+
+├── Very
+│ ├── Long
+│ │ ├── Word → VeryLongWord
+├── Word → Word
+│ ├── -
+│ │ ├── _
+│ │ │ ├── 0 → Word-_0
+│ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Rebuilt trie │
+└────────────────────────────────────────────────────┘
+
+├── Very
+│ ├── Long
+│ │ ├── Word → VeryLongWord
+├── Word → Word
+│ ├── -
+│ │ ├── _
+│ │ │ ├── 0 → Word-_0
+│ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 4 │
+└────────────────────────────────────────────────────┘
+
+├── Word → Word
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 5 │
+└────────────────────────────────────────────────────┘
+
+├── Word
+│ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 7 │
+└────────────────────────────────────────────────────┘
+
+├── Word
+│ ├── -
+│ │ ├── _
+│ │ │ ├── 0 → Word-_0
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 12 │
+└────────────────────────────────────────────────────┘
+
+├── Very
+│ ├── Long
+│ │ ├── Word → VeryLongWord" triehash --multi-byte=2 -l tree /dev/stdin
+# Eigh byte optimization
+testsuccessequal "\
+┌────────────────────────────────────────────────────┐
+│ Initial trie │
+└────────────────────────────────────────────────────┘
+
+├── VeryLong
+│ ├── W
+│ │ ├── o
+│ │ │ ├── r
+│ │ │ │ ├── d → VeryLongWord
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d → Word
+│ │ │ │ ├── -
+│ │ │ │ │ ├── _
+│ │ │ │ │ │ ├── 0 → Word-_0
+│ │ │ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Rebuilt trie │
+└────────────────────────────────────────────────────┘
+
+├── V
+│ ├── eryLongW
+│ │ ├── o
+│ │ │ ├── r
+│ │ │ │ ├── d → VeryLongWord
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d → Word
+│ │ │ │ ├── -
+│ │ │ │ │ ├── _
+│ │ │ │ │ │ ├── 0 → Word-_0
+│ │ │ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 4 │
+└────────────────────────────────────────────────────┘
+
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d → Word
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 5 │
+└────────────────────────────────────────────────────┘
+
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d
+│ │ │ │ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 7 │
+└────────────────────────────────────────────────────┘
+
+├── W
+│ ├── o
+│ │ ├── r
+│ │ │ ├── d
+│ │ │ │ ├── -
+│ │ │ │ │ ├── _
+│ │ │ │ │ │ ├── 0 → Word-_0
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 12 │
+└────────────────────────────────────────────────────┘
+
+├── VeryLong
+│ ├── W
+│ │ ├── o
+│ │ │ ├── r
+│ │ │ │ ├── d → VeryLongWord" triehash --multi-byte=3 -l tree /dev/stdin
+
+
+# Check that building a multi-byte trie works
+testsuccessequal "\
+┌────────────────────────────────────────────────────┐
+│ Initial trie │
+└────────────────────────────────────────────────────┘
+
+├── VeryLong
+│ ├── Word → VeryLongWord
+├── Word → Word
+│ ├── -
+│ │ ├── _
+│ │ │ ├── 0 → Word-_0
+│ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Rebuilt trie │
+└────────────────────────────────────────────────────┘
+
+├── Very
+│ ├── LongWord → VeryLongWord
+├── Word → Word
+│ ├── -
+│ │ ├── _
+│ │ │ ├── 0 → Word-_0
+│ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 4 │
+└────────────────────────────────────────────────────┘
+
+├── Word → Word
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 5 │
+└────────────────────────────────────────────────────┘
+
+├── Word
+│ ├── 2 → Label
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 7 │
+└────────────────────────────────────────────────────┘
+
+├── Word
+│ ├── -
+│ │ ├── _
+│ │ │ ├── 0 → Word-_0
+┌────────────────────────────────────────────────────┐
+│ Trie for words of length 12 │
+└────────────────────────────────────────────────────┘
+
+├── VeryLong
+│ ├── Word → VeryLongWord" triehash -l tree /dev/stdin
+
+
+###### CHANGE THE WORDS FOR THE FOLLOWING TESTS #######
+WORDS="Word"
+
+# Check that we are generating the proper multi-byte and fallback sessions
+testsuccessequal "#include \"/dev/null\"
+#ifdef __GNUC__
+typedef uint16_t __attribute__((aligned (1))) triehash_uu16;
+typedef char static_assert16[__alignof__(triehash_uu16) == 1 ? 1 : -1];
+typedef uint32_t __attribute__((aligned (1))) triehash_uu32;
+typedef char static_assert32[__alignof__(triehash_uu32) == 1 ? 1 : -1];
+typedef uint64_t __attribute__((aligned (1))) triehash_uu64;
+typedef char static_assert64[__alignof__(triehash_uu64) == 1 ? 1 : -1];
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+#define onechar(c, s, l) (((uint64_t)(c)) << (s))
+#else
+#define onechar(c, s, l) (((uint64_t)(c)) << (l-8-s))
+#endif
+#if (!defined(__ARM_ARCH) || defined(__ARM_FEATURE_UNALIGNED)) && !defined(TRIE_HASH_NO_MULTI_BYTE)
+#define TRIE_HASH_MULTI_BYTE
+#endif
+#endif /*GNUC */
+#ifdef TRIE_HASH_MULTI_BYTE
+static enum PerfectKey PerfectHash4(const char *string)
+{
+ switch(*((triehash_uu32*) &string[0])) {
+ case 0| onechar('W', 0, 32)| onechar('o', 8, 32)| onechar('r', 16, 32)| onechar('d', 24, 32):
+ return Word;
+ }
+ return Unknown;
+}
+#else
+static enum PerfectKey PerfectHash4(const char *string)
+{
+ switch(string[0]) {
+ case 'W':
+ switch(string[1]) {
+ case 'o':
+ switch(string[2]) {
+ case 'r':
+ switch(string[3]) {
+ case 'd':
+ return Word;
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+#endif /* TRIE_HASH_MULTI_BYTE */
+ enum PerfectKey PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ case 4:
+ return PerfectHash4(string);
+ default:
+ return Unknown;
+ }
+}" triehash -H /dev/null /dev/stdin
+
+
+# Check that we are generating no multi-byte session
+testsuccessequal "#include \"/dev/null\"
+static enum PerfectKey PerfectHash4(const char *string)
+{
+ switch(string[0]) {
+ case 'W':
+ switch(string[1]) {
+ case 'o':
+ switch(string[2]) {
+ case 'r':
+ switch(string[3]) {
+ case 'd':
+ return Word;
+ }
+ }
+ }
+ }
+ return Unknown;
+}
+ enum PerfectKey PerfectHash(const char *string, size_t length)
+{
+ switch (length) {
+ case 4:
+ return PerfectHash4(string);
+ default:
+ return Unknown;
+ }
+}" triehash --multi-byte=0 -H /dev/null /dev/stdin