Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/misc/volume13/combine/part01

Text File | 1990-06-15 | 48.3 KB | 1,392 lines

Newsgroups: comp.sources.misc
subject: v13i054: combine: 3 file compare/merge utility (part 1of3)
from: [e-mail] (Cliff Van Dyke)
Sender: [e-mail] (Brandon S. Allbery - comp.sources.misc)

Posting-number: Volume 13, Issue 54
Submitted-by: [e-mail] (Cliff Van Dyke)
Archive-name: combine/part01

Please acknowledge receipt of this submission.

The combine utility is a general purpose utility to compare 2 or 3 ASCII files.
The output of the utility is either a report describing the differences
between the files or a file which is the composite of the original files.
The output report format of this utility is friendlier than the Unix diff
utility. The composite output file feature of this utility is unique in
its presentation of file differences.

The combine utility uses a fundamental comparison algorithm as described
in "A technique for Isolating differences between files";
Communications of the ACM; April 1978; Volume 21 Number 4.

The combine utility is being contributed to the public domain. The disclaimer
at the begining of each file is required by my employer (Harris Computer
Systems Division) to ensure that Harris is not liable in the event
of errors in the software.

The combine utility has been in use at HCSD for 5 years. It runs on
Harris HCX and GCX architectures (CX/UX 4.1) and a SUN 3/160
(SUNOS version 4.0),
--
Cliff Van Dyke                   [e-mail]
Harris Computer Systems          ...!{uunet,novavax}!hcx1!cliff
2101 W. Cypress Creek Rd.
Ft. Lauderdale, FL 33309-1892    Tel: [phone]
# This is a shell archive.  Remove anything before this line,
# then unpack it by saving it in a file and typing "sh file".
#
# Wrapped by cliff on Tue Feb 13 14:26:20 EST 1990
# Contents:  README combine.1 design_spec combine.h Makefile

echo x - README
sed 's/^@//' > "README" <<'@//E*O*F README//'
The combine utility is a general purpose utility to compare 2 or 3 ASCII files.
The output of the utility is either a report describing the differences
between the files or a file which is the composite of the original files.
The output report format of this utility is friendlier than the Unix diff
utility. The composite output file feature of this utility is unique in
its presentation of file differences.

The combine utility uses a fundamental comparison algorithm as described
in "A technique for Isolating differences between files";
Communications of the ACM; April 1978; Volume 21 Number 4.

The combine utility is being contributed to the public domain. The disclaimer
at the begining of each file is required by my employer (Harris Computer
Systems Division) to ensure that Harris is not liable in the event
of errors in the software.

The combine utility has been in use at HCSD for 5 years. It runs on
Harris HCX and GCX architectures (CX/UX 4.1) and a SUN 3/160
(SUNOS version 4.0),
--
Cliff Van Dyke                   [e-mail]
Harris Computer Systems          ...!{uunet,novavax}!hcx1!cliff
2101 W. Cypress Creek Rd.
Ft. Lauderdale, FL 33309-1892    Tel: [phone]
@//E*O*F README//
chmod u=rw,g=r,o=r README

echo x - combine.1
sed 's/^@//' > "combine.1" <<'@//E*O*F combine.1//'
'\"
'\" The combine utility is a product of Harris, Inc. and is provided for
'\" unrestricted use provided that this legend is included on all tape
'\" media and as a part of the software program in whole or part.  Users
'\" may copy, modify, license or distribute the combine utility without charge.
'\"
'\" THE COMBINE UTILITY IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND
'\" INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR A
'\" PARTICULAR PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE
'\" PRACTICE.
'\"
'\" The combine utility is provided with no support and without any obligation
'\" on the part of Harris, Inc. to assist in its use, correction,
'\" modification or enhancement.
'\"
'\" HARRIS, INC. SHALL HAVE NO LIABILITY WITH RESPECT TO THE
'\" INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THE COMBINE
'\" UTILITY OR ANY PART THEREOF.
'\"
'\" In no event will Harris, Inc. be liable for any lost revenue
'\" or profits or other special, indirect and consequential damages, even if
'\" Harris has been advised of the possibility of such damages.
'\"
'\" Harris Computer Systems Division
'\" 2101 W Cypress Creek Rd
'\" Fort Lauderdale, Florida 33309
'\"
@.TH COMBINE 1 "" "CX/UX User's Reference Manual"
@.SH NAME
combine, combine2 \- compare or combine 2 or 3 source files
@.SH SYNOPSIS
@.B combine
[
@.B \-options
] old_file new1_file [ new2_file ]
@.br
@.B combine2
temp_file merged_file
@.SH DESCRIPTION
@.I Combine
compares the differences between 2 or 3 source files and produces
a result file.
Where 'old_file' is the name of the original file, 'new1_file' is a file
containing modifications to 'old_file', and 'new2_file' is a file containing
a different set of modifications to 'old_file'.
@.sp
The option arguments are:
@.TP 9
@.B \-b
Blank compress option --
Causes
@.I combine
to treat all sequences of blanks and horizontal tabs
as a single blank.
@.TP
@.B \-B
Blank remove option --
Causes
@.I combine
to ignore all blanks and horizontal tabs in a line
when comparing lines.
@.TP
@.B \-c #,#
Column specification option -- Specifies the column range to be compared.
By default, all columns are compared.
The number of the
first column to compare immediately follows the -c option.
The number of the last column to compare is separated from the first column
to compare by a comma.
Up to 32 different column ranges may be given.

For example,

      combine -c10,20 a b c

