Return to mapit.c CVS log

Up to [CSRG BSD Unix] / 43BSD / contrib / pathalias

Annotation of 43BSD/contrib/pathalias/mapit.c, revision 1.1

1.1     ! root        1: /* pathalias -- by steve bellovin, as told to peter honeyman */
        !             2: #ifndef lint
        !             3: static char    *sccsid = "@(#)mapit.c  8.1 (down!honey) 86/01/19";
        !             4: #endif
        !             5: 
        !             6: #include "def.h"
        !             7: 
        !             8: /* privates */
        !             9: extern void    reheap(), insert(), heapswap();
        !            10: extern link    *min_node(), *rmlink();
        !            11: extern Cost    costof();
        !            12: 
        !            13: static long    Nheap;
        !            14: static long    Heaphighwater;
        !            15: static link    **Heap;
        !            16: 
        !            17: 
        !            18: /* transform the graph to a shortest-path tree by marking tree edges */
        !            19: 
        !            20: mapit()
        !            21: {
        !            22:        register node *n, *next;
        !            23:        register link *l;
        !            24:        link    *lprev, *lnext;
        !            25:        Cost cost;
        !            26: 
        !            27:        /*
        !            28:         * re-use the hash table space for the heap.
        !            29:         */
        !            30:        Heap = (link **) Table;
        !            31: 
        !            32:        pack();         /* remove holes in the Table */
        !            33:        if (Linkout && *Linkout)        /* dump cheapest links */
        !            34:                showlinks();
        !            35:        if (Graphout && *Graphout)      /* dump the edge list */
        !            36:                dumpgraph();
        !            37: 
        !            38:        /* invent and insert a link for Home to get things started */
        !            39:        l = newlink();
        !            40:        l->l_to = Home;
        !            41:        (void) dehash(Home);
        !            42:        insert(l);
        !            43: 
        !            44:        /* main mapping loop */
        !            45: remap:
        !            46:        Heaphighwater = Nheap;
        !            47:        while ((l = min_node()) != 0) {
        !            48:                l->l_flag |= LTREE;
        !            49:                n = l->l_to;
        !            50:                n->n_flag |= MAPPED;
        !            51:  
        !            52:                /* add children to heap */
        !            53:                lprev = 0;
        !            54:                for (l = n->n_link; l != 0; l = lnext) {
        !            55: 
        !            56:                        next = l->l_to;         /* neighboring node */
        !            57:                        if (next->n_flag & MAPPED) {
        !            58:                                lnext = rmlink(l, lprev, n);
        !            59:                                continue;
        !            60:                        }
        !            61:                        cost = costof(n, l);
        !            62: 
        !            63:                        if (skiplink(l, n, cost)) {
        !            64:                                lnext = rmlink(l, lprev, n);
        !            65:                                continue;
        !            66:                        }
        !            67: 
        !            68:                        /*
        !            69:                         * put this link in the heap, in a place where it may
        !            70:                         * percolate up, but not down.  if new, or if cost is
        !            71:                         * being increased, move to end.  otherwise, cost is
        !            72:                         * same or less, so leave it where it is.  unfortunately,
        !            73:                         * freeing a link already in the heap is too costly at
        !            74:                         * this point.
        !            75:                         *
        !            76:                         * TODO: avoid heaping aliases and network members.
        !            77:                         */
        !            78:                        if (dehash(next) == 0)  /* first time in heap */
        !            79:                                insert(l);      /* insert at end */
        !            80:                        else {
        !            81:                                /* replace heaped link by this one */
        !            82:                                if (cost > next->n_cost) {      /* gateway */
        !            83:                                        /* move old link to end of heap */
        !            84:                                        heapswap((long) (next->n_tloc), Nheap);
        !            85:                                        next->n_tloc = Nheap;
        !            86:                                }
        !            87:                                Heap[next->n_tloc] = l;
        !            88:                        }
        !            89:                                
        !            90:                        next->n_cost = cost;
        !            91:                        next->n_parent = n;
        !            92:                        reheap(l);              /* restore heap property */
        !            93: 
        !            94:                        /*
        !            95:                         * note whether we got here via a gatewayed net.
        !            96:                         * domains are presumed to require gateways.
        !            97:                         * aliases inherit parent's gateway status.
        !            98:                         */
        !            99:                        next->n_flag &= ~GATEWAYIN;
        !           100:                        if (l->l_flag & LALIAS)
        !           101:                                next->n_flag |= (n->n_flag & GATEWAYIN);
        !           102:                        else if (GATEWAYED(n))
        !           103:                                next->n_flag |= GATEWAYIN;
        !           104:                        lprev = l;      /* this link's a keeper */
        !           105:                        lnext = l->l_next;
        !           106:                }
        !           107: 
        !           108:        }
        !           109:        vprintf(stderr, "heap high water mark was %d\n", Heaphighwater);
        !           110: 
        !           111:        /* sanity check on implementation */
        !           112:        if (Nheap != 0) {
        !           113:                fprintf(stderr, "%s: null entry found in heap\n", ProgName);
        !           114:                badmagic(1);
        !           115:        }
        !           116: 
        !           117:        if (Hashpart < Tabsize) {
        !           118:                /*
        !           119:                 * add back links from unreachable hosts to reachable
        !           120:                 * neighbors, then remap.  asymptotically, this is
        !           121:                 * quadratic.  in practice, this is done exactly once.
        !           122:                 */
        !           123:                backlinks();
        !           124:                if (Nheap)
        !           125:                        goto remap;
        !           126:        }
        !           127:        if (Hashpart < Tabsize) {
        !           128:                fputs("You can't get there from here:\n", stderr);
        !           129:                for ( ; Hashpart < Tabsize; Hashpart++) {
        !           130:                        fprintf(stderr, "\t%s", Table[Hashpart]->n_name);
        !           131:                        if (Table[Hashpart]->n_flag & (ISPRIVATE|COLLISION))
        !           132:                                fputs(" (private)", stderr);
        !           133:                        putc('\n', stderr);
        !           134:                }
        !           135:        }
        !           136: }
        !           137: 
        !           138: /*
        !           139:  * can this link be ignored?  if yes, return 1, o.w. 0.
        !           140:  * a link can be skipped if it is not in the shortest path tree.
        !           141:  */
        !           142: STATIC int
        !           143: skiplink(l, parent, cost)
        !           144: link   *l;                     /* new link to this node */
        !           145: node   *parent;                /* new parent of this node */
        !           146: Cost   cost;                   /* new cost to this node */
        !           147: {
        !           148:        node    *n;             /* this node */
        !           149:        link    *lheap;         /* existing link to this node */
        !           150: 
        !           151:        n = l->l_to;
        !           152: 
        !           153:        /* first time we've reached this node? */
        !           154:        if (n->n_tloc >= Hashpart)
        !           155:                return(0);
        !           156: 
        !           157:        lheap = Heap[n->n_tloc];
        !           158: 
        !           159:        /* examine links to nets that require gateways */
        !           160:        if (GATEWAYED(n)) {
        !           161:                /* if exactly one is a gateway, use it */
        !           162:                if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY))
        !           163:                        return(1);      /* old is gateway */
        !           164:                if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
        !           165:                        return(0);      /* new is gateway */
        !           166: 
        !           167:                /* no gateway or both gateways;  resolve in standard way ... */
        !           168:        }
        !           169: 
        !           170:        /* examine dup link (sanity check) */
        !           171:        if (n->n_parent == parent && ((lheap->l_flag & LDEAD) || (l->l_flag & LDEAD))) {
        !           172:                fprintf(stderr, "%s: dup dead link not eliminated: %s -> %s\n",
        !           173:                        ProgName, parent->n_name, n->n_name);
        !           174:                badmagic(1);
        !           175:        }
        !           176: 
        !           177: 
        !           178:        /*  examine cost */
        !           179:        if (cost < n->n_cost)
        !           180:                return(0);
        !           181:        if (cost > n->n_cost)
        !           182:                return(1);
        !           183: 
        !           184:        /* all other things being equal, consult the oracle */
        !           185:        return(tiebreaker(n, parent));
        !           186: }
        !           187: 
        !           188: STATIC Cost
        !           189: costof(prev, l)
        !           190: register node  *prev;
        !           191: register link  *l;
        !           192: {
        !           193:        register node   *next;
        !           194:        register Cost   cost;
        !           195: 
        !           196:        next = l->l_to;
        !           197: 
        !           198:        if (l->l_flag & LALIAS) {
        !           199:                /* copy left/right bits */
        !           200:                next->n_flag &= ~(HASLEFT|HASRIGHT);
        !           201:                next->n_flag |= (prev->n_flag & (HASLEFT|HASRIGHT));
        !           202:                return(prev->n_cost);   /* by definition */
        !           203:        }
        !           204: 
        !           205:                
        !           206:        cost = prev->n_cost + l->l_cost;        /* basic cost */
        !           207: 
        !           208:        /*
        !           209:         * heuristics:
        !           210:         *    charge for a dead link.
        !           211:         *    charge for getting out of a dead host.
        !           212:         *    charge for getting into a gatewayed net (except at a gateway).
        !           213:         *    discourage mixing of left and right syntax when next is a host.
        !           214:         *    charge for leaving a gatewayed net.
        !           215:         *
        !           216:         * life was simpler when pathalias computed true shortest paths.
        !           217:         */
        !           218:        if (l->l_flag & LDEAD)          /* dead link */
        !           219:                cost += INF/2;
        !           220:        if (DEADHOST(prev))             /* dead host */
        !           221:                cost += INF/2;
        !           222:        if (GATEWAYED(next) && !(l->l_flag & LGATEWAY)) /* not gateway */
        !           223:                cost += INF/2;
        !           224:        if (!ISANET(next)) {
        !           225:                /* charge for mixed syntax here */
        !           226:                if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
        !           227:                 || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
        !           228:                        cost += DEFCOST;
        !           229:        }
        !           230:        /*
        !           231:         * if reached by a gatewayed net, discourage further links.
        !           232:         * this has some relevance to common carriers and the FCC ...
        !           233:         * the penalty inheres to hosts, not aliases, nets, or domains.
        !           234:         */
        !           235:        if ((prev->n_flag & GATEWAYIN) && !ISADOMAIN(prev) && !(prev->n_flag & NNET))
        !           236:                cost += INF/2;  /* heavyweight, but appropriate */
        !           237: 
        !           238:        /* set left/right bits */
        !           239:        next->n_flag &= ~(HASLEFT|HASRIGHT);
        !           240:        if (NETDIR(l) == LLEFT || (prev->n_flag & HASLEFT))
        !           241:                next->n_flag |= HASLEFT;
        !           242:        if (NETDIR(l) == LRIGHT || (prev->n_flag & HASRIGHT))
        !           243:                next->n_flag |= HASRIGHT;
        !           244: 
        !           245:        return(cost);
        !           246: }
        !           247: 
        !           248: STATIC link *
        !           249: rmlink(l, lprev, n)
        !           250: link   *l, *lprev;
        !           251: node   *n;
        !           252: {
        !           253:        link    *lnext;
        !           254: 
        !           255:        lnext = l->l_next;
        !           256:        if (lprev)
        !           257:                lprev->l_next = l->l_next;
        !           258:        else
        !           259:                n->n_link = l->l_next;
        !           260:        free((char *) l);
        !           261:        return(lnext);
        !           262: }
        !           263: 
        !           264: /*
        !           265:  * binary heap implementation of priority queue.
        !           266:  * TODO: make the heap smaller by giving inserting a placeholder
        !           267:  * for net members when the net is extracted.  this requires storing the
        !           268:  * cost of a net in the net node itself -- yuck.  is it worth it?
        !           269:  */
        !           270: 
        !           271: STATIC void
        !           272: insert(l)
        !           273: link   *l;
        !           274: {
        !           275:        register node   *n;
        !           276: 
        !           277:        n = l->l_to;
        !           278:        Heap[n->n_tloc] = 0;
        !           279:        if (Heap[Nheap+1] != 0) {
        !           280:                fprintf(stderr, "%s: heap error in insert\n", ProgName);
        !           281:                badmagic(1);
        !           282:        }
        !           283:        if (Nheap++ == 0) {
        !           284:                Heap[1] = l;
        !           285:                n->n_tloc = 1;
        !           286:                return;
        !           287:        }
        !           288:        if (Vflag && Nheap > Heaphighwater)
        !           289:                Heaphighwater = Nheap;  /* diagnostics */
        !           290: 
        !           291:        /* insert at the end.  caller must reheap(). */
        !           292:        Heap[Nheap] = l;
        !           293:        n->n_tloc = Nheap;
        !           294: }
        !           295: 
        !           296: /*
        !           297:  * replace existing link in heap by this one, then
        !           298:  * "percolate" up the heap by exchanging with the parent
        !           299:  */
        !           300: STATIC void
        !           301: reheap(l)
        !           302: link   *l;
        !           303: {
        !           304:        register long   loc, parent;
        !           305:        register Cost   cost;
        !           306:        register node   *n, *np;
        !           307: 
        !           308:        n = l->l_to;
        !           309: 
        !           310:        cost = n->n_cost;
        !           311:        for (loc = n->n_tloc; loc > 1; loc = parent) {
        !           312:                parent = loc / 2;
        !           313:                /* sanity check on implementation */
        !           314:                if (Heap[parent] == 0) {
        !           315:                        fprintf(stderr, "%s: heap error in insert\n", ProgName);
        !           316:                        badmagic(1);
        !           317:                }
        !           318:                np = Heap[parent]->l_to;
        !           319:                if (cost > np->n_cost)
        !           320:                        return;
        !           321:                /* move nets below hosts for output stability */
        !           322:                if (cost == np->n_cost && ((n->n_flag & NNET) || !(np->n_flag & NNET)))
        !           323:                        return;
        !           324:                heapswap(loc, parent);
        !           325:        }
        !           326: }
        !           327: 
        !           328: /* extract min (== Heap[1]) from heap */
        !           329: STATIC link    *
        !           330: min_node()
        !           331: {
        !           332:        link *rval;
        !           333:        register link **regheap;
        !           334:        register long   i, child;
        !           335:        
        !           336:        if (Nheap == 0)
        !           337:                return(0);
        !           338: 
        !           339:        regheap = Heap;         /* in register -- heavily used */
        !           340:        rval = regheap[1];      /* return this one */
        !           341:                        
        !           342:        /* move last entry into root, percolate down */
        !           343:        regheap[1] = regheap[Nheap];
        !           344:        regheap[1]->l_to->n_tloc = 1;
        !           345:        regheap[Nheap] = 0;
        !           346:        if (--Nheap == 0)
        !           347:                return(rval);
        !           348: 
        !           349:        i = 1;
        !           350:        for (;;) {
        !           351:                /* swap with smaller child down the tree */
        !           352:                child = i * 2;  /* lhs child is 2i, rhs is 2i+1. */
        !           353:                if (child >= Nheap)
        !           354:                        return(rval);
        !           355:                /* use rhs child if smaller than lhs child */
        !           356:                if (regheap[child]->l_to->n_cost > regheap[child+1]->l_to->n_cost
        !           357:                 || (regheap[child]->l_to->n_cost == regheap[child+1]->l_to->n_cost
        !           358:                  && !ISANET(regheap[child+1]->l_to)))
        !           359:                        child++;
        !           360:                        
        !           361:                if (regheap[i]->l_to->n_cost < regheap[child]->l_to->n_cost)
        !           362:                        return(rval);
        !           363:                /* move nets below hosts for output stability */
        !           364:                if (regheap[i]->l_to->n_cost == regheap[child]->l_to->n_cost
        !           365:                 && (!ISANET(regheap[i]->l_to) || ISANET(regheap[child]->l_to)))
        !           366:                        return(rval);
        !           367:                heapswap(i, child);
        !           368:                i = child;
        !           369:        }
        !           370:        /*NOTREACHED*/
        !           371: }
        !           372: 
        !           373: /* exchange Heap[i] and Heap[j] pointers */
        !           374: STATIC void
        !           375: heapswap(i, j)
        !           376: long   i, j;
        !           377: {
        !           378:        register link   *temp, **regheap;
        !           379: 
        !           380:        regheap = Heap; /* heavily used -- put in register */
        !           381:        temp = regheap[i];
        !           382:        regheap[i] = regheap[j];
        !           383:        regheap[j] = temp;
        !           384:        regheap[j]->l_to->n_tloc = j;
        !           385:        regheap[i]->l_to->n_tloc = i;
        !           386: }
        !           387: 
        !           388: /* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
        !           389: dehash(n)
        !           390: register node  *n;
        !           391: {
        !           392:        if (n->n_tloc < Hashpart)
        !           393:                return(1);
        !           394: 
        !           395:        /* swap with entry in Table[Hashpart] */
        !           396:        Table[Hashpart]->n_tloc = n->n_tloc;
        !           397:        Table[n->n_tloc] = Table[Hashpart];
        !           398:        Table[Hashpart] = n;
        !           399: 
        !           400:        n->n_tloc = Hashpart++;
        !           401:        return(0);
        !           402: }
        !           403: 
        !           404: backlinks()
        !           405: {
        !           406:        link *l;
        !           407:        node *n, *parent, *nomap;
        !           408:        long i;
        !           409: 
        !           410:        for (i = Hashpart; i < Tabsize; i++) {
        !           411:                nomap = Table[i];
        !           412:                parent = 0;
        !           413:                for (l = nomap->n_link; l; l = l->l_next) {
        !           414:                        n = l->l_to;
        !           415:                        if (!(n->n_flag & MAPPED))
        !           416:                                continue;
        !           417:                        if (parent == 0) {
        !           418:                                parent = n;
        !           419:                                continue;
        !           420:                        }
        !           421:                        if (n->n_cost > parent->n_cost)
        !           422:                                continue;
        !           423:                        if (n->n_cost == parent->n_cost) {
        !           424:                                nomap->n_parent = parent;
        !           425:                                if (tiebreaker(nomap, n))
        !           426:                                        continue;
        !           427:                        }
        !           428:                        parent = n;
        !           429:                }
        !           430:                if (parent == 0)
        !           431:                        continue;
        !           432:                (void) dehash(nomap);
        !           433:                l = addlink(parent, nomap, INF, DEFNET, DEFDIR);
        !           434:                nomap->n_parent = parent;
        !           435:                nomap->n_cost = costof(parent, l);
        !           436:                insert(l);
        !           437:                reheap(l);
        !           438:        }
        !           439:        vprintf(stderr, "%d backlinks\n", Nheap);
        !           440: }

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