static intcompare (register const struct line *a, register const struct line *b){  int diff;  size_t alen, blen;  /* 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 (keylist)    {      diff = keycompare (a, b);      alloca (0);      if (diff != 0 || unique || stable)	return diff;    }  /* If the keys all compare equal (or no keys were specified)     fall through to the default comparison.  */  alen = a->length - 1, blen = b->length - 1;  if (alen == 0)    diff = - NONZERO (blen);  else if (blen == 0)    diff = NONZERO (alen);  else if (HAVE_SETLOCALE && hard_LC_COLLATE)    diff = xmemcoll (a->text, alen, b->text, blen);  else if (! (diff = memcmp (a->text, b->text, min (alen, blen))))    diff = alen < blen ? -1 : alen != blen;  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   one if they are not in order.  Otherwise, print no diagnostic   and return zero.  */static intcheckfp (FILE *fp, char *file_name){  struct buffer buf;		/* Input buffer. */  struct line temp;		/* Copy of previous line. */  size_t alloc = 0;  uintmax_t line_number = 0;  struct keyfield *key = keylist;  int nonunique = 1 - unique;  int disordered = 0;  initbuf (&buf, sizeof (struct line),	   MAX (merge_buffer_size, sort_size));  temp.text = NULL;  while (fillbuf (&buf, fp, file_name))    {      struct line const *line = buffer_linelim (&buf);      struct line const *linebase = line - buf.nlines;      /* Make sure the line saved from the old buffer contents is	 less than or equal to the first line of the new buffer. */      if (alloc && nonunique <= compare (&temp, line - 1))	{	found_disorder:	  {	    struct line const *disorder_line = line - 1;	    uintmax_t disorder_line_number =	      buffer_linelim (&buf) - disorder_line + line_number;	    char hr_buf[INT_BUFSIZE_BOUND (uintmax_t)];	    fprintf (stderr, _("%s: %s:%s: disorder: "),		     program_name, file_name,		     umaxtostr (disorder_line_number, hr_buf));	    write_bytes (disorder_line->text, disorder_line->length, stderr,			 _("standard error"));	    disordered = 1;	    break;	  }	}      /* Compare each line in the buffer with its successor.  */      while (linebase < --line)	if (nonunique <= compare (line, line - 1))	  goto found_disorder;      line_number += buf.nlines;      /* Save the last line of the buffer.  */      if (alloc < line->length)	{	  do	    {	      alloc *= 2;	      if (! alloc)		{		  alloc = line->length;		  break;		}	    }	  while (alloc < line->length);	  temp.text = xrealloc (temp.text, alloc);	}      memcpy (temp.text, line->text, line->length);      temp.length = line->length;      if (key)	{	  temp.keybeg = temp.text + (line->keybeg - line->text);	  temp.keylim = temp.text + (line->keylim - line->text);	}    }  xfclose (fp, file_name);  free (buf.buf);  if (temp.text)    free (temp.text);  return disordered;}/* Merge lines from FILES onto OFP.  NFILES cannot be greater than   NMERGE.  Close input and output files before returning.   OUTPUT_FILE gives the name of the output file; if OFP is NULL, the   output file has not been opened yet.  */static voidmergefps (char **files, register int nfiles,	  FILE *ofp, const char *output_file){  FILE *fps[NMERGE];		/* Input streams for each file.  */  struct buffer buffer[NMERGE];	/* Input buffers for each file. */  struct line saved;		/* Saved line storage for unique check. */  struct line const *savedline = NULL;				/* &saved if there is a saved line. */  size_t savealloc = 0;		/* Size allocated for the saved line. */  struct line const *cur[NMERGE]; /* Current line in each line table. */  struct line const *base[NMERGE]; /* Base of each line table.  */  int ord[NMERGE];		/* Table representing a permutation of fps,				   such that cur[ord[0]] is the smallest line				   and will be next output. */  register int i, j, t;  struct keyfield *key = keylist;  saved.text = NULL;  /* Read initial lines from each input file. */  for (i = 0; i < nfiles; )    {      fps[i] = xfopen (files[i], "r");      initbuf (&buffer[i], sizeof (struct line),	       MAX (merge_buffer_size, sort_size / nfiles));      if (fillbuf (&buffer[i], fps[i], files[i]))	{	  struct line const *linelim = buffer_linelim (&buffer[i]);	  cur[i] = linelim - 1;	  base[i] = linelim - buffer[i].nlines;	  i++;	}      else	{	  /* fps[i] is empty; eliminate it from future consideration.  */	  xfclose (fps[i], files[i]);	  zaptemp (files[i]);	  free (buffer[i].buf);	  --nfiles;	  for (j = i; j < nfiles; ++j)	    files[j] = files[j + 1];	}    }  if (! ofp)    ofp = xfopen (output_file, "w");  /* 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 < nfiles; ++i)    ord[i] = i;  for (i = 1; i < nfiles; ++i)    if (0 < compare (cur[ord[i - 1]], cur[ord[i]]))      t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;  /* Repeatedly output the smallest line until no input remains. */  while (nfiles)    {      struct line const *smallest = cur[ord[0]];      /* If uniquified output is turned on, output only the first of	 an identical series of lines. */      if (unique)	{	  if (savedline && compare (savedline, smallest))	    {	      savedline = 0;	      write_bytes (saved.text, saved.length, ofp, output_file);	    }	  if (!savedline)	    {	      savedline = &saved;	      if (savealloc < smallest->length)		{		  do		    if (! savealloc)		      {			savealloc = smallest->length;			break;		      }		  while ((savealloc *= 2) < smallest->length);		  saved.text = xrealloc (saved.text, savealloc);		}	      saved.length = smallest->length;	      memcpy (saved.text, smallest->text, saved.length);	      if (key)		{		  saved.keybeg =		    saved.text + (smallest->keybeg - smallest->text);		  saved.keylim =		    saved.text + (smallest->keylim - smallest->text);		}	    }	}      else	write_bytes (smallest->text, smallest->length, ofp, output_file);      /* Check if we need to read more lines into core. */      if (base[ord[0]] < smallest)	cur[ord[0]] = smallest - 1;      else	{	  if (fillbuf (&buffer[ord[0]], fps[ord[0]], files[ord[0]]))	    {	      struct line const *linelim = buffer_linelim (&buffer[ord[0]]);	      cur[ord[0]] = linelim - 1;	      base[ord[0]] = linelim - buffer[ord[0]].nlines;	    }	  else	    {	      /* We reached EOF on fps[ord[0]]. */	      for (i = 1; i < nfiles; ++i)		if (ord[i] > ord[0])		  --ord[i];	      --nfiles;	      xfclose (fps[ord[0]], files[ord[0]]);	      zaptemp (files[ord[0]]);	      free (buffer[ord[0]].buf);	      for (i = ord[0]; i < nfiles; ++i)		{		  fps[i] = fps[i + 1];		  files[i] = files[i + 1];		  buffer[i] = buffer[i + 1];		  cur[i] = cur[i + 1];		  base[i] = base[i + 1];		}	      for (i = 0; i < nfiles; ++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 < nfiles; ++i)	{	  t = compare (cur[ord[0]], 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 && savedline)    {      write_bytes (saved.text, saved.length, ofp, output_file);      free (saved.text);    }  xfclose (ofp, output_file);}/* Sort the array LINES with NLINES members, using TEMP for temporary space.   The input and output arrays are in reverse order, and LINES and   TEMP point just past the end of their respective arrays.  */static voidsortlines (struct line *lines, size_t nlines, struct line *temp){  register struct line *lo, *hi, *t;  register size_t nlo, nhi;  if (nlines == 2)    {      if (0 < compare (&lines[-1], &lines[-2]))	{	  struct line tmp = lines[-1];	  lines[-1] = lines[-2];	  lines[-2] = tmp;	}      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 - 1, hi - 1) <= 0)      *--t = *--lo, --nlo;    else      *--t = *--hi, --nhi;  while (nlo--)    *--t = *--lo;  for (lo = lines, nlo = nlines - nhi, t = temp; nlo; --nlo)    *--lo = *--t;}/* Return the index of the first of NFILES FILES that is the same file   as OUTFILE.  If none can be the same, return NFILES.  Consider an   input pipe to be the same as OUTFILE, since the pipe might be the   output of a command like "cat OUTFILE".  */static intfirst_same_file (char **files, int nfiles, char const *outfile){  int i;  int got_outstat = 0;  struct stat instat, outstat;  for (i = 0; i < nfiles; i++)    {      int standard_input = STREQ (files[i], "-");      if (STREQ (outfile, files[i]) && ! standard_input)	return i;      if (! got_outstat)	{	  got_outstat = 1;	  if ((STREQ (outfile, "-")	       ? fstat (STDOUT_FILENO, &outstat)	       : stat (outfile, &outstat))	      != 0)	    return nfiles;	}      if (((standard_input	    ? fstat (STDIN_FILENO, &instat)	    : stat (files[i], &instat))	   == 0)	  && (S_ISFIFO (instat.st_mode) || SAME_INODE (instat, outstat)))	return i;    }  return nfiles;}/* Check that each of the NFILES FILES is ordered.   Return a count of disordered files. */static intcheck (char **files, int nfiles){  int i, disorders = 0;  FILE *fp;  for (i = 0; i < nfiles; ++i)    {      fp = xfopen (files[i], "r");      disorders += checkfp (fp, files[i]);    }  return disorders;}/* Merge NFILES FILES onto OUTPUT_FILE.  However, merge at most   MAX_MERGE input files directly onto OUTPUT_FILE.  MAX_MERGE cannot   exceed NMERGE.  */static voidmerge (char **files, int nfiles, int max_merge, char const *output_file){  while (max_merge < nfiles)    {      FILE *tfp;      int i, t = 0;      char *temp;      for (i = 0; i < nfiles / NMERGE; ++i)	{	  temp = create_temp_file (&tfp);	  mergefps (&files[i * NMERGE], NMERGE, tfp, temp);	  files[t++] = temp;	}      temp = create_temp_file (&tfp);      mergefps (&files[i * NMERGE], nfiles % NMERGE, tfp, temp);      files[t++] = temp;      nfiles = t;      if (nfiles == 1)	break;    }  mergefps (files, nfiles, NULL, output_file);}/* Sort NFILES FILES onto OUTPUT_FILE. */static voidsort (char **files, int nfiles, char const *output_file){  struct buffer buf;  int n_temp_files = 0;  int output_file_created = 0;  static size_t size;  if (! size && ! (size = sort_size))    size = default_sort_size ();  buf.alloc = 0;  while (nfiles)    {      char const *temp_output;      char const *file = *files;      FILE *fp = xfopen (file, "r");      FILE *tfp;      if (! buf.alloc)	initbuf (&buf, 2 * sizeof (struct line),		 sort_buffer_size (&fp, 1, files, nfiles,				   2 * sizeof (struct line), size));      buf.eof = 0;      files++;      nfiles--;      while (fillbuf (&buf, fp, file))	{	  struct line *line;	  struct line *linebase;	  if (buf.eof && nfiles	      && (2 * sizeof (struct line) + 1		  < (buf.alloc - buf.used		     - 2 * sizeof (struct line) * buf.nlines)))	    {	      /* End of file, but there is more input and buffer room.		 Concatenate the next input file; this is faster in		 the usual case.  */	      buf.left = buf.used;	      break;	    }	  line = buffer_linelim (&buf);	  linebase = line - buf.nlines;	  sortlines (line, buf.nlines, linebase);	  if (buf.eof && !nfiles && !n_temp_files && !buf.left)	    {	      xfclose (fp, file);	      tfp = xfopen (output_file, "w");	      temp_output = output_file;	      output_file_created = 1;	    }	  else	    {	      ++n_temp_files;	      temp_output = create_temp_file (&tfp);	    }	  do	    {	      line--;	      write_bytes (line->text, line->length, tfp, temp_output);	      if (unique)		while (linebase < line && compare (line, line - 1) == 0)		  line--;	    }	  while (linebase < line);	  xfclose (tfp, temp_output);	  if (output_file_created)	    goto finish;	}      xfclose (fp, file);    } finish:  free (buf.buf);  if (! output_file_created)