compares only columns 10 through 20.
@.TP
@.B \-d flag
Debug options -- specifies how much debug information is to be output.
The possibilities are:
@.B \-d1,
pass1 debug;
@.B \-d2,
pass2 debug;
@.B \-d3,
pass3 debug;
@.B \-d4,
pass4 debug;
@.B \-d5,
pass5 debug; and
@.B \-da,
all debug.
@.TP
@.B \-h
h option -- produces a composite file on standard output suitable
for input into
@.IR combine2 (1).
The file is an ASCII text file which may be manually modified by an text
editor such as
@.IR vi (1).
The example below describes the use of this option in detail.
@.TP
@.B \-p #
Postfix option -- The number of unchanged lines to output to the standard
output file following any group of changed lines.
The number of unchanged lines is specified by the argument following the -p
option. The default is 5.
This option is used only if the
@.B \-h
option is not specified.
@.TP
@.B \-P #
Prefix option -- The number of unchanged lines to output to the standard
output file prior to any group of changed lines.
The number of unchanged lines is specified by the argument following the -P
option. The default is 5.
This option is used only if the
@.B \-h
option is not specified.
@.TP
@.B \-q
Quiet option -- Specifies that no output is to be generated to the standard
output file if no changes are detected.
@.TP
@.B \-s
Statistics option -- Specifies that performance statistics are to be output
to standard output when
@.B combine
is finished.
@.TP
@.B \-1 text
New1 file description -- Symbolic description of the 'new1' file. This text
is printed as the description of the new1 file on the listing output and
h option output file.
@.TP
@.B \-2 text
New2 file description -- Symbolic description of the 'new2' file. This text
is printed as the description of the new1 file on the listing output and
h option output file.
@.SH EXAMPLE
@.I Combine
may be used to perform a simple two file comparison.
by merely omitting the name of the third file.
@.PP
@.I Combine
is best suited to do a three file comparison.
Consider a file which is being modified along two development paths.
The original copy of the file with no modifications is called the 'old' file.
The copy modified along one development path is called the 'new1' file.
The copy modified along the other development path is called the 'new2' file.
The following is a guide for producing a 'merged' file which contains
both set of modifications.

First,
@.I combine
is called with the following command line:

   combine -h old new1 new2 >temp_file

The 'temp_file' contains all of the lines from the 'old', 'new1' and 'new2'
files combined with control lines. A control line identifies those
portions of the 'temp_file' which represent modifications made by the 'new1'
and 'new2' files.

Text which is inserted by the 'new1' or 'new2' file is surrounded by
an ~~Insert line and an ~End line. The ~~Insert line also contains comments
indicating which of the two files the inserted lines came from and whether
the insertion was involved in a 'move' operation.
In the example below, the line 'apple' was inserted between two already
existing lines 'bob' and 'fred'.

    bob
    ~~Insert 'file2'
    apple
    ~End of changes
    fred

Text which is deleted by the 'new1' or 'new2' file is surrounded by
an ~~Delete line and an ~End line. The ~~Delete line also contains comments
indicating which of the two files deleted the specified lines an whether
the deletion is a side effect of a 'move' operation.
In the example below, the line 'apple' was deleted from between the
lines 'bob' and 'fred'.

    bob
    ~~Delete 'file1'
    apple
    ~End of changes
    fred

The 'temp_file' may be edited with any text editor. Changes in the 'temp_file'
can easily be found by finding lines with two tildes (~~) on them. Changes
which are correct should be left alone. Changes which are wrong should be
fixed. Deleted text can be allowed to remain in the file by merely deleting
the ~~Delete line. Things to watch out for during this process include:
Lines which are inserted by both the 'new1' and 'new2' files, and lines
which are deleted by both the 'new1' and 'new2' files.

After all of the changes have been made in the tempfile,
@.IR combine2(1)
should be used to produce the merged file.
@.IR Combine2(1)
is called with the following command line:

      combine2 temp_file merged_file

@.IR Combine2(1)
produces a merged file by removing the control lines and the deleted
lines from the temp file. If the name of the temp file is omitted, standard
input is used. If the name of the merged file is omitted, standard output
is used.
@.SH SEE ALSO
cmp(1), combine2(1), comm(1), diff(1), diff3(1)
@.SH DIAGNOSTICS
Exit status is 0 for files identical, 1 for some differences, 2 for errors.
@.SH AUTHOR
Clifford P. Van Dyke
@.SH BUGS
Does not allow input file to be specified as \- to indicate stdin.

Does not allow comparison of binary files. Does not always complain if an
input file is a binary file.

Does not check to see if two files have the same inode.
@.Em
@//E*O*F combine.1//
chmod u=rw,g=r,o=r combine.1

echo x - design_spec
sed 's/^@//' > "design_spec" <<'@//E*O*F design_spec//'
'\"
'\" The combine utility is a product of Harris, Inc. and is provided for
'\" unrestricted use provided that this legend is included on all tape
'\" media and as a part of the software program in whole or part.  Users
'\" may copy, modify, license or distribute the combine utility without charge.
'\"
'\" THE COMBINE UTILITY IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND
'\" INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR A
'\" PARTICULAR PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE
'\" PRACTICE.
'\"
'\" The combine utility is provided with no support and without any obligation
'\" on the part of Harris, Inc. to assist in its use, correction,
'\" modification or enhancement.
'\"
'\" HARRIS, INC. SHALL HAVE NO LIABILITY WITH RESPECT TO THE
'\" INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THE COMBINE
'\" UTILITY OR ANY PART THEREOF.
'\"
'\" In no event will Harris, Inc. be liable for any lost revenue
'\" or profits or other special, indirect and consequential damages, even if
'\" Harris has been advised of the possibility of such damages.
'\"
'\" Harris Computer Systems Division
'\" 2101 W Cypress Creek Rd
'\" Fort Lauderdale, Florida 33309
'\"
@.so /usr/lib/tmac/tmac.m
@.de )k                      \" remove -- lines at top of page
@..
@.nr Cl 7                    \" keep level 1-7 headers in table of contents
@.nr Hb 7                    \" all text after heading starts on new line
@.nr Hs 7                    \" all headers followed by 1 line
@.nr Li 10                   \" AL indent: 10 spaces
@.nr Pi 10                   \" BL indent: 10 spaces
@.nr Ps 2                    \" paragraph spacing: 2 lines
@.ds HF 3 3 3 3 2 2 2        \" header fonts: bold, italic, normal
@.ds HP +6 +4 +2 +2          \" print first level headings 2 ps larger
@.ds T \t
@.ll 6.5i
@.de HX                \" macro to ensure 15 lines on page before heading
@.nr ;3 (15-\\n(;0)v
@..
@.de HZ                      \" macro to output a blank line after heading
@.sp 0.5v
@..
@.PH "''Combine Utility Design Spec''"
@.PF "'' - Page \\\\nP -''"
@.TL
Combine Utility
@.br
Design Specification
@.AF "Harris Computer Systems"
@.AU "Cliff Van Dyke"
@.MT 4
@.ce
January 1985
\}
This utility compares the differences in 3 source files and produces
a result file.
@.H 1 "Invocation Sequence"
The combine utility accepts the following UNIX-like invocation sequence.

   combine [option-args] old_file new1_file [new2_file] [>list_output]

