texindex.c

linux下bash的源码

char *
find_braced_pos (str, words, chars, ignore_blanks)
     char *str;
     int words, chars;
     int ignore_blanks;
{
  int i;
  int bracelevel;
  char *p = str;
  char c;

  for (i = 0; i < words; i++)
    {
      bracelevel = 1;
      while ((c = *p++) != '{' && c != '\n' && c)
	/* Do nothing. */ ;
      if (c != '{')
	return p - 1;
      while (bracelevel)
	{
	  c = *p++;
	  if (c == '{')
	    bracelevel++;
	  if (c == '}')
	    bracelevel--;
	  if (c == 0 || c == '\n')
	    return p - 1;
	}
    }

  while ((c = *p++) != '{' && c != '\n' && c)
    /* Do nothing. */ ;

  if (c != '{')
    return p - 1;

  if (ignore_blanks)
    while ((c = *p) == ' ' || c == '\t')
      p++;

  for (i = 0; i < chars; i++)
    {
      if (!*p || *p == '\n')
	break;
      p++;
    }
  return p;
}

/* Find the end of the balanced-brace field which starts at STR.
   The position returned is just before the closing brace. */

char *
find_braced_end (str)
     char *str;
{
  int bracelevel;
  char *p = str;
  char c;

  bracelevel = 1;
  while (bracelevel)
    {
      c = *p++;
      if (c == '{')
	bracelevel++;
      if (c == '}')
	bracelevel--;
      if (c == 0 || c == '\n')
	return p - 1;
    }
  return p - 1;
}

long
find_value (start, length)
     char *start;
     long length;
{
  while (length != 0L)
    {
      if (isdigit (*start))
	return atol (start);
      length--;
      start++;
    }
  return 0l;
}

/* Vector used to translate characters for comparison.
   This is how we make all alphanumerics follow all else,
   and ignore case in the first sorting.  */
int char_order[256];

void
init_char_order ()
{
  int i;
  for (i = 1; i < 256; i++)
    char_order[i] = i;

  for (i = '0'; i <= '9'; i++)
    char_order[i] += 512;

  for (i = 'a'; i <= 'z'; i++)
    {
      char_order[i] = 512 + i;
      char_order[i + 'A' - 'a'] = 512 + i;
    }
}

/* Compare two fields (each specified as a start pointer and a character count)
   according to KEYFIELD.
   The sign of the value reports the relation between the fields. */

int
compare_field (keyfield, start1, length1, pos1, start2, length2, pos2)
     struct keyfield *keyfield;
     char *start1;
     long length1;
     long pos1;
     char *start2;
     long length2;
     long pos2;
{
  if (keyfields->positional)
    {
      if (pos1 > pos2)
	return 1;
      else
	return -1;
    }
  if (keyfield->numeric)
    {
      long value = find_value (start1, length1) - find_value (start2, length2);
      if (value > 0)
	return 1;
      if (value < 0)
	return -1;
      return 0;
    }
  else
    {
      char *p1 = start1;
      char *p2 = start2;
      char *e1 = start1 + length1;
      char *e2 = start2 + length2;

      while (1)
	{
	  int c1, c2;

	  if (p1 == e1)
	    c1 = 0;
	  else
	    c1 = *p1++;
	  if (p2 == e2)
	    c2 = 0;
	  else
	    c2 = *p2++;

	  if (char_order[c1] != char_order[c2])
	    return char_order[c1] - char_order[c2];
	  if (!c1)
	    break;
	}

      /* Strings are equal except possibly for case.  */
      p1 = start1;
      p2 = start2;
      while (1)
	{
	  int c1, c2;

	  if (p1 == e1)
	    c1 = 0;
	  else
	    c1 = *p1++;
	  if (p2 == e2)
	    c2 = 0;
	  else
	    c2 = *p2++;

	  if (c1 != c2)
	    /* Reverse sign here so upper case comes out last.  */
	    return c2 - c1;
	  if (!c1)
	    break;
	}

      return 0;
    }
}

/* A `struct linebuffer' is a structure which holds a line of text.
   `readline' reads a line from a stream into a linebuffer
   and works regardless of the length of the line.  */

struct linebuffer
{
  long size;
  char *buffer;
};

/* Initialize LINEBUFFER for use. */

void
initbuffer (linebuffer)
     struct linebuffer *linebuffer;
{
  linebuffer->size = 200;
  linebuffer->buffer = (char *) xmalloc (200);
}

