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