sort.c

代码检索工具GLOBAL源码。可用来浏览分析LINUX源码。

	      /* Ignore and/or translate chars before comparing.  */
	      for (new_len_a = new_len_b = i = 0; i < max (lena, lenb); i++)
		{
		  if (i < lena)
		    {
		      copy_a[new_len_a] = (translate
					   ? translate[UCHAR (texta[i])]
					   : texta[i]);
		      if (!ignore || !ignore[UCHAR (texta[i])])
			++new_len_a;
		    }
		  if (i < lenb)
		    {
		      copy_b[new_len_b] = (translate
					   ? translate[UCHAR (textb[i])]
					   : textb [i]);
		      if (!ignore || !ignore[UCHAR (textb[i])])
			++new_len_b;
		    }
		}

	      diff = memcoll (copy_a, new_len_a, copy_b, new_len_b);
	    }
	  else
	    {
	      diff = memcoll (texta, lena, textb, lenb);
	    }

	  if (diff)
	    return key->reverse ? -diff : diff;

	  continue;
	}
#endif
      else if (ignore && translate)

#define CMP_WITH_IGNORE(A, B)						\
  do									\
    {									\
	  while (texta < lima && textb < limb)				\
	    {								\
	      while (texta < lima && ignore[UCHAR (*texta)])		\
		++texta;						\
	      while (textb < limb && ignore[UCHAR (*textb)])		\
		++textb;						\
	      if (texta < lima && textb < limb)				\
		{							\
		  if ((A) != (B))					\
		    {							\
		      diff = UCHAR (A) - UCHAR (B);	      		\
		      break;						\
		    }							\
		  ++texta;						\
		  ++textb;						\
		}							\
									\
	      if (texta == lima && textb < limb && !ignore[UCHAR (*textb)]) \
		diff = -1;						\
	      else if (texta < lima && textb == limb			\
		       && !ignore[UCHAR (*texta)])			\
		diff = 1;						\
	    }								\
									\
	  if (diff == 0)						\
	    {								\
	      while (texta < lima && ignore[UCHAR (*texta)])		\
		++texta;						\
	      while (textb < limb && ignore[UCHAR (*textb)])		\
		++textb;						\
									\
	      if (texta == lima && textb < limb)			\
		diff = -1;						\
	      else if (texta < lima && textb == limb)			\
		diff = 1;						\
	    }								\
	  /* Relative lengths are meaningless if characters were ignored.  \
	     Handling this case here avoids what might be an invalid length  \
	     comparison below.  */					\
	  if (diff == 0 && texta == lima && textb == limb)		\
	    comparable_lengths = 0;					\
    }									\
  while (0)

	CMP_WITH_IGNORE (translate[UCHAR (*texta)], translate[UCHAR (*textb)]);
      else if (ignore)
	CMP_WITH_IGNORE (UCHAR (*texta), UCHAR (*textb));
      else if (translate)
	while (texta < lima && textb < limb)
	  {
	    if (translate[UCHAR (*texta++)] != translate[UCHAR (*textb++)])
	      {
		diff = (UCHAR (translate[UCHAR (*--texta)])
			- UCHAR (translate[UCHAR (*--textb)]));
		break;
	      }
	  }
      else
	{
#ifdef ENABLE_NLS
	  if (hard_LC_COLLATE)
	    {
	      /* Ignore any length difference if the localized comparison
		 says the strings are equal.  */
	      comparable_lengths = 0;
	      diff = memcoll (texta, lena, textb, lenb);
	    }
	  else
#endif
	    {
	      diff = memcmp (texta, textb, min (lena, lenb));
	    }
	}

      if (diff)
	return key->reverse ? -diff : diff;
      if (comparable_lengths && (diff = lena - lenb) != 0)
	return key->reverse ? -diff : diff;
    }

  return 0;
}

/* Compare two lines A and B, returning negative, zero, or positive
   depending on whether A compares less than, equal to, or greater than B. */

static int
compare (register const struct line *a, register const struct line *b)
{
  int diff, tmpa, tmpb;

  /* First try to compare on the specified keys (if any).
     The only two cases with no key at all are unadorned sort,
     and unadorned sort -r. */
  if (keyhead.next)
    {
      diff = keycompare (a, b);
      if (diff != 0 || unique || stable)
	{
	  alloca (0);
	  return diff;
	}
    }

  /* If the keys all compare equal (or no keys were specified)
     fall through to the default byte-by-byte comparison. */
  tmpa = a->length, tmpb = b->length;

#ifdef ENABLE_NLS
  if (hard_LC_COLLATE)
    {
      diff = memcoll (a->text, tmpa, b->text, tmpb);
      alloca (0);
      return reverse ? -diff : diff;
    }
#endif

  diff = UCHAR (a->text[0]) - UCHAR (b->text[0]);
  if (diff == 0)
    {
      diff = memcmp (a->text, b->text, min (tmpa, tmpb));
      if (diff == 0)
	diff = tmpa - tmpb;
    }

  return reverse ? -diff : diff;
}

