Return to mapaux.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / new / pathalias

Annotation of 43BSDTahoe/new/pathalias/mapaux.c, revision 1.1

1.1     ! root        1: /* pathalias -- by steve bellovin, as told to peter honeyman */
        !             2: #ifndef lint
        !             3: static char    *sccsid = "@(#)mapaux.c 8.2 (down!honey) 86/01/26";
        !             4: #endif lint
        !             5: 
        !             6: #include "def.h"
        !             7: 
        !             8: void   pack();
        !             9: 
        !            10: void
        !            11: pack()
        !            12: {
        !            13:        long    hole, next;
        !            14: 
        !            15:        /* find first "hole " */
        !            16:        for (hole = Tabsize - 1; hole >= 0 && Table[hole] != 0; --hole)
        !            17:                ;
        !            18: 
        !            19:        /* repeatedly move next filled entry into last hole */
        !            20:        for (next = hole - 1; next >= 0; --next) {
        !            21:                if (Table[next] != 0) {
        !            22:                        Table[hole] = Table[next];
        !            23:                        Table[hole]->n_tloc = hole;
        !            24:                        Table[next] = 0;
        !            25:                        while (Table[--hole] != 0)      /* find next hole */
        !            26:                                ;
        !            27:                }
        !            28:        }
        !            29:        Hashpart = hole + 1;
        !            30: }
        !            31: 
        !            32: FILE   *Gstream;
        !            33: 
        !            34: dumpgraph()
        !            35: {
        !            36:        long    i;
        !            37:        node    *n;
        !            38: 
        !            39:        if ((Gstream = fopen(Graphout, "w")) == NULL) {
        !            40:                fprintf(stderr, "%s: ", ProgName);
        !            41:                perror(Graphout);
        !            42:        }
        !            43: 
        !            44:        untangle();     /* untangle net cycles for proper output */
        !            45: 
        !            46:        for (i = Hashpart; i < Tabsize; i++) {
        !            47:                n = Table[i];
        !            48:                if (n == 0)
        !            49:                        continue;       /* impossible, but ... */
        !            50:                /* a minor optimization ... */
        !            51:                if (n->n_link == 0)
        !            52:                        continue;
        !            53:                /* pathparse doesn't need these */
        !            54:                if (n->n_flag & NNET)
        !            55:                        continue;
        !            56:                dumpnode(n);
        !            57:        }
        !            58: }
        !            59: 
        !            60: dumpnode(from)
        !            61: node   *from;
        !            62: {
        !            63:        node    *to;
        !            64:        link    *l;
        !            65:        char    netbuf[BUFSIZ], *nptr = netbuf;
        !            66: 
        !            67:        for (l = from->n_link ; l; l = l->l_next) {
        !            68:                to = l->l_to;
        !            69:                if (from == to)
        !            70:                        continue;       /* oops -- it's me! */
        !            71: 
        !            72:                if ((to->n_flag & NNET) == 0) {
        !            73:                        /* host -> host -- print host>host */
        !            74:                        if (l->l_cost == INF)
        !            75:                                continue;       /* phoney link */
        !            76:                        fputs(from->n_name, Gstream);
        !            77:                        putc('>', Gstream);
        !            78:                        fputs(to->n_name, Gstream);
        !            79:                        putc('\n', Gstream);
        !            80:                } else {
        !            81:                        /* host -> net -- just cache it for now */
        !            82:                        while (to->n_root && to != to->n_root)
        !            83:                                to = to->n_root;
        !            84:                        *nptr++ = ',';
        !            85:                        strcpy(nptr, to->n_name);
        !            86:                        nptr += strlen(nptr);
        !            87:                }
        !            88:        }
        !            89: 
        !            90:        /* dump nets */
        !            91:        if (nptr != netbuf) {
        !            92:                /* nets -- print host@\tnet,net, ... */
        !            93:                *nptr = 0;
        !            94:                fputs(from->n_name, Gstream);
        !            95:                putc('@', Gstream);
        !            96:                *netbuf = '\t'; /* insert tab by killing initial ',' */
        !            97:                fputs(netbuf, Gstream); /* skip initial ',' */
        !            98:                putc('\n', Gstream);
        !            99:        }
        !           100: }
        !           101: 
        !           102: /*
        !           103:  * remove cycles in net definitions. 
        !           104:  *
        !           105:  * depth-first search
        !           106:  *
        !           107:  * for each net, run dfs on its neighbors (nets only).  if we return to
        !           108:  * a visited node, that's a net cycle.  mark the cycle with a pointer
        !           109:  * in the n_root field (which gets us closer to the root of this
        !           110:  * portion of the dfs tree).
        !           111:  */
        !           112: untangle()
        !           113: {
        !           114:        long    i;
        !           115:        node    *n;
        !           116: 
        !           117:        for (i = Hashpart; i < Tabsize; i++) {
        !           118:                n = Table[i];
        !           119:                if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
        !           120:                        continue;
        !           121:                dfs(n);
        !           122:        }
        !           123: }
        !           124: 
        !           125: dfs(n)
        !           126: node   *n;
        !           127: {
        !           128:        link    *l;
        !           129:        node    *next;
        !           130: 
        !           131:        n->n_flag |= INDFS;
        !           132:        n->n_root = n;
        !           133:        for (l = n->n_link; l; l = l->l_next) {
        !           134:                next = l->l_to;
        !           135:                if ((next->n_flag & NNET) == 0)
        !           136:                        continue;
        !           137:                if ((next->n_flag & INDFS) == 0) {
        !           138:                        dfs(next);
        !           139:                        if (next->n_root != next)
        !           140:                                n->n_root = next->n_root;
        !           141:                } else
        !           142:                        n->n_root = next->n_root;
        !           143:        }
        !           144:        n->n_flag &= ~INDFS;
        !           145: }
        !           146: 
        !           147: showlinks() 
        !           148: {
        !           149:        link    *l;
        !           150:        node    *n;
        !           151:        long    i;
        !           152:        FILE    *estream;
        !           153: 
        !           154:        if ((estream = fopen(Linkout, "w")) == 0)
        !           155:                return;
        !           156: 
        !           157:        for (i = Hashpart; i < Tabsize; i++) {
        !           158:                n = Table[i];
        !           159:                if (n == 0)     /* impossible, but ... */
        !           160:                        continue;
        !           161:                if (l = n->n_link) {
        !           162:                        fprintf(estream, "%s\t%s(%d)", n->n_name,
        !           163:                                l->l_to->n_name,
        !           164:                                l->l_cost ? l->l_cost : DEFCOST);
        !           165:                        for (l = l->l_next; l; l = l->l_next)
        !           166:                                fprintf(estream, ",\n\t%s(%d)", l->l_to->n_name,
        !           167:                                        l->l_cost ? l->l_cost : DEFCOST);
        !           168:                        fputc('\n', estream);
        !           169:                }
        !           170:        }
        !           171:        (void) fclose(estream);
        !           172: }
        !           173: 
        !           174: /*
        !           175:  * n is node in heap, newp is candidate for new parent.
        !           176:  * choose between newp and n->n_parent for parent.
        !           177:  * return 0 to use newp, non-zero o.w.
        !           178:  */
        !           179: #define NEWP 0
        !           180: #define OLDP 1
        !           181: tiebreaker(n, newp)
        !           182: node   *n, *newp;
        !           183: {
        !           184:        register char   *opname, *npname, *name;
        !           185:        node    *oldp;
        !           186:        int     metric;
        !           187: 
        !           188:        oldp = n->n_parent;
        !           189: 
        !           190:        /*
        !           191:         * given the choice, avoid gatewayed nets,
        !           192:         * thereby placating the FCC or some such.
        !           193:         */
        !           194:        if (GATEWAYED(newp) && !GATEWAYED(oldp))
        !           195:                return(OLDP);
        !           196:        if (!GATEWAYED(newp) && GATEWAYED(oldp))
        !           197:                return(NEWP);
        !           198: 
        !           199:        /* look at real parents, not nets */
        !           200:        while (oldp->n_flag & NNET)
        !           201:                oldp = oldp->n_parent;
        !           202:        while (newp->n_flag & NNET)
        !           203:                newp = newp->n_parent;
        !           204: 
        !           205:        /* use fewer hops, if possible */
        !           206:        metric = height(oldp) - height(newp);
        !           207:        if (metric < 0)
        !           208:                return(OLDP);
        !           209:        if (metric > 0)
        !           210:                return(NEWP);
        !           211: 
        !           212:        /* compare names */
        !           213:        opname = oldp->n_name;
        !           214:        npname = newp->n_name;
        !           215:        name = n->n_name;
        !           216: 
        !           217:        /* find point of departure */
        !           218:        while (*opname == *npname && *npname == *name) {
        !           219:                if (*name == 0) {
        !           220:                        fprintf(stderr, "%s: error in tie breaker\n", ProgName);
        !           221:                        badmagic(1);
        !           222:                }
        !           223:                opname++;
        !           224:                npname++;
        !           225:                name++;
        !           226:        }
        !           227: 
        !           228:        /* use longest match, if appl. */
        !           229:        if (*opname == *name || *opname == 0)
        !           230:                return(OLDP);
        !           231:        if (*npname == *name || *npname == 0)
        !           232:                return(NEWP);
        !           233: 
        !           234:        /* use shorter host name, if appl. */
        !           235:        metric = strlen(opname) - strlen(npname);
        !           236:        if (metric < 0)
        !           237:                return(OLDP);
        !           238:        if (metric > 0)
        !           239:                return(NEWP);
        !           240: 
        !           241:        /* use larger lexicographically (no reason) */
        !           242:        metric = strcmp(opname, npname);
        !           243:        if (metric < 0)
        !           244:                return(NEWP);
        !           245:        return(OLDP);
        !           246: }
        !           247: 
        !           248: height(n)
        !           249: register node  *n;
        !           250: {
        !           251:        register int i = 0;
        !           252: 
        !           253:        while ((n = n->n_parent) != 0)
        !           254:                if ((n->n_flag & NNET) == 0)
        !           255:                        i++;    /* should count domains too ... */
        !           256:        return(i);
        !           257: }

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