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