where 'old_file' is the name of the original file, 'new1_file' is a file
containing modification to 'old_file', and 'new2_file' is a file containing
a different set of modifications to 'old_file'. (Actually, see the
functionality section for a description of other possible uses.)

where the option arguments are:
@.VL 10
@.LI -b
Blank compress option --
Causes COMBINE to treat all sequences of blanks and horizontal tabs
as a single blank.
@.LI -B
Blank remove option --
Causes COMBINE to ignore all blanks and horizontal tabs in a line
when comparing lines.
@.LI "-c #,#"
Column specification option -- Specifies the column range to be compared.
If column range is not specified, columns 1 through 135 are compared.
The number of the
first column to compare immediately follows the -c option.
The number of the last column to compare is separated from the first column
to compare by a comma.
Up to 32 different column ranges may be given.

For example,

      combine -c10,20 a b c

compares only columns 10 through 20.

IMPORTANT NOTE: On VOS, the comma which separates the column values must
be enclosed in quotes.
@.LI "-d flag"
Debug options -- specifies how much debug information is to be output.
The possibilities are: -d1, pass1 debug; -d2, pass2 debug; -d3, pass3 debug;
-d4, pass4 debug; -d5, pass5 debug; and -da, all debug.
@.LI "-e area"
MERGE editor option -- specifies the name of the disk area to write the
MERGE script to. This script contains adequate information to allow MERGE
to edit the 'old' file and insert the changes from
the 'new1' and 'new2' files.
The file name is specified by the argument following the -e option.
This option is not yet implemented.
@.LI "-h area"
HED editor option -- specifies the name of the disk area to write the
HED script to. This script contains adequate information to allow HED
to highlight changes to the 'old' file which produce the 'new1' and 'new2'
files.
The file name is specified by the argument following the -h option.
@.LI "-p #"
Postfix option -- The number of unchanged lines to output to the standard
output file following any group of changed lines.
The number of unchanged lines is specified by the argument following the -p
option. The default is 5.
@.LI "-P #"
Prefix option -- The number of unchanged lines to output to the standard
output file prior to any group of changed lines.
The number of unchanged lines is specified by the argument following the -p
option. The default is 5.
@.LI -q
Quiet option -- Specifies that no output is to be generated to the standard
output file if no changes are detected.
@.LI "-1 text"
New1 file description -- Symbolic description of the 'new1' file. This text
is printed as the description of the new1 file on the listing output and
HED output file.
@.LI "-2 text"
New2 file description -- Symbolic description of the 'new2' file. This text
is printed as the description of the new1 file on the listing output and
HED output file.
@.LE
@.H 1 Uses
@.H 2 "Two file comparison"
The combine utility may be used to perform a simple two file comparison
by merely omitting the name of the third file.
@.H 2 "Three file comparison"
The combine utility is best suited to do a three file comparison.
Consider a file which is being modified along two development paths.
The original copy of the file with no modifications is called the 'old' file.
The copy modified along one development path is called the 'new1' file.
The copy modified along the other development path is called the 'new2' file.
The following is a guide for producing a 'merged' file which contains
both set of modifications.

First, combine is called with the following command line:

   combine -h temp_file old new1 new2 >listing

The output in the 'listing' file is a 'pretty' summary of the changes.
The 'temp_file' contains all of the lines from the 'old', 'new1' and
'new2' files combined with control lines. A control line identifies those
portions of the 'temp_file' which represent modifications made by the
'new1' and 'new2' files.

Text which is inserted by the 'new1' or 'new2' file is surrounded by an
@~~Insert line and an ~End line. The ~~Insert line also contains comments
indicating which of the two files the inserted lines came from and whether
the insertion was involved in a 'move' operation.
In the example below, the line 'apple' was inserted between two already
existing lines 'bob' and 'fred'.


    bob
    ~~Insert 'file2'
    apple
    ~End of changes
    fred


Text which is deleted by the 'new1' or 'new2' file is surrounded by
an ~~Delete line and an ~End line. The ~~Delete line also contains comments
indicating which of the two files deleted the specified lines an whether
the deletion is a side effect of a 'move' operation.
In the example below, the line 'apple' was deleted from between the
lines 'bob' and 'fred'.


    bob
    ~~Delete 'file1'
    apple
    ~End of changes
    fred


The 'temp_file' may be edited with any text editor. Changes in the 'temp_file'
can easily be found by finding lines with two tildas (~~) on them. Changes
which are correct should be left alone. Changes which are wrong should be
fixed. Deleted text can be allowed to remain in the file by merely deleting
to ~~Delete line. Things to watch out for during this process include:
the ~~Delete line. Things to watch out for during this process include:
Lines which are inserted by both the 'new1' and 'new2' files, and lines
which are deleted by both the 'new1' and 'new2' files.

After all of the changes have been made in the tempfile, the 'combine2'
utility should be used to produce the merged file. Combine2 is called
with the following command line:


      combine2 temp_file merged_file


Combine2 produces a merged file by removing the control lines and the deleted
lines from the temp file. If the name of the temp file is omitted, standard
input is used. If the name of the merged file is omitted, standard output
is used.
@.H 1 Algorithm
Combine uses the general algorithm as described in "A technique for Isolating
differences between files"; Communications of the ACM; April 1978; Volume 21
Number 4. This document presents a very, very brief overview of that algorithm
and modifications made to that algorithm to overcome its weaknesses and
to allow support for a 3 file comparison.
@.H 2 "Term Definition"
This section contains definitions of several terms
used in the description of the algorithm.

