src/invlib.c

   1 /*===========================================================================
   2  Copyright (c) 1998-2000, The Santa Cruz Operation
   3  All rights reserved.
   4
   5  Redistribution and use in source and binary forms, with or without
   6  modification, are permitted provided that the following conditions are met:
   7
   8  *Redistributions of source code must retain the above copyright notice,
   9  this list of conditions and the following disclaimer.
  10
  11  *Redistributions in binary form must reproduce the above copyright notice,
  12  this list of conditions and the following disclaimer in the documentation
  13  and/or other materials provided with the distribution.
  14
  15  *Neither name of The Santa Cruz Operation nor the names of its contributors
  16  may be used to endorse or promote products derived from this software
  17  without specific prior written permission.
  18
  19  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS
  20  IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
  23  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  INTERRUPTION)
  27  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
  30  DAMAGE.
  31  =========================================================================*/
  32
  33
  34 #include <ctype.h>
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #if SHARE
  38 #include <sys/types.h>
  39 #include <sys/ipc.h>
  40 #include <sys/shm.h>
  41 #define ERR  -1
  42 #endif
  43 #include "invlib.h"
  44 #include "global.h"
  45
  46 #include <assert.h>
  47
  48 #define DEBUG           0       /* debugging code and realloc messages */
  49 #define BLOCKSIZE       2 * BUFSIZ      /* logical block size */
  50 #define POSTINC         10000   /* posting buffer size increment */
  51 #define SEP             ' '     /* sorted posting field separator */
  52 #define SETINC          100     /* posting set size increment */
  53 #define STATS           0       /* print statistics */
  54 #define SUPERINC        10000   /* super index size increment */
  55 #define TERMMAX         512     /* term max size */
  56 #define FMTVERSION      1       /* inverted index format version */
  57 #define ZIPFSIZE        200     /* zipf curve size */
  58
  59 static char const rcsid[] = "$Id: invlib.c,v 1.21 2012/07/10 20:01:40 nhorman Exp $";
  60
  61 #if DEBUG
  62 /* FIXME HBB 20010705: nowhere in the source is `invbreak' ever set to
  63  * a value other than the (silent) initialization to zero. Pretty
  64  * useless, that looks */
  65 int     invbreak;
  66 #endif
  67
  68 static  int     boolready(void);
  69 static  int     invnewterm(void);
  70 static  void    invstep(INVCONTROL *invcntl);
  71 static  void    invcannotalloc(unsigned n);
  72 static  void    invcannotopen(char *file);
  73 static  void    invcannotwrite(char *file);
  74
  75 #if STATS
  76 int     showzipf;       /* show postings per term distribution */
  77 #endif
  78
  79 static  POSTING *item, *enditem, *item1 = NULL, *item2 = NULL;
  80 static  unsigned setsize1, setsize2;
  81 static  long    numitems, totterm, zerolong;
  82 static  char    *indexfile, *postingfile;
  83 static  FILE    *outfile, *fpost;
  84 static  unsigned supersize = SUPERINC, supintsize;
  85 static  unsigned int numpost, numlogblk, amtused, nextpost;
  86 static  unsigned int lastinblk, numinvitems;
  87 static  POSTING *POST, *postptr;
  88 static  unsigned long   *SUPINT, *supint, nextsupfing;
  89 static  char    *SUPFING, *supfing;
  90 static  char    thisterm[TERMMAX];
  91 typedef union logicalblk {
  92         long    invblk[BLOCKSIZE / sizeof(long)];
  93         char    chrblk[BLOCKSIZE];
  94 } t_logicalblk;
  95 static t_logicalblk logicalblk;
  96
  97 #if DEBUG || STATS
  98 static  long    totpost;
  99 #endif
 100
 101 #if STATS
 102 static  int     zipf[ZIPFSIZE + 1];
 103 #endif
 104
 105 long
 106 invmake(char *invname, char *invpost, FILE *infile)
 107 {
 108         unsigned char   *s;
 109         long    num;
 110         int     i;
 111         long    fileindex = 0;  /* initialze, to avoid warning */
 112         unsigned postsize = POSTINC * sizeof(POSTING);
 113         unsigned long   *intptr;
 114         char    line[TERMMAX];
 115         long    tlong;
 116         PARAM   param;
 117         POSTING posting;
 118         char    temp[BLOCKSIZE];
 119 #if STATS
 120         int     j;
 121         unsigned maxtermlen = 0;
 122 #endif
 123         /* output file */
 124         if ((outfile = vpfopen(invname, "w+b")) == NULL) {
 125                 invcannotopen(invname);
 126                 return(0);
 127         }
 128         indexfile = invname;
 129         fseek(outfile, BUFSIZ, SEEK_SET);
 130
 131         /* posting file  */
 132         if ((fpost = vpfopen(invpost, "wb")) == NULL) {
 133                 invcannotopen(invpost);
 134                 return(0);
 135         }
 136         postingfile = invpost;
 137         nextpost = 0;
 138         /* get space for the postings list */
 139         if ((POST = malloc(postsize)) == NULL) {
 140                 invcannotalloc(postsize);
 141                 return(0);
 142         }
 143         postptr = POST;
 144         /* get space for the superfinger (superindex) */
 145         if ((SUPFING = malloc(supersize)) == NULL) {
 146                 invcannotalloc(supersize);
 147                 return(0);
 148         }
 149         supfing = SUPFING;
 150         /* FIXME HBB: magic number alert (40) */
 151         supintsize = supersize / 40;
 152         /* also for the superfinger index */
 153         if ((SUPINT = malloc(supintsize * sizeof(long))) == NULL) {
 154                 invcannotalloc(supintsize * sizeof(long));
 155                 return(0);
 156         }
 157         supint = SUPINT;
 158         supint++; /* leave first term open for a count */
 159         /* initialize using an empty term */
 160         strcpy(thisterm, "");
 161         *supint++ = 0;
 162         *supfing++ = ' ';
 163         *supfing++ = '\0';
 164         nextsupfing = 2;
 165 #if DEBUG || STATS
 166         totpost = 0L;
 167 #endif
 168         totterm = 0L;
 169         numpost = 1;
 170
 171         /* set up as though a block had come and gone, i.e., set up for new block  */
 172         /* 3 longs needed for: numinvitems, next block, and previous block */
 173         amtused = 3 * sizeof(long);
 174         numinvitems = 0;
 175         numlogblk = 0;
 176         lastinblk = sizeof(t_logicalblk);
 177
 178         /* now loop as long as more to read (till eof)  */
 179         while (fgets(line, TERMMAX, infile) != NULL) {
 180 #if DEBUG || STATS
 181                 ++totpost;
 182 #endif
 183                 s = strchr(line, SEP);
 184                 if (s != NULL) {
 185                         *s = '\0';
 186                 }
 187                 else {
 188                         continue;
 189                 }
 190 #if STATS
 191                 if ((i = strlen(line)) > maxtermlen) {
 192                         maxtermlen = i;
 193                 }
 194 #endif
 195 #if DEBUG
 196                 printf("%ld: %s ", totpost, line);
 197                 fflush(stdout);
 198 #endif
 199                 if (strcmp(thisterm, line) == 0) {
 200                         if (postptr + 10 > POST + postsize / sizeof(POSTING)) {
 201                                 i = postptr - POST;
 202                                 postsize += POSTINC * sizeof(POSTING);
 203                                 if ((POST = realloc(POST, postsize)) == NULL) {
 204                                         invcannotalloc(postsize);
 205                                         return(0);
 206                                 }
 207                                 postptr = i + POST;
 208 #if DEBUG
 209                                 printf("reallocated post space to %u, totpost=%ld\n",
 210                                        postsize, totpost);
 211 #endif
 212                         }
 213                         numpost++;
 214                 } else {
 215                         /* have a new term */
 216                         if (!invnewterm()) {
 217                                 return(0);
 218                         }
 219                         strcpy(thisterm, line);
 220                         numpost = 1;
 221                         postptr = POST;
 222                         fileindex = 0;
 223                 }
 224                 /* get the new posting */
 225                 num = *++s - '!';
 226                 i = 1;
 227                 do {
 228                         num = BASE * num + *++s - '!';
 229                 } while (++i < PRECISION);
 230                 posting.lineoffset = num;
 231                 while (++fileindex < nsrcfiles && num > srcoffset[fileindex]) {
 232                         ;
 233                 }
 234                 posting.fileindex = --fileindex;
 235                 posting.type = *++s;
 236                 ++s;
 237                 if (*s != '\n') {
 238                         num = *++s - '!';
 239                         while (*++s != '\n') {
 240                                 num = BASE * num + *s - '!';
 241                         }
 242                         posting.fcnoffset = num;
 243                 }
 244                 else {
 245                         posting.fcnoffset = 0;
 246                 }
 247                 *postptr++ = posting;
 248 #if DEBUG
 249                 printf("%ld %ld %ld %ld\n", posting.fileindex,
 250                        posting.fcnoffset, posting.lineoffset, posting.type);
 251                 fflush(stdout);
 252 #endif
 253         }
 254         if (!invnewterm()) {
 255                 return(0);
 256         }
 257         /* now clean up final block  */
 258         logicalblk.invblk[0] = numinvitems;
 259         /* loops pointer around to start */
 260         logicalblk.invblk[1] = 0;
 261         logicalblk.invblk[2] = numlogblk - 1;
 262         if (fwrite(&logicalblk, sizeof(t_logicalblk), 1, outfile) == 0) {
 263                 goto cannotwrite;
 264         }
 265         numlogblk++;
 266         /* write out block to save space. what in it doesn't matter */
 267         if (fwrite(&logicalblk, sizeof(t_logicalblk), 1, outfile) == 0) {
 268                 goto cannotwrite;
 269         }
 270         /* finish up the super finger */
 271         *SUPINT = numlogblk;
 272         /* add to the offsets the size of the offset pointers */
 273         intptr = (SUPINT + 1);
 274         i = (char *)supint - (char *)SUPINT;
 275         while (intptr < supint)
 276                 *intptr++ += i;
 277         /* write out the offsets (1 for the N at start) and the super finger */
 278         if (fwrite(SUPINT, sizeof(*SUPINT), numlogblk + 1, outfile) == 0 ||
 279             fwrite(SUPFING, 1, supfing - SUPFING, outfile) == 0) {
 280                 goto cannotwrite;
 281         }
 282         /* save the size for reference later */
 283         nextsupfing = sizeof(long) + sizeof(long) * numlogblk + (supfing - SUPFING);
 284         /* make sure the file ends at a logical block boundary.  This is
 285         necessary for invinsert to correctly create extended blocks
 286          */
 287         i = nextsupfing % sizeof(t_logicalblk);
 288         /* write out junk to fill log blk */
 289         if (fwrite(temp, sizeof(t_logicalblk) - i, 1, outfile) == 0 ||
 290             fflush(outfile) == EOF) {   /* rewind doesn't check for write failure */
 291                 goto cannotwrite;
 292         }
 293         /* write the control area */
 294         rewind(outfile);
 295         param.version = FMTVERSION;
 296         param.filestat = 0;
 297         param.sizeblk = sizeof(t_logicalblk);
 298         param.startbyte = (numlogblk + 1) * sizeof(t_logicalblk) + BUFSIZ;;
 299         param.supsize = nextsupfing;
 300         param.cntlsize = BUFSIZ;
 301         param.share = 0;
 302         if (fwrite(&param, sizeof(param), 1, outfile) == 0) {
 303                 goto cannotwrite;
 304         }
 305         for (i = 0; i < 10; i++)        /* for future use */
 306                 if (fwrite(&zerolong, sizeof(zerolong), 1, outfile) == 0) {
 307                         goto cannotwrite;
 308                 }
 309
 310         /* make first block loop backwards to last block */
 311         if (fflush(outfile) == EOF) {   /* fseek doesn't check for write failure */
 312                 goto cannotwrite;
 313         }
 314         /* get to second word first block */
 315         fseek(outfile, BUFSIZ + 2 * sizeof(long), SEEK_SET);
 316         tlong = numlogblk - 1;
 317         if (fwrite(&tlong, sizeof(tlong), 1, outfile) == 0 ||
 318             fclose(outfile) == EOF) {
 319         cannotwrite:
 320                 invcannotwrite(invname);
 321                 return(0);
 322         }
 323         if (fclose(fpost) == EOF) {
 324                 invcannotwrite(postingfile);
 325                 return(0);
 326         }
 327         --totterm;      /* don't count null term */
 328 #if STATS
 329         printf("logical blocks = %d, postings = %ld, terms = %ld, max term length = %d\n",
 330             numlogblk, totpost, totterm, maxtermlen);
 331         if (showzipf) {
 332                 printf("\n*************   ZIPF curve  ****************\n");
 333                 for (j = ZIPFSIZE; j > 1; j--)
 334                         if (zipf[j])
 335                                 break;
 336                 for (i = 1; i < j; ++i) {
 337                         printf("%3d -%6d ", i, zipf[i]);
 338                         if (i % 6 == 0) putchar('\n');
 339                 }
 340                 printf(">%d-%6d\n", ZIPFSIZE, zipf[0]);
 341         }
 342 #endif
 343         /* free all malloc'd memory */
 344         free(POST);
 345         free(SUPFING);
 346         free(SUPINT);
 347         return(totterm);
 348 }
 349
 350 /* add a term to the data base */
 351
 352 static int
 353 invnewterm(void)
 354 {
 355     int backupflag, i, j, holditems, gooditems, howfar;
 356     unsigned int maxback, len, numwilluse, wdlen;
 357     char        *tptr, *tptr3;
 358
 359     union {
 360         unsigned long   packword[2];
 361         ENTRY           e;
 362     } iteminfo;
 363
 364     gooditems = 0;              /* initialize, to avoid warning */
 365     totterm++;
 366 #if STATS
 367     /* keep zipfian info on the distribution */
 368     if (numpost <= ZIPFSIZE)
 369         zipf[numpost]++;
 370     else
 371         zipf[0]++;
 372 #endif
 373     len = strlen(thisterm);
 374     /* length of term rounded up to long boundary */
 375     wdlen = (len + (sizeof(long) - 1)) / sizeof(long);
 376     /* each term needs 2 longs for its iteminfo and
 377      * 1 long for its offset */
 378     numwilluse = (wdlen + 3) * sizeof(long);
 379     /* new block if at least 1 item in block */
 380     if (numinvitems && numwilluse + amtused > sizeof(t_logicalblk)) {
 381         /* set up new block */
 382         if (supfing + 500 > SUPFING + supersize) {
 383             i = supfing - SUPFING;
 384             supersize += 20000;
 385             if ((SUPFING = (char *)realloc(SUPFING, supersize)) == NULL) {
 386                 invcannotalloc(supersize);
 387                 return(0);
 388             }
 389             supfing = i + SUPFING;
 390 #if DEBUG
 391             printf("reallocated superfinger space to %d, totpost=%ld\n",
 392                    supersize, totpost);
 393 #endif
 394         }
 395         /* check that room for the offset as well */
 396         /* FIXME HBB: magic number alert (10) */
 397         if ((numlogblk + 10) > supintsize) {
 398             i = supint - SUPINT;
 399             supintsize += SUPERINC;
 400             if ((SUPINT = realloc(SUPINT, supintsize * sizeof(long))) == NULL) {
 401                 invcannotalloc(supintsize * sizeof(long));
 402                 return(0);
 403             }
 404             supint = i + SUPINT;
 405 #if DEBUG
 406             printf("reallocated superfinger offset to %d, totpost = %ld\n",
 407                    supintsize * sizeof(long), totpost);
 408 #endif
 409         }
 410         /* See if backup is efficatious  */
 411         backupflag = 0;
 412         maxback = (int) strlen(thisterm) / 10;
 413         holditems = numinvitems;
 414         if (maxback > numinvitems)
 415             maxback = numinvitems - 2;
 416         howfar = 0;
 417         while (maxback-- > 1) {
 418             howfar++;
 419             iteminfo.packword[0] =
 420                 logicalblk.invblk[--holditems * 2 + (sizeof(long) - 1)];
 421             if ((i = iteminfo.e.size / 10) < maxback) {
 422                 maxback = i;
 423                 backupflag = howfar;
 424                 gooditems = holditems;
 425             }
 426         }
 427         /* see if backup will occur  */
 428         if (backupflag) {
 429             numinvitems = gooditems;
 430         }
 431         logicalblk.invblk[0] = numinvitems;
 432         /* set forward pointer pointing to next */
 433         logicalblk.invblk[1] = numlogblk + 1;
 434         /* set back pointer to last block */
 435         logicalblk.invblk[2] = numlogblk - 1;
 436         if (fwrite(logicalblk.chrblk, 1, sizeof(t_logicalblk), outfile) == 0) {
 437             invcannotwrite(indexfile);
 438             return(0);
 439         }
 440         /* 3 longs needed for: numinvitems, next block, and previous block */
 441         amtused = 3 * sizeof(long);
 442         numlogblk++;
 443         /* check if had to back up, if so do it */
 444         if (backupflag) {
 445             char *tptr2;
 446
 447             /* find out where the end of the new block is */
 448             iteminfo.packword[0] = logicalblk.invblk[numinvitems*2+1];
 449             tptr3 = logicalblk.chrblk + iteminfo.e.offset;
 450             /* move the index for this block */
 451             for (i = 3; i <= (backupflag * 2 + 2); i++)
 452                 logicalblk.invblk[i] = logicalblk.invblk[numinvitems*2+i];
 453             /* move the word into the super index */
 454             iteminfo.packword[0] = logicalblk.invblk[3];
 455             iteminfo.packword[1] = logicalblk.invblk[4];
 456             tptr2 = logicalblk.chrblk + iteminfo.e.offset;
 457             strncpy(supfing, tptr2, (int) iteminfo.e.size);
 458             *(supfing + iteminfo.e.size) = '\0';
 459 #if DEBUG
 460             printf("backup %d at term=%s to term=%s\n",
 461                    backupflag, thisterm, supfing);
 462 #endif
 463             *supint++ = nextsupfing;
 464             nextsupfing += strlen(supfing) + 1;
 465             supfing += strlen(supfing) + 1;
 466             /* now fix up the logical block */
 467             tptr = logicalblk.chrblk + lastinblk;
 468             lastinblk = sizeof(t_logicalblk);
 469             tptr2 = logicalblk.chrblk + lastinblk;
 470             j = tptr3 - tptr;
 471             while (tptr3 > tptr)
 472                 *--tptr2 = *--tptr3;
 473             lastinblk -= j;
 474             amtused += ((2 * sizeof(long)) * backupflag + j);
 475             for (i = 3; i < (backupflag * 2 + 2); i += 2) {
 476                 iteminfo.packword[0] = logicalblk.invblk[i];
 477                 iteminfo.e.offset += (tptr2 - tptr3);
 478                 logicalblk.invblk[i] = iteminfo.packword[0];
 479             }
 480             numinvitems = backupflag;
 481         } else { /* no backup needed */
 482             numinvitems = 0;
 483             lastinblk = sizeof(t_logicalblk);
 484             /* add new term to superindex */
 485             strcpy(supfing, thisterm);
 486             supfing += strlen(thisterm) + 1;
 487             *supint++ = nextsupfing;
 488             nextsupfing += strlen(thisterm) + 1;
 489         }
 490     }
 491     /* HBB 20010501: Fixed bug by replacing magic number '8' by
 492      * what it actually represents. */
 493     lastinblk -= (numwilluse - 2 * sizeof(long));
 494     iteminfo.e.offset = lastinblk;
 495     iteminfo.e.size = len;
 496     iteminfo.e.space = 0;
 497     iteminfo.e.post = numpost;
 498     strncpy(logicalblk.chrblk + lastinblk, thisterm, len);
 499     amtused += numwilluse;
 500     logicalblk.invblk[(lastinblk/sizeof(long))+wdlen] = nextpost;
 501     if ((i = postptr - POST) > 0) {
 502         if (fwrite(POST, sizeof(POSTING), i, fpost) == 0) {
 503             invcannotwrite(postingfile);
 504             return(0);
 505         }
 506         nextpost += i * sizeof(POSTING);
 507     }
 508     logicalblk.invblk[3+2*numinvitems++] = iteminfo.packword[0];
 509     logicalblk.invblk[2+2*numinvitems] = iteminfo.packword[1];
 510     return(1);
 511 }
 512
 513 /*
 514  * If 'invname' ends with the 'from' substring, it is replaced inline with the
 515  * 'to' substring (which must be of the exact same length), and the function
 516  * returns 0. Otherwise, returns -1.
 517  */
 518
 519 static int
 520 invflipname(char * invname, const char *from, const char *to)
 521 {
 522         char *temp, *i = NULL;
 523
 524         assert(strlen(from) == strlen(to));
 525
 526         temp = invname - 1;
 527         while( (temp = strstr(temp + 1, from)))
 528                 i = temp;
 529         if (!i || i[strlen(from)] != '\0')
 530                 return -1;
 531         while(*to)
 532                 *i++ = *to++;
 533         return 0;
 534 }
 535
 536 int
 537 invopen(INVCONTROL *invcntl, char *invname, char *invpost, int stat)
 538 {
 539         int     read_index;
 540
 541         if ((invcntl->invfile = vpfopen(invname, ((stat == 0) ? "rb" : "r+b"))) == NULL) {
 542                 /* If db created without '-f', but now invoked with '-f cscope.out',
 543                  * we need to check for 'cscope.in.out', rather than 'cscope.out.in':
 544                  * I.e, hack around our own violation of the inverse db naming convention */
 545                 if (!invflipname(invname, INVNAME2, INVNAME)) {
 546                         if ((invcntl->invfile = vpfopen(invname, ((stat == 0) ? "rb" : "r+b"))))
 547                                 goto openedinvname;
 548                         invflipname(invname, INVNAME, INVNAME2); /* change back for err msg */
 549                 }
 550                 /* more silliness: if you create the db with '-f cscope', then try to open
 551                  * it without '-f cscope', you'll fail unless we check for 'cscope.out.in'
 552                  * here. */
 553                 else if (!invflipname(invname, INVNAME, INVNAME2)) {
 554                         if ((invcntl->invfile = vpfopen(invname, ((stat == 0) ? "rb" : "r+b"))))
 555                                 goto openedinvname;
 556                         invflipname(invname, INVNAME2, INVNAME); /* change back for err msg */
 557                 }
 558                 invcannotopen(invname);
 559                 return(-1);
 560         }
 561 openedinvname:
 562         if (fread(&invcntl->param, sizeof(invcntl->param), 1, invcntl->invfile) == 0) {
 563                 fprintf(stderr, "%s: empty inverted file\n", argv0);
 564                 goto closeinv;
 565         }
 566         if (invcntl->param.version != FMTVERSION) {
 567                 fprintf(stderr, "%s: cannot read old index format; use -U option to force database to rebuild\n", argv0);
 568                 goto closeinv;
 569         }
 570         assert(invcntl->param.sizeblk == sizeof(t_logicalblk));
 571
 572         if (stat == 0 && invcntl->param.filestat == INVALONE) {
 573                 fprintf(stderr, "%s: inverted file is locked\n", argv0);
 574                 goto closeinv;
 575         }
 576         if ((invcntl->postfile = vpfopen(invpost, ((stat == 0) ? "rb" : "r+b"))) == NULL) {
 577                 /* exact same naming convention hacks as above for invname */
 578                 if (!invflipname(invpost, INVPOST2, INVPOST)) {
 579                         if ((invcntl->postfile = vpfopen(invpost, ((stat == 0) ? "rb" : "r+b"))))
 580                                 goto openedinvpost;
 581                         invflipname(invpost, INVPOST, INVPOST2); /* change back for err msg */
 582                 } else if (!invflipname(invpost, INVPOST, INVPOST2)) {
 583                         if ((invcntl->postfile = vpfopen(invpost,((stat == 0)?"rb":"r+b"))))
 584                                 goto openedinvpost;
 585                         invflipname(invpost, INVPOST2, INVPOST); /* change back for err msg */
 586                 }
 587                 invcannotopen(invpost);
 588                 goto closeinv;
 589         }
 590 openedinvpost:
 591         /* allocate core for a logical block  */
 592         if ((invcntl->logblk = malloc((unsigned) invcntl->param.sizeblk)) == NULL) {
 593                 invcannotalloc((unsigned) invcntl->param.sizeblk);
 594                 goto closeboth;
 595         }
 596         /* allocate for and read in superfinger  */
 597         read_index = 1;
 598         invcntl->iindex = NULL;
 599 #if SHARE
 600         if (invcntl->param.share == 1) {
 601                 key_t shm_key;
 602                 struct shmid_ds shm_buf;
 603                 int     shm_id;
 604
 605                 /* see if the shared segment exists */
 606                 shm_key = ftok(invname, 2);
 607                 shm_id = shmget(shm_key, 0, 0);
 608                 /* Failure simply means (hopefully) that segment doesn't exists */
 609                 if (shm_id == -1) {
 610                         /* Have to give general write permission due to AMdahl not having protected segments */
 611                         shm_id = shmget(shm_key, invcntl->param.supsize + sizeof(long), IPC_CREAT | 0666);
 612                         if (shm_id == -1)
 613                                 perror("Could not create shared memory segment");
 614                 } else
 615                         read_index = 0;
 616
 617                 if (shm_id != -1) {
 618                         invcntl->iindex = shmat(shm_id, 0, ((read_index) ? 0 : SHM_RDONLY));
 619                         if (invcntl->iindex == (char *)ERR) {
 620                                 fprintf(stderr, "%s: shared memory link failed\n", argv0);
 621                                 invcntl->iindex = NULL;
 622                                 read_index = 1;
 623                         }
 624                 }
 625         }
 626 #endif
 627         if (invcntl->iindex == NULL)
 628                 /* FIXME HBB: magic number alert (4) */
 629                 invcntl->iindex = malloc((unsigned) invcntl->param.supsize
 630                                          + 4 *sizeof(long));
 631         if (invcntl->iindex == NULL) {
 632                 invcannotalloc((unsigned) invcntl->param.supsize);
 633                 free(invcntl->logblk);
 634                 goto closeboth;
 635         }
 636         if (read_index) {
 637                 fseek(invcntl->invfile, invcntl->param.startbyte, SEEK_SET);
 638                 fread(invcntl->iindex, (int) invcntl->param.supsize, 1,
 639                       invcntl->invfile);
 640         }
 641         invcntl->numblk = -1;
 642         if (boolready() == -1) {
 643         closeboth:
 644                 fclose(invcntl->postfile);
 645         closeinv:
 646                 fclose(invcntl->invfile);
 647                 return(-1);
 648         }
 649         /* write back out the control block if anything changed */
 650         invcntl->param.filestat = stat;
 651         if (stat > invcntl->param.filestat ) {
 652                 rewind(invcntl->invfile);
 653                 fwrite(&invcntl->param, sizeof(invcntl->param), 1, invcntl->invfile);
 654         }
 655         return(1);
 656 }
 657
 658 /** invclose must be called to wrap things up and deallocate core  **/
 659 void
 660 invclose(INVCONTROL *invcntl)
 661 {
 662         /* write out the control block in case anything changed */
 663         if (invcntl->param.filestat > 0) {
 664                 invcntl->param.filestat = 0;
 665                 rewind(invcntl->invfile);
 666                 fwrite(&invcntl->param, 1,
 667                     sizeof(invcntl->param), invcntl->invfile);
 668         }
 669         if (invcntl->param.filestat == INVALONE) {
 670                 /* write out the super finger */
 671                 fseek(invcntl->invfile, invcntl->param.startbyte, SEEK_SET);
 672                 fwrite(invcntl->iindex, 1,
 673                        (int) invcntl->param.supsize, invcntl->invfile);
 674         }
 675         fclose(invcntl->invfile);
 676         fclose(invcntl->postfile);
 677 #if SHARE
 678         if (invcntl->param.share > 0) {
 679                 shmdt(invcntl->iindex);
 680                 invcntl->iindex = NULL;
 681         }
 682 #endif
 683         if (invcntl->iindex != NULL)
 684                 free(invcntl->iindex);
 685         free(invcntl->logblk);
 686 }
 687
 688 /** invstep steps the inverted file forward one item **/
 689 static void
 690 invstep(INVCONTROL *invcntl)
 691 {
 692         if (invcntl->keypnt < (invcntl->logblk->invblk[0] - 1)) {
 693                 invcntl->keypnt++;
 694                 return;
 695         }
 696
 697         /* move forward a block else wrap */
 698         invcntl->numblk = invcntl->logblk->invblk[1]; /* was: *(int *)(invcntl->logblk + sizeof(long))*/
 699
 700         /* now read in the block  */
 701         fseek(invcntl->invfile,
 702               invcntl->numblk*invcntl->param.sizeblk + invcntl->param.cntlsize,
 703               SEEK_SET);
 704         fread(invcntl->logblk, (int) invcntl->param.sizeblk, 1,
 705               invcntl->invfile);
 706         invcntl->keypnt = 0;
 707 }
 708
 709 /** invforward moves forward one term in the inverted file  **/
 710 int
 711 invforward(INVCONTROL *invcntl)
 712 {
 713         invstep(invcntl);
 714         /* skip things with 0 postings */
 715         /* FIXME HBB: magic number alert! (3) */
 716         while (((ENTRY * )(invcntl->logblk->invblk + 3) + invcntl->keypnt)->post == 0) {
 717                 invstep(invcntl);
 718         }
 719         /* Check for having wrapped - reached start of inverted file! */
 720         if ((invcntl->numblk == 0) && (invcntl->keypnt == 0))
 721                 return(0);
 722         return(1);
 723 }
 724
 725 /**  invterm gets the present term from the present logical block  **/
 726 long
 727 invterm(INVCONTROL *invcntl, char *term)
 728 {
 729         ENTRY * entryptr;
 730
 731         /* FIXME HBB: magic number alert! (3) */
 732         entryptr = (ENTRY *)(invcntl->logblk->invblk + 3) + invcntl->keypnt;
 733         strncpy(term, invcntl->logblk->chrblk + entryptr->offset,
 734                        (int) entryptr->size);
 735         *(term + entryptr->size) = '\0';
 736         return(entryptr->post);
 737 }
 738
 739 /** invfind searches for an individual item in the inverted file  **/
 740 long
 741 invfind(INVCONTROL *invcntl, char *searchterm) /* term being searched for  */
 742 {
 743         int     imid, ilow, ihigh;
 744         long    num;
 745         int     i;
 746         unsigned long   *intptr, *intptr2;
 747         ENTRY *entryptr;
 748
 749         /* make sure it is initialized via invready  */
 750         if (invcntl->invfile == 0)
 751                 return(-1L);
 752
 753         /* now search for the appropriate finger block */
 754         intptr = (unsigned long *)invcntl->iindex;
 755
 756         ilow = 0;
 757         ihigh = *intptr++ - 1;
 758         while (ilow <= ihigh) {
 759                 imid = (ilow + ihigh) / 2;
 760                 intptr2 = intptr + imid;
 761                 i = strcmp(searchterm, (invcntl->iindex + *intptr2));
 762                 if (i < 0)
 763                         ihigh = imid - 1;
 764                 else if (i > 0)
 765                         ilow = ++imid;
 766                 else {
 767                         ilow = imid + 1;
 768                         break;
 769                 }
 770         }
 771         /* be careful about case where searchterm is after last in this block  */
 772         imid = (ilow) ? ilow - 1 : 0;
 773
 774         /* fetch the appropriate logical block if not in core  */
 775         /* note always fetch it if the file is busy */
 776         if ((imid != invcntl->numblk) || (invcntl->param.filestat >= INVBUSY)) {
 777                 fseek(invcntl->invfile,
 778                       (imid*invcntl->param.sizeblk) + invcntl->param.cntlsize,
 779                       SEEK_SET);
 780                 invcntl->numblk = imid;
 781                 fread(invcntl->logblk, (int)invcntl->param.sizeblk, 1,
 782                       invcntl->invfile);
 783         }
 784
 785 srch_ext:
 786         /* now find the term in this block. tricky this  */
 787         intptr = (unsigned long *) invcntl->logblk->invblk;
 788
 789         ilow = 0;
 790         ihigh = *intptr - 1;
 791         intptr += 3;
 792         num = 0;
 793         while (ilow <= ihigh) {
 794                 imid = (ilow + ihigh) / 2;
 795                 entryptr = (ENTRY *)intptr + imid;
 796                 i = strncmp(searchterm, invcntl->logblk->chrblk + entryptr->offset,
 797                     (int) entryptr->size );
 798                 if (i == 0)
 799                         i = strlen(searchterm) - entryptr->size;
 800                 if (i < 0)
 801                         ihigh = imid - 1;
 802                 else if (i > 0)
 803                         ilow = ++imid;
 804                 else {
 805                         num = entryptr->post;
 806                         break;
 807                 }
 808         }
 809         /* be careful about case where searchterm is after last in this block  */
 810         if (imid >= invcntl->logblk->invblk[0]) {
 811                 invcntl->keypnt = invcntl->logblk->invblk[0];
 812                 invstep(invcntl);
 813                 /* note if this happens the term could be in extended block */
 814                 if (invcntl->param.startbyte < invcntl->numblk * invcntl->param.sizeblk)
 815                         goto srch_ext;
 816         } else
 817                 invcntl->keypnt = imid;
 818         return(num);
 819 }
 820
 821 #if DEBUG
 822
 823 /** invdump dumps the block the term parameter is in **/
 824 void
 825 invdump(INVCONTROL *invcntl, char *term)
 826 {
 827         long    i, j, n, *longptr;
 828         ENTRY * entryptr;
 829         char    temp[512], *ptr;
 830
 831         /* dump superindex if term is "-"  */
 832         if (*term == '-') {
 833                 j = atoi(term + 1);
 834                 longptr = (long *)invcntl->iindex;
 835                 n = *longptr++;
 836                 printf("Superindex dump, num blocks=%ld\n", n);
 837                 longptr += j;
 838                 while ((longptr <= ((long *)invcntl->iindex) + n) && invbreak == 0) {
 839                         printf("%2ld  %6ld %s\n", j++, *longptr, invcntl->iindex + *longptr);
 840                         longptr++;
 841                 }
 842                 return;
 843         } else if (*term == '#') {
 844                 j = atoi(term + 1);
 845                 /* fetch the appropriate logical block */
 846                 invcntl->numblk = j;
 847                 fseek(invcntl->invfile,
 848                       (j * invcntl->param.sizeblk) + invcntl->param.cntlsize,
 849                       SEEK_SET);
 850                 fread(invcntl->logblk, (int) invcntl->param.sizeblk, 1,
 851                       invcntl->invfile);
 852         } else
 853                 i = abs((int) invfind(invcntl, term));
 854         longptr = invcntl->logblk->invblk;
 855         n = *longptr++;
 856         printf("Entry term to invdump=%s, postings=%ld, forwrd ptr=%ld, back ptr=%ld\n"
 857             , term, i, *(longptr), *(longptr + 1));
 858         /* FIXME HBB: magic number alert! (3) */
 859         entryptr = (ENTRY *) (invcntl->logblk->invblk + 3);
 860         printf("%ld terms in this block, block=%ld\n", n, invcntl->numblk);
 861         printf("\tterm\t\t\tposts\tsize\toffset\tspace\t1st word\n");
 862         for (j = 0; j < n && invbreak == 0; j++) {
 863                 ptr = invcntl->logblk->chrblk + entryptr->offset;
 864                 strncpy(temp, ptr, (int) entryptr->size);
 865                 temp[entryptr->size] = '\0';
 866                 ptr += (sizeof(long) * (long)((entryptr->size + (sizeof(long) - 1)) / sizeof(long)));
 867                 printf("%2ld  %-24s\t%5ld\t%3d\t%d\t%d\t%ld\n", j, temp, entryptr->post,
 868                     entryptr->size, entryptr->offset, entryptr->space,
 869                     *(long *)ptr);
 870                 entryptr++;
 871         }
 872 }
 873 #endif
 874
 875 static int
 876 boolready(void)
 877 {
 878         numitems = 0;
 879         if (item1 != NULL)
 880                 free(item1);
 881         setsize1 = SETINC;
 882         if ((item1 = malloc(SETINC * sizeof(POSTING))) == NULL) {
 883                 invcannotalloc(SETINC);
 884                 return(-1);
 885         }
 886         if (item2 != NULL)
 887                 free(item2);
 888         setsize2 = SETINC;
 889         if ((item2 = malloc(SETINC * sizeof(POSTING))) == NULL) {
 890                 invcannotalloc(SETINC);
 891                 return(-1);
 892         }
 893         item = item1;
 894         enditem = item;
 895         return(0);
 896 }
 897
 898 void
 899 boolclear(void)
 900 {
 901         numitems = 0;
 902         item = item1;
 903         enditem = item;
 904 }
 905
 906 POSTING *
 907 boolfile(INVCONTROL *invcntl, long *num, int boolarg)
 908 {
 909         ENTRY   *entryptr;
 910         FILE    *file;
 911         void    *ptr;
 912         unsigned long   *ptr2;
 913         POSTING *newitem = NULL; /* initialize, to avoid warning */
 914         POSTING posting;
 915         unsigned u;
 916         POSTING *newsetp = NULL, *set1p;
 917         long    newsetc, set1c, set2c;
 918
 919         /* FIXME HBB: magic number alert! (3) */
 920         entryptr = (ENTRY *) (invcntl->logblk->invblk + 3) + invcntl->keypnt;
 921         ptr = invcntl->logblk->chrblk + entryptr->offset;
 922         ptr2 = ((unsigned long *) ptr) + (entryptr->size + (sizeof(long) - 1)) / sizeof(long);
 923         *num = entryptr->post;
 924         switch (boolarg) {
 925         case BOOL_OR:
 926         case NOT:
 927                 if (*num == 0) {
 928                         *num = numitems;
 929                         return(item);
 930                 }
 931         }
 932         /* make room for the new set */
 933         u = 0;
 934         switch (boolarg) {
 935         case AND:
 936         case NOT:
 937                 newsetp = item;
 938                 break;
 939
 940         case BOOL_OR:
 941                 u = enditem - item;
 942                 /* FALLTHROUGH */
 943         case REVERSENOT:
 944                 u += *num;
 945                 if (item == item2) {
 946                         if (u > setsize1) {
 947                                 u += SETINC;
 948                                 if ((item1 = realloc(
 949                                     item1, u * sizeof(POSTING))) == NULL) {
 950                                         goto cannotalloc;
 951                                 }
 952                                 setsize1 = u;
 953                         }
 954                         newitem = item1;
 955                 }
 956                 else {
 957                         if (u > setsize2) {
 958                                 u += SETINC;
 959                                 if ((item2 = realloc(
 960                                     item2, u * sizeof(POSTING))) == NULL) {
 961                                 cannotalloc:
 962                                         invcannotalloc(u * sizeof(POSTING));
 963                                         boolready();
 964                                         *num = -1;
 965                                         return(NULL);
 966                                 }
 967                                 setsize2 = u;
 968                         }
 969                         newitem = item2;
 970                 }
 971 #if 0 /* this write is only need by commented-out code later */
 972                 set1p = item;
 973 #endif
 974                 newsetp = newitem;
 975         }
 976         file = invcntl->postfile;
 977         fseek(file, *ptr2, SEEK_SET);
 978         fread(&posting, sizeof(posting), 1, file);
 979         newsetc = 0;
 980         switch (boolarg) {
 981         case BOOL_OR:
 982                 /* while something in both sets */
 983                 set1p = item;
 984                 newsetp = newitem;
 985                 for (set1c = 0, set2c = 0;
 986                     set1c < numitems && set2c < *num; newsetc++) {
 987                         if (set1p->lineoffset < posting.lineoffset) {
 988                                 *newsetp++ = *set1p++;
 989                                 set1c++;
 990                         }
 991                         else if (set1p->lineoffset > posting.lineoffset) {
 992                                 *newsetp++ = posting;
 993                                 fread(&posting, (int) sizeof(posting), 1, file);
 994                                 set2c++;
 995                         }
 996                         else if (set1p->type < posting.type) {
 997                                 *newsetp++ = *set1p++;
 998                                 set1c++;
 999                         }
1000                         else if (set1p->type > posting.type) {
1001                                 *newsetp++ = posting;
1002                                 fread(&posting, (int) sizeof(posting), 1, file);
1003                                 set2c++;
1004                         }
1005                         else {  /* identical postings */
1006                                 *newsetp++ = *set1p++;
1007                                 set1c++;
1008                                 fread(&posting, (int) sizeof(posting), 1, file);
1009                                 set2c++;
1010                         }
1011                 }
1012                 /* find out what ran out and move the rest in */
1013                 if (set1c < numitems) {
1014                         newsetc += numitems - set1c;
1015                         while (set1c++ < numitems) {
1016                                 *newsetp++ = *set1p++;
1017                         }
1018                 } else {
1019                         while (set2c++ < *num) {
1020                                 *newsetp++ = posting;
1021                                 newsetc++;
1022                                 fread(&posting, (int) sizeof(posting), 1, file);
1023                         }
1024                 }
1025                 item = newitem;
1026                 break; /* end of BOOL_OR */
1027 #if 0
1028         case AND:
1029                 for (set1c = 0, set2c = 0; set1c < numitems && set2c < *num; ) {
1030                         if (set1p->lineoffset < posting.lineoffset) {
1031                                 set1p++;
1032                                 set1c++;
1033                         }
1034                         else if (set1p->lineoffset > posting.lineoffset) {
1035                                 fread(&posting, (int) sizeof(posting), 1, file);
1036                                 set2c++;
1037                         }
1038                         else if (set1p->type < posting.type)  {
1039                                 *set1p++;
1040                                 set1c++;
1041                         }
1042                         else if (set1p->type > posting.type) {
1043                                 fread(&posting, (int) sizeof(posting), 1, file);
1044                                 set2c++;
1045                         }
1046                         else {  /* identical postings */
1047                                 *newsetp++ = *set1p++;
1048                                 newsetc++;
1049                                 set1c++;
1050                                 fread(&posting, (int) sizeof(posting), 1, file);
1051                                 set2c++;
1052                         }
1053                 }
1054                 break; /* end of AND */
1055
1056         case NOT:
1057                 for (set1c = 0, set2c = 0; set1c < numitems && set2c < *num; ) {
1058                         if (set1p->lineoffset < posting.lineoffset) {
1059                                 *newsetp++ = *set1p++;
1060                                 newsetc++;
1061                                 set1c++;
1062                         }
1063                         else if (set1p->lineoffset > posting.lineoffset) {
1064                                 fread(&posting, (int) sizeof(posting), 1, file);
1065                                 set2c++;
1066                         }
1067                         else if (set1p->type < posting.type) {
1068                                 *newsetp++ = *set1p++;
1069                                 newsetc++;
1070                                 set1c++;
1071                         }
1072                         else if (set1p->type > posting.type) {
1073                                 fread(&posting, (int) sizeof(posting), 1, file);
1074                                 set2c++;
1075                         }
1076                         else {  /* identical postings */
1077                                 set1c++;
1078                                 set1p++;
1079                                 fread(&posting, (int) sizeof(posting), 1, file);
1080                                 set2c++;
1081                         }
1082                 }
1083                 newsetc += numitems - set1c;
1084                 while (set1c++ < numitems) {
1085                         *newsetp++ = *set1p++;
1086                 }
1087                 break; /* end of NOT */
1088
1089         case REVERSENOT:  /* core NOT incoming set */
1090                 for (set1c = 0, set2c = 0; set1c < numitems && set2c < *num; ) {
1091                         if (set1p->lineoffset < posting.lineoffset) {
1092                                 set1p++;
1093                                 set1c++;
1094                         }
1095                         else if (set1p->lineoffset > posting.lineoffset) {
1096                                 *newsetp++ = posting;
1097                                 fread(&posting, (int) sizeof(posting), 1, file);
1098                                 set2c++;
1099                         }
1100                         else if (set1p->type < posting.type) {
1101                                 set1p++;
1102                                 set1c++;
1103                         }
1104                         else if (set1p->type > posting.type) {
1105                                 *newsetp++ = posting;
1106                                 fread(&posting, (int) sizeof(posting), 1, file);
1107                                 set2c++;
1108                         }
1109                         else {  /* identical postings */
1110                                 set1c++;
1111                                 set1p++;
1112                                 fread(&posting, (int) sizeof(posting), 1, file);
1113                                 set2c++;
1114                         }
1115                 }
1116                 while (set2c++ < *num) {
1117                         *newsetp++ = posting;
1118                         newsetc++;
1119                         fread(&posting, (int) sizeof(posting), 1, file);
1120                 }
1121                 item = newitem;
1122                 break; /* end of REVERSENOT  */
1123 #endif
1124         }
1125         numitems = newsetc;
1126         *num = newsetc;
1127         enditem = (POSTING *) newsetp;
1128         return((POSTING *) item);
1129 }
1130
1131 #if 0
1132 POSTING *
1133 boolsave(int clear)             /* flag about whether to clear core  */
1134 {
1135         int     i;
1136         POSTING *ptr;
1137         POSTING *oldstuff, *newstuff;
1138
1139         if (numitems == 0) {
1140                 if (clear)
1141                         boolclear();
1142                 return(NULL);
1143         }
1144         /* if clear then give them what we have and use boolready to realloc  */
1145         if (clear) {
1146                 ptr = item;
1147                 /* free up the space we didn't give them */
1148                 if (item == item1)
1149                         item1 = NULL;
1150                 else
1151                         item2 = NULL;
1152                 boolready();
1153                 return(ptr);
1154         }
1155         i = (enditem - item) * sizeof(POSTING) + 100;
1156         if ((ptr = malloc(i))r == NULL) {
1157                 invcannotalloc(i);
1158                 return(ptr);
1159         }
1160         /* move present set into place  */
1161         oldstuff = item;
1162         newstuff = ptr;
1163         while (oldstuff < enditem)
1164                 *newstuff++ = *oldstuff++;
1165         return(ptr);
1166 }
1167 #endif
1168
1169 static void
1170 invcannotalloc(unsigned n)
1171 {
1172         fprintf(stderr, "%s: cannot allocate %u bytes\n", argv0, n);
1173 }
1174
1175 static void
1176 invcannotopen(char *file)
1177 {
1178         fprintf(stderr, "%s: cannot open file %s\n", argv0, file);
1179 }
1180
1181 static void
1182 invcannotwrite(char *file)
1183 {
1184         perror(argv0);  /* must be first to preserve errno */
1185         fprintf(stderr, "%s: write to file %s failed\n", argv0, file);
1186 }