![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to optim.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ucb / Mail|
Return to optim.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ucb / Mail |
1.1 root 1: /*
2: * Copyright (c) 1980 Regents of the University of California.
3: * All rights reserved. The Berkeley software License Agreement
4: * specifies the terms and conditions for redistribution.
5: */
6:
7: #ifndef lint
8: static char *sccsid = "@(#)optim.c 5.5 (Berkeley) 11/2/85";
9: #endif not lint
10:
11: /*
12: * Mail -- a program for sending and receiving mail.
13: *
14: * Network name modification routines.
15: */
16:
17: #include "rcv.h"
18: #include "configdefs.h"
19: #include <ctype.h>
20:
21: /*
22: * Map a name into the correct network "view" of the
23: * name. This is done by prepending the name with the
24: * network address of the sender, then optimizing away
25: * nonsense.
26: */
27:
28: char *
29: netmap(name, from)
30: char name[], from[];
31: {
32: char nbuf[BUFSIZ], ret[BUFSIZ];
33: register char *cp;
34:
35: if (strlen(from) == 0)
36: return(name);
37: if (any('@', name) || any('%', name))
38: return(savestr(arpafix(name, from)));
39: cp = revarpa(from);
40: if (cp == NOSTR)
41: return(name);
42: strcpy(nbuf, cp);
43: cp = &nbuf[strlen(nbuf) - 1];
44: while (!any(*cp, metanet) && cp > nbuf)
45: cp--;
46: if (cp == nbuf)
47: return(name);
48: *++cp = 0;
49: strcat(nbuf, revarpa(name));
50: optim(nbuf, ret);
51: cp = revarpa(ret);
52: if (!icequal(name, cp))
53: return(savestr(cp));
54: return(name);
55: }
56:
57: /*
58: * Rename the given network path to use
59: * the kinds of names that we would right here.
60: */
61:
62: char *
63: rename(str)
64: char str[];
65: {
66: register char *cp, *cp2;
67: char buf[BUFSIZ], path[BUFSIZ];
68: register int c, host;
69:
70: cp = str;
71: strcpy(path, "");
72: for (;;) {
73: if ((c = *cp++) == 0)
74: break;
75: cp2 = buf;
76: while (!any(c, metanet) && c != 0) {
77: *cp2++ = c;
78: c = *cp++;
79: }
80: *cp2 = 0;
81: if (c == 0) {
82: strcat(path, buf);
83: break;
84: }
85: host = netlook(buf, ntype(c));
86: strcat(path, netname(host));
87: stradd(path, c);
88: }
89: if (strcmp(str, path) != 0)
90: return(savestr(path));
91: return(str);
92: }
93:
94: /*
95: * Turn a network machine name into a unique character
96: */
97: netlook(machine, attnet)
98: char machine[];
99: {
100: register struct netmach *np;
101: register char *cp, *cp2;
102: char nbuf[BUFSIZ];
103:
104: /*
105: * Make into lower case.
106: */
107:
108: for (cp = machine, cp2 = nbuf; *cp; *cp2++ = little(*cp++))
109: if (cp2 >= &nbuf[sizeof(nbuf)-1])
110: break;
111: *cp2 = 0;
112:
113: /*
114: * If a single letter machine, look through those first.
115: */
116:
117: if (strlen(nbuf) == 1)
118: for (np = netmach; np->nt_mid != 0; np++)
119: if (np->nt_mid == nbuf[0])
120: return(nbuf[0]);
121:
122: /*
123: * Look for usual name
124: */
125:
126: for (np = netmach; np->nt_mid != 0; np++)
127: if (strcmp(np->nt_machine, nbuf) == 0)
128: return(np->nt_mid);
129:
130: /*
131: * Look in side hash table.
132: */
133:
134: return(mstash(nbuf, attnet));
135: }
136:
137: /*
138: * Make a little character.
139: */
140:
141: little(c)
142: register int c;
143: {
144:
145: if (c >= 'A' && c <= 'Z')
146: c += 'a' - 'A';
147: return(c);
148: }
149:
150: /*
151: * Turn a network unique character identifier into a network name.
152: */
153:
154: char *
155: netname(mid)
156: {
157: register struct netmach *np;
158: char *mlook();
159:
160: if (mid & 0200)
161: return(mlook(mid));
162: for (np = netmach; np->nt_mid != 0; np++)
163: if (np->nt_mid == mid)
164: return(np->nt_machine);
165: return(NOSTR);
166: }
167:
168: /*
169: * Deal with arpa net addresses. The way this is done is strange.
170: * In particular, if the destination arpa net host is not Berkeley,
171: * then the address is correct as stands. Otherwise, we strip off
172: * the trailing @Berkeley, then cook up a phony person for it to
173: * be from and optimize the result.
174: */
175: char *
176: arpafix(name, from)
177: char name[];
178: char from[];
179: {
180: register char *cp;
181: register int arpamach;
182: char newname[BUFSIZ];
183: char fake[5];
184: char fakepath[20];
185:
186: if (debug) {
187: fprintf(stderr, "arpafix(%s, %s)\n", name, from);
188: }
189: cp = rindex(name, '@');
190: if (cp == NOSTR)
191: cp = rindex(name, '%');
192: if (cp == NOSTR) {
193: fprintf(stderr, "Somethings amiss -- no @ or % in arpafix\n");
194: return(name);
195: }
196: cp++;
197: arpamach = netlook(cp, '@');
198: if (arpamach == 0) {
199: if (debug)
200: fprintf(stderr, "machine %s unknown, uses: %s\n", cp, name);
201: return(name);
202: }
203: if (((nettype(arpamach) & nettype(LOCAL)) & ~AN) == 0) {
204: if (debug)
205: fprintf(stderr, "machine %s known but remote, uses: %s\n",
206: cp, name);
207: return(name);
208: }
209: strcpy(newname, name);
210: cp = rindex(newname, '@');
211: if (cp == NOSTR)
212: cp = rindex(newname, '%');
213: *cp = 0;
214: fake[0] = arpamach;
215: fake[1] = ':';
216: fake[2] = LOCAL;
217: fake[3] = ':';
218: fake[4] = 0;
219: prefer(fake);
220: strcpy(fakepath, netname(fake[0]));
221: stradd(fakepath, fake[1]);
222: strcat(fakepath, "daemon");
223: if (debug)
224: fprintf(stderr, "machine local, call netmap(%s, %s)\n",
225: newname, fakepath);
226: return(netmap(newname, fakepath));
227: }
228:
229: /*
230: * Take a network machine descriptor and find the types of connected
231: * nets and return it.
232: */
233:
234: nettype(mid)
235: {
236: register struct netmach *np;
237:
238: if (mid & 0200)
239: return(mtype(mid));
240: for (np = netmach; np->nt_mid != 0; np++)
241: if (np->nt_mid == mid)
242: return(np->nt_type);
243: return(0);
244: }
245:
246: /*
247: * Hashing routines to salt away machines seen scanning
248: * networks paths that we don't know about.
249: */
250:
251: #define XHSIZE 19 /* Size of extra hash table */
252: #define NXMID (XHSIZE*3/4) /* Max extra machines */
253:
254: struct xtrahash {
255: char *xh_name; /* Name of machine */
256: short xh_mid; /* Machine ID */
257: short xh_attnet; /* Attached networks */
258: } xtrahash[XHSIZE];
259:
260: struct xtrahash *xtab[XHSIZE]; /* F: mid-->machine name */
261:
262: short midfree; /* Next free machine id */
263:
264: /*
265: * Initialize the extra host hash table.
266: * Called by sreset.
267: */
268:
269: minit()
270: {
271: register struct xtrahash *xp, **tp;
272: register int i;
273:
274: midfree = 0;
275: tp = &xtab[0];
276: for (xp = &xtrahash[0]; xp < &xtrahash[XHSIZE]; xp++) {
277: xp->xh_name = NOSTR;
278: xp->xh_mid = 0;
279: xp->xh_attnet = 0;
280: *tp++ = (struct xtrahash *) 0;
281: }
282: }
283:
284: /*
285: * Stash a net name in the extra host hash table.
286: * If a new entry is put in the hash table, deduce what
287: * net the machine is attached to from the net character.
288: *
289: * If the machine is already known, add the given attached
290: * net to those already known.
291: */
292:
293: mstash(name, attnet)
294: char name[];
295: {
296: register struct xtrahash *xp;
297: struct xtrahash *xlocate();
298: int x;
299:
300: xp = xlocate(name);
301: if (xp == (struct xtrahash *) 0) {
302: printf("Ran out of machine id spots\n");
303: return(0);
304: }
305: if (xp->xh_name == NOSTR) {
306: if (midfree >= XHSIZE) {
307: printf("Out of machine ids\n");
308: return(0);
309: }
310: xtab[midfree] = xp;
311: xp->xh_name = savestr(name);
312: xp->xh_mid = 0200 + midfree++;
313: }
314: x = ntype(attnet);
315: if (x == 0)
316: xp->xh_attnet |= SN;
317: else
318: xp->xh_attnet |= x;
319: return(xp->xh_mid);
320: }
321:
322: /*
323: * Search for the given name in the hash table
324: * and return the pointer to it if found, or to the first
325: * empty slot if not found.
326: *
327: * If no free slots can be found, return 0.
328: */
329:
330: struct xtrahash *
331: xlocate(name)
332: char name[];
333: {
334: register int h, q, i;
335: register char *cp;
336: register struct xtrahash *xp;
337:
338: for (h = 0, cp = name; *cp; h = (h << 2) + *cp++)
339: ;
340: if (h < 0 && (h = -h) < 0)
341: h = 0;
342: h = h % XHSIZE;
343: cp = name;
344: for (i = 0, q = 0; q < XHSIZE; i++, q = i * i) {
345: xp = &xtrahash[(h + q) % XHSIZE];
346: if (xp->xh_name == NOSTR)
347: return(xp);
348: if (strcmp(cp, xp->xh_name) == 0)
349: return(xp);
350: if (h - q < 0)
351: h += XHSIZE;
352: xp = &xtrahash[(h - q) % XHSIZE];
353: if (xp->xh_name == NOSTR)
354: return(xp);
355: if (strcmp(cp, xp->xh_name) == 0)
356: return(xp);
357: }
358: return((struct xtrahash *) 0);
359: }
360:
361: /*
362: * Return the name from the extra host hash table corresponding
363: * to the passed machine id.
364: */
365:
366: char *
367: mlook(mid)
368: {
369: register int m;
370:
371: if ((mid & 0200) == 0)
372: return(NOSTR);
373: m = mid & 0177;
374: if (m >= midfree) {
375: printf("Use made of undefined machine id\n");
376: return(NOSTR);
377: }
378: return(xtab[m]->xh_name);
379: }
380:
381: /*
382: * Return the bit mask of net's that the given extra host machine
383: * id has so far.
384: */
385:
386: mtype(mid)
387: {
388: register int m;
389:
390: if ((mid & 0200) == 0)
391: return(0);
392: m = mid & 0177;
393: if (m >= midfree) {
394: printf("Use made of undefined machine id\n");
395: return(0);
396: }
397: return(xtab[m]->xh_attnet);
398: }
399:
400: /*
401: * Take a network name and optimize it. This gloriously messy
402: * operation takes place as follows: the name with machine names
403: * in it is tokenized by mapping each machine name into a single
404: * character machine id (netlook). The separator characters (network
405: * metacharacters) are left intact. The last component of the network
406: * name is stripped off and assumed to be the destination user name --
407: * it does not participate in the optimization. As an example, the
408: * name "research!vax135!research!ucbvax!bill" becomes, tokenized,
409: * "r!x!r!v!" and "bill" A low level routine, optim1, fixes up the
410: * network part (eg, "r!x!r!v!"), then we convert back to network
411: * machine names and tack the user name on the end.
412: *
413: * The result of this is copied into the parameter "name"
414: */
415:
416: optim(net, name)
417: char net[], name[];
418: {
419: char netcomp[BUFSIZ], netstr[40], xfstr[40];
420: register char *cp, *cp2;
421: register int c;
422:
423: strcpy(netstr, "");
424: cp = net;
425: for (;;) {
426: /*
427: * Rip off next path component into netcomp
428: */
429: cp2 = netcomp;
430: while (*cp && !any(*cp, metanet))
431: *cp2++ = *cp++;
432: *cp2 = 0;
433: /*
434: * If we hit null byte, then we just scanned
435: * the destination user name. Go off and optimize
436: * if its so.
437: */
438: if (*cp == 0)
439: break;
440: if ((c = netlook(netcomp, *cp)) == 0) {
441: printf("No host named \"%s\"\n", netcomp);
442: err:
443: strcpy(name, net);
444: return;
445: }
446: stradd(netstr, c);
447: stradd(netstr, *cp++);
448: /*
449: * If multiple network separators given,
450: * throw away the extras.
451: */
452: while (any(*cp, metanet))
453: cp++;
454: }
455: if (strlen(netcomp) == 0) {
456: printf("net name syntax\n");
457: goto err;
458: }
459: optim1(netstr, xfstr);
460:
461: /*
462: * Convert back to machine names.
463: */
464:
465: cp = xfstr;
466: strcpy(name, "");
467: while (*cp) {
468: if ((cp2 = netname(*cp++)) == NOSTR) {
469: printf("Made up bad net name\n");
470: printf("Machine code %c (0%o)\n", cp[-1], cp[-1]);
471: printf("Sorry -- dumping now. Alert K. Shoens\n");
472: core(0);
473: goto err;
474: }
475: strcat(name, cp2);
476: stradd(name, *cp++);
477: }
478: strcat(name, netcomp);
479: }
480:
481: /*
482: * Take a string of network machine id's and separators and
483: * optimize them. We process these by pulling off maximal
484: * leading strings of the same type, passing these to the appropriate
485: * optimizer and concatenating the results.
486: */
487:
488: optim1(netstr, name)
489: char netstr[], name[];
490: {
491: char path[40], rpath[40];
492: register char *cp, *cp2;
493: register int tp, nc;
494:
495: cp = netstr;
496: prefer(cp);
497: strcpy(name, "");
498: /*
499: * If the address ultimately points back to us,
500: * just return a null network path.
501: */
502: if (strlen(cp) > 1 && cp[strlen(cp) - 2] == LOCAL)
503: return;
504: while (*cp != 0) {
505: strcpy(path, "");
506: tp = ntype(cp[1]);
507: nc = cp[1];
508: while (*cp && tp == ntype(cp[1])) {
509: stradd(path, *cp++);
510: cp++;
511: }
512: switch (netkind(tp)) {
513: default:
514: strcpy(rpath, path);
515: break;
516:
517: case IMPLICIT:
518: optimimp(path, rpath);
519: break;
520:
521: case EXPLICIT:
522: optimex(path, rpath);
523: break;
524: }
525: for (cp2 = rpath; *cp2 != 0; cp2++) {
526: stradd(name, *cp2);
527: stradd(name, nc);
528: }
529: }
530: optiboth(name);
531: prefer(name);
532: }
533:
534: /*
535: * Return the network of the separator --
536: * AN for arpa net
537: * BN for Bell labs net
538: * SN for Schmidt (berkeley net)
539: * 0 if we don't know.
540: */
541:
542: ntype(nc)
543: register int nc;
544: {
545: register struct ntypetab *np;
546:
547: for (np = ntypetab; np->nt_char != 0; np++)
548: if (np->nt_char == nc)
549: return(np->nt_bcode);
550: return(0);
551: }
552:
553: /*
554: * Return the kind of routing used for the particular net
555: * EXPLICIT means explicitly routed
556: * IMPLICIT means implicitly routed
557: * 0 means don't know
558: */
559:
560: netkind(nt)
561: register int nt;
562: {
563: register struct nkindtab *np;
564:
565: for (np = nkindtab; np->nk_type != 0; np++)
566: if (np->nk_type == nt)
567: return(np->nk_kind);
568: return(0);
569: }
570:
571: /*
572: * Do name optimization for an explicitly routed network (eg BTL network).
573: */
574:
575: optimex(net, name)
576: char net[], name[];
577: {
578: register char *cp, *rp;
579: register int m;
580: char *rindex();
581:
582: strcpy(name, net);
583: cp = name;
584: if (strlen(cp) == 0)
585: return(-1);
586: if (cp[strlen(cp)-1] == LOCAL) {
587: name[0] = 0;
588: return(0);
589: }
590: for (cp = name; *cp; cp++) {
591: m = *cp;
592: rp = rindex(cp+1, m);
593: if (rp != NOSTR)
594: strcpy(cp, rp);
595: }
596: return(0);
597: }
598:
599: /*
600: * Do name optimization for implicitly routed network (eg, arpanet,
601: * Berkeley network)
602: */
603:
604: optimimp(net, name)
605: char net[], name[];
606: {
607: register char *cp;
608: register int m;
609:
610: cp = net;
611: if (strlen(cp) == 0)
612: return(-1);
613: m = cp[strlen(cp) - 1];
614: if (m == LOCAL) {
615: strcpy(name, "");
616: return(0);
617: }
618: name[0] = m;
619: name[1] = 0;
620: return(0);
621: }
622:
623: /*
624: * Perform global optimization on the given network path.
625: * The trick here is to look ahead to see if there are any loops
626: * in the path and remove them. The interpretation of loops is
627: * more strict here than in optimex since both the machine and net
628: * type must match.
629: */
630:
631: optiboth(net)
632: char net[];
633: {
634: register char *cp, *cp2;
635: char *rpair();
636:
637: cp = net;
638: if (strlen(cp) == 0)
639: return;
640: if ((strlen(cp) % 2) != 0) {
641: printf("Strange arg to optiboth\n");
642: return;
643: }
644: while (*cp) {
645: cp2 = rpair(cp+2, *cp);
646: if (cp2 != NOSTR)
647: strcpy(cp, cp2);
648: cp += 2;
649: }
650: }
651:
652: /*
653: * Find the rightmost instance of the given (machine, type) pair.
654: */
655:
656: char *
657: rpair(str, mach)
658: char str[];
659: {
660: register char *cp, *last;
661:
662: cp = str;
663: last = NOSTR;
664: while (*cp) {
665: if (*cp == mach)
666: last = cp;
667: cp += 2;
668: }
669: return(last);
670: }
671:
672: /*
673: * Change the network separators in the given network path
674: * to the preferred network transmission means.
675: */
676:
677: prefer(name)
678: char name[];
679: {
680: register char *cp;
681: register int state, n;
682:
683: state = LOCAL;
684: for (cp = name; *cp; cp += 2) {
685: n = best(state, *cp);
686: if (n)
687: cp[1] = n;
688: state = *cp;
689: }
690: }
691:
692: /*
693: * Return the best network separator for the given machine pair.
694: */
695:
696: best(src, dest)
697: {
698: register int dtype, stype;
699: register struct netorder *np;
700:
701: stype = nettype(src);
702: dtype = nettype(dest);
703: fflush(stdout);
704: if (stype == 0 || dtype == 0) {
705: printf("ERROR: unknown internal machine id\n");
706: return(0);
707: }
708: if ((stype & dtype) == 0)
709: return(0);
710: np = &netorder[0];
711: while ((np->no_stat & stype & dtype) == 0)
712: np++;
713: return(np->no_char);
714: }
715:
716: #ifdef GETHOST
717: /*
718: * Initialize the network name of the current host.
719: */
720: inithost()
721: {
722: register struct netmach *np;
723: static char host[64];
724:
725: gethostname(host, sizeof host);
726: for (np = netmach; np->nt_machine != 0; np++)
727: if (strcmp(np->nt_machine, EMPTY) == 0)
728: break;
729: if (np->nt_machine == 0) {
730: printf("Cannot find empty slot for dynamic host entry\n");
731: exit(1);
732: }
733: np->nt_machine = host;
734: }
735: #endif GETHOST
736:
737: /*
738: * Code to twist around arpa net names.
739: */
740:
741: #define WORD 257 /* Token for a string */
742:
743: static char netbuf[256];
744: static char *yylval;
745:
746: /*
747: * Reverse all of the arpa net addresses in the given name to
748: * be of the form "host @ user" instead of "user @ host"
749: * This function is its own inverse.
750: */
751:
752: char *
753: revarpa(str)
754: char str[];
755: {
756:
757: if (yyinit(str) < 0)
758: return(NOSTR);
759: if (name())
760: return(NOSTR);
761: if (strcmp(str, netbuf) == 0)
762: return(str);
763: return(savestr(netbuf));
764: }
765:
766: /*
767: * Parse (by recursive descent) network names, using the following grammar:
768: * name:
769: * term {':' term}
770: * term {'^' term}
771: * term {'!' term}
772: * term '@' name
773: * term '%' name
774: *
775: * term:
776: * string of characters.
777: */
778:
779: name()
780: {
781: register int t;
782: register char *cp;
783:
784: for (;;) {
785: t = yylex();
786: if (t != WORD)
787: return(-1);
788: cp = yylval;
789: t = yylex();
790: switch (t) {
791: case 0:
792: strcat(netbuf, cp);
793: return(0);
794:
795: case '@':
796: case '%':
797: if (name())
798: return(-1);
799: stradd(netbuf, '@');
800: strcat(netbuf, cp);
801: return(0);
802:
803: case WORD:
804: return(-1);
805:
806: default:
807: strcat(netbuf, cp);
808: stradd(netbuf, t);
809: }
810: }
811: }
812:
813: /*
814: * Scanner for network names.
815: */
816:
817: static char *charp; /* Current input pointer */
818: static int nexttok; /* Salted away next token */
819:
820: /*
821: * Initialize the network name scanner.
822: */
823:
824: yyinit(str)
825: char str[];
826: {
827: static char lexbuf[BUFSIZ];
828:
829: netbuf[0] = 0;
830: if (strlen(str) >= sizeof lexbuf - 1)
831: return(-1);
832: nexttok = 0;
833: strcpy(lexbuf, str);
834: charp = lexbuf;
835: return(0);
836: }
837:
838: /*
839: * Scan and return a single token.
840: * yylval is set to point to a scanned string.
841: */
842:
843: yylex()
844: {
845: register char *cp, *dot;
846: register int s;
847:
848: if (nexttok) {
849: s = nexttok;
850: nexttok = 0;
851: return(s);
852: }
853: cp = charp;
854: while (*cp && isspace(*cp))
855: cp++;
856: if (*cp == 0)
857: return(0);
858: if (any(*cp, metanet)) {
859: charp = cp+1;
860: return(*cp);
861: }
862: dot = cp;
863: while (*cp && !any(*cp, metanet) && !any(*cp, " \t"))
864: cp++;
865: if (any(*cp, metanet))
866: nexttok = *cp;
867: if (*cp == 0)
868: charp = cp;
869: else
870: charp = cp+1;
871: *cp = 0;
872: yylval = dot;
873: return(WORD);
874: }
875:
876: /*
877: * Add a single character onto a string.
878: */
879:
880: stradd(str, c)
881: register char *str;
882: register int c;
883: {
884:
885: str += strlen(str);
886: *str++ = c;
887: *str = 0;
888: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.