The 'current file' is one of the files being compared.
At any point in the algorithm, the 'current
file' is the one which is being compared to the 'corresponding file'.
The 'other file' is the file which is neither the current file
nor the corresponding file.
@.H 2 "Record Array Description"
For each file which is being compared, a record array exists. There is one
entry in the array for every record in the file. There is also a dummy entry
at the beginning of the array and a dummy entry at the end of the array. These
dummy entries allow easy detection of beginning of file and end of file.

Each entry in the array contains an 'rfa'. An 'rfa' is a
record's file address. An rfa can be used to position the file to the particular
record. On VOS, the rfa is merely the record's CRA (current record address).
On UNIX, the rfa is byte displacement into the file.

Each entry in the array also contains two 'value' fields. Each value field
describes the relationship between the current file and the other two files.
The content of the value field will become obvious as we progress through
the description of the algorithm. For now, suffice it to say that the field
contains either a negative displacement into the symbol table or a positive
displacement into the record array of the corresponding file.
@.H 2 "Symbol Table Description"
The symbol table consists of four arrays each indexed by the same value.
The index into the symbol table is a unique
hash code computed from the text of the record from any of the files. Identical
records always hash to the same location. Different records always hash to
different locations.

The first symbol table array is the cache pointer array.
The value in this array is 0 if the symbol
table entry is not used. The value is a pointer to the cache entry if
the symbol table entry is used and the record is still in cache. The value
is -1 if the symbol table entry is used but the record is not in cache.

One symbol table array exists for each file being compared. The value in
this array is 0 if the hashed record does not occur in the current file at all.
The value is a positive record number if the hash record occurs in the
current file precisely once. The value is a negative record number if the
hash code occurs in the current file more than once.
@.H 2 Cache
The cache maintains a copy of the text of the 300 most recently read records.
Combine ensures that two records that hash to the same value are indeed
the same record by comparing actual record contents. The cache allows the
comparison to be done efficiently. See the description of pass1 for detailed
information.
@.H 2 Pass1
Pass1 reads all of the records from all of the files and initializes the
symbol table and record arrays. On completion of this pass,
the symbol table is initialized as described above and the record array
for each file contains a negative hash code for each record in the file.

Pass1 reads a record from a file into a cache entry.
Pass1 then computes the hash code for the record.
If the hash code has never been used before, pass1 links the cache entry from
the symbol table, marks the symbol table of the current file to indicate
that this line exists precisely once in the file, and marks the record array
of the current file to contain the negative hash code.

If the hash code has been used before, the value of the current record is
compared with the value of the other record which hashed to the same value.
The other record is either already in cache or is read into cache at this
time.

If the current record and the other record are the same, pass1 marks the
symbol table of the current file to indicate that this line exists in the
file and marks the record array of the current file to contain the negative
hash code. This condition can occur under two circumstances. First, a
record from one file and the same record from the corresponding file will
hash to the same location. Second, a record from one file and the same
record at a different location in the same file will hash to the same location.
The symbol table entry is marked to indicate whether a record occurs precisely
once in a particular file or whether is occurs multiple times in a particular
file.

If the current record and the other record are different, pass1 computes a
different hash code for the current record and the above
algorithm is repeated.

Pass1 alternately reads one record from each file. Thus, if a record is read
into cache on the first file, the record will probably still be in cache
when it is read on the second file. Cache is only used as described here in
pass1. Nothing in the cache is passed between passes.
@.H 2 Pass2
Pass2 determines anchor points in the files. Pass2 identifies lines
which occur precisely once in at least two of the files and no more than
once in the third file. On completion of this pass, the record array
for each file
contains either a negative hash code for those records which don't meet
the above criteria or contains a positive index into the record array
of the corresponding file for those records which do meet the criteria.
The symbol table is no longer used following this pass.
@.H 2 Pass3
Pass3 expands the anchor points to non-unique records. A non-unique record
is a record which occurs more than once in at least one file. On completion
of this pass, record array for each file will contain more positive indexes
into the record array of another file and less negative hash codes.
In general, following this pass, records which have negative hash codes
are records which exist in the current file and have absolutely no corresponding
records in the corresponding file. (I'll be more specific on this when I
discuss pass4.)

Each pair of two files is scanned first in the forward direction and then
in the backward direction. If, in the pair of files, there are lines which
are adjacent to an anchor point and which are identical to each other, these
lines are considered to be anchor points themselves. Lines are compared by
comparing their negative hash codes.
@.H 2 Pass4
Pass4 expands the anchor points into non-unique record clusters.
Pass4 tries to fix up problems which arise due to groups of non-unique
records which are surrounded by insertions. When pass3 completed these
records were treated as a part of the insertion. If, indeed, a large
portion of the insertion actually matches a large portion of an insertion
in another file, but if the match went undetected because the records
were non-unique, then pass4 finds these non-unique lines and matches them.

Pass4 finds a pair of anchor records which have inserted lines between
them (See diagram below). All inserted lines are compared to one another
trying to find a group of non-unique lines which match. Such lines are
considered equal and are flagged as anchor points.

          match1                       match1
          insert
          non-unique1                  non-unique1
          insert
          match2                       match2

The current implementation of the algorithm runs in M x N time where M is
the number of inserted lines at the current position in the first file and
N is the number of inserted lines at the current position in the second file.
@.H 2 Pass5
Pass5 outputs the result of the comparison. The record arrays for the
three files are traversed. An index is maintained into each of the record
arrays. As each index is incremented the corresponding record is output.
Pass5 merely determines which file the next record is to come from.

The hardest problem for pass5 to resolve is one of record movement. That is,
if a group of records from one file is moved to a different position in the
second file. In this situation, the 'shortest' group of records is considered
to have moved. This group of records is output first by pass5.

Pass5 uses the record cache to maintain a list of the last several records
output. This cache is used to enable the 'prefix' lines capability of
the comparison listing.
@//E*O*F design_spec//
chmod u=rw,g=rw,o=rw design_spec