/* Check that the lines read from the given FP come in order.  Print a
   diagnostic (FILE_NAME, line number, contents of line) to stderr and return
   the line number of the first out-of-order line (counting from 1) if they
   are not in order.  Otherwise, print no diagnostic and return zero.  */

static int
checkfp (FILE *fp, const char *file_name)
{
  struct buffer buf;		/* Input buffer. */
  struct lines lines;		/* Lines scanned from the buffer. */
  struct line temp;		/* Copy of previous line. */
  int cc;			/* Character count. */
  int alloc;
  int line_number = 1;
  struct line *disorder_line = NULL;
  int disorder_line_number = 0;

#ifdef lint  /* Suppress `used before initialized' warning.  */
  disorder_line = NULL;
#endif

  initbuf (&buf, mergealloc);
  initlines (&lines, mergealloc / linelength + 1,
	     LINEALLOC / ((NMERGE + NMERGE) * sizeof (struct line)));
  alloc = linelength;
  temp.text = xmalloc (alloc);

  cc = fillbuf (&buf, fp);
  if (cc == 0)
    goto finish;

  findlines (&buf, &lines);

  while (1)
    {
      struct line *prev_line;	/* Pointer to previous line. */
      int cmp;			/* Result of calling compare. */
      int i;

      /* Compare each line in the buffer with its successor. */
      for (i = 0; i < lines.used - 1; ++i)
	{
	  cmp = compare (&lines.lines[i], &lines.lines[i + 1]);
	  if ((unique && cmp >= 0) || (cmp > 0))
	    {
	      disorder_line = &lines.lines[i + 1];
	      disorder_line_number = line_number + i + 1;
	      goto finish;
	    }
	}

      line_number += lines.used;

      /* Save the last line of the buffer and refill the buffer. */
      prev_line = lines.lines + (lines.used - 1);
      if (prev_line->length + 1 > alloc)
	{
	  do
	    {
	      alloc *= 2;
	    }
	  while (alloc < prev_line->length + 1);
	  temp.text = xrealloc (temp.text, alloc);
	}
      assert (prev_line->length + 1 <= alloc);
      memcpy (temp.text, prev_line->text, prev_line->length);
      temp.length = prev_line->length;
      temp.keybeg = temp.text + (prev_line->keybeg - prev_line->text);
      temp.keylim = temp.text + (prev_line->keylim - prev_line->text);

      cc = fillbuf (&buf, fp);
      if (cc == 0)
        break;

      findlines (&buf, &lines);
      /* Make sure the line saved from the old buffer contents is
	 less than or equal to the first line of the new buffer. */
      cmp = compare (&temp, &lines.lines[0]);
      if ((unique && cmp >= 0) || (cmp > 0))
	{
	  disorder_line = &lines.lines[0];
	  disorder_line_number = line_number;
	  break;
	}
    }

finish:
  xfclose (fp);

  if (disorder_line_number)
    {
      fprintf (stderr, _("%s: %s:%d: disorder: "), program_name, file_name,
	       disorder_line_number);
      write_bytes (disorder_line->text, disorder_line->length, stderr,
		   _("standard error"));
    }

  free (buf.buf);
  free ((char *) lines.lines);
  free (temp.text);
  return disorder_line_number;
}

/* Merge lines from FPS onto OFP.  NFPS cannot be greater than NMERGE.
   Close FPS before returning. */

