2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.5 1995-01-24 16:01:03 adam
8 * Added -ansi to CFLAGS.
9 * Use new API of dfa module.
11 * Revision 1.4 1994/10/05 12:16:51 adam
12 * Pagesize is a resource now.
14 * Revision 1.3 1994/09/26 16:31:06 adam
17 * Revision 1.2 1994/09/22 14:43:57 adam
18 * First functional version of lookup with error correction. A 'range'
19 * specified the maximum number of insertions+deletions+substitutions.
21 * Revision 1.1 1994/09/22 10:43:44 adam
22 * Two versions of depend. Type 1 is the tail-type compatible with
23 * all make programs. Type 2 is the GNU make with include facility.
24 * Type 2 is default. depend rule chooses current rule.
34 typedef unsigned MatchWord;
41 #define SH(x) (((x)<<1)+1)
43 int dict_look_ec (Dict dict, Dict_ptr ptr, MatchInfo *mi, MatchWord *ri_base,
44 int pos, int (*userfunc)(Dict_char *),
45 int range, Dict_char *prefix)
51 MatchWord match_mask = 1<<(mi->m-1);
53 dict_bf_readp (dict->dbf, ptr, &p);
56 indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
61 /* string (Dict_char *) DICT_EOS terminated */
62 /* unsigned char length of information */
63 /* char * information */
64 MatchWord *ri = ri_base, sc;
66 info = (char*)p + indxp[-lo];
71 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
75 if (ri[range] & match_mask)
79 if (j+pos >= mi->m+range)
82 ri[1+range] = SH(ri[0]) & sc;
83 for (i=1; i<=range; i++)
84 ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
85 | SH(ri[i+range]) | ri[i-1];
87 if (!(ri[range] & (1<<(pos+j))))
94 MatchWord *ri = ri_base, sc;
98 /* Dict_char sub char */
99 /* unsigned char length of information */
100 /* char * information */
101 info = (char*)p - indxp[-lo];
102 memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
105 sc = mi->s[ch & 255];
106 ri[1+range] = SH(ri[0]) & sc;
107 for (i=1; i<=range; i++)
108 ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
109 | SH(ri[i+range]) | ri[i-1];
111 if (ri[range] & (1<<pos))
114 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)] &&
115 (ri[range] & match_mask))
117 prefix[pos+1] = DICT_EOS;
120 memcpy (&subptr, info, sizeof(Dict_ptr));
123 dict_look_ec (dict, subptr, mi, ri, pos+1,
124 userfunc, range, prefix);
125 dict_bf_readp (dict->dbf, ptr, &p);
126 indxp = (short*) ((char*) p +
127 DICT_pagesize(dict)-sizeof(short));
136 static MatchInfo *prepare_match (Dict_char *pattern)
142 mi = xmalloc (sizeof(*mi));
143 mi->m = dict_strlen (pattern);
144 mi->s = s = xmalloc (sizeof(*s)*256); /* 256 !!! */
145 for (i=0; i<256; i++)
147 for (i=0; pattern[i]; i++)
148 s[pattern[i]&255] += 1<<i;
152 int dict_lookup_ec (Dict dict, Dict_char *pattern, int range,
153 int (*userfunc)(Dict_char *name))
158 Dict_char prefix[2048];
160 if (dict->head.last == 1)
163 mi = prepare_match (pattern);
165 ri = xmalloc ((dict_strlen(pattern)+range+2)*(range+1)*sizeof(*ri));
166 for (i=0; i<=range; i++)
169 i = dict_look_ec (dict, 1, mi, ri, 0, userfunc, range, prefix);