echo x - combine.h
sed 's/^@//' > "combine.h" <<'@//E*O*F combine.h//'
/*
 * The combine utility is a product of Harris, Inc. and is provided for
 * unrestricted use provided that this legend is included on all tape
 * media and as a part of the software program in whole or part.  Users
 * may copy, modify, license or distribute the combine utility without charge.
 *
 * THE COMBINE UTILITY IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND
 * INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE
 * PRACTICE.
 *
 * The combine utility is provided with no support and without any obligation
 * on the part of Harris, Inc. to assist in its use, correction,
 * modification or enhancement.
 *
 * HARRIS, INC. SHALL HAVE NO LIABILITY WITH RESPECT TO THE
 * INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THE COMBINE
 * UTILITY OR ANY PART THEREOF.
 *
 * In no event will Harris, Inc. be liable for any lost revenue
 * or profits or other special, indirect and consequential damages, even if
 * Harris has been advised of the possibility of such damages.
 *
 * Harris Computer Systems Division
 * 2101 W Cypress Creek Rd
 * Fort Lauderdale, Florida 33309
 */
#ifdef ALLOC
#   define EXTERN
#   define INIT( _x ) = _x
#else
#   define EXTERN extern
#   define INIT( _x )
#endif

/*
 * Some OS dependent stuff
 */
#define rfa_type long

#define SZ$_FILE_NAME 256
#ifdef VOS    /* 24-bit word */
#define HI7       077400000    /* Hi 7 bits of a word */
#else        /* 32-bit word */
#define HI7       0xFE000000    /* Hi 7 bits of a word */
#endif

/*
 * Cache Entry:
 *
 * This structure describes a single entry in the cache of lines.
 * The cache is organized as a linked list of cache entries.
 * The entries at the front of the list are the most recently accessed.
 * The variables 'cache_head_ptr' and 'cache_tail_ptr' point to the
 * head and the tail of the cache.
 */

struct cache_entry_struct;
typedef struct cache_entry_struct       cache_entry_type;

struct cache_entry_struct {

    cache_entry_type * cache_next_ptr;/* Link to the next cache entry */

    cache_entry_type * cache_prev_ptr;/* Link to the prev cache entry */

    int     hash_code;    /* The hash code for the line. A a value of
                   HASH_FREE_ENTRY indicates this is a free
                   cache entry. */

    int     record_length;    /* Length of the record */

    char    *recordp;    /* Actual record contents. */

    int    record_alen;    /* Allocated length of recordp buffer */

};

#define CACHE_ENTRIES 500    /* Total number of cache entries */
EXTERN cache_entry_type * cache_head_ptr;/* Head of the cache linked list. */
EXTERN cache_entry_type * cache_tail_ptr;/* Head of the cache linked list. */


#define LINE_LENGTH 135        /* Default line length */

/* Maximum number of characters in a record */
/*
 * record_type:
 *
 * This structure describes a single record in a file.
 * The 'file_type' structure points to an array of these entries.
 */

struct record_struct;
typedef struct record_struct    record_type;

struct record_struct {

    rfa_type rfa;        /* The record's file address. This is an
                   operating system dependent value which is a
                   token which can be used to seek to the
                   specified record. */

/*
 * The 'value' field describes the relationship between this record and
 * another record in another file. Valid values are:
 *
 * Negative:        hash code for the record (See 'is_hash_code' macro).
 *                  A hash code is an index into the symbol table.
 * 0 or Positive:   index into record array of other file.
 *
 * The defines below are used to describes whether the 'value[0]' or
 * 'value[1]' field is used to describe a relationship between files.
 */

#define MAX_VALUE_SUB 2

    int     value[MAX_VALUE_SUB];
                /* Describes the relationship between this
                   record and another record in another file.
                */


#define OLD_TO_NEW1         0    /* Old file: index into new1  */
#define OLD_TO_NEW2         1    /* Old file: index into new2  */
#define NEW1_TO_OLD         0    /* new1 file: index into old  */
#define NEW1_TO_NEW2        1    /* new1 file: index into new2 */
#define NEW2_TO_OLD         0    /* new2 file: index into old  */
#define NEW2_TO_NEW1        1    /* new2 file: index into new1 */

};

/*
 * Record index values:
 *
 * Record indexes include a special record at the beginning of the file
 * and a special record at the end of the file. These definitions describe
 * that phenomena.
 */

#define BEGIN_INDEX 0        /* Index of the dummy begin record */
#define DUMMY_RECORD_COUNT 2    /* Number of dummy records */

/*
 * File Description:
 *
 * This structure describes a single input file.
 * A structure of this type occurs for the 'old' file, 'new1' file,
 * and 'new2' file.
 */

struct file_struct;
typedef struct file_struct      file_type;

struct file_struct {

    char   *name_ptr;    /* Zero terminated name of file */

    char   *text_ptr;    /* Zero terminated text describing file */

    char   *lw_ptr;        /* Zero terminated last written date */

    FILE *  seq_fd;        /* fd to use for sequential access */

    FILE *  rnd_fd;        /* fd to use for random access */

    int     record_array_size;/* number of lines in the file (including
                     DUMMY_RECORD_COUNT). */

    int    record_array_alloc;/* number of allocated entries in the
                   record array. */

#define RA_ORIG    5000        /* Original # of records in record array */
#define RA_INCR 5000        /* Number of records to add on each increment */

    record_type * record;    /* Allocated array of record descriptions.
                   This field contains 0 if the file does not
                   exists. (i.e., this is the third file in a
                   two file comparison ) */

/*
 * The entry below is actually the portion of the symbol table which
 * needs an entry for each file. The array is indexed by 'hash_code'.
 *
 * Each index below is an index into the array for the specified file.
 * Valid values are:
 *
 * 0:                      This line is not in this file.
 * negative:               This line is not unique in the file.
 *                         Value is negative index to one of the records.
 * not negative:           This line occurs precisely once in the file.
 *                         Value is index to the record.
 */

    int    *sym_tab_index;    /* Index into 'record'. */
                /* There are 'sym_tab_size' elements in this array. */
};

#define OLD_FILE   0        /* Array index of 'old' file */
#define NEW1_FILE  1        /* Array index of 'new1' file */
#define NEW2_FILE  2        /* Array index of 'new2' file */
#define MAX_FILE_COUNT 3    /* Maximum number of files */

EXTERN int      file_count;    /* actual number of files */

