From bacchus.pa.dec.com!decwrl!apple!usc!cs.utexas.edu!uunet!allbery Sat Jun 16 11:53:50 PDT 1990 Article 1649 of comp.sources.misc: Path: bacchus.pa.dec.com!decwrl!apple!usc!cs.utexas.edu!uunet!allbery From: cliff@gcx1.SSD.CSD.HARRIS.COM (Cliff Van Dyke) Newsgroups: comp.sources.misc Subject: v13i054: combine: 3 file compare/merge utility (part 1of3) Message-ID: <93342@uunet.UU.NET> Date: 15 Jun 90 23:03:45 GMT Sender: allbery@uunet.UU.NET Lines: 1385 Approved: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc) Posting-number: Volume 13, Issue 54 Submitted-by: cliff@gcx1.SSD.CSD.HARRIS.COM (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 cliff@ssd.csd.harris.com Harris Computer Systems ...!{uunet,novavax}!hcx1!cliff 2101 W. Cypress Creek Rd. Ft. Lauderdale, FL 33309-1892 Tel: (305) 973-5349 # 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 cliff@ssd.csd.harris.com Harris Computer Systems ...!{uunet,novavax}!hcx1!cliff 2101 W. Cypress Creek Rd. Ft. Lauderdale, FL 33309-1892 Tel: (305) 973-5349 @//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 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