/* Read a line of text from STREAM into LINEBUFFER.
   Return the length of the line.  */

long
readline (linebuffer, stream)
     struct linebuffer *linebuffer;
     FILE *stream;
{
  char *buffer = linebuffer->buffer;
  char *p = linebuffer->buffer;
  char *end = p + linebuffer->size;

  while (1)
    {
      int c = getc (stream);
      if (p == end)
	{
	  buffer = (char *) xrealloc (buffer, linebuffer->size *= 2);
	  p += buffer - linebuffer->buffer;
	  end += buffer - linebuffer->buffer;
	  linebuffer->buffer = buffer;
	}
      if (c < 0 || c == '\n')
	{
	  *p = 0;
	  break;
	}
      *p++ = c;
    }

  return p - buffer;
}

/* Sort an input file too big to sort in core.  */

void
sort_offline (infile, nfiles, total, outfile)
     char *infile;
     int nfiles;
     long total;
     char *outfile;
{
  /* More than enough. */
  int ntemps = 2 * (total + MAX_IN_CORE_SORT - 1) / MAX_IN_CORE_SORT;
  char **tempfiles = (char **) xmalloc (ntemps * sizeof (char *));
  FILE *istream = fopen (infile, "r");
  int i;
  struct linebuffer lb;
  long linelength;
  int failure = 0;

  initbuffer (&lb);

  /* Read in one line of input data.  */

  linelength = readline (&lb, istream);

  if (lb.buffer[0] != '\\' && lb.buffer[0] != '@')
    {
      error ("%s: not a texinfo index file", infile);
      return;
    }

  /* Split up the input into `ntemps' temporary files, or maybe fewer,
     and put the new files' names into `tempfiles' */

  for (i = 0; i < ntemps; i++)
    {
      char *outname = maketempname (++tempcount);
      FILE *ostream = fopen (outname, "w");
      long tempsize = 0;

      if (!ostream)
	pfatal_with_name (outname);
      tempfiles[i] = outname;

      /* Copy lines into this temp file as long as it does not make file
	 "too big" or until there are no more lines.  */

      while (tempsize + linelength + 1 <= MAX_IN_CORE_SORT)
	{
	  tempsize += linelength + 1;
	  fputs (lb.buffer, ostream);
	  putc ('\n', ostream);

	  /* Read another line of input data.  */

	  linelength = readline (&lb, istream);
	  if (!linelength && feof (istream))
	    break;

	  if (lb.buffer[0] != '\\' && lb.buffer[0] != '@')
	    {
	      error ("%s: not a texinfo index file", infile);
	      failure = 1;
	      goto fail;
	    }
	}
      fclose (ostream);
      if (feof (istream))
	break;
    }

  free (lb.buffer);

fail:
  /* Record number of temp files we actually needed.  */

  ntemps = i;

  /* Sort each tempfile into another tempfile.
    Delete the first set of tempfiles and put the names of the second
    into `tempfiles'. */

  for (i = 0; i < ntemps; i++)
    {
      char *newtemp = maketempname (++tempcount);
      sort_in_core (&tempfiles[i], MAX_IN_CORE_SORT, newtemp);
      if (!keep_tempfiles)
	unlink (tempfiles[i]);
      tempfiles[i] = newtemp;
    }

  if (failure)
    return;

  /* Merge the tempfiles together and indexify. */

  merge_files (tempfiles, ntemps, outfile);
}

/* Sort INFILE, whose size is TOTAL,
   assuming that is small enough to be done in-core,
   then indexify it and send the output to OUTFILE (or to stdout).  */

