1db202179Sdist /*
2*ef4413e0Sbostic * Copyright (c) 1980, 1993
3*ef4413e0Sbostic * The Regents of the University of California. All rights reserved.
4b08c0a32Sbostic *
571b0a924Sbostic * %sccs.include.redist.c%
6db202179Sdist */
7db202179Sdist
8e03c1f43Ssam #ifndef lint
9*ef4413e0Sbostic static char copyright[] =
10*ef4413e0Sbostic "@(#) Copyright (c) 1980, 1993\n\
11*ef4413e0Sbostic The Regents of the University of California. All rights reserved.\n";
12b08c0a32Sbostic #endif /* not lint */
13db202179Sdist
14db202179Sdist #ifndef lint
15*ef4413e0Sbostic static char sccsid[] = "@(#)checknr.c 8.1 (Berkeley) 06/06/93";
16b08c0a32Sbostic #endif /* not lint */
17db202179Sdist
18215f343dSbill /*
19215f343dSbill * checknr: check an nroff/troff input file for matching macro calls.
20215f343dSbill * we also attempt to match size and font changes, but only the embedded
21215f343dSbill * kind. These must end in \s0 and \fP resp. Maybe more sophistication
22215f343dSbill * later but for now think of these restrictions as contributions to
23215f343dSbill * structured typesetting.
24215f343dSbill */
25215f343dSbill #include <stdio.h>
26215f343dSbill #include <ctype.h>
27215f343dSbill
28215f343dSbill #define MAXSTK 100 /* Stack size */
29215f343dSbill #define MAXBR 100 /* Max number of bracket pairs known */
30215f343dSbill #define MAXCMDS 500 /* Max number of commands known */
31215f343dSbill
32215f343dSbill /*
33215f343dSbill * The stack on which we remember what we've seen so far.
34215f343dSbill */
35215f343dSbill struct stkstr {
36215f343dSbill int opno; /* number of opening bracket */
37215f343dSbill int pl; /* '+', '-', ' ' for \s, 1 for \f, 0 for .ft */
38215f343dSbill int parm; /* parm to size, font, etc */
39215f343dSbill int lno; /* line number the thing came in in */
40215f343dSbill } stk[MAXSTK];
41215f343dSbill int stktop;
42215f343dSbill
43215f343dSbill /*
44215f343dSbill * The kinds of opening and closing brackets.
45215f343dSbill */
46215f343dSbill struct brstr {
47215f343dSbill char *opbr;
48215f343dSbill char *clbr;
49215f343dSbill } br[MAXBR] = {
50215f343dSbill /* A few bare bones troff commands */
51215f343dSbill #define SZ 0
52215f343dSbill "sz", "sz", /* also \s */
53215f343dSbill #define FT 1
54215f343dSbill "ft", "ft", /* also \f */
5510a67484Sroot /* the -mm package */
5610a67484Sroot "AL", "LE",
5710a67484Sroot "AS", "AE",
5810a67484Sroot "BL", "LE",
5910a67484Sroot "BS", "BE",
6010a67484Sroot "DF", "DE",
6110a67484Sroot "DL", "LE",
6210a67484Sroot "DS", "DE",
6310a67484Sroot "FS", "FE",
6410a67484Sroot "ML", "LE",
6510a67484Sroot "NS", "NE",
6610a67484Sroot "RL", "LE",
6710a67484Sroot "VL", "LE",
68215f343dSbill /* the -ms package */
69215f343dSbill "AB", "AE",
70e03c1f43Ssam "BD", "DE",
71215f343dSbill "CD", "DE",
7210a67484Sroot "DS", "DE",
7310a67484Sroot "FS", "FE",
74215f343dSbill "ID", "DE",
75215f343dSbill "KF", "KE",
7610a67484Sroot "KS", "KE",
7710a67484Sroot "LD", "DE",
7810a67484Sroot "LG", "NL",
79215f343dSbill "QS", "QE",
8010a67484Sroot "RS", "RE",
8110a67484Sroot "SM", "NL",
82e03c1f43Ssam "XA", "XE",
83e03c1f43Ssam "XS", "XE",
84215f343dSbill /* The -me package */
85215f343dSbill "(b", ")b",
86215f343dSbill "(c", ")c",
87215f343dSbill "(d", ")d",
88215f343dSbill "(f", ")f",
8910a67484Sroot "(l", ")l",
9010a67484Sroot "(q", ")q",
91215f343dSbill "(x", ")x",
9210a67484Sroot "(z", ")z",
9310a67484Sroot /* Things needed by preprocessors */
9410a67484Sroot "EQ", "EN",
9510a67484Sroot "TS", "TE",
9610a67484Sroot /* Refer */
9710a67484Sroot "[", "]",
98215f343dSbill 0, 0
99215f343dSbill };
100215f343dSbill
101215f343dSbill /*
10210a67484Sroot * All commands known to nroff, plus macro packages.
103215f343dSbill * Used so we can complain about unrecognized commands.
104215f343dSbill */
105215f343dSbill char *knowncmds[MAXCMDS] = {
10610a67484Sroot "$c", "$f", "$h", "$p", "$s", "(b", "(c", "(d", "(f", "(l", "(q", "(t",
10710a67484Sroot "(x", "(z", ")b", ")c", ")d", ")f", ")l", ")q", ")t", ")x", ")z", "++",
10810a67484Sroot "+c", "1C", "1c", "2C", "2c", "@(", "@)", "@C", "@D", "@F", "@I", "@M",
10910a67484Sroot "@c", "@e", "@f", "@h", "@m", "@n", "@o", "@p", "@r", "@t", "@z", "AB",
110e03c1f43Ssam "AE", "AF", "AI", "AL", "AM", "AS", "AT", "AU", "AX", "B", "B1", "B2",
111e03c1f43Ssam "BD", "BE", "BG", "BL", "BS", "BT", "BX", "C1", "C2", "CD", "CM", "CT",
112e03c1f43Ssam "D", "DA", "DE", "DF", "DL", "DS", "DT", "EC", "EF", "EG", "EH", "EM",
113e03c1f43Ssam "EN", "EQ", "EX", "FA", "FD", "FE", "FG", "FJ", "FK", "FL", "FN", "FO",
114e03c1f43Ssam "FQ", "FS", "FV", "FX", "H", "HC", "HD", "HM", "HO", "HU", "I", "ID",
115e03c1f43Ssam "IE", "IH", "IM", "IP", "IX", "IZ", "KD", "KE", "KF", "KQ", "KS", "LB",
116e03c1f43Ssam "LC", "LD", "LE", "LG", "LI", "LP", "MC", "ME", "MF", "MH", "ML", "MR",
117e03c1f43Ssam "MT", "ND", "NE", "NH", "NL", "NP", "NS", "OF", "OH", "OK", "OP", "P",
118e03c1f43Ssam "P1", "PF", "PH", "PP", "PT", "PX", "PY", "QE", "QP", "QS", "R", "RA",
119e03c1f43Ssam "RC", "RE", "RL", "RP", "RQ", "RS", "RT", "S", "S0", "S2", "S3", "SA",
120a1df2892Sbloom "SG", "SH", "SK", "SM", "SP", "SY", "T&", "TA", "TB", "TC", "TD", "TE",
121a1df2892Sbloom "TH", "TL", "TM", "TP", "TQ", "TR", "TS", "TX", "UL", "US", "UX", "VL",
122a1df2892Sbloom "WC", "WH", "XA", "XD", "XE", "XF", "XK", "XP", "XS", "[", "[-", "[0",
123a1df2892Sbloom "[1", "[2", "[3", "[4", "[5", "[<", "[>", "[]", "]", "]-", "]<", "]>",
124a1df2892Sbloom "][", "ab", "ac", "ad", "af", "am", "ar", "as", "b", "ba", "bc", "bd",
125a1df2892Sbloom "bi", "bl", "bp", "br", "bx", "c.", "c2", "cc", "ce", "cf", "ch", "cs",
126a1df2892Sbloom "ct", "cu", "da", "de", "di", "dl", "dn", "ds", "dt", "dw", "dy", "ec",
127a1df2892Sbloom "ef", "eh", "el", "em", "eo", "ep", "ev", "ex", "fc", "fi", "fl", "fo",
128a1df2892Sbloom "fp", "ft", "fz", "hc", "he", "hl", "hp", "ht", "hw", "hx", "hy", "i",
129a1df2892Sbloom "ie", "if", "ig", "in", "ip", "it", "ix", "lc", "lg", "li", "ll", "ln",
130a1df2892Sbloom "lo", "lp", "ls", "lt", "m1", "m2", "m3", "m4", "mc", "mk", "mo", "n1",
131a1df2892Sbloom "n2", "na", "ne", "nf", "nh", "nl", "nm", "nn", "np", "nr", "ns", "nx",
132a1df2892Sbloom "of", "oh", "os", "pa", "pc", "pi", "pl", "pm", "pn", "po", "pp", "ps",
133a1df2892Sbloom "q", "r", "rb", "rd", "re", "rm", "rn", "ro", "rr", "rs", "rt", "sb",
134a1df2892Sbloom "sc", "sh", "sk", "so", "sp", "ss", "st", "sv", "sz", "ta", "tc", "th",
135a1df2892Sbloom "ti", "tl", "tm", "tp", "tr", "u", "uf", "uh", "ul", "vs", "wh", "xp",
136a1df2892Sbloom "yr", 0
137215f343dSbill };
138215f343dSbill
139215f343dSbill int lineno; /* current line number in input file */
140215f343dSbill char line[256]; /* the current line */
141215f343dSbill char *cfilename; /* name of current file */
142215f343dSbill int nfiles; /* number of files to process */
143215f343dSbill int fflag; /* -f: ignore \f */
144215f343dSbill int sflag; /* -s: ignore \s */
145215f343dSbill int ncmds; /* size of knowncmds */
146215f343dSbill int slot; /* slot in knowncmds found by binsrch */
147215f343dSbill
148215f343dSbill char *malloc();
149215f343dSbill
main(argc,argv)150215f343dSbill main(argc, argv)
151215f343dSbill int argc;
152215f343dSbill char **argv;
153215f343dSbill {
154215f343dSbill FILE *f;
155215f343dSbill int i;
156215f343dSbill char *cp;
157f9487a73Smark char b1[4];
158215f343dSbill
159f9487a73Smark /* Figure out how many known commands there are */
160f9487a73Smark while (knowncmds[ncmds])
161f9487a73Smark ncmds++;
162215f343dSbill while (argc > 1 && argv[1][0] == '-') {
163215f343dSbill switch(argv[1][1]) {
164f9487a73Smark
165215f343dSbill /* -a: add pairs of macros */
166f9487a73Smark case 'a':
167215f343dSbill i = strlen(argv[1]) - 2;
168f9487a73Smark if (i % 6 != 0)
169f9487a73Smark usage();
170215f343dSbill /* look for empty macro slots */
171215f343dSbill for (i=0; br[i].opbr; i++)
172215f343dSbill ;
173215f343dSbill for (cp=argv[1]+3; cp[-1]; cp += 6) {
174f9487a73Smark br[i].opbr = malloc(3);
175f9487a73Smark strncpy(br[i].opbr, cp, 2);
176f9487a73Smark br[i].clbr = malloc(3);
177f9487a73Smark strncpy(br[i].clbr, cp+3, 2);
178f9487a73Smark addmac(br[i].opbr); /* knows pairs are also known cmds */
179f9487a73Smark addmac(br[i].clbr);
180215f343dSbill i++;
181215f343dSbill }
182215f343dSbill break;
183f9487a73Smark
184f9487a73Smark /* -c: add known commands */
185f9487a73Smark case 'c':
186f9487a73Smark i = strlen(argv[1]) - 2;
187f9487a73Smark if (i % 3 != 0)
188f9487a73Smark usage();
189f9487a73Smark for (cp=argv[1]+3; cp[-1]; cp += 3) {
190f9487a73Smark if (cp[2] && cp[2] != '.')
191f9487a73Smark usage();
192f9487a73Smark strncpy(b1, cp, 2);
193f9487a73Smark addmac(b1);
194f9487a73Smark }
195f9487a73Smark break;
196f9487a73Smark
197f9487a73Smark /* -f: ignore font changes */
198215f343dSbill case 'f':
199215f343dSbill fflag = 1;
200215f343dSbill break;
201f9487a73Smark
202f9487a73Smark /* -s: ignore size changes */
203215f343dSbill case 's':
204215f343dSbill sflag = 1;
205215f343dSbill break;
206215f343dSbill default:
207f9487a73Smark usage();
208215f343dSbill }
209215f343dSbill argc--; argv++;
210215f343dSbill }
211215f343dSbill
212215f343dSbill nfiles = argc - 1;
213215f343dSbill
214215f343dSbill if (nfiles > 0) {
215215f343dSbill for (i=1; i<argc; i++) {
216215f343dSbill cfilename = argv[i];
217215f343dSbill f = fopen(cfilename, "r");
218215f343dSbill if (f == NULL)
219215f343dSbill perror(cfilename);
220215f343dSbill else
221215f343dSbill process(f);
222215f343dSbill }
223215f343dSbill } else {
224215f343dSbill cfilename = "stdin";
225215f343dSbill process(stdin);
226215f343dSbill }
227215f343dSbill exit(0);
228215f343dSbill }
229215f343dSbill
usage()230f9487a73Smark usage()
231f9487a73Smark {
232f9487a73Smark printf("Usage: checknr -s -f -a.xx.yy.xx.yy... -c.xx.xx.xx...\n");
233f9487a73Smark exit(1);
234f9487a73Smark }
235f9487a73Smark
process(f)236215f343dSbill process(f)
237215f343dSbill FILE *f;
238215f343dSbill {
239215f343dSbill register int i, n;
240215f343dSbill char mac[5]; /* The current macro or nroff command */
241215f343dSbill int pl;
242215f343dSbill
243215f343dSbill stktop = -1;
244215f343dSbill for (lineno = 1; fgets(line, sizeof line, f); lineno++) {
245215f343dSbill if (line[0] == '.') {
246215f343dSbill /*
247215f343dSbill * find and isolate the macro/command name.
248215f343dSbill */
249215f343dSbill strncpy(mac, line+1, 4);
250215f343dSbill if (isspace(mac[0])) {
251215f343dSbill pe(lineno);
252215f343dSbill printf("Empty command\n");
253215f343dSbill } else if (isspace(mac[1])) {
254215f343dSbill mac[1] = 0;
255215f343dSbill } else if (isspace(mac[2])) {
256215f343dSbill mac[2] = 0;
25710a67484Sroot } else if (mac[0] != '\\' || mac[1] != '\"') {
258215f343dSbill pe(lineno);
259215f343dSbill printf("Command too long\n");
260215f343dSbill }
261215f343dSbill
262215f343dSbill /*
263215f343dSbill * Is it a known command?
264215f343dSbill */
265215f343dSbill checkknown(mac);
266215f343dSbill
267215f343dSbill /*
268215f343dSbill * Should we add it?
269215f343dSbill */
270215f343dSbill if (eq(mac, "de"))
271215f343dSbill addcmd(line);
272215f343dSbill
273215f343dSbill chkcmd(line, mac);
274215f343dSbill }
275215f343dSbill
276215f343dSbill /*
277215f343dSbill * At this point we process the line looking
278215f343dSbill * for \s and \f.
279215f343dSbill */
280215f343dSbill for (i=0; line[i]; i++)
281215f343dSbill if (line[i]=='\\' && (i==0 || line[i-1]!='\\')) {
282215f343dSbill if (!sflag && line[++i]=='s') {
283215f343dSbill pl = line[++i];
284215f343dSbill if (isdigit(pl)) {
285215f343dSbill n = pl - '0';
286215f343dSbill pl = ' ';
287215f343dSbill } else
288215f343dSbill n = 0;
289215f343dSbill while (isdigit(line[++i]))
290215f343dSbill n = 10 * n + line[i] - '0';
291215f343dSbill i--;
292215f343dSbill if (n == 0) {
293215f343dSbill if (stk[stktop].opno == SZ) {
294215f343dSbill stktop--;
295215f343dSbill } else {
296215f343dSbill pe(lineno);
297215f343dSbill printf("unmatched \\s0\n");
298215f343dSbill }
299215f343dSbill } else {
300215f343dSbill stk[++stktop].opno = SZ;
301215f343dSbill stk[stktop].pl = pl;
302215f343dSbill stk[stktop].parm = n;
303215f343dSbill stk[stktop].lno = lineno;
304215f343dSbill }
305215f343dSbill } else if (!fflag && line[i]=='f') {
306215f343dSbill n = line[++i];
307215f343dSbill if (n == 'P') {
308215f343dSbill if (stk[stktop].opno == FT) {
309215f343dSbill stktop--;
310215f343dSbill } else {
311215f343dSbill pe(lineno);
312215f343dSbill printf("unmatched \\fP\n");
313215f343dSbill }
314215f343dSbill } else {
315215f343dSbill stk[++stktop].opno = FT;
316215f343dSbill stk[stktop].pl = 1;
317215f343dSbill stk[stktop].parm = n;
318215f343dSbill stk[stktop].lno = lineno;
319215f343dSbill }
320215f343dSbill }
321215f343dSbill }
322215f343dSbill }
323215f343dSbill /*
324215f343dSbill * We've hit the end and look at all this stuff that hasn't been
325215f343dSbill * matched yet! Complain, complain.
326215f343dSbill */
327215f343dSbill for (i=stktop; i>=0; i--) {
328215f343dSbill complain(i);
329215f343dSbill }
330215f343dSbill }
331215f343dSbill
complain(i)332215f343dSbill complain(i)
333215f343dSbill {
334215f343dSbill pe(stk[i].lno);
335215f343dSbill printf("Unmatched ");
336215f343dSbill prop(i);
337215f343dSbill printf("\n");
338215f343dSbill }
339215f343dSbill
prop(i)340215f343dSbill prop(i)
341215f343dSbill {
342215f343dSbill if (stk[i].pl == 0)
343215f343dSbill printf(".%s", br[stk[i].opno].opbr);
344215f343dSbill else switch(stk[i].opno) {
345215f343dSbill case SZ:
346215f343dSbill printf("\\s%c%d", stk[i].pl, stk[i].parm);
347215f343dSbill break;
348215f343dSbill case FT:
349215f343dSbill printf("\\f%c", stk[i].parm);
350215f343dSbill break;
351215f343dSbill default:
352215f343dSbill printf("Bug: stk[%d].opno = %d = .%s, .%s",
353215f343dSbill i, stk[i].opno, br[stk[i].opno].opbr, br[stk[i].opno].clbr);
354215f343dSbill }
355215f343dSbill }
356215f343dSbill
chkcmd(line,mac)357215f343dSbill chkcmd(line, mac)
358215f343dSbill char *line;
359215f343dSbill char *mac;
360215f343dSbill {
361215f343dSbill register int i, n;
362215f343dSbill
363215f343dSbill /*
364215f343dSbill * Check to see if it matches top of stack.
365215f343dSbill */
366215f343dSbill if (stktop >= 0 && eq(mac, br[stk[stktop].opno].clbr))
367215f343dSbill stktop--; /* OK. Pop & forget */
368215f343dSbill else {
369215f343dSbill /* No. Maybe it's an opener */
370215f343dSbill for (i=0; br[i].opbr; i++) {
371215f343dSbill if (eq(mac, br[i].opbr)) {
372215f343dSbill /* Found. Push it. */
373215f343dSbill stktop++;
374215f343dSbill stk[stktop].opno = i;
375215f343dSbill stk[stktop].pl = 0;
376215f343dSbill stk[stktop].parm = 0;
377215f343dSbill stk[stktop].lno = lineno;
378215f343dSbill break;
379215f343dSbill }
380215f343dSbill /*
381215f343dSbill * Maybe it's an unmatched closer.
382215f343dSbill * NOTE: this depends on the fact
383215f343dSbill * that none of the closers can be
384215f343dSbill * openers too.
385215f343dSbill */
386215f343dSbill if (eq(mac, br[i].clbr)) {
387215f343dSbill nomatch(mac);
388215f343dSbill break;
389215f343dSbill }
390215f343dSbill }
391215f343dSbill }
392215f343dSbill }
393215f343dSbill
nomatch(mac)394215f343dSbill nomatch(mac)
395215f343dSbill char *mac;
396215f343dSbill {
397215f343dSbill register int i, j;
398215f343dSbill
399215f343dSbill /*
400215f343dSbill * Look for a match further down on stack
401215f343dSbill * If we find one, it suggests that the stuff in
402215f343dSbill * between is supposed to match itself.
403215f343dSbill */
404215f343dSbill for (j=stktop; j>=0; j--)
405215f343dSbill if (eq(mac,br[stk[j].opno].clbr)) {
406215f343dSbill /* Found. Make a good diagnostic. */
407215f343dSbill if (j == stktop-2) {
408215f343dSbill /*
409215f343dSbill * Check for special case \fx..\fR and don't
410215f343dSbill * complain.
411215f343dSbill */
412215f343dSbill if (stk[j+1].opno==FT && stk[j+1].parm!='R'
413215f343dSbill && stk[j+2].opno==FT && stk[j+2].parm=='R') {
414215f343dSbill stktop = j -1;
415215f343dSbill return;
416215f343dSbill }
417215f343dSbill /*
418215f343dSbill * We have two unmatched frobs. Chances are
419215f343dSbill * they were intended to match, so we mention
420215f343dSbill * them together.
421215f343dSbill */
422215f343dSbill pe(stk[j+1].lno);
423215f343dSbill prop(j+1);
424215f343dSbill printf(" does not match %d: ", stk[j+2].lno);
425215f343dSbill prop(j+2);
426215f343dSbill printf("\n");
427215f343dSbill } else for (i=j+1; i <= stktop; i++) {
428215f343dSbill complain(i);
429215f343dSbill }
430215f343dSbill stktop = j-1;
431215f343dSbill return;
432215f343dSbill }
433215f343dSbill /* Didn't find one. Throw this away. */
434215f343dSbill pe(lineno);
435215f343dSbill printf("Unmatched .%s\n", mac);
436215f343dSbill }
437215f343dSbill
438215f343dSbill /* eq: are two strings equal? */
eq(s1,s2)439215f343dSbill eq(s1, s2)
440215f343dSbill char *s1, *s2;
441215f343dSbill {
442215f343dSbill return (strcmp(s1, s2) == 0);
443215f343dSbill }
444215f343dSbill
445215f343dSbill /* print the first part of an error message, given the line number */
pe(lineno)446215f343dSbill pe(lineno)
447215f343dSbill int lineno;
448215f343dSbill {
449215f343dSbill if (nfiles > 1)
450215f343dSbill printf("%s: ", cfilename);
451215f343dSbill printf("%d: ", lineno);
452215f343dSbill }
453215f343dSbill
checkknown(mac)454215f343dSbill checkknown(mac)
455215f343dSbill char *mac;
456215f343dSbill {
457215f343dSbill
458215f343dSbill if (eq(mac, "."))
459215f343dSbill return;
460215f343dSbill if (binsrch(mac) >= 0)
461215f343dSbill return;
46210a67484Sroot if (mac[0] == '\\' && mac[1] == '"') /* comments */
46310a67484Sroot return;
464215f343dSbill
465215f343dSbill pe(lineno);
466215f343dSbill printf("Unknown command: .%s\n", mac);
467215f343dSbill }
468215f343dSbill
469215f343dSbill /*
470215f343dSbill * We have a .de xx line in "line". Add xx to the list of known commands.
471215f343dSbill */
addcmd(line)472215f343dSbill addcmd(line)
473215f343dSbill char *line;
474215f343dSbill {
475215f343dSbill char *mac;
476215f343dSbill
477215f343dSbill /* grab the macro being defined */
478215f343dSbill mac = line+4;
479215f343dSbill while (isspace(*mac))
480215f343dSbill mac++;
481215f343dSbill if (*mac == 0) {
482215f343dSbill pe(lineno);
483215f343dSbill printf("illegal define: %s\n", line);
484215f343dSbill return;
485215f343dSbill }
486215f343dSbill mac[2] = 0;
487215f343dSbill if (isspace(mac[1]) || mac[1] == '\\')
488215f343dSbill mac[1] = 0;
489215f343dSbill if (ncmds >= MAXCMDS) {
490215f343dSbill printf("Only %d known commands allowed\n", MAXCMDS);
491215f343dSbill exit(1);
492215f343dSbill }
493f9487a73Smark addmac(mac);
494f9487a73Smark }
495215f343dSbill
496215f343dSbill /*
497215f343dSbill * Add mac to the list. We should really have some kind of tree
498215f343dSbill * structure here but this is a quick-and-dirty job and I just don't
499215f343dSbill * have time to mess with it. (I wonder if this will come back to haunt
500215f343dSbill * me someday?) Anyway, I claim that .de is fairly rare in user
501215f343dSbill * nroff programs, and the register loop below is pretty fast.
502215f343dSbill */
addmac(mac)503f9487a73Smark addmac(mac)
504f9487a73Smark char *mac;
505f9487a73Smark {
506f9487a73Smark register char **src, **dest, **loc;
507f9487a73Smark
508a0779696Srrh if (binsrch(mac) >= 0){ /* it's OK to redefine something */
509a0779696Srrh #ifdef DEBUG
510a0779696Srrh printf("binsrch(%s) -> already in table\n", mac);
511a0779696Srrh #endif DEBUG
512a0779696Srrh return;
513a0779696Srrh }
514215f343dSbill /* binsrch sets slot as a side effect */
515f9487a73Smark #ifdef DEBUG
516f9487a73Smark printf("binsrch(%s) -> %d\n", mac, slot);
517f9487a73Smark #endif
518215f343dSbill loc = &knowncmds[slot];
519215f343dSbill src = &knowncmds[ncmds-1];
520215f343dSbill dest = src+1;
521215f343dSbill while (dest > loc)
522215f343dSbill *dest-- = *src--;
523215f343dSbill *loc = malloc(3);
524215f343dSbill strcpy(*loc, mac);
525215f343dSbill ncmds++;
526f9487a73Smark #ifdef DEBUG
527f9487a73Smark printf("after: %s %s %s %s %s, %d cmds\n", knowncmds[slot-2], knowncmds[slot-1], knowncmds[slot], knowncmds[slot+1], knowncmds[slot+2], ncmds);
528f9487a73Smark #endif
529215f343dSbill }
530215f343dSbill
531215f343dSbill /*
532215f343dSbill * Do a binary search in knowncmds for mac.
533215f343dSbill * If found, return the index. If not, return -1.
534215f343dSbill */
binsrch(mac)535215f343dSbill binsrch(mac)
536215f343dSbill char *mac;
537215f343dSbill {
538215f343dSbill register char *p; /* pointer to current cmd in list */
539215f343dSbill register int d; /* difference if any */
540215f343dSbill register int mid; /* mid point in binary search */
541215f343dSbill register int top, bot; /* boundaries of bin search, inclusive */
542215f343dSbill
543215f343dSbill top = ncmds-1;
544215f343dSbill bot = 0;
545215f343dSbill while (top >= bot) {
546215f343dSbill mid = (top+bot)/2;
547215f343dSbill p = knowncmds[mid];
548215f343dSbill d = p[0] - mac[0];
549215f343dSbill if (d == 0)
550215f343dSbill d = p[1] - mac[1];
551215f343dSbill if (d == 0)
552215f343dSbill return mid;
553215f343dSbill if (d < 0)
554215f343dSbill bot = mid + 1;
555215f343dSbill else
556215f343dSbill top = mid - 1;
557215f343dSbill }
558215f343dSbill slot = bot; /* place it would have gone */
559215f343dSbill return -1;
560215f343dSbill }
561