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 <arpa/inet.h>
  37 #include <fcntl.h>
  38 #include <netinet/in.h>
  39 #include <sys/mman.h>
  40 #include <sys/stat.h>
  41
  42 #include "common.h"
  43 #include "str.h"
  44 #include "trie.h"
  45
  46 static trie_t *create_trie_from_file(const char *file)
  47 {
  48     trie_t *db;
  49     const char *map, *p, *end;
  50     struct stat st;
  51     int fd;
  52     char line[BUFSIZ];
  53
  54     fd = open(file, O_RDONLY, 0000);
  55     if (fd < 0) {
  56         UNIXERR("open");
  57         return NULL;
  58     }
  59
  60     if (fstat(fd, &st) < 0) {
  61         UNIXERR("fstat");
  62         close(fd);
  63         return NULL;
  64     }
  65
  66     p = map = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
  67     if (map == MAP_FAILED) {
  68         UNIXERR("mmap");
  69         close(fd);
  70         return NULL;
  71     }
  72     close(fd);
  73
  74     end = map + st.st_size;
  75     while (end > map && end[-1] != '\n') {
  76         --end;
  77     }
  78     if (end != map + st.st_size) {
  79         syslog(LOG_WARNING, "file %s miss a final \\n, ignoring last line",
  80                file);
  81     }
  82
  83     db = trie_new();
  84     while (p < end && p != NULL) {
  85         const char *eol = (char *)memchr(p, '\n', end - p);
  86         if (eol == NULL) {
  87             eol = end;
  88         }
  89         if (eol - p > BUFSIZ) {
  90             p = eol - BUFSIZ;
  91         }
  92         int i = 0;
  93 #if 0
  94         for (const char *s = eol - 1 ; s >= p ; --s) {
  95             line[i++] = ascii_tolower(*s);
  96         }
  97 #else
  98         memcpy(line, p, eol - p);
  99         i = eol - p;
 100 #endif
 101         line[i] = '\0';
 102         trie_insert(db, line);
 103         p = eol + 1;
 104     }
 105     munmap((void*)map, st.st_size);
 106     return db;
 107 }
 108
 109
 110 int main(int argc, char *argv[])
 111 {
 112     /* Trivial tests
 113      */
 114     trie_t *trie = trie_new();
 115     trie_insert(trie, "abcdefghi");
 116     trie_insert(trie, "abcde123654789");
 117     trie_insert(trie, "abcde123456789");
 118     trie_insert(trie, "abcde123654789");
 119     trie_insert(trie, "coucou");
 120     trie_insert(trie, "coucou chez vous");
 121
 122 #define ASSERT_TRUE(str)                            \
 123     if (!trie_lookup(trie, str)) {                  \
 124         printf("\"%s\" not found in trie\n", str);  \
 125         return 1;                                   \
 126     }
 127 #define ASSERT_FALSE(str)                           \
 128     if (trie_lookup(trie, str)) {                   \
 129         printf("\"%s\" found in trie\n", str);      \
 130         return 1;                                   \
 131     }
 132     ASSERT_FALSE("");
 133     ASSERT_FALSE("coucou ");
 134     ASSERT_FALSE("abcde123");
 135     ASSERT_FALSE("abcde");
 136     ASSERT_TRUE("abcdefghi");
 137     ASSERT_TRUE("coucou");
 138     ASSERT_FALSE("coucou chez vous tous");
 139     trie_delete(&trie);
 140
 141     /* Perf test
 142      */
 143     if (argc > 1) {
 144         trie = create_trie_from_file(argv[1]);
 145 //        trie_inspect(trie);
 146         trie_delete(&trie);
 147     }
 148     return 0;
 149 }