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