EXTERN file_type files[MAX_FILE_COUNT];/* Description of the each file. */

/*
 * For each record, six different relationships exist. That is,
 * for each of the three files there is a relationship to each of the
 * other two files.
 * The tables below describe the six relationships.
 */

#define MATCH_COUNT ( 2*MAX_FILE_COUNT )

EXTERN int      curr_file[MATCH_COUNT]
#ifdef ALLOC
= {
    OLD_FILE, OLD_FILE, NEW1_FILE, NEW1_FILE, NEW2_FILE, NEW2_FILE
}
#endif
           ;

/*Array of subsrcipts into the 'files' array of files which have
relationships */

EXTERN int      corres_file[MATCH_COUNT]
#ifdef ALLOC
= {
    NEW1_FILE, NEW2_FILE, OLD_FILE, NEW2_FILE, OLD_FILE, NEW1_FILE
}
#endif
           ;
/* Array of subscripts into the 'files' array of the file which is related to */


EXTERN int      other_file[MATCH_COUNT]
#ifdef ALLOC
= {
    NEW2_FILE, NEW1_FILE, NEW2_FILE, OLD_FILE, NEW1_FILE, OLD_FILE
}
#endif
           ;
 /* Array of subscripts into the 'files' array of the file which is not
    involved in the current relationship */

EXTERN int      value_sub[MATCH_COUNT]
#ifdef ALLOC
= {
    OLD_TO_NEW1, OLD_TO_NEW2, NEW1_TO_OLD, NEW1_TO_NEW2,
    NEW2_TO_OLD, NEW2_TO_NEW1
}
#endif
           ;
 /* Array of subscripts to the 'value' array. This subscript identifies which
    of the two relationships are being tested. */

EXTERN int      rev_value_sub[MATCH_COUNT]
#ifdef ALLOC
= {
    NEW1_TO_OLD, NEW2_TO_OLD, OLD_TO_NEW1, NEW2_TO_NEW1,
    OLD_TO_NEW2, NEW1_TO_NEW2
}
#endif
           ;
 /* Array of subscripts to the 'value' array. This subscript identifies the
    relationship between the 'corres' file and the 'curr' file */

EXTERN int      other_value_sub[MATCH_COUNT]
#ifdef ALLOC
= {
    NEW2_TO_OLD, NEW1_TO_OLD, NEW2_TO_NEW1, OLD_TO_NEW1,
    NEW1_TO_NEW2, OLD_TO_NEW2
}
#endif
           ;
 /* Array of subscripts to the 'value' array. This subscript identifies the
    relationship between the 'other' file and the 'curr' file */


#define UNIQUE_MATCH_COUNT (MATCH_COUNT / 2)

EXTERN int      unique_match[UNIQUE_MATCH_COUNT]
#ifdef ALLOC
= {
    0, 1, 3
}
#endif
           ;
 /* Array of subscripts into the relation arrays defined above. These are the
    subscripts of the relations pairing each pair of files precisely once. */
/*
 * is_hash_code:
 *
 * This macro determines if the value in the record array is a hash code
 * or an index into another file array. This macro relies on the fact
 * that all hash codes are nagetive.
 *
 * Return value:
 *      TRUE:  The value represents a hash code
 *      FALSE: The value represents an index into a file array.
 *
 * Parameter:
 *      value: The value from the file array.
 */

#define is_hash_code( _value )  ((_value) < 0)
/*
 * Options:
 */

EXTERN bool blank_compress INIT (FALSE);
                /* TRUE if blank compression is desired */

EXTERN bool blank_remove INIT (FALSE);/* TRUE if blank removal is desired */

EXTERN bool compress_records INIT (FALSE);
                /* TRUE if any record compression needs to
                   occur */

EXTERN int      prefix_lines INIT (5);/* Number of prefix lines */

EXTERN int      postfix_lines INIT (5);/* Number of postfix lines */

EXTERN bool quiet_option INIT (FALSE);
                /* TRUE if COMBINE is to be quiet if there are
                   no differences */

EXTERN bool pa_debug INIT (FALSE);/* TRUE for generic debugging */
EXTERN bool p1_debug INIT (FALSE);/* TRUE for debug of pass 1 */
EXTERN bool p2_debug INIT (FALSE);/* TRUE for debug of pass 2 */
EXTERN bool p3_debug INIT (FALSE);/* TRUE for debug of pass 3 */
EXTERN bool p4_debug INIT (FALSE);/* TRUE for debug of pass 4 */
EXTERN bool p5_debug INIT (FALSE);/* TRUE for debug of pass 5 */

EXTERN bool statistics_flag INIT (FALSE);/* TRUE to output statistics */

EXTERN bool hed_flag INIT (FALSE);/* TRUE to output hed file */

EXTERN char     exec_time[LINE_LENGTH];/* Begin execution time */

/*
 * Column specifications:
 */

#define MAX_COLUMNS 32        /* maximum number of column ranges */

EXTERN int      column_count INIT (0);/* Actual number of column ranges */

EXTERN int      first_column[MAX_COLUMNS];/* first column to compare */
                /* Column numbers are 0 relative */

EXTERN int      last_column[MAX_COLUMNS];/* last column to compare */
                 /* Column numbers are 0 relative */

/*
 * other_sub:
 *
 * This macro is given the subscript to one of the elements in the
 * 'value' array and returns the subscript to the other element.
 * This macro is heavily dependent on the fact that there are only
 * two elements in the value array.
 *
 * Return value:
 *      other subscript
 *
 * Parameter:
 *      value_sub: Subsrcipt into the value array.
 */

#define other_sub( _sub )  ( 1 - (_sub) )

/*
 * Primes: list of prime numbers.
 *
 * This array defines a set of prime numbers. For all multiples of 1024,
 * this table contains the prime number which is less than but closest
 * to that number.
 *
 * The list is terminated by a -1.
 */

