Return to optim.c CVS log

Up to [CSRG BSD Unix] / 3BSD / cmd / ucbmail

Annotation of 3BSD/cmd/ucbmail/optim.c, revision 1.1

1.1     ! root        1: #
        !             2: 
        !             3: /*
        !             4:  * Mail -- a program for sending and receiving mail.
        !             5:  *
        !             6:  * Network name modification routines.
        !             7:  */
        !             8: 
        !             9: #include "rcv.h"
        !            10: 
        !            11: /*
        !            12:  * Map a name into the correct network "view" of the
        !            13:  * name.  This is done by prepending the name with the
        !            14:  * network address of the sender, then optimizing away
        !            15:  * nonsense.
        !            16:  */
        !            17: 
        !            18: char   *metanet = "!^:@";
        !            19: 
        !            20: char *
        !            21: netmap(name, from)
        !            22:        char name[], from[];
        !            23: {
        !            24:        char nbuf[BUFSIZ], ret[BUFSIZ];
        !            25:        register char *cp;
        !            26: 
        !            27:        strcpy(nbuf, from);
        !            28:        if (strlen(nbuf) == 0)
        !            29:                return(name);
        !            30:        cp = &nbuf[strlen(nbuf) - 1];
        !            31:        while (!any(*cp, metanet) && cp > nbuf)
        !            32:                cp--;
        !            33:        if (cp == nbuf)
        !            34:                return(name);
        !            35:        *++cp = 0;
        !            36:        strcat(nbuf, name);
        !            37:        optim(nbuf, ret);
        !            38:        if (!equal(name, ret))
        !            39:                return((char *) savestr(ret));
        !            40:        return(name);
        !            41: }
        !            42: 
        !            43: /*
        !            44:  * Turn a network machine name into a unique character
        !            45:  * + give connection-to status.  BN -- connected to Bell Net.
        !            46:  * AN -- connected to ARPA net, SN -- connected to Schmidt net.
        !            47:  * CN -- connected to COCANET.
        !            48:  */
        !            49: 
        !            50: #define        AN      1                       /* Connected to ARPA net */
        !            51: #define        BN      2                       /* Connected to BTL net */
        !            52: #define        CN      4                       /* Connected to COCANET */
        !            53: #define        SN      8                       /* Connected to Schmidt net */
        !            54: 
        !            55: struct netmach {
        !            56:        char    *nt_machine;
        !            57:        char    nt_mid;
        !            58:        short   nt_type;
        !            59: } netmach[] = {
        !            60:        "a",            'a',            SN,
        !            61:        "b",            'b',            SN,
        !            62:        "c",            'c',            SN,
        !            63:        "d",            'd',            SN,
        !            64:        "e",            'e',            SN,
        !            65:        "f",            'f',            SN,
        !            66:        "ccvax",        'f',            SN,
        !            67:        "ingres",       'i',            AN|SN,
        !            68:        "ing70",        'i',            AN|SN,
        !            69:        "ingvax",       'j',            SN,
        !            70:        "image",        'm',            SN,
        !            71:        "optvax",       'o',            SN,
        !            72:        "sesm",         'o',            SN,
        !            73:        "q",            'q',            SN,
        !            74:        "research",     'r',            BN,
        !            75:        "src",          's',            SN,
        !            76:        "vax",          'v',            BN|SN,
        !            77:        "csvax",        'v',            BN|SN,
        !            78:        "ucbvax",       'v',            BN|SN,
        !            79:        "vax135",       'x',            BN,
        !            80:        "cory",         'y',            SN,
        !            81:        "eecs40",       'z',            SN,
        !            82:        0,              0,              0
        !            83: };
        !            84: 
        !            85: netlook(machine, attnet)
        !            86:        char machine[];
        !            87: {
        !            88:        register struct netmach *np;
        !            89:        register char *cp, *cp2;
        !            90:        char nbuf[20];
        !            91: 
        !            92:        /*
        !            93:         * Make into lower case.
        !            94:         */
        !            95: 
        !            96:        for (cp = machine, cp2 = nbuf; *cp; *cp2++ = little(*cp++))
        !            97:                ;
        !            98:        *cp2 = 0;
        !            99: 
        !           100:        /*
        !           101:         * If a single letter machine, look through those first.
        !           102:         */
        !           103: 
        !           104:        if (strlen(nbuf) == 1)
        !           105:                for (np = netmach; np->nt_mid != 0; np++)
        !           106:                        if (np->nt_mid == nbuf[0])
        !           107:                                return(nbuf[0]);
        !           108: 
        !           109:        /*
        !           110:         * Look for usual name
        !           111:         */
        !           112: 
        !           113:        for (np = netmach; np->nt_mid != 0; np++)
        !           114:                if (strcmp(np->nt_machine, nbuf) == 0)
        !           115:                        return(np->nt_mid);
        !           116: 
        !           117:        /*
        !           118:         * Look in side hash table.
        !           119:         */
        !           120: 
        !           121:        return(mstash(nbuf, attnet));
        !           122: }
        !           123: 
        !           124: /*
        !           125:  * Make a little character.
        !           126:  */
        !           127: 
        !           128: little(c)
        !           129:        register int c;
        !           130: {
        !           131: 
        !           132:        if (c >= 'A' && c <= 'Z')
        !           133:                c += 'a' - 'A';
        !           134:        return(c);
        !           135: }
        !           136: 
        !           137: /*
        !           138:  * Turn a network unique character identifier into a network name.
        !           139:  */
        !           140: 
        !           141: char *
        !           142: netname(mid)
        !           143: {
        !           144:        register struct netmach *np;
        !           145:        char *mlook();
        !           146: 
        !           147:        if (mid & 0200)
        !           148:                return(mlook(mid));
        !           149:        for (np = netmach; np->nt_mid != 0; np++)
        !           150:                if (np->nt_mid == mid)
        !           151:                        return(np->nt_machine);
        !           152:        return(NOSTR);
        !           153: }
        !           154: 
        !           155: /*
        !           156:  * Take a network machine descriptor and find the types of connected
        !           157:  * nets and return it.
        !           158:  */
        !           159: 
        !           160: nettype(mid)
        !           161: {
        !           162:        register struct netmach *np;
        !           163: 
        !           164:        if (mid & 0200)
        !           165:                return(mtype(mid));
        !           166:        for (np = netmach; np->nt_mid != 0; np++)
        !           167:                if (np->nt_mid == mid)
        !           168:                        return(np->nt_type);
        !           169:        return(0);
        !           170: }
        !           171: 
        !           172: /*
        !           173:  * Hashing routines to salt away machines seen scanning
        !           174:  * networks paths that we don't know about.
        !           175:  */
        !           176: 
        !           177: #define        XHSIZE          19              /* Size of extra hash table */
        !           178: #define        NXMID           (XHSIZE*3/4)    /* Max extra machines */
        !           179: 
        !           180: struct xtrahash {
        !           181:        char    *xh_name;               /* Name of machine */
        !           182:        short   xh_mid;                 /* Machine ID */
        !           183:        short   xh_attnet;              /* Attached networks */
        !           184: } xtrahash[XHSIZE];
        !           185: 
        !           186: struct xtrahash        *xtab[XHSIZE];          /* F: mid-->machine name */
        !           187: 
        !           188: short  midfree;                        /* Next free machine id */
        !           189: 
        !           190: /*
        !           191:  * Initialize the extra host hash table.
        !           192:  * Called by sreset.
        !           193:  */
        !           194: 
        !           195: minit()
        !           196: {
        !           197:        register struct xtrahash *xp, **tp;
        !           198:        register int i;
        !           199: 
        !           200:        midfree = 0;
        !           201:        tp = &xtab[0];
        !           202:        for (xp = &xtrahash[0]; xp < &xtrahash[XHSIZE]; xp++) {
        !           203:                xp->xh_name = NOSTR;
        !           204:                xp->xh_mid = 0;
        !           205:                xp->xh_attnet = 0;
        !           206:                *tp++ = (struct xtrahash *) 0;
        !           207:        }
        !           208: }
        !           209: 
        !           210: /*
        !           211:  * Stash a net name in the extra host hash table.
        !           212:  * If a new entry is put in the hash table, deduce what
        !           213:  * net the machine is attached to from the net character.
        !           214:  *
        !           215:  * If the machine is already known, add the given attached
        !           216:  * net to those already known.
        !           217:  */
        !           218: 
        !           219: mstash(name, attnet)
        !           220:        char name[];
        !           221: {
        !           222:        register struct xtrahash *xp;
        !           223:        struct xtrahash *xlocate();
        !           224: 
        !           225:        xp = xlocate(name);
        !           226:        if (xp == (struct xtrahash *) 0) {
        !           227:                printf("Ran out of machine id spots\n");
        !           228:                return(0);
        !           229:        }
        !           230:        if (xp->xh_name == NOSTR) {
        !           231:                if (midfree >= XHSIZE) {
        !           232:                        printf("Out of machine ids\n");
        !           233:                        return(0);
        !           234:                }
        !           235:                xtab[midfree] = xp;
        !           236:                xp->xh_name = savestr(name);
        !           237:                xp->xh_mid = 0200 + midfree++;
        !           238:        }
        !           239:        switch (attnet) {
        !           240:        case '!':
        !           241:        case '^':
        !           242:                xp->xh_attnet |= BN;
        !           243:                break;
        !           244: 
        !           245:        default:
        !           246:        case ':':
        !           247:                xp->xh_attnet |= SN;
        !           248:                break;
        !           249: 
        !           250:        case '@':
        !           251:                xp->xh_attnet |= AN;
        !           252:                break;
        !           253:        }
        !           254:        return(xp->xh_mid);
        !           255: }
        !           256: 
        !           257: /*
        !           258:  * Search for the given name in the hash table
        !           259:  * and return the pointer to it if found, or to the first
        !           260:  * empty slot if not found.
        !           261:  *
        !           262:  * If no free slots can be found, return 0.
        !           263:  */
        !           264: 
        !           265: struct xtrahash *
        !           266: xlocate(name)
        !           267:        char name[];
        !           268: {
        !           269:        register int h, q, i;
        !           270:        register char *cp;
        !           271:        register struct xtrahash *xp;
        !           272: 
        !           273:        for (h = 0, cp = name; *cp; h = (h << 2) + *cp++)
        !           274:                ;
        !           275:        if (h < 0 && (h = -h) < 0)
        !           276:                h = 0;
        !           277:        h = h % XHSIZE;
        !           278:        cp = name;
        !           279:        for (i = 0, q = 0; q < XHSIZE; i++, q = i * i) {
        !           280:                xp = &xtrahash[(h + q) % XHSIZE];
        !           281:                if (xp->xh_name == NOSTR)
        !           282:                        return(xp);
        !           283:                if (strcmp(cp, xp->xh_name) == 0)
        !           284:                        return(xp);
        !           285:                if (h - q < 0)
        !           286:                        q += XHSIZE;
        !           287:                xp = &xtrahash[(h - q) % XHSIZE];
        !           288:                if (xp->xh_name == NOSTR)
        !           289:                        return(xp);
        !           290:                if (strcmp(cp, xp->xh_name) == 0)
        !           291:                        return(xp);
        !           292:        }
        !           293:        return((struct xtrahash *) 0);
        !           294: }
        !           295: 
        !           296: /*
        !           297:  * Return the name from the extra host hash table corresponding
        !           298:  * to the passed machine id.
        !           299:  */
        !           300: 
        !           301: char *
        !           302: mlook(mid)
        !           303: {
        !           304:        register int m;
        !           305: 
        !           306:        if ((mid & 0200) == 0)
        !           307:                return(NOSTR);
        !           308:        m = mid & 0177;
        !           309:        if (m >= midfree) {
        !           310:                printf("Use made of undefined machine id\n");
        !           311:                return(NOSTR);
        !           312:        }
        !           313:        return(xtab[m]->xh_name);
        !           314: }
        !           315: 
        !           316: /*
        !           317:  * Return the bit mask of net's that the given extra host machine
        !           318:  * id has so far.
        !           319:  */
        !           320: 
        !           321: mtype(mid)
        !           322: {
        !           323:        register int m;
        !           324: 
        !           325:        if ((mid & 0200) == 0)
        !           326:                return(0);
        !           327:        m = mid & 0177;
        !           328:        if (m >= midfree) {
        !           329:                printf("Use made of undefined machine id\n");
        !           330:                return(0);
        !           331:        }
        !           332:        return(xtab[m]->xh_attnet);
        !           333: }
        !           334: 
        !           335: /*
        !           336:  * Take a network name and optimize it.  This gloriously messy
        !           337:  * opertions takes place as follows:  the name with machine names
        !           338:  * in it is tokenized by mapping each machine name into a single
        !           339:  * character machine id (netlook).  The separator characters (network
        !           340:  * metacharacters) are left intact.  The last component of the network
        !           341:  * name is stripped off and assumed to be the destination user name --
        !           342:  * it does not participate in the optimization.  As an example, the
        !           343:  * name "research!vax135!research!ucbvax!bill" becomes, tokenized,
        !           344:  * "r!x!r!v!" and "bill"  A low level routine, optim1, fixes up the
        !           345:  * network part (eg, "r!x!r!v!"), then we convert back to network
        !           346:  * machine names and tack the user name on the end.
        !           347:  *
        !           348:  * The result of this is copied into the parameter "name"
        !           349:  */
        !           350: 
        !           351: optim(net, name)
        !           352:        char net[], name[];
        !           353: {
        !           354:        char netcomp[BUFSIZ], netstr[40], xfstr[40];
        !           355:        register char *cp, *cp2;
        !           356:        register int c;
        !           357: 
        !           358:        strcpy(netstr, "");
        !           359:        cp = net;
        !           360:        for (;;) {
        !           361:                /*
        !           362:                 * Rip off next path component into netcomp
        !           363:                 */
        !           364:                cp2 = netcomp;
        !           365:                while (*cp && !any(*cp, metanet))
        !           366:                        *cp2++ = *cp++;
        !           367:                *cp2 = 0;
        !           368:                /*
        !           369:                 * If we hit null byte, then we just scanned
        !           370:                 * the destination user name.  Go off and optimize
        !           371:                 * if its so.
        !           372:                 */
        !           373:                if (*cp == 0)
        !           374:                        break;
        !           375:                if ((c = netlook(netcomp, *cp)) == 0) {
        !           376:                        printf("No host named \"%s\"\n", netcomp);
        !           377: err:
        !           378:                        strcpy(name, net);
        !           379:                        return;
        !           380:                }
        !           381:                stradd(netstr, c);
        !           382:                stradd(netstr, *cp++);
        !           383:                /*
        !           384:                 * If multiple network separators given,
        !           385:                 * throw away the extras.
        !           386:                 */
        !           387:                while (any(*cp, metanet))
        !           388:                        cp++;
        !           389:        }
        !           390:        if (strlen(netcomp) == 0) {
        !           391:                printf("net name syntax\n");
        !           392:                goto err;
        !           393:        }
        !           394:        optim1(netstr, xfstr);
        !           395: 
        !           396:        /*
        !           397:         * Convert back to machine names.
        !           398:         */
        !           399: 
        !           400:        cp = xfstr;
        !           401:        strcpy(name, "");
        !           402:        while (*cp) {
        !           403:                if ((cp2 = netname(*cp++)) == NOSTR) {
        !           404:                        printf("Made up bad net name\n");
        !           405:                        goto err;
        !           406:                }
        !           407:                strcat(name, cp2);
        !           408:                stradd(name, *cp++);
        !           409:        }
        !           410:        strcat(name, netcomp);
        !           411: }
        !           412: 
        !           413: /*
        !           414:  * Take a string of network machine id's and separators and
        !           415:  * optimize them.  We process these by pulling off maximal
        !           416:  * leading strings of the same type, ppassing these to the appropriate
        !           417:  * optimizer and concatenating the results.
        !           418:  */
        !           419: 
        !           420: #define        IMPLICIT        1
        !           421: #define        EXPLICIT        2
        !           422: 
        !           423: optim1(netstr, name)
        !           424:        char netstr[], name[];
        !           425: {
        !           426:        char path[40], rpath[40];
        !           427:        register char *cp, *cp2;
        !           428:        register int tp, nc;
        !           429: 
        !           430:        cp = netstr;
        !           431:        prefer(cp);
        !           432:        strcpy(name, "");
        !           433:        while (*cp != 0) {
        !           434:                strcpy(path, "");
        !           435:                tp = ntype(cp[1]);
        !           436:                nc = cp[1];
        !           437:                while (*cp && tp == ntype(cp[1])) {
        !           438:                        stradd(path, *cp++);
        !           439:                        cp++;
        !           440:                }
        !           441:                switch (tp) {
        !           442:                default:
        !           443:                        strcpy(rpath, path);
        !           444:                        break;
        !           445: 
        !           446:                case IMPLICIT:
        !           447:                        optimimp(path, rpath);
        !           448:                        break;
        !           449: 
        !           450:                case EXPLICIT:
        !           451:                        optimex(path, rpath);
        !           452:                        break;
        !           453:                }
        !           454:                for (cp2 = rpath; *cp2 != 0; cp2++) {
        !           455:                        stradd(name, *cp2);
        !           456:                        stradd(name, nc);
        !           457:                }
        !           458:        }
        !           459:        optiboth(name);
        !           460:        prefer(name);
        !           461: }
        !           462: 
        !           463: /*
        !           464:  * Return the type of the separator --
        !           465:  *     IMPLICIT -- if for a smart, implicitly routed network
        !           466:  *     EXPLICIT -- if for a dumb, explicitly routed neetwork.
        !           467:  *     0 if we don't know.
        !           468:  */
        !           469: 
        !           470: ntype(nc)
        !           471:        register int nc;
        !           472: {
        !           473: 
        !           474:        switch (nc) {
        !           475:        case '^':
        !           476:        case '!':
        !           477:                return(EXPLICIT);
        !           478: 
        !           479:        case ':':
        !           480:                return(IMPLICIT);
        !           481: 
        !           482:        default:
        !           483:                return(0);
        !           484:        }
        !           485:        /* NOTREACHED */
        !           486: }
        !           487:                
        !           488: /*
        !           489:  * Do name optimization for an explicitly routed network (eg BTL network).
        !           490:  */
        !           491: 
        !           492: optimex(net, name)
        !           493:        char net[], name[];
        !           494: {
        !           495:        register char *cp, *rp;
        !           496:        register int m;
        !           497:        char *rindex();
        !           498: 
        !           499:        strcpy(name, net);
        !           500:        cp = name;
        !           501:        if (strlen(cp) == 0)
        !           502:                return(-1);
        !           503:        if (cp[strlen(cp)-1] == LOCAL) {
        !           504:                name[0] = 0;
        !           505:                return(0);
        !           506:        }
        !           507:        for (cp = name; *cp; cp++) {
        !           508:                m = *cp;
        !           509:                rp = rindex(cp+1, m);
        !           510:                if (rp != NOSTR)
        !           511:                        strcpy(cp, rp);
        !           512:        }
        !           513:        return(0);
        !           514: }
        !           515: 
        !           516: /*
        !           517:  * Do name optimization for implicitly routed network (eg, arpanet,
        !           518:  * Berkeley network)
        !           519:  */
        !           520: 
        !           521: optimimp(net, name)
        !           522:        char net[], name[];
        !           523: {
        !           524:        register char *cp;
        !           525:        register int m;
        !           526: 
        !           527:        cp = net;
        !           528:        if (strlen(cp) == 0)
        !           529:                return(-1);
        !           530:        m = cp[strlen(cp) - 1];
        !           531:        if (m == LOCAL) {
        !           532:                strcpy(name, "");
        !           533:                return(0);
        !           534:        }
        !           535:        name[0] = m;
        !           536:        name[1] = 0;
        !           537:        return(0);
        !           538: }
        !           539: 
        !           540: /*
        !           541: 
        !           542:  * Perform global optimization on the given network path.
        !           543:  * The trick here is to look ahead to see if there are any loops
        !           544:  * in the path and remove them.  The interpretation of loops is
        !           545:  * more strict here than in optimex since both the machine and net
        !           546:  * type must match.
        !           547:  */
        !           548: 
        !           549: optiboth(net)
        !           550:        char net[];
        !           551: {
        !           552:        register char *cp, *cp2;
        !           553:        char *rpair();
        !           554: 
        !           555:        cp = net;
        !           556:        if (strlen(cp) == 0)
        !           557:                return;
        !           558:        if ((strlen(cp) % 2) != 0) {
        !           559:                printf("Strange arg to optiboth\n");
        !           560:                return;
        !           561:        }
        !           562:        while (*cp) {
        !           563:                cp2 = rpair(cp+2, *cp, ntype(cp[1]));
        !           564:                if (cp2 != NOSTR)
        !           565:                        strcpy(cp, cp2);
        !           566:                cp += 2;
        !           567:        }
        !           568: }
        !           569: 
        !           570: /*
        !           571:  * Find the rightmost instance of the given (machine, type) pair.
        !           572:  */
        !           573: 
        !           574: char *
        !           575: rpair(str, mach, t)
        !           576:        char str[];
        !           577: {
        !           578:        register char *cp, *last;
        !           579: 
        !           580:        last = NOSTR;
        !           581:        while (*cp) {
        !           582:                if (*cp == mach /* && ntype(cp[1]) == t */ )
        !           583:                        last = cp;
        !           584:                cp += 2;
        !           585:        }
        !           586:        return(last);
        !           587: }
        !           588: 
        !           589: /*
        !           590:  * Change the network separators in the given network path
        !           591:  * to the preferred network transmission means.
        !           592:  */
        !           593: 
        !           594: prefer(name)
        !           595:        char name[];
        !           596: {
        !           597:        register char *cp;
        !           598:        register int state, n;
        !           599: 
        !           600:        state = LOCAL;
        !           601:        for (cp = name; *cp; cp += 2) {
        !           602:                n = best(state, *cp);
        !           603:                if (n)
        !           604:                        cp[1] = n;
        !           605:                state = *cp;
        !           606:        }
        !           607: }
        !           608: 
        !           609: /*
        !           610:  * Return the best network separator for the given machine pair.
        !           611:  */
        !           612: 
        !           613: struct netorder {
        !           614:        short   no_stat;
        !           615:        char    no_char;
        !           616: } netorder[] = {
        !           617:        CN,     ':',
        !           618:        AN,     '@',
        !           619:        SN,     ':',
        !           620:        BN,     '!',
        !           621:        -1,     0
        !           622: };
        !           623: 
        !           624: best(src, dest)
        !           625: {
        !           626:        register int dtype, stype;
        !           627:        register struct netorder *np;
        !           628: 
        !           629:        stype = nettype(src);
        !           630:        dtype = nettype(dest);
        !           631:        if (stype == 0 || dtype == 0) {
        !           632:                printf("ERROR:  unknown internal machine id\n");
        !           633:                return(0);
        !           634:        }
        !           635:        if ((stype & dtype) == 0) {
        !           636:                printf("No way to get from \"%s\" to \"%s\"\n", 
        !           637:                    netname(src), netname(dest));
        !           638:                return(0);
        !           639:        }
        !           640:        np = &netorder[0];
        !           641:        while ((np->no_stat & stype & dtype) == 0)
        !           642:                np++;
        !           643:        return(np->no_char);
        !           644: }
        !           645: 
        !           646: /*
        !           647:  * Add a single character onto a string.
        !           648:  */
        !           649: 
        !           650: stradd(str, c)
        !           651:        register char *str;
        !           652:        register int c;
        !           653: {
        !           654: 
        !           655:        str += strlen(str);
        !           656:        *str++ = c;
        !           657:        *str = 0;
        !           658: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.