IDZEBRA  2.1.2
lookgrep.c
Go to the documentation of this file.
1 /* This file is part of the Zebra server.
2  Copyright (C) Index Data
3 
4  Zebra is free software; you can redistribute it and/or modify it under
5  the terms of the GNU General Public License as published by the Free
6  Software Foundation; either version 2, or (at your option) any later
7  version.
8 
9  Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
10  WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12  for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with this program; if not, write to the Free Software
16  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 
18 */
19 
20 
21 
22 #if HAVE_CONFIG_H
23 #include <config.h>
24 #endif
25 #include <stdlib.h>
26 #include <string.h>
27 #include <stdio.h>
28 #include <assert.h>
29 
30 #include <dfa.h>
31 #include "dict-p.h"
32 
33 typedef unsigned MatchWord;
34 #define WORD_BITS 32
35 #define MAX_LENGTH 1024
36 
37 /* This code is based
38  * Sun Wu and Udi Manber: Fast Text Searching Allowing Errors.
39  * Communications of the ACM, pp. 83-91, Vol. 35, No. 10, Oct. 1992, USA.
40  * PostScript version of the paper in its submitted form: agrep1.ps)
41  * recommended reading to understand AGREP !
42  *
43  * http://www.tgries.de/agrep/#AGREP1PS
44  * http://www.tgries.de/agrep/doc/agrep1ps.zip
45  */
46 
47 typedef struct {
48  int n; /* no of MatchWord needed */
49  int range; /* max no. of errors */
50  int fact; /* (range+1)*n */
51  MatchWord *match_mask; /* match_mask */
52 } MatchContext;
53 
54 #define INLINE
55 
56 static INLINE void set_bit(MatchContext *mc, MatchWord *m, int ch, int state)
57 {
58  int off = state & (WORD_BITS-1);
59  int wno = state / WORD_BITS;
60 
61  m[mc->n * ch + wno] |= 1<<off;
62 }
63 
65  int state)
66 {
67  int off = state & (WORD_BITS-1);
68  int wno = state / WORD_BITS;
69 
70  return m[mc->n * ch + wno] & (1<<off);
71 }
72 
73 static MatchContext *mk_MatchContext(struct DFA *dfa, int range)
74 {
75  MatchContext *mc = (MatchContext *) xmalloc(sizeof(*mc));
76  int s;
77 
78  mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
79  mc->range = range;
80  mc->fact = (range+1)*mc->n;
81  mc->match_mask = (MatchWord *) xcalloc(mc->n, sizeof(*mc->match_mask));
82 
83  for (s = 0; s<dfa->no_states; s++)
84  if (dfa->states[s]->rule_no)
85  set_bit(mc, mc->match_mask, 0, s);
86  return mc;
87 }
88 
89 static void rm_MatchContext(MatchContext **mc)
90 {
91  xfree((*mc)->match_mask);
92  xfree(*mc);
93  *mc = NULL;
94 }
95 
96 static void mask_shift(MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
97  struct DFA *dfa, int ch)
98 {
99  int j, s = 0;
100  MatchWord *Rsrc_p = Rsrc, mask;
101 
102  for (j = 0; j<mc->n; j++)
103  Rdst[j] = 0;
104  while (1)
105  {
106  mask = *Rsrc_p++;
107  for (j = 0; j<WORD_BITS/4; j++)
108  {
109  if (mask & 15)
110  {
111  if (mask & 1)
112  {
113  struct DFA_state *state = dfa->states[s];
114  int i = state->tran_no;
115  while (--i >= 0)
116  if (ch >= state->trans[i].ch[0] &&
117  ch <= state->trans[i].ch[1])
118  set_bit(mc, Rdst, 0, state->trans[i].to);
119  }
120  if (mask & 2)
121  {
122  struct DFA_state *state = dfa->states[s+1];
123  int i = state->tran_no;
124  while (--i >= 0)
125  if (ch >= state->trans[i].ch[0] &&
126  ch <= state->trans[i].ch[1])
127  set_bit(mc, Rdst, 0, state->trans[i].to);
128  }
129  if (mask & 4)
130  {
131  struct DFA_state *state = dfa->states[s+2];
132  int i = state->tran_no;
133  while (--i >= 0)
134  if (ch >= state->trans[i].ch[0] &&
135  ch <= state->trans[i].ch[1])
136  set_bit(mc, Rdst, 0, state->trans[i].to);
137  }
138  if (mask & 8)
139  {
140  struct DFA_state *state = dfa->states[s+3];
141  int i = state->tran_no;
142  while (--i >= 0)
143  if (ch >= state->trans[i].ch[0] &&
144  ch <= state->trans[i].ch[1])
145  set_bit(mc, Rdst, 0, state->trans[i].to);
146  }
147  }
148  s += 4;
149  if (s >= dfa->no_states)
150  return;
151  mask >>= 4;
152  }
153  }
154 }
155 
156 static void shift(MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
157  struct DFA *dfa)
158 {
159  int j, s = 0;
160  MatchWord *Rsrc_p = Rsrc, mask;
161  for (j = 0; j<mc->n; j++)
162  Rdst[j] = 0;
163  while (1)
164  {
165  mask = *Rsrc_p++;
166  for (j = 0; j<WORD_BITS/4; j++)
167  {
168  if (mask & 15)
169  {
170  if (mask & 1)
171  {
172  struct DFA_state *state = dfa->states[s];
173  int i = state->tran_no;
174  while (--i >= 0)
175  set_bit(mc, Rdst, 0, state->trans[i].to);
176  }
177  if (mask & 2)
178  {
179  struct DFA_state *state = dfa->states[s+1];
180  int i = state->tran_no;
181  while (--i >= 0)
182  set_bit(mc, Rdst, 0, state->trans[i].to);
183  }
184  if (mask & 4)
185  {
186  struct DFA_state *state = dfa->states[s+2];
187  int i = state->tran_no;
188  while (--i >= 0)
189  set_bit(mc, Rdst, 0, state->trans[i].to);
190  }
191  if (mask & 8)
192  {
193  struct DFA_state *state = dfa->states[s+3];
194  int i = state->tran_no;
195  while (--i >= 0)
196  set_bit(mc, Rdst, 0, state->trans[i].to);
197  }
198  }
199  s += 4;
200  if (s >= dfa->no_states)
201  return;
202  mask >>= 4;
203  }
204  }
205 }
206 
207 static void or(MatchContext *mc, MatchWord *Rdst,
208  MatchWord *Rsrc1, MatchWord *Rsrc2)
209 {
210  int i;
211  for (i = 0; i<mc->n; i++)
212  Rdst[i] = Rsrc1[i] | Rsrc2[i];
213 }
214 
215 static INLINE int move(MatchContext *mc, MatchWord *Rj1, MatchWord *Rj,
216  Dict_char ch, struct DFA *dfa, MatchWord *Rtmp,
217  int range)
218 {
219  int d;
220  MatchWord *Rtmp_2 = Rtmp + mc->n;
221 
222  mask_shift(mc, Rj1, Rj, dfa, ch);
223  for (d = 1; d <= mc->range; d++)
224  {
225  or(mc, Rtmp, Rj, Rj1); /* 2,3 */
226 
227  shift(mc, Rtmp_2, Rtmp, dfa);
228 
229  mask_shift(mc, Rtmp, Rj+mc->n, dfa, ch); /* 1 */
230 
231  or(mc, Rtmp, Rtmp_2, Rtmp); /* 1,2,3*/
232 
233  Rj1 += mc->n;
234 
235  or(mc, Rj1, Rtmp, Rj); /* 1,2,3,4 */
236 
237  Rj += mc->n;
238  }
239  return 1;
240 
241 }
242 
243 
244 static int grep(Dict dict, Dict_ptr ptr, MatchContext *mc,
245  MatchWord *Rj, int pos, void *client,
246  int (*userfunc)(char *, const char *, void *),
247  Dict_char *prefix, struct DFA *dfa,
248  int *max_pos, int init_pos)
249 {
250  int lo, hi, d;
251  void *p;
252  short *indxp;
253  char *info;
254 
255  dict_bf_readp(dict->dbf, ptr, &p);
256  lo = 0;
257  hi = DICT_nodir(p)-1;
258  indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
259 
260  while (lo <= hi)
261  {
262  if (indxp[-lo] > 0)
263  {
264  /* string (Dict_char *) DICT_EOS terminated */
265  /* unsigned char length of information */
266  /* char * information */
267  int j;
268  int was_match = 0;
269  info = (char*)p + indxp[-lo];
270  for (j=0; ; j++)
271  {
272  Dict_char ch;
273  MatchWord *Rj0 = Rj + j *mc->fact;
274  MatchWord *Rj1 = Rj + (j+1)*mc->fact;
275  MatchWord *Rj_tmp = Rj + (j+2)*mc->fact;
276  int range;
277 
278  memcpy(&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
279  prefix[pos+j] = ch;
280  if (pos+j > *max_pos)
281  *max_pos = pos+j;
282  if (ch == DICT_EOS)
283  {
284  if (was_match)
285  {
286  int ret = userfunc((char*) prefix,
287  info+(j+1)*sizeof(Dict_char), client);
288  if (ret)
289  return ret;
290  }
291  break;
292  }
293  if (pos+j >= init_pos)
294  range = mc->range;
295  else
296  range = 0;
297  move(mc, Rj1, Rj0, ch, dfa, Rj_tmp, range);
298  for (d = mc->n; --d >= 0; )
299  if (Rj1[range*mc->n + d])
300  break;
301  if (d < 0)
302  break;
303  was_match = 0;
304  for (d = mc->n; --d >= 0; )
305  if (Rj1[range*mc->n + d] & mc->match_mask[d])
306  {
307  was_match = 1;
308  break;
309  }
310  }
311  }
312  else
313  {
314  MatchWord *Rj1 = Rj+ mc->fact;
315  MatchWord *Rj_tmp = Rj+2*mc->fact;
316  Dict_char ch;
317  int range;
318 
319  /* Dict_ptr subptr */
320  /* Dict_char sub char */
321  /* unsigned char length of information */
322  /* char * information */
323  info = (char*)p - indxp[-lo];
324  memcpy(&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
325  prefix[pos] = ch;
326 
327  if (pos > *max_pos)
328  *max_pos = pos;
329  if (pos >= init_pos)
330  range = mc->range;
331  else
332  range = 0;
333  move(mc, Rj1, Rj, ch, dfa, Rj_tmp, range);
334  for (d = mc->n; --d >= 0; )
335  if (Rj1[range*mc->n + d])
336  break;
337  if (d >= 0)
338  {
339  Dict_ptr subptr;
340  if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
341  {
342  for (d = mc->n; --d >= 0; )
343  if (Rj1[range*mc->n + d] & mc->match_mask[d])
344  {
345  int ret;
346  prefix[pos+1] = DICT_EOS;
347  ret = userfunc((char*) prefix,
348  info+sizeof(Dict_ptr)+
349  sizeof(Dict_char), client);
350  if (ret)
351  return ret;
352  break;
353  }
354  }
355  memcpy(&subptr, info, sizeof(Dict_ptr));
356  if (subptr)
357  {
358  int ret = grep(dict, subptr, mc, Rj1, pos+1,
359  client, userfunc, prefix, dfa, max_pos,
360  init_pos);
361  if (ret)
362  return ret;
363 
364  dict_bf_readp(dict->dbf, ptr, &p);
365  indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
366  }
367  }
368  }
369  lo++;
370  }
371  return 0;
372 }
373 
374 int dict_lookup_grep(Dict dict, const char *pattern, int range, void *client,
375  int *max_pos, int init_pos,
376  int (*userfunc)(char *name, const char *info,
377  void *client))
378 {
379  MatchWord *Rj;
380  Dict_char prefix[MAX_LENGTH+1];
381  const char *this_pattern = pattern;
382  MatchContext *mc;
383  struct DFA *dfa = dfa_init();
384  int i, d, ret = 0;
385 
386 #if 0
387  debug_dfa_trav = 1;
388  debug_dfa_tran = 1;
390  dfa_verbose = 1;
391 #endif
392 
394 
395  yaz_log(YLOG_DEBUG, "dict_lookup_grep range=%d", range);
396  for (i = 0; pattern[i]; i++)
397  {
398  yaz_log(YLOG_DEBUG, " %2d %3d %c", i, pattern[i],
399  (pattern[i] > ' ' && pattern[i] < 127) ? pattern[i] : '?');
400  }
401 
402  dfa_set_cmap(dfa, dict->grep_cmap_data, dict->grep_cmap);
403 
404  i = dfa_parse(dfa, &this_pattern);
405  if (i || *this_pattern)
406  {
407  yaz_log(YLOG_WARN, "dfa_parse fail=%d", i);
408  dfa_delete(&dfa);
409  return -1;
410  }
411  dfa_mkstate(dfa);
412 
413  mc = mk_MatchContext(dfa, range);
414 
415  Rj = (MatchWord *) xcalloc((MAX_LENGTH+2) * mc->fact, sizeof(*Rj));
416 
417  set_bit (mc, Rj, 0, 0);
418  for (d = 1; d<=mc->range; d++)
419  {
420  int s;
421  memcpy(Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
422  for (s = 0; s < dfa->no_states; s++)
423  {
424  if (get_bit(mc, Rj, d-1, s))
425  {
426  struct DFA_state *state = dfa->states[s];
427  int i = state->tran_no;
428  while (--i >= 0)
429  set_bit(mc, Rj, d, state->trans[i].to);
430  }
431  }
432  }
433  *max_pos = 0;
434  if (dict->head.root)
435  ret = grep(dict, dict->head.root, mc, Rj, 0, client,
436  userfunc, prefix,
437  dfa, max_pos, init_pos);
438  yaz_log(YLOG_DEBUG, "max_pos = %d", *max_pos);
439  dfa_delete(&dfa);
440  xfree(Rj);
441  rm_MatchContext(&mc);
442  return ret;
443 }
444 
445 void dict_grep_cmap(Dict dict, void *vp,
446  const char **(*cmap)(void *vp, const char **from, int len))
447 {
448  dict->grep_cmap = cmap;
449  dict->grep_cmap_data = vp;
450 }
451 /*
452  * Local variables:
453  * c-basic-offset: 4
454  * c-file-style: "Stroustrup"
455  * indent-tabs-mode: nil
456  * End:
457  * vim: shiftwidth=4 tabstop=8 expandtab
458  */
459 
void dfa_set_cmap(struct DFA *dfa, void *vp, const char **(*cmap)(void *vp, const char **from, int len))
Definition: dfa.c:1107
unsigned short to
Definition: dfa.h:32
struct DFA * dfa_init(void)
Definition: dfa.c:1090
void dfa_mkstate(struct DFA *)
Definition: dfa.c:1146
void dfa_anyset_includes_nl(struct DFA *dfa)
Definition: dfa.c:1102
struct Dict_head head
Definition: dict-p.h:83
static INLINE void set_bit(MatchContext *mc, MatchWord *m, int ch, int state)
Definition: lookgrep.c:56
static int grep(Dict dict, Dict_ptr ptr, MatchContext *mc, MatchWord *Rj, int pos, void *client, int(*userfunc)(char *, const char *, void *), Dict_char *prefix, struct DFA *dfa, int *max_pos, int init_pos)
Definition: lookgrep.c:244
#define DICT_bsize(x)
Definition: dict-p.h:105
#define DICT_EOS
Definition: dict-p.h:102
void * grep_cmap_data
Definition: dict-p.h:76
struct DFA_state ** states
Definition: dfa.h:55
int no_states
Definition: dfa.h:54
unsigned char ch[2]
Definition: dfa.h:31
static MatchContext * mk_MatchContext(struct DFA *dfa, int range)
Definition: lookgrep.c:73
static INLINE int move(MatchContext *mc, MatchWord *Rj1, MatchWord *Rj, Dict_char ch, struct DFA *dfa, MatchWord *Rtmp, int range)
Definition: lookgrep.c:215
void dict_grep_cmap(Dict dict, void *vp, const char **(*cmap)(void *vp, const char **from, int len))
install character mapping handler for dict_lookup_grep
Definition: lookgrep.c:445
int range
Definition: grepper.c:43
struct DFA_tran * trans
Definition: dfa.h:45
void dfa_delete(struct DFA **)
Definition: dfa.c:1156
static Dict dict
Definition: dicttest.c:34
#define INLINE
Definition: lookgrep.c:54
static void mask_shift(MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc, struct DFA *dfa, int ch)
Definition: lookgrep.c:96
unsigned Dict_ptr
Definition: dict-p.h:34
Dict_BFile dbf
Definition: dict-p.h:74
#define WORD_BITS
Definition: lookgrep.c:34
int dfa_verbose
Definition: dfa.c:67
int debug_dfa_followpos
Definition: dfa.c:66
static void rm_MatchContext(MatchContext **mc)
Definition: lookgrep.c:89
int dict_lookup_grep(Dict dict, const char *pattern, int range, void *client, int *max_pos, int init_pos, int(*userfunc)(char *name, const char *info, void *client))
regular expression search with error correction
Definition: lookgrep.c:374
static void init_pos(struct DFA_parse *parse_info)
Definition: dfa.c:625
unsigned MatchWord
Definition: grepper.c:38
const char **(* grep_cmap)(void *vp, const char **from, int len)
Definition: dict-p.h:75
int dict_bf_readp(Dict_BFile bf, int no, void **bufp)
Definition: drdwr.c:188
#define DICT_nodir(x)
Definition: dict-p.h:106
unsigned MatchWord
Definition: lookgrep.c:33
Definition: dfa.h:42
int dfa_parse(struct DFA *, const char **)
Definition: dfa.c:1119
short tran_no
Definition: dfa.h:48
int debug_dfa_tran
Definition: dfa.c:65
int debug_dfa_trav
Definition: dfa.c:64
Dict_ptr root
Definition: dict-p.h:40
static INLINE MatchWord get_bit(MatchContext *mc, MatchWord *m, int ch, int state)
Definition: lookgrep.c:64
short rule_no
Definition: dfa.h:49
MatchWord * match_mask
Definition: lookgrep.c:51
#define MAX_LENGTH
Definition: lookgrep.c:35
Definition: dfa.h:53
static void or(MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc1, MatchWord *Rsrc2)
Definition: lookgrep.c:207
unsigned char Dict_char
Definition: dict-p.h:33
static void shift(MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc, struct DFA *dfa)
Definition: lookgrep.c:156