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