2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.4 1994-10-05 12:16:51 adam
8 * Pagesize is a resource now.
10 * Revision 1.3 1994/09/26 16:31:06 adam
13 * Revision 1.2 1994/09/22 14:43:57 adam
14 * First functional version of lookup with error correction. A 'range'
15 * specified the maximum number of insertions+deletions+substitutions.
17 * Revision 1.1 1994/09/22 10:43:44 adam
18 * Two versions of depend. Type 1 is the tail-type compatible with
19 * all make programs. Type 2 is the GNU make with include facility.
20 * Type 2 is default. depend rule chooses current rule.
30 typedef unsigned MatchWord;
37 #define SH(x) (((x)<<1)+1)
39 int dict_look_ec (Dict dict, Dict_ptr ptr, MatchInfo *mi, MatchWord *ri_base,
40 int pos, int (*userfunc)(Dict_char *),
41 int range, Dict_char *prefix)
47 MatchWord match_mask = 1<<(mi->m-1);
49 dict_bf_readp (dict->dbf, ptr, &p);
52 indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
57 /* string (Dict_char *) DICT_EOS terminated */
58 /* unsigned char length of information */
59 /* char * information */
60 MatchWord *ri = ri_base, sc;
62 info = (char*)p + indxp[-lo];
67 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
71 if (ri[range] & match_mask)
75 if (j+pos >= mi->m+range)
78 ri[1+range] = SH(ri[0]) & sc;
79 for (i=1; i<=range; i++)
80 ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
81 | SH(ri[i+range]) | ri[i-1];
83 if (!(ri[range] & (1<<(pos+j))))
90 MatchWord *ri = ri_base, sc;
94 /* Dict_char sub char */
95 /* unsigned char length of information */
96 /* char * information */
97 info = (char*)p - indxp[-lo];
98 memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
101 sc = mi->s[ch & 255];
102 ri[1+range] = SH(ri[0]) & sc;
103 for (i=1; i<=range; i++)
104 ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
105 | SH(ri[i+range]) | ri[i-1];
107 if (ri[range] & (1<<pos))
110 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)] &&
111 (ri[range] & match_mask))
113 prefix[pos+1] = DICT_EOS;
116 memcpy (&subptr, info, sizeof(Dict_ptr));
119 dict_look_ec (dict, subptr, mi, ri, pos+1,
120 userfunc, range, prefix);
121 dict_bf_readp (dict->dbf, ptr, &p);
122 indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
131 static MatchInfo *prepare_match (Dict_char *pattern)
137 mi = xmalloc (sizeof(*mi));
138 mi->m = dict_strlen (pattern);
139 mi->s = s = xmalloc (sizeof(*s)*256); /* 256 !!! */
140 for (i=0; i<256; i++)
142 for (i=0; pattern[i]; i++)
143 s[pattern[i]&255] += 1<<i;
147 int dict_lookup_ec (Dict dict, Dict_char *pattern, int range,
148 int (*userfunc)(Dict_char *name))
153 Dict_char prefix[2048];
155 if (dict->head.last == 1)
158 mi = prepare_match (pattern);
161 ri = xmalloc ((dict_strlen(pattern)+range+2)*(range+1)*sizeof(*ri));
163 ri = xmalloc (2048 * (range+1) * sizeof(*ri));
166 for (i=0; i<=range; i++)
169 i = dict_look_ec (dict, 1, mi, ri, 0, userfunc, range, prefix);