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