diff3.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

  -v  --version  Output version info.\n\
  --help  Output this help.\n\n");
  printf ("If a FILE is `-', read standard input.\n");
}

/*
 * Routines that combine the two diffs together into one.  The
 * algorithm used follows:
 *
 *   File2 is shared in common between the two diffs.
 *   Diff02 is the diff between 0 and 2.
 *   Diff12 is the diff between 1 and 2.
 *
 *	1) Find the range for the first block in File2.
 *	    a) Take the lowest of the two ranges (in File2) in the two
 *	       current blocks (one from each diff) as being the low
 *	       water mark.  Assign the upper end of this block as
 *	       being the high water mark and move the current block up
 *	       one.  Mark the block just moved over as to be used.
 *	    b) Check the next block in the diff that the high water
 *	       mark is *not* from.
 *
 *	       *If* the high water mark is above
 *	       the low end of the range in that block,
 *
 *		   mark that block as to be used and move the current
 *		   block up.  Set the high water mark to the max of
 *		   the high end of this block and the current.  Repeat b.
 *
 *	 2) Find the corresponding ranges in File0 (from the blocks
 *	    in diff02; line per line outside of diffs) and in File1.
 *	    Create a diff3_block, reserving space as indicated by the ranges.
 *
 *	 3) Copy all of the pointers for file2 in.  At least for now,
 *	    do memcmp's between corresponding strings in the two diffs.
 *
 *	 4) Copy all of the pointers for file0 and 1 in.  Get what you
 *	    need from file2 (when there isn't a diff block, it's
 *	    identical to file2 within the range between diff blocks).
 *
 *	 5) If the diff blocks you used came from only one of the two
 *	    strings of diffs, then that file (i.e. the one other than
 *	    the common file in that diff) is the odd person out.  If you used
 *	    diff blocks from both sets, check to see if files 0 and 1 match:
 *
 *		Same number of lines?  If so, do a set of memcmp's (if a
 *	    memcmp matches; copy the pointer over; it'll be easier later
 *	    if you have to do any compares).  If they match, 0 & 1 are
 *	    the same.  If not, all three different.
 *
 *   Then you do it again, until you run out of blocks.
 *
 */

/*
 * This routine makes a three way diff (chain of diff3_block's) from two
 * two way diffs (chains of diff_block's).  It is assumed that each of
 * the two diffs passed are onto the same file (i.e. that each of the
 * diffs were made "to" the same file).  The three way diff pointer
 * returned will have numbering FILE0--the other file in diff02,
 * FILE1--the other file in diff12, and FILEC--the common file.
 */
static struct diff3_block *
make_3way_diff (thread0, thread1)
     struct diff_block *thread0, *thread1;
{
/*
 * This routine works on the two diffs passed to it as threads.
 * Thread number 0 is diff02, thread number 1 is diff12.  The USING
 * array is set to the base of the list of blocks to be used to
 * construct each block of the three way diff; if no blocks from a
 * particular thread are to be used, that element of the using array
 * is set to 0.  The elements LAST_USING array are set to the last
 * elements on each of the using lists.
 *
 * The HIGH_WATER_MARK is set to the highest line number in the common file
 * described in any of the diffs in either of the USING lists.  The
 * HIGH_WATER_THREAD names the thread.  Similarly the BASE_WATER_MARK
 * and BASE_WATER_THREAD describe the lowest line number in the common file
 * described in any of the diffs in either of the USING lists.  The
 * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was
 * taken.
 *
 * The HIGH_WATER_DIFF should always be equal to LAST_USING
 * [HIGH_WATER_THREAD].  The OTHER_DIFF is the next diff to check for
 * higher water, and should always be equal to
 * CURRENT[HIGH_WATER_THREAD ^ 0x1].  The OTHER_THREAD is the thread
 * in which the OTHER_DIFF is, and hence should always be equal to
 * HIGH_WATER_THREAD ^ 0x1.
 *
 * The variable LAST_DIFF is kept set to the last diff block produced
 * by this routine, for line correspondence purposes between that diff
 * and the one currently being worked on.  It is initialized to
 * ZERO_DIFF before any blocks have been created.
 */

  struct diff_block
    *using[2],
    *last_using[2],
    *current[2];

  int
    high_water_mark;

  int
    high_water_thread,
    base_water_thread,
    other_thread;

  struct diff_block
    *high_water_diff,
    *other_diff;

  struct diff3_block
    *result,
    *tmpblock,
    **result_end;

  struct diff3_block const *last_diff3;

  static struct diff3_block const zero_diff3;

  /* Initialization */
  result = 0;
  result_end = &result;
  current[0] = thread0; current[1] = thread1;
  last_diff3 = &zero_diff3;

  /* Sniff up the threads until we reach the end */