void
sort_in_core (infile, total, outfile)
     char *infile;
     long total;
     char *outfile;
{
  char **nextline;
  char *data = (char *) xmalloc (total + 1);
  char *file_data;
  long file_size;
  int i;
  FILE *ostream = stdout;
  struct lineinfo *lineinfo;

  /* Read the contents of the file into the moby array `data'. */

  int desc = open (infile, O_RDONLY, 0);

  if (desc < 0)
    fatal ("failure reopening %s", infile);
  for (file_size = 0;;)
    {
      i = read (desc, data + file_size, total - file_size);
      if (i <= 0)
	break;
      file_size += i;
    }
  file_data = data;
  data[file_size] = 0;

  close (desc);

  if (file_size > 0 && data[0] != '\\' && data[0] != '@')
    {
      error ("%s: not a texinfo index file", infile);
      return;
    }

  init_char_order ();

  /* Sort routines want to know this address. */

  text_base = data;

  /* Create the array of pointers to lines, with a default size
     frequently enough.  */

  nlines = total / 50;
  if (!nlines)
    nlines = 2;
  linearray = (char **) xmalloc (nlines * sizeof (char *));

  /* `nextline' points to the next free slot in this array.
     `nlines' is the allocated size.  */

  nextline = linearray;

  /* Parse the input file's data, and make entries for the lines.  */

  nextline = parsefile (infile, nextline, file_data, file_size);
  if (nextline == 0)
    {
      error ("%s: not a texinfo index file", infile);
      return;
    }

  /* Sort the lines. */

  /* If we have enough space, find the first keyfield of each line in advance.
     Make a `struct lineinfo' for each line, which records the keyfield
     as well as the line, and sort them.  */

  lineinfo = (struct lineinfo *) malloc ((nextline - linearray) * sizeof (struct lineinfo));

  if (lineinfo)
    {
      struct lineinfo *lp;
      char **p;

      for (lp = lineinfo, p = linearray; p != nextline; lp++, p++)
	{
	  lp->text = *p;
	  lp->key.text = find_field (keyfields, *p, &lp->keylen);
	  if (keyfields->numeric)
	    lp->key.number = find_value (lp->key.text, lp->keylen);
	}

      qsort (lineinfo, nextline - linearray, sizeof (struct lineinfo), compare_prepared);

      for (lp = lineinfo, p = linearray; p != nextline; lp++, p++)
	*p = lp->text;

      free (lineinfo);
    }
  else
    qsort (linearray, nextline - linearray, sizeof (char *), compare_full);

  /* Open the output file. */

  if (outfile)
    {
      ostream = fopen (outfile, "w");
      if (!ostream)
	pfatal_with_name (outfile);
    }

  writelines (linearray, nextline - linearray, ostream);
  if (outfile)
    fclose (ostream);

  free (linearray);
  free (data);
}

/* Parse an input string in core into lines.
   DATA is the input string, and SIZE is its length.
   Data goes in LINEARRAY starting at NEXTLINE.
   The value returned is the first entry in LINEARRAY still unused.
   Value 0 means input file contents are invalid.  */

char **
parsefile (filename, nextline, data, size)
     char *filename;
     char **nextline;
     char *data;
     long size;
{
  char *p, *end;
  char **line = nextline;

  p = data;
  end = p + size;
  *end = 0;

  while (p != end)
    {
      if (p[0] != '\\' && p[0] != '@')
	return 0;

      *line = p;
      while (*p && *p != '\n')
	p++;
      if (p != end)
	p++;

      line++;
      if (line == linearray + nlines)
	{
	  char **old = linearray;
	  linearray = (char **) xrealloc (linearray, sizeof (char *) * (nlines *= 4));
	  line += linearray - old;
	}
    }

  return line;
}

/* Indexification is a filter applied to the sorted lines
   as they are being written to the output file.
   Multiple entries for the same name, with different page numbers,
   get combined into a single entry with multiple page numbers.
   The first braced field, which is used for sorting, is discarded.
   However, its first character is examined, folded to lower case,
   and if it is different from that in the previous line fed to us
   a \initial line is written with one argument, the new initial.

   If an entry has four braced fields, then the second and third
   constitute primary and secondary names.
   In this case, each change of primary name
   generates a \primary line which contains only the primary name,
   and in between these are \secondary lines which contain
   just a secondary name and page numbers. */

/* The last primary name we wrote a \primary entry for.
   If only one level of indexing is being done, this is the last name seen. */
char *lastprimary;
/* Length of storage allocated for lastprimary. */
int lastprimarylength;

/* Similar, for the secondary name. */
char *lastsecondary;
int lastsecondarylength;

/* Zero if we are not in the middle of writing an entry.
   One if we have written the beginning of an entry but have not
   yet written any page numbers into it.
   Greater than one if we have written the beginning of an entry
   plus at least one page number. */
int pending;

/* The initial (for sorting purposes) of the last primary entry written.
   When this changes, a \initial {c} line is written */

char *lastinitial;

int lastinitiallength;

/* When we need a string of length 1 for the value of lastinitial,
   store it here.  */

char lastinitial1[2];

/* Initialize static storage for writing an index. */

static void
xbzero(s, n)