sort.c

操作系统源代码

			} while ((table[*el2] & DICT) == 0);
			continue;
		}
	}
	if (field->fold_case) {	/* Fold upper case to lower */
		if (table[c1 = *el1++] & UPPER) c1 += 'a' - 'A';
		if (table[c2 = *el2++] & UPPER) c2 += 'a' - 'A';
		if (c1 == c2) continue;
		return c1 - c2;
	}
	return *el1 - *el2;
  }

  /* NOTREACHED */
}

/*
 * Digits compares () the two strings that point to a number of digits followed
 * by an optional decimal point.
 */
int digits(str1, str2, check_sign)
register char *str1, *str2;
BOOL check_sign;		/* True if sign must be checked */
{
  BOOL negative = FALSE;	/* True if negative numbers */
  int diff, pow, ret;

/* Check for optional minus or plus sign */
  if (check_sign) {
	if (*str1 == '-') {
		negative = TRUE;
		str1++;
	} else if (*str1 == '+')
		str1++;

	if (*str2 == '-') {
		if (negative == FALSE) return HIGHER;
		str2++;
	} else if (negative)
		return LOWER;
	else if (*str2 == '+')
		str2++;
  }

/* Keep incrementing as long as digits are available and equal */
  while ((table[*str1] & DIGIT) && table[*str2] & DIGIT) {
	if (*str1 != *str2) break;
	str1++;
	str2++;
  }

/* First check for the decimal point. */
  if (*str1 == '.' || *str2 == '.') {
	if (*str1 == '.') {
		if (*str2 == '.')	/* Both. Check decimal part */
			ret = digits(str1 + 1, str2 + 1, FALSE);
		else
			ret = (table[*str2] & DIGIT) ? LOWER : HIGHER;
	} else
		ret = (table[*str1] & DIGIT) ? HIGHER : LOWER;
  }

/* Now either two digits differ, or unknown char is seen (e.g. end of string) */
  else if ((table[*str1] & DIGIT) && (table[*str2] & DIGIT)) {
	diff = *str1 - *str2;	/* Basic difference */
	pow = 0;		/* Check power of numbers */
	while (table[*str1++] & DIGIT) pow++;
	while (table[*str2++] & DIGIT) pow--;
	ret = (pow == 0) ? diff : pow;
  }

/* Unknown char. Check on which string it occurred */
  else {
	if ((table[*str1] & DIGIT) == 0)
		ret = (table[*str2] & DIGIT) ? LOWER : SAME;
	else
		ret = HIGHER;
  }

/* Reverse sense of comparisons if negative is true. (-1000 < -1) */
  return(negative) ? -ret : ret;
}

/* Files_merge () merges all files as indicated by nr_of_files. Merging goes
 * in numbers of files that can be opened at the same time. (OPEN_FILES)
 */
void files_merge(file_cnt)
register int file_cnt;		/* Nr_of_files to merge */
{
  register int i;
  int limit;

  for (i = 0; i < file_cnt; i += OPEN_FILES) {
	/* Merge last files and store in output file */
	if ((limit = i + OPEN_FILES) >= file_cnt) {
		open_outfile();
		limit = file_cnt;
	} else {		/* Merge OPEN_FILES files and store in temp
			 * file */
		temp_files[16] = file_cnt / 26 + 'a';
		temp_files[17] = file_cnt % 26 + 'a';
		if ((out_fd = creat(temp_files, 0644)) < 0)
			error(TRUE, "Cannot creat ", temp_files);
		file_cnt++;
	}
	merge(i, limit);
  }

/* Cleanup mess */
  i = (only_merge) ? args_limit - args_offset : 0;
  while (i < file_cnt) (void) unlink(file_name(i++));
}