  while (current[0] || current[1])
    {
      using[0] = using[1] = last_using[0] = last_using[1] = 0;

      /* Setup low and high water threads, diffs, and marks.  */
      if (!current[0])
	base_water_thread = 1;
      else if (!current[1])
	base_water_thread = 0;
      else
	base_water_thread =
	  (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));

      high_water_thread = base_water_thread;

      high_water_diff = current[high_water_thread];

#if 0
      /* low and high waters start off same diff */
      base_water_mark = D_LOWLINE (high_water_diff, FC);
#endif

      high_water_mark = D_HIGHLINE (high_water_diff, FC);

      /* Make the diff you just got info from into the using class */
      using[high_water_thread]
	= last_using[high_water_thread]
	= high_water_diff;
      current[high_water_thread] = high_water_diff->next;
      last_using[high_water_thread]->next = 0;

      /* And mark the other diff */
      other_thread = high_water_thread ^ 0x1;
      other_diff = current[other_thread];

      /* Shuffle up the ladder, checking the other diff to see if it
	 needs to be incorporated.  */
      while (other_diff
	     && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
	{

	  /* Incorporate this diff into the using list.  Note that
	     this doesn't take it off the current list */
	  if (using[other_thread])
	    last_using[other_thread]->next = other_diff;
	  else
	    using[other_thread] = other_diff;
	  last_using[other_thread] = other_diff;

	  /* Take it off the current list.  Note that this following
	     code assumes that other_diff enters it equal to
	     current[high_water_thread ^ 0x1] */
	  current[other_thread] = current[other_thread]->next;
	  other_diff->next = 0;

	  /* Set the high_water stuff
	     If this comparison is equal, then this is the last pass
	     through this loop; since diff blocks within a given
	     thread cannot overlap, the high_water_mark will be
	     *below* the range_start of either of the next diffs.  */

	  if (high_water_mark < D_HIGHLINE (other_diff, FC))
	    {
	      high_water_thread ^= 1;
	      high_water_diff = other_diff;
	      high_water_mark = D_HIGHLINE (other_diff, FC);
	    }

	  /* Set the other diff */
	  other_thread = high_water_thread ^ 0x1;
	  other_diff = current[other_thread];
	}

      /* The using lists contain a list of all of the blocks to be
	 included in this diff3_block.  Create it.  */

      tmpblock = using_to_diff3_block (using, last_using,
				       base_water_thread, high_water_thread,
				       last_diff3);

      if (!tmpblock)
	fatal ("internal error: screwup in format of diff blocks");

      /* Put it on the list.  */
      *result_end = tmpblock;
      result_end = &tmpblock->next;

      /* Set up corresponding lines correctly.  */
      last_diff3 = tmpblock;
    }
  return result;
}

/*
 * using_to_diff3_block:
 *   This routine takes two lists of blocks (from two separate diff
 * threads) and puts them together into one diff3 block.
 * It then returns a pointer to this diff3 block or 0 for failure.
 *
 * All arguments besides using are for the convenience of the routine;
 * they could be derived from the using array.
 * LAST_USING is a pair of pointers to the last blocks in the using
 * structure.
 * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest
 * and highest line numbers for File0.
 * last_diff3 contains the last diff produced in the calling routine.
 * This is used for lines mappings which would still be identical to
 * the state that diff ended in.
 *
 * A distinction should be made in this routine between the two diffs
 * that are part of a normal two diff block, and the three diffs that
 * are part of a diff3_block.
 */
static struct diff3_block *
using_to_diff3_block (using, last_using, low_thread, high_thread, last_diff3)
     struct diff_block
       *using[2],
       *last_using[2];
     int low_thread, high_thread;
     struct diff3_block const *last_diff3;
{
  int low[2], high[2];
  struct diff3_block *result;
  struct diff_block *ptr;
  int d, i;

  /* Find the range in the common file.  */
  int lowc = D_LOWLINE (using[low_thread], FC);
  int highc = D_HIGHLINE (last_using[high_thread], FC);

  /* Find the ranges in the other files.
     If using[d] is null, that means that the file to which that diff
     refers is equivalent to the common file over this range.  */

  for (d = 0; d < 2; d++)
    if (using[d])
      {
	low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
	high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
      }
    else
      {
	low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
	high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
      }

