![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mapit.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / new / pathalias|
Return to mapit.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / new / pathalias |
1.1 root 1: /* pathalias -- by steve bellovin, as told to peter honeyman */
2: #ifndef lint
3: static char *sccsid = "@(#)mapit.c 8.1 (down!honey) 86/01/19";
4: #endif
5:
6: #include "def.h"
7:
8: /* privates */
9: extern void reheap(), insert(), heapswap();
10: extern link *min_node(), *rmlink();
11: extern Cost costof();
12:
13: static long Nheap;
14: static long Heaphighwater;
15: static link **Heap;
16:
17:
18: /* transform the graph to a shortest-path tree by marking tree edges */
19:
20: mapit()
21: {
22: register node *n, *next;
23: register link *l;
24: link *lprev, *lnext;
25: Cost cost;
26:
27: /*
28: * re-use the hash table space for the heap.
29: */
30: Heap = (link **) Table;
31:
32: pack(); /* remove holes in the Table */
33: if (Linkout && *Linkout) /* dump cheapest links */
34: showlinks();
35: if (Graphout && *Graphout) /* dump the edge list */
36: dumpgraph();
37:
38: /* invent and insert a link for Home to get things started */
39: l = newlink();
40: l->l_to = Home;
41: (void) dehash(Home);
42: insert(l);
43:
44: /* main mapping loop */
45: remap:
46: Heaphighwater = Nheap;
47: while ((l = min_node()) != 0) {
48: l->l_flag |= LTREE;
49: n = l->l_to;
50: n->n_flag |= MAPPED;
51:
52: /* add children to heap */
53: lprev = 0;
54: for (l = n->n_link; l != 0; l = lnext) {
55:
56: next = l->l_to; /* neighboring node */
57: if (next->n_flag & MAPPED) {
58: lnext = rmlink(l, lprev, n);
59: continue;
60: }
61: cost = costof(n, l);
62:
63: if (skiplink(l, n, cost)) {
64: lnext = rmlink(l, lprev, n);
65: continue;
66: }
67:
68: /*
69: * put this link in the heap, in a place where it may
70: * percolate up, but not down. if new, or if cost is
71: * being increased, move to end. otherwise, cost is
72: * same or less, so leave it where it is. unfortunately,
73: * freeing a link already in the heap is too costly at
74: * this point.
75: *
76: * TODO: avoid heaping aliases and network members.
77: */
78: if (dehash(next) == 0) /* first time in heap */
79: insert(l); /* insert at end */
80: else {
81: /* replace heaped link by this one */
82: if (cost > next->n_cost) { /* gateway */
83: /* move old link to end of heap */
84: heapswap((long) (next->n_tloc), Nheap);
85: next->n_tloc = Nheap;
86: }
87: Heap[next->n_tloc] = l;
88: }
89:
90: next->n_cost = cost;
91: next->n_parent = n;
92: reheap(l); /* restore heap property */
93:
94: /*
95: * note whether we got here via a gatewayed net.
96: * domains are presumed to require gateways.
97: * aliases inherit parent's gateway status.
98: */
99: next->n_flag &= ~GATEWAYIN;
100: if (l->l_flag & LALIAS)
101: next->n_flag |= (n->n_flag & GATEWAYIN);
102: else if (GATEWAYED(n))
103: next->n_flag |= GATEWAYIN;
104: lprev = l; /* this link's a keeper */
105: lnext = l->l_next;
106: }
107:
108: }
109: vprintf(stderr, "heap high water mark was %d\n", Heaphighwater);
110:
111: /* sanity check on implementation */
112: if (Nheap != 0) {
113: fprintf(stderr, "%s: null entry found in heap\n", ProgName);
114: badmagic(1);
115: }
116:
117: if (Hashpart < Tabsize) {
118: /*
119: * add back links from unreachable hosts to reachable
120: * neighbors, then remap. asymptotically, this is
121: * quadratic. in practice, this is done exactly once.
122: */
123: backlinks();
124: if (Nheap)
125: goto remap;
126: }
127: if (Hashpart < Tabsize) {
128: fputs("You can't get there from here:\n", stderr);
129: for ( ; Hashpart < Tabsize; Hashpart++) {
130: fprintf(stderr, "\t%s", Table[Hashpart]->n_name);
131: if (Table[Hashpart]->n_flag & (ISPRIVATE|COLLISION))
132: fputs(" (private)", stderr);
133: putc('\n', stderr);
134: }
135: }
136: }
137:
138: /*
139: * can this link be ignored? if yes, return 1, o.w. 0.
140: * a link can be skipped if it is not in the shortest path tree.
141: */
142: STATIC int
143: skiplink(l, parent, cost)
144: link *l; /* new link to this node */
145: node *parent; /* new parent of this node */
146: Cost cost; /* new cost to this node */
147: {
148: node *n; /* this node */
149: link *lheap; /* existing link to this node */
150:
151: n = l->l_to;
152:
153: /* first time we've reached this node? */
154: if (n->n_tloc >= Hashpart)
155: return(0);
156:
157: lheap = Heap[n->n_tloc];
158:
159: /* examine links to nets that require gateways */
160: if (GATEWAYED(n)) {
161: /* if exactly one is a gateway, use it */
162: if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY))
163: return(1); /* old is gateway */
164: if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
165: return(0); /* new is gateway */
166:
167: /* no gateway or both gateways; resolve in standard way ... */
168: }
169:
170: /* examine dup link (sanity check) */
171: if (n->n_parent == parent && ((lheap->l_flag & LDEAD) || (l->l_flag & LDEAD))) {
172: fprintf(stderr, "%s: dup dead link not eliminated: %s -> %s\n",
173: ProgName, parent->n_name, n->n_name);
174: badmagic(1);
175: }
176:
177:
178: /* examine cost */
179: if (cost < n->n_cost)
180: return(0);
181: if (cost > n->n_cost)
182: return(1);
183:
184: /* all other things being equal, consult the oracle */
185: return(tiebreaker(n, parent));
186: }
187:
188: STATIC Cost
189: costof(prev, l)
190: register node *prev;
191: register link *l;
192: {
193: register node *next;
194: register Cost cost;
195:
196: next = l->l_to;
197:
198: if (l->l_flag & LALIAS) {
199: /* copy left/right bits */
200: next->n_flag &= ~(HASLEFT|HASRIGHT);
201: next->n_flag |= (prev->n_flag & (HASLEFT|HASRIGHT));
202: return(prev->n_cost); /* by definition */
203: }
204:
205:
206: cost = prev->n_cost + l->l_cost; /* basic cost */
207:
208: /*
209: * heuristics:
210: * charge for a dead link.
211: * charge for getting out of a dead host.
212: * charge for getting into a gatewayed net (except at a gateway).
213: * discourage mixing of left and right syntax when next is a host.
214: * charge for leaving a gatewayed net.
215: *
216: * life was simpler when pathalias computed true shortest paths.
217: */
218: if (l->l_flag & LDEAD) /* dead link */
219: cost += INF/2;
220: if (DEADHOST(prev)) /* dead host */
221: cost += INF/2;
222: if (GATEWAYED(next) && !(l->l_flag & LGATEWAY)) /* not gateway */
223: cost += INF/2;
224: if (!ISANET(next)) {
225: /* charge for mixed syntax here */
226: if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
227: || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
228: cost += DEFCOST;
229: }
230: /*
231: * if reached by a gatewayed net, discourage further links.
232: * this has some relevance to common carriers and the FCC ...
233: * the penalty inheres to hosts, not aliases, nets, or domains.
234: */
235: if ((prev->n_flag & GATEWAYIN) && !ISADOMAIN(prev) && !(prev->n_flag & NNET))
236: cost += INF/2; /* heavyweight, but appropriate */
237:
238: /* set left/right bits */
239: next->n_flag &= ~(HASLEFT|HASRIGHT);
240: if (NETDIR(l) == LLEFT || (prev->n_flag & HASLEFT))
241: next->n_flag |= HASLEFT;
242: if (NETDIR(l) == LRIGHT || (prev->n_flag & HASRIGHT))
243: next->n_flag |= HASRIGHT;
244:
245: return(cost);
246: }
247:
248: STATIC link *
249: rmlink(l, lprev, n)
250: link *l, *lprev;
251: node *n;
252: {
253: link *lnext;
254:
255: lnext = l->l_next;
256: if (lprev)
257: lprev->l_next = l->l_next;
258: else
259: n->n_link = l->l_next;
260: free((char *) l);
261: return(lnext);
262: }
263:
264: /*
265: * binary heap implementation of priority queue.
266: * TODO: make the heap smaller by giving inserting a placeholder
267: * for net members when the net is extracted. this requires storing the
268: * cost of a net in the net node itself -- yuck. is it worth it?
269: */
270:
271: STATIC void
272: insert(l)
273: link *l;
274: {
275: register node *n;
276:
277: n = l->l_to;
278: Heap[n->n_tloc] = 0;
279: if (Heap[Nheap+1] != 0) {
280: fprintf(stderr, "%s: heap error in insert\n", ProgName);
281: badmagic(1);
282: }
283: if (Nheap++ == 0) {
284: Heap[1] = l;
285: n->n_tloc = 1;
286: return;
287: }
288: if (Vflag && Nheap > Heaphighwater)
289: Heaphighwater = Nheap; /* diagnostics */
290:
291: /* insert at the end. caller must reheap(). */
292: Heap[Nheap] = l;
293: n->n_tloc = Nheap;
294: }
295:
296: /*
297: * replace existing link in heap by this one, then
298: * "percolate" up the heap by exchanging with the parent
299: */
300: STATIC void
301: reheap(l)
302: link *l;
303: {
304: register long loc, parent;
305: register Cost cost;
306: register node *n, *np;
307:
308: n = l->l_to;
309:
310: cost = n->n_cost;
311: for (loc = n->n_tloc; loc > 1; loc = parent) {
312: parent = loc / 2;
313: /* sanity check on implementation */
314: if (Heap[parent] == 0) {
315: fprintf(stderr, "%s: heap error in insert\n", ProgName);
316: badmagic(1);
317: }
318: np = Heap[parent]->l_to;
319: if (cost > np->n_cost)
320: return;
321: /* move nets below hosts for output stability */
322: if (cost == np->n_cost && ((n->n_flag & NNET) || !(np->n_flag & NNET)))
323: return;
324: heapswap(loc, parent);
325: }
326: }
327:
328: /* extract min (== Heap[1]) from heap */
329: STATIC link *
330: min_node()
331: {
332: link *rval;
333: register link **regheap;
334: register long i, child;
335:
336: if (Nheap == 0)
337: return(0);
338:
339: regheap = Heap; /* in register -- heavily used */
340: rval = regheap[1]; /* return this one */
341:
342: /* move last entry into root, percolate down */
343: regheap[1] = regheap[Nheap];
344: regheap[1]->l_to->n_tloc = 1;
345: regheap[Nheap] = 0;
346: if (--Nheap == 0)
347: return(rval);
348:
349: i = 1;
350: for (;;) {
351: /* swap with smaller child down the tree */
352: child = i * 2; /* lhs child is 2i, rhs is 2i+1. */
353: if (child >= Nheap)
354: return(rval);
355: /* use rhs child if smaller than lhs child */
356: if (regheap[child]->l_to->n_cost > regheap[child+1]->l_to->n_cost
357: || (regheap[child]->l_to->n_cost == regheap[child+1]->l_to->n_cost
358: && !ISANET(regheap[child+1]->l_to)))
359: child++;
360:
361: if (regheap[i]->l_to->n_cost < regheap[child]->l_to->n_cost)
362: return(rval);
363: /* move nets below hosts for output stability */
364: if (regheap[i]->l_to->n_cost == regheap[child]->l_to->n_cost
365: && (!ISANET(regheap[i]->l_to) || ISANET(regheap[child]->l_to)))
366: return(rval);
367: heapswap(i, child);
368: i = child;
369: }
370: /*NOTREACHED*/
371: }
372:
373: /* exchange Heap[i] and Heap[j] pointers */
374: STATIC void
375: heapswap(i, j)
376: long i, j;
377: {
378: register link *temp, **regheap;
379:
380: regheap = Heap; /* heavily used -- put in register */
381: temp = regheap[i];
382: regheap[i] = regheap[j];
383: regheap[j] = temp;
384: regheap[j]->l_to->n_tloc = j;
385: regheap[i]->l_to->n_tloc = i;
386: }
387:
388: /* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
389: dehash(n)
390: register node *n;
391: {
392: if (n->n_tloc < Hashpart)
393: return(1);
394:
395: /* swap with entry in Table[Hashpart] */
396: Table[Hashpart]->n_tloc = n->n_tloc;
397: Table[n->n_tloc] = Table[Hashpart];
398: Table[Hashpart] = n;
399:
400: n->n_tloc = Hashpart++;
401: return(0);
402: }
403:
404: backlinks()
405: {
406: link *l;
407: node *n, *parent, *nomap;
408: long i;
409:
410: for (i = Hashpart; i < Tabsize; i++) {
411: nomap = Table[i];
412: parent = 0;
413: for (l = nomap->n_link; l; l = l->l_next) {
414: n = l->l_to;
415: if (!(n->n_flag & MAPPED))
416: continue;
417: if (parent == 0) {
418: parent = n;
419: continue;
420: }
421: if (n->n_cost > parent->n_cost)
422: continue;
423: if (n->n_cost == parent->n_cost) {
424: nomap->n_parent = parent;
425: if (tiebreaker(nomap, n))
426: continue;
427: }
428: parent = n;
429: }
430: if (parent == 0)
431: continue;
432: (void) dehash(nomap);
433: l = addlink(parent, nomap, INF, DEFNET, DEFDIR);
434: nomap->n_parent = parent;
435: nomap->n_cost = costof(parent, l);
436: insert(l);
437: reheap(l);
438: }
439: vprintf(stderr, "%d backlinks\n", Nheap);
440: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.