1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
|
--- mapit.c.orig 1993-03-03 22:10:02.000000000 +0100
+++ mapit.c 2013-06-16 17:13:06.000000000 +0200
@@ -1,6 +1,6 @@
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
-static char *sccsid = "@(#)mapit.c 9.16 92/08/25";
+static const char *sccsid = "@(#)mapit.c 9.16 92/08/25";
#endif
#include "def.h"
@@ -17,43 +17,42 @@
long Nheap; /* end of heap */
long NumNcopy, Nlink, NumLcopy;
-void mapit();
-
/* imports */
extern long Nheap, Hashpart, Tabsize, Tcount;
extern int Tflag, Vflag;
extern node **Table, *Home;
extern char *Linkout, *Graphout;
-extern void freelink(), resetnodes(), printit(), dumpgraph();
-extern void showlinks(), die();
-extern long pack(), allocation();
-extern link *newlink(), *addlink();
-extern int maptrace(), tiebreaker();
-extern node *ncopy();
-
-
/* privates */
static long Heaphighwater;
-static link **Heap;
+static palink **Heap;
-STATIC void insert(), heapup(), heapdown(), heapswap(), backlinks();
-STATIC void setheapbits(), mtracereport(), heapchildren(), otracereport();
-STATIC link *min_node();
-STATIC int dehash(), skiplink(), skipterminalalias();
-STATIC Cost costof();
-STATIC node *mappedcopy();
+STATIC void insert(palink *l);
+STATIC void heapup(palink *l);
+STATIC void heapdown(palink *l);
+STATIC void heapswap(long i, long j);
+STATIC void backlinks(void);
+STATIC void setheapbits(register palink *l);
+STATIC void mtracereport(node *from, palink *l, const char *excuse);
+STATIC void heapchildren(register node *n);
+STATIC void otracereport(node *n);
+STATIC palink *min_node(void);
+STATIC int dehash(register node *n);
+STATIC int skiplink(palink *l, node *parent, register Cost cost, int trace);
+STATIC int skipterminalalias(node *n, node *next);
+STATIC Cost costof(register node *prev, register palink *l);
+STATIC node *mappedcopy(register node *n);
/* transform the graph to a shortest-path tree by marking tree edges */
void
mapit()
{ register node *n;
- register link *l;
+ register palink *l;
vprintf(stderr, "*** mapping\ttcount = %ld\n", Tcount);
Tflag = Tflag && Vflag; /* tracing here only if verbose */
/* re-use the hash table space for the heap */
- Heap = (link **) Table;
+ Heap = (palink **) Table;
Hashpart = pack(0L, Tabsize - 1);
/* expunge penalties from -a option and make circular copy lists */
@@ -84,7 +83,7 @@
n->n_flag |= MAPPED;
heapchildren(n); /* add children to heap */
}
- vprintf(stderr, "heap hiwat %d\nalloc %ldk, ncopy = %ld, nlink = %ld, lcopy = %ld\n", Heaphighwater, allocation(), NumNcopy, Nlink, NumLcopy);
+ vprintf(stderr, "heap hiwat %ld\nalloc %ldk, ncopy = %ld, nlink = %ld, lcopy = %ld\n", Heaphighwater, allocation(), NumNcopy, Nlink, NumLcopy);
if (Nheap != 0) /* sanity check */
die("null entry in heap");
@@ -116,7 +115,7 @@
STATIC void
heapchildren(n)
register node *n;
-{ register link *l;
+{ register palink *l;
register node *next;
register int mtrace;
register Cost cost;
@@ -132,11 +131,12 @@
if (l->l_flag & LTERMINAL)
l->l_to = next = ncopy(n, l);
- if ((n->n_flag & NTERMINAL) && (l->l_flag & LALIAS))
+ if ((n->n_flag & NTERMINAL) && (l->l_flag & LALIAS)) {
if (skipterminalalias(n, next))
continue;
else
l->l_to = next = ncopy(n, l);
+ }
if (next->n_flag & MAPPED) {
if (mtrace)
@@ -208,12 +208,12 @@
*/
STATIC int
skiplink(l, parent, cost, trace)
- link *l; /* new link to this node */
+ palink *l; /* new link to this node */
node *parent; /* (potential) new parent of this node */
register Cost cost; /* new cost to this node */
int trace; /* trace this link? */
{ register node *n; /* this node */
- register link *lheap; /* old link to this node */
+ register palink *lheap; /* old link to this node */
n = l->l_to;
@@ -263,7 +263,7 @@
STATIC Cost
costof(prev, l)
register node *prev;
- register link *l;
+ register palink *l;
{ register node *next;
register Cost cost;
@@ -296,6 +296,9 @@
|| (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
cost += INF; /* mixed syntax */
}
+ /* Dirk meyer 10.02.94 */
+ if ( cost < 0 ) /* Overflow, more than 31 bit */
+ cost = INF; /* Limit, to avoid recursive paths */
return cost;
}
@@ -303,7 +306,7 @@
/* binary heap implementation of priority queue */
STATIC void
insert(l)
- link *l;
+ palink *l;
{ register node *n;
n = l->l_to;
@@ -336,7 +339,7 @@
*/
STATIC void
heapup(l)
- link *l;
+ palink *l;
{ register long cindx, pindx; /* child, parent indices */
register Cost cost;
register node *child, *parent;
@@ -366,10 +369,10 @@
}
/* extract min (== Heap[1]) from heap */
-STATIC link *
+STATIC palink *
min_node()
-{ link *rval, *lastlink;
- register link **rheap;
+{ palink *rval, *lastlink;
+ register palink **rheap;
if (Nheap == 0)
return 0;
@@ -399,9 +402,9 @@
STATIC void
heapdown(l)
- link *l;
+ palink *l;
{ register long pindx, cindx;
- register link **rheap = Heap; /* in register -- heavily used */
+ register palink **rheap = Heap; /* in register -- heavily used */
node *child, *rchild, *parent;
pindx = l->l_to->n_tloc;
@@ -450,7 +453,7 @@
STATIC void
heapswap(i, j)
long i, j;
-{ register link *temp, **rheap;
+{ register palink *temp, **rheap;
rheap = Heap; /* heavily used -- put in register */
temp = rheap[i];
@@ -489,7 +492,7 @@
*/
STATIC void
backlinks()
-{ register link *l;
+{ register palink *l;
register node *n, *child;
node *nomap;
long i;
@@ -539,7 +542,7 @@
if (Vflag > 1)
fprintf(stderr, "backlink: %s <- %s\n", nomap->n_name, child->n_name);
}
- vprintf(stderr, "%d backlinks\n", Nheap);
+ vprintf(stderr, "%ld backlinks\n", Nheap);
}
/* find a mapped copy of n if it exists */
@@ -562,7 +565,7 @@
*/
STATIC void
setheapbits(l)
- register link *l;
+ register palink *l;
{ register node *n;
register node *parent;
@@ -588,8 +591,8 @@
STATIC void
mtracereport(from, l, excuse)
node *from;
- link *l;
- char *excuse;
+ palink *l;
+ const char *excuse;
{ node *to = l->l_to;
fprintf(stderr, "%-16s ", excuse);
@@ -638,7 +641,7 @@
#if 00
/* this hasn't been used for years */
for (i = 1; i < Nheap; i++) {
- link *l;
+ palink *l;
vprintf(stderr, "%5d %-16s", i, Heap[i]->l_to->n_name);
if ((l = Heap[i]->l_to->n_link) != 0) do {
@@ -647,7 +650,7 @@
vprintf(stderr, "\n");
}
for (i = Hashpart; i < Tabsize; i++) {
- link *l;
+ palink *l;
node *n;
vprintf(stderr, "%5d %-16s", i, Table[i]->n_name);
|