  /* Create a block with the appropriate sizes */
  result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);

  /* Copy information for the common file.
     Return with a zero if any of the compares failed.  */

  for (d = 0; d < 2; d++)
    for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
      {
	int result_offset = D_LOWLINE (ptr, FC) - lowc;

	if (!copy_stringlist (D_LINEARRAY (ptr, FC),
			      D_LENARRAY (ptr, FC),
			      D_LINEARRAY (result, FILEC) + result_offset,
			      D_LENARRAY (result, FILEC) + result_offset,
			      D_NUMLINES (ptr, FC)))
	  return 0;
      }

  /* Copy information for file d.  First deal with anything that might be
     before the first diff.  */

  for (d = 0; d < 2; d++)
    {
      struct diff_block *u = using[d];
      int lo = low[d], hi = high[d];

      for (i = 0;
	   i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
	   i++)
	{
	  D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
	  D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
	}

      for (ptr = u; ptr; ptr = D_NEXT (ptr))
	{
	  int result_offset = D_LOWLINE (ptr, FO) - lo;
	  int linec;

	  if (!copy_stringlist (D_LINEARRAY (ptr, FO),
				D_LENARRAY (ptr, FO),
				D_LINEARRAY (result, FILE0 + d) + result_offset,
				D_LENARRAY (result, FILE0 + d) + result_offset,
				D_NUMLINES (ptr, FO)))
	    return 0;

	  /* Catch the lines between here and the next diff */
	  linec = D_HIGHLINE (ptr, FC) + 1 - lowc;
	  for (i = D_HIGHLINE (ptr, FO) + 1 - lo;
	       i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;
	       i++)
	    {
	      D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
	      D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
	      linec++;
	    }
	}
    }

  /* Set correspond */
  if (!using[0])
    D3_TYPE (result) = DIFF_2ND;
  else if (!using[1])
    D3_TYPE (result) = DIFF_1ST;
  else
    {
      int nl0 = D_NUMLINES (result, FILE0);
      int nl1 = D_NUMLINES (result, FILE1);

      if (nl0 != nl1
	  || !compare_line_list (D_LINEARRAY (result, FILE0),
				 D_LENARRAY (result, FILE0),
				 D_LINEARRAY (result, FILE1),
				 D_LENARRAY (result, FILE1),
				 nl0))
	D3_TYPE (result) = DIFF_ALL;
      else
	D3_TYPE (result) = DIFF_3RD;
    }

  return result;
}

/*
 * This routine copies pointers from a list of strings to a different list
 * of strings.  If a spot in the second list is already filled, it
 * makes sure that it is filled with the same string; if not it
 * returns 0, the copy incomplete.
 * Upon successful completion of the copy, it returns 1.
 */
static int
copy_stringlist (fromptrs, fromlengths, toptrs, tolengths, copynum)
     char * const fromptrs[];
     char *toptrs[];
     size_t const fromlengths[];
     size_t tolengths[];
     int copynum;
{
  register char * const *f = fromptrs;
  register char **t = toptrs;
  register size_t const *fl = fromlengths;
  register size_t *tl = tolengths;

  while (copynum--)
    {
      if (*t)
	{ if (*fl != *tl || memcmp (*f, *t, *fl)) return 0; }
      else
	{ *t = *f ; *tl = *fl; }

      t++; f++; tl++; fl++;
    }
  return 1;
}

/*
 * Create a diff3_block, with ranges as specified in the arguments.
 * Allocate the arrays for the various pointers (and zero them) based
 * on the arguments passed.  Return the block as a result.
 */
static struct diff3_block *
create_diff3_block (low0, high0, low1, high1, low2, high2)
     register int low0, high0, low1, high1, low2, high2;
{
  struct diff3_block *result = ALLOCATE (1, struct diff3_block);
  int numlines;

  D3_TYPE (result) = ERROR;
  D_NEXT (result) = 0;

  /* Assign ranges */
  D_LOWLINE (result, FILE0) = low0;
  D_HIGHLINE (result, FILE0) = high0;
  D_LOWLINE (result, FILE1) = low1;
  D_HIGHLINE (result, FILE1) = high1;
  D_LOWLINE (result, FILE2) = low2;
  D_HIGHLINE (result, FILE2) = high2;

  /* Allocate and zero space */
  numlines = D_NUMLINES (result, FILE0);
  if (numlines)
    {
      D_LINEARRAY (result, FILE0) = ALLOCATE (numlines, char *);
      D_LENARRAY (result, FILE0) = ALLOCATE (numlines, size_t);
      bzero (D_LINEARRAY (result, FILE0), (numlines * sizeof (char *)));
      bzero (D_LENARRAY (result, FILE0), (numlines * sizeof (size_t)));
    }
  else
    {
      D_LINEARRAY (result, FILE0) = 0;
      D_LENARRAY (result, FILE0) = 0;
    }

  numlines = D_NUMLINES (result, FILE1);
  if (numlines)
    {
      D_LINEARRAY (result, FILE1) = ALLOCATE (numlines, char *);
      D_LENARRAY (result, FILE1) = ALLOCATE (numlines, size_t);
      bzero (D_LINEARRAY (result, FILE1), (numlines * sizeof (char *)));
      bzero (D_LENARRAY (result, FILE1), (numlines * sizeof (size_t)));
    }
  else
    {
      D_LINEARRAY (result, FILE1) = 0;
      D_LENARRAY (result, FILE1) = 0;
    }

  numlines = D_NUMLINES (result, FILE2);