common/tst-trie.c

   1 /******************************************************************************/
   2 /*          pfixtools: a collection of postfix related tools                  */
   3 /*          ~~~~~~~~~                                                         */
   4 /*  ________________________________________________________________________  */
   5 /*                                                                            */
   6 /*  Redistribution and use in source and binary forms, with or without        */
   7 /*  modification, are permitted provided that the following conditions        */
   8 /*  are met:                                                                  */
   9 /*                                                                            */
  10 /*  1. Redistributions of source code must retain the above copyright         */
  11 /*     notice, this list of conditions and the following disclaimer.          */
  12 /*  2. Redistributions in binary form must reproduce the above copyright      */
  13 /*     notice, this list of conditions and the following disclaimer in the    */
  14 /*     documentation and/or other materials provided with the distribution.   */
  15 /*  3. The names of its contributors may not be used to endorse or promote    */
  16 /*     products derived from this software without specific prior written     */
  17 /*     permission.                                                            */
  18 /*                                                                            */
  19 /*  THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND   */
  20 /*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE     */
  21 /*  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        */
  22 /*  PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS    */
  23 /*  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR    */
  24 /*  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF      */
  25 /*  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  */
  26 /*  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN   */
  27 /*  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)   */
  28 /*  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF    */
  29 /*  THE POSSIBILITY OF SUCH DAMAGE.                                           */
  30 /******************************************************************************/
  31
  32 /*
  33  * Copyright © 2008 Florent Bruneau
  34  */
  35
  36 #include <time.h>
  37 #include <sys/time.h>
  38 #include "common.h"
  39 #include "str.h"
  40 #include "trie.h"
  41 #include "file.h"
  42
  43 static trie_t *create_trie_from_file(const char *file)
  44 {
  45     trie_t *db;
  46     file_map_t map;
  47     const char *p, *end;
  48     char line[BUFSIZ];
  49
  50     if (!file_map_open(&map, file, false)) {
  51         return NULL;
  52     }
  53     p   = map.map;
  54     end = map.end;
  55     while (end > p && end[-1] != '\n') {
  56         --end;
  57     }
  58     if (end != map.end) {
  59         warn("file %s miss a final \\n, ignoring last line", file);
  60     }
  61
  62     db = trie_new();
  63     while (p < end && p != NULL) {
  64         const char *eol = (char *)memchr(p, '\n', end - p);
  65         if (eol == NULL) {
  66             eol = end;
  67         }
  68         if (eol - p > BUFSIZ) {
  69             p = eol - BUFSIZ;
  70         }
  71         int i = 0;
  72 #if 1
  73         for (const char *s = eol - 1 ; s >= p ; --s) {
  74             line[i++] = ascii_tolower(*s);
  75         }
  76 #else
  77         memcpy(line, p, eol - p);
  78         i = eol - p;
  79 #endif
  80         line[i] = '\0';
  81         trie_insert(db, line);
  82         p = eol + 1;
  83     }
  84     file_map_close(&map);
  85     trie_compile(db, false);
  86     return db;
  87 }
  88
  89
  90 __attribute__((used))
  91 static void check_trie_with_file(const trie_t *db, const char *file)
  92 {
  93     file_map_t map;
  94     const char *p, *end;
  95     char line[BUFSIZ];
  96
  97     if (!file_map_open(&map, file, false)) {
  98         return;
  99     }
 100     p   = map.map;
 101     end = map.end;
 102     while (end > p && end[-1] != '\n') {
 103         --end;
 104     }
 105     if (end != map.end) {
 106         warn("file %s miss a final \\n, ignoring last line", file);
 107     }
 108
 109     while (p < end && p != NULL) {
 110         const char *eol = (char *)memchr(p, '\n', end - p);
 111         if (eol == NULL) {
 112             eol = end;
 113         }
 114         if (eol - p > BUFSIZ) {
 115             p = eol - BUFSIZ;
 116         }
 117         int i = 0;
 118 #if 1
 119         for (const char *s = eol - 1 ; s >= p ; --s) {
 120             line[i++] = ascii_tolower(*s);
 121         }
 122 #else
 123         memcpy(line, p, eol - p);
 124         i = eol - p;
 125 #endif
 126         line[i] = '\0';
 127         if (!trie_lookup(db, line)) {
 128           warn("'%s' not found in the trie", line);
 129         }
 130         p = eol + 1;
 131     }
 132     file_map_close(&map);
 133 }
 134
 135
 136 static bool test_linear(const uint8_t *start, uint32_t len, uint8_t data) {
 137     const uint8_t *end = start + len;
 138     while (start < end) {
 139         const uint8_t val = *start;
 140         if (val == data) {
 141             return true;
 142         } else if (val > data) {
 143             return false;
 144         }
 145         ++start;
 146     }
 147     return false;
 148 }
 149
 150 static bool test_dicho(const uint8_t *start, uint32_t len, uint8_t data) {
 151     const uint8_t *end = start + len;
 152
 153     while (start < end) {
 154         const uint8_t *mid = start + ((end - start) >> 1);
 155         const uint8_t val = *mid;
 156
 157         if (val == data) {
 158             return true;
 159         } else if (data < val) {
 160             end = mid;
 161         } else {
 162             start = mid + 1;
 163         }
 164     }
 165     return false;
 166 }
 167
 168 __attribute__((used))
 169 static void test_lookup(void) {
 170     bool set[64];
 171     uint8_t data[64];
 172
 173     printf("size,dicho,linear\n");
 174     for (int i = 1 ; i < 64 ; ++i) {
 175         if (i > 32) {
 176             int selected = 64;
 177             memset(set, 1, 64 * sizeof(bool));
 178             while (selected > i) {
 179                 int val = rand() % 64;
 180                 if (set[val]) {
 181                     set[val] = false;
 182                     --selected;
 183                 }
 184             }
 185         } else {
 186             int selected = 0;
 187             memset(set, 0, 64 * sizeof(bool));
 188             while (selected < i) {
 189                 int val = rand() % 64;
 190                 if (!set[val]) {
 191                     set[val] = true;
 192                     ++selected;
 193                 }
 194             }
 195         }
 196         int pos = 0;
 197         for (int j = 0 ; j < 64 ; ++j) {
 198             if (set[j]) {
 199                 data[pos] = j;
 200                 ++pos;
 201             }
 202         }
 203
 204         struct timeval start, end;
 205         double diff_dicho, diff_linear;
 206         const int iterations = 50000000;
 207
 208         gettimeofday(&start, NULL);
 209         for (int k = 0 ; k < iterations ; ++k) {
 210             for (int j = 0 ; j < 64 ; ++j) {
 211                 test_dicho(data, i, j);
 212             }
 213         }
 214         gettimeofday(&end, NULL);
 215         diff_dicho = ((end.tv_sec - start.tv_sec) * 10.0)
 216              + (double)(end.tv_usec - start.tv_usec) / 10e5;
 217
 218         gettimeofday(&start, NULL);
 219         for (int k = 0 ; k < iterations ; ++k) {
 220             for (int j = 0 ; j < 64 ; ++j) {
 221                 test_linear(data, i, j);
 222             }
 223         }
 224         gettimeofday(&end, NULL);
 225         diff_linear = ((end.tv_sec - start.tv_sec) * 10.0)
 226              + (double)(end.tv_usec - start.tv_usec) / 10e5;
 227         printf("%d,%d,%d\n", i, (int)diff_dicho, (int)diff_linear);
 228     }
 229 }
 230
 231
 232 int main(int argc, char *argv[])
 233 {
 234     /* test_lookup(); */
 235
 236     /* Trivial tests
 237      */
 238     trie_t *trie = trie_new();
 239     trie_insert(trie, "abcde123456789");
 240     trie_insert(trie, "abcde123654789");
 241     trie_insert(trie, "abcdefghi");
 242     trie_insert(trie, "coucou");
 243     trie_insert(trie, "coucou chez vous");
 244     trie_insert(trie, "debout !");
 245     trie_compile(trie, false);
 246     trie_inspect(trie, true);
 247
 248 #define ASSERT_TRUE(str)                            \
 249     if (!trie_lookup(trie, str)) {                  \
 250         printf("\"%s\" not found in trie\n", str);  \
 251         return 1;                                   \
 252     }
 253 #define ASSERT_FALSE(str)                           \
 254     if (trie_lookup(trie, str)) {                   \
 255         printf("\"%s\" found in trie\n", str);      \
 256         return 1;                                   \
 257     }
 258     ASSERT_FALSE("");
 259     ASSERT_FALSE("coucou ");
 260     ASSERT_FALSE("abcde123");
 261     ASSERT_FALSE("abcde");
 262     ASSERT_FALSE("coucou chez vous tous");
 263     ASSERT_TRUE("abcde123456789");
 264     ASSERT_TRUE("abcde123456789");
 265     ASSERT_TRUE("abcde123654789");
 266     ASSERT_TRUE("abcdefghi");
 267     ASSERT_TRUE("coucou");
 268     ASSERT_TRUE("coucou chez vous");
 269     ASSERT_TRUE("debout !");
 270
 271     trie_delete(&trie);
 272
 273     /* Perf test
 274      */
 275     if (argc > 1) {
 276         trie = create_trie_from_file(argv[1]);
 277         trie_inspect(trie, false);
 278         check_trie_with_file(trie, argv[1]);
 279         if (argc > 2) {
 280             const uint32_t how_many = 8 * 1000 * 1000;
 281             struct timeval start, end;
 282             double diff;
 283
 284             gettimeofday(&start, NULL);
 285             for (uint32_t i = 0 ; i < how_many ; ++i) {
 286                 trie_lookup(trie, argv[2]);
 287             }
 288             gettimeofday(&end, NULL);
 289             diff = (end.tv_sec - start.tv_sec) + (double)(end.tv_usec - start.tv_usec) / 10e6;
 290             printf("%u lookups per second\n", (int)(how_many / diff));
 291         }
 292         trie_delete(&trie);
 293     }
 294     return 0;
 295 }