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