EXTERN int      primes[]
#ifdef ALLOC
= {
    1021, 2039, 3067, 4093, 5119, 6143, 7159, 8191, 9209,
    10223, 11261, 12281, 13309, 14327, 15359, 16381, 17401, 18427,
    19447, 20479, 21503, 22511, 23549, 24571, 25589, 26597, 27647,
    28669, 29683, 30713, 31741, 32749, 33791, 34807, 35839, 36857,
    37879, 38903, 39929, 40949, 41983, 43003, 44029, 45053, 46073,
    47093, 48121, 49139, 50159, 51199, 52223, 53239, 54269, 55291,
    56311, 57331, 58367, 59387, 60413, 61417, 62459, 63487, 64499,
    65521, 66553, 67579, 68597, 69623, 70639, 71671, 72701, 73727,
    74747, 75773, 76781, 77813, 78839, 79867, 80863, 81919, 82939,
    83939, 84991, 86011, 87037, 88037, 89087, 90107, 91129, 92153,
    93179, 94207, 95231, 96233, 97259, 98299, 99317, 100343, 101363,
    102397, 103423, 104417, 105467, 106487, 107509, 108541, 109567,
    110587, 111611, 112621, 113657, 114679, 115693, 116731, 117757,
    118757, 119797, 120829, 121853, 122869, 123887, 124919, 125941,
    126967, 127997, 129023, 130043, 131071, 132071, 133117, 134129,
    135151, 136189, 137209, 138239, 139241, 140281, 141311, 142327,
    143357, 144383, 145399, 146423, 147451, 148471, 149503, 150523,
    151549, 152567, 153589, 154621, 155627, 156671, 157679, 158699,
    159739, 160757, 161783, 162791, 163819, 164839, 165887, 166909,
    167917, 168943, 169957, 171007, 172031, 173053, 174079, 175103,
    176123, 177131, 178169, 179173, 180221, 181243, 182261, 183289,
    184309, 185327, 186343, 187387, 188407, 189439, 190409, 191473,
    192499, 193513, 194543, 195581, 196597, 197621, 198647, 199679,
    200699, 201709, 202751, 203773, 204797, 205823, 206827, 207869,
    208891, 209917, 210943, 211949, 212987, 214009, 214993, 216061,
    217081, 218111, 219133, 220151, 221173, 222199, 223229, 224251,
    224737,
    -1
}
#endif
           ;

/*
 * relate_type:
 *
 * This structure describes the relationsip between between a particular
 * record of a particular file and corresponding records in the other
 * files.
 *
 * This structure is built by 'pass5_analyze_relationship'. This structure
 * is used by all of the other pass5 routines to determine whether the
 * current record is the next one to be output.
 */

struct relate_struct;
typedef struct relate_struct    relate_type;

struct relate_struct {

    int     index[MAX_FILE_COUNT];
                /* Index that this record appears at in the
                   file. Value will be a hash code if this
                   record is not in the corresponding file */

    bool current[MAX_FILE_COUNT];
                /* TRUE if the record at the current position
                   in the corresponding file */

    int     relation;    /* A summary of the relationship of this record
                   to the current record in each file */
    /* The zeroeth element is represented in the least significant bit,
       etc. */

#define INSERT_NONE           0
#define INSERT_OLD            1
#define INSERT_NEW1           2
#define INSERT_OLD_NEW1       (INSERT_OLD + INSERT_NEW1)
#define INSERT_NEW2           4
#define INSERT_OLD_NEW2       (INSERT_OLD + INSERT_NEW2)
#define INSERT_NEW1_NEW2      (INSERT_NEW1 + INSERT_NEW2)
#define INSERT_OLD_NEW1_NEW2  (INSERT_OLD + INSERT_NEW1 + INSERT_NEW2)
#define INSERT_EOT            -1

    bool moved;        /* TRUE if this record is involved in a record
                   movement. */

    bool in_all;        /* TRUE if the record is at the current
                   position in all of the files. */

};

/*
 * Statistics:
 */

EXTERN int      cache_miss;    /* total number of cache misses. */

EXTERN int      hash_collisions;/* total number of hash collsions */

EXTERN int      old_new1_change_count;
                /* Number of differences between old and new1
                   files */

EXTERN int      old_new2_change_count;
                /* Number of differences between old and new2
                   files */

EXTERN int      new1_new2_change_count;
                /* Number of differences between new1 and new2
                   files */

/*
 * Symbol Table:
 *
 * This structure describes a the symbol table.
 * Each entry in the symbol table represents a record in one of the files.
 * The contents of each record is hashed.
 * The hash value is used as an index into the arrays.
 * If the hash value is not unique, a re-hash is performed until a
 * unique hash value is obtained.
 *
 * The symbol table is organized as four arrays of entries.
 * There is one array for each file and one array of cache entry pointers
 * described below.
 */

/*
 * The index into the symbol table is a hash code. Hash codes are positive.
 * Significant hash codes include:
 *
 * 0: Not valid
 * 1: begin record
 * 2: end record
 * 3: eof (some archaic operating systems allow multiple eof's in a file.)
 */

#define HASH_FREE_ENTRY 0    /* A hash code of this value indicates a free
                   entry. This value is used in a cache entry
                   to indicate an unused cache entry */

/*
 * The cache ptr below is a pointer to the cache entry for the line.
 * Valid values are:
 *
 * CACHE_FREE_ENTRY:       This symbol table entry is unused.
 * CACHE_NOT_IN_CACHE:     This line is no longer in the cache.
 * positive:               Pointer to cache entry.
 */

EXTERN cache_entry_type * *sym_tab_cache_ptr;
                /* Pointer to table of pointers to cache
                   entries */

#define CACHE_FREE_ENTRY 0    /* Symbol table entry is unused */
 /* The code depends on the fact that the allocator zeros this entry upon
    allocation */

#define CACHE_NOT_IN_CACHE -1    /* This line no longer in cache */

EXTERN int      sym_tab_size;    /* Number of entries in the symbol table. */
/*
 * Procedure forwards:
 */

void dump_arrays() ;
void dump_statistics() ;
void dump_sym_tab() ;

void error() ;
char * mem_alloc() ;
void init() ;
void link_records() ;

void pass1() ;
int  pass1_read_record() ;
void pass1_record_compress() ;

void pass2() ;

void pass3() ;
void pass3_scan() ;

void pass4() ;
void pass4_scan() ;