static void
mergefps (FILE **fps, register int nfps, FILE *ofp, const char *output_file)
{
  struct buffer buffer[NMERGE];	/* Input buffers for each file. */
  struct lines lines[NMERGE];	/* Line tables for each buffer. */
  struct line saved;		/* Saved line for unique check. */
  int savedflag = 0;		/* True if there is a saved line. */
  int savealloc = 0;		/* Size allocated for the saved line. */
  int cur[NMERGE];		/* Current line in each line table. */
  int ord[NMERGE];		/* Table representing a permutation of fps,
				   such that lines[ord[0]].lines[cur[ord[0]]]
				   is the smallest line and will be next
				   output. */
  register int i, j, t;

#ifdef lint  /* Suppress `used before initialized' warning.  */
  savealloc = 0;
#endif

  /* Allocate space for a saved line if necessary. */
  if (unique)
    {
      savealloc = linelength;
      saved.text = xmalloc (savealloc);
    }

  /* Read initial lines from each input file. */
  for (i = 0; i < nfps; ++i)
    {
      initbuf (&buffer[i], mergealloc);
      /* If a file is empty, eliminate it from future consideration. */
      while (i < nfps && !fillbuf (&buffer[i], fps[i]))
	{
	  xfclose (fps[i]);
	  --nfps;
	  for (j = i; j < nfps; ++j)
	    fps[j] = fps[j + 1];
	}
      if (i == nfps)
	free (buffer[i].buf);
      else
	{
	  initlines (&lines[i], mergealloc / linelength + 1,
		     LINEALLOC / ((NMERGE + NMERGE) * sizeof (struct line)));
	  findlines (&buffer[i], &lines[i]);
	  cur[i] = 0;
	}
    }

  /* Set up the ord table according to comparisons among input lines.
     Since this only reorders two items if one is strictly greater than
     the other, it is stable. */
  for (i = 0; i < nfps; ++i)
    ord[i] = i;
  for (i = 1; i < nfps; ++i)
    if (compare (&lines[ord[i - 1]].lines[cur[ord[i - 1]]],
		 &lines[ord[i]].lines[cur[ord[i]]]) > 0)
      t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;

  /* Repeatedly output the smallest line until no input remains. */
  while (nfps)
    {
      /* If uniquified output is turned on, output only the first of
	 an identical series of lines. */
      if (unique)
	{
	  if (savedflag && compare (&saved, &lines[ord[0]].lines[cur[ord[0]]]))
	    {
	      write_bytes (saved.text, saved.length, ofp, output_file);
	      savedflag = 0;
	    }
	  if (!savedflag)
	    {
	      if (savealloc < lines[ord[0]].lines[cur[ord[0]]].length + 1)
		{
		  while (savealloc < lines[ord[0]].lines[cur[ord[0]]].length + 1)
		    savealloc *= 2;
		  saved.text = xrealloc (saved.text, savealloc);
		}
	      saved.length = lines[ord[0]].lines[cur[ord[0]]].length;
	      memcpy (saved.text, lines[ord[0]].lines[cur[ord[0]]].text,
		      saved.length);
	      if (lines[ord[0]].lines[cur[ord[0]]].keybeg != NULL)
		{
		  saved.keybeg = saved.text +
		    (lines[ord[0]].lines[cur[ord[0]]].keybeg
		     - lines[ord[0]].lines[cur[ord[0]]].text);
		}
	      if (lines[ord[0]].lines[cur[ord[0]]].keylim != NULL)
		{
		  saved.keylim = saved.text +
		    (lines[ord[0]].lines[cur[ord[0]]].keylim
		     - lines[ord[0]].lines[cur[ord[0]]].text);
		}
	      savedflag = 1;
	    }
	}
      else
	write_bytes (lines[ord[0]].lines[cur[ord[0]]].text,
		     lines[ord[0]].lines[cur[ord[0]]].length, ofp, output_file);

      /* Check if we need to read more lines into core. */
      if (++cur[ord[0]] == lines[ord[0]].used)
	{
	  if (fillbuf (&buffer[ord[0]], fps[ord[0]]))
	    {
	      findlines (&buffer[ord[0]], &lines[ord[0]]);
	      cur[ord[0]] = 0;
	    }
	  else
	    {
	      /* We reached EOF on fps[ord[0]]. */
	      for (i = 1; i < nfps; ++i)
		if (ord[i] > ord[0])
		  --ord[i];
	      --nfps;
	      xfclose (fps[ord[0]]);
	      free (buffer[ord[0]].buf);
	      free ((char *) lines[ord[0]].lines);
	      for (i = ord[0]; i < nfps; ++i)
		{
		  fps[i] = fps[i + 1];
		  buffer[i] = buffer[i + 1];
		  lines[i] = lines[i + 1];
		  cur[i] = cur[i + 1];
		}
	      for (i = 0; i < nfps; ++i)
		ord[i] = ord[i + 1];
	      continue;
	    }
	}

      /* The new line just read in may be larger than other lines
	 already in core; push it back in the queue until we encounter
	 a line larger than it. */
      for (i = 1; i < nfps; ++i)
	{
	  t = compare (&lines[ord[0]].lines[cur[ord[0]]],
		       &lines[ord[i]].lines[cur[ord[i]]]);
	  if (!t)
	    t = ord[0] - ord[i];
	  if (t < 0)
	    break;
	}
      t = ord[0];
      for (j = 1; j < i; ++j)
	ord[j - 1] = ord[j];
      ord[i - 1] = t;
    }

  if (unique && savedflag)
    {
      write_bytes (saved.text, saved.length, ofp, output_file);
      free (saved.text);
    }
}

/* Sort the array LINES with NLINES members, using TEMP for temporary space. */

