util/gtrie.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2 /*  GMime
   3  *  Copyright (C) 2000-2012 Jeffrey Stedfast
   4  *
   5  *  This library is free software; you can redistribute it and/or
   6  *  modify it under the terms of the GNU Lesser General Public License
   7  *  as published by the Free Software Foundation; either version 2.1
   8  *  of the License, or (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public
  16  *  License along with this library; if not, write to the Free
  17  *  Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  18  *  02110-1301, USA.
  19  */
  20
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include <config.h>
  24 #endif
  25
  26 #include <stdio.h>
  27 #include <string.h>
  28
  29 #include "gtrie.h"
  30
  31 #ifdef ENABLE_WARNINGS
  32 #define w(x) x
  33 #else
  34 #define w(x)
  35 #endif /* ENABLE_WARNINGS */
  36
  37 #define d(x)
  38
  39 struct _trie_state {
  40         struct _trie_state *next;
  41         struct _trie_state *fail;
  42         struct _trie_match *match;
  43         unsigned int final;
  44         int id;
  45 };
  46
  47 struct _trie_match {
  48         struct _trie_match *next;
  49         struct _trie_state *state;
  50         gunichar c;
  51 };
  52
  53 struct _GTrie {
  54         struct _trie_state root;
  55         GPtrArray *fail_states;
  56         gboolean icase;
  57 };
  58
  59 static void trie_match_free (struct _trie_match *match);
  60 static void trie_state_free (struct _trie_state *state);
  61
  62 static struct _trie_match *
  63 trie_match_new (void)
  64 {
  65         return g_slice_new (struct _trie_match);
  66 }
  67
  68 static void
  69 trie_match_free (struct _trie_match *match)
  70 {
  71         struct _trie_match *next;
  72
  73         while (match) {
  74                 next = match->next;
  75                 trie_state_free (match->state);
  76                 g_slice_free (struct _trie_match, match);
  77                 match = next;
  78         }
  79 }
  80
  81 static struct _trie_state *
  82 trie_state_new (void)
  83 {
  84         return g_slice_new (struct _trie_state);
  85 }
  86
  87 static void
  88 trie_state_free (struct _trie_state *state)
  89 {
  90         trie_match_free (state->match);
  91         g_slice_free (struct _trie_state, state);
  92 }
  93
  94
  95 static inline gunichar
  96 trie_utf8_getc (const char **in, size_t inlen)
  97 {
  98         register const unsigned char *inptr = (const unsigned char *) *in;
  99         const unsigned char *inend = inptr + inlen;
 100         register unsigned char c, r;
 101         register gunichar m, u = 0;
 102
 103         if (inlen == 0)
 104                 return 0;
 105
 106         r = *inptr++;
 107         if (r < 0x80) {
 108                 *in = (const char *) inptr;
 109                 u = r;
 110         } else if (r < 0xfe) { /* valid start char? */
 111                 u = r;
 112                 m = 0x7f80;     /* used to mask out the length bits */
 113                 do {
 114                         if (inptr >= inend)
 115                                 return 0;
 116
 117                         c = *inptr++;
 118                         if ((c & 0xc0) != 0x80)
 119                                 goto error;
 120
 121                         u = (u << 6) | (c & 0x3f);
 122                         r <<= 1;
 123                         m <<= 5;
 124                 } while (r & 0x40);
 125
 126                 *in = (const char *) inptr;
 127
 128                 u &= ~m;
 129         } else {
 130         error:
 131                 *in = (*in) + 1;
 132                 u = 0xfffe;
 133         }
 134
 135         return u;
 136 }
 137
 138
 139 GTrie *
 140 g_trie_new (gboolean icase)
 141 {
 142         GTrie *trie;
 143
 144         trie = g_new (GTrie, 1);
 145         trie->root.next = NULL;
 146         trie->root.fail = NULL;
 147         trie->root.match = NULL;
 148         trie->root.final = 0;
 149
 150         trie->fail_states = g_ptr_array_new ();
 151         trie->icase = icase;
 152
 153         return trie;
 154 }
 155
 156
 157 void
 158 g_trie_free (GTrie *trie)
 159 {
 160         g_ptr_array_free (trie->fail_states, TRUE);
 161         trie_match_free (trie->root.match);
 162         g_free (trie);
 163 }
 164
 165
 166
 167 static struct _trie_match *
 168 g (struct _trie_state *s, gunichar c)
 169 {
 170         struct _trie_match *m = s->match;
 171
 172         while (m && m->c != c)
 173                 m = m->next;
 174
 175         return m;
 176 }
 177
 178 static struct _trie_state *
 179 trie_insert (GTrie *trie, guint depth, struct _trie_state *q, gunichar c)
 180 {
 181         struct _trie_match *m;
 182
 183         m = trie_match_new ();
 184         m->next = q->match;
 185         m->c = c;
 186
 187         q->match = m;
 188         q = m->state = trie_state_new ();
 189         q->match = NULL;
 190         q->fail = &trie->root;
 191         q->final = 0;
 192         q->id = 0;
 193
 194         if (trie->fail_states->len < depth + 1) {
 195                 unsigned int size = trie->fail_states->len;
 196
 197                 size = MAX (size + 64, depth + 1);
 198                 g_ptr_array_set_size (trie->fail_states, size);
 199         }
 200
 201         q->next = trie->fail_states->pdata[depth];
 202         trie->fail_states->pdata[depth] = q;
 203
 204         return q;
 205 }
 206
 207
 208 #if d(!)0
 209 static void
 210 dump_trie (struct _trie_state *s, int depth)
 211 {
 212         char *p = g_alloca ((depth * 2) + 1);
 213         struct _trie_match *m;
 214
 215         memset (p, ' ', depth * 2);
 216         p[depth * 2] = '\0';
 217
 218         fprintf (stderr, "%s[state] %p: final=%d; pattern-id=%s; fail=%p\n",
 219                  p, s, s->final, s->id, s->fail);
 220         m = s->match;
 221         while (m) {
 222                 fprintf (stderr, " %s'%c' -> %p\n", p, m->c, m->state);
 223                 if (m->state)
 224                         dump_trie (m->state, depth + 1);
 225
 226                 m = m->next;
 227         }
 228 }
 229 #endif
 230
 231
 232 /*
 233  * final = empty set
 234  * FOR p = 1 TO #pat
 235  *   q = root
 236  *   FOR j = 1 TO m[p]
 237  *     IF g(q, pat[p][j]) == null
 238  *       insert(q, pat[p][j])
 239  *     ENDIF
 240  *     q = g(q, pat[p][j])
 241  *   ENDFOR
 242  *   final = union(final, q)
 243  * ENDFOR
 244 */
 245
 246 void
 247 g_trie_add (GTrie *trie, const char *pattern, int pattern_id)
 248 {
 249         const char *inptr = pattern;
 250         struct _trie_state *q, *q1, *r;
 251         struct _trie_match *m, *n;
 252         guint i, depth = 0;
 253         gunichar c;
 254
 255         /* Step 1: add the pattern to the trie */
 256
 257         q = &trie->root;
 258
 259         while ((c = trie_utf8_getc (&inptr, -1))) {
 260                 if (c == 0xfffe) {
 261                         w(g_warning ("Invalid UTF-8 sequence in pattern '%s' at %s",
 262                                      pattern, (inptr - 1)));
 263                         continue;
 264                 }
 265
 266                 if (trie->icase)
 267                         c = g_unichar_tolower (c);
 268
 269                 m = g (q, c);
 270                 if (m == NULL) {
 271                         q = trie_insert (trie, depth, q, c);
 272                 } else {
 273                         q = m->state;
 274                 }
 275
 276                 depth++;
 277         }
 278
 279         q->final = depth;
 280         q->id = pattern_id;
 281
 282         /* Step 2: compute failure graph */
 283
 284         for (i = 0; i < trie->fail_states->len; i++) {
 285                 q = trie->fail_states->pdata[i];
 286                 while (q) {
 287                         m = q->match;
 288                         while (m) {
 289                                 c = m->c;
 290                                 q1 = m->state;
 291                                 r = q->fail;
 292                                 while (r && (n = g (r, c)) == NULL)
 293                                         r = r->fail;
 294
 295                                 if (r != NULL) {
 296                                         q1->fail = n->state;
 297                                         if (q1->fail->final > q1->final)
 298                                                 q1->final = q1->fail->final;
 299                                 } else {
 300                                         if ((n = g (&trie->root, c)))
 301                                                 q1->fail = n->state;
 302                                         else
 303                                                 q1->fail = &trie->root;
 304                                 }
 305
 306                                 m = m->next;
 307                         }
 308
 309                         q = q->next;
 310                 }
 311         }
 312
 313         d(fprintf (stderr, "\nafter adding pattern '%s' to trie %p:\n", pattern, trie));
 314         d(dump_trie (&trie->root, 0));
 315 }
 316
 317 /*
 318  * Aho-Corasick
 319  *
 320  * q = root
 321  * FOR i = 1 TO n
 322  *   WHILE q != fail AND g(q, text[i]) == fail
 323  *     q = h(q)
 324  *   ENDWHILE
 325  *   IF q == fail
 326  *     q = root
 327  *   ELSE
 328  *     q = g(q, text[i])
 329  *   ENDIF
 330  *   IF isElement(q, final)
 331  *     RETURN TRUE
 332  *   ENDIF
 333  * ENDFOR
 334  * RETURN FALSE
 335  */
 336
 337 const char *
 338 g_trie_quick_search (GTrie *trie, const char *buffer, size_t buflen, int *matched_id)
 339 {
 340         const char *inptr, *inend, *prev, *pat;
 341         register size_t inlen = buflen;
 342         struct _trie_match *m = NULL;
 343         struct _trie_state *q;
 344         gunichar c;
 345
 346         inend = buffer + buflen;
 347         inptr = buffer;
 348
 349         q = &trie->root;
 350         pat = prev = inptr;
 351         while ((c = trie_utf8_getc (&inptr, inlen))) {
 352                 inlen = (inend - inptr);
 353
 354                 if (c == 0xfffe) {
 355 #ifdef ENABLE_WARNINGS
 356                         prev = (inptr - 1);
 357                         pat = buffer + buflen;
 358                         g_warning ("Invalid UTF-8 in buffer '%.*s' at %.*s",
 359                                    buflen, buffer, pat - prev, prev);
 360 #endif
 361
 362                         pat = prev = inptr;
 363                 }
 364
 365                 if (trie->icase)
 366                         c = g_unichar_tolower (c);
 367
 368                 while (q != NULL && (m = g (q, c)) == NULL)
 369                         q = q->fail;
 370
 371                 if (q == &trie->root)
 372                         pat = prev;
 373
 374                 if (q == NULL) {
 375                         q = &trie->root;
 376                         pat = inptr;
 377                 } else if (m != NULL) {
 378                         q = m->state;
 379
 380                         if (q->final) {
 381                                 if (matched_id)
 382                                         *matched_id = q->id;
 383
 384                                 return pat;
 385                         }
 386                 }
 387
 388                 prev = inptr;
 389         }
 390
 391         return NULL;
 392 }
 393
 394 const char *
 395 g_trie_search (GTrie *trie, const char *buffer, size_t buflen, int *matched_id)
 396 {
 397         const char *inptr, *inend, *prev, *pat;
 398         register size_t inlen = buflen;
 399         struct _trie_match *m = NULL;
 400         struct _trie_state *q;
 401         size_t matched = 0;
 402         gunichar c;
 403
 404         inend = buffer + buflen;
 405         inptr = buffer;
 406
 407         q = &trie->root;
 408         pat = prev = inptr;
 409         while ((c = trie_utf8_getc (&inptr, inlen))) {
 410                 inlen = (inend - inptr);
 411
 412                 if (c == 0xfffe) {
 413                         if (matched)
 414                                 return pat;
 415
 416 #ifdef ENABLE_WARNINGS
 417                         prev = (inptr - 1);
 418                         pat = buffer + buflen;
 419                         g_warning ("Invalid UTF-8 in buffer '%.*s' at %.*s",
 420                                    buflen, buffer, pat - prev, prev);
 421 #endif
 422
 423                         pat = prev = inptr;
 424                 }
 425
 426                 if (trie->icase)
 427                         c = g_unichar_tolower (c);
 428
 429                 while (q != NULL && (m = g (q, c)) == NULL && matched == 0)
 430                         q = q->fail;
 431
 432                 if (q == &trie->root) {
 433                         if (matched)
 434                                 return pat;
 435
 436                         pat = prev;
 437                 }
 438
 439                 if (q == NULL) {
 440                         if (matched)
 441                                 return pat;
 442
 443                         q = &trie->root;
 444                         pat = inptr;
 445                 } else if (m != NULL) {
 446                         q = m->state;
 447
 448                         if (q->final > matched) {
 449                                 if (matched_id)
 450                                         *matched_id = q->id;
 451
 452                                 matched = q->final;
 453                         }
 454                 }
 455
 456                 prev = inptr;
 457         }
 458
 459         return matched ? pat : NULL;
 460 }
 461
 462
 463 #ifdef TEST
 464
 465 static char *patterns[] = {
 466         "news://",
 467         "nntp://",
 468         "telnet://",
 469         "file://",
 470         "ftp://",
 471         "http://",
 472         "https://",
 473         "www.",
 474         "ftp.",
 475         "mailto:",
 476         "@"
 477 };
 478
 479 static char *haystacks[] = {
 480         "try this url: http://www.ximian.com",
 481         "or, feel free to email me at fejj@ximian.com",
 482         "don't forget to check out www.ximian.com",
 483         "I've attached a file (file:///cvs/gmime/gmime/gtrie.c)",
 484 };
 485
 486 int main (int argc, char **argv)
 487 {
 488         const char *match;
 489         GTrie *trie;
 490         guint i;
 491         int id;
 492
 493         trie = g_trie_new (TRUE);
 494         for (i = 0; i < G_N_ELEMENTS (patterns); i++)
 495                 g_trie_add (trie, patterns[i], i);
 496
 497         for (i = 0; i < G_N_ELEMENTS (haystacks); i++) {
 498                 if ((match = g_trie_search (trie, haystacks[i], -1, &id))) {
 499                         fprintf (stderr, "matched @ '%s' with pattern '%s'\n", match, patterns[id]);
 500                 } else {
 501                         fprintf (stderr, "no match\n");
 502                 }
 503         }
 504
 505         fflush (stdout);
 506
 507         g_trie_free (trie);
 508
 509         return match == NULL ? 0 : 1;
 510 }
 511 #endif /* TEST */