Squashed 'flatcc/' content from commit 473da2a

git-subtree-dir: flatcc
git-subtree-split: 473da2afa5ca435363f8c5e6569167aee6bc31c5

1 files changed, 419 insertions, 0 deletions

diff --git a/external/hash/hash_test.c b/external/hash/hash_test.c
new file mode 100644
index 0000000..d54cc07
--- /dev/null
+++ b/external/hash/hash_test.c
@@ -0,0 +1,419 @@
+/*
+ * The MIT License (MIT)
+ *
+ * Copyright (c) 2015 Mikkel F. Jørgensen, dvide.com
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <assert.h>
+
+/* Not used here, just included to catch compiler errors and warnings. */
+#include "hash.h"
+
+#include "str_set.h"
+#include "token_map.h"
+#include "ht64.h"
+#include "ht32.h"
+#include "ht64rh.h"
+#include "ht32rh.h"
+
+#include "ht_trace.h"
+
+#define test_assert(x) if (!(x)) { printf("Test failed at %s:%d\n", __FILE__, __LINE__); assert(0); exit(1); }
+
+
+str_set_t S;
+token_map_t TM;
+
+char *keys[] = {
+    "foo",
+    "bar",
+    "baz",
+    "gimli",
+    "bofur"
+};
+
+struct token tokens[5];
+
+void free_key(void *context, char *key) {
+    free(key);
+}
+
+void test_str_set()
+{
+    int i;
+    char *s, *s0, *s1;
+    unsigned int n = sizeof(keys)/sizeof(keys[0]);
+
+    /* We rely on zero initialization here. */
+    test_assert(str_set_count(&S) == 0);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        /* We don't have to use strdup, but we test the
+         * allocation management and item replacement. */
+        s = str_set_insert(&S, s, strlen(s), strdup(s), ht_keep);
+        test_assert(str_set_count(&S) == i + 1);
+        test_assert(s == 0);
+    }
+    test_assert(n == 5);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        s = str_set_find(&S, s, strlen(s));
+        test_assert(strcmp(s, keys[i]) == 0);
+    }
+    s = str_set_remove(&S, "gimlibofur", 5);
+    test_assert(strcmp(s, "gimli") == 0);
+    free(s);
+    test_assert(str_set_count(&S) == n - 1);
+    s = str_set_remove(&S, "gimlibofur", 5);
+    test_assert(s == 0);
+    test_assert(str_set_count(&S) == n - 1);
+    s = str_set_insert(&S, "foobarbaz", 6,
+            (s0 = strndup("foobarbaz", 6)), ht_keep);
+    test_assert(s == 0);
+    test_assert(str_set_count(&S) == n);
+    s = str_set_insert(&S, "foobarbaz", 6,
+            (s1 = strndup("foobarbaz", 6)), ht_keep);
+    test_assert(s == s0);
+    free(s1);
+    test_assert(str_set_count(&S) == n);
+    s = str_set_find(&S, "foobar", 6);
+    test_assert(s == s0);
+    s = str_set_insert(&S, "foobarbaz", 6,
+            (s1 = strndup("foobarbaz", 6)), ht_replace);
+    test_assert(s == s0);
+    free(s);
+    s = str_set_find(&S, "foobar", 6);
+    test_assert(s == s1);
+    s = str_set_find(&S, "foobarbaz", 9);
+    test_assert(s == 0);
+    str_set_destroy(&S, free_key, 0);
+    s = str_set_find(&S, "foobar", 6);
+    test_assert(s == 0);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        s = str_set_find(&S, s, strlen(s));
+        test_assert(s == 0);
+    }
+}
+
+void test_str_set2()
+{
+    int i;
+    char *s, *s1;
+    unsigned int n = sizeof(keys)/sizeof(keys[0]);
+
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        str_set_insert(&S, s, strlen(s), s, ht_unique);
+    }
+    test_assert(str_set_count(&S) == n);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        /*
+         * Unique and multi are the same logically, but different
+         * intentionally.
+         */
+        str_set_insert(&S, s, strlen(s), s, ht_multi);
+    }
+    test_assert(str_set_count(&S) == 2 * n);
+    ht_trace_buckets(&S, "after double insert", 0, 8);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        s1 = str_set_find(&S, s, strlen(s));
+        test_assert(strcmp(s, s1) == 0);
+    }
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        s1 = str_set_remove(&S, s, strlen(s));
+        test_assert(strcmp(s, s1) == 0);
+        test_assert(str_set_count(&S) == 2 * n - i - 1);
+        ht_trace_buckets(&S, "after single", 8, 8);
+    }
+    ht_trace_buckets(&S, "after first remove", 0, 8);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        s1 = str_set_remove(&S, s, strlen(s));
+        test_assert(strcmp(s, s1) == 0);
+        test_assert(str_set_count(&S) == n - i - 1);
+    }
+    ht_trace_buckets(&S, "efter second remove", 0, 8);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        s1 = str_set_remove(&S, s, strlen(s));
+        test_assert(s1 == 0);
+        test_assert(str_set_count(&S) == 0);
+    }
+    str_set_clear(&S);
+}
+
+void test_str_set3()
+{
+    int i;
+    char *s, *s1;
+    unsigned int n = sizeof(keys)/sizeof(keys[0]);
+
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        str_set_insert_item(&S, s, ht_unique);
+    }
+    test_assert(str_set_count(&S) == n);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        str_set_insert_item(&S, s, ht_keep);
+    }
+    test_assert(str_set_count(&S) == n);
+    for (i = 0; i < n; ++i) {
+        s = keys[i];
+        s1 = str_set_find_item(&S, s);
+        test_assert(strcmp(s, s1) == 0);
+    }
+    s = keys[1];
+    s1 = str_set_remove_item(&S, s);
+    /*
+     * This doesn't always hold, but here we
+     * are sure because of how we inserted data.
+     */
+    test_assert(s == s1);
+    s1 = str_set_find_item(&S, s);
+    test_assert(s1 == 0);
+    str_set_clear(&S);
+}
+
+void test_str_set4()
+{
+    char *s, *s1;
+
+    s = "dumble";
+    str_set_insert_item(&S, "dumble", ht_keep);
+    s1 = str_set_find_item(&S, s);
+    /* TMnsert without replace. */
+    str_set_insert_item(&S, "2dumble" + 1, ht_keep);
+    test_assert(s == s1);
+    s1 = str_set_find_item(&S, s);
+    test_assert(s == s1);
+    /* TMnsert with replace. */
+    s1 = str_set_insert_item(&S, "2dumble" + 1, ht_replace);
+    /* Old value still returned. */
+    test_assert(s == s1);
+    s1 = str_set_find_item(&S, s);
+    test_assert(s != s1);
+    /* New item returned. */
+    test_assert(strcmp(s1 - 1, "2dumble") == 0);
+    str_set_clear(&S);
+}
+
+void visit_item_set(void *context, token_map_item_t item)
+{
+    int *count = context;
+    ++*count;
+}
+
+void test_token_map()
+{
+    int i, count;
+    token_map_item_t item;
+    unsigned int n = sizeof(keys)/sizeof(keys[0]);
+
+    test_assert(sizeof(tokens)/sizeof(item[0]) == n);
+
+    for (i = 0; i < n; ++i) {
+        tokens[i].token = keys[i];
+        tokens[i].len = strlen(keys[i]);
+    }
+    for (i = 0; i < n; ++i) {
+        item = &tokens[i];
+        token_map_insert(&TM, item->token, item->len, item, ht_unique);
+    }
+    count = 0;
+    token_map_visit(&TM, visit_item_set, &count);
+    test_assert(count == n);
+
+    for (i = 0; i < n; ++i) {
+        item = token_map_find(&TM, keys[i], strlen(keys[i]));
+        test_assert(item->type == 0);
+        item->type = 1;
+    }
+    for (i = 0; i < n; ++i) {
+        item = token_map_find_item(&TM, &tokens[i]);
+        test_assert(item->type == 1);
+        item->type = 2;
+    }
+}
+
+void test_ht32()
+{
+    uint32_t keys[100];
+    int i, j;
+    ht32_t ht;
+    uint32_t *x, *y;
+
+    ht32_init(&ht, 10);
+    for (i = 0; i < 100; ++i) {
+        keys[i] = i + 3398;
+    }
+    for (i = 0; i < 100; ++i) {
+        x = ht32_insert_item(&ht, &keys[i], ht_unique);
+    }
+    for (i = 0; i < 100; ++i) {
+        x = ht32_find_item(&ht, &keys[i]);
+        test_assert(x != 0);
+        test_assert(*x == i + 3398);
+    }
+    for (i = 0; i < 100; ++i) {
+        y = ht32_remove_item(&ht, &keys[i]);
+        test_assert(y != ht32_missing);
+        for (j = 0; j < 100; ++j) {
+            x = ht32_find_item(&ht, &keys[j]);
+            if (j > i) {
+                test_assert(x != ht32_missing);
+                test_assert(*x == j + 3398);
+            } else {
+                test_assert(x == ht32_missing);
+            }
+        }
+    }
+    ht32_clear(&ht);
+}
+
+void test_ht64()
+{
+    uint64_t keys[100];
+    int i, j;
+    ht64_t ht;
+    uint64_t *x, *y;
+
+    ht64_init(&ht, 10);
+    for (i = 0; i < 100; ++i) {
+        keys[i] = i + 3398;
+    }
+    for (i = 0; i < 100; ++i) {
+        x = ht64_insert_item(&ht, &keys[i], ht_unique);
+    }
+    for (i = 0; i < 100; ++i) {
+        x = ht64_find_item(&ht, &keys[i]);
+        test_assert(x != 0);
+        test_assert(*x == i + 3398);
+    }
+    for (i = 0; i < 100; ++i) {
+        y = ht64_remove_item(&ht, &keys[i]);
+        test_assert(y != ht64_missing);
+        for (j = 0; j < 100; ++j) {
+            x = ht64_find_item(&ht, &keys[j]);
+            if (j > i) {
+                test_assert(x != ht64_missing);
+                test_assert(*x == j + 3398);
+            } else {
+                test_assert(x == ht64_missing);
+            }
+        }
+    }
+    ht64_clear(&ht);
+}
+
+void test_ht32rh()
+{
+    uint32_t keys[100];
+    int i, j;
+    ht32rh_t ht;
+    uint32_t *x, *y;
+
+    ht32rh_init(&ht, 10);
+    for (i = 0; i < 100; ++i) {
+        keys[i] = i + 3398;
+    }
+    for (i = 0; i < 100; ++i) {
+        x = ht32rh_insert_item(&ht, &keys[i], ht_unique);
+    }
+    for (i = 0; i < 100; ++i) {
+        x = ht32rh_find_item(&ht, &keys[i]);
+        test_assert(x != 0);
+        test_assert(*x == i + 3398);
+    }
+    for (i = 0; i < 100; ++i) {
+        y = ht32rh_remove_item(&ht, &keys[i]);
+        test_assert(y != ht32rh_missing);
+        for (j = 0; j < 100; ++j) {
+            x = ht32rh_find_item(&ht, &keys[j]);
+            if (j > i) {
+                test_assert(x != ht32rh_missing);
+                test_assert(*x == j + 3398);
+            } else {
+                test_assert(x == ht32rh_missing);
+            }
+        }
+    }
+    ht32rh_clear(&ht);
+}
+
+void test_ht64rh()
+{
+    uint64_t keys[100];
+    int i, j;
+    ht64rh_t ht;
+    uint64_t *x, *y;
+
+    ht64rh_init(&ht, 10);
+    for (i = 0; i < 100; ++i) {
+        keys[i] = i + 3398;
+    }
+    for (i = 0; i < 100; ++i) {
+        x = ht64rh_insert_item(&ht, &keys[i], ht_unique);
+    }
+    for (i = 0; i < 100; ++i) {
+        x = ht64rh_find_item(&ht, &keys[i]);
+        test_assert(x != 0);
+        test_assert(*x == i + 3398);
+    }
+    for (i = 0; i < 100; ++i) {
+        y = ht64rh_remove_item(&ht, &keys[i]);
+        test_assert(y != ht64rh_missing);
+        for (j = 0; j < 100; ++j) {
+            x = ht64rh_find_item(&ht, &keys[j]);
+            if (j > i) {
+                test_assert(x != ht64rh_missing);
+                test_assert(*x == j + 3398);
+            } else {
+                test_assert(x == ht64rh_missing);
+            }
+        }
+    }
+    ht64rh_clear(&ht);
+}
+
+int main(int argc, char *argv[])
+{
+    test_str_set();
+    test_str_set2();
+    test_str_set3();
+    test_str_set4();
+    test_token_map();
+    test_ht32();
+    test_ht64();
+    test_ht32rh();
+    test_ht64rh();
+
+    printf("all tests passed\n");
+
+    return 0;
+}