X-Git-Url: http://git.madism.org/?p=apps%2Fpfixtools.git;a=blobdiff_plain;f=common%2Ftst-trie.c;h=999114e1da437cac26803b71b20b932a7e8713ad;hp=df9e1d27bc23de2d33c4493f014adbcb7a640959;hb=1dc8eb6ccc6f70a51ce0c42773892fcb20806c48;hpb=c7ca68d5bda0b49e7b7bc6a997a4140e6197bf11

diff --git a/common/tst-trie.c b/common/tst-trie.c
index df9e1d2..999114e 100644
--- a/common/tst-trie.c
+++ b/common/tst-trie.c
@@ -87,8 +87,152 @@ static trie_t *create_trie_from_file(const char *file)
 }
 
 
+__attribute__((used))
+static void check_trie_with_file(const trie_t *db, const char *file)
+{
+    file_map_t map;
+    const char *p, *end;
+    char line[BUFSIZ];
+
+    if (!file_map_open(&map, file, false)) {
+        return;
+    }
+    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);
+    }
+
+    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';
+        if (!trie_lookup(db, line)) {
+          warn("'%s' not found in the trie", line);
+        }
+        p = eol + 1;
+    }
+    file_map_close(&map);
+}
+
+
+static bool test_linear(const uint8_t *start, uint32_t len, uint8_t data) {
+    const uint8_t *end = start + len;
+    while (start < end) {
+        const uint8_t val = *start;
+        if (val == data) {
+            return true;
+        } else if (val > data) {
+            return false;
+        }
+        ++start;
+    }
+    return false;
+}
+
+static bool test_dicho(const uint8_t *start, uint32_t len, uint8_t data) {
+    const uint8_t *end = start + len;
+
+    while (start < end) {
+        const uint8_t *mid = start + ((end - start) >> 1);
+        const uint8_t val = *mid;
+
+        if (val == data) {
+            return true;
+        } else if (data < val) {
+            end = mid;
+        } else {
+            start = mid + 1;
+        }
+    }
+    return false;
+}
+
+__attribute__((used))
+static void test_lookup(void) {
+    bool set[64];
+    uint8_t data[64];
+
+    printf("size,dicho,linear\n");
+    for (int i = 1 ; i < 64 ; ++i) {
+        if (i > 32) {
+            int selected = 64;
+            memset(set, 1, 64 * sizeof(bool));
+            while (selected > i) {
+                int val = rand() % 64;
+                if (set[val]) {
+                    set[val] = false;
+                    --selected;
+                }
+            }
+        } else {
+            int selected = 0;
+            memset(set, 0, 64 * sizeof(bool));
+            while (selected < i) {
+                int val = rand() % 64;
+                if (!set[val]) {
+                    set[val] = true;
+                    ++selected;
+                }
+            }
+        }
+        int pos = 0;
+        for (int j = 0 ; j < 64 ; ++j) {
+            if (set[j]) {
+                data[pos] = j;
+                ++pos;
+            }
+        }
+
+        struct timeval start, end;
+        double diff_dicho, diff_linear;
+        const int iterations = 50000000;
+
+        gettimeofday(&start, NULL);
+        for (int k = 0 ; k < iterations ; ++k) {
+            for (int j = 0 ; j < 64 ; ++j) {
+                test_dicho(data, i, j);
+            }
+        }
+        gettimeofday(&end, NULL);
+        diff_dicho = ((end.tv_sec - start.tv_sec) * 10.0)
+             + (double)(end.tv_usec - start.tv_usec) / 10e5;
+
+        gettimeofday(&start, NULL);
+        for (int k = 0 ; k < iterations ; ++k) {
+            for (int j = 0 ; j < 64 ; ++j) {
+                test_linear(data, i, j);
+            }
+        }
+        gettimeofday(&end, NULL);
+        diff_linear = ((end.tv_sec - start.tv_sec) * 10.0)
+             + (double)(end.tv_usec - start.tv_usec) / 10e5;
+        printf("%d,%d,%d\n", i, (int)diff_dicho, (int)diff_linear);
+    }
+}
+
+
 int main(int argc, char *argv[])
 {
+    /* test_lookup(); */
+
     /* Trivial tests
      */
     trie_t *trie = trie_new();
@@ -131,6 +275,7 @@ int main(int argc, char *argv[])
     if (argc > 1) {
         trie = create_trie_from_file(argv[1]);
         trie_inspect(trie, false);
+        check_trie_with_file(trie, argv[1]);
         if (argc > 2) {
             const uint32_t how_many = 8 * 1000 * 1000;
             struct timeval start, end;