/* Merge () merges the files between start_file and limit_file. */
void merge(start_file, limit_file)
int start_file, limit_file;
{
  register MERGE *smallest;	/* Keeps track of smallest line */
  register int i;
  int file_cnt = limit_file - start_file;	/* Nr of files to merge */

/* Calculate size in core available for file_cnt merge structs */
  buf_size = MEMORY_SIZE / file_cnt - LINE_SIZE;

  mbrk(mem_top);		/* First reset mem to lowest loc. */
  disabled = 0;			/* All files not done yet */

/* Set up merge structures. */
  for (i = start_file; i < limit_file; i++) {
	smallest = &merge_f[i - start_file];
	if (!strcmp(file_name(i), "-"))	/* File is stdin */
		smallest->fd = 0;
	else if ((smallest->fd = open(file_name(i), O_RDONLY)) < 0) {
		smallest->fd = ERROR;
		error(FALSE, "Cannot open ", file_name(i));
		disabled++;	/* Done this file */
		continue;
	}
	smallest->buffer = msbrk(buf_size);
	smallest->line = msbrk(LINE_SIZE);
	smallest->cnt = smallest->read_chars = 0;
	(void) read_line(smallest);	/* Read first line */
  }

  if (disabled == file_cnt) {	/* Couldn't open files */
	(void) close(out_fd);
	return;
  }

/* Find a merg struct to assign smallest. */
  for (i = 0; i < file_cnt; i++) {
	if (merge_f[i].fd != ERROR) {
		smallest = &merge_f[i];
		break;
	}
  }

/* Loop until all files minus one are done */
  while (disabled < file_cnt - 1) {
	if (uniq)		/* Skip all same lines */
		smallest = skip_lines(smallest, file_cnt);
	else {			/* Find smallest line */
		for (i = 0; i < file_cnt; i++) {
			if (merge_f[i].fd == ERROR)
				continue;	/* We've had this one */
			if (compare(merge_f[i].line, smallest->line) < 0)
				smallest = &merge_f[i];
		}
	}			/* Print line and read next */
	smallest = print(smallest, file_cnt);
  }

  if (only_merge && uniq)
	uniq_lines(smallest);	/* Print only uniq lines */
  else				/* Print rest of file */
	while (print(smallest, file_cnt) != NIL_MERGE);

  put_line(NIL_PTR);		/* Flush output buffer */
}

/* Put_line () prints the line into the out_fd filedescriptor. If line equals
 * NIL_PTR, the out_fd is flushed and closed.
 */
void put_line(line)
register char *line;
{
  static int index = 0;		/* Index in out_buffer */

  if (line == NIL_PTR) {	/* Flush and close */
	mwrite(out_fd, out_buffer, index);
	index = 0;
	(void) close(out_fd);
	return;
  }
  do {				/* Fill out_buffer with line */
	out_buffer[index++] = *line;
	if (index == IO_SIZE) {
		mwrite(out_fd, out_buffer, IO_SIZE);
		index = 0;
	}
  } while (*line++ != '\n');
}

/*
 * Print () prints the line of the merg structure and tries to read another one.
 * If this fails, it returns the next merg structure which file_descriptor is
 * still open. If none could be found, a NIL structure is returned.
 */
MERGE *print(merg, file_cnt)
register MERGE *merg;
int file_cnt;			/* Nr of files that are being merged */
{
  register int i;

  put_line(merg->line);		/* Print the line */

  if (read_line(merg) == ERROR) {	/* Read next line */
	for (i = 0; i < file_cnt; i++) {
		if (merge_f[i].fd != ERROR) {
			merg = &merge_f[i];
			break;
		}
	}
	if (i == file_cnt)	/* No more files left */
		return NIL_MERGE;
  }
  return merg;
}

/* Read_line () reads a line from the fd from the merg struct. If the read
 * failed, disabled is incremented and the file is closed. Readings are
 * done in buf_size bytes.
 * Lines longer than LINE_SIZE are silently truncated.
 */
int read_line(merg)
register MERGE *merg;
{
  register char *ptr = merg->line - 1;	/* Ptr buf that will hold line */

  do {
	ptr++;
	if (merg->cnt == merg->read_chars) {	/* Read new buffer */
		if ((merg->read_chars =
		     read(merg->fd, merg->buffer, buf_size)) <= 0) {
			(void) close(merg->fd);	/* OOPS */
			merg->fd = ERROR;
			disabled++;
			return ERROR;
		}
		merg->cnt = 0;
	}
	*ptr = merg->buffer[merg->cnt++];	/* Assign next char of line */
	if (ptr - merg->line == LINE_SIZE - 1)
		*ptr = '\n';	/* Truncate very long lines */
  } while (*ptr != '\n' && *ptr != '\0');

  if (*ptr == '\0')		/* Add '\n' to last line */
	*ptr = '\n';
  *++ptr = '\0';		/* Add '\0' */
  return OK;
}

