summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/cwebdir/twinx.w
blob: ecfce0c8da823e926192e0347d6f1ecf113b9199 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
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 cttwinxmac\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.