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

   1: /* pathalias -- by steve bellovin, as told to peter honeyman */
   2: #ifndef lint
   3: static char *sccsid = "@(#)addlink.c	9.1 87/10/04";
   4: #endif /* lint */
   5: 
   6: #include "def.h"
   7: 
   8: /* exports */
   9: extern p_link addlink();
  10: extern void deadlink(), atrace();
  11: extern int tracelink();
  12: char *Netchars = "!:@%";    /* sparse, but sufficient */
  13: long Lcount;            /* how many edges? */
  14: 
  15: 
  16: /* imports */
  17: extern int Tflag, Dflag;
  18: extern void freelink();
  19: extern p_link newlink();
  20: extern p_node addnode();
  21: #ifndef TMPFILES
  22: #define getnode(x) x
  23: #define getlink(y) y
  24: #else  /*TMPFILES*/
  25: extern node *getnode();
  26: extern link *getlink();
  27: #endif /*TMPFILES*/
  28: extern void yyerror(), die();
  29: 
  30: /* privates */
  31: STATIC void netbits(), ltrace(), ltrprint();
  32: static p_link   Trace[NTRACE];
  33: static int  Tracecount;
  34: 
  35: p_link
  36: addlink(from, to, cost, netchar, netdir)
  37:     p_node from;
  38:     register p_node to;
  39:     Cost cost;
  40:     char netchar, netdir;
  41: {   register p_link l;
  42:     register p_link prev = 0;
  43: 
  44:     if (Tflag)
  45:         ltrace(from, to, cost, netchar, netdir);
  46:     /*
  47: 	 * maintain uniqueness for dead links (only).
  48: 	 */
  49:     for (l = getnode(from)->n_link; l; l = getlink(l)->l_next) {
  50:         if (!(getlink(l)->l_flag & LDEAD))
  51:             break;
  52:         if (to == getlink(l)->l_to) {
  53:             /* what the hell, use cheaper dead cost */
  54:             if (cost < getlink(l)->l_cost) {
  55:                 getlink(l)->l_cost = cost;
  56:                 netbits(l, netchar, netdir);
  57:             }
  58:             return l;
  59:         }
  60:         prev = l;
  61:     }
  62: 
  63:     /* allocate and link in the new link struct */
  64:     l = newlink();
  65:     if (cost != INF)    /* ignore back links */
  66:         Lcount++;
  67:     if (prev) {
  68:         getlink(l)->l_next = getlink(prev)->l_next;
  69:         getlink(prev)->l_next = l;
  70:     } else {
  71:         getlink(l)->l_next = getnode(from)->n_link;
  72:         getnode(from)->n_link = l;
  73:     }
  74: 
  75:     getlink(l)->l_to = to;
  76:     getlink(l)->l_cost = cost + getnode(from)->n_cost;    /* add penalty */
  77:     if (netchar == 0) {
  78:         netchar = DEFNET;
  79:         netdir = DEFDIR;
  80:     }
  81:     netbits(l, netchar, netdir);
  82:     if (Dflag && ISADOMAIN(getnode(from)) && !ISADOMAIN(getnode(to)))
  83:         getlink(l)->l_flag |= LTERMINAL;
  84: 
  85:     return l;
  86: }
  87: 
  88: void
  89: deadlink(nleft, nright)
  90:     p_node nleft;
  91:     p_node nright;
  92: {   p_link l;
  93:     p_link lhold = 0;
  94:     p_link lprev;
  95:     p_link lnext;
  96: 
  97:     /* DEAD host */
  98:     if (nright == 0) {
  99:         getnode(nleft)->n_flag |= NDEAD;    /* DEAD host */
 100:         return;
 101:     }
 102: 
 103:     /* DEAD link */
 104: 
 105:     /* grab <nleft, nright> instances at head of nleft adjacency list */
 106:     while ((l = getnode(nleft)->n_link) != 0 &&
 107:                     getlink(l)->l_to == nright) {
 108:         getnode(nleft)->n_link = getlink(l)->l_next;    /* disconnect */
 109:         getlink(l)->l_next = lhold;     /* terminate */
 110:         lhold = l;              /* add to lhold */
 111:     }
 112: 
 113:     /* move remaining <nleft, nright> instances */
 114:     for (lprev = getnode(nleft)->n_link; lprev && getlink(lprev)->l_next;
 115:                     lprev = getlink(lprev)->l_next) {
 116:         if (getlink(getlink(lprev)->l_next)->l_to == nright) {
 117:             l = getlink(lprev)->l_next;
 118:             getlink(lprev)->l_next = getlink(l)->l_next;    /* disconnect */
 119:             getlink(l)->l_next = lhold; /* terminate */
 120:             lhold = l;
 121:         }
 122:     }
 123: 
 124:     /* check for emptiness */
 125:     if (lhold == 0) {
 126:         getlink(addlink(nleft, nright, INF / 2, DEFNET, DEFDIR))->l_flag |= LDEAD;
 127:         return;
 128:     }
 129: 
 130:     /* reinsert deleted edges as DEAD links */
 131:     for (l = lhold; l; l = lnext) {
 132:         lnext = getlink(l)->l_next;
 133:         getlink(addlink(nleft, nright, getlink(l)->l_cost,
 134:             NETCHAR(getlink(l)),
 135:             NETDIR(getlink(l))))->l_flag |= LDEAD;
 136:         freelink(l);
 137:     }
 138: }
 139: 
 140: STATIC void
 141: netbits(l, netchar, netdir)
 142:     register p_link l;
 143:     char netchar, netdir;
 144: {
 145:     getlink(l)->l_flag &= ~LDIR;
 146:     getlink(l)->l_flag |= netdir;
 147:     getlink(l)->l_netop = netchar;
 148: }
 149: 
 150: int
 151: tracelink(arg)
 152:     char *arg;
 153: {   char *bang;
 154:     p_link l;
 155:     register p_node tnode;
 156: 
 157:     if (Tracecount >= NTRACE)
 158:         return -1;
 159:     l = newlink();
 160:     bang = index(arg, '!');
 161:     if (bang) {
 162:         *bang = 0;
 163:         tnode = addnode(bang+1);
 164:         getlink(l)->l_to = tnode;
 165:     } else
 166:         getlink(l)->l_to = 0;
 167: 
 168:     tnode = addnode(arg);
 169:     getlink(l)->l_from = tnode;
 170:     Trace[Tracecount++] = l;
 171:     return 0;
 172: }
 173: 
 174: STATIC void
 175: ltrace(from, to, cost, netchar, netdir)
 176:     p_node from;
 177:     p_node to;
 178:     Cost cost;
 179:     char netchar, netdir;
 180: {   p_link l;
 181:     int i;
 182: 
 183:     for (i = 0; i < Tracecount; i++) {
 184:         l = Trace[i];
 185:         /* overkill, but you asked for it! */
 186:         if ((getlink(l)->l_to == 0
 187:          && (from == (p_node) getlink(l)->l_from
 188:          || to == (p_node) getlink(l)->l_from))
 189:          || (from == (p_node) getlink(l)->l_from
 190:          && to == getlink(l)->l_to)
 191:          || (to == (p_node) getlink(l)->l_from
 192:          && from == getlink(l)->l_to)) {
 193:             ltrprint(from, to, cost, netchar, netdir);
 194:             return;
 195:         }
 196:     }
 197: }
 198: 
 199: /* print a trace item */
 200: STATIC void
 201: ltrprint(from, to, cost, netchar, netdir)
 202:     p_node from;
 203:     p_node to;
 204:     Cost cost;
 205:     char netchar;
 206:     char netdir;
 207: {   char buf[256], *bptr = buf;
 208: 
 209:     strcpy(bptr, getnode(from)->n_name);
 210:     bptr += strlen(bptr);
 211:     *bptr++ = ' ';
 212:     if (netdir == LRIGHT)           /* @% */
 213:         *bptr++ = netchar;
 214:     strcpy(bptr, getnode(to)->n_name);
 215:     bptr += strlen(bptr);
 216:     if (netdir == LLEFT)            /* !: */
 217:         *bptr++ = netchar;
 218:     sprintf(bptr, "(%ld)", cost);
 219:     yyerror(buf);
 220: }
 221: 
 222: void
 223: atrace(n1, n2)
 224:     p_node n1;
 225:     p_node n2;
 226: {   p_link l;
 227:     int i;
 228:     char buf[256];
 229: 
 230:     for (i = 0; i < Tracecount; i++) {
 231:         l = Trace[i];
 232:         if (getlink(l)->l_to == 0
 233:             && ((p_node) getlink(l)->l_from == n1
 234:             || (p_node) getlink(l)->l_from == n2)) {
 235:             sprintf(buf, "%s = %s", getnode(n1)->n_name,
 236:                 getnode(n2)->n_name);
 237:             yyerror(buf);
 238:             return;
 239:         }
 240:     }
 241: }
 242: 
 243: #define EQ(n1, n2) strcmp(getnode(n1)->n_name, getnode(n2)->n_name) == 0
 244: maptrace(from, to)
 245:     register p_node from;
 246:     register p_node to;
 247: {   register p_link l;
 248:     register int i;
 249: 
 250:     for (i = 0; i < Tracecount; i++) {
 251:         l = Trace[i];
 252:         if (getlink(l)->l_to == 0) {
 253:             if (EQ(from, getlink(l)->l_from)
 254:                 || EQ(to, getlink(l)->l_from))
 255:                 return 1;
 256:         } else if (EQ(from, getlink(l)->l_from)
 257:                && EQ(to, getlink(l)->l_to))
 258:                 return 1;
 259:     }
 260:     return 0;
 261: }

Defined functions

Defined variables

Defined macros