/* ![[previous]](../icons/n_left.png)
![[next]](../icons/n_right.png)
![[first]](../icons/first.png)
![[last]](../icons/last.png)
![[top]](../icons/n_top.png)
![[bottom]](../icons/bottom.png)
![[index]](../icons/index.png)
![[help]](../icons/help.png)
*/
This source file includes following definitions.
- literal_comple
- literal_search
- cgotofn
- cfail
- overflo
1 /*
2 * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved.
3 *
4 * See 'Caldera Ancient Unix License' in 'LICENSE' file.
5 *
6 * Copyright (c) 2012 Tama Communications Corporation
7 *
8 * This file is part of GNU GLOBAL.
9 *
10 * This program is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program. If not, see <http://www.gnu.org/licenses/>.
22 */
23 /*
24 * This code was derived from /usr/src/usr.bin/fgrep.c in 4.3 Berkeley
25 * Software Distribution (4.3BSD) by the University of California.
26 * Since GNU grep is very strong, I would like to include its code into
27 * global command in near future.
28 */
29 #ifdef HAVE_CONFIG_H
30 #include <config.h>
31 #endif
32 #include <stdio.h>
33 #include <ctype.h>
34 #include <sys/param.h>
35 #include <sys/stat.h>
36 #include <errno.h>
37 #ifdef STDC_HEADERS
38 #include <stdlib.h>
39 #endif
40 #ifdef HAVE_MMAP
41 #include <sys/mman.h>
42 #elif _WIN32
43 #define WIN32_LEAN_AND_MEAN
44 #include <windows.h>
45 #endif
46 #ifdef HAVE_FCNTL_H
47 #include <fcntl.h>
48 #endif
49 #ifdef HAVE_UNISTD_H
50 #include <unistd.h>
51 #endif
52 #include "format.h"
53 #include "pathconvert.h"
54 #include "die.h"
55
56 #ifndef O_BINARY
57 #define O_BINARY 0
58 #endif
59
60 void overflo(void);
61 void cgotofn(const char *);
62 void cfail(void);
63
64 extern int iflag;
65 extern int Vflag;
66 extern void encode(char *, int, const char *);
67
68 #define MAXSIZ 6000
69 #define QSIZE 400
70 static struct words {
71 char inp;
72 char out;
73 struct words *nst;
74 struct words *link;
75 struct words *fail;
76 } w[MAXSIZ], *smax, *q;
77
78 static char encoded_pattern[IDENTLEN];
79
80 /**
81 * literal_comple: compile literal for search.
82 *
83 * @param[in] pattern literal string
84 *
85 * Literal string is treated as is.
86 */
87 void
88 literal_comple(const char *pattern)
89 {
90 /*
91 * convert spaces into %FF format.
92 */
93 encode(encoded_pattern, sizeof(encoded_pattern), pattern);
94 /*
95 * construct a goto table.
96 */
97 cgotofn(pattern);
98 /*
99 * construct fail links.
100 */
101 cfail();
102 }
103 /**
104 * literal_search: execute literal search
105 *
106 * @param[in] file file to search
107 * @return 0: normal, -1: error
108 */
109 # define ccomp(a,b) (iflag ? lca(a)==lca(b) : a==b)
110 # define lca(x) (isupper(x) ? tolower(x) : x)
111 void
112 literal_search(CONVERT *cv, const char *file)
113 {
114 struct words *c;
115 int ccount;
116 char *p;
117 char *buf;
118 struct stat stb;
119 char *linep;
120 long lineno;
121 int f;
122
123 if ((f = open(file, O_BINARY)) < 0) {
124 warning("cannot open '%s'.", file);
125 return;
126 }
127 if (fstat(f, &stb) < 0) {
128 warning("cannot fstat '%s'.", file);
129 goto skip_empty_file;
130 }
131 if (stb.st_size == 0)
132 goto skip_empty_file;
133 #ifdef HAVE_MMAP
134 buf = mmap(0, stb.st_size, PROT_READ, MAP_SHARED, f, 0);
135 if (buf == MAP_FAILED)
136 die("mmap failed (%s).", file);
137 #elif _WIN32
138 {
139 HANDLE hMap = CreateFileMapping((HANDLE)_get_osfhandle(f), NULL, PAGE_READONLY, 0, stb.st_size, NULL);
140 if (hMap == NULL)
141 die("CreateFileMapping failed (%s).", file);
142 buf = MapViewOfFile(hMap, FILE_MAP_READ, 0, 0, 0);
143 if (buf == NULL)
144 die("MapViewOfFile failed (%s).", file);
145 #else
146 #ifdef HAVE_ALLOCA
147 buf = (char *)alloca(stb.st_size);
148 #else
149 buf = (char *)malloc(stb.st_size);
150 #endif
151 if (buf == NULL)
152 die("short of memory.");
153 if (read(f, buf, stb.st_size) < stb.st_size)
154 die("read failed (%s).", file);
155 #endif
156 linep = p = buf;
157 ccount = stb.st_size;
158 lineno = 1;
159 c = w;
160 for (;;) {
161 if (--ccount <= 0)
162 break;
163 nstate:
164 if (ccomp(c->inp, *p)) {
165 c = c->nst;
166 }
167 else if (c->link != 0) {
168 c = c->link;
169 goto nstate;
170 }
171 else {
172 c = c->fail;
173 if (c==0) {
174 c = w;
175 istate:
176 if (ccomp(c->inp , *p)) {
177 c = c->nst;
178 }
179 else if (c->link != 0) {
180 c = c->link;
181 goto istate;
182 }
183 }
184 else goto nstate;
185 }
186 if (c->out) {
187 while (*p++ != '\n') {
188 if (--ccount <= 0)
189 break;
190 }
191 if (Vflag)
192 goto nomatch;
193 succeed: if (cv->format == FORMAT_PATH) {
194 convert_put_path(cv, file);
195 goto finish;
196 } else {
197 STATIC_STRBUF(sb);
198
199 strbuf_clear(sb);
200 strbuf_nputs(sb, linep, p - linep);
201 strbuf_unputc(sb, '\n');
202 strbuf_unputc(sb, '\r');
203 convert_put_using(cv, encoded_pattern, file, lineno, strbuf_value(sb), NULL);
204 }
205 nomatch: lineno++;
206 linep = p;
207 c = w;
208 continue;
209 }
210 if (*p++ == '\n') {
211 if (Vflag)
212 goto succeed;
213 else {
214 lineno++;
215 linep = p;
216 c = w;
217 }
218 }
219 }
220 finish:
221 #ifdef HAVE_MMAP
222 munmap(buf, stb.st_size);
223 #elif _WIN32
224 UnmapViewOfFile(buf);
225 CloseHandle(hMap);
226 }
227 #elif HAVE_ALLOCA
228 #else
229 free(buf);
230 #endif
231 skip_empty_file:
232 close(f);
233 }
234 /**
235 * make automaton.
236 */
237 void
238 cgotofn(const char *pattern) {
239 int c;
240 struct words *s;
241
242 s = smax = w;
243 nword: for(;;) {
244 c = *pattern++;
245 if (c==0)
246 return;
247 if (c == '\n') {
248 s->out = 1;
249 s = w;
250 } else {
251 loop: if (s->inp == c) {
252 s = s->nst;
253 continue;
254 }
255 if (s->inp == 0) goto enter;
256 if (s->link == 0) {
257 if (smax >= &w[MAXSIZ - 1])
258 overflo();
259 s->link = ++smax;
260 s = smax;
261 goto enter;
262 }
263 s = s->link;
264 goto loop;
265 }
266 }
267 enter:
268 do {
269 s->inp = c;
270 if (smax >= &w[MAXSIZ - 1])
271 overflo();
272 s->nst = ++smax;
273 s = smax;
274 } while ((c = *pattern++) != '\n' && c!=0);
275 smax->out = 1;
276 s = w;
277 if (c != 0)
278 goto nword;
279 }
280
281 void
282 cfail() {
283 struct words *queue[QSIZE];
284 struct words **front, **rear;
285 struct words *state;
286 int bstart;
287 char c;
288 struct words *s;
289
290 s = w;
291 front = rear = queue;
292 init: if ((s->inp) != 0) {
293 *rear++ = s->nst;
294 if (rear >= &queue[QSIZE - 1])
295 overflo();
296 }
297 if ((s = s->link) != 0) {
298 goto init;
299 }
300
301 while (rear != front) {
302 s = *front;
303 if (front == &queue[QSIZE-1])
304 front = queue;
305 else front++;
306 cloop: if ((c = s->inp) != 0) {
307 bstart = 0;
308 *rear = (q = s->nst);
309 if (front < rear)
310 if (rear >= &queue[QSIZE-1])
311 if (front == queue) overflo();
312 else rear = queue;
313 else rear++;
314 else
315 if (++rear == front) overflo();
316 state = s->fail;
317 floop: if (state == 0) {
318 state = w;
319 bstart = 1;
320 }
321 if (state->inp == c) {
322 qloop: q->fail = state->nst;
323 if ((state->nst)->out == 1)
324 q->out = 1;
325 if ((q = q->link) != 0)
326 goto qloop;
327 }
328 else if ((state = state->link) != 0)
329 goto floop;
330 else if (bstart == 0){
331 state = 0;
332 goto floop;
333 }
334 }
335 if ((s = s->link) != 0)
336 goto cloop;
337 }
338 }
339 void
340 overflo() {
341 die("wordlist too large.");
342 }
/* ![[top]](../icons/top.png)
![[bottom]](../icons/n_bottom.png)
*/