![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to addnode.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 addnode.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 = "@(#)addnode.c 8.1 (down!honey) 86/01/19";
4: #endif
5:
6: #include "def.h"
7:
8: extern void lowercase(), rehash();
9: extern node *isprivate();
10: extern long hash();
11:
12: /*
13: * these numbers are chosen because:
14: * -> they are prime,
15: * -> they are monotonic increasing,
16: * -> each is a tad smaller than a multiple of 1024,
17: * -> they form a fibonacci sequence (almost).
18: * the first point yields good hash functions, the second is used for the
19: * standard re-hashing implementation of open addressing, the third
20: * optimizes for quirks in some mallocs i have seen, and the fourth simply
21: * appeals to me.
22: */
23: static int Primes[] = {
24: #ifndef SQUANDER
25: 1021, 2039, 3067, 5113, 8179,
26: #endif
27: 13309, 21499, 0
28: };
29:
30: static int Tabindex = -1;
31: static int Collision; /* mark host name collisions in hash() */
32:
33: node *
34: addnode(name)
35: register char *name;
36: {
37: register long i;
38: register node *n;
39:
40: if (Iflag)
41: lowercase(name);
42:
43: /* is it a private host? */
44: n = isprivate(name);
45: if (n)
46: return(n);
47:
48: i = hash(name, 0);
49: if (Table[i])
50: return(Table[i]);
51:
52: n = newnode();
53: n->n_name = strsave(name);
54: Table[i] = n;
55: n->n_tloc = i; /* essentially a back link to the table */
56: if (Collision)
57: n->n_flag |= COLLISION; /* name collision with private host */
58:
59: return(n);
60: }
61:
62: alias(n1, n2)
63: node *n1, *n2;
64: {
65: link *l;
66: extern link *addlink();
67:
68: l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
69: l->l_flag |= LALIAS;
70: l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
71: l->l_flag |= LALIAS;
72: if (Tflag)
73: atrace(n1, n2);
74: }
75:
76: /*
77: * fold a string into a long int. this algorithm ignores all but the last
78: * eight bytes, which affects < 15% of all host names, many of which have
79: * common prefixes anyway.
80: */
81: STATIC long
82: fold(str)
83: register char *str;
84: {
85: register long sum;
86:
87: sum = *str++;
88: while (*str) {
89: sum <<= 4;
90: sum += *str++;
91: }
92: if (sum < 0)
93: sum = -sum;
94: return(sum);
95: }
96:
97: #define HASH1(n) ((n) % Tabsize);
98: #define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2))) /* princeton!rs */
99:
100: /*
101: * with a 0.75 high water mark, probes per access should be 1.84.
102: * use long constant to force promotion.
103: */
104: #define HIGHWATER 75L
105: #define isfull(n, size) ((n) > ((size) * HIGHWATER) / 100)
106:
107: STATIC long
108: hash(name, unique)
109: char *name;
110: {
111: register long probe, hash2;
112: register node *n;
113:
114: if (Tabindex < 0) { /* first time */
115: Tabindex = 0;
116: Tabsize = Primes[0];
117: Table = newtable(Tabsize);
118: } else if (isfull(Ncount, Tabsize))
119: rehash(); /* more, more! */
120:
121: probe = fold(name);
122: /* don't change the order of the next two lines */
123: hash2 = HASH2(probe);
124: probe = HASH1(probe);
125: /* thank you! */
126:
127: /*
128: * probe the hash table.
129: * if unique is set, we require a fresh slot.
130: * otherwise, use double hashing to find either
131: * (1) an empty slot, or
132: * (2) a non-private copy of this host name
133: *
134: * as a side effect, if we notice a collision with a private host
135: * we mark the other so that it is skipped at output time.
136: */
137: Collision = 0;
138: while ((n = Table[probe]) != 0) {
139: if (strcmp(n->n_name, name) == 0) {
140: if (unique)
141: n->n_flag |= COLLISION;
142: else if (n->n_flag & ISPRIVATE)
143: Collision++;
144: else
145: break; /* this is it! */
146: }
147: probe -= hash2;
148: if (probe < 0)
149: probe += Tabsize;
150: }
151: return(probe);
152: }
153:
154: STATIC void
155: rehash()
156: {
157: register node **otable, **optr;
158: register long probe;
159: long osize;
160:
161: #ifdef DEBUG
162: hashanalyze();
163: #endif
164: optr = Table + Tabsize - 1; /* ptr to last */
165: otable = Table;
166: osize = Tabsize;
167: Tabsize = Primes[++Tabindex];
168: if (Tabsize == 0) { /* need more prime numbers */
169: fprintf(stderr, "%s: > %d hosts\n", ProgName, Primes[Tabindex-1]);
170: badmagic(1);
171: }
172: vprintf(stderr, "rehash into %d\n", Tabsize);
173: Table = newtable(Tabsize);
174:
175: do {
176: if (*optr == 0)
177: continue; /* empty slot in old table */
178: probe = hash((*optr)->n_name, (*optr)->n_flag & ISPRIVATE);
179: if (Table[probe] != 0) {
180: fprintf(stderr, "%s: rehash error\n", ProgName);
181: badmagic(1);
182: }
183: Table[probe] = *optr;
184: (*optr)->n_tloc = probe;
185: } while (optr-- > otable);
186: freetable(otable, osize);
187: }
188:
189: hashanalyze()
190: {
191: long probe, hash2;
192: int count, i, collision[8];
193: int longest = 0, total = 0, slots = 0;
194: int nslots = sizeof(collision)/sizeof(collision[0]);
195:
196: if (!Vflag)
197: return;
198:
199: strclear((char *) collision, sizeof(collision));
200: for (i = 0; i < Tabsize; i++) {
201: if (Table[i] == 0)
202: continue;
203: /* private hosts too hard to account for ... */
204: if (Table[i]->n_flag & ISPRIVATE)
205: continue;
206: count = 1;
207: probe = fold(Table[i]->n_name);
208: /* don't change the order of the next two lines */
209: hash2 = HASH2(probe);
210: probe = HASH1(probe);
211: /* thank you! */
212: while (Table[probe] != 0
213: && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
214: count++;
215: probe -= hash2;
216: if (probe < 0)
217: probe += Tabsize;
218: }
219: if (Table[probe] == 0) {
220: fprintf(stderr, "%s: impossible hash error for %s\n",
221: ProgName, Table[i]->n_name);
222: badmagic(1);
223: }
224:
225: total += count;
226: slots++;
227: if (count > longest)
228: longest = count;
229: if (count >= nslots)
230: count = 0;
231: collision[count]++;
232: }
233: for (i = 1; i < nslots; i++)
234: if (collision[i])
235: fprintf(stderr, "%d chains: %d (%ld%%)\n",
236: i, collision[i], (collision[i] * 100L)/ slots);
237: if (collision[0])
238: fprintf(stderr, "> %d chains: %d (%ld%%)\n",
239: nslots - 1, collision[0],
240: (collision[0] * 100L)/ slots);
241: fprintf(stderr, "%2.2f probes per access, longest chain: %d\n",
242: (double) total / slots, longest);
243: }
244:
245: STATIC void
246: lowercase(s)
247: register char *s;
248: {
249: do {
250: if (isupper(*s))
251: *s -= 'A' - 'a'; /* assumes ASCII */
252: } while (*s++);
253: }
254:
255: /*
256: * this might have to be recoded for performance if privates catch on
257: */
258: STATIC node *
259: isprivate(name)
260: register char *name;
261: {
262: register node *n;
263:
264: for (n = Private; n != 0; n = n->n_private)
265: if (strcmp(name, n->n_name) == 0)
266: return(n);
267: return(0);
268: }
269:
270: fixprivate()
271: {
272: register node *n, *next;
273: register long i;
274:
275: for (n = Private; n != 0; n = next) {
276: n->n_flag |= ISPRIVATE; /* overkill, but safe */
277: i = hash(n->n_name, 1);
278: if (Table[i] != 0) {
279: fprintf(stderr, "%s: impossible private node error on %s\n",
280: ProgName, n->n_name);
281: badmagic(1);
282: }
283:
284: Table[i] = n;
285: n->n_tloc = i; /* essentially a back link to the table */
286: next = n->n_private;
287: n->n_private = 0; /* clear for later use */
288: }
289: Private = 0;
290: }
291:
292: node *
293: addprivate(name)
294: register char *name;
295: {
296: register node *n;
297:
298: if (Iflag)
299: lowercase(name);
300: if ((n = isprivate(name)) != 0)
301: return(n);
302:
303: n = newnode();
304: n->n_name = strsave(name);
305: n->n_private = Private;
306: Private = n;
307: return(n);
308: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.