summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/cwebdir/twinx.w
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2019-01-06 23:19:16 +0000
committerKarl Berry <karl@freefriends.org>2019-01-06 23:19:16 +0000
commit976f2b9b61a086f8594f6bfe6dbea42faa56edb2 (patch)
tree9e620153df80a27b0304ae9827fa0f69a02191e0 /Build/source/texk/web2c/cwebdir/twinx.w
parentb109e3c47399f4fdfc7805b8f9168c7452f78e96 (diff)
cwebbin for cweb, from Andreas Scherer https://github.com/ascherer/cwebbin)
git-svn-id: svn://tug.org/texlive/trunk@49626 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/web2c/cwebdir/twinx.w')
-rw-r--r--Build/source/texk/web2c/cwebdir/twinx.w460
1 files changed, 460 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/cwebdir/twinx.w b/Build/source/texk/web2c/cwebdir/twinx.w
new file mode 100644
index 00000000000..c49906fa4e0
--- /dev/null
+++ b/Build/source/texk/web2c/cwebdir/twinx.w
@@ -0,0 +1,460 @@
+\datethis
+
+@*Introduction. This short program compiles a master index for a
+set of programs that have been processed by \.{CTWILL}.
+To use it, you say, e.g., \.{twinx} \.{*.tex} \.{>index.tex}.
+The individual programs should define their names with a line of
+the form `\.{\\def\\title\{NAME\}}'.
+
+@c
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+@<Type definitions@>@;
+@<Global variables@>@;
+@<Procedures@>@;
+@#
+int main(
+ int argc,
+ char *argv[])
+{ @<Local variables@>;
+ @<Initialize the data structures@>;
+ while (--argc) {
+ f=fopen(*++argv,"r");
+ if (!f)
+ fprintf(stderr,"twinx: Couldn't open file %s for reading!\n",*argv);
+ else {
+ @<Scan file |f| until coming to the title@>;
+ fclose(f);
+ strncpy(*argv+strlen(*argv)-3,"idx",3);
+ f=fopen(*argv,"r");
+ if (!f)
+ fprintf(stderr,"twinx: Couldn't open file %s for reading!\n",*argv);
+ else {
+ @<Copy the index file |f| into the data structures@>;
+ fclose(f);
+ }
+ }
+ }
+ @<Output the data structures to make a master index@>;
+ return 0;
+}
+
+@ @d buf_size 100 /* input lines won't be this long */
+
+@<Glob...@>=
+FILE *f;
+char buf[buf_size];
+char title[buf_size];
+char cur_name[buf_size];
+
+@ @<Scan file |f|...@>=
+while (1) {
+ if (fgets(buf,buf_size,f)==NULL) {
+ fprintf(stderr,"twinx: (no title found in file %s)\n",*argv);
+ title[0]='\0';
+ break;
+ }
+ if (strncmp(buf,"\\def\\title\{",11)==0) {@+register char *p,*q;
+ for (p=buf+11,q=title;*p && *p!='}';p++) *q++=*p;
+ *q='\0';
+ break;
+ }
+}
+
+@* Data structures.
+Our main task is to collate a bunch of texts associated with keys that
+have already been sorted. It seems easiest to do this by repeatedly merging
+the new data into the old, even though this means we'll be passing over
+some of the same keys 30 times or more; the computer is fast, and this
+program won't be run often.
+
+Further examination shows that a merging strategy isn't so easy after all,
+because the sorting done by \.{CTWILL} (and by \.{CWEAVE}) is weird
+in certain cases. When two index entries agree except for their
+``ilk,'' the order in which they appear in the index depends on the order in
+which they appear in the program. Thus, they might well appear in
+different order in two of the indexes we are merging.
+(There's also another glitch, although not quite as devasting:
+When two index entries have the
+same letters and the same ilk, but differ with respect to uppercase
+versus lowercase, the order in which they appear depends on the
+hash code used in \.{CWEB}'s \.{common.w} code!)
+
+So we'll use Plan B: All index entries will first be copied into a long
+list. The list will almost always consist of many sorted sublists,
+but we will not assume anything about its order. After all the copying
+has been done, we will use a list-merge sort to finish the job.
+
+The data structure is built from nodes that each contain three pointers.
+The first pointer is to an |id| string; the third pointer is to the
+|next| node; and the second pointer is either |data.s|, a pointer to
+a string of text, or |data.n|, a pointer to a node. In the main list,
+the |id| fields are the keys of the index, and the |data.n| fields
+point to lists of associated texts. In the latter lists, the |id| fields
+are the individual program titles, while the |data.s| fields are the
+texts.
+
+@<Type...@>=
+typedef union {
+ char *s;
+ struct node_struct *n;
+} mixed;
+typedef struct node_struct {
+ const char *id;
+ mixed data;
+ struct node_struct *next;
+} node;
+
+@ We copy strings into blocks of storage that are allocated as needed.
+Here's a routine that stashes away a given string. It makes no attempt to
+handle extremely long strings, because such strings will arise only
+if the input is all screwed up.
+
+@d string_block_size 8192 /* number of bytes per string block */
+
+@<Proc...@>=
+char *save_string(
+ char *s)
+{
+ register char *p,*q; register int l;
+ for (p=s;*p;p++) ;
+ l=p-s+1;
+ if (l>string_block_size) {
+ fprintf(stderr,"twinx: Huge string `%.20s...' will be truncated!\n",s);
+ l=string_block_size;
+ s[l-1]='\0';
+ }
+ if (next_string+l>=bad_string) {
+ next_string=(char*)malloc(string_block_size);
+ if (next_string==NULL) {
+ fprintf(stderr,"twinx: Not enough room for strings!\n");
+ exit(-1);
+ }
+ bad_string=next_string+string_block_size;
+ }
+ for (p=s,q=next_string;*p;p++) *q++=*p;
+ *q='\0';
+ next_string=q+1;
+ return next_string-l;
+}
+
+@ Nodes are allocated with a similar but simpler mechanism.
+
+@d nodes_per_block 340
+
+@<Proc...@>=
+node *new_node(void)
+{
+ if (next_node==bad_node) {
+ next_node=(node*)calloc(nodes_per_block,sizeof(node));
+ if (next_node==NULL) {
+ fprintf(stderr,"twinx: Not enough room for nodes!\n");
+ exit(-2);
+ }
+ bad_node=next_node+nodes_per_block;
+ }
+ next_node++;
+ return next_node-1;
+}
+
+@ @<Glob...@>=
+char *next_string,*bad_string;
+node *next_node,*bad_node;
+node header; /* the main list begins at |header.next| */
+node sentinel; /* intermediate lists will end at this node */
+
+@ We don't really have to initialize the string and node storage
+pointers, because global variables are zero already. But we might as
+well be tidy and state the initial conditions explicitly.
+
+It will be convenient to have extremely small and large keys in
+the dummy nodes.
+
+@<Initialize the data structures@>=
+next_string=bad_string=NULL;
+next_node=bad_node=NULL;
+header.next=NULL;
+header.id=" {"; /* smaller than any valid |id| */
+sentinel.id=" {\200}"; /* larger than any valid |id| */
+main_node=&header;
+
+@ @<Local v...@>=
+register node* main_node; /* current end of main list */
+
+@* Copying.
+Lines in the index file |f| that we're reading either begin a new
+entry or continue a long entry. In the first case, the line begins with
+\.{\\I} and then either \.{\\\\\{key\}} or \.{\\\char'174\{key\}} or
+\.{\\.\{key\}} or \.{\\\&\{key\}} or \.{\\\$\{key\}} or \.{\\9\{key\}}
+or just \.{\ \ \{key\}}. (These correspond to multi-character italic,
+single-digit italic, typewriter, bold, custom, variable, and roman styles.)
+In the second case, the line begins with a page number or \.{\\[};
+however, we recognize the second case by the fact that the previous line
+did not end with a period.
+
+@<Copy the index...@>=
+while (1) {@+register node *cur_node;
+ if (fgets(buf,buf_size,f)==NULL) break; /* end of file */
+ if (strncmp(buf,"\\I",2)==0) {
+ @<Copy a new index entry into |cur_name| and |cur_node|@>;
+ main_node->next=new_node();@+main_node=main_node->next;
+ main_node->id=save_string(cur_name);
+ main_node->data.n=cur_node;
+ }
+ else if (buf[0]!='\n')
+ fprintf(stderr,"twinx: couldn't deal with `%.10s...' in file %s!\n",
+ buf,*argv);
+}
+
+@ @<Copy a new index entry...@>=
+if (buf[4]!='{') {
+ fprintf(stderr,"twinx: missing brace in file %s: `%.20s...'\n",*argv,buf);
+ break;
+}
+{@+register char *p,*q;@+register int bal=1;
+ cur_name[0]=buf[2];@+cur_name[1]=buf[3];@+cur_name[2]='{';
+ for (p=buf+5,q=cur_name+3;*p&&(bal||*p=='{');p++) {
+ if (*p=='{') bal++;
+ else if (*p=='}') bal--;
+ *q++=*p;
+ }
+ if (bal) {
+ fprintf(stderr,"twinx: unbalanced entry in file %s: `%.20s...'\n",*argv,buf);
+ break;
+ }
+ if (*p++!=',') {
+ fprintf(stderr,"twinx: missing comma in file %s: `%.20s...'\n",*argv,buf);
+ break;
+ }
+ if (*p++!=' ') {
+ fprintf(stderr,"twinx: missing space in file %s: `%.20s...'\n",*argv,buf);
+ break;
+ }
+ *q='\0';
+ @<Copy the text part of the index entry into |cur_node|@>;
+}
+
+@ When we get here, |p| points to the beginning of the text following a key
+in the index. The index entry ends with the next period, possibly several
+lines hence. In the multiple-line case, |cur_node| will point to the
+final line, which points to the penultimate line, etc.
+
+@<Copy the text part of the index entry...@>=
+{@+int period_sensed=0;
+ node *continuation;
+ cur_node=new_node();
+ cur_node->id=save_string(title);
+ do@+{
+ for (q=p;*q&&*q!='\n'&&*q!='.';q++) ;
+ if (*q=='.') period_sensed=1;
+ *q='\0';
+ cur_node->data.s=save_string(p);
+ if (period_sensed) break;
+ continuation=new_node(); /* the |id| field is |NULL| */
+ continuation->next=cur_node;
+ cur_node=continuation;
+ p=buf;
+ }@+while(fgets(buf,buf_size,f));
+ if (!period_sensed) {
+ fprintf(stderr,"twinx: File %s ended in middle of entry for %s!\n",
+ *argv,cur_name);
+ break;
+ }
+}
+
+@* Sorting.
+Let us opt for simplicity instead of tuning up for speed. The idea in
+this step is to take a list that contains $k$ ascending runs and reduce it
+to a list that contains $\lceil k/2\rceil$ runs, repeating until $k=1$.
+We could make the program about twice as fast if we took the trouble to
+remember the boundaries of runs on the previous pass; here, every
+pass will be the same.
+
+@<Output the data structures to make a master index@>=
+@<Sort the main list, collapsing entries with the same |id|@>;
+@<Output the main list in suitable \TeX\ format@>;
+
+@ The |compare| subroutine, which specifies the relative order of
+|id| fields in two nodes, appears below. Let's get the sorting logic
+right first.
+
+The algorithm is, in fact, rather pretty---I hate to say cute, but
+that's the word that comes to mind. Some day I must write out the
+nice invariant relations in these loops. Too bad it's not more efficient.
+
+Remember that |header.id| is $-\infty$ and |sentinel.id| is $+\infty$.
+Also remember that the main list begins and ends at the header node.
+
+@<Sort the main list, collapsing entries with the same |id|@>=
+main_node->next=&header;
+while (1) {@+register node *p,*q,*r,*s,*t;
+ t=&header;
+ r=t->next;
+ while (1) {
+ if (r==&header) break;
+ p=s=r;
+ @<Advance |s| until it exceeds |r=s->next|@>;
+ if (r==&header) break;
+ s->next=&sentinel;
+ q=s=r;
+ @<Advance |s| until it exceeds |r=s->next|@>;
+ s->next=&sentinel;
+ @<Merge |p| and |q|, appending to |t|@>;
+ t->next=r;
+ }
+ if (t==&header) break;
+}
+
+@ @<Advance...@>=
+do@+{@+register int d;
+ r=s->next;
+ d=compare(s,r);
+ if (d>0) break; /* |s->id>r->id| */
+ if (d==0) { /* |s->id=r->id| */
+ collapse(s,r); /* put |r|'s data into |s|'s list */
+ s->next=r->next; /* node |r| will be unclaimed garbage */
+ } else s=r; /* this is the normal case, |s->id<r->id| */
+}@+while(1);
+
+@ Merging takes place in such a way that sorting is stable.
+Thus, index entries for a key that appears in different programs
+will remain in the order of the \.{.tex} files on the command line.
+
+@<Merge...@>=
+do@+{@+register int d;
+ d=compare(p,q);
+ if (d>0) { /* |p->id>q->id| */
+ t->next=q;
+ t=q;
+ q=q->next;
+ } else if (d<0) { /* |p->id<q->id| */
+ t->next=p; /* |p->id<q->id| */
+ t=p;
+ p=p->next;
+ } else if (p==&sentinel) break;
+ else {
+ collapse(p,q); /* put |q|'s data into |p|'s list */
+ q=q->next;
+ }
+}@+while(1);
+
+@ Comparison is a three-stage process in general. First we compare the
+keys without regarding case or format type. If they are equal with
+respect to that criterion, we try again, with case significant.
+If they are still equal, we look at the format characters (the first
+two characters of the |id| field).
+
+@<Proc...@>=
+int compare(
+ node *p, node *q)
+{@+register unsigned char *pp,*qq;
+ for (pp=(unsigned char*)p->id+3,qq=(unsigned char*)q->id+3;
+ *pp&&ord[*pp]==ord[*qq];pp++,qq++) ;
+ if (*pp || *qq) return ord[*pp]-ord[*qq];
+ for (pp=(unsigned char*)p->id+3,qq=(unsigned char*)q->id+3;
+ *pp&&*pp==*qq;pp++,qq++) ;
+ if (*pp || *qq) return (int)*pp-(int)*qq;
+ if (p->id[0]!=q->id[0]) return p->id[0]-q->id[0];
+ return p->id[1]-q->id[1];
+}
+
+@ The collation order follows a string copied from \.{CWEAVE}.
+
+@<Glob...@>=
+char collate[102]; /* collation order */
+char ord[256]; /* rank in collation order */
+
+@ The right brace is placed lowest in collating order, because each
+key is actually followed by a right brace when we are sorting.
+
+Apology: I haven't had time to update this part of the program to
+allow 8-bit characters. At present the data is assumed to be
+7-bit ASCII, as it was in the early versions of \.{CWEAVE}.
+
+@<Init...@>=
+collate[0]=0; strcpy(collate+1,"} \1\2\3\4\5\6\7\10\11\12\13\14\15\16\17\
+\20\21\22\23\24\25\26\27\30\31\32\33\34\35\36\37\
+!\42#$%&'()*+,-./:;<=>?@@[\\]^`{|~_\
+abcdefghijklmnopqrstuvwxyz0123456789");
+{@+register int j;
+ for (j=1;collate[j];j++) ord[(int)collate[j]]=j;
+ ord[128]=j; /* this affects the ordering of |sentinel.id| */
+ for (j='A';j<='Z';j++) ord[j]=ord[tolower(j)];
+}
+
+@ When two lists are combined, we put the data from the second node
+before the data from the first node, because we are going to reverse
+the order when printing. After this procedure has acted, the field
+|q->data.n| should not be considered an active pointer.
+
+@<Proc...@>=
+void collapse(
+ node *p, node *q)
+{@+register node *x;
+ for (x=q->data.n;x->next;x=x->next) ;
+ x->next=p->data.n;
+ p->data.n=q->data.n;
+}
+
+@ The only remaining trick is to format the underline characters
+properly, especially in the ``custom'' format when they must become
+\.x's.
+
+@<Output the main list in suitable \TeX\ format@>=
+{@+register node *x;
+ printf("\\input twinxmac\n");
+ for (x=header.next;x!=&header;x=x->next) {
+ printf("\\I");
+ @<Output |x->id| in suitable \TeX\ format@>;
+ @<Output the lines of |x->data.n| in reverse order@>;
+ }
+ printf("\\fin\n");
+}
+
+@ @<Output |x->id|...@>=
+{@+register const char *p=x->id;
+ if (*p==' ') {
+ if (*(p+1)!=' ') goto unknown;
+ goto known;
+ }
+ if (*p!='\\') goto unknown;
+ switch (*(p+1)) {
+ case '\\': case '|': case '.': case '&': case '9':
+ printf("\\%c",*(p+1));
+ goto known;
+ case '$': printf("$\\");
+ for (p+=3;*p!='}';p++)
+ if (*p=='_') putchar('x');
+ else putchar(*p);
+ putchar('$');
+ goto done;
+ default: goto unknown;
+ }
+ unknown: fprintf(stderr,"twinx: `%s' has unknown format!\n",p);
+ known: for (p+=2;*p;p++) {
+ if (*p=='_') putchar('\\');
+ putchar(*p);
+ }
+done:;
+}
+
+@ @<Output the lines of |x->data.n| in reverse order@>=
+{@+register node *y=x->data.n,*z=NULL;
+ while (y) {@+register node *w;
+ w=y->next;
+ y->next=z;
+ z=y;
+ y=w;
+ }
+ while (z) {
+ if (z->id) printf("\\unskip, {\\sc %s}~",z->id);
+ fputs(z->data.s,stdout);
+ z=z->next;
+ if (z) putchar('\n');
+ else puts(".");
+ }
+}
+
+@* Index.