libedataserver/e-trie.c

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