1 /* $NetBSD: locate.bigram.c,v 1.11 2008/07/21 14:19:23 lukem 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.11 2008/07/21 14:19:23 lukem 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 int main __P((int, char **)); 61 static int compare_bigrams __P((const void *, const void *)); 62 static void add_bigram __P((u_char, u_char)); 63 64 static char buf1[MAXPATHLEN] = " "; 65 static char buf2[MAXPATHLEN]; 66 67 struct bigram { 68 int count; 69 u_char b1, b2; /* needed for final sorting */ 70 }; 71 72 struct bigram bigrams[256 * 256]; 73 74 static void 75 add_bigram(i1, i2) 76 u_char i1, i2; 77 { 78 if (i1 != '\n' && i2 != '\n') 79 bigrams[(i1<<8)+i2].count++; 80 } 81 82 static int 83 compare_bigrams(item1, item2) 84 const void *item1, *item2; 85 { 86 const struct bigram *it1=item1, *it2=item2; 87 88 if (it1->count != it2->count) 89 return it2->count - it1->count; 90 else if (it1->b1 != it2->b1) 91 return it2->b1 - it1->b1; 92 else 93 return it2->b2 - it2->b2; 94 } 95 96 int 97 main(argc, argv) 98 int argc; 99 char *argv[]; 100 { 101 char *cp; 102 char *oldpath = buf1, *path = buf2; 103 struct bigram *bg; 104 int i; 105 106 /* initialize bigram array */ 107 memset(bigrams, 0, sizeof(bigrams)); 108 for(i=0; i < 65536; i++) { 109 bigrams[i].b1 = i / 256; 110 bigrams[i].b2 = i % 256; 111 } 112 113 while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) { 114 115 /* skip longest common prefix */ 116 for ( cp = path; *cp == *oldpath; cp++, oldpath++ ) 117 if ( *oldpath == '\0' ) 118 break; 119 120 /* 121 * output post-residue bigrams only 122 */ 123 for(; cp[0] != '\0' && cp[1] != '\0'; cp += 2) 124 add_bigram((u_char)cp[0], (u_char)cp[1]); 125 126 if (path == buf1) /* swap pointers */ 127 path = buf2, oldpath = buf1; 128 else 129 path = buf1, oldpath = buf2; 130 } 131 132 /* sort the bigrams by how many times it appeared and their value */ 133 heapsort((void *)bigrams, 256 * 256, sizeof(struct bigram), 134 compare_bigrams); 135 136 /* write 128 most frequent bigrams out */ 137 bg = bigrams; 138 for (i = 0; i < 128 && bg->count > 0; i++, bg++) { 139 if (bg->b1 != '\0') 140 fputc(bg->b1, stdout); 141 if (bg->b2 != '\0') 142 fputc(bg->b2, stdout); 143 } 144 145 return (0); 146 } 147