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.5  1995-09-14 11:52:59  adam
   8  * Grep handle function parameter info is const now.
   9  *
  10  * Revision 1.4  1995/01/24  16:01:02  adam
  11  * Added -ansi to CFLAGS.
  12  * Use new API of dfa module.
  13  *
  14  * Revision 1.3  1994/10/05  12:16:50  adam
  15  * Pagesize is a resource now.
  16  *
  17  * Revision 1.2  1994/10/04  12:08:07  adam
  18  * Some bug fixes and some optimizations.
  19  *
  20  * Revision 1.1  1994/10/03  17:23:04  adam
  21  * First version of dictionary lookup with regular expressions and errors.
  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 = 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 = 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 {
 208     int d;
 209     MatchWord *Rtmp_2 = Rtmp + mc->n;
 210
 211     mask_shift (mc, Rj1, Rj, dfa, ch);
 212     for (d = 1; d <= mc->range; d++)
 213     {
 214         or (mc, Rtmp, Rj, Rj1);                         /* 2,3 */
 215
 216         shift (mc, Rtmp_2, Rtmp, dfa);
 217
 218         mask_shift (mc, Rtmp, Rj+mc->n, dfa, ch);      /* 1 */
 219
 220         or (mc, Rtmp, Rtmp_2, Rtmp);                    /* 1,2,3*/
 221
 222         Rj1 += mc->n;
 223
 224         or (mc, Rj1, Rtmp, Rj);                         /* 1,2,3,4 */
 225
 226         Rj += mc->n;
 227     }
 228     return 1;
 229
 230 }
 231
 232
 233 static int dict_grep (Dict dict, Dict_ptr ptr, MatchContext *mc,
 234                       MatchWord *Rj, int pos,
 235                       int (*userfunc)(Dict_char *name, const char *info),
 236                       Dict_char *prefix, struct DFA *dfa)
 237 {
 238     int lo, hi, d;
 239     void *p;
 240     short *indxp;
 241     char *info;
 242
 243     dict_bf_readp (dict->dbf, ptr, &p);
 244     lo = 0;
 245     hi = DICT_nodir(p)-1;
 246     indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
 247
 248     while (lo <= hi)
 249     {
 250         if (indxp[-lo] > 0)
 251         {
 252             /* string (Dict_char *) DICT_EOS terminated */
 253             /* unsigned char        length of information */
 254             /* char *               information */
 255             int j;
 256             int was_match = 0;
 257             info = (char*)p + indxp[-lo];
 258             for (j=0; ; j++)
 259             {
 260                 Dict_char ch;
 261                 MatchWord *Rj0 =    Rj + j    *mc->fact;
 262                 MatchWord *Rj1 =    Rj + (j+1)*mc->fact;
 263                 MatchWord *Rj_tmp = Rj + (j+2)*mc->fact;
 264
 265                 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
 266                 prefix[pos+j] = ch;
 267                 if (ch == DICT_EOS)
 268                 {
 269                     if (was_match)
 270                         (*userfunc)(prefix, info+(j+1)*sizeof(Dict_char));
 271                     break;
 272                 }
 273                 move (mc, Rj1, Rj0, ch, dfa, Rj_tmp);
 274                 for (d = mc->n; --d >= 0; )
 275                     if (Rj1[mc->range*mc->n + d])
 276                         break;
 277                 if (d < 0)
 278                     break;
 279                 was_match = 0;
 280                 for (d = mc->n; --d >= 0; )
 281                     if (Rj1[mc->range*mc->n + d] & mc->match_mask[d])
 282                     {
 283                         was_match = 1;
 284                         break;
 285                     }
 286             }
 287         }
 288         else
 289         {
 290             MatchWord *Rj1 =    Rj+  mc->fact;
 291             MatchWord *Rj_tmp = Rj+2*mc->fact;
 292             Dict_char ch;
 293
 294             /* Dict_ptr             subptr */
 295             /* Dict_char            sub char */
 296             /* unsigned char        length of information */
 297             /* char *               information */
 298             info = (char*)p - indxp[-lo];
 299             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
 300             prefix[pos] = ch;
 301
 302             move (mc, Rj1, Rj, ch, dfa, Rj_tmp);
 303             for (d = mc->n; --d >= 0; )
 304                 if (Rj1[mc->range*mc->n + d])
 305                     break;
 306             if (d >= 0)
 307             {
 308                 Dict_ptr subptr;
 309                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 310                 {
 311                     for (d = mc->n; --d >= 0; )
 312                         if (Rj1[mc->range*mc->n + d] & mc->match_mask[d])
 313                         {
 314                             prefix[pos+1] = DICT_EOS;
 315                             (*userfunc)(prefix, info+sizeof(Dict_ptr)+
 316                                         sizeof(Dict_char));
 317                             break;
 318                         }
 319                 }
 320                 memcpy (&subptr, info, sizeof(Dict_ptr));
 321                 if (subptr)
 322                 {
 323                     dict_grep (dict, subptr, mc, Rj1, pos+1,
 324                                   userfunc, prefix, dfa);
 325                     dict_bf_readp (dict->dbf, ptr, &p);
 326                     indxp = (short*) ((char*) p+DICT_pagesize(dict)
 327                                       -sizeof(short));
 328                 }
 329             }
 330         }
 331         lo++;
 332     }
 333     return 0;
 334 }
 335
 336 int dict_lookup_grep (Dict dict, Dict_char *pattern, int range,
 337                     int (*userfunc)(Dict_char *name, const char *info))
 338 {
 339     MatchWord *Rj;
 340     Dict_char prefix[MAX_LENGTH+1];
 341     char *this_pattern = pattern;
 342     MatchContext *mc;
 343     struct DFA *dfa = dfa_init();
 344     int i, d;
 345
 346     i = dfa_parse (dfa, &this_pattern);
 347     if (i || *this_pattern)
 348     {
 349         dfa_delete (&dfa);
 350         return -1;
 351     }
 352     dfa_mkstate (dfa);
 353
 354     mc = mk_MatchContext (dfa, range);
 355
 356     Rj = xcalloc ((MAX_LENGTH+1) * mc->n, sizeof(*Rj));
 357
 358     set_bit (mc, Rj, 0, 0);
 359     for (d = 1; d<=mc->range; d++)
 360     {
 361         int s;
 362         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
 363         for (s = 0; s<dfa->no_states; s++)
 364         {
 365             if (get_bit (mc, Rj, d-1, s))
 366             {
 367                 struct DFA_state *state = dfa->states[s];
 368                 int i = state->tran_no;
 369                 while (--i >= 0)
 370                     set_bit (mc, Rj, d, state->trans[i].to);
 371             }
 372         }
 373     }
 374     i = dict_grep (dict, 1, mc, Rj, 0, userfunc, prefix, dfa);
 375
 376     dfa_delete (&dfa);
 377     xfree (Rj);
 378     rm_MatchContext (&mc);
 379     return i;
 380 }