dict/lookgrep.c

   1 /* $Id: lookgrep.c,v 1.25 2002-08-02 19:26:55 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   3    Index Data Aps
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <stdio.h>
  28 #include <assert.h>
  29
  30 #include <dfa.h>
  31 #include <dict.h>
  32
  33 typedef unsigned MatchWord;
  34 #define WORD_BITS 32
  35 #define MAX_LENGTH 1024
  36
  37 typedef struct {
  38   int n;                 /* no of MatchWord needed */
  39   int range;             /* max no. of errors */
  40   int fact;              /* (range+1)*n */
  41   MatchWord *match_mask; /* match_mask */
  42 } MatchContext;
  43
  44 #define INLINE
  45
  46 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
  47 {
  48     int off = state & (WORD_BITS-1);
  49     int wno = state / WORD_BITS;
  50
  51     m[mc->n * ch + wno] |= 1<<off;
  52 }
  53
  54 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
  55                                  int state)
  56 {
  57     int off = state & (WORD_BITS-1);
  58     int wno = state / WORD_BITS;
  59
  60     return m[mc->n * ch + wno] & (1<<off);
  61 }
  62
  63 static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
  64 {
  65     MatchContext *mc = (MatchContext *) xmalloc (sizeof(*mc));
  66     int s;
  67
  68     mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
  69     mc->range = range;
  70     mc->fact = (range+1)*mc->n;
  71     mc->match_mask = (MatchWord *) xcalloc (mc->n, sizeof(*mc->match_mask));
  72
  73     for (s = 0; s<dfa->no_states; s++)
  74         if (dfa->states[s]->rule_no)
  75             set_bit (mc, mc->match_mask, 0, s);
  76     return mc;
  77 }
  78
  79 static void rm_MatchContext (MatchContext **mc)
  80 {
  81     xfree ((*mc)->match_mask);
  82     xfree (*mc);
  83     *mc = NULL;
  84 }
  85
  86 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
  87                    struct DFA *dfa, int ch)
  88 {
  89     int j, s = 0;
  90     MatchWord *Rsrc_p = Rsrc, mask;
  91
  92     for (j = 0; j<mc->n; j++)
  93         Rdst[j] = 0;
  94     while (1)
  95     {
  96         mask = *Rsrc_p++;
  97         for (j = 0; j<WORD_BITS/4; j++)
  98         {
  99             if (mask & 15)
 100             {
 101                 if (mask & 1)
 102                 {
 103                     struct DFA_state *state = dfa->states[s];
 104                     int i = state->tran_no;
 105                     while (--i >= 0)
 106                         if (ch >= state->trans[i].ch[0] &&
 107                             ch <= state->trans[i].ch[1])
 108                             set_bit (mc, Rdst, 0, state->trans[i].to);
 109                 }
 110                 if (mask & 2)
 111                 {
 112                     struct DFA_state *state = dfa->states[s+1];
 113                     int i = state->tran_no;
 114                     while (--i >= 0)
 115                         if (ch >= state->trans[i].ch[0] &&
 116                             ch <= state->trans[i].ch[1])
 117                             set_bit (mc, Rdst, 0, state->trans[i].to);
 118                 }
 119                 if (mask & 4)
 120                 {
 121                     struct DFA_state *state = dfa->states[s+2];
 122                     int i = state->tran_no;
 123                     while (--i >= 0)
 124                         if (ch >= state->trans[i].ch[0] &&
 125                             ch <= state->trans[i].ch[1])
 126                             set_bit (mc, Rdst, 0, state->trans[i].to);
 127                 }
 128                 if (mask & 8)
 129                 {
 130                     struct DFA_state *state = dfa->states[s+3];
 131                     int i = state->tran_no;
 132                     while (--i >= 0)
 133                         if (ch >= state->trans[i].ch[0] &&
 134                             ch <= state->trans[i].ch[1])
 135                             set_bit (mc, Rdst, 0, state->trans[i].to);
 136                 }
 137             }
 138             s += 4;
 139             if (s >= dfa->no_states)
 140                 return;
 141             mask >>= 4;
 142         }
 143     }
 144 }
 145
 146 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 147                    struct DFA *dfa)
 148 {
 149     int j, s = 0;
 150     MatchWord *Rsrc_p = Rsrc, mask;
 151     for (j = 0; j<mc->n; j++)
 152         Rdst[j] = 0;
 153     while (1)
 154     {
 155         mask = *Rsrc_p++;
 156         for (j = 0; j<WORD_BITS/4; j++)
 157         {
 158             if (mask & 15)
 159             {
 160                 if (mask & 1)
 161                 {
 162                     struct DFA_state *state = dfa->states[s];
 163                     int i = state->tran_no;
 164                     while (--i >= 0)
 165                         set_bit (mc, Rdst, 0, state->trans[i].to);
 166                 }
 167                 if (mask & 2)
 168                 {
 169                     struct DFA_state *state = dfa->states[s+1];
 170                     int i = state->tran_no;
 171                     while (--i >= 0)
 172                         set_bit (mc, Rdst, 0, state->trans[i].to);
 173                 }
 174                 if (mask & 4)
 175                 {
 176                     struct DFA_state *state = dfa->states[s+2];
 177                     int i = state->tran_no;
 178                     while (--i >= 0)
 179                         set_bit (mc, Rdst, 0, state->trans[i].to);
 180                 }
 181                 if (mask & 8)
 182                 {
 183                     struct DFA_state *state = dfa->states[s+3];
 184                     int i = state->tran_no;
 185                     while (--i >= 0)
 186                         set_bit (mc, Rdst, 0, state->trans[i].to);
 187                 }
 188             }
 189             s += 4;
 190             if (s >= dfa->no_states)
 191                 return;
 192             mask >>= 4;
 193         }
 194     }
 195 }
 196
 197 static void or (MatchContext *mc, MatchWord *Rdst,
 198                 MatchWord *Rsrc1, MatchWord *Rsrc2)
 199 {
 200     int i;
 201     for (i = 0; i<mc->n; i++)
 202         Rdst[i] = Rsrc1[i] | Rsrc2[i];
 203 }
 204
 205 static INLINE int move (MatchContext *mc, MatchWord *Rj1, MatchWord *Rj,
 206                         Dict_char ch, struct DFA *dfa, MatchWord *Rtmp,
 207                         int range)
 208 {
 209     int d;
 210     MatchWord *Rtmp_2 = Rtmp + mc->n;
 211
 212     mask_shift (mc, Rj1, Rj, dfa, ch);
 213     for (d = 1; d <= mc->range; d++)
 214     {
 215         or (mc, Rtmp, Rj, Rj1);                         /* 2,3 */
 216
 217         shift (mc, Rtmp_2, Rtmp, dfa);
 218
 219         mask_shift (mc, Rtmp, Rj+mc->n, dfa, ch);      /* 1 */
 220
 221         or (mc, Rtmp, Rtmp_2, Rtmp);                    /* 1,2,3*/
 222
 223         Rj1 += mc->n;
 224
 225         or (mc, Rj1, Rtmp, Rj);                         /* 1,2,3,4 */
 226
 227         Rj += mc->n;
 228     }
 229     return 1;
 230
 231 }
 232
 233
 234 static int dict_grep (Dict dict, Dict_ptr ptr, MatchContext *mc,
 235                       MatchWord *Rj, int pos, void *client,
 236                       int (*userfunc)(char *, const char *, void *),
 237                       Dict_char *prefix, struct DFA *dfa,
 238                       int *max_pos, int init_pos)
 239 {
 240     int lo, hi, d;
 241     void *p;
 242     short *indxp;
 243     char *info;
 244
 245     dict_bf_readp (dict->dbf, ptr, &p);
 246     lo = 0;
 247     hi = DICT_nodir(p)-1;
 248     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 249
 250     while (lo <= hi)
 251     {
 252         if (indxp[-lo] > 0)
 253         {
 254             /* string (Dict_char *) DICT_EOS terminated */
 255             /* unsigned char        length of information */
 256             /* char *               information */
 257             int j;
 258             int was_match = 0;
 259             info = (char*)p + indxp[-lo];
 260             for (j=0; ; j++)
 261             {
 262                 Dict_char ch;
 263                 MatchWord *Rj0 =    Rj + j    *mc->fact;
 264                 MatchWord *Rj1 =    Rj + (j+1)*mc->fact;
 265                 MatchWord *Rj_tmp = Rj + (j+2)*mc->fact;
 266                 int range;
 267
 268                 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
 269                 prefix[pos+j] = ch;
 270                 if (pos+j > *max_pos)
 271                     *max_pos = pos+j;
 272                 if (ch == DICT_EOS)
 273                 {
 274                     if (was_match)
 275                         if ((*userfunc)((char*) prefix,
 276                                         info+(j+1)*sizeof(Dict_char), client))
 277                             return 1;
 278                     break;
 279                 }
 280                 if (pos+j >= init_pos)
 281                     range = mc->range;
 282                 else
 283                     range = 0;
 284                 move (mc, Rj1, Rj0, ch, dfa, Rj_tmp, range);
 285                 for (d = mc->n; --d >= 0; )
 286                     if (Rj1[range*mc->n + d])
 287                         break;
 288                 if (d < 0)
 289                     break;
 290                 was_match = 0;
 291                 for (d = mc->n; --d >= 0; )
 292                     if (Rj1[range*mc->n + d] & mc->match_mask[d])
 293                     {
 294                         was_match = 1;
 295                         break;
 296                     }
 297             }
 298         }
 299         else
 300         {
 301             MatchWord *Rj1 =    Rj+  mc->fact;
 302             MatchWord *Rj_tmp = Rj+2*mc->fact;
 303             Dict_char ch;
 304             int range;
 305
 306             /* Dict_ptr             subptr */
 307             /* Dict_char            sub char */
 308             /* unsigned char        length of information */
 309             /* char *               information */
 310             info = (char*)p - indxp[-lo];
 311             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
 312             prefix[pos] = ch;
 313
 314             if (pos > *max_pos)
 315                 *max_pos = pos;
 316             if (pos >= init_pos)
 317                 range = mc->range;
 318             else
 319                 range = 0;
 320             move (mc, Rj1, Rj, ch, dfa, Rj_tmp, range);
 321             for (d = mc->n; --d >= 0; )
 322                 if (Rj1[range*mc->n + d])
 323                     break;
 324             if (d >= 0)
 325             {
 326                 Dict_ptr subptr;
 327                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 328                 {
 329                     for (d = mc->n; --d >= 0; )
 330                         if (Rj1[range*mc->n + d] & mc->match_mask[d])
 331                         {
 332                             prefix[pos+1] = DICT_EOS;
 333                             if ((*userfunc)((char*) prefix,
 334                                             info+sizeof(Dict_ptr)+
 335                                             sizeof(Dict_char), client))
 336                                 return 1;
 337                             break;
 338                         }
 339                 }
 340                 memcpy (&subptr, info, sizeof(Dict_ptr));
 341                 if (subptr)
 342                 {
 343                     if (dict_grep (dict, subptr, mc, Rj1, pos+1,
 344                                    client, userfunc, prefix, dfa, max_pos,
 345                                    init_pos))
 346                         return 1;
 347                     dict_bf_readp (dict->dbf, ptr, &p);
 348                     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 349                 }
 350             }
 351         }
 352         lo++;
 353     }
 354     return 0;
 355 }
 356
 357 int dict_lookup_grep (Dict dict, const char *pattern, int range, void *client,
 358                       int *max_pos, int init_pos,
 359                       int (*userfunc)(char *name, const char *info,
 360                                       void *client))
 361 {
 362     MatchWord *Rj;
 363     Dict_char prefix[MAX_LENGTH+1];
 364     const char *this_pattern = pattern;
 365     MatchContext *mc;
 366     struct DFA *dfa = dfa_init();
 367     int i, d;
 368
 369 #if 0
 370     debug_dfa_trav = 1;
 371     debug_dfa_tran = 1;
 372     debug_dfa_followpos = 1;
 373     dfa_verbose = 1;
 374 #endif
 375
 376     logf (LOG_DEBUG, "dict_lookup_grep range=%d", range);
 377     for (i = 0; pattern[i]; i++)
 378     {
 379         logf (LOG_DEBUG, " %3d  %c", pattern[i],
 380               (pattern[i] > ' ' && pattern[i] < 127) ? pattern[i] : '?');
 381     }
 382
 383     dfa_set_cmap (dfa, dict->grep_cmap_data, dict->grep_cmap);
 384
 385     i = dfa_parse (dfa, &this_pattern);
 386     if (i || *this_pattern)
 387     {
 388         dfa_delete (&dfa);
 389         return -1;
 390     }
 391     dfa_mkstate (dfa);
 392
 393     mc = mk_MatchContext (dfa, range);
 394
 395     Rj = (MatchWord *) xcalloc ((MAX_LENGTH+1) * mc->n, sizeof(*Rj));
 396
 397     set_bit (mc, Rj, 0, 0);
 398     for (d = 1; d<=mc->range; d++)
 399     {
 400         int s;
 401         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
 402         for (s = 0; s<dfa->no_states; s++)
 403         {
 404             if (get_bit (mc, Rj, d-1, s))
 405             {
 406                 struct DFA_state *state = dfa->states[s];
 407                 int i = state->tran_no;
 408                 while (--i >= 0)
 409                     set_bit (mc, Rj, d, state->trans[i].to);
 410             }
 411         }
 412     }
 413     *max_pos = 0;
 414     if (dict->head.root)
 415         i = dict_grep (dict, dict->head.root, mc, Rj, 0, client,
 416                        userfunc, prefix,
 417                        dfa, max_pos, init_pos);
 418     else
 419         i = 0;
 420     logf (LOG_DEBUG, "max_pos = %d", *max_pos);
 421     dfa_delete (&dfa);
 422     xfree (Rj);
 423     rm_MatchContext (&mc);
 424     return i;
 425 }
 426
 427 void dict_grep_cmap (Dict dict, void *vp,
 428                      const char **(*cmap)(void *vp, const char **from, int len))
 429 {
 430     dict->grep_cmap = cmap;
 431     dict->grep_cmap_data = vp;
 432 }