1 /* 2 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 7 /* All Rights Reserved */ 8 9 /* 10 * Copyright (c) 1980 Regents of the University of California. 11 * All rights reserved. The Berkeley software License Agreement 12 * specifies the terms and conditions for redistribution. 13 */ 14 15 #include "refer..c" 16 17 static int *coord = 0; 18 int hh[50]; 19 extern int *hfreq, hfrflg; 20 extern int prfreqs; 21 union ptr { 22 unsigned *a; 23 long *b; 24 }; 25 26 extern int hash(); 27 extern void shell(); 28 extern void *zalloc(); 29 30 static long getl(FILE *); 31 static int hcomp(int, int); 32 static void hexch(int, int); 33 34 int 35 doquery(long *hpt, int nhash, FILE *fb, int nitem, 36 char *qitem[], unsigned *mptr) 37 { 38 long k; 39 union ptr prevdrop, master; 40 int nf = 0, best = 0, nterm = 0, i, g, j; 41 int *prevcoord; 42 long lp; 43 extern int lmaster, colevel, reached; 44 extern int iflong; 45 46 if (iflong) { 47 master.b = (long *)mptr; 48 } else { 49 master.a = mptr; 50 } 51 52 #if D1 53 fprintf(stderr, "entering doquery nitem %d\n", nitem); 54 fprintf(stderr, "first few hashes are %ld %ld %ld %ld %ld\n", 55 hpt[0], hpt[1], hpt[2], hpt[3], hpt[4]); 56 fprintf(stderr, "and frequencies are %d %d %d %d %d\n", 57 hfreq[0], hfreq[1], hfreq[2], hfreq[3], hfreq[4]); 58 #endif 59 assert(lmaster > 0); 60 if (coord == 0) 61 coord = (int *)zalloc(lmaster, sizeof (lmaster)); 62 if (colevel > 0) { 63 if (iflong) 64 prevdrop.b = (long *)zalloc(lmaster, sizeof (long)); 65 else 66 prevdrop.a = (unsigned *)zalloc(lmaster, sizeof (int)); 67 prevcoord = (int *)zalloc(lmaster, sizeof (lmaster)); 68 } else { 69 prevdrop.a = master.a; 70 prevcoord = coord; 71 } 72 #if D1 73 fprintf(stderr, "nitem %d\n", nitem); 74 #endif 75 for (i = 0; i < nitem; i++) { 76 hh[i] = hash(qitem[i])%nhash; 77 #if D1 78 fprintf(stderr, "query wd X%sX has hash %d\n", qitem[i], hh[i]); 79 #endif 80 } 81 #if D1 82 fprintf(stderr, "past that loop nhash %d hpt is %lo\n", nhash, hpt); 83 #endif 84 if (prfreqs) 85 for (i = 0; i < nitem; i++) 86 fprintf(stderr, "item %s hash %d hfreq %d\n", 87 qitem[i], hh[i], hfreq[hh[i]]); 88 /* if possible, sort query into decreasing frequency of hashes */ 89 if (hfrflg) 90 shell(nitem, hcomp, hexch); 91 #if D1 92 for (i = 0; i < nitem; i++) 93 fprintf(stderr, "item hash %d frq %d\n", hh[i], hfreq[hh[i]]); 94 #endif 95 lp = hpt [hh[0]]; 96 #if D1 97 fprintf(stderr, "first item hash %d lp %ld 0%lo\n", hh[0], lp, lp); 98 #endif 99 assert(fb != NULL); 100 assert(fseek(fb, lp, 0) != -1); 101 for (i = 0; i < lmaster; i++) { 102 if (iflong) 103 master.b[i] = getl(fb); 104 else 105 master.a[i] = getw(fb); 106 coord[i] = 1; 107 #if D2 108 if (iflong) 109 fprintf(stderr, "master has %ld\n", (master.b[i])); 110 else 111 fprintf(stderr, "master has %d\n", (master.a[i])); 112 #endif 113 assert(i < lmaster); 114 if (iflong) { 115 if (master.b[i] == -1L) break; 116 } else { 117 if (master.a[i] == -1) break; 118 } 119 } 120 nf = i; 121 for (nterm = 1; nterm < nitem; nterm++) { 122 #ifdef D1 123 fprintf(stderr, "item %d, hash %d\n", nterm, hh[nterm]); 124 #endif 125 if (colevel > 0) { 126 for (j = 0; j < nf; j++) { 127 if (iflong) 128 prevdrop.b[j] = master.b[j]; 129 else 130 prevdrop.a[j] = master.a[j]; 131 prevcoord[j] = coord[j]; 132 } 133 } 134 lp = hpt[hh[nterm]]; 135 assert(fseek(fb, lp, 0) != -1); 136 #if D1 137 fprintf(stderr, "item %d hash %d seek to %ld\n", 138 nterm, hh[nterm], lp); 139 #endif 140 g = j = 0; 141 while (1) { 142 if (iflong) 143 k = getl(fb); 144 else 145 k = getw(fb); 146 if (k == -1) break; 147 #if D2 148 fprintf(stderr, "next term finds %ld\n", k); 149 #endif 150 #if D3 151 if (iflong) 152 fprintf(stderr, 153 "bfwh j %d nf %d master %ld k %ld\n", 154 j, nf, prevdrop.b[j], (long)(k)); 155 else 156 fprintf(stderr, 157 "bfwh j %d nf %d master %ld k %ld\n", 158 j, nf, prevdrop.a[j], (long)(k)); 159 #endif 160 while (j < nf && 161 (iflong ? prevdrop.b[j] : prevdrop.a[j]) < k) { 162 #if D3 163 if (iflong) 164 fprintf(stderr, "j %d nf %d prevdrop " 165 "%ld prevcoord %d colevel %d nterm " 166 "%d k %ld\n", j, nf, prevdrop.b[j], 167 prevcoord[j], colevel, nterm, 168 (long)(k)); 169 else 170 fprintf(stderr, "j %d nf %d prevdrop " 171 "%ld prevcoord %d colevel %d nterm " 172 "%d k %ld\n", j, nf, prevdrop.a[j], 173 prevcoord[j], colevel, nterm, 174 (long)(k)); 175 #endif 176 if (prevcoord[j] + colevel <= nterm) 177 j++; 178 else { 179 assert(g < lmaster); 180 if (iflong) 181 master.b[g] = prevdrop.b[j]; 182 else 183 master.a[g] = prevdrop.a[j]; 184 coord[g++] = prevcoord[j++]; 185 #if D1 186 if (iflong) 187 fprintf(stderr, " not skip g " 188 "%d doc %d coord %d note " 189 "%d\n", g, master.b[g-1], 190 coord[g-1], master.b[j-1]); 191 else 192 fprintf(stderr, " not skip g " 193 "%d doc %ld coord %d nterm " 194 "%d\n", g, master.a[g-1], 195 coord[g-1], nterm); 196 #endif 197 continue; 198 } 199 } 200 if (colevel == 0 && j >= nf) break; 201 if (j < nf && 202 (iflong ? prevdrop.b[j] : prevdrop.a[j]) == k) { 203 if (iflong) 204 master.b[g] = k; 205 else 206 master.a[g] = k; 207 coord[g++] = prevcoord[j++]+1; 208 #if D1 209 if (iflong) 210 fprintf(stderr, " at g %d item %ld " 211 "coord %d note %ld\n", g, 212 master.b[g-1], coord[g-1], 213 master.b[j-1]); 214 else 215 fprintf(stderr, " at g %d item %d " 216 "coord %d note %d\n", g, 217 master.a[g-1], coord[g-1], 218 master.a[j-1]); 219 #endif 220 } else 221 if (colevel >= nterm) { 222 if (iflong) 223 master.b[g] = k; 224 else 225 master.a[g] = k; 226 coord[g++] = 1; 227 } 228 } 229 #if D1 230 fprintf(stderr, "now have %d items\n", g); 231 #endif 232 if (colevel > 0) 233 for (; j < nf; j++) 234 if ((iflong ? prevdrop.b[j] : prevdrop.a[j]) + 235 colevel > nterm) { 236 assert(g < lmaster); 237 if (iflong) 238 master.b[g] = prevdrop.b[j]; 239 else 240 master.a[g] = prevdrop.a[j]; 241 coord[g++] = prevcoord[j]; 242 #if D3 243 if (iflong) 244 fprintf(stderr, "copied over " 245 "%ld coord %d\n", 246 master.b[g-1], coord[g-1]); 247 else 248 fprintf(stderr, "copied over " 249 "%d coord %d\n", 250 master.a[g-1], coord[g-1]); 251 #endif 252 } 253 nf = g; 254 } 255 if (colevel > 0) { 256 best = 0; 257 for (j = 0; j < nf; j++) 258 if (coord[j] > best) best = coord[j]; 259 #if D1 260 fprintf(stderr, "colevel %d best %d\n", colevel, best); 261 #endif 262 reached = best; 263 for (g = j = 0; j < nf; j++) 264 if (coord[j] == best) { 265 if (iflong) 266 master.b[g++] = master.b[j]; 267 else 268 master.a[g++] = master.a[j]; 269 } 270 nf = g; 271 #if D1 272 fprintf(stderr, "yet got %d\n", nf); 273 #endif 274 } 275 #ifdef D1 276 fprintf(stderr, " returning with %d\n", nf); 277 #endif 278 if (colevel) { 279 free(prevdrop, lmaster, iflong ? sizeof (long): sizeof (int)); 280 free(prevcoord, lmaster, sizeof (lmaster)); 281 } 282 #if D3 283 for (g = 0; g < nf; g++) 284 if (iflong) 285 fprintf(stderr, ":%ld\n", master.b[g]); 286 else 287 fprintf(stderr, ":%d\n", master.a[g]); 288 #endif 289 return (nf); 290 } 291 292 static long 293 getl(FILE *fb) 294 { 295 return (getw(fb)); 296 } 297 298 static int 299 hcomp(int n1, int n2) 300 { 301 return (hfreq[hh[n1]] <= hfreq[hh[n2]]); 302 } 303 304 static void 305 hexch(int n1, int n2) 306 { 307 int t; 308 t = hh[n1]; 309 hh[n1] = hh[n2]; 310 hh[n2] = t; 311 } 312