2.11BSD#431 - /usr/src/new/pathalias/mapaux.c

   1: /* pathalias -- by steve bellovin, as told to peter honeyman */
   2: #ifndef lint
   3: static char *sccsid = "@(#)mapaux.c	9.1 87/10/04";
   4: #endif /* lint */
   5: 
   6: #include "def.h"
   7: 
   8: /* imports */
   9: extern long Nheap, Hashpart, Tabsize;
  10: extern p_node *Table;
  11: extern p_node Home;
  12: extern char *Graphout, *Linkout, *Netchars, **Argv;
  13: extern void freelink(), die();
  14: extern long pack();
  15: extern p_link newlink();
  16: extern p_node newnode();
  17: #ifndef TMPFILES
  18: #define getnode(x) x
  19: #define getlink(y) y
  20: #else  /*TMPFILES*/
  21: extern node *getnode();
  22: extern link *getlink();
  23: #endif /*TMPFILES*/
  24: extern char *strsave();
  25: 
  26: /* exports */
  27: long pack();
  28: void resetnodes(), dumpgraph(), showlinks();
  29: int tiebreaker();
  30: p_node ncopy();
  31: 
  32: /* privates */
  33: static FILE *Gstream;   /* for dumping graph */
  34: STATIC void dumpnode(), untangle(), dfs();
  35: STATIC int height();
  36: STATIC p_link lcopy();
  37: 
  38: /*
  39:  * slide everything from Table[low] to Table[high]
  40:  * up toward the high end.  make room!  make room!
  41:  */
  42: long
  43: pack(low, high)
  44:     long low, high;
  45: {   long hole, next;
  46: 
  47:     /* find first "hole " */
  48:     for (hole = high; hole >= low && Table[hole] != 0; --hole)
  49:         ;
  50: 
  51:     /* repeatedly move next filled entry into last hole */
  52:     for (next = hole - 1; next >= low; --next) {
  53:         if (Table[next] != 0) {
  54:             Table[hole] = Table[next];
  55:             getnode(Table[hole])->n_tloc = hole;
  56:             Table[next] = 0;
  57:             while (Table[--hole] != 0)  /* find next hole */
  58:                 ;
  59:         }
  60:     }
  61:     return hole + 1;
  62: }
  63: 
  64: void
  65: resetnodes()
  66: {   register long i;
  67:     register p_node n;
  68: 
  69:     for (i = Hashpart; i < Tabsize; i++)
  70:         if ((n = Table[i]) != 0) {
  71:             getnode(n)->n_cost = (Cost) 0;
  72:             getnode(n)->n_flag &= ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT|NTERMINAL);
  73:             getnode(n)->n_copy = n;
  74:         }
  75: 
  76:     getnode(Home)->n_cost = (Cost) 0;
  77:     getnode(Home)->n_flag &= ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT|NTERMINAL);
  78:     getnode(Home)->n_copy = Home;
  79: }
  80: 
  81: void
  82: dumpgraph()
  83: {   register long i;
  84:     register p_node n;
  85: 
  86:     if ((Gstream = fopen(Graphout, "w")) == NULL) {
  87:         fprintf(stderr, "%s: ", Argv[0]);
  88:         perror(Graphout);
  89:         return;
  90:     }
  91: 
  92:     untangle(); /* untangle net cycles for proper output */
  93: 
  94:     for (i = Hashpart; i < Tabsize; i++) {
  95:         n = Table[i];
  96:         if (n == 0)
  97:             continue;   /* impossible, but ... */
  98:         /* a minor optimization ... */
  99:         if (getnode(n)->n_link == 0)
 100:             continue;
 101:         /* pathparse doesn't need these */
 102:         if (getnode(n)->n_flag & NNET)
 103:             continue;
 104:         dumpnode(n);
 105:     }
 106: }
 107: 
 108: STATIC void
 109: dumpnode(from)
 110:     register p_node from;
 111: {   register p_node to;
 112:     register p_link l;
 113:     p_link lnet = 0;
 114:     p_link ll;
 115:     p_link lnext;
 116: 
 117:     for (l = getnode(from)->n_link ; l; l = getlink(l)->l_next) {
 118:         to = getlink(l)->l_to;
 119:         if (from == to)
 120:             continue;   /* oops -- it's me! */
 121: 
 122:         if ((getnode(to)->n_flag & NNET) == 0) {
 123:             /* host -> host -- print host>host */
 124:             if (getlink(l)->l_cost == INF)
 125:                 continue;   /* phoney link */
 126:             fputs(getnode(from)->n_name, Gstream);
 127:             putc('>', Gstream);
 128:             fputs(getnode(to)->n_name, Gstream);
 129:             putc('\n', Gstream);
 130:         } else {
 131:             /*
 132: 			 * host -> net -- just cache it for now.
 133: 			 * first check for dups.  (quadratic, but
 134: 			 * n is small here.)
 135: 			 */
 136:             while (getnode(to)->n_root && to != getnode(to)->n_root)
 137:                 to = getnode(to)->n_root;
 138:             for (ll = lnet; ll; ll = getlink(ll)->l_next)
 139:                 if (strcmp(getnode(getlink(ll)->l_to)->n_name,
 140:                        getnode(to)->n_name) == 0)
 141:                     break;
 142:             if (ll)
 143:                 continue;   /* dup */
 144:             ll = newlink();
 145:             getlink(ll)->l_next = lnet;
 146:             getlink(ll)->l_to = to;
 147:             lnet = ll;
 148:         }
 149:     }
 150: 
 151:     /* dump nets */
 152:     if (lnet) {
 153:         /* nets -- print host@\tnet,net, ... */
 154:         fputs(getnode(from)->n_name, Gstream);
 155:         putc('@', Gstream);
 156:         putc('\t', Gstream);
 157:         for (ll = lnet; ll; ll = lnext) {
 158:             lnext = getlink(ll)->l_next;
 159:             fputs(getnode(getlink(ll)->l_to)->n_name, Gstream);
 160:             if (lnext)
 161:                 fputc(',', Gstream);
 162:             freelink(ll);
 163:         }
 164:         putc('\n', Gstream);
 165:     }
 166: }
 167: 
 168: /*
 169:  * remove cycles in net definitions.
 170:  *
 171:  * depth-first search
 172:  *
 173:  * for each net, run dfs on its neighbors (nets only).  if we return to
 174:  * a visited node, that's a net cycle.  mark the cycle with a pointer
 175:  * in the n_root field (which gets us closer to the root of this
 176:  * portion of the dfs tree).
 177:  */
 178: STATIC void
 179: untangle()
 180: {   register long i;
 181:     register p_node n;
 182: 
 183:     for (i = Hashpart; i < Tabsize; i++) {
 184:         n = Table[i];
 185:         if (n == 0 || (getnode(n)->n_flag & NNET) == 0
 186:             || getnode(n)->n_root)
 187:             continue;
 188:         dfs(n);
 189:     }
 190: }
 191: 
 192: STATIC void
 193: dfs(n)
 194:     register p_node n;
 195: {   register p_link l;
 196:     register p_node next;
 197: 
 198:     getnode(n)->n_flag |= INDFS;
 199:     getnode(n)->n_root = n;
 200:     for (l = getnode(n)->n_link; l; l = getlink(l)->l_next) {
 201:         next = getlink(l)->l_to;
 202:         if ((getnode(next)->n_flag & NNET) == 0)
 203:             continue;
 204:         if ((getnode(next)->n_flag & INDFS) == 0) {
 205:             dfs(next);
 206:             if (getnode(next)->n_root != next)
 207:                 getnode(n)->n_root = getnode(next)->n_root;
 208:         } else
 209:             getnode(n)->n_root = getnode(next)->n_root;
 210:     }
 211:     getnode(n)->n_flag &= ~INDFS;
 212: }
 213: 
 214: void
 215: showlinks()
 216: {   register p_link l;
 217:     register p_node n;
 218:     register long i;
 219:     FILE    *estream;
 220: 
 221:     if ((estream = fopen(Linkout, "w")) == 0)
 222:         return;
 223: 
 224:     for (i = Hashpart; i < Tabsize; i++) {
 225:         n = Table[i];
 226:         if (n == 0 || getnode(n)->n_link == 0)
 227:             continue;
 228:         for (l = getnode(n)->n_link; l; l = getlink(l)->l_next) {
 229:             fputs(getnode(n)->n_name, estream);
 230:             putc('\t', estream);
 231:             if (NETDIR(getlink(l)) == LRIGHT)
 232:                 putc(NETCHAR(getlink(l)), estream);
 233:             fputs(getnode(getlink(l)->l_to)->n_name, estream);
 234:             if (NETDIR(getlink(l)) == LLEFT)
 235:                 putc(NETCHAR(getlink(l)), estream);
 236:             fprintf(estream, "(%ld)\n", getlink(l)->l_cost);
 237:         }
 238:     }
 239:     (void) fclose(estream);
 240: }
 241: 
 242: /*
 243:  * n is node in heap, newp is candidate for new parent.
 244:  * choose between newp and n->n_parent for parent.
 245:  * return 0 to use newp, non-zero o.w.
 246:  */
 247: #define NEWP 0
 248: #define OLDP 1
 249: int
 250: tiebreaker(n, newp)
 251:     p_node n;
 252:     register p_node newp;
 253: {   register char *opname, *npname, *name;
 254:     register p_node oldp;
 255:     int metric;
 256: 
 257:     oldp = getnode(n)->n_parent;
 258: 
 259:     /* given the choice, avoid gatewayed nets */
 260:     if (GATEWAYED(getnode(newp)) && !GATEWAYED(getnode(oldp)))
 261:         return OLDP;
 262:     if (!GATEWAYED(getnode(newp)) && GATEWAYED(getnode(oldp)))
 263:         return NEWP;
 264: 
 265:     /* look at real parents, not nets */
 266:     while ((getnode(oldp)->n_flag & NNET) && getnode(oldp)->n_parent)
 267:         oldp = getnode(oldp)->n_parent;
 268:     while ((getnode(newp)->n_flag & NNET) && getnode(newp)->n_parent)
 269:         newp = getnode(newp)->n_parent;
 270: 
 271:     /* use fewer hops, if possible */
 272:     metric = height(oldp) - height(newp);
 273:     if (metric < 0)
 274:         return OLDP;
 275:     if (metric > 0)
 276:         return NEWP;
 277: 
 278:     /*
 279: 	 * compare names
 280: 	 */
 281:     opname = getnode(oldp)->n_name;
 282:     npname = getnode(newp)->n_name;
 283:     name = getnode(n)->n_name;
 284: 
 285:     /* use longest common prefix with parent */
 286:     while (*opname == *name && *npname == *name && *name) {
 287:         opname++;
 288:         npname++;
 289:         name++;
 290:     }
 291:     if (*opname == *name)
 292:         return OLDP;
 293:     if (*npname == *name)
 294:         return NEWP;
 295: 
 296:     /* use shorter host name */
 297:     metric = strlen(opname) - strlen(npname);
 298:     if (metric < 0)
 299:         return OLDP;
 300:     if (metric > 0)
 301:         return NEWP;
 302: 
 303:     /* use larger lexicographically */
 304:     metric = strcmp(opname, npname);
 305:     if (metric < 0)
 306:         return NEWP;
 307:     return OLDP;
 308: }
 309: 
 310: STATIC int
 311: height(n)
 312:     register p_node n;
 313: {   register int i = 0;
 314: 
 315:     if (n == 0)
 316:         return 0;
 317:     while ((n = getnode(n)->n_parent) != 0)
 318:         if (ISADOMAIN(getnode(n)) || !(getnode(n)->n_flag & NNET))
 319:             i++;
 320:     return i;
 321: }
 322: 
 323: /* l is a terminal edge from n -> next; return a copy of next */
 324: p_node
 325: ncopy(n)
 326:     register p_node n;
 327: {   register p_node ncp;
 328:     register p_link dummy;
 329: 
 330:     ncp = newnode();
 331: #ifndef TMPFILES
 332:     getnode(ncp)->n_name = getnode(n)->n_name;  /* nonvolatile */
 333: #else /*TMPFILES*/      /* It's not very nonvolatile in the cache! */
 334:     getnode(ncp)->n_name = strsave(getnode(n)->n_name);
 335: #endif /*TMPFILES*/
 336:     getnode(ncp)->n_tloc = --Hashpart; /* better not be > 20% of total ... */
 337:     if (Hashpart == Nheap)
 338:         die("too many terminal links");
 339:     Table[Hashpart] = ncp;
 340:     getnode(ncp)->n_copy = getnode(n)->n_copy;  /* circular list */
 341:     getnode(n)->n_copy = ncp;
 342:     dummy = lcopy(getnode(n)->n_link);
 343:     getnode(ncp)->n_link = dummy;
 344:     getnode(ncp)->n_flag = (getnode(n)->n_flag & ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT)) | NTERMINAL;
 345:     return ncp;
 346: }
 347: 
 348: STATIC p_link
 349: lcopy(l)
 350:     register p_link l;
 351: {   register p_link lcp;
 352:     register p_link ltp;
 353: 
 354:     if (l == 0)
 355:         return 0;
 356:     lcp = newlink();
 357: #ifndef TMPFILES
 358:     *getlink(lcp) = *getlink(l);
 359: #else /*TMPFILES*/  /* inefficient, but we must preserve l_seq */
 360:     getlink(lcp)->l_to = getlink(l)->l_to;
 361:     getlink(lcp)->l_cost = getlink(l)->l_cost;
 362:     getlink(lcp)->l_from = getlink(l)->l_from;
 363:     getlink(lcp)->l_flag = getlink(l)->l_flag;
 364:     getlink(lcp)->l_netop = getlink(l)->l_netop;
 365: #endif /*TMPFILES*/
 366:     getlink(lcp)->l_flag &= ~LTREE;
 367: #ifndef TMPFILES
 368:     getlink(lcp)->l_next = lcopy(getlink(l)->l_next);
 369: #else
 370:     /*
 371: 	 * we could avoid recursive cache flushing by breaking
 372: 	 * the above statement into two assignments, but the
 373: 	 * recursion overflows the stack for the giant att link chain.
 374: 	 */
 375:     ltp = lcp;
 376:     while ((l = getlink(l)->l_next)) {
 377:         ltp = getlink(ltp)->l_next = newlink();
 378:         getlink(ltp)->l_to = getlink(l)->l_to;
 379:         getlink(ltp)->l_cost = getlink(l)->l_cost;
 380:         getlink(ltp)->l_from = getlink(l)->l_from;
 381:         getlink(ltp)->l_flag = getlink(l)->l_flag;
 382:         getlink(ltp)->l_netop = getlink(l)->l_netop;
 383:         getlink(ltp)->l_flag &= ~LTREE;
 384:     }
 385: #endif
 386:     return lcp;
 387: }

Defined functions

Defined variables

Defined macros