4.3BSD - /usr/src/new/pathalias/mapit.c

   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: }

Defined functions

Defined variables