void pass5() ;
void pass5_analyze_relationship() ;
int  pass5_move() ;
void pass5_dump_record() ;
void pass5_write_hed() ;
void pass5_write_listing() ;
void pass5_write_listing_line() ;
void pass5_write_listing_head() ;
@//E*O*F combine.h//
chmod u=rw,g=rw,o=rw combine.h

echo x - Makefile
sed 's/^@//' > "Makefile" <<'@//E*O*F Makefile//'
# The combine utility is a product of Harris, Inc. and is provided for
# unrestricted use provided that this legend is included on all tape
# media and as a part of the software program in whole or part.  Users
# may copy, modify, license or distribute the combine utility without charge.
#
# THE COMBINE UTILITY IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND
# INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR A
# PARTICULAR PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE
# PRACTICE.
#
# The combine utility is provided with no support and without any obligation
# on the part of Harris, Inc. to assist in its use, correction,
# modification or enhancement.
#
# HARRIS, INC. SHALL HAVE NO LIABILITY WITH RESPECT TO THE
# INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THE COMBINE
# UTILITY OR ANY PART THEREOF.
#
# In no event will Harris, Inc. be liable for any lost revenue
# or profits or other special, indirect and consequential damages, even if
# Harris has been advised of the possibility of such damages.
#
# Harris Computer Systems Division
# 2101 W Cypress Creek Rd
# Fort Lauderdale, Florida 33309
#
#
# Makefile
#

OBJ = pass1.o pass2.o pass3.o pass4.o pass5.o main.o unix.o data.o
SRC = pass1.c pass2.c pass3.c pass4.c pass5.c main.c unix.c data.c
OBJ2 = combine2.o
SRC2 = combine2.c
LFLAGS = $(LFL)
CFLAGS=${CFL} -O

all: combine combine2

combine: ${OBJ}
    ${CC} ${CFLAGS} ${OBJ} -o combine

combine2: ${OBJ2} unix.o
    ${CC} ${CFLAGS} ${OBJ2} unix.o -o combine2

${OBJ} ${OBJ2} :
    ${CC} -c ${CFLAGS} $*.c

install: all
    install -r -f $(ROOT)/usr/bin combine
    install -r -f $(ROOT)/usr/bin combine2


clean:
    rm -f ${OBJ} ${OBJ2} core a.out errs

clobber: clean
    rm -f combine combine2

depend: combine.mk
    for i in ${SRC} ${SRC2}; do \
        (echo $$i: $$i >>makedep; \
        /bin/grep '^#[     ]*include' /dev/null $$i | sed \
            -e 's,<\(.*\)>,"$${ROOT}/usr/include/\1",' \
            -e 's/:[^"]*"\([^"]*\)".*/: \1/' >>makedep); done
    sed <makedep -e 's/\.c/\.o/' >makedep2
    echo '/^# DO NOT DELETE THIS LINE/+2,$$d' >eddep
    echo '$$r makedep2' >>eddep
    echo 'w' >>eddep
    cp combine.mk combine.mk.bak
    ed - combine.mk < eddep
    rm eddep makedep makedep2
    echo '# DEPENDENCIES MUST END AT END OF FILE' >> combine.mk
    echo '# IF YOU PUT STUFF HERE IT WILL GO AWAY' >> combine.mk
    echo '# see make depend above' >> combine.mk


# DO NOT DELETE THIS LINE -- make depend uses it
# DEPENDENCIES MUST END AT END OF FILE
pass1.o: pass1.c
pass1.o: ${ROOT}/usr/include/stdio.h
pass1.o: ${ROOT}/usr/include/ctype.h
pass1.o: util.h
pass1.o: os_dep.h
pass1.o: combine.h
pass2.o: pass2.c
pass2.o: ${ROOT}/usr/include/stdio.h
pass2.o: ${ROOT}/usr/include/ctype.h
pass2.o: util.h
pass2.o: os_dep.h
pass2.o: combine.h
pass3.o: pass3.c
pass3.o: ${ROOT}/usr/include/stdio.h
pass3.o: ${ROOT}/usr/include/ctype.h
pass3.o: util.h
pass3.o: os_dep.h
pass3.o: combine.h
pass4.o: pass4.c
pass4.o: ${ROOT}/usr/include/stdio.h
pass4.o: ${ROOT}/usr/include/ctype.h
pass4.o: util.h
pass4.o: os_dep.h
pass4.o: combine.h
pass5.o: pass5.c
pass5.o: ${ROOT}/usr/include/stdio.h
pass5.o: ${ROOT}/usr/include/ctype.h
pass5.o: util.h
pass5.o: os_dep.h
pass5.o: combine.h
main.o: main.c
main.o: ${ROOT}/usr/include/ctype.h
main.o: ${ROOT}/usr/include/stdio.h
main.o: ${ROOT}/usr/include/sys/types.h
main.o: ${ROOT}/usr/include/sys/stat.h
main.o: util.h
main.o: os_dep.h
main.o: combine.h
unix.o: unix.c
unix.o: ${ROOT}/usr/include/sys/types.h
unix.o: ${ROOT}/usr/include/sys/uio.h
unix.o: ${ROOT}/usr/include/sys/socket.h
unix.o: ${ROOT}/usr/include/sys/ioctl.h
unix.o: ${ROOT}/usr/include/sys/file.h
unix.o: util.h
unix.o: os_dep.h
unix.o: ${ROOT}/usr/include/stdio.h
unix.o: ${ROOT}/usr/include/ctype.h
data.o: data.c
data.o: ${ROOT}/usr/include/stdio.h
data.o: ${ROOT}/usr/include/ctype.h
data.o: util.h
data.o: os_dep.h
data.o: combine.h
comb2.o: comb2.c
comb2.o: ${ROOT}/usr/include/stdio.h
comb2.o: ${ROOT}/usr/include/ctype.h
comb2.o: util.h
comb2.o: os_dep.h
# DEPENDENCIES MUST END AT END OF FILE
# IF YOU PUT STUFF HERE IT WILL GO AWAY
# see make depend above
@//E*O*F Makefile//
chmod u=rw,g=rw,o=rw Makefile

exit 0