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