dict/lookgrep.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: lookgrep.c,v $
   7  * Revision 1.2  1994-10-04 12:08:07  adam
   8  * Some bug fixes and some optimizations.
   9  *
  10  * Revision 1.1  1994/10/03  17:23:04  adam
  11  * First version of dictionary lookup with regular expressions and errors.
  12  *
  13  */
  14
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <stdio.h>
  18 #include <assert.h>
  19
  20 #include <dfa.h>
  21 #include <dict.h>
  22
  23 typedef unsigned MatchWord;
  24 #define WORD_BITS 32
  25 #define MAX_LENGTH 1024
  26
  27 typedef struct {
  28   int n;                 /* no of MatchWord needed */
  29   int range;             /* max no. of errors */
  30   int fact;              /* (range+1)*n */
  31   MatchWord *match_mask; /* match_mask */
  32 } MatchContext;
  33
  34 #define INLINE
  35
  36 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
  37 {
  38     int off = state & (WORD_BITS-1);
  39     int wno = state / WORD_BITS;
  40
  41     m[mc->n * ch + wno] |= 1<<off;
  42 }
  43
  44 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
  45                                  int state)
  46 {
  47     int off = state & (WORD_BITS-1);
  48     int wno = state / WORD_BITS;
  49
  50     return m[mc->n * ch + wno] & (1<<off);
  51 }
  52
  53 static MatchContext *mk_MatchContext (DFA_states *dfas, int range)
  54 {
  55     MatchContext *mc = xmalloc (sizeof(*mc));
  56     int s;
  57
  58     mc->n = (dfas->no+WORD_BITS) / WORD_BITS;
  59     mc->range = range;
  60     mc->fact = (range+1)*mc->n;
  61     mc->match_mask = xcalloc (mc->n, sizeof(*mc->match_mask));
  62
  63     for (s = 0; s<dfas->no; s++)
  64         if (dfas->sortarray[s]->rule_no)
  65             set_bit (mc, mc->match_mask, 0, s);
  66     return mc;
  67 }
  68
  69 static void rm_MatchContext (MatchContext **mc)
  70 {
  71     xfree ((*mc)->match_mask);
  72     xfree (*mc);
  73     *mc = NULL;
  74 }
  75
  76 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
  77                    DFA_states *dfas, int ch)
  78 {
  79     int j, s = 0;
  80     MatchWord *Rsrc_p = Rsrc, mask;
  81
  82     for (j = 0; j<mc->n; j++)
  83         Rdst[j] = 0;
  84     while (1)
  85     {
  86         mask = *Rsrc_p++;
  87         for (j = 0; j<WORD_BITS/4; j++)
  88         {
  89             if (mask & 15)
  90             {
  91                 if (mask & 1)
  92                 {
  93                     DFA_state *state = dfas->sortarray[s];
  94                     int i = state->tran_no;
  95                     while (--i >= 0)
  96                         if (ch >= state->trans[i].ch[0] &&
  97                             ch <= state->trans[i].ch[1])
  98                             set_bit (mc, Rdst, 0, state->trans[i].to);
  99                 }
 100                 if (mask & 2)
 101                 {
 102                     DFA_state *state = dfas->sortarray[s+1];
 103                     int i = state->tran_no;
 104                     while (--i >= 0)
 105                         if (ch >= state->trans[i].ch[0] &&
 106                             ch <= state->trans[i].ch[1])
 107                             set_bit (mc, Rdst, 0, state->trans[i].to);
 108                 }
 109                 if (mask & 4)
 110                 {
 111                     DFA_state *state = dfas->sortarray[s+2];
 112                     int i = state->tran_no;
 113                     while (--i >= 0)
 114                         if (ch >= state->trans[i].ch[0] &&
 115                             ch <= state->trans[i].ch[1])
 116                             set_bit (mc, Rdst, 0, state->trans[i].to);
 117                 }
 118                 if (mask & 8)
 119                 {
 120                     DFA_state *state = dfas->sortarray[s+3];
 121                     int i = state->tran_no;
 122                     while (--i >= 0)
 123                         if (ch >= state->trans[i].ch[0] &&
 124                             ch <= state->trans[i].ch[1])
 125                             set_bit (mc, Rdst, 0, state->trans[i].to);
 126                 }
 127             }
 128             s += 4;
 129             if (s >= dfas->no)
 130                 return;
 131             mask >>= 4;
 132         }
 133     }
 134 }
 135
 136 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 137                    DFA_states *dfas)
 138 {
 139     int j, s = 0;
 140     MatchWord *Rsrc_p = Rsrc, mask;
 141     for (j = 0; j<mc->n; j++)
 142         Rdst[j] = 0;
 143     while (1)
 144     {
 145         mask = *Rsrc_p++;
 146         for (j = 0; j<WORD_BITS/4; j++)
 147         {
 148             if (mask & 15)
 149             {
 150                 if (mask & 1)
 151                 {
 152                     DFA_state *state = dfas->sortarray[s];
 153                     int i = state->tran_no;
 154                     while (--i >= 0)
 155                         set_bit (mc, Rdst, 0, state->trans[i].to);
 156                 }
 157                 if (mask & 2)
 158                 {
 159                     DFA_state *state = dfas->sortarray[s+1];
 160                     int i = state->tran_no;
 161                     while (--i >= 0)
 162                         set_bit (mc, Rdst, 0, state->trans[i].to);
 163                 }
 164                 if (mask & 4)
 165                 {
 166                     DFA_state *state = dfas->sortarray[s+2];
 167                     int i = state->tran_no;
 168                     while (--i >= 0)
 169                         set_bit (mc, Rdst, 0, state->trans[i].to);
 170                 }
 171                 if (mask & 8)
 172                 {
 173                     DFA_state *state = dfas->sortarray[s+3];
 174                     int i = state->tran_no;
 175                     while (--i >= 0)
 176                         set_bit (mc, Rdst, 0, state->trans[i].to);
 177                 }
 178             }
 179             s += 4;
 180             if (s >= dfas->no)
 181                 return;
 182             mask >>= 4;
 183         }
 184     }
 185 }
 186
 187 static void or (MatchContext *mc, MatchWord *Rdst,
 188                 MatchWord *Rsrc1, MatchWord *Rsrc2)
 189 {
 190     int i;
 191     for (i = 0; i<mc->n; i++)
 192         Rdst[i] = Rsrc1[i] | Rsrc2[i];
 193 }
 194
 195 static INLINE int move (MatchContext *mc, MatchWord *Rj1, MatchWord *Rj,
 196                  Dict_char ch, DFA_states *dfas, MatchWord *Rtmp)
 197 {
 198     int d;
 199     MatchWord *Rtmp_2 = Rtmp + mc->n;
 200
 201     mask_shift (mc, Rj1, Rj, dfas, ch);
 202     for (d = 1; d <= mc->range; d++)
 203     {
 204         or (mc, Rtmp, Rj, Rj1);                         /* 2,3 */
 205
 206         shift (mc, Rtmp_2, Rtmp, dfas);
 207
 208         mask_shift (mc, Rtmp, Rj+mc->n, dfas, ch);      /* 1 */
 209
 210         or (mc, Rtmp, Rtmp_2, Rtmp);                    /* 1,2,3*/
 211
 212         Rj1 += mc->n;
 213
 214         or (mc, Rj1, Rtmp, Rj);                         /* 1,2,3,4 */
 215
 216         Rj += mc->n;
 217     }
 218     return 1;
 219
 220 }
 221
 222
 223 static int dict_grep (Dict dict, Dict_ptr ptr, MatchContext *mc,
 224                       MatchWord *Rj, int pos,
 225                       int (*userfunc)(Dict_char *name, char *info),
 226                       Dict_char *prefix, DFA_states *dfas)
 227 {
 228     int lo, hi, d;
 229     void *p;
 230     short *indxp;
 231     char *info;
 232
 233     dict_bf_readp (dict->dbf, ptr, &p);
 234     lo = 0;
 235     hi = DICT_nodir(p)-1;
 236     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 237
 238     while (lo <= hi)
 239     {
 240         if (indxp[-lo] > 0)
 241         {
 242             /* string (Dict_char *) DICT_EOS terminated */
 243             /* unsigned char        length of information */
 244             /* char *               information */
 245             int j;
 246             int was_match = 0;
 247             info = (char*)p + indxp[-lo];
 248             for (j=0; ; j++)
 249             {
 250                 Dict_char ch;
 251                 MatchWord *Rj0 =    Rj + j    *mc->fact;
 252                 MatchWord *Rj1 =    Rj + (j+1)*mc->fact;
 253                 MatchWord *Rj_tmp = Rj + (j+2)*mc->fact;
 254
 255                 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
 256                 prefix[pos+j] = ch;
 257                 if (ch == DICT_EOS)
 258                 {
 259                     if (was_match)
 260                         (*userfunc)(prefix, info+(j+1)*sizeof(Dict_char));
 261                     break;
 262                 }
 263                 move (mc, Rj1, Rj0, ch, dfas, Rj_tmp);
 264                 for (d = mc->n; --d >= 0; )
 265                     if (Rj1[mc->range*mc->n + d])
 266                         break;
 267                 if (d < 0)
 268                     break;
 269                 was_match = 0;
 270                 for (d = mc->n; --d >= 0; )
 271                     if (Rj1[mc->range*mc->n + d] & mc->match_mask[d])
 272                     {
 273                         was_match = 1;
 274                         break;
 275                     }
 276             }
 277         }
 278         else
 279         {
 280             MatchWord *Rj1 =    Rj+  mc->fact;
 281             MatchWord *Rj_tmp = Rj+2*mc->fact;
 282             Dict_char ch;
 283
 284             /* Dict_ptr             subptr */
 285             /* Dict_char            sub char */
 286             /* unsigned char        length of information */
 287             /* char *               information */
 288             info = (char*)p - indxp[-lo];
 289             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
 290             prefix[pos] = ch;
 291
 292             move (mc, Rj1, Rj, ch, dfas, Rj_tmp);
 293             for (d = mc->n; --d >= 0; )
 294                 if (Rj1[mc->range*mc->n + d])
 295                     break;
 296             if (d >= 0)
 297             {
 298                 Dict_ptr subptr;
 299                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 300                 {
 301                     for (d = mc->n; --d >= 0; )
 302                         if (Rj1[mc->range*mc->n + d] & mc->match_mask[d])
 303                         {
 304                             prefix[pos+1] = DICT_EOS;
 305                             (*userfunc)(prefix, info+sizeof(Dict_ptr)+
 306                                         sizeof(Dict_char));
 307                             break;
 308                         }
 309                 }
 310                 memcpy (&subptr, info, sizeof(Dict_ptr));
 311                 if (subptr)
 312                 {
 313                     dict_grep (dict, subptr, mc, Rj1, pos+1,
 314                                   userfunc, prefix, dfas);
 315                     dict_bf_readp (dict->dbf, ptr, &p);
 316                     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
 317                 }
 318             }
 319         }
 320         lo++;
 321     }
 322     return 0;
 323 }
 324
 325 int dict_lookup_grep (Dict dict, Dict_char *pattern, int range,
 326                     int (*userfunc)(Dict_char *name, char *info))
 327 {
 328     MatchWord *Rj;
 329     Dict_char prefix[MAX_LENGTH+1];
 330     char *this_pattern = pattern;
 331     DFA_states *dfas;
 332     MatchContext *mc;
 333     DFA *dfa = init_dfa();
 334     int i, d;
 335
 336     i = parse_dfa (dfa, &this_pattern, dfa_thompson_chars);
 337     if (i || *this_pattern)
 338     {
 339         rm_dfa (&dfa);
 340         return -1;
 341     }
 342     dfa->root = dfa->top;
 343     dfas = mk_dfas (dfa, 50);
 344     rm_dfa (&dfa);
 345
 346     mc = mk_MatchContext (dfas, range);
 347
 348     Rj = xcalloc ((MAX_LENGTH+1) * mc->n, sizeof(*Rj));
 349
 350     set_bit (mc, Rj, 0, 0);
 351     for (d = 1; d<=mc->range; d++)
 352     {
 353         int s;
 354         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
 355         for (s = 0; s<dfas->no; s++)
 356         {
 357             if (get_bit (mc, Rj, d-1, s))
 358             {
 359                 DFA_state *state = dfas->sortarray[s];
 360                 int i = state->tran_no;
 361                 while (--i >= 0)
 362                     set_bit (mc, Rj, d, state->trans[i].to);
 363             }
 364         }
 365     }
 366     i = dict_grep (dict, 1, mc, Rj, 0, userfunc, prefix, dfas);
 367
 368     rm_dfas (&dfas);
 369     xfree (Rj);
 370     rm_MatchContext (&mc);
 371     return i;
 372 }