Correct typo: vender -> vendor
[dragonfly.git] / contrib / texinfo / util / texindex.c
1 /* Process TeX index dribble output into an actual index.
2    $Id: texindex.c,v 1.41 2002/03/11 19:55:46 karl Exp $
3
4    Copyright (C) 1987, 91, 92, 96, 97, 98, 99, 2000, 01, 02
5    Free Software Foundation, Inc. 
6
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 2, or (at your option)
10    any later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with this program; if not, write to the Free Software
19    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307. */
20
21 #include "system.h"
22 #include <getopt.h>
23
24 static char *program_name = "texindex";
25
26 #if defined (emacs)
27 #  include "../src/config.h"
28 /* Some s/os.h files redefine these. */
29 #  undef read
30 #  undef close
31 #  undef write
32 #  undef open
33 #endif
34
35 #if !defined (HAVE_MEMSET)
36 #undef memset
37 #define memset(ptr, ignore, count) bzero (ptr, count)
38 #endif
39
40 char *mktemp ();
41
42 #if !defined (SEEK_SET)
43 #  define SEEK_SET 0
44 #  define SEEK_CUR 1
45 #  define SEEK_END 2
46 #endif /* !SEEK_SET */
47
48 /* When sorting in core, this structure describes one line
49    and the position and length of its first keyfield.  */
50 struct lineinfo
51 {
52   char *text;           /* The actual text of the line. */
53   union {
54     char *text;         /* The start of the key (for textual comparison). */
55     long number;        /* The numeric value (for numeric comparison). */
56   } key;
57   long keylen;          /* Length of KEY field. */
58 };
59
60 /* This structure describes a field to use as a sort key. */
61 struct keyfield
62 {
63   int startwords;       /* Number of words to skip. */
64   int startchars;       /* Number of additional chars to skip. */
65   int endwords;         /* Number of words to ignore at end. */
66   int endchars;         /* Ditto for characters of last word. */
67   char ignore_blanks;   /* Non-zero means ignore spaces and tabs. */
68   char fold_case;       /* Non-zero means case doesn't matter. */
69   char reverse;         /* Non-zero means compare in reverse order. */
70   char numeric;         /* Non-zeros means field is ASCII numeric. */
71   char positional;      /* Sort according to file position. */
72   char braced;          /* Count balanced-braced groupings as fields. */
73 };
74
75 /* Vector of keyfields to use. */
76 struct keyfield keyfields[3];
77
78 /* Number of keyfields stored in that vector.  */
79 int num_keyfields = 3;
80
81 /* Vector of input file names, terminated with a null pointer. */
82 char **infiles;
83
84 /* Vector of corresponding output file names, or NULL, meaning default it
85    (add an `s' to the end). */
86 char **outfiles;
87
88 /* Length of `infiles'. */
89 int num_infiles;
90
91 /* Pointer to the array of pointers to lines being sorted. */
92 char **linearray;
93
94 /* The allocated length of `linearray'. */
95 long nlines;
96
97 /* Directory to use for temporary files.  On Unix, it ends with a slash.  */
98 char *tempdir;
99
100 /* Start of filename to use for temporary files.  */
101 char *tempbase;
102
103 /* Number of last temporary file.  */
104 int tempcount;
105
106 /* Number of last temporary file already deleted.
107    Temporary files are deleted by `flush_tempfiles' in order of creation.  */
108 int last_deleted_tempcount;
109
110 /* During in-core sort, this points to the base of the data block
111    which contains all the lines of data.  */
112 char *text_base;
113
114 /* Additional command switches .*/
115
116 /* Nonzero means do not delete tempfiles -- for debugging. */
117 int keep_tempfiles;
118
119 /* Forward declarations of functions in this file. */
120 void decode_command ();
121 void sort_in_core ();
122 void sort_offline ();
123 char **parsefile ();
124 char *find_field ();
125 char *find_pos ();
126 long find_value ();
127 char *find_braced_pos ();
128 char *find_braced_end ();
129 void writelines ();
130 int compare_field ();
131 int compare_full ();
132 long readline ();
133 int merge_files ();
134 int merge_direct ();
135 void pfatal_with_name ();
136 void fatal ();
137 void error ();
138 void *xmalloc (), *xrealloc ();
139 char *concat ();
140 void flush_tempfiles ();
141 \f
142 #define MAX_IN_CORE_SORT 500000
143
144 int
145 main (argc, argv)
146      int argc;
147      char **argv;
148 {
149   int i;
150
151   tempcount = 0;
152   last_deleted_tempcount = 0;
153
154 #ifdef HAVE_SETLOCALE
155   /* Set locale via LC_ALL.  */
156   setlocale (LC_ALL, "");
157 #endif
158
159   /* Set the text message domain.  */
160   bindtextdomain (PACKAGE, LOCALEDIR);
161   textdomain (PACKAGE);
162
163   /* Describe the kind of sorting to do. */
164   /* The first keyfield uses the first braced field and folds case. */
165   keyfields[0].braced = 1;
166   keyfields[0].fold_case = 1;
167   keyfields[0].endwords = -1;
168   keyfields[0].endchars = -1;
169
170   /* The second keyfield uses the second braced field, numerically. */
171   keyfields[1].braced = 1;
172   keyfields[1].numeric = 1;
173   keyfields[1].startwords = 1;
174   keyfields[1].endwords = -1;
175   keyfields[1].endchars = -1;
176
177   /* The third keyfield (which is ignored while discarding duplicates)
178      compares the whole line. */
179   keyfields[2].endwords = -1;
180   keyfields[2].endchars = -1;
181
182   decode_command (argc, argv);
183
184   tempbase = mktemp (concat ("txiXXXXXX", "", ""));
185
186   /* Process input files completely, one by one.  */
187
188   for (i = 0; i < num_infiles; i++)
189     {
190       int desc;
191       off_t ptr;
192       char *outfile;
193       struct stat instat;
194
195       desc = open (infiles[i], O_RDONLY, 0);
196       if (desc < 0)
197         pfatal_with_name (infiles[i]);
198
199       if (stat (infiles[i], &instat))
200         pfatal_with_name (infiles[i]);
201       if (S_ISDIR (instat.st_mode))
202         {
203 #ifdef EISDIR
204           errno = EISDIR;
205 #endif
206           pfatal_with_name (infiles[i]);
207         }
208
209       lseek (desc, (off_t) 0, SEEK_END);
210       ptr = (off_t) lseek (desc, (off_t) 0, SEEK_CUR);
211
212       close (desc);
213
214       outfile = outfiles[i];
215       if (!outfile)
216         {
217           outfile = concat (infiles[i], "s", "");
218         }
219
220       if (ptr < MAX_IN_CORE_SORT)
221         /* Sort a small amount of data. */
222         sort_in_core (infiles[i], ptr, outfile);
223       else
224         sort_offline (infiles[i], ptr, outfile);
225     }
226
227   flush_tempfiles (tempcount);
228   xexit (0);
229
230   return 0; /* Avoid bogus warnings.  */
231 }
232 \f
233 typedef struct
234 {
235   char *long_name;
236   char *short_name;
237   int *variable_ref;
238   int variable_value;
239   char *arg_name;
240   char *doc_string;
241 } TEXINDEX_OPTION;
242
243 TEXINDEX_OPTION texindex_options[] = {
244   { "--help", "-h", (int *)NULL, 0, (char *)NULL,
245       N_("display this help and exit") },
246   { "--keep", "-k", &keep_tempfiles, 1, (char *)NULL,
247       N_("keep temporary files around after processing") },
248   { "--no-keep", 0, &keep_tempfiles, 0, (char *)NULL,
249       N_("do not keep temporary files around after processing (default)") },
250   { "--output", "-o", (int *)NULL, 0, "FILE",
251       N_("send output to FILE") },
252   { "--version", (char *)NULL, (int *)NULL, 0, (char *)NULL,
253       N_("display version information and exit") },
254   { (char *)NULL, (char *)NULL, (int *)NULL, 0, (char *)NULL }
255 };
256
257 void
258 usage (result_value)
259      int result_value;
260 {
261   register int i;
262   FILE *f = result_value ? stderr : stdout;
263
264   fprintf (f, _("Usage: %s [OPTION]... FILE...\n"), program_name);
265   fprintf (f, _("Generate a sorted index for each TeX output FILE.\n"));
266   /* Avoid trigraph nonsense.  */
267   fprintf (f,
268 _("Usually FILE... is specified as `foo.%c%c\' for a document `foo.texi'.\n"),
269            '?', '?'); /* avoid trigraph in cat-id-tbl.c */
270   fprintf (f, _("\nOptions:\n"));
271
272   for (i = 0; texindex_options[i].long_name; i++)
273     {
274       putc (' ', f);
275
276       if (texindex_options[i].short_name)
277         fprintf (f, "%s, ", texindex_options[i].short_name);
278
279       fprintf (f, "%s %s",
280                texindex_options[i].long_name,
281                texindex_options[i].arg_name
282                ? texindex_options[i].arg_name : "");
283
284       fprintf (f, "\t%s\n", _(texindex_options[i].doc_string));
285     }
286   fputs (_("\n\
287 Email bug reports to bug-texinfo@gnu.org,\n\
288 general questions and discussion to help-texinfo@gnu.org.\n\
289 Texinfo home page: http://www.gnu.org/software/texinfo/"), f);
290   fputs ("\n", f);
291
292   xexit (result_value);
293 }
294
295 /* Decode the command line arguments to set the parameter variables
296    and set up the vector of keyfields and the vector of input files. */
297
298 void
299 decode_command (argc, argv)
300      int argc;
301      char **argv;
302 {
303   int arg_index = 1;
304   char **ip;
305   char **op;
306
307   /* Store default values into parameter variables. */
308
309   tempdir = getenv ("TMPDIR");
310   if (tempdir == NULL)
311     tempdir = getenv ("TEMP");
312   if (tempdir == NULL)
313     tempdir = getenv ("TMP");
314   if (tempdir == NULL)
315     tempdir = DEFAULT_TMPDIR;
316   else
317     tempdir = concat (tempdir, "/", "");
318
319   keep_tempfiles = 0;
320
321   /* Allocate ARGC input files, which must be enough.  */
322
323   infiles = (char **) xmalloc (argc * sizeof (char *));
324   outfiles = (char **) xmalloc (argc * sizeof (char *));
325   ip = infiles;
326   op = outfiles;
327
328   while (arg_index < argc)
329     {
330       char *arg = argv[arg_index++];
331
332       if (*arg == '-')
333         {
334           if (strcmp (arg, "--version") == 0)
335             {
336               printf ("texindex (GNU %s) %s\n", PACKAGE, VERSION);
337               puts ("");
338               printf (_("Copyright (C) %s Free Software Foundation, Inc.\n\
339 There is NO warranty.  You may redistribute this software\n\
340 under the terms of the GNU General Public License.\n\
341 For more information about these matters, see the files named COPYING.\n"),
342                   "2002");
343               xexit (0);
344             }
345           else if ((strcmp (arg, "--keep") == 0) ||
346                    (strcmp (arg, "-k") == 0))
347             {
348               keep_tempfiles = 1;
349             }
350           else if ((strcmp (arg, "--help") == 0) ||
351                    (strcmp (arg, "-h") == 0))
352             {
353               usage (0);
354             }
355           else if ((strcmp (arg, "--output") == 0) ||
356                    (strcmp (arg, "-o") == 0))
357             {
358               if (argv[arg_index] != (char *)NULL)
359                 {
360                   arg_index++;
361                   if (op > outfiles)
362                     *(op - 1) = argv[arg_index];
363                 }
364               else
365                 usage (1);
366             }
367           else
368             usage (1);
369         }
370       else
371         {
372           *ip++ = arg;
373           *op++ = (char *)NULL;
374         }
375     }
376
377   /* Record number of keyfields and terminate list of filenames. */
378   num_infiles = ip - infiles;
379   *ip = (char *)NULL;
380   if (num_infiles == 0)
381     usage (1);
382 }
383 \f
384 /* Return a name for a temporary file. */
385
386 static char *
387 maketempname (count)
388      int count;
389 {
390   char tempsuffix[10];
391   sprintf (tempsuffix, ".%d", count);
392   return concat (tempdir, tempbase, tempsuffix);
393 }
394
395 /* Delete all temporary files up to TO_COUNT. */
396
397 void
398 flush_tempfiles (to_count)
399      int to_count;
400 {
401   if (keep_tempfiles)
402     return;
403   while (last_deleted_tempcount < to_count)
404     unlink (maketempname (++last_deleted_tempcount));
405 }
406
407 \f
408 /* Compare LINE1 and LINE2 according to the specified set of keyfields. */
409
410 int
411 compare_full (line1, line2)
412      char **line1, **line2;
413 {
414   int i;
415
416   /* Compare using the first keyfield;
417      if that does not distinguish the lines, try the second keyfield;
418      and so on. */
419
420   for (i = 0; i < num_keyfields; i++)
421     {
422       long length1, length2;
423       char *start1 = find_field (&keyfields[i], *line1, &length1);
424       char *start2 = find_field (&keyfields[i], *line2, &length2);
425       int tem = compare_field (&keyfields[i], start1, length1, *line1 - text_base,
426                                start2, length2, *line2 - text_base);
427       if (tem)
428         {
429           if (keyfields[i].reverse)
430             return -tem;
431           return tem;
432         }
433     }
434
435   return 0;                     /* Lines match exactly. */
436 }
437
438 /* Compare LINE1 and LINE2, described by structures
439    in which the first keyfield is identified in advance.
440    For positional sorting, assumes that the order of the lines in core
441    reflects their nominal order.  */
442
443 int
444 compare_prepared (line1, line2)
445      struct lineinfo *line1, *line2;
446 {
447   int i;
448   int tem;
449   char *text1, *text2;
450
451   /* Compare using the first keyfield, which has been found for us already. */
452   if (keyfields->positional)
453     {
454       if (line1->text - text_base > line2->text - text_base)
455         tem = 1;
456       else
457         tem = -1;
458     }
459   else if (keyfields->numeric)
460     tem = line1->key.number - line2->key.number;
461   else
462     tem = compare_field (keyfields, line1->key.text, line1->keylen, 0,
463                          line2->key.text, line2->keylen, 0);
464   if (tem)
465     {
466       if (keyfields->reverse)
467         return -tem;
468       return tem;
469     }
470
471   text1 = line1->text;
472   text2 = line2->text;
473
474   /* Compare using the second keyfield;
475      if that does not distinguish the lines, try the third keyfield;
476      and so on. */
477
478   for (i = 1; i < num_keyfields; i++)
479     {
480       long length1, length2;
481       char *start1 = find_field (&keyfields[i], text1, &length1);
482       char *start2 = find_field (&keyfields[i], text2, &length2);
483       int tem = compare_field (&keyfields[i], start1, length1, text1 - text_base,
484                                start2, length2, text2 - text_base);
485       if (tem)
486         {
487           if (keyfields[i].reverse)
488             return -tem;
489           return tem;
490         }
491     }
492
493   return 0;                     /* Lines match exactly. */
494 }
495
496 /* Like compare_full but more general.
497    You can pass any strings, and you can say how many keyfields to use.
498    POS1 and POS2 should indicate the nominal positional ordering of
499    the two lines in the input.  */
500
501 int
502 compare_general (str1, str2, pos1, pos2, use_keyfields)
503      char *str1, *str2;
504      long pos1, pos2;
505      int use_keyfields;
506 {
507   int i;
508
509   /* Compare using the first keyfield;
510      if that does not distinguish the lines, try the second keyfield;
511      and so on. */
512
513   for (i = 0; i < use_keyfields; i++)
514     {
515       long length1, length2;
516       char *start1 = find_field (&keyfields[i], str1, &length1);
517       char *start2 = find_field (&keyfields[i], str2, &length2);
518       int tem = compare_field (&keyfields[i], start1, length1, pos1,
519                                start2, length2, pos2);
520       if (tem)
521         {
522           if (keyfields[i].reverse)
523             return -tem;
524           return tem;
525         }
526     }
527
528   return 0;                     /* Lines match exactly. */
529 }
530
531 /* Find the start and length of a field in STR according to KEYFIELD.
532    A pointer to the starting character is returned, and the length
533    is stored into the int that LENGTHPTR points to.  */
534
535 char *
536 find_field (keyfield, str, lengthptr)
537      struct keyfield *keyfield;
538      char *str;
539      long *lengthptr;
540 {
541   char *start;
542   char *end;
543   char *(*fun) ();
544
545   if (keyfield->braced)
546     fun = find_braced_pos;
547   else
548     fun = find_pos;
549
550   start = (*fun) (str, keyfield->startwords, keyfield->startchars,
551                   keyfield->ignore_blanks);
552   if (keyfield->endwords < 0)
553     {
554       if (keyfield->braced)
555         end = find_braced_end (start);
556       else
557         {
558           end = start;
559           while (*end && *end != '\n')
560             end++;
561         }
562     }
563   else
564     {
565       end = (*fun) (str, keyfield->endwords, keyfield->endchars, 0);
566       if (end - str < start - str)
567         end = start;
568     }
569   *lengthptr = end - start;
570   return start;
571 }
572
573 /* Return a pointer to a specified place within STR,
574    skipping (from the beginning) WORDS words and then CHARS chars.
575    If IGNORE_BLANKS is nonzero, we skip all blanks
576    after finding the specified word.  */
577
578 char *
579 find_pos (str, words, chars, ignore_blanks)
580      char *str;
581      int words, chars;
582      int ignore_blanks;
583 {
584   int i;
585   char *p = str;
586
587   for (i = 0; i < words; i++)
588     {
589       char c;
590       /* Find next bunch of nonblanks and skip them. */
591       while ((c = *p) == ' ' || c == '\t')
592         p++;
593       while ((c = *p) && c != '\n' && !(c == ' ' || c == '\t'))
594         p++;
595       if (!*p || *p == '\n')
596         return p;
597     }
598
599   while (*p == ' ' || *p == '\t')
600     p++;
601
602   for (i = 0; i < chars; i++)
603     {
604       if (!*p || *p == '\n')
605         break;
606       p++;
607     }
608   return p;
609 }
610
611 /* Like find_pos but assumes that each field is surrounded by braces
612    and that braces within fields are balanced. */
613
614 char *
615 find_braced_pos (str, words, chars, ignore_blanks)
616      char *str;
617      int words, chars;
618      int ignore_blanks;
619 {
620   int i;
621   int bracelevel;
622   char *p = str;
623   char c;
624
625   for (i = 0; i < words; i++)
626     {
627       bracelevel = 1;
628       while ((c = *p++) != '{' && c != '\n' && c)
629         /* Do nothing. */ ;
630       if (c != '{')
631         return p - 1;
632       while (bracelevel)
633         {
634           c = *p++;
635           if (c == '{')
636             bracelevel++;
637           if (c == '}')
638             bracelevel--;
639           if (c == 0 || c == '\n')
640             return p - 1;
641         }
642     }
643
644   while ((c = *p++) != '{' && c != '\n' && c)
645     /* Do nothing. */ ;
646
647   if (c != '{')
648     return p - 1;
649
650   if (ignore_blanks)
651     while ((c = *p) == ' ' || c == '\t')
652       p++;
653
654   for (i = 0; i < chars; i++)
655     {
656       if (!*p || *p == '\n')
657         break;
658       p++;
659     }
660   return p;
661 }
662
663 /* Find the end of the balanced-brace field which starts at STR.
664    The position returned is just before the closing brace. */
665
666 char *
667 find_braced_end (str)
668      char *str;
669 {
670   int bracelevel;
671   char *p = str;
672   char c;
673
674   bracelevel = 1;
675   while (bracelevel)
676     {
677       c = *p++;
678       if (c == '{')
679         bracelevel++;
680       if (c == '}')
681         bracelevel--;
682       if (c == 0 || c == '\n')
683         return p - 1;
684     }
685   return p - 1;
686 }
687
688 long
689 find_value (start, length)
690      char *start;
691      long length;
692 {
693   while (length != 0L)
694     {
695       if (isdigit (*start))
696         return atol (start);
697       length--;
698       start++;
699     }
700   return 0l;
701 }
702
703 /* Vector used to translate characters for comparison.
704    This is how we make all alphanumerics follow all else,
705    and ignore case in the first sorting.  */
706 int char_order[256];
707
708 void
709 init_char_order ()
710 {
711   int i;
712   for (i = 1; i < 256; i++)
713     char_order[i] = i;
714
715   for (i = '0'; i <= '9'; i++)
716     char_order[i] += 512;
717
718   for (i = 'a'; i <= 'z'; i++)
719     {
720       char_order[i] = 512 + i;
721       char_order[i + 'A' - 'a'] = 512 + i;
722     }
723 }
724
725 /* Compare two fields (each specified as a start pointer and a character count)
726    according to KEYFIELD.
727    The sign of the value reports the relation between the fields. */
728
729 int
730 compare_field (keyfield, start1, length1, pos1, start2, length2, pos2)
731      struct keyfield *keyfield;
732      char *start1;
733      long length1;
734      long pos1;
735      char *start2;
736      long length2;
737      long pos2;
738 {
739   if (keyfields->positional)
740     {
741       if (pos1 > pos2)
742         return 1;
743       else
744         return -1;
745     }
746   if (keyfield->numeric)
747     {
748       long value = find_value (start1, length1) - find_value (start2, length2);
749       if (value > 0)
750         return 1;
751       if (value < 0)
752         return -1;
753       return 0;
754     }
755   else
756     {
757       char *p1 = start1;
758       char *p2 = start2;
759       char *e1 = start1 + length1;
760       char *e2 = start2 + length2;
761
762       while (1)
763         {
764           int c1, c2;
765
766           if (p1 == e1)
767             c1 = 0;
768           else
769             c1 = *p1++;
770           if (p2 == e2)
771             c2 = 0;
772           else
773             c2 = *p2++;
774
775           if (char_order[c1] != char_order[c2])
776             return char_order[c1] - char_order[c2];
777           if (!c1)
778             break;
779         }
780
781       /* Strings are equal except possibly for case.  */
782       p1 = start1;
783       p2 = start2;
784       while (1)
785         {
786           int c1, c2;
787
788           if (p1 == e1)
789             c1 = 0;
790           else
791             c1 = *p1++;
792           if (p2 == e2)
793             c2 = 0;
794           else
795             c2 = *p2++;
796
797           if (c1 != c2)
798             /* Reverse sign here so upper case comes out last.  */
799             return c2 - c1;
800           if (!c1)
801             break;
802         }
803
804       return 0;
805     }
806 }
807 \f
808 /* A `struct linebuffer' is a structure which holds a line of text.
809    `readline' reads a line from a stream into a linebuffer
810    and works regardless of the length of the line.  */
811
812 struct linebuffer
813 {
814   long size;
815   char *buffer;
816 };
817
818 /* Initialize LINEBUFFER for use. */
819
820 void
821 initbuffer (linebuffer)
822      struct linebuffer *linebuffer;
823 {
824   linebuffer->size = 200;
825   linebuffer->buffer = (char *) xmalloc (200);
826 }
827
828 /* Read a line of text from STREAM into LINEBUFFER.
829    Return the length of the line.  */
830
831 long
832 readline (linebuffer, stream)
833      struct linebuffer *linebuffer;
834      FILE *stream;
835 {
836   char *buffer = linebuffer->buffer;
837   char *p = linebuffer->buffer;
838   char *end = p + linebuffer->size;
839
840   while (1)
841     {
842       int c = getc (stream);
843       if (p == end)
844         {
845           buffer = (char *) xrealloc (buffer, linebuffer->size *= 2);
846           p += buffer - linebuffer->buffer;
847           end += buffer - linebuffer->buffer;
848           linebuffer->buffer = buffer;
849         }
850       if (c < 0 || c == '\n')
851         {
852           *p = 0;
853           break;
854         }
855       *p++ = c;
856     }
857
858   return p - buffer;
859 }
860 \f
861 /* Sort an input file too big to sort in core.  */
862
863 void
864 sort_offline (infile, nfiles, total, outfile)
865      char *infile;
866      int nfiles;
867      off_t total;
868      char *outfile;
869 {
870   /* More than enough. */
871   int ntemps = 2 * (total + MAX_IN_CORE_SORT - 1) / MAX_IN_CORE_SORT;
872   char **tempfiles = (char **) xmalloc (ntemps * sizeof (char *));
873   FILE *istream = fopen (infile, "r");
874   int i;
875   struct linebuffer lb;
876   long linelength;
877   int failure = 0;
878
879   initbuffer (&lb);
880
881   /* Read in one line of input data.  */
882
883   linelength = readline (&lb, istream);
884
885   if (lb.buffer[0] != '\\' && lb.buffer[0] != '@')
886     {
887       error (_("%s: not a texinfo index file"), infile);
888       return;
889     }
890
891   /* Split up the input into `ntemps' temporary files, or maybe fewer,
892      and put the new files' names into `tempfiles' */
893
894   for (i = 0; i < ntemps; i++)
895     {
896       char *outname = maketempname (++tempcount);
897       FILE *ostream = fopen (outname, "w");
898       long tempsize = 0;
899
900       if (!ostream)
901         pfatal_with_name (outname);
902       tempfiles[i] = outname;
903
904       /* Copy lines into this temp file as long as it does not make file
905          "too big" or until there are no more lines.  */
906
907       while (tempsize + linelength + 1 <= MAX_IN_CORE_SORT)
908         {
909           tempsize += linelength + 1;
910           fputs (lb.buffer, ostream);
911           putc ('\n', ostream);
912
913           /* Read another line of input data.  */
914
915           linelength = readline (&lb, istream);
916           if (!linelength && feof (istream))
917             break;
918
919           if (lb.buffer[0] != '\\' && lb.buffer[0] != '@')
920             {
921               error (_("%s: not a texinfo index file"), infile);
922               failure = 1;
923               goto fail;
924             }
925         }
926       fclose (ostream);
927       if (feof (istream))
928         break;
929     }
930
931   free (lb.buffer);
932
933 fail:
934   /* Record number of temp files we actually needed.  */
935
936   ntemps = i;
937
938   /* Sort each tempfile into another tempfile.
939     Delete the first set of tempfiles and put the names of the second
940     into `tempfiles'. */
941
942   for (i = 0; i < ntemps; i++)
943     {
944       char *newtemp = maketempname (++tempcount);
945       sort_in_core (&tempfiles[i], MAX_IN_CORE_SORT, newtemp);
946       if (!keep_tempfiles)
947         unlink (tempfiles[i]);
948       tempfiles[i] = newtemp;
949     }
950
951   if (failure)
952     return;
953
954   /* Merge the tempfiles together and indexify. */
955
956   merge_files (tempfiles, ntemps, outfile);
957 }
958 \f
959 /* Sort INFILE, whose size is TOTAL,
960    assuming that is small enough to be done in-core,
961    then indexify it and send the output to OUTFILE (or to stdout).  */
962
963 void
964 sort_in_core (infile, total, outfile)
965      char *infile;
966      off_t total;
967      char *outfile;
968 {
969   char **nextline;
970   char *data = (char *) xmalloc (total + 1);
971   char *file_data;
972   long file_size;
973   int i;
974   FILE *ostream = stdout;
975   struct lineinfo *lineinfo;
976
977   /* Read the contents of the file into the moby array `data'. */
978
979   int desc = open (infile, O_RDONLY, 0);
980
981   if (desc < 0)
982     fatal (_("failure reopening %s"), infile);
983   for (file_size = 0;;)
984     {
985       i = read (desc, data + file_size, total - file_size);
986       if (i <= 0)
987         break;
988       file_size += i;
989     }
990   file_data = data;
991   data[file_size] = 0;
992
993   close (desc);
994
995   if (file_size > 0 && data[0] != '\\' && data[0] != '@')
996     {
997       error (_("%s: not a texinfo index file"), infile);
998       return;
999     }
1000
1001   init_char_order ();
1002
1003   /* Sort routines want to know this address. */
1004
1005   text_base = data;
1006
1007   /* Create the array of pointers to lines, with a default size
1008      frequently enough.  */
1009
1010   nlines = total / 50;
1011   if (!nlines)
1012     nlines = 2;
1013   linearray = (char **) xmalloc (nlines * sizeof (char *));
1014
1015   /* `nextline' points to the next free slot in this array.
1016      `nlines' is the allocated size.  */
1017
1018   nextline = linearray;
1019
1020   /* Parse the input file's data, and make entries for the lines.  */
1021
1022   nextline = parsefile (infile, nextline, file_data, file_size);
1023   if (nextline == 0)
1024     {
1025       error (_("%s: not a texinfo index file"), infile);
1026       return;
1027     }
1028
1029   /* Sort the lines. */
1030
1031   /* If we have enough space, find the first keyfield of each line in advance.
1032      Make a `struct lineinfo' for each line, which records the keyfield
1033      as well as the line, and sort them.  */
1034
1035   lineinfo = (struct lineinfo *) malloc ((nextline - linearray) * sizeof (struct lineinfo));
1036
1037   if (lineinfo)
1038     {
1039       struct lineinfo *lp;
1040       char **p;
1041
1042       for (lp = lineinfo, p = linearray; p != nextline; lp++, p++)
1043         {
1044           lp->text = *p;
1045           lp->key.text = find_field (keyfields, *p, &lp->keylen);
1046           if (keyfields->numeric)
1047             lp->key.number = find_value (lp->key.text, lp->keylen);
1048         }
1049
1050       qsort (lineinfo, nextline - linearray, sizeof (struct lineinfo),
1051              compare_prepared);
1052
1053       for (lp = lineinfo, p = linearray; p != nextline; lp++, p++)
1054         *p = lp->text;
1055
1056       free (lineinfo);
1057     }
1058   else
1059     qsort (linearray, nextline - linearray, sizeof (char *), compare_full);
1060
1061   /* Open the output file. */
1062
1063   if (outfile)
1064     {
1065       ostream = fopen (outfile, "w");
1066       if (!ostream)
1067         pfatal_with_name (outfile);
1068     }
1069
1070   writelines (linearray, nextline - linearray, ostream);
1071   if (outfile)
1072     fclose (ostream);
1073
1074   free (linearray);
1075   free (data);
1076 }
1077 \f
1078 /* Parse an input string in core into lines.
1079    DATA is the input string, and SIZE is its length.
1080    Data goes in LINEARRAY starting at NEXTLINE.
1081    The value returned is the first entry in LINEARRAY still unused.
1082    Value 0 means input file contents are invalid.  */
1083
1084 char **
1085 parsefile (filename, nextline, data, size)
1086      char *filename;
1087      char **nextline;
1088      char *data;
1089      long size;
1090 {
1091   char *p, *end;
1092   char **line = nextline;
1093
1094   p = data;
1095   end = p + size;
1096   *end = 0;
1097
1098   while (p != end)
1099     {
1100       if (p[0] != '\\' && p[0] != '@')
1101         return 0;
1102
1103       *line = p;
1104       while (*p && *p != '\n')
1105         p++;
1106       if (p != end)
1107         p++;
1108
1109       line++;
1110       if (line == linearray + nlines)
1111         {
1112           char **old = linearray;
1113           linearray = (char **) xrealloc (linearray, sizeof (char *) * (nlines *= 4));
1114           line += linearray - old;
1115         }
1116     }
1117
1118   return line;
1119 }
1120 \f
1121 /* Indexification is a filter applied to the sorted lines
1122    as they are being written to the output file.
1123    Multiple entries for the same name, with different page numbers,
1124    get combined into a single entry with multiple page numbers.
1125    The first braced field, which is used for sorting, is discarded.
1126    However, its first character is examined, folded to lower case,
1127    and if it is different from that in the previous line fed to us
1128    a \initial line is written with one argument, the new initial.
1129
1130    If an entry has four braced fields, then the second and third
1131    constitute primary and secondary names.
1132    In this case, each change of primary name
1133    generates a \primary line which contains only the primary name,
1134    and in between these are \secondary lines which contain
1135    just a secondary name and page numbers. */
1136
1137 /* The last primary name we wrote a \primary entry for.
1138    If only one level of indexing is being done, this is the last name seen. */
1139 char *lastprimary;
1140 /* Length of storage allocated for lastprimary. */
1141 int lastprimarylength;
1142
1143 /* Similar, for the secondary name. */
1144 char *lastsecondary;
1145 int lastsecondarylength;
1146
1147 /* Zero if we are not in the middle of writing an entry.
1148    One if we have written the beginning of an entry but have not
1149    yet written any page numbers into it.
1150    Greater than one if we have written the beginning of an entry
1151    plus at least one page number. */
1152 int pending;
1153
1154 /* The initial (for sorting purposes) of the last primary entry written.
1155    When this changes, a \initial {c} line is written */
1156
1157 char *lastinitial;
1158
1159 int lastinitiallength;
1160
1161 /* When we need a string of length 1 for the value of lastinitial,
1162    store it here.  */
1163
1164 char lastinitial1[2];
1165
1166 /* Initialize static storage for writing an index. */
1167
1168 void
1169 init_index ()
1170 {
1171   pending = 0;
1172   lastinitial = lastinitial1;
1173   lastinitial1[0] = 0;
1174   lastinitial1[1] = 0;
1175   lastinitiallength = 0;
1176   lastprimarylength = 100;
1177   lastprimary = (char *) xmalloc (lastprimarylength + 1);
1178   memset (lastprimary, '\0', lastprimarylength + 1);
1179   lastsecondarylength = 100;
1180   lastsecondary = (char *) xmalloc (lastsecondarylength + 1);
1181   memset (lastsecondary, '\0', lastsecondarylength + 1);
1182 }
1183
1184 /* Indexify.  Merge entries for the same name,
1185    insert headers for each initial character, etc.  */
1186
1187 void
1188 indexify (line, ostream)
1189      char *line;
1190      FILE *ostream;
1191 {
1192   char *primary, *secondary, *pagenumber;
1193   int primarylength, secondarylength = 0, pagelength;
1194   int nosecondary;
1195   int initiallength;
1196   char *initial;
1197   char initial1[2];
1198   register char *p;
1199
1200   /* First, analyze the parts of the entry fed to us this time. */
1201
1202   p = find_braced_pos (line, 0, 0, 0);
1203   if (*p == '{')
1204     {
1205       initial = p;
1206       /* Get length of inner pair of braces starting at `p',
1207          including that inner pair of braces.  */
1208       initiallength = find_braced_end (p + 1) + 1 - p;
1209     }
1210   else
1211     {
1212       initial = initial1;
1213       initial1[0] = *p;
1214       initial1[1] = 0;
1215       initiallength = 1;
1216
1217       if (initial1[0] >= 'a' && initial1[0] <= 'z')
1218         initial1[0] -= 040;
1219     }
1220
1221   pagenumber = find_braced_pos (line, 1, 0, 0);
1222   pagelength = find_braced_end (pagenumber) - pagenumber;
1223   if (pagelength == 0)
1224     fatal (_("No page number in %s"), line);
1225
1226   primary = find_braced_pos (line, 2, 0, 0);
1227   primarylength = find_braced_end (primary) - primary;
1228
1229   secondary = find_braced_pos (line, 3, 0, 0);
1230   nosecondary = !*secondary;
1231   if (!nosecondary)
1232     secondarylength = find_braced_end (secondary) - secondary;
1233
1234   /* If the primary is different from before, make a new primary entry. */
1235   if (strncmp (primary, lastprimary, primarylength))
1236     {
1237       /* Close off current secondary entry first, if one is open. */
1238       if (pending)
1239         {
1240           fputs ("}\n", ostream);
1241           pending = 0;
1242         }
1243
1244       /* If this primary has a different initial, include an entry for
1245          the initial. */
1246       if (initiallength != lastinitiallength ||
1247           strncmp (initial, lastinitial, initiallength))
1248         {
1249           fprintf (ostream, "\\initial {");
1250           fwrite (initial, 1, initiallength, ostream);
1251           fputs ("}\n", ostream);
1252           if (initial == initial1)
1253             {
1254               lastinitial = lastinitial1;
1255               *lastinitial1 = *initial1;
1256             }
1257           else
1258             {
1259               lastinitial = initial;
1260             }
1261           lastinitiallength = initiallength;
1262         }
1263
1264       /* Make the entry for the primary.  */
1265       if (nosecondary)
1266         fputs ("\\entry {", ostream);
1267       else
1268         fputs ("\\primary {", ostream);
1269       fwrite (primary, primarylength, 1, ostream);
1270       if (nosecondary)
1271         {
1272           fputs ("}{", ostream);
1273           pending = 1;
1274         }
1275       else
1276         fputs ("}\n", ostream);
1277
1278       /* Record name of most recent primary. */
1279       if (lastprimarylength < primarylength)
1280         {
1281           lastprimarylength = primarylength + 100;
1282           lastprimary = (char *) xrealloc (lastprimary,
1283                                            1 + lastprimarylength);
1284         }
1285       strncpy (lastprimary, primary, primarylength);
1286       lastprimary[primarylength] = 0;
1287
1288       /* There is no current secondary within this primary, now. */
1289       lastsecondary[0] = 0;
1290     }
1291
1292   /* Should not have an entry with no subtopic following one with a subtopic. */
1293
1294   if (nosecondary && *lastsecondary)
1295     error (_("entry %s follows an entry with a secondary name"), line);
1296
1297   /* Start a new secondary entry if necessary. */
1298   if (!nosecondary && strncmp (secondary, lastsecondary, secondarylength))
1299     {
1300       if (pending)
1301         {
1302           fputs ("}\n", ostream);
1303           pending = 0;
1304         }
1305
1306       /* Write the entry for the secondary.  */
1307       fputs ("\\secondary {", ostream);
1308       fwrite (secondary, secondarylength, 1, ostream);
1309       fputs ("}{", ostream);
1310       pending = 1;
1311
1312       /* Record name of most recent secondary. */
1313       if (lastsecondarylength < secondarylength)
1314         {
1315           lastsecondarylength = secondarylength + 100;
1316           lastsecondary = (char *) xrealloc (lastsecondary,
1317                                              1 + lastsecondarylength);
1318         }
1319       strncpy (lastsecondary, secondary, secondarylength);
1320       lastsecondary[secondarylength] = 0;
1321     }
1322
1323   /* Here to add one more page number to the current entry. */
1324   if (pending++ != 1)
1325     fputs (", ", ostream);      /* Punctuate first, if this is not the first. */
1326   fwrite (pagenumber, pagelength, 1, ostream);
1327 }
1328
1329 /* Close out any unfinished output entry. */
1330
1331 void
1332 finish_index (ostream)
1333      FILE *ostream;
1334 {
1335   if (pending)
1336     fputs ("}\n", ostream);
1337   free (lastprimary);
1338   free (lastsecondary);
1339 }
1340 \f
1341 /* Copy the lines in the sorted order.
1342    Each line is copied out of the input file it was found in. */
1343
1344 void
1345 writelines (linearray, nlines, ostream)
1346      char **linearray;
1347      int nlines;
1348      FILE *ostream;
1349 {
1350   char **stop_line = linearray + nlines;
1351   char **next_line;
1352
1353   init_index ();
1354
1355   /* Output the text of the lines, and free the buffer space. */
1356
1357   for (next_line = linearray; next_line != stop_line; next_line++)
1358     {
1359       /* If -u was specified, output the line only if distinct from previous one.  */
1360       if (next_line == linearray
1361       /* Compare previous line with this one, using only the
1362          explicitly specd keyfields. */
1363           || compare_general (*(next_line - 1), *next_line, 0L, 0L, num_keyfields - 1))
1364         {
1365           char *p = *next_line;
1366           char c;
1367
1368           while ((c = *p++) && c != '\n')
1369             /* Do nothing. */ ;
1370           *(p - 1) = 0;
1371           indexify (*next_line, ostream);
1372         }
1373     }
1374
1375   finish_index (ostream);
1376 }
1377 \f
1378 /* Assume (and optionally verify) that each input file is sorted;
1379    merge them and output the result.
1380    Returns nonzero if any input file fails to be sorted.
1381
1382    This is the high-level interface that can handle an unlimited
1383    number of files.  */
1384
1385 #define MAX_DIRECT_MERGE 10
1386
1387 int
1388 merge_files (infiles, nfiles, outfile)
1389      char **infiles;
1390      int nfiles;
1391      char *outfile;
1392 {
1393   char **tempfiles;
1394   int ntemps;
1395   int i;
1396   int value = 0;
1397   int start_tempcount = tempcount;
1398
1399   if (nfiles <= MAX_DIRECT_MERGE)
1400     return merge_direct (infiles, nfiles, outfile);
1401
1402   /* Merge groups of MAX_DIRECT_MERGE input files at a time,
1403      making a temporary file to hold each group's result.  */
1404
1405   ntemps = (nfiles + MAX_DIRECT_MERGE - 1) / MAX_DIRECT_MERGE;
1406   tempfiles = (char **) xmalloc (ntemps * sizeof (char *));
1407   for (i = 0; i < ntemps; i++)
1408     {
1409       int nf = MAX_DIRECT_MERGE;
1410       if (i + 1 == ntemps)
1411         nf = nfiles - i * MAX_DIRECT_MERGE;
1412       tempfiles[i] = maketempname (++tempcount);
1413       value |= merge_direct (&infiles[i * MAX_DIRECT_MERGE], nf, tempfiles[i]);
1414     }
1415
1416   /* All temporary files that existed before are no longer needed
1417      since their contents have been merged into our new tempfiles.
1418      So delete them.  */
1419   flush_tempfiles (start_tempcount);
1420
1421   /* Now merge the temporary files we created.  */
1422
1423   merge_files (tempfiles, ntemps, outfile);
1424
1425   free (tempfiles);
1426
1427   return value;
1428 }
1429 \f
1430 /* Assume (and optionally verify) that each input file is sorted;
1431    merge them and output the result.
1432    Returns nonzero if any input file fails to be sorted.
1433
1434    This version of merging will not work if the number of
1435    input files gets too high.  Higher level functions
1436    use it only with a bounded number of input files.  */
1437
1438 int
1439 merge_direct (infiles, nfiles, outfile)
1440      char **infiles;
1441      int nfiles;
1442      char *outfile;
1443 {
1444   struct linebuffer *lb1, *lb2;
1445   struct linebuffer **thisline, **prevline;
1446   FILE **streams;
1447   int i;
1448   int nleft;
1449   int lossage = 0;
1450   int *file_lossage;
1451   struct linebuffer *prev_out = 0;
1452   FILE *ostream = stdout;
1453
1454   if (outfile)
1455     {
1456       ostream = fopen (outfile, "w");
1457     }
1458   if (!ostream)
1459     pfatal_with_name (outfile);
1460
1461   init_index ();
1462
1463   if (nfiles == 0)
1464     {
1465       if (outfile)
1466         fclose (ostream);
1467       return 0;
1468     }
1469
1470   /* For each file, make two line buffers.
1471      Also, for each file, there is an element of `thisline'
1472      which points at any time to one of the file's two buffers,
1473      and an element of `prevline' which points to the other buffer.
1474      `thisline' is supposed to point to the next available line from the file,
1475      while `prevline' holds the last file line used,
1476      which is remembered so that we can verify that the file is properly sorted. */
1477
1478   /* lb1 and lb2 contain one buffer each per file. */
1479   lb1 = (struct linebuffer *) xmalloc (nfiles * sizeof (struct linebuffer));
1480   lb2 = (struct linebuffer *) xmalloc (nfiles * sizeof (struct linebuffer));
1481
1482   /* thisline[i] points to the linebuffer holding the next available line in file i,
1483      or is zero if there are no lines left in that file.  */
1484   thisline = (struct linebuffer **)
1485     xmalloc (nfiles * sizeof (struct linebuffer *));
1486   /* prevline[i] points to the linebuffer holding the last used line
1487      from file i.  This is just for verifying that file i is properly
1488      sorted.  */
1489   prevline = (struct linebuffer **)
1490     xmalloc (nfiles * sizeof (struct linebuffer *));
1491   /* streams[i] holds the input stream for file i.  */
1492   streams = (FILE **) xmalloc (nfiles * sizeof (FILE *));
1493   /* file_lossage[i] is nonzero if we already know file i is not
1494      properly sorted.  */
1495   file_lossage = (int *) xmalloc (nfiles * sizeof (int));
1496
1497   /* Allocate and initialize all that storage. */
1498
1499   for (i = 0; i < nfiles; i++)
1500     {
1501       initbuffer (&lb1[i]);
1502       initbuffer (&lb2[i]);
1503       thisline[i] = &lb1[i];
1504       prevline[i] = &lb2[i];
1505       file_lossage[i] = 0;
1506       streams[i] = fopen (infiles[i], "r");
1507       if (!streams[i])
1508         pfatal_with_name (infiles[i]);
1509
1510       readline (thisline[i], streams[i]);
1511     }
1512
1513   /* Keep count of number of files not at eof. */
1514   nleft = nfiles;
1515
1516   while (nleft)
1517     {
1518       struct linebuffer *best = 0;
1519       struct linebuffer *exch;
1520       int bestfile = -1;
1521       int i;
1522
1523       /* Look at the next avail line of each file; choose the least one.  */
1524
1525       for (i = 0; i < nfiles; i++)
1526         {
1527           if (thisline[i] &&
1528               (!best ||
1529                0 < compare_general (best->buffer, thisline[i]->buffer,
1530                                  (long) bestfile, (long) i, num_keyfields)))
1531             {
1532               best = thisline[i];
1533               bestfile = i;
1534             }
1535         }
1536
1537       /* Output that line, unless it matches the previous one and we
1538          don't want duplicates. */
1539
1540       if (!(prev_out &&
1541             !compare_general (prev_out->buffer,
1542                               best->buffer, 0L, 1L, num_keyfields - 1)))
1543         indexify (best->buffer, ostream);
1544       prev_out = best;
1545
1546       /* Now make the line the previous of its file, and fetch a new
1547          line from that file.  */
1548
1549       exch = prevline[bestfile];
1550       prevline[bestfile] = thisline[bestfile];
1551       thisline[bestfile] = exch;
1552
1553       while (1)
1554         {
1555           /* If the file has no more, mark it empty. */
1556
1557           if (feof (streams[bestfile]))
1558             {
1559               thisline[bestfile] = 0;
1560               /* Update the number of files still not empty. */
1561               nleft--;
1562               break;
1563             }
1564           readline (thisline[bestfile], streams[bestfile]);
1565           if (thisline[bestfile]->buffer[0] || !feof (streams[bestfile]))
1566             break;
1567         }
1568     }
1569
1570   finish_index (ostream);
1571
1572   /* Free all storage and close all input streams. */
1573
1574   for (i = 0; i < nfiles; i++)
1575     {
1576       fclose (streams[i]);
1577       free (lb1[i].buffer);
1578       free (lb2[i].buffer);
1579     }
1580   free (file_lossage);
1581   free (lb1);
1582   free (lb2);
1583   free (thisline);
1584   free (prevline);
1585   free (streams);
1586
1587   if (outfile)
1588     fclose (ostream);
1589
1590   return lossage;
1591 }
1592 \f
1593 /* Print error message and exit.  */
1594
1595 void
1596 fatal (format, arg)
1597      char *format, *arg;
1598 {
1599   error (format, arg);
1600   xexit (1);
1601 }
1602
1603 /* Print error message.  FORMAT is printf control string, ARG is arg for it. */
1604 void
1605 error (format, arg)
1606      char *format, *arg;
1607 {
1608   printf ("%s: ", program_name);
1609   printf (format, arg);
1610   if (format[strlen (format) -1] != '\n')
1611     printf ("\n");
1612 }
1613
1614 void
1615 perror_with_name (name)
1616      char *name;
1617 {
1618   char *s;
1619
1620   s = strerror (errno);
1621   printf ("%s: ", program_name);
1622   printf ("%s; for file `%s'.\n", s, name);
1623 }
1624
1625 void
1626 pfatal_with_name (name)
1627      char *name;
1628 {
1629   char *s;
1630
1631   s = strerror (errno);
1632   printf ("%s: ", program_name);
1633   printf (_("%s; for file `%s'.\n"), s, name);
1634   xexit (1);
1635 }
1636
1637 /* Return a newly-allocated string whose contents concatenate those of
1638    S1, S2, S3.  */
1639
1640 char *
1641 concat (s1, s2, s3)
1642      char *s1, *s2, *s3;
1643 {
1644   int len1 = strlen (s1), len2 = strlen (s2), len3 = strlen (s3);
1645   char *result = (char *) xmalloc (len1 + len2 + len3 + 1);
1646
1647   strcpy (result, s1);
1648   strcpy (result + len1, s2);
1649   strcpy (result + len1 + len2, s3);
1650   *(result + len1 + len2 + len3) = 0;
1651
1652   return result;
1653 }
1654
1655 #if !defined (HAVE_STRCHR)
1656 char *
1657 strrchr (string, character)
1658      char *string;
1659      int character;
1660 {
1661   register int i;
1662
1663   for (i = strlen (string) - 1; i > -1; i--)
1664     if (string[i] == character)
1665       return (string + i);
1666
1667   return ((char *)NULL);
1668 }
1669 #endif /* HAVE_STRCHR */