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