1 /*
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1995-2022 Wolfram Schneider <[email protected]>
5 * Copyright (c) 1989, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * This code is derived from software contributed to Berkeley by
9 * James A. Woods.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36 #ifndef lint
37 static const char copyright[] =
38 "@(#) Copyright (c) 1995-1996 Wolfram Schneider, Berlin.\n\
39 @(#) Copyright (c) 1989, 1993\n\
40 The Regents of the University of California. All rights reserved.\n";
41 #endif /* not lint */
42
43 #ifndef lint
44 #if 0
45 static char sccsid[] = "@(#)locate.c 8.1 (Berkeley) 6/6/93";
46 #endif
47 #endif /* not lint */
48
49 /*
50 * Ref: Usenix ;login:, Vol 8, No 1, February/March, 1983, p. 8.
51 *
52 * Locate scans a file list for the full pathname of a file given only part
53 * of the name. The list has been processed with with "front-compression"
54 * and bigram coding. Front compression reduces space by a factor of 4-5,
55 * bigram coding by a further 20-25%.
56 *
57 * The codes are:
58 *
59 * 0-28 likeliest differential counts + offset to make nonnegative
60 * 30 switch code for out-of-range count to follow in next word
61 * 31 an 8 bit char followed
62 * 128-255 bigram codes (128 most common, as determined by 'updatedb')
63 * 32-127 single character (printable) ascii residue (ie, literal)
64 *
65 * A novel two-tiered string search technique is employed:
66 *
67 * First, a metacharacter-free subpattern and partial pathname is matched
68 * BACKWARDS to avoid full expansion of the pathname list. The time savings
69 * is 40-50% over forward matching, which cannot efficiently handle
70 * overlapped search patterns and compressed path residue.
71 *
72 * Then, the actual shell glob-style regular expression (if in this form) is
73 * matched against the candidate pathnames using the slower routines provided
74 * in the standard 'find'.
75 */
76
77 #include <sys/param.h>
78 #include <ctype.h>
79 #include <err.h>
80 #include <fnmatch.h>
81 #include <locale.h>
82 #include <stdio.h>
83 #include <stdlib.h>
84 #include <string.h>
85 #include <unistd.h>
86
87 #ifdef MMAP
88 # include <sys/types.h>
89 # include <sys/stat.h>
90 # include <sys/mman.h>
91 # include <fcntl.h>
92 #endif
93
94 #include "locate.h"
95 #include "pathnames.h"
96
97
98 int f_mmap; /* use mmap */
99 int f_icase; /* ignore case */
100 int f_stdin; /* read database from stdin */
101 int f_statistic; /* print statistic */
102 int f_silent; /* suppress output, show only count of matches */
103 long f_limit; /* limit number of output lines, 0 == infinite */
104 long counter; /* counter for matches [-c] */
105 char separator='\n'; /* line separator */
106
107 u_char myctype[UCHAR_MAX + 1];
108
109 void usage(void);
110 void statistic(FILE *, char *);
111 void fastfind(FILE *, char *, char *);
112 void fastfind_icase(FILE *, char *, char *);
113 void fastfind_mmap(char *, caddr_t, off_t, char *);
114 void fastfind_mmap_icase(char *, caddr_t, off_t, char *);
115 void search_mmap(char *, char **);
116 void search_fopen(char *, char **);
117 unsigned long cputime(void);
118
119 extern char **colon(char **, char*, char*);
120 extern int getwm(caddr_t);
121 extern int getwf(FILE *);
122 extern u_char *tolower_word(u_char *);
123 extern int check_bigram_char(int);
124 extern char *patprep(char *);
125 extern void rebuild_message(char *db);
126 extern int check_size(char *db);
127
128 int
main(int argc,char ** argv)129 main(int argc, char **argv)
130 {
131 int ch;
132 char **dbv = NULL;
133 char *path_fcodes; /* locate database */
134 #ifdef MMAP
135 f_mmap = 1; /* mmap is default */
136 #endif
137 (void) setlocale(LC_ALL, "");
138
139 while ((ch = getopt(argc, argv, "0Scd:il:ms")) != -1)
140 switch(ch) {
141 case '0': /* 'find -print0' style */
142 separator = '\0';
143 break;
144 case 'S': /* statistic lines */
145 f_statistic = 1;
146 break;
147 case 'l': /* limit number of output lines, 0 == infinite */
148 f_limit = atol(optarg);
149 if (f_limit < 0 )
150 errx(1, "invalid argument for -l: '%s'", optarg);
151 break;
152 case 'd': /* database */
153 dbv = colon(dbv, optarg, _PATH_FCODES);
154 break;
155 case 'i': /* ignore case */
156 f_icase = 1;
157 break;
158 case 'm': /* mmap */
159 #ifdef MMAP
160 f_mmap = 1;
161 #else
162 warnx("mmap(2) not implemented");
163 #endif
164 break;
165 case 's': /* stdio lib */
166 f_mmap = 0;
167 break;
168 case 'c': /* suppress output, show only count of matches */
169 f_silent = 1;
170 break;
171 default:
172 usage();
173 }
174 argv += optind;
175 argc -= optind;
176
177 /* to few arguments */
178 if (argc < 1 && !(f_statistic))
179 usage();
180
181 /* no (valid) database as argument */
182 if (dbv == NULL || *dbv == NULL) {
183 /* try to read database from environment */
184 if ((path_fcodes = getenv("LOCATE_PATH")) == NULL ||
185 *path_fcodes == '\0')
186 /* use default database */
187 dbv = colon(dbv, _PATH_FCODES, _PATH_FCODES);
188 else /* $LOCATE_PATH */
189 dbv = colon(dbv, path_fcodes, _PATH_FCODES);
190 }
191
192 if (f_icase && UCHAR_MAX < 4096) /* init tolower lookup table */
193 for (ch = 0; ch < UCHAR_MAX + 1; ch++)
194 myctype[ch] = tolower(ch);
195
196 /* foreach database ... */
197 while((path_fcodes = *dbv) != NULL) {
198 dbv++;
199
200 if (!strcmp(path_fcodes, "-"))
201 f_stdin = 1;
202 else
203 f_stdin = 0;
204
205 #ifndef MMAP
206 f_mmap = 0; /* be paranoid */
207 #endif
208 if (!f_mmap || f_stdin || f_statistic)
209 search_fopen(path_fcodes, argv);
210 else
211 search_mmap(path_fcodes, argv);
212 }
213
214 if (f_silent)
215 printf("%ld\n", counter);
216 exit(0);
217 }
218
219 /*
220 * Arguments:
221 * db database
222 * s search strings
223 */
224 void
search_fopen(char * db,char ** s)225 search_fopen(char *db, char **s)
226 {
227 FILE *fp;
228
229 /* can only read stdin once */
230 if (f_stdin) {
231 fp = stdin;
232 if (*(s+1) != NULL) {
233 warnx("read database from stdin, use only `%s' as pattern", *s);
234 *(s+1) = NULL;
235 }
236 }
237 else {
238 if (!check_size(db))
239 exit(1);
240
241 if ((fp = fopen(db, "r")) == NULL) {
242 warn("`%s'", db);
243 rebuild_message(db);
244 exit(1);
245 }
246 }
247
248 /* count only chars or lines */
249 if (f_statistic) {
250 statistic(fp, db);
251 (void)fclose(fp);
252 return;
253 }
254
255 /* foreach search string ... */
256 while(*s != NULL) {
257 if (!f_stdin &&
258 fseek(fp, (long)0, SEEK_SET) == -1)
259 err(1, "fseek to begin of ``%s''\n", db);
260
261 if (f_icase)
262 fastfind_icase(fp, *s, db);
263 else
264 fastfind(fp, *s, db);
265 s++;
266 }
267 (void)fclose(fp);
268 }
269
270 #ifdef MMAP
271 /*
272 * Arguments:
273 * db database
274 * s search strings
275 */
276 void
search_mmap(char * db,char ** s)277 search_mmap(char *db, char **s)
278 {
279 struct stat sb;
280 int fd;
281 caddr_t p;
282 off_t len;
283
284 if (!check_size(db))
285 exit(1);
286
287 if (stat(db, &sb) == -1)
288 err(1, "stat");
289
290 len = sb.st_size;
291
292 if ((fd = open(db, O_RDONLY)) == -1) {
293 warn("%s", db);
294 rebuild_message(db);
295 exit(1);
296 }
297
298 if ((p = mmap((caddr_t)0, (size_t)len,
299 PROT_READ, MAP_SHARED,
300 fd, (off_t)0)) == MAP_FAILED)
301 err(1, "mmap ``%s''", db);
302
303 /* foreach search string ... */
304 while (*s != NULL) {
305 if (f_icase)
306 fastfind_mmap_icase(*s, p, len, db);
307 else
308 fastfind_mmap(*s, p, len, db);
309 s++;
310 }
311
312 if (munmap(p, (size_t)len) == -1)
313 warn("munmap %s\n", db);
314
315 (void)close(fd);
316 }
317 #endif /* MMAP */
318
319 void
usage()320 usage ()
321 {
322 (void)fprintf(stderr,
323 "usage: locate [-0Scims] [-l limit] [-d database] pattern ...\n\n");
324 (void)fprintf(stderr,
325 "default database: `%s' or $LOCATE_PATH\n", _PATH_FCODES);
326 exit(1);
327 }
328
329
330 /* load fastfind functions */
331
332 /* statistic */
333 /* fastfind_mmap, fastfind_mmap_icase */
334 #ifdef MMAP
335 #undef FF_MMAP
336 #undef FF_ICASE
337
338 #define FF_MMAP
339 #include "fastfind.c"
340 #define FF_ICASE
341 #include "fastfind.c"
342 #endif /* MMAP */
343
344 /* fopen */
345 /* fastfind, fastfind_icase */
346 #undef FF_MMAP
347 #undef FF_ICASE
348 #include "fastfind.c"
349 #define FF_ICASE
350 #include "fastfind.c"
351