home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume13 / combine / part03 < prev    next >
Encoding:
Text File  |  1990-06-15  |  54.6 KB  |  2,107 lines
  1. Newsgroups: comp.sources.misc
  2. subject: v13i056: combine: 3 file compare/merge utility (part 3of3)
  3. from: cliff@gcx1.SSD.CSD.HARRIS.COM (Cliff Van Dyke)
  4. Sender: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc)
  5.  
  6. Posting-number: Volume 13, Issue 56
  7. Submitted-by: cliff@gcx1.SSD.CSD.HARRIS.COM (Cliff Van Dyke)
  8. Archive-name: combine/part03
  9.  
  10. # This is a shell archive.  Remove anything before this line,
  11. # then unpack it by saving it in a file and typing "sh file".
  12. #
  13. # Wrapped by cliff on Tue Feb 13 14:14:08 EST 1990
  14. # Contents:  pass1.c pass3.c pass4.c pass5.c
  15.  
  16. echo x - pass1.c
  17. sed 's/^@//' > "pass1.c" <<'@//E*O*F pass1.c//'
  18. /*
  19.  * The combine utility is a product of Harris, Inc. and is provided for
  20.  * unrestricted use provided that this legend is included on all tape
  21.  * media and as a part of the software program in whole or part.  Users
  22.  * may copy, modify, license or distribute the combine utility without charge.
  23.  * 
  24.  * THE COMBINE UTILITY IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND
  25.  * INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR A
  26.  * PARTICULAR PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE
  27.  * PRACTICE.
  28.  * 
  29.  * The combine utility is provided with no support and without any obligation
  30.  * on the part of Harris, Inc. to assist in its use, correction,
  31.  * modification or enhancement.
  32.  * 
  33.  * HARRIS, INC. SHALL HAVE NO LIABILITY WITH RESPECT TO THE
  34.  * INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THE COMBINE
  35.  * UTILITY OR ANY PART THEREOF.
  36.  * 
  37.  * In no event will Harris, Inc. be liable for any lost revenue
  38.  * or profits or other special, indirect and consequential damages, even if
  39.  * Harris has been advised of the possibility of such damages.
  40.  * 
  41.  * Harris Computer Systems Division
  42.  * 2101 W Cypress Creek Rd
  43.  * Fort Lauderdale, Florida 33309
  44.  */
  45. #include <stdio.h>
  46. #include <ctype.h>
  47. #include "util.h"
  48. #include "combine.h"
  49. /*
  50.  * pass1: Perform the file read and table build pass
  51.  *
  52.  * This routine reads all of the records of all of the input files
  53.  * into the cache, symbol table, and record array.
  54.  *
  55.  * This routine alternately reads one record from each file. Assuming
  56.  * that the files have similar contents, this technique improves the
  57.  * chance that a record from the second and third files will be in
  58.  * the cache.
  59.  *
  60.  * Return value:
  61.  *    This procedure has no return value.
  62.  */
  63.  
  64. void pass1 () {
  65.  
  66.     int    i;        /* Misc. variable */
  67.  
  68.     int    index;        /* Index into record array */
  69.  
  70.     int    files_left;    /* number of files left to do */
  71.  
  72.     bool file_done[MAX_FILE_COUNT];/* TRUE if EOT reached on file */
  73.  
  74.     int    status;        /* Misc. status variable */
  75.  
  76.  
  77.  
  78.        /*
  79.     * Initialize completion parameters.
  80.     */
  81.  
  82.     files_left = file_count;
  83.     for (i = 0; i < file_count; ++i) {
  84.         file_done[i] = FALSE;
  85.     }
  86.  
  87.  
  88.     /*
  89.      * For each iteration of the file read the nth record of the each file.
  90.      */
  91.  
  92.     for (index = BEGIN_INDEX + 1; files_left != 0; ++index) {
  93.  
  94.         /*
  95.          * Handle each file.
  96.          */
  97.  
  98.         for (i = 0; i < file_count; ++i) {
  99.  
  100.             if (!file_done[i]) {
  101.  
  102.                 if (index + 1 >= files[i].record_array_alloc) {
  103.                     files[i].record_array_alloc += RA_INCR;
  104.                     files[i].record = (record_type *)
  105.                         realloc(files[i].record,
  106.                         files[i].record_array_alloc * sizeof (record_type));
  107.                     if ( files[i].record == 0 ){
  108.                         error( "out of memory -- files are way too big");
  109.                     }
  110.                 }
  111.  
  112.                 status = pass1_read_record (&files[i], index);
  113.  
  114.                 if (status < 0) {
  115.                     file_done[i] = TRUE;
  116.                     files[i].record_array_size = index + 1;
  117.                     --files_left;
  118.                     if (files_left == 0) {
  119.                         break;
  120.                     }
  121.                 }
  122.  
  123.             }
  124.  
  125.         }
  126.  
  127.     }
  128.  
  129. }
  130. /*
  131.  * pass1_read_record: read a record for pass 1
  132.  *
  133.  * This routine reads a record into the cache, symbol table, and record
  134.  * array.
  135.  * For each record read, a unique hash value is computed.
  136.  * That hash value is an index into the symbol table.
  137.  *
  138.  * Return value:
  139.  *     0:   record read as requested.
  140.  *    -1:   end of the file was reached.
  141.  */
  142.  
  143. int    pass1_read_record (file_ptr, index)
  144.     file_type * file_ptr;    /* input -- Description of the file
  145.                    to read record from. */
  146.  
  147.     int    index;        /* input -- Record number of the record
  148.                    currently being read. */
  149.  
  150. {
  151.  
  152.     static    cache_entry_type * cache_ptr = 0;
  153.                 /* Pointer to the cache entry which is used to read into. This cache buffer is linked onto the cache list if this is the first time the record is read. */
  154.  
  155.     register int   *end_int_ptr;
  156.                 /* Pointer to last integer in hashing algorithm */
  157.  
  158.     cache_entry_type * found_cache_ptr;
  159.                 /* Pointer to the cache entry found by hashing */
  160.  
  161.     register int   *found_int_ptr;/* co-erced pointer to found record */
  162.  
  163.     int    hash_code;    /* index into symbol table */
  164.  
  165.     int    i;        /* Misc. variable */
  166.  
  167.     register int   *int_ptr;/* Co-erced pointer to read record */
  168.  
  169.     char    mbuffer[LINE_LENGTH];/* Misc. buffer */
  170.  
  171.     int    probe_count;    /* Number a rehashes attempted. */
  172.  
  173.     int    quotient;    /* quotient of sum/table size.
  174.                    This value is used as the increment when
  175.                    re-hashing into the symbol table */
  176.  
  177.     cache_entry_type * reread_cache_ptr;
  178.                 /* Pointer to the cache buffer used for cache
  179.                    re-read operation. */
  180.  
  181.     file_type * reread_file_ptr;
  182.                 /* Pointer to the file to read from on a
  183.                    cache re-read operation. */
  184.  
  185.     int    reread_index;    /* Record number to read on a cache re-read operation. */
  186.  
  187.     rfa_type rfa;        /* RFA of record read */
  188.  
  189.     int    status;        /* Misc. status variable */
  190.  
  191.     register int    sum;    /* Sum of all bytes in a record */
  192.  
  193.  
  194.     /*
  195.      * If we don't have a cache buffer laying around,
  196.      *    delink one from end of list.
  197.      */
  198.  
  199.     if (cache_ptr == 0) {
  200.         deq_tail_dll (cache_head_ptr, cache_tail_ptr, cache_ptr,
  201.                 cache_next_ptr, cache_prev_ptr);
  202.         if (cache_ptr -> hash_code != HASH_FREE_ENTRY) {
  203.             sym_tab_cache_ptr[cache_ptr -> hash_code] =
  204.                 (cache_entry_type *) CACHE_NOT_IN_CACHE;
  205.         }
  206.     }
  207.  
  208.     /*
  209.      * Read the next record into our local cache entry.
  210.      */
  211.  
  212.     rfa = ftell(file_ptr->seq_fd);
  213.     if (p1_debug) {
  214.         printf ("index: %d hash_col: %d cache_miss: %d",
  215.                 index, hash_collisions, cache_miss);
  216.     }
  217.  
  218.     status = read_into_cache( file_ptr -> seq_fd, rfa, cache_ptr );
  219.     if (status < 0) {
  220.         return (-1);
  221.     }
  222.  
  223.     /*
  224.      * Pad to end of word with blanks, this allows hashing and comparison
  225.      * algorithms to be word oriented rather than byte oriented.
  226.      *
  227.      * Compress the record based on input parameters.
  228.      */
  229.  
  230.     if (cache_ptr -> record_length >= 0) {
  231.  
  232.         if (compress_records) {
  233.             pass1_record_compress (cache_ptr -> recordp,
  234.                     &cache_ptr -> record_length);
  235.         }
  236.  
  237.         /* Pad to the end of the word with blanks */
  238.         for (i = 0; i < sizeof (int) - 1; ++i) {
  239.             cache_ptr->recordp[cache_ptr->record_length + i] = ' ';
  240.         }
  241.     }
  242.  
  243.     /*
  244.      * Compute hash code for the record.
  245.      *
  246.      * The value is shifted on each iteration to ensure that the
  247.      * magnitude of the sum is large enough. Otherwise when the sum is
  248.      * divided by the size of the symbol table, the remainder will be
  249.      * clustered toward the beginning of the table.
  250.      */
  251.  
  252.     sum = 0;
  253.     int_ptr = (int *) cache_ptr -> recordp;
  254.     end_int_ptr = int_ptr +
  255.         ((cache_ptr->record_length + sizeof (int) - 1) / sizeof (int));
  256.     for (; int_ptr < end_int_ptr; int_ptr++) {
  257.  
  258.     /*    if (p1_debug) {
  259.             printf ("sum: %x ", sum);
  260.         }*/
  261.     /*
  262.      * The next statement does a left rotate of 7. The add operation is
  263.      * used instead of a logical-or operation since the right shift
  264.      * is an arithmetic shift which propogates the sign bit. An
  265.      * or operation into 25 bits of propogated sign bit loses a lot
  266.      * of significance.
  267.      */
  268.         sum = (sum >> (sizeof (int) * 8 - 7)) + (sum << 7);/* left rotate 7 */
  269.     /*    if (p1_debug) {
  270.             printf ("sum<<7: %x ", sum);
  271.         } */
  272.         sum += *int_ptr;
  273.     /*    if (p1_debug) {
  274.             printf ("sum:%x value:%X\n", sum, *int_ptr);
  275.         } */
  276.     }
  277.     sum = abs (sum);
  278.     if (p1_debug) {
  279.         printf ("sum: %d ", sum);
  280.     }
  281.  
  282.     hash_code = sum % sym_tab_size;
  283.     quotient = sum / sym_tab_size;
  284.     if ((quotient % sym_tab_size) == 0) {
  285.         quotient = 1;
  286.     }
  287.  
  288.     /*
  289.      * Loop until a unique hash code is found.
  290.      */
  291.  
  292.     for (probe_count = 0; probe_count < sym_tab_size;
  293.             ++probe_count, ++hash_collisions) {
  294.         do {
  295.             hash_code = (hash_code + quotient) % sym_tab_size;
  296.         } while (hash_code == 0);/* ensure sym tab loc 0 is never used */
  297.  
  298.         /*
  299.          * if symbol table entry is used but record is not is cache,
  300.          *     read record into cache by flushing the least recently
  301.          *    entry entry from the cache.
  302.          */
  303.  
  304.         if (p1_debug) {
  305.             printf ("hash_code: %d\n", hash_code);
  306.         }
  307.  
  308.         if ((int) sym_tab_cache_ptr[hash_code] == CACHE_NOT_IN_CACHE) {
  309.  
  310.             cache_miss++;
  311.             if (p1_debug) {
  312.                 printf ("cache_miss\n");
  313.             }
  314.  
  315.             deq_tail_dll (cache_head_ptr, cache_tail_ptr, reread_cache_ptr,
  316.                     cache_next_ptr, cache_prev_ptr);
  317.  
  318.             if (reread_cache_ptr -> hash_code != HASH_FREE_ENTRY) {
  319.                 sym_tab_cache_ptr[reread_cache_ptr -> hash_code] =
  320.                     (cache_entry_type *) CACHE_NOT_IN_CACHE;
  321.             }
  322.  
  323.             for (i = 0; i < file_count; ++i) {
  324.                 if (files[i].sym_tab_index[hash_code] != 0) {
  325.                     reread_file_ptr = &files[i];
  326.                     break;
  327.                 }
  328.             }
  329.  
  330.             if (i == file_count) {
  331.                 error ("Consistency error on rehash read");
  332.             }
  333.  
  334.             reread_index = abs (reread_file_ptr -> sym_tab_index[hash_code]);
  335.  
  336.             reread_into_cache( reread_file_ptr, reread_index,
  337.                 reread_cache_ptr);
  338.  
  339.             if (reread_cache_ptr -> record_length >= 0) {
  340.  
  341.                 if (compress_records) {
  342.                     pass1_record_compress (
  343.                         reread_cache_ptr -> recordp,
  344.                         &reread_cache_ptr -> record_length);
  345.                 }
  346.  
  347.                 for (i = 0; i < sizeof (int) - 1; ++i) {
  348.                     reread_cache_ptr->
  349.                     recordp[reread_cache_ptr->record_length + i] = ' ';
  350.                 }
  351.             }
  352.  
  353.             if (p1_debug) {
  354.                 printf ("%d %s\n",
  355.                     reread_cache_ptr -> record_length,
  356.                     reread_cache_ptr -> recordp);
  357.             }
  358.  
  359.             sym_tab_cache_ptr[hash_code] = reread_cache_ptr;
  360.             reread_cache_ptr -> hash_code = hash_code;
  361.             enq_head_dll (cache_head_ptr, cache_tail_ptr,
  362.                     reread_cache_ptr,
  363.                     cache_next_ptr, cache_prev_ptr);
  364.         }
  365.  
  366.         /*
  367.          * if this is the first time this hash code has been used,
  368.          *     point the symbol table to the cache entry,
  369.          *     insert the cache entry in the front of the cache.
  370.          *     break out of loop.
  371.          */
  372.  
  373.         if (sym_tab_cache_ptr[hash_code] == CACHE_FREE_ENTRY) {
  374.             if (p1_debug) {
  375.                 printf ("cache_free_entry\n");
  376.             }
  377.             sym_tab_cache_ptr[hash_code] = cache_ptr;
  378.             cache_ptr -> hash_code = hash_code;
  379.             enq_head_dll (cache_head_ptr, cache_tail_ptr, cache_ptr,
  380.                     cache_next_ptr, cache_prev_ptr);
  381.             cache_ptr = 0;
  382.             break;
  383.  
  384.         /*
  385.          * if this hash code is used and the record is in cache,
  386.          *     Compare our record with the one in the cache.
  387.          *     if the records are the same,
  388.          *      move cache entry to front of list,
  389.          *      break out of the loop.
  390.          */
  391.  
  392.         } else {
  393.             found_cache_ptr = sym_tab_cache_ptr[hash_code];
  394.             if (p1_debug) {
  395.                 printf ("len1: %d len2: %d\n",
  396.                     cache_ptr -> record_length,
  397.                     found_cache_ptr -> record_length);
  398.             }
  399.             if (cache_ptr->record_length ==
  400.                 found_cache_ptr->record_length) {
  401.  
  402.                 found_int_ptr = (int *) found_cache_ptr->recordp;
  403.                 int_ptr = (int *) cache_ptr -> recordp;
  404.                 end_int_ptr = int_ptr +
  405.                     ((cache_ptr -> record_length +
  406.                     sizeof (int) - 1) / sizeof (int));
  407.                 for (; int_ptr < end_int_ptr; int_ptr++) {
  408.                 /* printf( "v1: %x v2:%x\n", *int_ptr, *found_int_ptr ) ; */
  409.                     if (*int_ptr != *found_int_ptr) {
  410.                         break;
  411.                     }
  412.                     found_int_ptr++;
  413.                 }
  414.  
  415.                 if (int_ptr >= end_int_ptr) {
  416.                     rem_dll (cache_head_ptr,
  417.                          cache_tail_ptr,
  418.                          found_cache_ptr,
  419.                          cache_next_ptr,
  420.                          cache_prev_ptr);
  421.                     enq_head_dll (cache_head_ptr,
  422.                               cache_tail_ptr,
  423.                               found_cache_ptr,
  424.                               cache_next_ptr,
  425.                               cache_prev_ptr);
  426.                     break;
  427.                 }
  428.  
  429.             }
  430.         }
  431.  
  432.     }
  433.  
  434.     if (probe_count == sym_tab_size) {
  435.         error ("Symbol table overflow");
  436.     }
  437.  
  438.     /*
  439.      * If the record array for the file has overflowed,
  440.      *     fatal error.
  441.      */
  442.  
  443.     if (index + 1 >= file_ptr -> record_array_alloc) {
  444.         error ("record array size computed wrong");
  445.     }
  446.  
  447.      /*
  448.       * Install record into record array.
  449.       */
  450.  
  451.     file_ptr -> record[index].rfa = rfa;
  452.     file_ptr -> record[index].value[0] = -hash_code;
  453.     file_ptr -> record[index].value[1] = -hash_code;
  454.  
  455.     /*
  456.      * Install line into symbol table.
  457.      */
  458.  
  459.     if (file_ptr -> sym_tab_index[hash_code] == 0) {
  460.         file_ptr -> sym_tab_index[hash_code] = index;
  461.     }
  462.     else {
  463.         file_ptr -> sym_tab_index[hash_code] = -index;
  464.     }
  465.  
  466.     return (0);
  467.  
  468. }
  469. /*
  470.  * pass1_record_compress: compress out insignificant bytes in a record.
  471.  *
  472.  * This routine handles options which compares only a portion of the
  473.  * record. For the -b option, all occurrences of multiple blanks are
  474.  * compressed into a single blank. For the -c option, all columns not
  475.  * specified are removed.
  476.  *
  477.  * Return value:
  478.  *    This procedure has no return value.
  479.  */
  480.  
  481. void pass1_record_compress (record_ptr, record_len_ptr)
  482.     char   *record_ptr;    /* input/output */
  483.                 /* Record to be compressed in place. */
  484.  
  485.     int    *record_len_ptr; /* input/output */
  486.                 /* Length of record. */
  487.  
  488. {
  489.  
  490.     int    i;        /* Misc. variable */
  491.  
  492.     int    j;        /* Misc. variable */
  493.  
  494.     int    k;        /* Misc. variable */
  495.  
  496.     bool space;        /* TRUE if currently doing a space or tab sequence */
  497.  
  498.  
  499.     /*
  500.      * Handle column ranges:
  501.      */
  502.     if (column_count != 0) {
  503.         k = 0;
  504.         for (i = 0; i < column_count; ++i) {
  505.  
  506.             for (j = first_column[i];
  507.                 j <= last_column[i] && j < *record_len_ptr;
  508.                 ++j) {
  509.  
  510.                 record_ptr[k] = record_ptr[j];
  511.                 ++k;
  512.             }
  513.  
  514.         }
  515.  
  516.         *record_len_ptr = k;
  517.  
  518.     }
  519.  
  520.     /*
  521.      * Handle blank compression:
  522.      *
  523.      * Blank compression converts all groups of blanks and horizontal
  524.      * tabs to a single blank.
  525.      */
  526.  
  527.     if (blank_compress) {
  528.         k = 0;
  529.         space = FALSE;
  530.  
  531.         for (i = 0; i < *record_len_ptr; ++i) {
  532.  
  533.             if (record_ptr[i] == ' ' || record_ptr[i] == '\t') {
  534.                 space = TRUE;
  535.             } else {
  536.                 if (space) {
  537.                     record_ptr[k++] = ' ';
  538.                     space = FALSE;
  539.                 }
  540.                 record_ptr[k++] = record_ptr[i];
  541.             }
  542.  
  543.         }
  544.  
  545.         if (space) {
  546.             record_ptr[k++] = ' ';
  547.         }
  548.  
  549.         *record_len_ptr = k;
  550.  
  551.     }
  552.  
  553.     /*
  554.      * Handle blank removal:
  555.      *
  556.      * Blank removal removes all blanks and horizontal tabs.
  557.      */
  558.  
  559.     if (blank_remove) {
  560.         k = 0;
  561.         space = FALSE;
  562.  
  563.         for (i = 0; i < *record_len_ptr; ++i) {
  564.  
  565.             if (record_ptr[i] == ' ' || record_ptr[i] == '\t') {
  566.                 space = TRUE;
  567.             } else {
  568.                 if (space) {
  569.                     space = FALSE;
  570.                 }
  571.                 record_ptr[k++] = record_ptr[i];
  572.             }
  573.  
  574.         }
  575.  
  576.         *record_len_ptr = k;
  577.  
  578.     }
  579.  
  580. }
  581. @//E*O*F pass1.c//
  582. chmod u=rw,g=rw,o=rw pass1.c
  583.  
  584. echo x - pass3.c
  585. sed 's/^@//' > "pass3.c" <<'@//E*O*F pass3.c//'
  586. /*
  587.  * The combine utility is a product of Harris, Inc. and is provided for
  588.  * unrestricted use provided that this legend is included on all tape
  589.  * media and as a part of the software program in whole or part.  Users
  590.  * may copy, modify, license or distribute the combine utility without charge.
  591.  * 
  592.  * THE COMBINE UTILITY IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND
  593.  * INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR A
  594.  * PARTICULAR PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE
  595.  * PRACTICE.
  596.  * 
  597.  * The combine utility is provided with no support and without any obligation
  598.  * on the part of Harris, Inc. to assist in its use, correction,
  599.  * modification or enhancement.
  600.  * 
  601.  * HARRIS, INC. SHALL HAVE NO LIABILITY WITH RESPECT TO THE
  602.  * INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THE COMBINE
  603.  * UTILITY OR ANY PART THEREOF.
  604.  * 
  605.  * In no event will Harris, Inc. be liable for any lost revenue
  606.  * or profits or other special, indirect and consequential damages, even if
  607.  * Harris has been advised of the possibility of such damages.
  608.  * 
  609.  * Harris Computer Systems Division
  610.  * 2101 W Cypress Creek Rd
  611.  * Fort Lauderdale, Florida 33309
  612.  */
  613. #include <stdio.h>
  614. #include <ctype.h>
  615. #include "util.h"
  616. #include "combine.h"
  617. /*
  618.  * pass3: Expand anchors to non-unique records.
  619.  *
  620.  * If in a pair of files immediately adjacent to an anchor point
  621.  * there are lines which are identical to each other, these lines
  622.  * are then considered to be anchor points. Repeated application of this
  623.  * principle on each possible pair of files and in each possible direction
  624.  * results in all matched lines being found.
  625.  *
  626.  * This routine calls the 'pass3_scan' routine once for each combination of
  627.  * file pairs and directions.
  628.  *
  629.  * Possible design flaw: If a particular anchor exists in all three files,
  630.  * should adjacent records be considered to be an anchor only if all
  631.  * three adjacent records are identical.
  632.  *
  633.  * Return value:
  634.  *      This procedure has no return value.
  635.  */
  636.  
  637. void pass3 () {
  638.  
  639.     int     i;        /* Misc. variable */
  640.  
  641.     int     j;        /* Misc. variable */
  642.  
  643.     /*
  644.      * Scan each pair of files in the forward direction.
  645.      */
  646.  
  647.     for (j = 0; j < UNIQUE_MATCH_COUNT; ++j) {
  648.  
  649.         i = unique_match[j];
  650.  
  651.         if (files[curr_file[i]].record != 0 &&
  652.                 files[corres_file[i]].record != 0) {
  653.  
  654.             pass3_scan (i, 1);
  655.  
  656.         }
  657.  
  658.     }
  659.  
  660.     /*
  661.      * Scan each pair of files in the reverse direction.
  662.      */
  663.     for (j = 0; j < UNIQUE_MATCH_COUNT; ++j) {
  664.  
  665.         i = unique_match[j];
  666.  
  667.         if (files[curr_file[i]].record != 0 &&
  668.                 files[corres_file[i]].record != 0) {
  669.  
  670.             pass3_scan (i, -1);
  671.  
  672.         }
  673.  
  674.     }
  675.  
  676. }
  677. /*
  678.  * pass3_scan: Expand anchors to non-unique records.
  679.  *
  680.  * This routine scans the record arrays for a pair of files in one
  681.  * direction expanding anchors. For each record in the first file,
  682.  * if the current record is an anchor, and the next record in each file
  683.  * is a hash code (i.e. not an anchor), and the hash codes are the same,
  684.  * then the next records are considered to be anchors.
  685.  *
  686.  * Return value:
  687.  *      This procedure has no return value.
  688.  */
  689. void pass3_scan (match_no, direction)
  690. int     match_no;        /* input */
  691.                 /* Which relationship is being scanned */
  692.  
  693. int     direction;        /* This is the direction to scan the file.
  694.                    Valid values are 1 for forward and -1 for
  695.                    backward. */
  696.  
  697. {
  698.  
  699.     int     end_index1;    /* Index into record array of file1 of end of
  700.                    the record array. (e.g. the first record to
  701.                    not process when going in 'direction') */
  702.  
  703.     file_type * file1_ptr;    /* First file - current_file */
  704.  
  705.     file_type * file2_ptr;    /* Second file - corresponding file */
  706.  
  707.     int     file1_sub;    /* For each record of the first file, this is a
  708.                    subscript of the 'value' array of the
  709.                    relationship between file1 and file2 */
  710.  
  711.     int     file2_sub;    /* For each record of the second file, this is
  712.                    a subscript of the 'value' array of the
  713.                    relationship between file2 and file1 */
  714.  
  715.     int     index1;        /* Index into record array of file1 of the
  716.                    record currently being processed */
  717.  
  718.     int     index2;        /* Index into record array of file2 of the
  719.                    record anchored to the 'index1' record */
  720.  
  721.     record_type * record1;    /* Pointer to record array of file1 */
  722.  
  723.     record_type * record2;    /* Pointer to record array of file2 */
  724.  
  725.     int    *val1_ptr;    /* Pointer to the 'value' field in 'next'
  726.                    record on file1. This is the 'value' which
  727.                    indicates the relationship to file2. */
  728.  
  729.     int    *val2_ptr;    /* Pointer to the 'value' field in 'next'
  730.                    record on file2. This is the 'value' which
  731.                    indicates the relationship to file1. */
  732.  
  733.  
  734.     /*
  735.      * Initialize indexes to first and last record of the files.
  736.      */
  737.     file1_ptr = &files[curr_file[match_no]];
  738.     file2_ptr = &files[corres_file[match_no]];
  739.     file1_sub = value_sub[match_no];
  740.     file2_sub = rev_value_sub[match_no];
  741.  
  742.     record1 = file1_ptr -> record;
  743.     record2 = file2_ptr -> record;
  744.  
  745.     if (direction == 1) {
  746.         index1 = BEGIN_INDEX;
  747.         end_index1 = file1_ptr -> record_array_size - 1;
  748.     } else {
  749.         index1 = file1_ptr -> record_array_size - 1;
  750.         end_index1 = BEGIN_INDEX;
  751.     }
  752.  
  753.     /*
  754.      * For each record in the first file.
  755.      *
  756.      * Note: given the existence of the 'begin' and 'end' record on each
  757.      * end of the record array, and given the way the 'end_index1'
  758.      * was set up above (so as to not process the last record
  759.      * on the opposite end of the file from which the scan started),
  760.      * we can convince ourselves that the tests below won't ever index
  761.      * off the end of the arrays.
  762.      */
  763.     for (; index1 != end_index1; index1 += direction) {
  764.  
  765.         /*
  766.          * If the current record in file1 is an anchor point,
  767.          *     Compute the index into file2 of the corresponding record.
  768.          *     Compute a pointer to value field of the next record in each file.
  769.          */
  770.  
  771.         index2 = record1[index1].value[file1_sub];
  772.         if (!is_hash_code (index2)) {
  773.  
  774.             val1_ptr = &(record1[index1 + direction].
  775.                 value[file1_sub]);
  776.             val2_ptr = &(record2[index2 + direction].
  777.                 value[file2_sub]);
  778.  
  779.             /*
  780.              * If the neither of the next records are anchor points and
  781.              *     the records are identical,
  782.              *     consider these records to be anchors.
  783.              */
  784.             if (is_hash_code (*val1_ptr) &&
  785.                     is_hash_code (*val2_ptr) &&
  786.                     *val1_ptr == *val2_ptr) {
  787.  
  788.                 link_records (match_no, index1 + direction,
  789.                     index2 + direction);
  790.  
  791.             }
  792.  
  793.         }
  794.  
  795.     }
  796.  
  797. }
  798. @//E*O*F pass3.c//
  799. chmod u=rw,g=rw,o=rw pass3.c
  800.  
  801. echo x - pass4.c
  802. sed 's/^@//' > "pass4.c" <<'@//E*O*F pass4.c//'
  803. /*
  804.  * The combine utility is a product of Harris, Inc. and is provided for
  805.  * unrestricted use provided that this legend is included on all tape
  806.  * media and as a part of the software program in whole or part.  Users
  807.  * may copy, modify, license or distribute the combine utility without charge.
  808.  * 
  809.  * THE COMBINE UTILITY IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND
  810.  * INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR A
  811.  * PARTICULAR PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE
  812.  * PRACTICE.
  813.  * 
  814.  * The combine utility is provided with no support and without any obligation
  815.  * on the part of Harris, Inc. to assist in its use, correction,
  816.  * modification or enhancement.
  817.  * 
  818.  * HARRIS, INC. SHALL HAVE NO LIABILITY WITH RESPECT TO THE
  819.  * INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THE COMBINE
  820.  * UTILITY OR ANY PART THEREOF.
  821.  * 
  822.  * In no event will Harris, Inc. be liable for any lost revenue
  823.  * or profits or other special, indirect and consequential damages, even if
  824.  * Harris has been advised of the possibility of such damages.
  825.  * 
  826.  * Harris Computer Systems Division
  827.  * 2101 W Cypress Creek Rd
  828.  * Fort Lauderdale, Florida 33309
  829.  */
  830. #include <stdio.h>
  831. #include <ctype.h>
  832. #include "util.h"
  833. #include "combine.h"
  834. /*
  835.  * pass4: Handle non-unique record clusters.
  836.  *
  837.  * This routine tries to fix up problems which arise due to groups of
  838.  * non-unique records which are surrounded by insertions. When this
  839.  * condition arises, the group of non-unique records are treated as
  840.  * a part of the inserted text.
  841.  *
  842.  * This routine finds a pair of anchor records which have inserted lines
  843.  * between them. (See diagram below.) All inserted lines are compared
  844.  * to one another trying to find a group of non-unique lines which
  845.  * match. Such lines are considered equal and are flagged as anchor
  846.  * points.
  847.  *
  848.  *          match1                       match1
  849.  *          insert
  850.  *          non-unique1                  non-unique1
  851.  *          insert
  852.  *          match2                       match2
  853.  *
  854.  * This routine runs in M x N time where 'M' is the number of lines
  855.  * inserted at the current position in the first file and 'N' is the number
  856.  * of lines inserted at the current position in the second file.
  857.  *
  858.  * Possible design flaw: The algorithm used to match the non-unique lines
  859.  * should really be the same alogirthm used for the rest of the file.
  860.  * That algorithm runs in linear time. The main problem with doing that is
  861.  * that the other passes of this program were not designed for or optimized
  862.  * around working for a portion of a file. Also, the proposed algorithm
  863.  * relies on the fact that some of the non-unique lines will become unique
  864.  * when only this fragment of the files are compared.
  865.  *
  866.  * Return value:
  867.  *      This procedure has no return value.
  868.  */
  869.  
  870. void pass4 () {
  871.  
  872.     int     i;        /* Misc. variable */
  873.  
  874.     int     j;        /* Misc. variable */
  875.  
  876.     /*
  877.      * Scan each pair of files.
  878.      */
  879.  
  880.     for (j = 0; j < UNIQUE_MATCH_COUNT; ++j) {
  881.  
  882.         i = unique_match[j];
  883.  
  884.         if (files[curr_file[i]].record != 0 &&
  885.                 files[corres_file[i]].record != 0) {
  886.  
  887.             pass4_scan (i);
  888.  
  889.         }
  890.  
  891.     }
  892.  
  893. }
  894. /*
  895.  * pass4_scan: pass4 for two files.
  896.  *
  897.  * This routine implements the pass4 algorithm for a pair of files.
  898.  *
  899.  * Return value:
  900.  *      This procedure has no return value.
  901.  */
  902.  
  903. void pass4_scan (match_no)
  904. int     match_no;        /* input */
  905.                 /* Which relationship is being scanned */
  906.  
  907. {
  908.  
  909.     register int i;        /* Index into record array of file1 of the
  910.                    current position in the inserted records */
  911.  
  912.     register int j;        /* Index into record array of file2 of the
  913.                    current position in the inserted records */
  914.  
  915.     file_type * file1_ptr;    /* First file - current_file */
  916.  
  917.     file_type * file2_ptr;    /* Second file - corresponding file */
  918.  
  919.     int     file1_sub;    /* For each record of the first file, this is a
  920.                    subscript of the 'value' array of the
  921.                    relationship between file1 and file2 */
  922.  
  923.     int     file2_sub;    /* For each record of the second file, this is
  924.                    a subscript of the 'value' array of the
  925.                    relationship between file2 and file1 */
  926.  
  927.     register int fn_index1;    /* Index into record array of file1 of the
  928.                    position of the last inserted record */
  929.  
  930.     register int fn_index2;    /* Index into record array of file2 of the
  931.                    position of the last inserted record */
  932.  
  933.     int     index1;        /* Index into record array of file1 of the
  934.                    record currently being processed */
  935.  
  936.     record_type * record1;    /* Pointer to record array of file1 */
  937.  
  938.     record_type * record2;    /* Pointer to record array of file2 */
  939.  
  940.     register int st_index1;    /* Index into record array of file1 of the
  941.                    position of the first inserted record */
  942.  
  943.     register int st_index2;    /* Index into record array of file2 of the
  944.                    position of the first inserted record */
  945.  
  946.  
  947.     /*
  948.      * Initialize indexes to first and last record of the files.
  949.      */
  950.  
  951.     file1_ptr = &files[curr_file[match_no]];
  952.     file2_ptr = &files[corres_file[match_no]];
  953.     file1_sub = value_sub[match_no];
  954.     file2_sub = rev_value_sub[match_no];
  955.  
  956.     record1 = file1_ptr -> record;
  957.     record2 = file2_ptr -> record;
  958.  
  959.     /*
  960.      * For each record in the first file.
  961.      *
  962.      * Note: given the existence of the 'begin' and 'end' record on each
  963.      * end of the record array,
  964.      * we can convince ourselves that the tests below won't ever index
  965.      * off the end of the arrays.
  966.      */
  967.     for (index1 = BEGIN_INDEX; index1 < file1_ptr->record_array_size-1;
  968.         index1++) {
  969.  
  970.         /*
  971.          * If the current record in file1 is not an anchor point,
  972.          *     continue the big loop.
  973.          */
  974.         st_index2 = record1[index1].value[file1_sub];
  975.         if (is_hash_code (st_index2)) {
  976.             continue;
  977.         }
  978.  
  979.         /*
  980.          * Compute the index into file2 of the corresponding record.
  981.          * Compute a pointer to value field of the next record in each
  982.          *    file.
  983.          *
  984.          * If either of the next records are anchor points,
  985.          *      continue the big loop.
  986.          */
  987.         if (!is_hash_code( record1[index1 + 1].value[file1_sub]))
  988.             continue;
  989.         if (!is_hash_code( record2[st_index2 + 1].value[file2_sub]))
  990.             continue;
  991.  
  992.         /*
  993.          * We have found the point where a group of inserted records
  994.          * begins in both files.
  995.          *
  996.          * Set up indexes to the first and last inserted records in
  997.          * the group.
  998.          */
  999.         st_index1 = fn_index1 = index1 + 1;
  1000.         st_index2 = st_index2 + 1;
  1001.         while (is_hash_code (record1[fn_index1].value[file1_sub])) {
  1002.             ++fn_index1;
  1003.         }
  1004.         fn_index2 = record1[fn_index1].value[file1_sub];
  1005.         fn_index1--;    /* Adjust to index to last inserted record */
  1006.         fn_index2--;    /* Adjust to index to last inserted record */
  1007.  
  1008.         /*
  1009.          * If this group of inserted records is adjacent to a group of
  1010.          * moved records, skip the comparison. This isn't the case
  1011.          * we're interested in.
  1012.          */
  1013.         index1 = fn_index1;
  1014.         if (st_index2 > fn_index2) {
  1015.             continue;
  1016.         }
  1017.  
  1018.         /*
  1019.          * Ensure that only non-unique records exist in the range
  1020.          * of the corresponding file. This catches a move in the
  1021.          * other direction.
  1022.          */
  1023.         for ( j=st_index2; j<=fn_index2; ++ j){
  1024.             if (!is_hash_code (record2[j].value[file2_sub]))
  1025.                 break;
  1026.         }
  1027.         if ( j <= fn_index2 )
  1028.             continue;
  1029.  
  1030.         /*
  1031.          * Compare the hash codes. If two records are identical,
  1032.          * consider them to be anchor points.
  1033.          */
  1034.         if ( p4_debug ) {
  1035.             printf("pass4: match_no: %d (%d-%d) (%d-%d)\n",
  1036.                 match_no, st_index1, fn_index1,
  1037.                      st_index2, fn_index2);
  1038.         }
  1039.  
  1040.         for (i = st_index1; i<=fn_index1; ++i) {
  1041.             for (j=st_index2; j<=fn_index2; ++j) {
  1042.  
  1043.                 if (record1[i].value[file1_sub] ==
  1044.                     record2[j].value[file2_sub]) {
  1045.  
  1046.                     link_records(match_no,i, j);
  1047.                     st_index2 = j + 1;
  1048.                     break;
  1049.  
  1050.                 }
  1051.  
  1052.             }
  1053.         }
  1054.     }
  1055.  
  1056. }
  1057. @//E*O*F pass4.c//
  1058. chmod u=rw,g=rw,o=rw pass4.c
  1059.  
  1060. echo x - pass5.c
  1061. sed 's/^@//' > "pass5.c" <<'@//E*O*F pass5.c//'
  1062. /*
  1063.  * The combine utility is a product of Harris, Inc. and is provided for
  1064.  * unrestricted use provided that this legend is included on all tape
  1065.  * media and as a part of the software program in whole or part.  Users
  1066.  * may copy, modify, license or distribute the combine utility without charge.
  1067.  * 
  1068.  * THE COMBINE UTILITY IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND
  1069.  * INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR A
  1070.  * PARTICULAR PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE
  1071.  * PRACTICE.
  1072.  * 
  1073.  * The combine utility is provided with no support and without any obligation
  1074.  * on the part of Harris, Inc. to assist in its use, correction,
  1075.  * modification or enhancement.
  1076.  * 
  1077.  * HARRIS, INC. SHALL HAVE NO LIABILITY WITH RESPECT TO THE
  1078.  * INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THE COMBINE
  1079.  * UTILITY OR ANY PART THEREOF.
  1080.  * 
  1081.  * In no event will Harris, Inc. be liable for any lost revenue
  1082.  * or profits or other special, indirect and consequential damages, even if
  1083.  * Harris has been advised of the possibility of such damages.
  1084.  * 
  1085.  * Harris Computer Systems Division
  1086.  * 2101 W Cypress Creek Rd
  1087.  * Fort Lauderdale, Florida 33309
  1088.  */
  1089. #include <stdio.h>
  1090. #include <ctype.h>
  1091. #include "util.h"
  1092. #include "combine.h"
  1093. /*
  1094.  * pass5: Output compared records
  1095.  *
  1096.  * The record arrays for the three files are traversed outputing the
  1097.  * resultant file. An index is maintained into each of the record arrays.
  1098.  * As each index is incremented the record is output. This routine merely
  1099.  * determines which file the next record is to come from.
  1100.  *
  1101.  * Return value:
  1102.  *      This procedure has no return value.
  1103.  */
  1104. void pass5 () {
  1105.  
  1106.     int     i;        /* Misc. variable */
  1107.  
  1108.     int     indexes[MAX_FILE_COUNT];
  1109.                 /* index into each of the record arrays */
  1110.  
  1111.     int     j;        /* Misc. variable */
  1112.  
  1113.     record_type * new_rec_ptr;/* Pointer to the current record */
  1114.  
  1115.     record_type * old_rec_ptr;/* Pointer to the record for the previously
  1116.                    current record */
  1117.  
  1118.     relate_type relate;    /* Relationships for the current record under
  1119.                    consideration */
  1120.  
  1121.  
  1122.     /*
  1123.      * Initialize the scan.
  1124.      *
  1125.      * Note: for files which don't exist, the value initialized below
  1126.      * needs to yield a TRUE result for the end of file comparison done
  1127.      * below.
  1128.      */
  1129.     for (i = 0; i < MAX_FILE_COUNT; ++i) {
  1130.         indexes[i] = BEGIN_INDEX + 1;/* skip the dummy begin record */
  1131.     }
  1132.  
  1133.     /*
  1134.      * For each line output.
  1135.      */
  1136.     for (;;) {
  1137.  
  1138.         /*
  1139.          * For each file,
  1140.          *    if the current record in the file is not involved in a
  1141.          *    move operation, then the record should be dumped
  1142.          *    immediately.
  1143.          *
  1144.          * This condition occurs for the following cirucumstances:
  1145.          *    The record exists in the current position in all
  1146.          *        three files.
  1147.          *    The record exists in the current position in this
  1148.          *        file and one of the other files. However,
  1149.          *        the record does not occur anywhere in the
  1150.          *        third file.
  1151.          *    The record exists in the current position in this
  1152.          *        file and does not occur anywhere in the other
  1153.          *        two files.
  1154.          */
  1155.         for (i = 0; i < file_count; ++i) {
  1156.  
  1157.             pass5_analyze_relationship (
  1158.                     i,/* file containing record */
  1159.                     indexes, /* current posit. in all files */
  1160.                     &relate); /* Returns file relationships */
  1161.  
  1162.             if (!relate.moved) {
  1163.  
  1164.                 if (indexes[OLD_FILE] >=
  1165.                     files[OLD_FILE].record_array_size - 1 &&
  1166.                     indexes[NEW1_FILE] >=
  1167.                     files[NEW1_FILE].record_array_size-1 &&
  1168.                     indexes[NEW2_FILE] >=
  1169.                     files[NEW2_FILE].record_array_size-1) {
  1170.  
  1171.                     relate.relation = INSERT_EOT;
  1172.                     pass5_dump_record (i, indexes, &relate);
  1173.                     return;
  1174.                 }
  1175.  
  1176.                 pass5_dump_record (i, indexes, &relate);
  1177.                 goto continue_big_loop;
  1178.             }
  1179.  
  1180.         }
  1181.  
  1182.         /*
  1183.          * All other cases involve a move of text from one location to
  1184.          * another.
  1185.          *
  1186.          * The 'pass5_move' routine analyses which text is the shortest text.
  1187.          */
  1188.  
  1189.         i = pass5_move (indexes);
  1190.  
  1191.         pass5_analyze_relationship (
  1192.                 i,      /* file containing record */
  1193.                 indexes,  /* current position in all files */
  1194.                 &relate); /* Returns file relationships */
  1195.  
  1196.         old_rec_ptr = &(files[i].record[indexes[i]]);
  1197.  
  1198.         for (;;) {
  1199.  
  1200.             pass5_dump_record (i, indexes, &relate);
  1201.  
  1202.             /*
  1203.              * If any of the files involved in the move have now
  1204.              *    reached EOT,
  1205.              *     go on to process bigger and better things.
  1206.              */
  1207.             for (j = 0; j < file_count; ++j) {
  1208.                 if (!is_hash_code (relate.index[j])) {
  1209.                     relate.index[j]++;
  1210.                     if (relate.index[j] + 1 >=
  1211.                         files[j].record_array_size) {
  1212.                         goto continue_big_loop;
  1213.                     }
  1214.                 }
  1215.             }
  1216.  
  1217.             /*
  1218.              * Note: this code should continue to dump records
  1219.              * without re-iterating the pass5_move routine.
  1220.              * Since the pass5_move routine executes in a loop,
  1221.              * the above_mentioned enhancement is required to ensure
  1222.              * that pass5 completes in linear time.
  1223.              *
  1224.              * The test below determines if the current record
  1225.              * is logically next to the previous record.
  1226.              * If so, the record is merely dumped.
  1227.              * Note: the record relationship does not change
  1228.              * for this record.
  1229.              *
  1230.              * A record is logically next to a previous one
  1231.              * if either the value field is a hash code for
  1232.              * both records or if the record index in the
  1233.              * value field is one greater then that of the
  1234.              * previous record.
  1235.              */
  1236.  
  1237.             new_rec_ptr = &(files[i].record[indexes[i]]);
  1238.  
  1239.             for (j = 0; j < MAX_VALUE_SUB; ++j) {
  1240.                 if (is_hash_code (old_rec_ptr -> value[j])) {
  1241.                     if(is_hash_code(new_rec_ptr->value[j])){
  1242.                         continue;
  1243.                     }
  1244.                 } else if (old_rec_ptr->value[j]+1 ==
  1245.                        new_rec_ptr -> value[j]) {
  1246.                     continue;
  1247.                 }
  1248.                 goto continue_big_loop;
  1249.             }
  1250.  
  1251.             old_rec_ptr = new_rec_ptr;
  1252.  
  1253.         }
  1254.  
  1255. continue_big_loop: ;
  1256.     }
  1257.  
  1258. }
  1259. /*
  1260.  * pass5_analyze_relationship -- determine relationsip to other files
  1261.  *
  1262.  * This routine determines the relationship between one record in one file
  1263.  * and the records at the current position in the other files.
  1264.  * The routine returns information regarding whether the record exists
  1265.  * in each file at the current position and whether the record is involved
  1266.  * in a move operation.
  1267.  *
  1268.  * Return value:
  1269.  *      This procedure returns no value.
  1270.  */
  1271. void pass5_analyze_relationship (file_no, indexes, rel_ptr)
  1272. int     file_no;        /* input -- file number of the file
  1273.                  containing the record to be compared. */
  1274.  
  1275. int     indexes[MAX_FILE_COUNT];/* input -- Array of the current
  1276.                    indexes into the record arrays */
  1277.  
  1278. relate_type * rel_ptr;        /* output -- Returns relationship between
  1279.                    current record and records at the current
  1280.                    position in the corresponding files. */
  1281.  
  1282. {
  1283.  
  1284.     int     i;        /* Misc. variable */
  1285.  
  1286.     int     power;        /* Current power of 2 */
  1287.  
  1288.     record_type * record_ptr;/* Pointer to the record block is the record
  1289.                    currently being analyzed. */
  1290.  
  1291.  
  1292.  
  1293.     /*
  1294.      * Initialize the value_index array to contain the index of the current
  1295.      * record in each of the files.
  1296.      *
  1297.      * The record is at the current position in the current file. The record
  1298.      * is in the position indicated by the 'value' field in the record entry
  1299.      * for the other files.
  1300.      */
  1301.     record_ptr = &(files[file_no].record[indexes[file_no]]);
  1302.  
  1303.     rel_ptr -> index[file_no] = indexes[file_no];
  1304.     rel_ptr -> index[corres_file[file_no * 2]] =
  1305.         record_ptr -> value[value_sub[file_no * 2]];
  1306.     rel_ptr -> index[corres_file[file_no * 2 + 1]] =
  1307.         record_ptr -> value[value_sub[file_no * 2 + 1]];
  1308.  
  1309.     /*
  1310.      * Compare the current position in each file with the index of
  1311.      * this record in each file.
  1312.      */
  1313.     rel_ptr -> moved = FALSE;
  1314.     rel_ptr -> in_all = TRUE;
  1315.     rel_ptr -> relation = 0;
  1316.  
  1317.     power = 1;
  1318.  
  1319.     for (i = 0; i < file_count; ++i) {
  1320.  
  1321.         rel_ptr -> current[i] = (rel_ptr -> index[i] == indexes[i]);
  1322.  
  1323.         if (rel_ptr -> current[i]) {
  1324.             rel_ptr -> relation += power;
  1325.  
  1326.         } else {
  1327.             rel_ptr -> in_all = FALSE;
  1328.             if (!is_hash_code (rel_ptr -> index[i])) {
  1329.                 rel_ptr -> moved = TRUE;
  1330.             }
  1331.         }
  1332.  
  1333.         power *= 2;
  1334.  
  1335.     }
  1336.  
  1337. }
  1338. /*
  1339.  * pass5_dump_record: write a record for pass 5
  1340.  *
  1341.  * This routine writes the specified record to the output files and
  1342.  * increments the appropriate indexes.
  1343.  *
  1344.  * Return value:
  1345.  *      This routine returns no value.
  1346.  */
  1347. void pass5_dump_record (file_no, indexes, rel_ptr)
  1348. int     file_no;        /* input -- File number of the file to
  1349.                    read record from. */
  1350.  
  1351. int     indexes[MAX_FILE_COUNT];/* input/output -- Indexes of the current
  1352.                    records. Each index is incremented as
  1353.                    appropriate */
  1354.  
  1355. relate_type * rel_ptr;        /* input -- Relationships
  1356.                    of this record to other files. */
  1357.  
  1358. {
  1359.  
  1360.     cache_entry_type * cache_ptr;/* Current cache entry pointer */
  1361.  
  1362.     file_type * file_ptr;    /* Pointer to the current file */
  1363.  
  1364.     int     i;        /* Misc. variable */
  1365.  
  1366.     /*
  1367.      * Consider the case that the comparison was done with the -B
  1368.      * option. In that case, records reported to be identical here
  1369.      * may actually only be similar. The loop below computes the
  1370.      * largest file_no which has a record "identical" to the
  1371.      * current one. The theory is that the largest file_no contains
  1372.      * the "newest" record (and by deduction, the "best" record).
  1373.      */
  1374.     for (i = file_no+1; i < file_count; ++i) {
  1375.         if (rel_ptr -> current[i]) {
  1376.             if ( p5_debug ) {
  1377.                 printf ( "debug: oldfile:%d newfile: %d\n",
  1378.                     file_no, i );
  1379.             }
  1380.             file_no = i;
  1381.         }
  1382.     }
  1383.  
  1384.     /*
  1385.      * If this is the end of the world,
  1386.      *     Pass the word on.
  1387.      */
  1388.     if (rel_ptr -> relation == INSERT_EOT) {
  1389.         if (hed_flag) {
  1390.             pass5_write_hed (rel_ptr, (cache_entry_type *) 0);
  1391.         } else {
  1392.             pass5_write_listing(indexes, rel_ptr,
  1393.                 (cache_entry_type *) 0);
  1394.         }
  1395.         return;
  1396.     }
  1397.  
  1398.     /*
  1399.      * Initialize local variables.
  1400.      *
  1401.      * The cache of records is maintained as a queue of the previously seen
  1402.      * records. This queue is used by the 'write' routines.
  1403.      */
  1404.  
  1405.     file_ptr = &files[file_no];
  1406.     deq_tail_dll (cache_head_ptr, cache_tail_ptr, cache_ptr,
  1407.             cache_next_ptr, cache_prev_ptr);
  1408.     enq_head_dll (cache_head_ptr, cache_tail_ptr, cache_ptr,
  1409.             cache_next_ptr, cache_prev_ptr);
  1410.  
  1411.     /*
  1412.      * Write record to output files.
  1413.      */
  1414.     if (p5_debug) {
  1415.         printf ( "debug: file:%d indexes:%5d %5d %5d current: %d %d %d move: %d\n",
  1416.                 file_no, indexes[0], indexes[1], indexes[2],
  1417.                 rel_ptr -> current[0], rel_ptr -> current[1], rel_ptr -> current[2],
  1418.                 rel_ptr -> moved);
  1419.     }
  1420.     if (hed_flag) {
  1421.         /* if hed_flag, always read record into cache */
  1422.         reread_into_cache( file_ptr, indexes[file_no], cache_ptr );
  1423.         pass5_write_hed (rel_ptr, cache_ptr);
  1424.     } else {
  1425.         /* for normal output, wait to read into cache until we
  1426.            know for sure it is going to be needed. Most
  1427.            records are merely skipped and not output at all. */
  1428.         pass5_write_listing (indexes, rel_ptr, cache_ptr);
  1429.     }
  1430.  
  1431.     /*
  1432.      * Increment the count of differences.
  1433.      */
  1434.     switch (rel_ptr -> relation) {
  1435.     case INSERT_OLD:
  1436.     case INSERT_NEW1_NEW2:
  1437.         old_new1_change_count++;
  1438.         old_new2_change_count++;
  1439.         break;
  1440.     case INSERT_NEW1:
  1441.     case INSERT_OLD_NEW2:
  1442.         old_new1_change_count++;
  1443.         new1_new2_change_count++;
  1444.         break;
  1445.     case INSERT_NEW2:
  1446.     case INSERT_OLD_NEW1:
  1447.         old_new2_change_count++;
  1448.         new1_new2_change_count++;
  1449.         break;
  1450.     case INSERT_OLD_NEW1_NEW2:
  1451.         break;
  1452.     default:
  1453.         error ("pass5_dump_record: invalid relation");
  1454.     }
  1455.  
  1456.     /*
  1457.      * Increment the record indexes.
  1458.      */
  1459.     for (i = 0; i < file_count; ++i) {
  1460.         if (rel_ptr -> current[i]) {
  1461.             indexes[i]++;
  1462.         }
  1463.     }
  1464. }
  1465. /*
  1466.  * pass5_move: Analyse which text moved.
  1467.  *
  1468.  * This routine is called when a group of moved lines is detected.
  1469.  * A group of moved lines exists when (for the current position in
  1470.  * the file) the next line occurs in all three files but at different
  1471.  * relative positions. This routine scans forward in the each of the
  1472.  * 3 files trying to determine the shortest group of lines.
  1473.  *
  1474.  * In determining the shortest group of lines, inserted and deleted records
  1475.  * are not considered. Rather, the scan continues until a line which is
  1476.  * before the current line is found.
  1477.  *
  1478.  * Return value:
  1479.  *      This procedure return the file number of the file to be traversed
  1480.  *      to indicate the shortest common sequence of lines.
  1481.  */
  1482. int     pass5_move (indexes)
  1483. int    *indexes;        /* Array of pointers to the current indexes
  1484.                    into the record arrays */
  1485.  
  1486. {
  1487.  
  1488.     int     corres_file_recno;
  1489.                 /* Record number in the corresponding file */
  1490.  
  1491.     int     depth;        /* Number of lines tested */
  1492.  
  1493.     int     i;        /* Misc. variable */
  1494.  
  1495.     record_type * record;    /* Pointer to record array for the current
  1496.                    file. */
  1497.  
  1498.     /*
  1499.      * For each record, six different comparison need to be made. That is,
  1500.      * for each of the three files there is a relationship to each of the
  1501.      * other two files. A comparison needs to be made for each of those
  1502.      * relationships. The tables below describe the six relationships.
  1503.      */
  1504.  
  1505.     int     index[MATCH_COUNT];/* Current index into the record array of
  1506.                    'curr_file' */
  1507.  
  1508.     int     prev_value[MATCH_COUNT];
  1509.                 /* Previous contents of the 'value' field for
  1510.                    the record */
  1511.  
  1512.     bool bypass[MATCH_COUNT];/* TRUE if file should not by considered for
  1513.                    processing */
  1514.  
  1515.  
  1516.     /*
  1517.      * Initialize the index array and the prev_value array from the values
  1518.      * passed in.
  1519.      *
  1520.      * During this initialization, all entries which contain hash codes
  1521.      * are skipped over. All such entries represent a line which exists in
  1522.      * only two of the files.
  1523.      */
  1524.  
  1525.     for (i = 0; i < MATCH_COUNT; ++i) {
  1526.  
  1527.         bypass[i] = (files[curr_file[i]].record == 0) ||
  1528.             (files[corres_file[i]].record == 0) ||
  1529.             (indexes[curr_file[i]] + 1 >=
  1530.                 files[curr_file[i]].record_array_size);
  1531.  
  1532.         if (!bypass[i]) {
  1533.             record = files[curr_file[i]].record;
  1534.             index[i] = indexes[curr_file[i]];
  1535.             while(is_hash_code(
  1536.                 record[index[i]].value[value_sub[i]])) {
  1537.  
  1538.                 index[i]++;
  1539.             }
  1540.             prev_value[i] = record[index[i]].value[value_sub[i]];
  1541.         }
  1542.  
  1543.     }
  1544.  
  1545.     /*
  1546.      * Indentify the shortest common sequence of lines.
  1547.      *
  1548.      * For each iteration of this loop the index into the record array for
  1549.      * each of the six cases is incremented by one. The record detected at the
  1550.      * new index is compared against the previous record for the same case.
  1551.      *
  1552.      * In the documentation below, the 'current' file is the one which
  1553.      * has a relationship and the 'corresponding' file is the one related to.
  1554.      */
  1555.     for (depth = 0;; depth++) {
  1556.         for (i = 0; i < MATCH_COUNT; ++i) {
  1557.  
  1558.             /*
  1559.              * If this files has no records or no records left
  1560.              *    to dump,
  1561.              *     ignore the file.
  1562.              *
  1563.              * This happens in the case of a two file comparision.
  1564.              * or in the case of one file completely output.
  1565.              */
  1566.             if (bypass[i]) {
  1567.                 continue;
  1568.             }
  1569.  
  1570.             /*
  1571.              * If we have reached the end of the 'current' file,
  1572.              *    If this line is also the end of the
  1573.              *        'corresponding' file,
  1574.              *       If the 'corresponding' file is at EOF already,
  1575.              *           the 'current' file contains the
  1576.              *        shortest sequence
  1577.              *       else
  1578.              *           the 'corresponding' file contains the
  1579.              *        shortest sequence
  1580.              *    else
  1581.              *        the 'current' file contains the shortest
  1582.              *        common sequence.
  1583.              */
  1584.             if(index[i]+1 >= files[curr_file[i]].record_array_size){
  1585.                 if (prev_value[i] + 1 >=
  1586.                     files[corres_file[i]].record_array_size) {
  1587.  
  1588.                     if (indexes[corres_file[i]] + 1 >=
  1589.                         files[corres_file[i]].
  1590.                         record_array_size) {
  1591.  
  1592.                         return (curr_file[i]);
  1593.                     } else {
  1594.                         return (corres_file[i]);
  1595.                     }
  1596.                 } else {
  1597.                     return (curr_file[i]);
  1598.                 }
  1599.             }
  1600.  
  1601.             /*
  1602.              * For each record in the 'current' file which doesn't
  1603.              *     have a record in the 'corresponding' file,
  1604.              *     skip past the record.
  1605.              *
  1606.              * Since what we are trying to find is the shortest
  1607.              * group of records in the 'corresponding' file,
  1608.              * the search should not be penalized by
  1609.              * inserted records in the 'current' file.
  1610.              */
  1611.             record = files[curr_file[i]].record;
  1612.             index[i]++;
  1613.             while (is_hash_code(record[index[i]].
  1614.                 value[value_sub[i]])) {
  1615.  
  1616.                 index[i]++;
  1617.             }
  1618.  
  1619.             /*
  1620.              * If the record number in the corresponding file
  1621.              * is one of the records being considered as
  1622.              * moved by the 'corresponding' file, the 'current'
  1623.              * file contains the shortest common sequence.
  1624.              *
  1625.              * Note: this routine is only invoked if all files
  1626.              * are currently involved in a move.
  1627.              *
  1628.              * By outputting lines from the 'current' file,
  1629.              * we will soon get to the current point in the
  1630.              * 'corresponding' file. At that point, the
  1631.              * current line in the 'corresponding' file will
  1632.              * no longer be diagnosed as having moved.
  1633.              */
  1634.             corres_file_recno = record[index[i]].
  1635.                 value[value_sub[i]];
  1636.  
  1637.             if (corres_file_recno >= indexes[corres_file[i]] &&
  1638.                 corres_file_recno <=
  1639.                 indexes[corres_file[i]] + depth) {
  1640.                 if (p5_debug)
  1641.                     printf("move optimization found\n");
  1642.  
  1643.                 return (curr_file[i]);
  1644.             }
  1645.         }
  1646.         /*
  1647.          * The above loop and this loop were split in order to give the
  1648.          * above loop every opportunity to find a move optimization.
  1649.          */
  1650.         for (i = 0; i < MATCH_COUNT; ++i) {
  1651.             if (bypass[i])
  1652.                 continue;
  1653.             record = files[curr_file[i]].record;
  1654.             corres_file_recno = record[index[i]].
  1655.                 value[value_sub[i]];
  1656.  
  1657.             /*
  1658.              * If the record numbers in the 'corresponding' file are
  1659.              *  still going in the forward direction,
  1660.              *  then we haven't completed the search.
  1661.              *
  1662.              * Record numbers need not be immediately next to
  1663.              * one another (e.g. record number 5 and record
  1664.              * number 6). Record numbers merely need to
  1665.              * following one another. This ensures that the common
  1666.              * sequence check isn't interrupted by deletions in the
  1667.              * 'corresponding' file.
  1668.              *
  1669.              * The above comment is hereby rescinded. Cliff 1/23/85
  1670.              */
  1671.             if (prev_value[i] + 1 == corres_file_recno) {
  1672.                 prev_value[i] = corres_file_recno;
  1673.             } else {
  1674.                 if (p5_debug)
  1675.                     printf("short move found %d\n", depth);
  1676.                 return (curr_file[i]);
  1677.             }
  1678.         }
  1679.     }
  1680.  
  1681. }
  1682.  
  1683. /*
  1684.  * pass5_write_hed: write a record to 'hed' file.
  1685.  *
  1686.  * This routine writes the specified record to the 'hed' output file.
  1687.  *
  1688.  * Return value:
  1689.  *      This routine returns no value.
  1690.  */
  1691. void pass5_write_hed (rel_ptr, cache_ptr)
  1692. relate_type * rel_ptr;        /* input */
  1693.              /* Relationships of this record to other files. */
  1694.  
  1695. cache_entry_type * cache_ptr;    /* input */
  1696.              /* Cache entry describing buffer */
  1697.  
  1698. {
  1699.  
  1700.     bool flag;        /* TRUE if NEW1 and OLD file not same */
  1701.  
  1702.     int     i;        /* Misc. variable */
  1703.  
  1704. #define HED_END_RECORD "~End of changes"
  1705.  
  1706.     static int      prev_relation = INSERT_NONE;
  1707.                 /* Relationship of previous call */
  1708.  
  1709.     static  bool prev_in_all = TRUE;
  1710.             /* TRUE if previous record was in all of the files */
  1711.  
  1712.  
  1713.     /*
  1714.      * Handle EOT case.
  1715.      */
  1716.     if (rel_ptr -> relation == INSERT_EOT) {
  1717.         if (!prev_in_all) {
  1718.             puts (HED_END_RECORD);
  1719.         }
  1720.         return;
  1721.     }
  1722.  
  1723.     /*
  1724.      * Write any header of trailing records to 'hed' file.
  1725.      */
  1726.  
  1727.     if (rel_ptr -> relation != prev_relation) {
  1728.         if (!prev_in_all) {
  1729.             puts (HED_END_RECORD);
  1730.         }
  1731.  
  1732.  
  1733.         if (!rel_ptr -> in_all) {
  1734.             (void) fputs ("~~", stdout);
  1735.  
  1736.             if (rel_ptr -> current[OLD_FILE]) {
  1737.                 (void) fputs ("Delete ", stdout);
  1738.             } else {
  1739.                 (void) fputs ("Insert ", stdout);
  1740.             }
  1741.  
  1742.             flag = FALSE;
  1743.  
  1744.             for (i = NEW1_FILE; i < file_count; ++i) {
  1745.  
  1746.                 if (rel_ptr -> current[OLD_FILE] !=
  1747.                         rel_ptr -> current[i]) {
  1748.  
  1749.                     if (flag) {
  1750.                         (void) fputs (" and ", stdout);
  1751.                     }
  1752.  
  1753.                     (void) fputs("'", stdout);
  1754.                     (void) fputs(files[i].text_ptr?
  1755.                              files[i].text_ptr:
  1756.                              files[i].name_ptr,
  1757.                              stdout);
  1758.                     (void) fputs("'", stdout);
  1759.                     flag = TRUE;
  1760.  
  1761.                     if (!is_hash_code(rel_ptr->index[i]) &&
  1762.                         !is_hash_code(
  1763.                         rel_ptr->index[OLD_FILE])) {
  1764.  
  1765.                         (void) fputs(" (MOVED)",stdout);
  1766.                     }
  1767.  
  1768.                 }
  1769.  
  1770.             }
  1771.  
  1772.             (void) putchar ('\n');
  1773.  
  1774.         }
  1775.  
  1776.         prev_relation = rel_ptr -> relation;
  1777.         prev_in_all = rel_ptr -> in_all;
  1778.     }
  1779.  
  1780.     /*
  1781.      * Write record to 'hed' file.
  1782.      */
  1783.     cache_ptr -> recordp[cache_ptr -> record_length] = '\0';
  1784.     (void) puts (cache_ptr -> recordp);
  1785.  
  1786. }
  1787. /*
  1788.  * pass5_write_listing: write a record to 'listing' file.
  1789.  *
  1790.  * This routine writes a summary of the changes to the standard output.
  1791.  *
  1792.  * This routine writes all changed lines to standard output. It also
  1793.  * writes a few (-prefix and -postifx options) unchanged lines immediately
  1794.  * preceeding and following the changed lines. This routine assumes that
  1795.  * the caller, 'pass5_dump_record', is maintaining a queue of all records
  1796.  * read in the cache. The current record should be at the head of the
  1797.  * cache. The previous record should immediately follow that, etc.
  1798.  *
  1799.  * Return value:
  1800.  *      This routine returns no value.
  1801.  */
  1802.  
  1803. void pass5_write_listing (indexes, rel_ptr, cache_ptr)
  1804. int     indexes[MAX_FILE_COUNT];/* input */
  1805.                  /* Indexes of the current records. */
  1806.  
  1807. relate_type * rel_ptr;        /* input */
  1808.                  /* Relationships of this record to other files. */
  1809.  
  1810. cache_entry_type * cache_ptr;    /* input */
  1811.                  /* Cache entry describing buffer */
  1812.  
  1813. {
  1814.  
  1815.     static  relate_type all_rel;
  1816.                 /* relation used for outputting prefix lines.*/
  1817.  
  1818.     int     i;        /* Misc. variable */
  1819.  
  1820.     static int      postfix_count = 0;
  1821.                 /* Number of postfix lines remaining to output*/
  1822.  
  1823.     cache_entry_type * prefix_cache_ptr;
  1824.                 /* Pointer to cache entry containing the
  1825.                    current prefix line */
  1826.  
  1827.     int     prefix_count;    /* Number of prefix lines to output */
  1828.  
  1829.     static int      prev_relation = INSERT_NONE;
  1830.                 /* Relationship of previous call */
  1831.  
  1832.     static  bool prev_in_all = TRUE;
  1833.                 /* TRUE if previous line was in all files at
  1834.                    the current position */
  1835.  
  1836.     static int      same_count = 0;
  1837.                 /* Number of indentical lines scanned so far
  1838.                    which might later be output as prefix lines.
  1839.                    */
  1840.  
  1841.  
  1842.  
  1843.     /*
  1844.      * Handle EOT case.
  1845.      */
  1846.     if (rel_ptr -> relation == INSERT_EOT) {
  1847.         if (!quiet_option) {
  1848.             if (old_new1_change_count == 0 &&
  1849.                 (file_count == 2 ||
  1850.                     (old_new2_change_count == 0 &&
  1851.                         new1_new2_change_count == 0))) {
  1852.  
  1853.                 (void) strcpy (cache_tail_ptr -> recordp, "Files are identical");
  1854.                 cache_tail_ptr -> record_length = strlen (cache_tail_ptr -> recordp);
  1855.                 pass5_write_listing_line ((relate_type *) 0, cache_tail_ptr);
  1856.             } else {
  1857.                 cache_tail_ptr -> record_length = 0;
  1858.                 pass5_write_listing_line((relate_type *) 0,
  1859.                     cache_tail_ptr);
  1860.                 (void) strcpy(cache_tail_ptr->recordp,
  1861.                     "[ Comparison Complete ]");
  1862.                 cache_tail_ptr->record_length =
  1863.                     strlen(cache_tail_ptr -> recordp);
  1864.                 pass5_write_listing_line((relate_type *) 0,
  1865.                     cache_tail_ptr);
  1866.             }
  1867.             (void) putchar('\f');
  1868.         }
  1869.         return;
  1870.     }
  1871.  
  1872.     /*
  1873.      * Write any prefix lines which need to be written.
  1874.      */
  1875.     if (rel_ptr -> relation != prev_relation && prev_in_all) {
  1876.  
  1877.         prefix_count = min (prefix_lines, same_count);
  1878.  
  1879.         if (same_count > prefix_count) {
  1880.             /* Output seperator line */
  1881.             pass5_write_listing_line ((relate_type *) 0,
  1882.                 (cache_entry_type *) 0);
  1883.         }
  1884.  
  1885.         prefix_cache_ptr = cache_ptr;
  1886.         for (i = 0; i < prefix_count; ++i) {
  1887.             prefix_cache_ptr = prefix_cache_ptr -> cache_next_ptr;
  1888.         }
  1889.  
  1890.         all_rel.relation = INSERT_OLD_NEW1_NEW2;
  1891.         all_rel.moved = FALSE;
  1892.         all_rel.in_all = TRUE;
  1893.  
  1894.         while (prefix_count > 0) {
  1895.  
  1896.             for (i = 0; i < file_count; ++i) {
  1897.                 all_rel.index[i] = indexes[i] - prefix_count;
  1898.                 all_rel.current[i] = TRUE;
  1899.             }
  1900.  
  1901.             pass5_write_listing_line (
  1902.                 &all_rel, /* Indicate all lines are related */
  1903.                 prefix_cache_ptr); /* Pointer to record in cache */
  1904.  
  1905.             prefix_count--;
  1906.             prefix_cache_ptr = prefix_cache_ptr -> cache_prev_ptr;
  1907.  
  1908.         }
  1909.  
  1910.     }
  1911.  
  1912.     /*
  1913.      * If this is the first identical line,
  1914.      *     indicate how many postifx lines need to be output.
  1915.      */
  1916.     if (rel_ptr -> relation != prev_relation && rel_ptr -> in_all &&
  1917.             prev_relation != INSERT_NONE) {
  1918.         postfix_count = postfix_lines;
  1919.     }
  1920.  
  1921.     prev_relation = rel_ptr -> relation;
  1922.     prev_in_all = rel_ptr -> in_all;
  1923.  
  1924.     /*
  1925.      * If this line is a changed line or a postfix line,
  1926.      *     dump it.
  1927.      */
  1928.     if (!rel_ptr -> in_all || postfix_count > 0) {
  1929.         pass5_write_listing_line (
  1930.                 rel_ptr,/* Line relationships */
  1931.                 cache_ptr);/* Pointer to record in cache */
  1932.     }
  1933.  
  1934.     /*
  1935.      * Count the number of identical lines
  1936.      * and keep track of the number of postfix lines printed.
  1937.      */
  1938.     if (rel_ptr -> in_all) {
  1939.         if (postfix_count <= 0) {
  1940.             same_count++;
  1941.         }
  1942.         postfix_count--;
  1943.     } else {
  1944.         same_count = 0;
  1945.     }
  1946.  
  1947. }
  1948. /*
  1949.  * pass5_write_listing_line: write a record to 'listing' file.
  1950.  *
  1951.  * This routine writes a single line to the 'listing' file. The line has
  1952.  * already been checked to ensure that the line is to be output.
  1953.  *
  1954.  * Return value:
  1955.  *      This routine returns no value.
  1956.  */
  1957.  
  1958. void pass5_write_listing_line (rel_ptr, cache_ptr)
  1959. relate_type * rel_ptr;    /* input -- Relationships of this record to
  1960.                 other files. If this pointer is 0, write the line
  1961.                pointed to by cache_entry_type with
  1962.                no special formatting */
  1963.  
  1964. cache_entry_type * cache_ptr;    /* input -- Cache entry describing buffer
  1965.                    If this pointer is 0, write a
  1966.                    seperator line between changes */
  1967.  
  1968. {
  1969.  
  1970.     int     i;        /* Misc. variable */
  1971.  
  1972.     static int      line_count = 0;/* Number of lines left on a page */
  1973.  
  1974.     static int      page_count = 0;/* Number of pages output so far */
  1975.  
  1976.  
  1977.  
  1978.     /*
  1979.      * Output the header lines, if required.
  1980.      *
  1981.      * Don't output seperator record too close to bottom of a page.
  1982.      */
  1983.     --line_count;
  1984.     if (line_count <= 0 ||
  1985.             (line_count <= 10 && cache_ptr == 0)) {
  1986.  
  1987.         line_count = 50;
  1988.         if (page_count)
  1989.             (void) putchar('\f');
  1990.         page_count++;
  1991.  
  1992.         printf ("Time of comparison: %s                          Page %d\n\n",
  1993.                 exec_time, page_count);
  1994.  
  1995.         if (file_count == 2) {
  1996.             pass5_write_listing_head("Old ", OLD_FILE);
  1997.             pass5_write_listing_head("New ", NEW1_FILE);
  1998.             (void) putchar ('\n');
  1999.             puts ("Status  Old   New                   Contents");
  2000.             puts ("------  ---   ---                   --------");
  2001.         } else {
  2002.             pass5_write_listing_head("Old ", OLD_FILE);
  2003.             pass5_write_listing_head("New1", NEW1_FILE);
  2004.             pass5_write_listing_head("New2", NEW2_FILE);
  2005.             (void) putchar ('\n');
  2006.             puts ("Status  Old   New1  New2                  Contents");
  2007.             puts ("------  ---   ----  ----                  --------");
  2008.         }
  2009.  
  2010.         puts ("\n");
  2011.  
  2012.         if (cache_ptr == 0) {
  2013.             return;    /* Don't put seperator record at top of page */
  2014.         }
  2015.  
  2016.     }
  2017.  
  2018.     /*
  2019.      * If rel_ptr exists,
  2020.      * Output the Line status and file line numbers:
  2021.      */
  2022.     if (rel_ptr != 0) {
  2023.         if (!rel_ptr -> in_all) {
  2024.  
  2025.             if (rel_ptr -> current[OLD_FILE]) {
  2026.                 if (rel_ptr -> moved) {
  2027.                     fputs ("MOV[O]", stdout);
  2028.                 } else {
  2029.                     fputs ("Delete", stdout);
  2030.                 }
  2031.             } else {
  2032.                 if (rel_ptr -> moved) {
  2033.                     fputs ("MOV[N]", stdout);
  2034.                 } else {
  2035.                     fputs ("Insert", stdout);
  2036.                 }
  2037.             }
  2038.  
  2039.         } else {
  2040.  
  2041.             fputs ("      ", stdout);
  2042.  
  2043.         }
  2044.  
  2045.         cache_ptr->record_length = -1;
  2046.         for (i = 0; i < file_count; ++i) {
  2047.             if (is_hash_code (rel_ptr -> index[i])) {
  2048.                 fputs ("       ", stdout);
  2049.             } else {
  2050.                 if (cache_ptr->record_length == -1) {
  2051.                     reread_into_cache( &files[i],
  2052.                         rel_ptr->index[i],
  2053.                         cache_ptr );
  2054.                 }
  2055.                 printf ("%6d ", rel_ptr -> index[i]);
  2056.             }
  2057.         }
  2058.  
  2059.     } else if (cache_ptr == 0) {
  2060.  
  2061.         puts ("******");
  2062.         return;
  2063.  
  2064.     }
  2065.  
  2066.     /*
  2067.      * Finally, write the line.
  2068.      */
  2069.     if (cache_ptr -> record_length == -1) {
  2070.         puts (" < EOF.. >");
  2071.     } else {
  2072.         cache_ptr -> recordp[cache_ptr -> record_length] = '\0';
  2073.         puts (cache_ptr -> recordp);
  2074.     }
  2075.  
  2076. }
  2077. /*
  2078.  * pass5_write_listing_head: write a header line to 'listing' file.
  2079.  *
  2080.  * This routine writes a single header line to the 'listing' file.
  2081.  *
  2082.  * Return value:
  2083.  *      This routine returns no value.
  2084.  */
  2085. void pass5_write_listing_head (name_ptr, file_no)
  2086. char * name_ptr;        /* input -- name of header */
  2087.  
  2088. int     file_no;        /* input -- file number of the file
  2089.                  containing the record to be compared. */
  2090.  
  2091. {
  2092.     printf ("%s area: '%s'   Last Written: %s",
  2093.         name_ptr,
  2094.         files[file_no].name_ptr,
  2095.         files[file_no].lw_ptr);
  2096.  
  2097.     if ( files[file_no].text_ptr ) {
  2098.         printf ("   Text: '%s'", files[file_no].text_ptr );
  2099.     }
  2100.     (void) putchar ('\n');
  2101. }
  2102. @//E*O*F pass5.c//
  2103. chmod u=rw,g=rw,o=rw pass5.c
  2104.  
  2105. exit 0
  2106.  
  2107.