![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mapaux.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / contrib / pathalias|
Return to mapaux.c CVS log | Up to [CSRG BSD Unix] / 43BSD / contrib / pathalias |
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.