home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / compsrcs / misc / volume02 / qndxr < prev    next >
Encoding:
Internet Message Format  |  1991-08-27  |  51.1 KB
  1. From mipos3!omepd!uoregon!hp-pcd!hplabs!decwrl!labrea!aurora!amelia!ames!necntc!ncoast!allbery Tue Feb  9 21:18:08 PST 1988
  2. Article 291 of comp.sources.misc:
  3. Path: td2cad!mipos3!omepd!uoregon!hp-pcd!hplabs!decwrl!labrea!aurora!amelia!ames!necntc!ncoast!allbery
  4. From: science@nems.ARPA (Mark Zimmermann)
  5. Newsgroups: comp.sources.misc
  6. Subject: v02i041: qndxr - Inverted index builder for text files
  7. Message-ID: <7176@ncoast.UUCP>
  8. Date: 3 Feb 88 02:08:40 GMT
  9. Sender: allbery@ncoast.UUCP
  10. Lines: 1665
  11. Approved: allbery@ncoast.UUCP
  12. X-Archive: comp.sources.misc/8802/4
  13. Comp.sources.misc: Volume 2, Issue 41
  14. Submitted-By: "Mark Zimmerman" <science@nems.ARPA>
  15. Archive-Name: qndxr
  16.  
  17. Comp.sources.misc: Volume 2, Issue 41
  18. Submitted-By: "Mark Zimmerman" <science@nems.ARPA>
  19. Archive-Name: qndxr
  20.  
  21. [Yes, indeed, another un-shared program!  Sigh.  ++bsa]
  22.  
  23. Following C code builds inverted index files for big text files ... seems
  24. to work on Sun, VAX, and Macintosh in my tests.  Heavily commented in a
  25. helter-skelter style....  ^z
  26.  
  27. /*    revised main indexer program 'qndxr.c' by ^z -- 870820-...
  28.  *
  29.  * revised 870930-1008 to give the user more options and control of how
  30.  * delimiters are defined and handled.  Now can choose:
  31.  *    - the default:  any non-alphanumeric characters are delimiters (my
  32.  *        original approach, and perhaps the simplest to understand and use);
  33.  *    - option "-e":  keep punctuation characters ONLY when they are embedded
  34.  *        in between non-delimiter characters, otherwise turn them into
  35.  *        delimiters (approach invented by Bill Hole of MicroDynamics Ltd.;
  36.  *        very nice for displaying 'words' such as don't, non-ASCII, 3.14159,
  37.  *        87/10/02, etc. without splitting them up and requiring proximity
  38.  *        searching);
  39.  *    - option "-a":  keep ALL punctuation characters, whether embedded in
  40.  *        words or not (best for indexing FORTH programs and such, but does
  41.  *        make spurious 'distinct' words at ends of sentences, etc.);
  42.  *    - option "-s":  keep all special (non-ASCII) characters (with values
  43.  *        in the range 128-255; in the Apple character set, these are the
  44.  *        symbols that carry umlauts, tilde, accents, etc., making this
  45.  *        option the best for foreign-language and symbol-heavy files);
  46.  *        default is to remove the special characters.
  47.  *
  48.  *    Note that option "-s" can be combined with any of the other options;
  49.  *    options "-e" and "-a" are mutually exclusive.  (Actually, "-a" in my
  50.  *    implementation overrides "-e".)  The "-e" option does require
  51.  *    peeking ahead one character before deciding on the fate of
  52.  *    a punctuation symbol, but that isn't too hard to arrange....
  53.  *
  54.  *    ---------------------------------------------------------------
  55.  *
  56.  * Synopsis of the qndxr.c program's approach to sorting an index:
  57.  *    - load a chunk of the input file into memory; during the loading,
  58.  *        filter the characters appropriately, turning lower-case
  59.  *        into capitals, changing delimiters into \0's, and noting down
  60.  *        the locations of the beginnings of keys (words) in a ptr array;
  61.  *    - do a quicksort on the ptr array, using the keys in the buffer
  62.  *        to sort on;
  63.  *    - write the resulting sorted list of pointers along with their keys
  64.  *        to disk as files, named x0k0 and x0p0, in the *.k and *.p formats
  65.  *        used in ndxr.15;
  66.  *    - repeat the above steps with another chunk of the input file, and
  67.  *        name the resulting files x0k1 and x0p1; repeat, etc., until the
  68.  *        input file is all sorted into chunks;
  69.  *    - begin to merge the sorted files in an N-way merge ... for the
  70.  *        specific case of N=2, for example, merge x0k0/x0p0 and
  71.  *        x0k1/x0p1 into x1k0/x1p0; merge x0k2/x0p2 and x0k3/x0p3 into
  72.  *        x1k1/x1p1; etc., deleting the 0th-generation files as they are
  73.  *        merged;
  74.  *    - merge x1k0/x1p0 and x1k1/x1p1 into x2k0/x2p0, etc., and continue
  75.  *        merging subsequent generations until everything has become a
  76.  *        single pair of index files, xnk0/xnp0, which is then renamed
  77.  *        to be the original document name with '.k' and '.p' endings.
  78.  *
  79.  *    ---------------------------------------------------------------
  80.  *
  81.  * Comparison with the older radix sort approach:
  82.  *    The new quicksort/mergesort method gains a bit in speed (since so
  83.  *    much of the work is done in memory rather than streaming from disk
  84.  *    back and forth) and also saves on disk space requirements (since
  85.  *    the k and p files are significantly compressed relative to the raw
  86.  *    index files formerly used during index sorting).  The old radix sort
  87.  *    tended to only achieve about 2 MB/hour indexing on my Mac Plus setup,
  88.  *    and it required 5-6 times the size of the original file in free
  89.  *    disk space during indexing.  This new approach achieves >4 MB/hour
  90.  *    in tests on the same Mac Plus, and only requires about 1.9 times
  91.  * the original file size in free space!
  92.  *
  93.  *    The new approach also allows for greater key length -- try recompiling
  94.  *    with KEY_LENGTH of 28, for instance -- without such severe disk space
  95.  *    penalties as the old radix sort would have incurred, and without severe
  96.  *    time penalties.  (Duplicate words in the chunks are only stored once
  97.  *    in the key file, though each must have an entry in the pointer file.)
  98.  *
  99.  *    The only obvious disadvantage of the quicksort/mergesort approach is
  100.  *    that it is an O(NlogN) procedure rather than O(N), and thus gets slower
  101.  *    when files get very large.  (Radix sorting is strictly linear in N,
  102.  *    in theory anyway.)
  103.  *
  104.  *    ---------------------------------------------------------------
  105.  *
  106.  *    For further details, contact the author:
  107.  *     Mark Zimmermann             science (at) NEMS.ARPA
  108.  *     9511 Gwyndale Dr.           [75066,2044] on CompuServe
  109.  *     Silver Spring, MD  20910
  110.  *     301-565-2166
  111.  *    ---------------------------------------------------------------
  112.  */
  113.  
  114. #include <stdio.h>
  115. #include <strings.h>
  116. #include <ctype.h>
  117.  
  118. /* --------------header file--------------- */
  119.  
  120. /* header file for project qndxr -- by ^z -- 870820-0913-...
  121.  */
  122.  
  123. /* tell what compiler we're using ... Lightspeed C by Think, if the
  124.  * following line is #defined ... essentially, when LIGHTSPEED is here,
  125.  * assume that we have only 16-bit int variables and that Macintosh
  126.  * toolbox traps are available ... when LIGHTSPEED is not #defined,
  127.  * assume that ints can hold more like 32 bits without error, so more
  128.  * can be done using standard I/O routines from <stdio>
  129.  */
  130. /* #define LIGHTSPEED */
  131.  
  132. /* preprocessor 'function' to turn on/off debug printing of detailed info
  133.  *    during program runs ... when debugging, use a statement:
  134.  * #define DEBUG(fmt, arg)   printf (fmt, arg)
  135.  * ... and when not debugging, just use:  #define DEBUG(fmt, arg)
  136.  * to effectively remove those print commands....
  137.  */
  138. /* #define DEBUG(fmt, arg)   printf (fmt, arg) */
  139. #define DEBUG(fmt, arg)
  140.  
  141. /* sort on KEY_LENGTH characters ... make it 28 rather arbitrarily as an
  142.  * experiment ... want it long enough to avoid truncation of legitimate
  143.  * words, but short enough to save some space in the *.k files ... an
  144.  * alternative value is 12, for compatibility with the older ndxr.c program
  145.  * and brwsr.c, if they haven't been revised to allow for longer keys....
  146.  */
  147. #define KEY_LENGTH  28
  148.  
  149. /* define a structure for the index_keys file
  150.  */
  151. typedef struct
  152.   {
  153.     char kkey[KEY_LENGTH];
  154.     long ccount;
  155.   }  KEY_REC;
  156.  
  157. /* define a structure for my simpleminded I/O buffers ...
  158.  */
  159. typedef struct
  160.   {
  161.     char *zbufbase;
  162.     char *zbufp;
  163.     long zbufcounter;
  164.     long zbufsize;
  165.     FILE *zbuffilep;
  166.     int  zbufitemsize;
  167.   }  ZBUF;
  168.  
  169. /* choose this size to be the default memory size used for total buffer
  170.  * space ... for convenience on the Mac Plus, I have picked 512 kB, which
  171.  * leaves me a bit of space to spare ....
  172.  */
  173. #define DEFAULT_MEMSIZ  524288
  174.  
  175. /* merge this many files at each stage of the merging operation for index
  176.  * building ... 2 means a binary merge, etc. ... one needs to have at least
  177.  * 5 + 2 * NMERGE I/O buffers around:  for each of NMERGE files, there is
  178.  * a *.k keys file and a *.p pointers file; plus there must be a single
  179.  * output *.k and a single output *.p file; plus there is the need for stdin,
  180.  * stdout, and stderr to be open as well.  Thus, I have found that a 4-way
  181.  * merge (NMERGE = 4) works pretty nicely....
  182.  */
  183. #define NMERGE  4
  184.  
  185. #ifndef TRUE
  186. #define TRUE  1
  187. #endif
  188.  
  189. #ifndef FALSE
  190. #define FALSE  0
  191. #endif
  192.  
  193. /* CMASK makes sure that a returned character isn't sign-extended
  194.  */
  195. #ifndef CMASK
  196. #define CMASK  0xFF
  197. #endif
  198.  
  199. /* put the prototypes for my functions here... assume that if LIGHTSPEED
  200.  * is #define'd, then we want to use prototypes....
  201.  */
  202. #ifdef LIGHTSPEED
  203.  
  204. /* in qndxr unix main.c */
  205. void punt(void);
  206. void openfile(FILE *file, char *mode);
  207. void main(void);
  208.  
  209. /* in qndxr.c */
  210. void _main(int argc, char *argv[]);
  211.  
  212. /* in bufio.c */
  213. void create_zbuffer (int n, long bufsize, FILE *buffile, int bufitemsize);
  214. void free_zbuffer (int n);
  215. char *next_input_item (int n);
  216. void load_zbuffer (int n);
  217. char *next_output_item (int n);
  218. void flush_zbuffer (int n);
  219.  
  220. /* in build_indices.c */
  221. int build_indices (void);
  222.  
  223. /* in doc_buf.c */
  224. char *make_buf (long bufsiz);
  225. long load_doc_buffer (char *doc, long doc_bufsiz, char **ptr);
  226. int filtered_getc (void);
  227.  
  228. /* in merge_files.c */
  229. void nway_merge_kpfiles (FILE *ink[], FILE *inp[], FILE *outk, FILE *outp,
  230.         int n);
  231. void copy_ptr_recs (int inzbuf, long count, int outzbuf);
  232. void copy_key_rec (char *kkey, long ccount, int outzbuf);
  233. int merge_not_finished (KEY_REC *kr[], int n);
  234. int smallest_key (KEY_REC *kr[], int n);
  235.  
  236. /* in merge_indices.c */
  237. int merge_indices (char *doc_filename);
  238.  
  239. /* in file_utils.c */
  240. void write_sorted_files (char *doc, char **ptr, long nwords,
  241.         int pass_number, long offset);
  242. int is_new_word (char *w0, char *w1);
  243. void write_new_key (char *p, char *kp);
  244.  
  245. /* in merge_utils.c */
  246. FILE *open_inkfile (int generation_number, int file_number);
  247. FILE *open_inpfile (int generation_number, int file_number);
  248. void fix_oddball_file_name (int generation_number, int file_number);
  249. void fix_final_file_names (int generation_number, char *doc_filename);
  250. FILE *open_outkfile (int generation_number, int file_number);
  251. FILE *open_outpfile (int generation_number, int file_number);
  252. void remove_used_infiles (int generation_number, int file_number, int n);
  253. void close_infiles (FILE *ink[], FILE *inp[], int n);
  254.  
  255. /* in misc_utils.c */
  256. long set_params (int argc, char *argv[]);
  257. long set_zbufsiz (long zb);
  258. void set_parser_options (char *str);
  259. void check_interrupt (void);
  260. long file_size (FILE *fp);
  261.  
  262. /* in open_files.c */
  263. FILE *open_docfile (int argc, char *argv[]);
  264. FILE *open_kfile (int pass_number);
  265. FILE *open_pfile (int pass_number);
  266.  
  267. /* in zqsort.c */
  268. void zqsort (char **first, char **last);
  269. int compare_ptrs (char **p1, char **p2);
  270. int zstrcmp (char *s1, char *s2);
  271.  
  272. #endif
  273.  
  274.  
  275. /* ----------------------main program file---------------- */
  276.  
  277.  
  278. /* define a global variable to hold the chosen size of a fundamental
  279.  * quantum of buffer space ... experiments with dynamically choosing
  280.  * it at runtime seem to cause occasional problems on the Macintosh,
  281.  * and have other risks with virtual memory systems, so default to
  282.  * DEFAULT_MEMSIZ total buffer space but let the user override with
  283.  * a command-line choice to suit ... see function set_zbufsiz() for
  284.  * further discussion....
  285.  */
  286. long zbufsiz;
  287.  
  288. /* define a global variable to tell whether or not all punctuation chars
  289.  * are kept...
  290.  */
  291. int keep_all_punct = FALSE;
  292.  
  293. /* define a global variable to tell whether or not only embedded punctuation
  294.  * characters are preserved...
  295.  */
  296. int keep_embedded_punct = FALSE;
  297.  
  298. /* define a global variable to tell whether or not to keep special,
  299.  * non-ASCII characters...
  300.  */
  301. int keep_special_chars = FALSE;
  302.  
  303. /* define a global variable to hold the (FILE *) for the document file
  304.  */
  305. FILE *doc_file;
  306.  
  307. /* main program to do the work ... 
  308.  */
  309.  
  310. void main(argc, argv)
  311.   int argc;
  312.   char *argv[];
  313.   {
  314.     unsigned long start_time, end_time, time();
  315.     long set_params(), file_size();
  316.     char *ctime();
  317.     FILE *open_docfile();
  318.  
  319.     time (&start_time);
  320.     printf ("Starting work:  %s\n", ctime (&start_time));
  321.     
  322.     printf ("\nOpening document file \"%s\"...\n", argv[1]);
  323.     doc_file = open_docfile (argc, argv);
  324.  
  325.     zbufsiz = set_params (argc, argv);
  326.     printf ("Using buffers of size %ld each...\n", zbufsiz);
  327.  
  328.     printf ("Beginning to build index...\n");
  329.     while (build_indices ());
  330.  
  331.     printf ("Beginning to merge index subfiles...\n");    
  332.     while (merge_indices (argv[1]));
  333.  
  334.     time (&end_time);
  335.     printf ("\nEnding work:  %s\n", ctime (&end_time));
  336.     printf ("Elapsed time  = %ld seconds.\n", end_time - start_time);
  337.     printf ("Indexing rate = %.2f megabytes/hour.\n", file_size (doc_file) *
  338.                   0.003600 / ( end_time - start_time ));
  339.     printf ("Input database file \"%s\" was %ld bytes long.\n", argv[1],
  340.                   file_size (doc_file));
  341.  
  342.     fclose (doc_file);
  343.   }
  344.  
  345.  
  346. /* -------------------bufio.c file------------------- */
  347.  
  348. /* This is the file 'bufio.c' ... by ^z, 870830-0913- ... it includes 
  349.  * definitions of some buffer words to accumulate information on its
  350.  * way to/from the disks ... use these to speed up operations and reduce
  351.  * disk head movements, in place of calls to fputc(), fread(), fwrite(),
  352.  * etc. ... try to make them very general so that they will simplify
  353.  * other tasks....
  354.  *
  355.  */
  356.  
  357.  
  358. /* set up some buffers here to save on disk head movement and speed up
  359.  * operations ... use my simple ZBUF structure for both input and
  360.  * output operations ... keep everything static, local here to this file
  361.  * for safety's sake ... allocate enough items here for all the buffers
  362.  * that we may need for an NMERGE-way merge operation, taking into account
  363.  * the need for input buffers for all the NMERGE *.k and *.p files plus
  364.  * the output files *.k and *.p as well....
  365.  */
  366.  
  367. static ZBUF zbuffer[2 + 2 * NMERGE];
  368.  
  369.  
  370. /* function to create a zbuffer and set its parameters appropriately
  371.  */
  372.  
  373. void create_zbuffer (n, bufsize, buffile, bufitemsize)
  374.   int n, bufitemsize;
  375.   long bufsize;
  376.   FILE *buffile;
  377.   {
  378.     char *make_buf();
  379.     
  380.     zbuffer[n].zbufbase = make_buf (bufsize);
  381.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  382.     zbuffer[n].zbufcounter = 0;
  383.     zbuffer[n].zbufsize = bufsize;
  384.     zbuffer[n].zbuffilep = buffile;
  385.     zbuffer[n].zbufitemsize = bufitemsize;
  386.   }
  387.  
  388.  
  389. /* function to free a zbuffer ...
  390.  */
  391.  
  392. void free_zbuffer (n)
  393.   int n;
  394.   {
  395.     free (zbuffer[n].zbufbase);
  396.   }
  397.  
  398.  
  399. /* function to return a pointer to the next item in a chosen input
  400.  * buffer 'n'; it reloads the buffer if necessary ... returns NULL
  401.  * pointer when there's nothing left in the file ...
  402.  */
  403.  
  404. char *next_input_item (n)
  405.   int n;
  406.   {
  407.     char *result;
  408.     void load_zbuffer();
  409.     
  410.     if (zbuffer[n].zbufcounter == 0)
  411.         load_zbuffer (n);
  412.     
  413.     zbuffer[n].zbufcounter -= zbuffer[n].zbufitemsize;
  414.     if (zbuffer[n].zbufcounter >= 0)
  415.       {
  416.         result = zbuffer[n].zbufp;
  417.         zbuffer[n].zbufp += zbuffer[n].zbufitemsize;
  418.         return (result);
  419.       }
  420.     else
  421.         return (NULL);
  422.   }
  423.  
  424.  
  425. /* function to load the nth zbuffer appropriately ... it resets the buffer
  426.  * pointers, etc. ... might as well give the user a chance to interrupt (in
  427.  * the Macintosh version) here, as long as we have to go to the disk anyway....
  428.  */
  429.  
  430. void load_zbuffer (n)
  431.   int n;
  432.   {
  433.     long nread;
  434.     void exit(), check_interrupt();
  435.  
  436. #ifdef LIGHTSPEED
  437.     nread = zbuffer[n].zbufsize;
  438.     FSRead (zbuffer[n].zbuffilep->refnum, &nread, zbuffer[n].zbufbase);
  439. #else
  440.     nread = fread (zbuffer[n].zbufbase, sizeof(char),
  441.             (int)zbuffer[n].zbufsize, zbuffer[n].zbuffilep);
  442. #endif
  443.  
  444.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  445.     zbuffer[n].zbufcounter = nread;
  446.     
  447.     if (ferror (zbuffer[n].zbuffilep))
  448.       {
  449.         printf ("\nFatal error in load_zbuffer while reading in data!\n");
  450.         printf ("(n=%d, nread=%ld)\n", n, nread);
  451.         exit (1);
  452.       }
  453.     
  454. #ifdef LIGHTSPEED
  455.     check_interrupt ();
  456. #endif
  457.   }
  458.  
  459.  
  460. /* function to return a pointer to the right place to store the next
  461.  * output item for the nth zbuffer ... when the buffer becomes full,
  462.  * it flushes it to disk, resets pointers, etc.
  463.  */
  464.  
  465. char *next_output_item (n)
  466.   int n;
  467.   {
  468.     char *result;
  469.     void flush_zbuffer();
  470.     
  471.     if (zbuffer[n].zbufcounter == zbuffer[n].zbufsize)
  472.         flush_zbuffer (n);
  473.     
  474.     result = zbuffer[n].zbufp;
  475.     zbuffer[n].zbufp += zbuffer[n].zbufitemsize;
  476.     zbuffer[n].zbufcounter += zbuffer[n].zbufitemsize;
  477.     return (result);
  478.   }
  479.  
  480.  
  481. /* function to flush out a zbuffer to the disk ... might as well give user
  482.  * a chance to interrupt here (in the Macintosh version), as long as we
  483.  * have to go to the disk anyway....
  484.  */
  485.  
  486. void flush_zbuffer (n)
  487.   int n;
  488.   {
  489.     long chars_written;
  490.     void exit();
  491.     
  492.     if (zbuffer[n].zbufcounter == 0)
  493.         return;
  494.  
  495. #ifdef LIGHTSPEED
  496.     chars_written = zbuffer[n].zbufcounter;
  497.     FSWrite (zbuffer[n].zbuffilep->refnum, &chars_written,
  498.                 zbuffer[n].zbufbase);
  499. #else
  500.     chars_written = fwrite (zbuffer[n].zbufbase, sizeof(char),
  501.                 (int)zbuffer[n].zbufcounter, zbuffer[n].zbuffilep);
  502. #endif
  503.     if (ferror(zbuffer[n].zbuffilep) || chars_written == 0)
  504.       {
  505.         printf ("\nFatal error in flush_zbuffer while writing out data!\n");
  506.         printf ("(n=%d, zbufcounter=%ld, chars_written=%ld)\n", n,
  507.                     zbuffer[n].zbufcounter, chars_written);
  508.         exit(1);
  509.       }
  510.     
  511.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  512.     zbuffer[n].zbufcounter = 0;
  513.  
  514. #ifdef LIGHTSPEED
  515.     check_interrupt ();
  516. #endif
  517.   }
  518.   
  519.  
  520. /* ---------------build_indices.c file---------------- */
  521.  
  522. /* file build_indices.c ... by ^z, 870820-0913-...
  523.  *
  524.  * revised 870930-871007 to allow more user options on keeping/discarding
  525.  *    punctuation, etc. -- ideas based on Bill Hole's suggestions
  526.  *
  527.  * contains subroutine to build indices for each chunk of input document
  528.  * (database) text file for program qndxr ... 
  529.  *
  530.  * Strategy is as outlined in qndxr:  take in a big chunk of the doc_file,
  531.  *    generate the pointers to each word in the buffer as the buffer contents
  532.  *    are converted into appropriate (all caps, delimiters filtered into
  533.  *    spaces) form for sorting; sort the pointers in memory; and then write
  534.  *    out to disk the pointers and keys in the ndxr.c format for *.k and *.p
  535.  *    files.
  536.  *
  537.  * Allocate space for the doc and ptr buffers here so as to maximize use
  538.  * of available memory ... note that we need to have room for the doc
  539.  * buffer, for a ptr buffer that might (in the worst case of a file full
  540.  * of 1-letter words) be twice as long as the doc buffer, and also space
  541.  * for two standard zbuffers to accumulate the output *.k and *.p file
  542.  * info in before sending it to disk.
  543.  *
  544.  * Note that for speed, while they are being sorted the pointers just point
  545.  *    directly to the key strings in the input buffer; they must be converted
  546.  *    into true offset pointers relative to the 0th byte of the document file
  547.  *    as they are written to disk in the *.p file!  Make sure that all of
  548.  *    the delimiters in the document/database buffer are converted into
  549.  *    '\0' characters so that string comparison functions will work right.
  550.  *
  551.  * Also note that to avoid edge effects at the end of the buffer, an extra
  552.  *    amount of space is required at the end of the buffer, of length
  553.  *    KEY_LENGTH, to accomodate the end of the last word in the buffer.
  554.  *
  555.  * Use static local variables in the function here to keep track of where
  556.  *    we are in the document file from one chunk to the next, what chunk
  557.  *    number we are on now, etc.
  558.  *
  559.  * Give the user a chance to interrupt operations (in the Macintosh
  560.  * version of this program) at intervals here, as long as
  561.  * there are time-consuming I/O or sorting or scanning operations
  562.  * to be done ...
  563.  */
  564.  
  565.  
  566. int build_indices ()
  567.   {
  568.     static int pass_number = 0;
  569.     long doc_bufsiz, offset, load_doc_buffer(), nwords, 
  570.             ftell();
  571.     extern long zbufsiz;
  572.     extern FILE *doc_file;
  573.     char *doc, **ptr, *malloc(), *mlalloc(), *calloc(), *clalloc();
  574.     void zqsort(), write_sorted_files();
  575.  
  576.     doc_bufsiz = 2 * NMERGE * zbufsiz / 3;
  577.     DEBUG ("--allocating doc buffer of size %ld\n", doc_bufsiz + KEY_LENGTH);
  578.     doc = make_buf (doc_bufsiz + KEY_LENGTH);
  579.     
  580.     DEBUG ("--allocating ptr buffer of size %ld\n", doc_bufsiz * 2);
  581.     ptr = (char **)make_buf (doc_bufsiz * 2);
  582.     
  583. #ifdef LIGHTSPEED
  584.     check_interrupt ();
  585. #endif
  586.  
  587.     offset = ftell (doc_file);    
  588.     DEBUG ("--loading doc buffer beginning at offset %ld\n", offset);    
  589.     nwords = load_doc_buffer (doc, doc_bufsiz, ptr);
  590.  
  591.     if (nwords == 0)
  592.       {
  593.         DEBUG ("--Building done ... now freeing doc & ptr buffers\n", NULL);
  594.         free (doc);
  595.         free ((char *)ptr);
  596.         return (FALSE);
  597.       }
  598.     
  599.     printf ("Index subfile #%d contains %ld words...\n", pass_number,
  600.                 nwords);
  601.     
  602. #ifdef LIGHTSPEED
  603.     check_interrupt ();
  604. #endif
  605.  
  606.     DEBUG ("--sorting ptr array\n", NULL);
  607.     zqsort (ptr, ptr + nwords);
  608.     
  609. #ifdef LIGHTSPEED
  610.     check_interrupt ();
  611. #endif
  612.  
  613.     DEBUG ("--writing sorted keys and ptrs to disk\n", NULL);
  614.     write_sorted_files (doc, ptr, nwords, pass_number, offset);
  615.     
  616. #ifdef LIGHTSPEED
  617.     check_interrupt ();
  618. #endif
  619.  
  620.     DEBUG ("--freeing doc & ptr buffers\n", NULL);
  621.     free (doc);
  622.     free ((char *)ptr);
  623.     
  624.     ++pass_number;
  625.     return (TRUE);
  626.   }
  627.  
  628.  
  629. /* ---------------doc_buf.c file------------------ */
  630.  
  631. /* file doc_buf.c ...  by ^z 870830-0919-...
  632.  * functions to load in text from the document file and then
  633.  * save out keys and pointers to the *.k and *.p files ...
  634.  * modified 871007-... to unify the doc-buffer loading with the
  635.  * character-filtering and the pointer array building....
  636.  */
  637.  
  638. /* function to create a buffer for me to use...
  639.  */
  640.  
  641. char *make_buf (bufsiz)
  642.   long bufsiz;
  643.   {
  644.     char *buf, *malloc(), *mlalloc();
  645.     void exit();
  646.     
  647.     DEBUG ("--allocating a buffer, size = %ld\n", bufsiz);
  648.     
  649. #ifdef LIGHTSPEED
  650.     buf = mlalloc (bufsiz);
  651. #else
  652.     buf = malloc ((unsigned int)bufsiz);
  653. #endif
  654.  
  655.     if (buf == NULL)
  656.       {
  657.         printf ("\nFatal error in attempt to allocate a buffer!\n");
  658.         printf ("(bufsiz=%ld)\n", bufsiz);
  659.         exit(1);
  660.       }
  661.     
  662.     return (buf);
  663.   }
  664.  
  665.  
  666. /* function to load the document buffer ... bring in doc_bufsiz
  667.  * characters, and then enough more to finish out the final word,
  668.  * followed by a terminal delimiter .... as the characters are read
  669.  * in, filter them appropriately (depending on user choices) and
  670.  * build the pointer array in memory to the first character of each
  671.  * word ... return the total number of words that were
  672.  * read in to the buffer (zero if we're finished with the file)
  673.  *
  674.  * ... note that one must be sure to pull in and throw away
  675.  * any excess characters beyond KEY_LENGTH in the final word, so that
  676.  * the remaining fragment doesn't show up as the first "word" in the
  677.  * next chunk of the file....
  678.  *
  679.  * Routine modified 871007-... in order to unify the buffer-loading and
  680.  * character-filtering and pointer-array-building operations, and to go
  681.  * back to using getc() from <stdio> rather than Macintosh-specific
  682.  * operations for loading the buffer....
  683.  */
  684.  
  685. long load_doc_buffer (doc, doc_bufsiz, ptr)
  686.   char *doc, **ptr;
  687.   long doc_bufsiz;
  688.   {
  689.     int c, i, in_a_word = FALSE;
  690.     char **ptr0, *end_doc_buf;
  691.     extern FILE *doc_file;
  692.  
  693.     DEBUG ("--Loading document buffer...\n", NULL);
  694.      
  695.      ptr0 = ptr;
  696.      end_doc_buf = doc + doc_bufsiz;
  697.      
  698.      while (doc < end_doc_buf)
  699.        {
  700.          c = filtered_getc ();
  701.          DEBUG ("--filtered character = \"%c\"\n", c);
  702.          if (c == EOF)
  703.            {
  704.              *doc++ = '\0';
  705.              in_a_word = FALSE;
  706.              break;
  707.            }
  708.          if (! c)
  709.              in_a_word = FALSE;
  710.          else if (! in_a_word)
  711.            {
  712.              *ptr++ = doc;
  713.              in_a_word = TRUE;
  714.              DEBUG ("--adding new ptr = %ld\n", doc);
  715.            }
  716.          *doc++ = c;
  717.        }
  718.      
  719.      if (doc == end_doc_buf && in_a_word)
  720.       {
  721.         DEBUG ("--finishing off a final buffer word...\n", NULL);
  722.         for (i = 0; i < KEY_LENGTH; ++i)
  723.          {
  724.            c = filtered_getc ();
  725.            if (c == EOF)
  726.              {
  727.                *doc++ = '\0';
  728.                break;
  729.              }
  730.            if (! c)
  731.              {
  732.                *doc++ = '\0';
  733.                break;
  734.              }
  735.            *doc++ = c;
  736.          }
  737.        if (i == KEY_LENGTH)
  738.            while (filtered_getc ())
  739.                 ;
  740.        }
  741.      
  742.      return (ptr - ptr0);
  743.   }
  744.  
  745.  
  746. /* function to get the next character from the document file and filter it
  747.  * as the user desires ... return:
  748.  *  EOF  if end of file encountered;
  749.  *  '/0' if the character is a delimiter;
  750.  *  otherwise, the character itself (filtered into upper-case,
  751.  *        if it was lower-case)
  752.  */
  753.  
  754. int filtered_getc ()
  755.   {
  756.     static int prevc, c = '\0';
  757.     int nextc;
  758.     extern int keep_all_punct, keep_embedded_punct, keep_special_chars;
  759.     extern FILE *doc_file;
  760.  
  761.     prevc = c;
  762.     c = getc (doc_file);
  763.     
  764.     if (c == EOF)
  765.         return (EOF);
  766.     
  767.     if (islower (c))
  768.         return (c = toupper (c));
  769.     
  770.     if (isupper (c) || isdigit (c))
  771.         return (c);
  772.     
  773.     if (isspace (c))
  774.         return (c = '\0');
  775.     
  776.     if (keep_special_chars && ! isascii (c))
  777.         return (c);
  778.     
  779.     if (keep_all_punct && ispunct (c))
  780.         return (c);
  781.     
  782.     if (keep_embedded_punct && ispunct (c))
  783.       {
  784.         if (prevc == '\0')
  785.             return (c = '\0');
  786.         nextc = getc (doc_file);
  787.         ungetc (nextc, doc_file);
  788.         if (nextc == EOF)
  789.             return (c = '\0');
  790.         if (isalnum (nextc) || (keep_special_chars && ! isascii (nextc)))
  791.             return (c);
  792.         else
  793.             return (c = '\0');
  794.       }
  795.     
  796.     return (c = '\0');
  797.   }
  798.  
  799. /* ------------------------file_utils.c------------- */
  800.  
  801. /* file file_utils.c ... by ^z -- 870820-0913-...
  802.  * some utility routines for qndxr project, associated with files...
  803.  */
  804.  
  805.  
  806. /* function to write out sorted k & p files based on the doc and ptr
  807.  * arrays in memory....
  808.  *
  809.  * The kfile format is as described in detail elsewhere:
  810.  *    the key word, turned into all capital letters and with spaces
  811.  *        afterward, of fixed length KEY_LENGTH; and
  812.  *    the cumulative count of how many words have passed before, including
  813.  *        the current word, a long integer.
  814.  *
  815.  * Function revised 870907-... by ^z to use zbuffer method....
  816.  */
  817.  
  818. void write_sorted_files (doc, ptr, nwords, pass_number, offset)
  819.   char *doc, **ptr;
  820.   long nwords, offset;
  821.   int pass_number;
  822.   {
  823.     extern long zbufsiz;
  824.     FILE *kfile, *pfile, *open_kfile(), *open_pfile();
  825.     char *prev_word, *next_output_item();
  826.     KEY_REC *outk;
  827.     long *outp, i, file_size ();
  828.     void create_zbuffer(), write_new_key();
  829.     
  830.     DEBUG ("--Entering write_sorted_files with nwords %ld\n", nwords);
  831.     if (nwords == 0)
  832.         return;
  833.     
  834.     DEBUG ("--Opening kfile & pfile for pass_number = %d\n", pass_number);
  835.     kfile = open_kfile (pass_number);
  836.     pfile = open_pfile (pass_number);
  837.     
  838.     DEBUG ("--Creating buffers for keys & ptrs, size = %ld\n", zbufsiz);
  839.     create_zbuffer (0, zbufsiz, kfile, sizeof(KEY_REC));
  840.     create_zbuffer (1, zbufsiz, pfile, sizeof(long));
  841.  
  842.     DEBUG ("--Beginning to write keys and ptrs; first key=%.28s\n", ptr[0]);
  843.     prev_word = ptr[0];
  844.     outk = (KEY_REC *)next_output_item (0);
  845.     write_new_key (ptr[0], outk->kkey);
  846.     
  847.     for (i = 0; i < nwords; ++i)
  848.       {
  849.         if (is_new_word (prev_word, ptr[i]))
  850.           {
  851.             outk->ccount = i;
  852.             outk = (KEY_REC *)next_output_item (0);
  853.             write_new_key (ptr[i], outk->kkey);
  854.             prev_word = ptr[i];
  855.           }
  856.         outp = (long *)next_output_item (1);
  857.         *outp = (ptr[i] - doc) + offset;
  858.       }
  859.     outk->ccount = i;
  860.  
  861.     flush_zbuffer (0);
  862.     flush_zbuffer (1);
  863.     
  864.     DEBUG ("--Getting rid of key and ptr buffers...\n", NULL);
  865.     free_zbuffer (0);
  866.     free_zbuffer (1);
  867.     
  868.     printf (" ...%ld distinct words\n",
  869.             file_size (kfile) / sizeof(KEY_REC));
  870.     fclose (kfile);
  871.     fclose (pfile);
  872.   }
  873.  
  874.  
  875. /* function to determine if the current word is the same as or different
  876.  * from the previous word -- if it is different, we'll need to write an
  877.  * entry out to the key file kfile -- compare the words up to the first
  878.  * '\0', or for a maximum distance of KEY_LENGTH, and return TRUE
  879.  * if they differ, FALSE if they are identical that far.  Thus, a simple
  880.  * call to zstrcmp() does the job.... but keep ours as a function instead
  881.  * of a macro call for the moment, for safety and readability....
  882.  */
  883.  
  884. int is_new_word (w0, w1)
  885.   char *w0, *w1;
  886.   {
  887.     return (zstrcmp (w0, w1));
  888.   }
  889.  
  890.  
  891. /* function to write out a new key entry in the key_file:
  892.  * KEY_LENGTH letters consisting of the key word (which will be found
  893.  * delimited by a '\0'), followed by enough blanks to fill out the
  894.  * record to total length KEY_LENGTH ...
  895.  */
  896.  
  897. void write_new_key (p, kp)
  898.   register char *p, *kp;
  899.   {
  900.     register int i, c;
  901.     
  902.     for (i = 0; i < KEY_LENGTH; ++i)
  903.       {
  904.         c = *p++;
  905.         if (c == '\0')
  906.             break;
  907.         *kp++ = c;
  908.       }
  909.  
  910.     for ( ; i < KEY_LENGTH; ++i)
  911.         *kp++ = ' ';
  912.   }
  913.  
  914.  
  915.  
  916. /* ---------------------merge_files.c--------------- */
  917.  
  918. /* file merge_files.c ...  870902-... ^z
  919.  * more functions to do the work of merging subindices together ...
  920.  * with buffering of inputs and outputs ...
  921.  */
  922.  
  923.  
  924. /* function to do the real work of merging sorted k & p
  925.  * files into a single sorted file...
  926.  *
  927.  * Procedure is as follows:
  928.  *
  929.  *    Compare the current key records from each of the N files to be merged.
  930.  *    Take the smallest of the keys (or, if there is a tie, take the one
  931.  *    from the earlier file number) and write its pointer records out to
  932.  *    the *.p file for the next generation.  If the key is a new one, that
  933.  *    is, if it differs from the previous key, write out the previous key
  934.  *    word and the value for cumulative_counts to the *.k file, and reset
  935.  *    the previous key's value to that of the current key.  Then repeat
  936.  *    this whole procedure, until all the input files are exhausted.
  937.  *
  938.  *    The above works provided that we are careful in choosing the smallest
  939.  *    key and never let a file that has been exhausted (reached EOF) win a
  940.  *    comparison.  The function smallest_key does that properly below, since
  941.  *    a file that is at EOF has returned a NULL pointer for its key_rec...
  942.  *
  943.  *  For each file, the variable prev_cc[i] holds the previous value of
  944.  *    cumulative_counts for that file, so that we can determine how
  945.  *    many ptr_recs to write out by doing a simple subtraction.
  946.  *
  947.  * Buffer numbering scheme:  the Kth input file has zbuffer #K
  948.  *    for its keys and zbuffer #(K+n) for its pointers; the output
  949.  *    buffers are zbuffers #(2*n) for keys and #(2*n+1) for pointers.
  950.  */
  951.  
  952. void nway_merge_kpfiles (ink, inp, outk, outp, n)
  953.   FILE *ink[], *inp[], *outk, *outp;
  954.   register int n;
  955.   {
  956.     register int i;
  957.     KEY_REC *kr[NMERGE], prev_key;
  958.     long prev_cc[NMERGE], out_cc;
  959.     extern long zbufsiz;
  960.     char *strncpy();
  961.     void copy_ptr_recs(), copy_key_rec();
  962.     
  963.     DEBUG ("--entering nway_merge_kpfiles with n=%d\n", n);
  964.     for (i = 0; i < n; ++i)
  965.         prev_cc[i] = 0;
  966.     out_cc = 0;
  967.     
  968.     for (i = 0; i < n; ++i)
  969.       {
  970.         create_zbuffer (i, zbufsiz, ink[i], sizeof(KEY_REC));
  971.         create_zbuffer (i + n, zbufsiz, inp[i], sizeof(long));
  972.       }
  973.     create_zbuffer (2 * n, zbufsiz, outk, sizeof(KEY_REC));
  974.     create_zbuffer (2 * n + 1, zbufsiz, outp, sizeof(long));
  975.     
  976.     for (i = 0; i < n; ++i)
  977.         kr[i] = (KEY_REC *)next_input_item (i);
  978.     
  979.     i = smallest_key (kr, n);
  980.     strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  981.     DEBUG ("--first key is %.28s\n", prev_key.kkey);
  982.  
  983.     while (merge_not_finished (kr, n))
  984.       {
  985.         i = smallest_key (kr, n);
  986.         if (zstrcmp (prev_key.kkey, kr[i]->kkey))
  987.           {
  988.             copy_key_rec (prev_key.kkey, out_cc, 2 * n);
  989.             strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  990.           }
  991.         copy_ptr_recs (i + n, kr[i]->ccount - prev_cc[i], 2 * n + 1);
  992.         out_cc += kr[i]->ccount - prev_cc[i];
  993.         prev_cc[i] = kr[i]->ccount;
  994.         kr[i] = (KEY_REC *)next_input_item (i);
  995.       }
  996.     
  997.     copy_key_rec (prev_key.kkey, out_cc, 2 * n);
  998.     DEBUG ("--finished nway merge ... final key=%.28s\n", prev_key.kkey);
  999.     flush_zbuffer (2 * n);
  1000.     flush_zbuffer (2 * n + 1);
  1001.     for (i = 0; i < 2 * n + 2; ++i)
  1002.         free_zbuffer (i);
  1003.   }
  1004.  
  1005.  
  1006. /* function to copy a chosen number of ptr_recs (longs) from one file
  1007.  * to another ... used in merging two files by merge_kpfiles() above....
  1008.  * revised and simplified to use zbuffers....870902 ... ^z
  1009.  */
  1010.  
  1011. void copy_ptr_recs (inzbuf, count, outzbuf)
  1012.   register int inzbuf, outzbuf;
  1013.   register long count;
  1014.   {
  1015.     register long *inp, *outp;
  1016.     char *next_input_item(), *next_output_item();
  1017.  
  1018.     for ( ; count > 0; --count)
  1019.       {
  1020.         inp = (long *)next_input_item (inzbuf);
  1021.         outp = (long *)next_output_item (outzbuf);
  1022.         *outp = *inp;
  1023.       }
  1024.   }
  1025.  
  1026.  
  1027. /* function to write a key record including kkey (key word) and ccount
  1028.  * (cumulative_count) to an output file...
  1029.  */
  1030.  
  1031. void copy_key_rec (kkey, cc, outzbuf)
  1032.   char *kkey;
  1033.   long cc;
  1034.   int outzbuf;
  1035.   {
  1036.     KEY_REC *outp;
  1037.     char *strncpy(), *next_output_item();
  1038.  
  1039.     outp = (KEY_REC *)next_output_item (outzbuf);
  1040.     strncpy (outp->kkey, kkey, KEY_LENGTH);
  1041.     outp->ccount = cc;
  1042.   }
  1043.  
  1044.  
  1045. /* simple function to see if we are not yet finished with all of the input
  1046.  * files coming in to the merge operation ... signified by at least one of
  1047.  * the key pointers being non-NULL....
  1048.  */
  1049.  
  1050. int merge_not_finished (kr, n)
  1051.   KEY_REC *kr[];
  1052.   register int n;
  1053.   {
  1054.     register int i;
  1055.     
  1056.     for (i = 0; i < n; ++i)
  1057.         if (kr[i] != NULL)
  1058.             return (TRUE);
  1059.     
  1060.     return (FALSE);
  1061.   }
  1062.  
  1063.  
  1064. /* function to determine the smallest of the n keys pointed to by the
  1065.  * kr[] vector of pointers to KEY_RECs ... note that a NULL ptr ranks
  1066.  * after any other...also note that in case of a tie, the smaller
  1067.  * value of i is the one to return (for a stable merging sort)
  1068.  */
  1069.  
  1070. smallest_key (kr, n)
  1071.   KEY_REC *kr[];
  1072.   register int n;
  1073.   {
  1074.     register int i, smallest;
  1075.  
  1076.     for (i = 0; i < n; ++i)
  1077.         if (kr[i] != NULL)
  1078.           {
  1079.             smallest = i;
  1080.             break;
  1081.           }
  1082.  
  1083.     for (i = smallest + 1; i < n; ++i)
  1084.         if (kr[i] != NULL)
  1085.             if (zstrcmp (kr[smallest]->kkey, kr[i]->kkey) > 0)
  1086.                 smallest = i;
  1087.  
  1088.     return (smallest);
  1089.   }
  1090.  
  1091.  
  1092. /* -------------------------merge_indices.c-------------- */
  1093.  
  1094. /* file "merge_indices.c" ... by ^z -- 870823-...
  1095.  * function to merge sorted indices together repeatedly until finished
  1096.  * with them all in a single set of *.k/*.p files ...
  1097.  *
  1098.  * The merging strategy is straightforward enough:
  1099.  *    Let "g" denote the generation_number and "f" denote the file_number.
  1100.  *    Temporary file names begin with the letter x, which is then followed
  1101.  *    by a generation number (decimal), the letter k or p (standing for
  1102.  *    key or ptr, respectively), and then the file number (decimal).  Thus,
  1103.  *    the file "x0k0" is the keys file #0 for generation #0 (the starting,
  1104.  *    pre-merging, generation), file "x2p3" is the ptr file #3 for generation
  1105.  *    #2, etc.
  1106.  *
  1107.  * (The following discussion is specifically for a 2-way merge ... but
  1108.  * the generalization for N-way merging is straightforward.)
  1109.  *
  1110.  *    On a given call to merge_indices, the following may happen:
  1111.  *        - files xgkf/xgpf and xgk(f+1)/xgp(f+1) are merged into files
  1112.  *            x(g+1)k(f/2)/x(g+1)p(f/2), and then the parent files are
  1113.  *            deleted;
  1114.  *        - file xgkf isn't found, which means we are done with this
  1115.  *            generation and must go on to the next;
  1116.  *        - file xgk(f+1) isn't found, which means that either we are
  1117.  *            completely done with the merging work (if f=0) and just
  1118.  *            have to rename the files xgkf/xgpf into the correct final
  1119.  *            names (that is, doc_filename.k/doc_filename.p), or else
  1120.  *            (if f>0) we have an odd number of files for this level
  1121.  *            of merging, and therefore just have to rename xgkf/xgpf
  1122.  *            to x(g+1)k(f/2)/x(g+1)p(f/2).
  1123.  */
  1124.  
  1125.  
  1126. int merge_indices (doc_filename)
  1127.   char *doc_filename;
  1128.   {
  1129.     static int generation_number = 0, file_number = 0;
  1130.     FILE *ink[NMERGE], *inp[NMERGE], *outk, *outp, *open_inkfile(),
  1131.             *open_inpfile(), *open_outkfile(), *open_outpfile();
  1132.     void fix_oddball_file_name(), fix_final_file_names(), merge_kpfiles(),
  1133.             remove_used_infiles(), close_infiles();
  1134.     long inwords, indistinctwords, outdistinctwords, file_size();
  1135.     int i, n;
  1136.     
  1137.     for (n = 0; n < NMERGE; ++n)
  1138.       {
  1139.         ink[n] = open_inkfile (generation_number, file_number + n);
  1140.         if (ink[n] == NULL)
  1141.             break;
  1142.         inp[n] = open_inpfile (generation_number, file_number + n);
  1143.       }
  1144.     
  1145.     if (file_number + n == 1)
  1146.       {
  1147.         DEBUG ("--All finished with merging files!\n", NULL);
  1148.         printf ("\nFinished with index sorting!  Final file sizes:\n");
  1149.         printf ("%9ld bytes of distinct key words\n", file_size (ink[0]));
  1150.         printf ("%9ld bytes of pointers to words\n", file_size (inp[0]));
  1151.         close_infiles (ink, inp, n);
  1152.         fix_final_file_names (generation_number, doc_filename);
  1153.         return (FALSE);
  1154.       }
  1155.     
  1156.     if (n < 2)
  1157.       {
  1158.         DEBUG ("--finished generation_number=%d ", generation_number);
  1159.         DEBUG ("-- file_number=%d\n", file_number);
  1160.         if (n == 1)
  1161.           {
  1162.             close_infiles (ink, inp, n);
  1163.             fix_oddball_file_name (generation_number, file_number);
  1164.           }
  1165.         ++generation_number;
  1166.         file_number = 0;
  1167.         return (TRUE);
  1168.       }
  1169.     
  1170.     outk = open_outkfile (generation_number, file_number);
  1171.     outp = open_outpfile (generation_number, file_number);
  1172.     
  1173.     inwords = 0;
  1174.     indistinctwords = 0;
  1175.     for (i = 0; i < n; ++i)
  1176.       {
  1177.         inwords += file_size (inp[i]) / sizeof(long);
  1178.         indistinctwords += file_size (ink[i]) / sizeof(KEY_REC);
  1179.       }
  1180.     printf ("Merge pass #%d.%d\n", generation_number, file_number / NMERGE);
  1181.     printf ("Input files contain %ld words -- %ld distinct words...\n",
  1182.                 inwords, indistinctwords);
  1183.  
  1184.     nway_merge_kpfiles (ink, inp, outk, outp, n);
  1185.     
  1186.     outdistinctwords = file_size (outk) / sizeof(KEY_REC);
  1187.     printf (" ... merged result has %ld distinct words.\n",
  1188.                 outdistinctwords);
  1189.     
  1190.     close_infiles (ink, inp, n);
  1191.     fclose (outk);
  1192.     fclose (outp);
  1193.     remove_used_infiles (generation_number, file_number, n);
  1194.     
  1195.     file_number += NMERGE;
  1196.     
  1197.     return (TRUE);
  1198.   }
  1199.  
  1200. /* --------------------merge_utils.c---------------- */
  1201.  
  1202. /* file "merge_utils.c" ... 870902-... ^z
  1203.  * misc. utilities for the merge_indices functions...
  1204.  */
  1205.  
  1206.  
  1207. /* function to open an input key file for this generation and file number
  1208.  */
  1209.  
  1210. FILE *open_inkfile (generation_number, file_number)
  1211.   int generation_number, file_number;
  1212.   {
  1213.     FILE *fopen();
  1214.     char fname[32];
  1215.     
  1216.     sprintf (fname, "x%dk%d", generation_number, file_number);
  1217.     return (fopen (fname, "rb"));
  1218.   }
  1219.  
  1220.  
  1221. /* function to open an input ptr file for this generation and file number
  1222.  */
  1223.  
  1224. FILE *open_inpfile (generation_number, file_number)
  1225.   int generation_number, file_number;
  1226.   {
  1227.     FILE *fopen();
  1228.     char fname[32];
  1229.     
  1230.     sprintf (fname, "x%dp%d", generation_number, file_number);
  1231.     return (fopen (fname, "rb"));
  1232.   }
  1233.  
  1234.  
  1235. /* function to open an output key file for this generation and file number
  1236.  */
  1237.  
  1238. FILE *open_outkfile (generation_number, file_number)
  1239.   int generation_number, file_number;
  1240.   {
  1241.     FILE *fopen();
  1242.     char fname[32];
  1243.     
  1244.     sprintf (fname, "x%dk%d", generation_number + 1, file_number / NMERGE);
  1245.     return (fopen (fname, "wb"));
  1246.   }
  1247.  
  1248.  
  1249. /* function to open an output ptr file for this generation and file number
  1250.  */
  1251.  
  1252. FILE *open_outpfile (generation_number, file_number)
  1253.   int generation_number, file_number;
  1254.   {
  1255.     FILE *fopen();
  1256.     char fname[32];
  1257.     
  1258.     sprintf (fname, "x%dp%d", generation_number + 1, file_number / NMERGE);
  1259.     return (fopen (fname, "wb"));
  1260.   }
  1261.  
  1262.  
  1263. /* function to rename the remaining last unpaired key file & ptr file
  1264.  * from one generation to the next...
  1265.  */
  1266.  
  1267. void fix_oddball_file_name (generation_number, file_number)
  1268.   int generation_number, file_number;
  1269.   {
  1270.     char oldname[32], newname[32];
  1271.     
  1272.     sprintf (oldname, "x%dk%d", generation_number, file_number);
  1273.     sprintf (newname, "x%dk%d", generation_number + 1, file_number / NMERGE);
  1274.     if (rename (oldname, newname))
  1275.         printf ("Sorry -- error in attempt to rename %s to %s!\n", oldname,
  1276.                 newname);
  1277.     
  1278.     sprintf (oldname, "x%dp%d", generation_number, file_number);
  1279.     sprintf (newname, "x%dp%d", generation_number + 1, file_number / NMERGE);
  1280.     if (rename (oldname, newname))
  1281.         printf ("Sorry -- error in attempt to rename %s to %s!\n", oldname,
  1282.                 newname);
  1283.   }
  1284.  
  1285.  
  1286. /* function to give the final key and ptr files their proper ultimate
  1287.  * names ...
  1288.  */
  1289.  
  1290. void fix_final_file_names (generation_number, doc_filename)
  1291.   int generation_number;
  1292.   char *doc_filename;
  1293.   {
  1294.     char oldname[32], finalname[65];
  1295.     
  1296.     sprintf (oldname, "x%dk0", generation_number);
  1297.     sprintf (finalname, "%s.k", doc_filename);
  1298.     if (rename (oldname, finalname))
  1299.         printf ("Sorry -- error in renaming file %s to %s!\n", oldname,
  1300.                 finalname);
  1301.  
  1302.     sprintf (oldname, "x%dp0", generation_number);
  1303.     sprintf (finalname, "%s.p", doc_filename);
  1304.     if (rename (oldname, finalname))
  1305.         printf ("Sorry -- error in renaming file %s to %s!\n", oldname,
  1306.                 finalname);
  1307.   }
  1308.  
  1309.  
  1310. /* function to get rid of the superfluous k & p files now that they
  1311.  * have been merged into the next generation....
  1312.  */
  1313.  
  1314. void remove_used_infiles (generation_number, file_number, n)
  1315.   int generation_number, file_number, n;
  1316.   {
  1317.     char fname[32];
  1318.     register int i;
  1319.     
  1320.     for (i = 0; i < n; ++i)
  1321.       {
  1322.         sprintf (fname, "x%dk%d", generation_number, file_number + i);
  1323.         DEBUG ("--removing %s\n", fname);
  1324.         if (unlink (fname))
  1325.             printf ("Sorry -- unable to delete file %s!\n", fname);
  1326.         sprintf (fname, "x%dp%d", generation_number, file_number + i);
  1327.         DEBUG ("--removing %s\n", fname);
  1328.         if (unlink (fname))
  1329.             printf ("Sorry -- unable to delete file %s!\n", fname);
  1330.       }
  1331.   }
  1332.  
  1333.  
  1334. /* function to close out the ink and inp files that have been opened...
  1335.  */
  1336.  
  1337. void close_infiles (ink, inp, n)
  1338.   FILE *ink[], *inp[];
  1339.   register int n;
  1340.   {
  1341.     register int i;
  1342.     
  1343.     for (i = 0; i < n; ++i)
  1344.       {
  1345.         fclose (ink[i]);
  1346.         fclose (inp[i]);
  1347.       }
  1348.   }
  1349.  
  1350.  
  1351. /* ---------------------misc_utils.c----------------- */
  1352.  
  1353. /* file "misc_utils.c" -- miscellaneous utilities for the qndxr project...
  1354.  * by ^z -- 870821-...
  1355.  */
  1356.  
  1357.  
  1358. /* this function returns a value for the size of the internal buffers,
  1359.  * zbufsiz, and it also takes care of setting the other global parameters,
  1360.  * keep_all_punct, keep_embedded_punct, and keep_special_chars,
  1361.  * which govern how punctuation and special characters are handled.
  1362.  * They are set based on flags such as -e, -a, and -s in the input line.
  1363.  * The input parameters are taken one after another, and any that do
  1364.  * not convert to a nonzero number are scanned for the letters "e", "a", and
  1365.  * "s".  If a parameter is not reset, the default is to leave keep_all_punct,
  1366.  * keep_embedded_punct, and keep_special_chars as FALSE.
  1367.  * The default memory size is DEFAULT_MEMSIZ, set in the header file.
  1368.  */
  1369.  
  1370. long set_params (argc, argv)
  1371.   int argc;
  1372.   char *argv[];
  1373.   {
  1374.     int i;
  1375.     void set_parser_options();
  1376.     long zb = 0, n, atol(), set_zbufsiz();
  1377.     
  1378.     for (i = 2; i < argc; ++i)
  1379.       {
  1380.         n = atol (argv[i]);
  1381.         if (n != 0)
  1382.             zb = set_zbufsiz (n);
  1383.         else
  1384.             set_parser_options (argv[i]);
  1385.       }
  1386.     
  1387.     if (zb == 0)
  1388.         zb = set_zbufsiz (DEFAULT_MEMSIZ);
  1389.  
  1390.     return (zb);
  1391.   }
  1392.  
  1393.  
  1394.  
  1395. /* determine how big we should make the big buffers -- want to be sure
  1396.  * to have room for at least 2*NMERGE+2 of them at one time in memory,
  1397.  * so that the N-way merge function can hold all the input files
  1398.  * (2N) plus the output files (2).
  1399.  *
  1400.  * NOTE that the chosen buffer size must be a multiple of both sizeof(long)
  1401.  * and sizeof(KEY_REC); I ensure that very simply in what follows by
  1402.  * a little modular arithmetic.  I also take care of the sign and of the
  1403.  * requirement that the buffer size be non-zero -- thus, UNIX aficionados
  1404.  * can precede the parameter with a "-" with no ill effects.  I have put in
  1405.  * various safeguards against picking illegal buffer sizes, along with an
  1406.  * ultimate safety net small minimum value for zbufsiz.
  1407.  */
  1408.  
  1409. long set_zbufsiz (zb)
  1410.   long zb;
  1411.   {
  1412.     char *testb;
  1413.  
  1414.     if (zb < 0)
  1415.         zb = -zb;
  1416.     
  1417.     zb /=  (2 * NMERGE + 2);
  1418.     zb = zb - zb % (sizeof(KEY_REC) * sizeof(long));
  1419.     
  1420.     if (zb < sizeof(KEY_REC) * sizeof(long))
  1421.         zb = sizeof(KEY_REC) * sizeof(long);
  1422.  
  1423.     DEBUG ("--Checking for memory to support buffer size zb=%ld\n", zb);
  1424.     testb = make_buf ((2 * NMERGE + 2) * zb);
  1425.     free (testb);
  1426.     
  1427.     return (zb);
  1428.   }
  1429.  
  1430.  
  1431. /* function to set the parser options based on a character string ...
  1432.  * 'a' turns on keep_all_punct, 'e' turns on keep_embedded_punct,
  1433.  * and 's' turns on keep_special_chars
  1434.  */
  1435.  
  1436. void set_parser_options (str)
  1437.   char *str;
  1438.   {
  1439.     extern int keep_all_punct, keep_embedded_punct, keep_special_chars;
  1440.  
  1441.     while (*str)
  1442.       {
  1443.         if (*str == 'a')
  1444.           {
  1445.             keep_all_punct = TRUE;
  1446.             printf ("All punctuation characters will be kept.\n");
  1447.           }
  1448.         else if (*str == 'e')
  1449.           {
  1450.             keep_embedded_punct = TRUE;
  1451.             printf ("Embedded punctuation characters will be kept.\n");
  1452.           }
  1453.         else if (*str == 's')
  1454.           {
  1455.             keep_special_chars = TRUE;
  1456.             printf ("Special characters will be kept.\n");
  1457.           }
  1458.         
  1459.         ++str;
  1460.       }
  1461.   }
  1462.   
  1463.  
  1464.  
  1465. /* function to check for user interruption of operations (for use in the
  1466.  * Macintosh version of this program only) ... call SystemTask() to give
  1467.  * desk accessories a bit of time, and then check for non-null events
  1468.  * with GetNextEvent() ... if something comes along (a mouse click, or key
  1469.  * press, or whatever) let the user choose to exit the program or to
  1470.  * carry on ....
  1471.  */
  1472.  
  1473. #ifdef LIGHTSPEED
  1474.  
  1475. void check_interrupt ()
  1476.   {
  1477.     EventRecord myEvent;
  1478.     char cmd[256], *gets();
  1479.     void exit();
  1480.  
  1481.     SystemTask ();
  1482.     if (GetNextEvent (everyEvent, &myEvent))
  1483.       {
  1484.         fprintf (stderr, "\Quit indexing now?\n");
  1485.         gets (cmd);
  1486.         if (cmd[0] == 'y' || cmd[0] == 'Y')
  1487.             exit (0);
  1488.       }
  1489.   }
  1490.  
  1491. #endif
  1492.  
  1493.  
  1494. /* a very simple function to return the size of a file ... leave the file
  1495.  * pointer positioned at wherever it was when the routine was entered....
  1496.  * should work fine with stdio methods, but not guaranteed compatible when
  1497.  * mixed in with Mac-specific FSRead() function!
  1498.  */
  1499.  
  1500. long file_size (fp)
  1501.   FILE *fp;
  1502.   {
  1503.     long fpos, result, ftell();
  1504.     
  1505.     DEBUG ("--finding the size of file fp=%ld\n", fp);
  1506.     fpos = ftell (fp);
  1507.     fseek (fp, 0L, 2);
  1508.     result = ftell (fp);
  1509.     fseek (fp, fpos, 0);
  1510.     return (result);
  1511.   }
  1512.  
  1513.  
  1514. /* ----------------------open_files.c----------------- */
  1515.  
  1516. /* functions to open files as needed in qndxr work...
  1517.  */
  1518.  
  1519. FILE *open_docfile (argc, argv) 
  1520.   int argc;
  1521.   char *argv[];
  1522.   {
  1523.     FILE *fp, *fopen();
  1524.     void exit();
  1525.     
  1526.     if (argc < 2)
  1527.       {
  1528.         printf ("\nToo few command line arguments!\n");
  1529.         printf ("\nEnter a text file name (no embedded spaces allowed)\n");
  1530.         printf ("and the program will build and sort a complete inverted\n");
  1531.         printf ("index to that file.  Use \">\" in front of a file name to\n");
  1532.         printf ("redirect console output (UNIX-fashion) if desired.\n");
  1533.         printf ("Give the program a value for available memory (in bytes)\n");
  1534.         printf ("if the default value of 512kB is unsatisfactory ... larger\n");
  1535.         printf ("memory allows for faster index building and sorting.\n");
  1536.         printf ("Other command-line arguments:\n");
  1537.         printf ("  \"-e\" preserves embedded punctuation\n");
  1538.         printf ("  \"-a\" preserves all punctuation characters\n");
  1539.         printf ("  \"-s\" preserves special (non-ASCII) characters\n");
  1540.         printf ("\nContact Mark Zimmermann, 9511 Gwyndale Drive, Silver Spring\n");
  1541.         printf ("Maryland  20910  USA; 301-565-2166; science (at) nems.arpa;\n");
  1542.         printf ("[75066,2044] on CompuServe for further information. - ^z\n");
  1543.         exit (1);
  1544.       }
  1545.  
  1546.     if ((fp = fopen (argv[1], "r")) == NULL)
  1547.       {
  1548.         printf ("\nFatal error opening document file\"%s\"!\n", argv[1]);
  1549.         exit (1);
  1550.       }
  1551.     
  1552.     return (fp);
  1553.   }
  1554.  
  1555.  
  1556. /* open the key file with proper name for this pass ... file will be
  1557.  * named "x0kN" where N represents the pass number ....
  1558.  */
  1559.  
  1560. FILE *open_kfile (pass_number)
  1561.   int pass_number;
  1562.   {
  1563.     FILE *fopen();
  1564.     char fname[32];
  1565.     
  1566.     sprintf (fname, "x0k%d", pass_number);
  1567.     return (fopen (fname, "wb"));
  1568.   }
  1569.  
  1570.  
  1571. /* open the ptr file with proper name for this pass ... file will be
  1572.  * named "x0pN" where N represents the pass number ....
  1573.  */
  1574.  
  1575. FILE *open_pfile (pass_number)
  1576.   int pass_number;
  1577.   {
  1578.     FILE *fopen();
  1579.     char fname[32];
  1580.     
  1581.     sprintf (fname, "x0p%d", pass_number);
  1582.     return (fopen (fname, "wb"));
  1583.   }
  1584.  
  1585.  
  1586. /* ----------------------zqsort.c-------------------- */
  1587.  
  1588. /* file zqsort.c -- by ^z, 870823-...
  1589.  * my quicksort to sort out the ptr array ... based, at least initially,
  1590.  * on the Lightspeed C library qsort routine, specialized to the task
  1591.  * at hand here ...
  1592.  */
  1593.  
  1594.  
  1595. /*  sort elements "first" through "last" */
  1596.  
  1597. void zqsort (first, last)
  1598.   register char **first, **last;
  1599.   {
  1600.     register char **i, **j, *tmp;
  1601.  
  1602.     while (last - first > 1)
  1603.       {
  1604.         i = first;
  1605.         j = last;
  1606.         for (;;)
  1607.           {
  1608.             while (++i < last && compare_ptrs (i, first) < 0)
  1609.                 ;
  1610.             while (--j > first && compare_ptrs (j, first) > 0)
  1611.                 ;
  1612.             if (i >= j)
  1613.                  break;
  1614.              tmp = *i;
  1615.              *i = *j;
  1616.              *j = tmp;
  1617.           }
  1618.         tmp = *first;
  1619.         *first = *j;
  1620.         *j = tmp;
  1621.         if (j - first < last - (j + 1))
  1622.           {
  1623.             zqsort (first, j);
  1624.             first = j + 1;
  1625.           }
  1626.         else
  1627.           {
  1628.             zqsort (j + 1, last);
  1629.             last = j;
  1630.           }
  1631.       }
  1632.   }
  1633.  
  1634.  
  1635. /* function to compare two index ptrs and give a result appropriate
  1636.  * for quicksort to use in alphabetizing them....
  1637.  *
  1638.  * Since the words pointed to have already been turned into all capital
  1639.  * letters and delimiters have been filtered out, simply doing zstrcmp()
  1640.  * for KEY_LENGTH letters works fine!
  1641.  *
  1642.  * Slight modification to make the quicksort stable:  if two words tie,
  1643.  * then we want to compare their pointers to make the lesser one come
  1644.  * out first in the sort ...
  1645.  */
  1646.  
  1647. int compare_ptrs (p1, p2)
  1648.   register char **p1, **p2;
  1649.   {
  1650.     register int diff;
  1651.     
  1652.     diff = zstrcmp (*p1, *p2);
  1653.     if (diff == 0)
  1654.         diff = ((*p1 - *p2) > 0) ? 1 : -1;
  1655.     return (diff);
  1656.   }
  1657.  
  1658.  
  1659.  
  1660. /* my function to compare two strings and give a result as to who is
  1661.  * alphabetically earlier.  Note that this is almost the same as strncmp()
  1662.  * with the fixed value of KEY_LENGTH as the maximum comparison distance,
  1663.  * except that I must be sure to mask the characters to make them positive
  1664.  * (since we want to be able to handle the non-ASCII funny letters in
  1665.  * the Apple character set properly/consistently).  If the masking isn't
  1666.  * done, then inconsistent results can occur with those non-ASCII chars!
  1667.  */
  1668.  
  1669. int zstrcmp (s1, s2)
  1670.   register char *s1, *s2;
  1671.   {
  1672.     register int n = KEY_LENGTH;
  1673.     
  1674.     for (; --n && ((*s1 & CMASK) == (*s2 & CMASK)); s1++, s2++)
  1675.         if (!*s1) break;
  1676.         
  1677.     return ((*s1 & CMASK) - (*s2 & CMASK));
  1678.   }
  1679.  
  1680.  
  1681. -------
  1682.  
  1683.  
  1684.