1 /* $NetBSD: locate.bigram.c,v 1.13 2016/09/05 00:40:29 sevan Exp $ */
2
3 /*
4 * Copyright (c) 1989, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * James A. Woods.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 #include <sys/cdefs.h>
36 #ifndef lint
37 __COPYRIGHT("@(#) Copyright (c) 1989, 1993\
38 The Regents of the University of California. All rights reserved.");
39 #endif /* not lint */
40
41 #ifndef lint
42 #if 0
43 static char sccsid[] = "@(#)locate.bigram.c 8.2 (Berkeley) 4/28/95";
44 #endif
45 __RCSID("$NetBSD: locate.bigram.c,v 1.13 2016/09/05 00:40:29 sevan Exp $");
46 #endif /* not lint */
47
48 /*
49 * bigram < text > bigrams
50 *
51 * List bigrams for 'updatedb' script.
52 * Use 'code' to encode a file using this output.
53 */
54
55 #include <stdio.h>
56 #include <stdlib.h>
57 #include <string.h>
58 #include <sys/param.h> /* for MAXPATHLEN */
59
60 static int compare_bigrams(const void *, const void *);
61 static void add_bigram(u_char, u_char);
62
63 static char buf1[MAXPATHLEN] = " ";
64 static char buf2[MAXPATHLEN];
65
66 struct bigram {
67 int count;
68 u_char b1, b2; /* needed for final sorting */
69 };
70
71 struct bigram bigrams[256 * 256];
72
73 static void
add_bigram(u_char i1,u_char i2)74 add_bigram(u_char i1, u_char i2)
75 {
76 if (i1 != '\n' && i2 != '\n')
77 bigrams[(i1<<8)+i2].count++;
78 }
79
80 static int
compare_bigrams(const void * item1,const void * item2)81 compare_bigrams(const void *item1, const void *item2)
82 {
83 const struct bigram *it1=item1, *it2=item2;
84
85 if (it1->count != it2->count)
86 return it2->count - it1->count;
87 else if (it1->b1 != it2->b1)
88 return it2->b1 - it1->b1;
89 else
90 return it2->b2 - it2->b2;
91 }
92
93 int
main(int argc,char * argv[])94 main(int argc, char *argv[])
95 {
96 char *cp;
97 char *oldpath = buf1, *path = buf2;
98 struct bigram *bg;
99 int i;
100
101 /* initialize bigram array */
102 memset(bigrams, 0, sizeof(bigrams));
103 for(i=0; i < 65536; i++) {
104 bigrams[i].b1 = i / 256;
105 bigrams[i].b2 = i % 256;
106 }
107
108 while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) {
109
110 /* skip longest common prefix */
111 for ( cp = path; *cp == *oldpath; cp++, oldpath++ )
112 if ( *oldpath == '\0' )
113 break;
114
115 /*
116 * output post-residue bigrams only
117 */
118 for(; cp[0] != '\0' && cp[1] != '\0'; cp += 2)
119 add_bigram((u_char)cp[0], (u_char)cp[1]);
120
121 if (path == buf1) /* swap pointers */
122 path = buf2, oldpath = buf1;
123 else
124 path = buf1, oldpath = buf2;
125 }
126
127 /* sort the bigrams by how many times it appeared and their value */
128 heapsort((void *)bigrams, 256 * 256, sizeof(struct bigram),
129 compare_bigrams);
130
131 /* write 128 most frequent bigrams out */
132 bg = bigrams;
133 for (i = 0; i < 128 && bg->count > 0; i++, bg++) {
134 if (bg->b1 != '\0')
135 fputc(bg->b1, stdout);
136 if (bg->b2 != '\0')
137 fputc(bg->b2, stdout);
138 }
139
140 return (0);
141 }
142