Commit | Line | Data |
---|---|---|
95f51977 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 | } |