Date: Thu, 14 Sep 1995 18:29:47 +0200 From: Wolfram Schneider <wosch@cs.tu-berlin.de> To: current@freebsd.org Subject: /usr/libexec/locate.* Message-ID: <199509141629.SAA28249@caramba.cs.tu-berlin.de>
next in thread | raw e-mail | index | archive | help
[next try, I don't see this mail in mailinglist]
o locate.bigram.c
Bigram does not remove newline at end of filename. This
break particulary the bigram algorithm and /var/db/locate.database
grow up 15 %. It's really a bug!!!
The bigram output is silly and need ~1/2 CPU time of
database rebuilding.
old:
locate.bigram < $filelist | sort | uniq -c | sort -T /$TMPDIR -nr
^^^^^^^^^^^^^^
this can easy make bigram
new:
locate.bigram < $filelist | sort -T /$TMPDIR -nr
o locate.code.c
Use a lookup array instead a function. 3 x faster
o local.updatedb.csh
# search locally or everything
# find ${SRCHPATHS} -print | \
find ${SRCHPATHS} \! -fstype local -prune -or -print | \
tr '/' '\001' | \
^^^^^^^^^^^^^^^^^^
Superfluously. Nobody need it.
(sort -T $TMPDIR -f; echo $status > $errs) | tr '\001' '/' > $filelist
^^
wrong, made database 0.5% bigger
^^^^^^^^^^^^^^^^^^^^^^^^
Superfluously, see above. It double the disk space for filenames. The
filenames are in a temp sort file and at the same time in $filelist.
sort -T $TMPDIR -o $filelist avoid this by renaming temp sort file
to $filelist. My database is 115MB big ...
$LIBDIR/locate.bigram < $filelist | \
(sort -T /$TMPDIR; echo $status >> $errs) | uniq -c |
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
see locate.bigram.c
--- /usr/src/usr.bin/locate/bigram/locate.bigram.c Fri May 27 14:32:02 1994
+++ locate.bigram.c Tue Sep 12 14:24:56 1995
@@ -53,32 +53,51 @@
#include <stdio.h>
#include <sys/param.h> /* for MAXPATHLEN */
+#include <string.h> /* memchr */
-char buf1[MAXPATHLEN] = " ";
-char buf2[MAXPATHLEN];
+u_char buf1[MAXPATHLEN] = " ";
+u_char buf2[MAXPATHLEN];
+unsigned int bigram[UCHAR_MAX][UCHAR_MAX];
-main ( )
+
+void main ( )
{
- register char *cp;
- register char *oldpath = buf1, *path = buf2;
+ register u_char *cp;
+ register u_char *oldpath = buf1, *path = buf2;
+ register int i, j;
+
+ /* init bigram buffer */
+ for (i = 0; i < UCHAR_MAX; i++)
+ for (j = 0; j < UCHAR_MAX; j++)
+ bigram[i][j] = 0;
while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) {
+ /* chop newline */
+ if ((cp = memchr(path, '\n', sizeof(buf2))) != NULL)
+ *cp = NULL;
+
/* skip longest common prefix */
- for ( cp = path; *cp == *oldpath; cp++, oldpath++ )
- if ( *oldpath == NULL )
- break;
+ for (cp = path; (*cp == *oldpath) != NULL; cp++, oldpath++);
+
/*
* output post-residue bigrams only
*/
+
while ( *cp != NULL && *(cp + 1) != NULL ) {
- putchar ( *cp++ );
- putchar ( *cp++ );
- putchar ( '\n' );
+ bigram[*cp][*(cp+1)]++;
+ cp += 2;
}
+
if ( path == buf1 ) /* swap pointers */
path = buf2, oldpath = buf1;
else
path = buf1, oldpath = buf2;
}
+
+ /* output */
+ for (i = 0; i < UCHAR_MAX; i++)
+ for (j = 0; j < UCHAR_MAX; j++)
+ if (bigram[i][j] != 0)
+ fprintf(stdout, "%4d %c%c\n", bigram[i][j], i, j);
}
--- 1.1 1995/09/12 16:40:45
+++ locate.code.c 1995/09/12 18:07:57
@@ -93,8 +93,20 @@
char buf2[MAXPATHLEN];
char bigrams[BGBUFSIZE + 1] = { 0 };
+#if 1
+#define BGINDEX(x) (big[(int)*x][(int)*(x+1)])
+typedef u_char bg_t;
+bg_t big[UCHAR_MAX][UCHAR_MAX];
+
+#else
+#define BGINDEX(x) bgindex(x)
+typedef int bg_t;
+#endif
+
int bgindex __P((char *));
void usage __P((void));
+extern int optind;
+extern int optopt;
int
main(argc, argv)
@@ -104,6 +116,7 @@
register char *cp, *oldpath, *path;
int ch, code, count, diffcount, oldcount;
FILE *fp;
+ register int i, j;
while ((ch = getopt(argc, argv, "")) != EOF)
switch(ch) {
@@ -126,14 +139,22 @@
err(1, "stdout");
(void)fclose(fp);
+ /* init lookup table */
+ for (i = 0; i < UCHAR_MAX; i++)
+ for (j = 0; j < UCHAR_MAX; j++)
+ big[i][j] = (bg_t)-1;
+
+ for (cp = bigrams, i = 0; *cp != NULL; i += 2, cp += 2)
+ big[(int)*cp][(int)*(cp + 1)] = (bg_t)i;
+
oldpath = buf1;
path = buf2;
oldcount = 0;
while (fgets(path, sizeof(buf2), stdin) != NULL) {
- /* Truncate newline. */
- cp = path + strlen(path) - 1;
- if (cp > path && *cp == '\n')
- *cp = '\0';
+
+ /* chop newline */
+ if ((cp = memchr(path, '\n', sizeof(buf2))) != NULL)
+ *cp = NULL;
/* Squelch characters that would botch the decoding. */
for (cp = path; *cp != NULL; cp++) {
@@ -144,9 +165,9 @@
}
/* Skip longest common prefix. */
- for (cp = path; *cp == *oldpath; cp++, oldpath++)
- if (*oldpath == NULL)
- break;
+ for (cp = path; (*cp == *oldpath) != NULL; cp++, oldpath++)
+ ;
+
count = cp - path;
diffcount = count - oldcount + OFFSET;
oldcount = count;
@@ -164,7 +185,7 @@
err(1, "stdout");
break;
}
- if ((code = bgindex(cp)) < 0) {
+ if ((code = BGINDEX(cp)) == (bg_t)-1) {
if (putchar(*cp++) == EOF ||
putchar(*cp++) == EOF)
err(1, "stdout");
--- /usr/libexec/locate.updatedb.old Sun Jan 1 05:36:58 1995
+++ /usr/libexec/locate.updatedb Tue Sep 12 14:33:32 1995
@@ -58,12 +58,10 @@
# search locally or everything
# find ${SRCHPATHS} -print | \
find ${SRCHPATHS} \! -fstype local -prune -or -print | \
- tr '/' '\001' | \
- (sort -T $TMPDIR -f; echo $status > $errs) | tr '\001' '/' > $filelist
+ sort -T $TMPDIR -o $filelist; echo $status > $errs
-$LIBDIR/locate.bigram < $filelist | \
- (sort -T /$TMPDIR; echo $status >> $errs) | \
- uniq -c | sort -T /$TMPDIR -nr | \
+$LIBDIR/locate.bigram.new < $filelist | \
+ sort -T $TMPDIR -nr | \
awk '{ if (NR <= 128) print $2 }' | tr -d '\012' > $bigrams
# code the file list
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199509141629.SAA28249>