static void
sortlines (struct line *lines, int nlines, struct line *temp)
{
  register struct line *lo, *hi, *t;
  register int nlo, nhi;

  if (nlines == 2)
    {
      if (compare (&lines[0], &lines[1]) > 0)
	{
	  *temp = lines[0];
	  lines[0] = lines[1];
	  lines[1] = *temp;
	}
      return;
    }

  nlo = nlines / 2;
  lo = lines;
  nhi = nlines - nlo;
  hi = lines + nlo;

  if (nlo > 1)
    sortlines (lo, nlo, temp);

  if (nhi > 1)
    sortlines (hi, nhi, temp);

  t = temp;

  while (nlo && nhi)
    if (compare (lo, hi) <= 0)
      *t++ = *lo++, --nlo;
    else
      *t++ = *hi++, --nhi;
  while (nlo--)
    *t++ = *lo++;

  for (lo = lines, nlo = nlines - nhi, t = temp; nlo; --nlo)
    *lo++ = *t++;
}

/* Check that each of the NFILES FILES is ordered.
   Return a count of disordered files. */

static int
check (char **files, int nfiles)
{
  int i, disorders = 0;
  FILE *fp;

  for (i = 0; i < nfiles; ++i)
    {
      fp = xfopen (files[i], "r");
      if (checkfp (fp, files[i]))
	{
	  ++disorders;
	}
    }
  return disorders;
}

/* Merge NFILES FILES onto OFP. */

static void
merge (char **files, int nfiles, FILE *ofp, const char *output_file)
{
  int i, j, t;
  char *temp;
  FILE *fps[NMERGE], *tfp;

  while (nfiles > NMERGE)
    {
      t = 0;
      for (i = 0; i < nfiles / NMERGE; ++i)
	{
	  for (j = 0; j < NMERGE; ++j)
	    fps[j] = xfopen (files[i * NMERGE + j], "r");
	  tfp = xtmpfopen (temp = tempname ());
	  mergefps (fps, NMERGE, tfp, temp);
	  xfclose (tfp);
	  for (j = 0; j < NMERGE; ++j)
	    zaptemp (files[i * NMERGE + j]);
	  files[t++] = temp;
	}
      for (j = 0; j < nfiles % NMERGE; ++j)
	fps[j] = xfopen (files[i * NMERGE + j], "r");
      tfp = xtmpfopen (temp = tempname ());
      mergefps (fps, nfiles % NMERGE, tfp, temp);
      xfclose (tfp);
      for (j = 0; j < nfiles % NMERGE; ++j)
	zaptemp (files[i * NMERGE + j]);
      files[t++] = temp;
      nfiles = t;
    }

  for (i = 0; i < nfiles; ++i)
    fps[i] = xfopen (files[i], "r");
  mergefps (fps, i, ofp, output_file);
  for (i = 0; i < nfiles; ++i)
    zaptemp (files[i]);
}

/* Sort NFILES FILES onto OFP. */

static void
sort (char **files, int nfiles, FILE *ofp, const char *output_file)
{
  struct buffer buf;
  struct lines lines;
  struct line *tmp;
  int i, ntmp;
  FILE *fp, *tfp;
  struct tempnode *node;
  int n_temp_files = 0;
  char **tempfiles;

  initbuf (&buf, sortalloc);
  initlines (&lines, sortalloc / linelength + 1,
	     LINEALLOC / sizeof (struct line));
  ntmp = lines.alloc;
  tmp = (struct line *) xmalloc (ntmp * sizeof (struct line));

  while (nfiles--)
    {
      const char *temp_output;

      fp = xfopen (*files++, "r");
      while (fillbuf (&buf, fp))
	{
	  findlines (&buf, &lines);
	  if (lines.used > ntmp)
	    {
	      while (lines.used > ntmp)
		ntmp *= 2;
	      tmp = (struct line *)
		xrealloc ((char *) tmp, ntmp * sizeof (struct line));
	    }
	  sortlines (lines.lines, lines.used, tmp);
	  if (feof (fp) && !nfiles && !n_temp_files && !buf.left)
	    {
	      tfp = ofp;
	      temp_output = output_file;
	    }
	  else
	    {
	      ++n_temp_files;
	      tfp = xtmpfopen (temp_output = tempname ());
	    }
	  for (i = 0; i < lines.used; ++i)
	    if (!unique || i == 0
		|| compare (&lines.lines[i], &lines.lines[i - 1]))
	      write_bytes (lines.lines[i].text, lines.lines[i].length, tfp,
			   temp_output);
	  if (tfp != ofp)
	    xfclose (tfp);
	}
      xfclose (fp);
    }

  free (buf.buf);
  free ((char *) lines.lines);
  free ((char *) tmp);

  if (n_temp_files)
    {
      tempfiles = (char **) xmalloc (n_temp_files * sizeof (char *));