Speed-up lookup.

[apps/pfixtools.git] / common / tst-trie.c

diff --git a/common/tst-trie.c b/common/tst-trie.c
index 20ca5e3..739bd41 100644 (file)
--- a/common/tst-trie.c
+++ b/common/tst-trie.c
@@ -34,18 +34,109 @@
  */
 
 #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) {
+            time_t now = time(NULL);
+            for (uint32_t i = 0 ; i < 1000000000 ; ++i) {
+                trie_lookup(trie, argv[2]);
+            }
+            printf("%lu lookups per second\n", 1000000000 / (time(NULL) - now));
+        }
+        trie_delete(&trie);
+    }
     return 0;
 }