dict/lookgrep.c

   1 /* $Id: lookgrep.c,v 1.26.2.2 2006-12-05 21:14:40 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   3    Index Data Aps
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 */
  22
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <stdio.h>
  26 #include <assert.h>
  27
  28 #include <yaz/xmalloc.h>
  29 #include <dfa.h>
  30 #include <dict.h>
  31
  32 typedef unsigned MatchWord;
  33 #define WORD_BITS 32
  34 #define MAX_LENGTH 1024
  35
  36 typedef struct {
  37   int n;                 /* no of MatchWord needed */
  38   int range;             /* max no. of errors */
  39   int fact;              /* (range+1)*n */
  40   MatchWord *match_mask; /* match_mask */
  41 } MatchContext;
  42
  43 #define INLINE
  44
  45 static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
  46 {
  47     int off = state & (WORD_BITS-1);
  48     int wno = state / WORD_BITS;
  49
  50     m[mc->n * ch + wno] |= 1<<off;
  51 }
  52
  53 static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
  54                                  int state)
  55 {
  56     int off = state & (WORD_BITS-1);
  57     int wno = state / WORD_BITS;
  58
  59     return m[mc->n * ch + wno] & (1<<off);
  60 }
  61
  62 static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
  63 {
  64     MatchContext *mc = (MatchContext *) xmalloc (sizeof(*mc));
  65     int s;
  66
  67     mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
  68     mc->range = range;
  69     mc->fact = (range+1)*mc->n;
  70     mc->match_mask = (MatchWord *) xcalloc (mc->n, sizeof(*mc->match_mask));
  71
  72     for (s = 0; s<dfa->no_states; s++)
  73         if (dfa->states[s]->rule_no)
  74             set_bit (mc, mc->match_mask, 0, s);
  75     return mc;
  76 }
  77
  78 static void rm_MatchContext (MatchContext **mc)
  79 {
  80     xfree ((*mc)->match_mask);
  81     xfree (*mc);
  82     *mc = NULL;
  83 }
  84
  85 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
  86                    struct DFA *dfa, int ch)
  87 {
  88     int j, s = 0;
  89     MatchWord *Rsrc_p = Rsrc, mask;
  90
  91     for (j = 0; j<mc->n; j++)
  92         Rdst[j] = 0;
  93     while (1)
  94     {
  95         mask = *Rsrc_p++;
  96         for (j = 0; j<WORD_BITS/4; j++)
  97         {
  98             if (mask & 15)
  99             {
 100                 if (mask & 1)
 101                 {
 102                     struct DFA_state *state = dfa->states[s];
 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 & 2)
 110                 {
 111                     struct DFA_state *state = dfa->states[s+1];
 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 & 4)
 119                 {
 120                     struct DFA_state *state = dfa->states[s+2];
 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                 if (mask & 8)
 128                 {
 129                     struct DFA_state *state = dfa->states[s+3];
 130                     int i = state->tran_no;
 131                     while (--i >= 0)
 132                         if (ch >= state->trans[i].ch[0] &&
 133                             ch <= state->trans[i].ch[1])
 134                             set_bit (mc, Rdst, 0, state->trans[i].to);
 135                 }
 136             }
 137             s += 4;
 138             if (s >= dfa->no_states)
 139                 return;
 140             mask >>= 4;
 141         }
 142     }
 143 }
 144
 145 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
 146                    struct DFA *dfa)
 147 {
 148     int j, s = 0;
 149     MatchWord *Rsrc_p = Rsrc, mask;
 150     for (j = 0; j<mc->n; j++)
 151         Rdst[j] = 0;
 152     while (1)
 153     {
 154         mask = *Rsrc_p++;
 155         for (j = 0; j<WORD_BITS/4; j++)
 156         {
 157             if (mask & 15)
 158             {
 159                 if (mask & 1)
 160                 {
 161                     struct DFA_state *state = dfa->states[s];
 162                     int i = state->tran_no;
 163                     while (--i >= 0)
 164                         set_bit (mc, Rdst, 0, state->trans[i].to);
 165                 }
 166                 if (mask & 2)
 167                 {
 168                     struct DFA_state *state = dfa->states[s+1];
 169                     int i = state->tran_no;
 170                     while (--i >= 0)
 171                         set_bit (mc, Rdst, 0, state->trans[i].to);
 172                 }
 173                 if (mask & 4)
 174                 {
 175                     struct DFA_state *state = dfa->states[s+2];
 176                     int i = state->tran_no;
 177                     while (--i >= 0)
 178                         set_bit (mc, Rdst, 0, state->trans[i].to);
 179                 }
 180                 if (mask & 8)
 181                 {
 182                     struct DFA_state *state = dfa->states[s+3];
 183                     int i = state->tran_no;
 184                     while (--i >= 0)
 185                         set_bit (mc, Rdst, 0, state->trans[i].to);
 186                 }
 187             }
 188             s += 4;
 189             if (s >= dfa->no_states)
 190                 return;
 191             mask >>= 4;
 192         }
 193     }
 194 }
 195
 196 static void or (MatchContext *mc, MatchWord *Rdst,
 197                 MatchWord *Rsrc1, MatchWord *Rsrc2)
 198 {
 199     int i;
 200     for (i = 0; i<mc->n; i++)
 201         Rdst[i] = Rsrc1[i] | Rsrc2[i];
 202 }
 203
 204 static INLINE int move (MatchContext *mc, MatchWord *Rj1, MatchWord *Rj,
 205                         Dict_char ch, struct DFA *dfa, MatchWord *Rtmp,
 206                         int range)
 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, void *client,
 235                       int (*userfunc)(char *, const char *, void *),
 236                       Dict_char *prefix, struct DFA *dfa,
 237                       int *max_pos, int init_pos)
 238 {
 239     int lo, hi, d;
 240     void *p;
 241     short *indxp;
 242     char *info;
 243
 244     dict_bf_readp (dict->dbf, ptr, &p);
 245     lo = 0;
 246     hi = DICT_nodir(p)-1;
 247     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 248
 249     while (lo <= hi)
 250     {
 251         if (indxp[-lo] > 0)
 252         {
 253             /* string (Dict_char *) DICT_EOS terminated */
 254             /* unsigned char        length of information */
 255             /* char *               information */
 256             int j;
 257             int was_match = 0;
 258             info = (char*)p + indxp[-lo];
 259             for (j=0; ; j++)
 260             {
 261                 Dict_char ch;
 262                 MatchWord *Rj0 =    Rj + j    *mc->fact;
 263                 MatchWord *Rj1 =    Rj + (j+1)*mc->fact;
 264                 MatchWord *Rj_tmp = Rj + (j+2)*mc->fact;
 265                 int range;
 266
 267                 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
 268                 prefix[pos+j] = ch;
 269                 if (pos+j > *max_pos)
 270                     *max_pos = pos+j;
 271                 if (ch == DICT_EOS)
 272                 {
 273                     if (was_match)
 274                         if ((*userfunc)((char*) prefix,
 275                                         info+(j+1)*sizeof(Dict_char), client))
 276                             return 1;
 277                     break;
 278                 }
 279                 if (pos+j >= init_pos)
 280                     range = mc->range;
 281                 else
 282                     range = 0;
 283                 move (mc, Rj1, Rj0, ch, dfa, Rj_tmp, range);
 284                 for (d = mc->n; --d >= 0; )
 285                     if (Rj1[range*mc->n + d])
 286                         break;
 287                 if (d < 0)
 288                     break;
 289                 was_match = 0;
 290                 for (d = mc->n; --d >= 0; )
 291                     if (Rj1[range*mc->n + d] & mc->match_mask[d])
 292                     {
 293                         was_match = 1;
 294                         break;
 295                     }
 296             }
 297         }
 298         else
 299         {
 300             MatchWord *Rj1 =    Rj+  mc->fact;
 301             MatchWord *Rj_tmp = Rj+2*mc->fact;
 302             Dict_char ch;
 303             int range;
 304
 305             /* Dict_ptr             subptr */
 306             /* Dict_char            sub char */
 307             /* unsigned char        length of information */
 308             /* char *               information */
 309             info = (char*)p - indxp[-lo];
 310             memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
 311             prefix[pos] = ch;
 312
 313             if (pos > *max_pos)
 314                 *max_pos = pos;
 315             if (pos >= init_pos)
 316                 range = mc->range;
 317             else
 318                 range = 0;
 319             move (mc, Rj1, Rj, ch, dfa, Rj_tmp, range);
 320             for (d = mc->n; --d >= 0; )
 321                 if (Rj1[range*mc->n + d])
 322                     break;
 323             if (d >= 0)
 324             {
 325                 Dict_ptr subptr;
 326                 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 327                 {
 328                     for (d = mc->n; --d >= 0; )
 329                         if (Rj1[range*mc->n + d] & mc->match_mask[d])
 330                         {
 331                             prefix[pos+1] = DICT_EOS;
 332                             if ((*userfunc)((char*) prefix,
 333                                             info+sizeof(Dict_ptr)+
 334                                             sizeof(Dict_char), client))
 335                                 return 1;
 336                             break;
 337                         }
 338                 }
 339                 memcpy (&subptr, info, sizeof(Dict_ptr));
 340                 if (subptr)
 341                 {
 342                     if (dict_grep (dict, subptr, mc, Rj1, pos+1,
 343                                    client, userfunc, prefix, dfa, max_pos,
 344                                    init_pos))
 345                         return 1;
 346                     dict_bf_readp (dict->dbf, ptr, &p);
 347                     indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
 348                 }
 349             }
 350         }
 351         lo++;
 352     }
 353     return 0;
 354 }
 355
 356 int dict_lookup_grep (Dict dict, const char *pattern, int range, void *client,
 357                       int *max_pos, int init_pos,
 358                       int (*userfunc)(char *name, const char *info,
 359                                       void *client))
 360 {
 361     MatchWord *Rj;
 362     Dict_char prefix[MAX_LENGTH+1];
 363     const char *this_pattern = pattern;
 364     MatchContext *mc;
 365     struct DFA *dfa = dfa_init();
 366     int i, d;
 367
 368 #if 0
 369     debug_dfa_trav = 1;
 370     debug_dfa_tran = 1;
 371     debug_dfa_followpos = 1;
 372     dfa_verbose = 1;
 373 #endif
 374
 375     yaz_log(YLOG_DEBUG, "dict_lookup_grep range=%d", range);
 376     for (i = 0; pattern[i]; i++)
 377     {
 378         yaz_log(YLOG_DEBUG, " %3d  %c", pattern[i],
 379               (pattern[i] > ' ' && pattern[i] < 127) ? pattern[i] : '?');
 380     }
 381
 382     dfa_set_cmap (dfa, dict->grep_cmap_data, dict->grep_cmap);
 383
 384     i = dfa_parse (dfa, &this_pattern);
 385     if (i || *this_pattern)
 386     {
 387         yaz_log(YLOG_WARN, "dfa_parse fail=%d", i);
 388         dfa_delete (&dfa);
 389         return -1;
 390     }
 391     dfa_mkstate (dfa);
 392
 393     mc = mk_MatchContext (dfa, range);
 394
 395     Rj = (MatchWord *) xcalloc ((MAX_LENGTH+1) * mc->n, sizeof(*Rj));
 396
 397     set_bit (mc, Rj, 0, 0);
 398     for (d = 1; d<=mc->range; d++)
 399     {
 400         int s;
 401         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
 402         for (s = 0; s<dfa->no_states; s++)
 403         {
 404             if (get_bit (mc, Rj, d-1, s))
 405             {
 406                 struct DFA_state *state = dfa->states[s];
 407                 int i = state->tran_no;
 408                 while (--i >= 0)
 409                     set_bit (mc, Rj, d, state->trans[i].to);
 410             }
 411         }
 412     }
 413     *max_pos = 0;
 414     if (dict->head.root)
 415         i = dict_grep (dict, dict->head.root, mc, Rj, 0, client,
 416                        userfunc, prefix,
 417                        dfa, max_pos, init_pos);
 418     else
 419         i = 0;
 420     yaz_log(YLOG_DEBUG, "max_pos = %d", *max_pos);
 421     dfa_delete (&dfa);
 422     xfree (Rj);
 423     rm_MatchContext (&mc);
 424     return i;
 425 }
 426
 427 void dict_grep_cmap (Dict dict, void *vp,
 428                      const char **(*cmap)(void *vp, const char **from, int len))
 429 {
 430     dict->grep_cmap = cmap;
 431     dict->grep_cmap_data = vp;
 432 }