X-Git-Url: http://git.madism.org/?a=blobdiff_plain;f=common%2Ftst-trie.c;h=31d6c1b47dbe28b85a7fc2cd7a0b1298d252e2a5;hb=92dc834e982d4b71ce6a3fcc2c973e555afd3fcf;hp=20ca5e37a42090fb8d3f181c98fcc4a629f1c99c;hpb=266d6c0bfd9bce408aca73bb0d621e5d4d9fab6f;p=apps%2Fpfixtools.git

diff --git a/common/tst-trie.c b/common/tst-trie.c
index 20ca5e3..31d6c1b 100644
--- a/common/tst-trie.c
+++ b/common/tst-trie.c
@@ -33,19 +33,118 @@
  * Copyright © 2008 Florent Bruneau
  */
 
+#include <time.h>
+#include <sys/time.h>
 #include "common.h"
+#include "str.h"
 #include "trie.h"
+#include "file.h"
 
-int main(void)
+static trie_t *create_trie_from_file(const char *file)
 {
+    trie_t *db;
+    file_map_t map;
+    const char *p, *end;
+    char line[BUFSIZ];
+
+    if (!file_map_open(&map, file, false)) {
+        return NULL;
+    }
+    p   = map.map;
+    end = map.end;
+    while (end > p && end[-1] != '\n') {
+        --end;
+    }
+    if (end != map.end) {
+        warn("file %s miss a final \\n, ignoring last line", file);
+    }
+
+    db = trie_new();
+    while (p < end && p != NULL) {
+        const char *eol = (char *)memchr(p, '\n', end - p);
+        if (eol == NULL) {
+            eol = end;
+        }
+        if (eol - p > BUFSIZ) {
+            p = eol - BUFSIZ;
+        }
+        int i = 0;
+#if 1
+        for (const char *s = eol - 1 ; s >= p ; --s) {
+            line[i++] = ascii_tolower(*s);
+        }
+#else
+        memcpy(line, p, eol - p);
+        i = eol - p;
+#endif
+        line[i] = '\0';
+        trie_insert(db, line);
+        p = eol + 1;
+    }
+    file_map_close(&map);
+    trie_compile(db, false);
+    return db;
+}
+
+
+int main(int argc, char *argv[])
+{
+    /* Trivial tests
+     */
     trie_t *trie = trie_new();
-    trie_insert(trie, "abcdefghi");
-    trie_insert(trie, "abcde123654789");
     trie_insert(trie, "abcde123456789");
     trie_insert(trie, "abcde123654789");
+    trie_insert(trie, "abcdefghi");
     trie_insert(trie, "coucou");
     trie_insert(trie, "coucou chez vous");
-    trie_inspect(trie);
+    trie_insert(trie, "debout !");
+    trie_compile(trie, false);
+    trie_inspect(trie, true);
+
+#define ASSERT_TRUE(str)                            \
+    if (!trie_lookup(trie, str)) {                  \
+        printf("\"%s\" not found in trie\n", str);  \
+        return 1;                                   \
+    }
+#define ASSERT_FALSE(str)                           \
+    if (trie_lookup(trie, str)) {                   \
+        printf("\"%s\" found in trie\n", str);      \
+        return 1;                                   \
+    }
+    ASSERT_FALSE("");
+    ASSERT_FALSE("coucou ");
+    ASSERT_FALSE("abcde123");
+    ASSERT_FALSE("abcde");
+    ASSERT_FALSE("coucou chez vous tous");
+    ASSERT_TRUE("abcde123456789");
+    ASSERT_TRUE("abcde123456789");
+    ASSERT_TRUE("abcde123654789");
+    ASSERT_TRUE("abcdefghi");
+    ASSERT_TRUE("coucou");
+    ASSERT_TRUE("coucou chez vous");
+    ASSERT_TRUE("debout !");
+
     trie_delete(&trie);
+
+    /* Perf test
+     */
+    if (argc > 1) {
+        trie = create_trie_from_file(argv[1]);
+        trie_inspect(trie, false);
+        if (argc > 2) {
+            const uint32_t how_many = 2 * 1000 * 1000;
+            struct timeval start, end;
+            double diff;
+
+            gettimeofday(&start, NULL);
+            for (uint32_t i = 0 ; i < how_many ; ++i) {
+                trie_lookup(trie, argv[2]);
+            }
+            gettimeofday(&end, NULL);
+            diff = (end.tv_sec - start.tv_sec) + (double)(end.tv_usec - start.tv_usec) / 10e6;
+            printf("%u lookups per second\n", (int)(how_many / diff));
+        }
+        trie_delete(&trie);
+    }
     return 0;
 }