/* Skip_lines () skips all same lines in all the files currently being merged.
 * It returns a pointer to the merge struct containing the smallest line.
 */
MERGE *skip_lines(smallest, file_cnt)
register MERGE *smallest;
int file_cnt;
{
  register int i;
  int ret;

  if (disabled == file_cnt - 1)	/* We've had all */
	return smallest;

  for (i = 0; i < file_cnt; i++) {
	if (merge_f[i].fd == ERROR || smallest == &merge_f[i])
		continue;	/* Don't check same file */
	while ((ret = compare(merge_f[i].line, smallest->line)) == 0) {
		if (read_line(&merge_f[i]) == ERROR) break;	/* EOF */
	}
	if (ret < 0)		/* Line wasn't smallest. Try again */
		return skip_lines(&merge_f[i], file_cnt);
  }
  return smallest;
}

/* Uniq_lines () prints only the uniq lines out of the fd of the merg struct. */
void uniq_lines(merg)
register MERGE *merg;
{
  char lastline[LINE_SIZE];	/* Buffer to hold last line */

  for (;;) {
	put_line(merg->line);	/* Print this line */
	copy(lastline, merg->line);	/* and save it */
	if (read_line(merg) == ERROR)	/* Read the next */
		return;
	/* Keep reading until lines duffer */
	while (compare(lastline, merg->line) == SAME)
		if (read_line(merg) == ERROR) return;
  }

  /* NOTREACHED */
}

/*
 * Check_file () checks if a file is sorted in order according to the arguments
 * given in main ().
 */
void check_file(fd, file)
int fd;
char *file;
{
  register MERGE *merg;		/* 1 file only */
  char lastline[LINE_SIZE];	/* Save last line */
  register int ret;		/* ret status of compare */

  if (fd == 0) file = "stdin";
  merg = (MERGE *) mem_top;	/* Assign MERGE structure */
  merg->buffer = mem_top + sizeof(MERGE);
  merg->line = msbrk(LINE_SIZE);
  merg->cnt = merg->read_chars = 0;
  merg->fd = fd;
  buf_size = MEMORY_SIZE - sizeof(MERGE);

  if (read_line(merg) == ERROR)	/* Read first line */
	return;
  copy(lastline, merg->line);	/* and save it */

  for (;;) {
	if (read_line(merg) == ERROR)	/* EOF reached */
		break;
	if ((ret = compare(lastline, merg->line)) > 0) {
		error(FALSE, "Disorder in file ", file);
		write(2, merg->line, length(merg->line));
		break;
	} else if (ret < 0)	/* Copy if lines not equal */
		copy(lastline, merg->line);
	else if (uniq) {
		error(FALSE, "Non uniq line in file ", file);
		write(2, merg->line, length(merg->line));
		break;
	}
  }

  mbrk(mem_top);		/* Reset mem */
}

/* Length () returns the length of the argument line including the linefeed. */
int length(line)
register char *line;
{
  register int i = 1;		/* Add linefeed */

  while (*line++ != '\n') i++;
  return i;
}

/* Copy () copies the src line into the dest line including linefeed. */
void copy(dest, src)
register char *dest, *src;
{
  while ((*dest++ = *src++) != '\n');
}

/* Msbrk() does a sbrk() and checks the return value. */
char *msbrk(size)
register int size;
{
  register char *address;

  if ((address = sbrk(size)) == (char *) -1)
	error(TRUE, "Not enough memory. Use chmem to allocate more", NIL_PTR);
  return address;
}

/* Mbrk() does a brk() and checks the return value. */
void mbrk(address)
char *address;
{
  if (brk(address) < 0) error(TRUE, "Cannot reset memory", NIL_PTR);
}

void catch(dummy)
int dummy;			/* to satisfy the prototype */
{
  register int i;

  signal(SIGINT, SIG_IGN);
  only_merge = FALSE;
  for (i = 0; i < 26; i++) (void) unlink(file_name(i));
  exit(2);
}