2 * Copyright (C) 1994-1999, Index Data
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.9 1999-05-26 07:49:13 adam
10 * Revision 1.8 1999/05/15 14:36:37 adam
11 * Updated dictionary. Implemented "compression" of dictionary.
13 * Revision 1.7 1999/02/02 14:50:26 adam
14 * Updated WIN32 code specific sections. Changed header.
16 * Revision 1.6 1996/02/02 13:43:51 adam
17 * The public functions simply use char instead of Dict_char to represent
18 * search strings. Dict_char is used internally only.
20 * Revision 1.5 1995/01/24 16:01:03 adam
21 * Added -ansi to CFLAGS.
22 * Use new API of dfa module.
24 * Revision 1.4 1994/10/05 12:16:51 adam
25 * Pagesize is a resource now.
27 * Revision 1.3 1994/09/26 16:31:06 adam
30 * Revision 1.2 1994/09/22 14:43:57 adam
31 * First functional version of lookup with error correction. A 'range'
32 * specified the maximum number of insertions+deletions+substitutions.
34 * Revision 1.1 1994/09/22 10:43:44 adam
35 * Two versions of depend. Type 1 is the tail-type compatible with
36 * all make programs. Type 2 is the GNU make with include facility.
37 * Type 2 is default. depend rule chooses current rule.
47 typedef unsigned MatchWord;
54 #define SH(x) (((x)<<1)+1)
56 int dict_look_ec (Dict dict, Dict_ptr ptr, MatchInfo *mi, MatchWord *ri_base,
57 int pos, int (*userfunc)(char *), int range,
64 MatchWord match_mask = 1<<(mi->m-1);
66 dict_bf_readp (dict->dbf, ptr, &p);
69 indxp = (short*) ((char*) p+DICT_bsize(p)-sizeof(short));
74 /* string (Dict_char *) DICT_EOS terminated */
75 /* unsigned char length of information */
76 /* char * information */
77 MatchWord *ri = ri_base, sc;
79 info = (char*)p + indxp[-lo];
84 memcpy (&ch, info+j*sizeof(Dict_char), sizeof(Dict_char));
88 if (ri[range] & match_mask)
89 (*userfunc)((char*) prefix);
92 if (j+pos >= mi->m+range)
95 ri[1+range] = SH(ri[0]) & sc;
96 for (i=1; i<=range; i++)
97 ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
98 | SH(ri[i+range]) | ri[i-1];
100 if (!(ri[range] & (1<<(pos+j))))
107 MatchWord *ri = ri_base, sc;
110 /* Dict_ptr subptr */
111 /* Dict_char sub char */
112 /* unsigned char length of information */
113 /* char * information */
114 info = (char*)p - indxp[-lo];
115 memcpy (&ch, info+sizeof(Dict_ptr), sizeof(Dict_char));
118 sc = mi->s[ch & 255];
119 ri[1+range] = SH(ri[0]) & sc;
120 for (i=1; i<=range; i++)
121 ri[i+1+range] = (SH(ri[i]) & sc) | SH(ri[i-1])
122 | SH(ri[i+range]) | ri[i-1];
124 if (ri[range] & (1<<pos))
127 if (info[sizeof(Dict_ptr)+sizeof(Dict_char)] &&
128 (ri[range] & match_mask))
130 prefix[pos+1] = DICT_EOS;
131 (*userfunc)((char*) prefix);
133 memcpy (&subptr, info, sizeof(Dict_ptr));
136 dict_look_ec (dict, subptr, mi, ri, pos+1,
137 userfunc, range, prefix);
138 dict_bf_readp (dict->dbf, ptr, &p);
139 indxp = (short*) ((char*) p +
140 DICT_bsize(p)-sizeof(short));
149 static MatchInfo *prepare_match (Dict_char *pattern)
155 mi = (MatchInfo *) xmalloc (sizeof(*mi));
156 mi->m = dict_strlen (pattern);
157 mi->s = s = (MatchWord *) xmalloc (sizeof(*s)*256); /* 256 !!! */
158 for (i=0; i<256; i++)
160 for (i=0; pattern[i]; i++)
161 s[pattern[i]&255] += 1<<i;
165 int dict_lookup_ec (Dict dict, char *pattern, int range,
166 int (*userfunc)(char *name))
171 Dict_char prefix[2048];
173 if (!dict->head.root)
176 mi = prepare_match ((Dict_char*) pattern);
178 ri = (MatchWord *) xmalloc ((dict_strlen((Dict_char*) pattern)+range+2)
179 * (range+1)*sizeof(*ri));
180 for (i=0; i<=range; i++)
183 i = dict_look_ec (dict, dict->head.root, mi, ri, 0, userfunc,