camel/camel-trie.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2 /*
   3  *  Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU Lesser General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program 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
  13  *  GNU Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 59 Temple Street #330, Boston, MA 02111-1307, USA.
  18  *
  19  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 #include <config.h>
  23 #endif
  24
  25 #include <stdio.h>
  26 #include <string.h>
  27
  28 #include "camel-memchunk.h"
  29 #include "camel-trie.h"
  30
  31 #define d(x)
  32
  33 struct _trie_state {
  34         struct _trie_state *next;
  35         struct _trie_state *fail;
  36         struct _trie_match *match;
  37         guint final;
  38         gint id;
  39 };
  40
  41 struct _trie_match {
  42         struct _trie_match *next;
  43         struct _trie_state *state;
  44         gunichar c;
  45 };
  46
  47 /**
  48  * CamelTrie:
  49  *
  50  * A trie data structure.
  51  *
  52  * Since: 2.24
  53  **/
  54 struct _CamelTrie {
  55         struct _trie_state root;
  56         GPtrArray *fail_states;
  57         gboolean icase;
  58
  59         CamelMemChunk *match_chunks;
  60         CamelMemChunk *state_chunks;
  61 };
  62
  63 static inline gunichar
  64 trie_utf8_getc (const guchar **in,
  65                 gsize inlen)
  66 {
  67         register const guchar *inptr = *in;
  68         const guchar *inend = inptr + inlen;
  69         register guchar c, r;
  70         register gunichar u, m;
  71
  72         if (inlen == 0)
  73                 return 0;
  74
  75         r = *inptr++;
  76         if (r < 0x80) {
  77                 *in = inptr;
  78                 u = r;
  79         } else if (r < 0xfe) { /* valid start char? */
  80                 u = r;
  81                 m = 0x7f80;     /* used to mask out the length bits */
  82                 do {
  83                         if (inptr >= inend)
  84                                 return 0;
  85
  86                         c = *inptr++;
  87                         if ((c & 0xc0) != 0x80)
  88                                 goto error;
  89
  90                         u = (u << 6) | (c & 0x3f);
  91                         r <<= 1;
  92                         m <<= 5;
  93                 } while (r & 0x40);
  94
  95                 *in = inptr;
  96
  97                 u &= ~m;
  98         } else {
  99         error:
 100                 *in = (*in)+1;
 101                 u = 0xfffe;
 102         }
 103
 104         return u;
 105 }
 106
 107 /**
 108  * camel_trie_new:
 109  * @icase: Case sensitivity for the #CamelTrie.
 110  *
 111  * Creates a new #CamelTrie. If @icase is %TRUE, then pattern matching
 112  * done by the CamelTrie will be case insensitive.
 113  *
 114  * Returns: The newly-created #CamelTrie.
 115  *
 116  * Since: 2.24
 117  **/
 118 CamelTrie *
 119 camel_trie_new (gboolean icase)
 120 {
 121         CamelTrie *trie;
 122
 123         trie = g_new (CamelTrie, 1);
 124         trie->root.next = NULL;
 125         trie->root.fail = NULL;
 126         trie->root.match = NULL;
 127         trie->root.final = 0;
 128
 129         trie->fail_states = g_ptr_array_sized_new (8);
 130         trie->icase = icase;
 131
 132         trie->match_chunks = camel_memchunk_new (8, sizeof (struct _trie_match));
 133         trie->state_chunks = camel_memchunk_new (8, sizeof (struct _trie_state));
 134
 135         return trie;
 136 }
 137
 138 /**
 139  * camel_trie_free:
 140  * @trie: The #CamelTrie to free.
 141  *
 142  * Frees the memory associated with the #CamelTrie @trie.
 143  *
 144  * Since: 2.24
 145  **/
 146 void
 147 camel_trie_free (CamelTrie *trie)
 148 {
 149         g_ptr_array_free (trie->fail_states, TRUE);
 150         camel_memchunk_destroy (trie->match_chunks);
 151         camel_memchunk_destroy (trie->state_chunks);
 152         g_free (trie);
 153 }
 154
 155 static struct _trie_match *
 156 g (struct _trie_state *s,
 157    gunichar c)
 158 {
 159         struct _trie_match *m = s->match;
 160
 161         while (m && m->c != c)
 162                 m = m->next;
 163
 164         return m;
 165 }
 166
 167 static struct _trie_state *
 168 trie_insert (CamelTrie *trie,
 169              gint depth,
 170              struct _trie_state *q,
 171              gunichar c)
 172 {
 173         struct _trie_match *m;
 174
 175         m = camel_memchunk_alloc (trie->match_chunks);
 176         m->next = q->match;
 177         m->c = c;
 178
 179         q->match = m;
 180         q = m->state = camel_memchunk_alloc (trie->state_chunks);
 181         q->match = NULL;
 182         q->fail = &trie->root;
 183         q->final = 0;
 184         q->id = -1;
 185
 186         if (trie->fail_states->len < depth + 1) {
 187                 guint size = trie->fail_states->len;
 188
 189                 size = MAX (size + 64, depth + 1);
 190                 g_ptr_array_set_size (trie->fail_states, size);
 191         }
 192
 193         q->next = trie->fail_states->pdata[depth];
 194         trie->fail_states->pdata[depth] = q;
 195
 196         return q;
 197 }
 198
 199 #if d(!)0
 200 static void
 201 dump_trie (struct _trie_state *s,
 202            gint depth)
 203 {
 204         gchar *p = g_alloca ((depth * 2) + 1);
 205         struct _trie_match *m;
 206
 207         memset (p, ' ', depth * 2);
 208         p[depth * 2] = '\0';
 209
 210         fprintf (
 211                 stderr, "%s[state] %p: final=%d; pattern-id=%d; fail=%p\n",
 212                 p, s, s->final, s->id, s->fail);
 213         m = s->match;
 214         while (m) {
 215                 fprintf (stderr, " %s'%c' -> %p\n", p, m->c, m->state);
 216                 if (m->state)
 217                         dump_trie (m->state, depth + 1);
 218
 219                 m = m->next;
 220         }
 221 }
 222 #endif
 223
 224 /*
 225  * final = empty set
 226  * FOR p = 1 TO #pat
 227  *   q = root
 228  *   FOR j = 1 TO m[p]
 229  *     IF g(q, pat[p][j]) == null
 230  *       insert(q, pat[p][j])
 231  *     ENDIF
 232  *     q = g(q, pat[p][j])
 233  *   ENDFOR
 234  *   final = union(final, q)
 235  * ENDFOR
 236 */
 237
 238 /**
 239  * camel_trie_add:
 240  * @trie: The #CamelTrie to add a pattern to.
 241  * @pattern: The pattern to add.
 242  * @pattern_id: The id to use for the pattern.
 243  *
 244  * Add a new pattern to the #CamelTrie @trie.
 245  *
 246  * Since: 2.24
 247  **/
 248 void
 249 camel_trie_add (CamelTrie *trie,
 250                 const gchar *pattern,
 251                 gint pattern_id)
 252 {
 253         const guchar *inptr = (const guchar *) pattern;
 254         struct _trie_state *q, *q1, *r;
 255         struct _trie_match *m, *n;
 256         gint i, depth = 0;
 257         gunichar c;
 258
 259         /* Step 1: add the pattern to the trie */
 260
 261         q = &trie->root;
 262
 263         while ((c = trie_utf8_getc (&inptr, -1))) {
 264                 if (trie->icase)
 265                         c = g_unichar_tolower (c);
 266
 267                 m = g (q, c);
 268                 if (m == NULL) {
 269                         q = trie_insert (trie, depth, q, c);
 270                 } else {
 271                         q = m->state;
 272                 }
 273
 274                 depth++;
 275         }
 276
 277         q->final = depth;
 278         q->id = pattern_id;
 279
 280         /* Step 2: compute failure graph */
 281
 282         for (i = 0; i < trie->fail_states->len; i++) {
 283                 q = trie->fail_states->pdata[i];
 284                 while (q) {
 285                         m = q->match;
 286                         while (m) {
 287                                 c = m->c;
 288                                 q1 = m->state;
 289                                 r = q->fail;
 290                                 while (r && (n = g (r, c)) == NULL)
 291                                         r = r->fail;
 292
 293                                 if (r != NULL) {
 294                                         q1->fail = n->state;
 295                                         if (q1->fail->final > q1->final)
 296                                                 q1->final = q1->fail->final;
 297                                 } else {
 298                                         if ((n = g (&trie->root, c)))
 299                                                 q1->fail = n->state;
 300                                         else
 301                                                 q1->fail = &trie->root;
 302                                 }
 303
 304                                 m = m->next;
 305                         }
 306
 307                         q = q->next;
 308                 }
 309         }
 310
 311         d (fprintf (stderr, "\nafter adding pattern '%s' to trie %p:\n", pattern, trie));
 312         d (dump_trie (&trie->root, 0));
 313 }
 314
 315 /*
 316  * Aho-Corasick
 317  *
 318  * q = root
 319  * FOR i = 1 TO n
 320  *   WHILE q != fail AND g(q, text[i]) == fail
 321  *     q = h(q)
 322  *   ENDWHILE
 323  *   IF q == fail
 324  *     q = root
 325  *   ELSE
 326  *     q = g(q, text[i])
 327  *   ENDIF
 328  *   IF isElement(q, final)
 329  *     RETURN TRUE
 330  *   ENDIF
 331  * ENDFOR
 332  * RETURN FALSE
 333  */
 334
 335 /**
 336  * camel_trie_search:
 337  * @trie: The #CamelTrie to search in.
 338  * @buffer: The string to match against a pattern in @trie.
 339  * @buflen: The length of @buffer.
 340  * @matched_id: An integer address to store the matched pattern id in.
 341  *
 342  * Try to match the string @buffer with a pattern in @trie.
 343  *
 344  * Returns: The matched pattern, or %NULL if no pattern is matched.
 345  *
 346  * Since: 2.24
 347  **/
 348 const gchar *
 349 camel_trie_search (CamelTrie *trie,
 350                    const gchar *buffer,
 351                    gsize buflen,
 352                    gint *matched_id)
 353 {
 354         const guchar *inptr, *inend, *prev, *pat;
 355         register gsize inlen = buflen;
 356         struct _trie_state *q;
 357         struct _trie_match *m = NULL; /* init to please gcc */
 358         gunichar c;
 359
 360         inptr = (const guchar *) buffer;
 361         inend = inptr + buflen;
 362
 363         q = &trie->root;
 364         pat = prev = inptr;
 365         while ((c = trie_utf8_getc (&inptr, inlen))) {
 366                 inlen = (inend - inptr);
 367
 368                 if (c != 0xfffe) {
 369                         if (trie->icase)
 370                                 c = g_unichar_tolower (c);
 371
 372                         while (q != NULL && (m = g (q, c)) == NULL)
 373                                 q = q->fail;
 374
 375                         if (q == &trie->root)
 376                                 pat = prev;
 377
 378                         if (q == NULL) {
 379                                 q = &trie->root;
 380                                 pat = inptr;
 381                         } else if (m != NULL) {
 382                                 q = m->state;
 383
 384                                 if (q->final) {
 385                                         if (matched_id)
 386                                                 *matched_id = q->id;
 387
 388                                         return (const gchar *) pat;
 389                                 }
 390                         }
 391                 }
 392
 393                 prev = inptr;
 394         }
 395
 396         return NULL;
 397 }