4.3BSD - /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	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: }

Defined functions

Defined variables

Defined macros