Commit | Line | Data |
---|---|---|
15637ed4 RG |
1 | /* |
2 | * Copyright (c) 1988, 1989 Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * Redistribution and use in source and binary forms, with or without | |
6 | * modification, are permitted provided that the following conditions | |
7 | * are met: | |
8 | * 1. Redistributions of source code must retain the above copyright | |
9 | * notice, this list of conditions and the following disclaimer. | |
10 | * 2. Redistributions in binary form must reproduce the above copyright | |
11 | * notice, this list of conditions and the following disclaimer in the | |
12 | * documentation and/or other materials provided with the distribution. | |
13 | * 3. All advertising materials mentioning features or use of this software | |
14 | * must display the following acknowledgement: | |
15 | * This product includes software developed by the University of | |
16 | * California, Berkeley and its contributors. | |
17 | * 4. Neither the name of the University nor the names of its contributors | |
18 | * may be used to endorse or promote products derived from this software | |
19 | * without specific prior written permission. | |
20 | * | |
21 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
22 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
23 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
24 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
25 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
26 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
27 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
28 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
29 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
30 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
31 | * SUCH DAMAGE. | |
32 | * | |
33 | * @(#)radix.c 7.9 (Berkeley) 2/4/91 | |
34 | */ | |
35 | ||
36 | /* | |
37 | * Routines to build and maintain radix trees for routing lookups. | |
38 | */ | |
39 | #ifndef RNF_NORMAL | |
40 | #include "param.h" | |
dd18dc33 | 41 | #include "systm.h" |
15637ed4 RG |
42 | #include "radix.h" |
43 | #include "malloc.h" | |
44 | #define M_DONTWAIT M_NOWAIT | |
45 | #endif | |
46 | struct radix_node_head *mask_rnhead; | |
47 | #define rn_maskhead mask_rnhead->rnh_treetop | |
48 | struct radix_mask *rn_mkfreelist; | |
49 | struct radix_node_head *radix_node_head; | |
50 | #undef Bcmp | |
51 | #define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l)) | |
52 | /* | |
53 | * The data structure for the keys is a radix tree with one way | |
54 | * branching removed. The index rn_b at an internal node n represents a bit | |
55 | * position to be tested. The tree is arranged so that all descendants | |
56 | * of a node n have keys whose bits all agree up to position rn_b - 1. | |
57 | * (We say the index of n is rn_b.) | |
58 | * | |
59 | * There is at least one descendant which has a one bit at position rn_b, | |
60 | * and at least one with a zero there. | |
61 | * | |
62 | * A route is determined by a pair of key and mask. We require that the | |
63 | * bit-wise logical and of the key and mask to be the key. | |
64 | * We define the index of a route to associated with the mask to be | |
65 | * the first bit number in the mask where 0 occurs (with bit number 0 | |
66 | * representing the highest order bit). | |
67 | * | |
68 | * We say a mask is normal if every bit is 0, past the index of the mask. | |
69 | * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, | |
70 | * and m is a normal mask, then the route applies to every descendant of n. | |
71 | * If the index(m) < rn_b, this implies the trailing last few bits of k | |
72 | * before bit b are all 0, (and hence consequently true of every descendant | |
73 | * of n), so the route applies to all descendants of the node as well. | |
74 | * | |
75 | * The present version of the code makes no use of normal routes, | |
76 | * but similar logic shows that a non-normal mask m such that | |
77 | * index(m) <= index(n) could potentially apply to many children of n. | |
78 | * Thus, for each non-host route, we attach its mask to a list at an internal | |
79 | * node as high in the tree as we can go. | |
80 | */ | |
81 | ||
82 | struct radix_node * | |
83 | rn_search(v, head) | |
84 | struct radix_node *head; | |
85 | register caddr_t v; | |
86 | { | |
87 | register struct radix_node *x; | |
88 | ||
89 | for (x = head; x->rn_b >= 0;) { | |
90 | if (x->rn_bmask & v[x->rn_off]) | |
91 | x = x->rn_r; | |
92 | else | |
93 | x = x->rn_l; | |
94 | } | |
95 | return x; | |
96 | }; | |
97 | ||
98 | struct radix_node * | |
99 | rn_search_m(v, head, m) | |
100 | struct radix_node *head; | |
101 | register caddr_t v, m; | |
102 | { | |
103 | register struct radix_node *x; | |
104 | ||
105 | for (x = head; x->rn_b >= 0;) { | |
106 | if ((x->rn_bmask & m[x->rn_off]) && | |
107 | (x->rn_bmask & v[x->rn_off])) | |
108 | x = x->rn_r; | |
109 | else | |
110 | x = x->rn_l; | |
111 | } | |
112 | return x; | |
113 | }; | |
114 | ||
115 | ||
116 | static int gotOddMasks; | |
117 | static char maskedKey[MAXKEYLEN]; | |
118 | ||
119 | struct radix_node * | |
120 | rn_match(v, head) | |
121 | struct radix_node *head; | |
122 | caddr_t v; | |
123 | { | |
124 | register struct radix_node *t = head, *x; | |
125 | register caddr_t cp = v, cp2, cp3; | |
126 | caddr_t cplim, mstart; | |
127 | struct radix_node *saved_t; | |
128 | int off = t->rn_off, vlen = *(u_char *)cp, matched_off; | |
129 | ||
130 | /* | |
131 | * Open code rn_search(v, head) to avoid overhead of extra | |
132 | * subroutine call. | |
133 | */ | |
134 | for (; t->rn_b >= 0; ) { | |
135 | if (t->rn_bmask & cp[t->rn_off]) | |
136 | t = t->rn_r; | |
137 | else | |
138 | t = t->rn_l; | |
139 | } | |
140 | /* | |
141 | * See if we match exactly as a host destination | |
142 | */ | |
143 | cp += off; cp2 = t->rn_key + off; cplim = v + vlen; | |
144 | for (; cp < cplim; cp++, cp2++) | |
145 | if (*cp != *cp2) | |
146 | goto on1; | |
147 | /* | |
148 | * This extra grot is in case we are explicitly asked | |
149 | * to look up the default. Ugh! | |
150 | */ | |
151 | if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey) | |
152 | t = t->rn_dupedkey; | |
153 | return t; | |
154 | on1: | |
155 | matched_off = cp - v; | |
156 | saved_t = t; | |
157 | do { | |
158 | if (t->rn_mask) { | |
159 | /* | |
160 | * Even if we don't match exactly as a hosts; | |
161 | * we may match if the leaf we wound up at is | |
162 | * a route to a net. | |
163 | */ | |
164 | cp3 = matched_off + t->rn_mask; | |
165 | cp2 = matched_off + t->rn_key; | |
166 | for (; cp < cplim; cp++) | |
167 | if ((*cp2++ ^ *cp) & *cp3++) | |
168 | break; | |
169 | if (cp == cplim) | |
170 | return t; | |
171 | cp = matched_off + v; | |
172 | } | |
173 | } while (t = t->rn_dupedkey); | |
174 | t = saved_t; | |
175 | /* start searching up the tree */ | |
176 | do { | |
177 | register struct radix_mask *m; | |
178 | t = t->rn_p; | |
179 | if (m = t->rn_mklist) { | |
180 | /* | |
181 | * After doing measurements here, it may | |
182 | * turn out to be faster to open code | |
183 | * rn_search_m here instead of always | |
184 | * copying and masking. | |
185 | */ | |
186 | off = min(t->rn_off, matched_off); | |
187 | mstart = maskedKey + off; | |
188 | do { | |
189 | cp2 = mstart; | |
190 | cp3 = m->rm_mask + off; | |
191 | for (cp = v + off; cp < cplim;) | |
192 | *cp2++ = *cp++ & *cp3++; | |
193 | x = rn_search(maskedKey, t); | |
194 | while (x && x->rn_mask != m->rm_mask) | |
195 | x = x->rn_dupedkey; | |
196 | if (x && | |
197 | (Bcmp(mstart, x->rn_key + off, | |
198 | vlen - off) == 0)) | |
199 | return x; | |
200 | } while (m = m->rm_mklist); | |
201 | } | |
202 | } while (t != head); | |
203 | return 0; | |
204 | }; | |
205 | ||
206 | #ifdef RN_DEBUG | |
207 | int rn_nodenum; | |
208 | struct radix_node *rn_clist; | |
209 | int rn_saveinfo; | |
210 | #endif | |
211 | ||
212 | struct radix_node * | |
213 | rn_newpair(v, b, nodes) | |
214 | caddr_t v; | |
215 | struct radix_node nodes[2]; | |
216 | { | |
217 | register struct radix_node *tt = nodes, *t = tt + 1; | |
218 | t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); | |
219 | t->rn_l = tt; t->rn_off = b >> 3; | |
220 | tt->rn_b = -1; tt->rn_key = v; tt->rn_p = t; | |
221 | tt->rn_flags = t->rn_flags = RNF_ACTIVE; | |
222 | #ifdef RN_DEBUG | |
223 | tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; | |
224 | tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; | |
225 | #endif | |
226 | return t; | |
227 | } | |
228 | ||
229 | int rn_debug = 1; | |
230 | struct radix_node * | |
231 | rn_insert(v, head, dupentry, nodes) | |
232 | caddr_t v; | |
233 | struct radix_node *head; | |
234 | int *dupentry; | |
235 | struct radix_node nodes[2]; | |
236 | { | |
237 | int head_off = head->rn_off, vlen = (int)*((u_char *)v); | |
238 | register struct radix_node *t = rn_search(v, head); | |
239 | register caddr_t cp = v + head_off; | |
240 | register int b; | |
241 | struct radix_node *tt; | |
242 | /* | |
243 | *find first bit at which v and t->rn_key differ | |
244 | */ | |
245 | { | |
246 | register caddr_t cp2 = t->rn_key + head_off; | |
247 | register int cmp_res; | |
248 | caddr_t cplim = v + vlen; | |
249 | ||
250 | while (cp < cplim) | |
251 | if (*cp2++ != *cp++) | |
252 | goto on1; | |
253 | *dupentry = 1; | |
254 | return t; | |
255 | on1: | |
256 | *dupentry = 0; | |
257 | cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; | |
258 | for (b = (cp - v) << 3; cmp_res; b--) | |
259 | cmp_res >>= 1; | |
260 | } | |
261 | { | |
262 | register struct radix_node *p, *x = head; | |
263 | cp = v; | |
264 | do { | |
265 | p = x; | |
266 | if (cp[x->rn_off] & x->rn_bmask) | |
267 | x = x->rn_r; | |
268 | else x = x->rn_l; | |
269 | } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ | |
270 | #ifdef RN_DEBUG | |
271 | if (rn_debug) | |
272 | printf("Going In:\n"), traverse(p); | |
273 | #endif | |
274 | t = rn_newpair(v, b, nodes); tt = t->rn_l; | |
275 | if ((cp[p->rn_off] & p->rn_bmask) == 0) | |
276 | p->rn_l = t; | |
277 | else | |
278 | p->rn_r = t; | |
279 | x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ | |
280 | if ((cp[t->rn_off] & t->rn_bmask) == 0) { | |
281 | t->rn_r = x; | |
282 | } else { | |
283 | t->rn_r = tt; t->rn_l = x; | |
284 | } | |
285 | #ifdef RN_DEBUG | |
286 | if (rn_debug) | |
287 | printf("Coming out:\n"), traverse(p); | |
288 | #endif | |
289 | } | |
290 | return (tt); | |
291 | } | |
292 | ||
293 | struct radix_node * | |
294 | rn_addmask(netmask, search, skip) | |
295 | caddr_t netmask; | |
296 | { | |
297 | register struct radix_node *x; | |
298 | register caddr_t cp, cplim; | |
299 | register int b, mlen, j; | |
300 | int maskduplicated; | |
301 | ||
302 | mlen = *(u_char *)netmask; | |
303 | if (search) { | |
304 | x = rn_search(netmask, rn_maskhead); | |
305 | mlen = *(u_char *)netmask; | |
306 | if (Bcmp(netmask, x->rn_key, mlen) == 0) | |
307 | return (x); | |
308 | } | |
309 | R_Malloc(x, struct radix_node *, MAXKEYLEN + 2 * sizeof (*x)); | |
310 | if (x == 0) | |
311 | return (0); | |
312 | Bzero(x, MAXKEYLEN + 2 * sizeof (*x)); | |
313 | cp = (caddr_t)(x + 2); | |
314 | Bcopy(netmask, cp, mlen); | |
315 | netmask = cp; | |
316 | x = rn_insert(netmask, rn_maskhead, &maskduplicated, x); | |
317 | /* | |
318 | * Calculate index of mask. | |
319 | */ | |
320 | cplim = netmask + mlen; | |
321 | for (cp = netmask + skip; cp < cplim; cp++) | |
322 | if (*(u_char *)cp != 0xff) | |
323 | break; | |
324 | b = (cp - netmask) << 3; | |
325 | if (cp != cplim) { | |
326 | if (*cp != 0) { | |
327 | gotOddMasks = 1; | |
328 | for (j = 0x80; j; b++, j >>= 1) | |
329 | if ((j & *cp) == 0) | |
330 | break; | |
331 | } | |
332 | } | |
333 | x->rn_b = -1 - b; | |
334 | return (x); | |
335 | } | |
336 | ||
337 | struct radix_node * | |
338 | rn_addroute(v, netmask, head, treenodes) | |
339 | struct radix_node *head; | |
340 | caddr_t netmask, v; | |
341 | struct radix_node treenodes[2]; | |
342 | { | |
343 | register int j; | |
344 | register caddr_t cp; | |
345 | register struct radix_node *t, *x, *tt; | |
346 | short b = 0, b_leaf; | |
347 | int vlen = *(u_char *)v, mlen, keyduplicated; | |
348 | caddr_t cplim; unsigned char *maskp; | |
349 | struct radix_mask *m, **mp; | |
350 | struct radix_node *saved_tt; | |
351 | ||
352 | /* | |
353 | * In dealing with non-contiguous masks, there may be | |
354 | * many different routes which have the same mask. | |
355 | * We will find it useful to have a unique pointer to | |
356 | * the mask to speed avoiding duplicate references at | |
357 | * nodes and possibly save time in calculating indices. | |
358 | */ | |
359 | if (netmask) { | |
360 | x = rn_search(netmask, rn_maskhead); | |
361 | mlen = *(u_char *)netmask; | |
362 | if (Bcmp(netmask, x->rn_key, mlen) != 0) { | |
363 | x = rn_addmask(netmask, 0, head->rn_off); | |
364 | if (x == 0) | |
365 | return (0); | |
366 | } | |
367 | netmask = x->rn_key; | |
368 | b = -1 - x->rn_b; | |
369 | } | |
370 | /* | |
371 | * Deal with duplicated keys: attach node to previous instance | |
372 | */ | |
373 | saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); | |
374 | if (keyduplicated) { | |
375 | do { | |
376 | if (tt->rn_mask == netmask) | |
377 | return (0); | |
378 | t = tt; | |
379 | } while (tt = tt->rn_dupedkey); | |
380 | /* | |
381 | * If the mask is not duplicated, we wouldn't | |
382 | * find it among possible duplicate key entries | |
383 | * anyway, so the above test doesn't hurt. | |
384 | * | |
385 | * XXX: we really ought to sort the masks | |
386 | * for a duplicated key the same way as in a masklist. | |
387 | * It is an unfortunate pain having to relocate | |
388 | * the head of the list. | |
389 | */ | |
390 | t->rn_dupedkey = tt = treenodes; | |
391 | #ifdef RN_DEBUG | |
392 | t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; | |
393 | tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; | |
394 | #endif | |
395 | t = saved_tt; | |
396 | tt->rn_key = (caddr_t) v; | |
397 | tt->rn_b = -1; | |
398 | tt->rn_flags = t->rn_flags & ~RNF_ROOT; | |
399 | } | |
400 | /* | |
401 | * Put mask in tree. | |
402 | */ | |
403 | if (netmask) { | |
404 | tt->rn_mask = netmask; | |
405 | tt->rn_b = x->rn_b; | |
406 | } | |
407 | t = saved_tt->rn_p; | |
408 | b_leaf = -1 - t->rn_b; | |
409 | if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; | |
410 | /* Promote general routes from below */ | |
411 | if (x->rn_b < 0) { | |
412 | if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { | |
413 | MKGet(m); | |
414 | if (m) { | |
415 | Bzero(m, sizeof *m); | |
416 | m->rm_b = x->rn_b; | |
417 | m->rm_mask = x->rn_mask; | |
418 | x->rn_mklist = t->rn_mklist = m; | |
419 | } | |
420 | } | |
421 | } else if (x->rn_mklist) { | |
422 | /* | |
423 | * Skip over masks whose index is > that of new node | |
424 | */ | |
425 | for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) | |
426 | if (m->rm_b >= b_leaf) | |
427 | break; | |
428 | t->rn_mklist = m; *mp = 0; | |
429 | } | |
430 | /* Add new route to highest possible ancestor's list */ | |
431 | if ((netmask == 0) || (b > t->rn_b )) | |
432 | return tt; /* can't lift at all */ | |
433 | b_leaf = tt->rn_b; | |
434 | do { | |
435 | x = t; | |
436 | t = t->rn_p; | |
437 | } while (b <= t->rn_b && x != head); | |
438 | /* | |
439 | * Search through routes associated with node to | |
440 | * insert new route according to index. | |
441 | * For nodes of equal index, place more specific | |
442 | * masks first. | |
443 | */ | |
444 | cplim = netmask + mlen; | |
445 | for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) { | |
446 | if (m->rm_b < b_leaf) | |
447 | continue; | |
448 | if (m->rm_b > b_leaf) | |
449 | break; | |
450 | if (m->rm_mask == netmask) { | |
451 | m->rm_refs++; | |
452 | tt->rn_mklist = m; | |
453 | return tt; | |
454 | } | |
455 | maskp = (u_char *)m->rm_mask; | |
456 | for (cp = netmask; cp < cplim; cp++) | |
457 | if (*(u_char *)cp > *maskp++) | |
458 | goto on2; | |
459 | } | |
460 | on2: | |
461 | MKGet(m); | |
462 | if (m == 0) { | |
463 | printf("Mask for route not entered\n"); | |
464 | return (tt); | |
465 | } | |
466 | Bzero(m, sizeof *m); | |
467 | m->rm_b = b_leaf; | |
468 | m->rm_mask = netmask; | |
469 | m->rm_mklist = *mp; | |
470 | *mp = m; | |
471 | tt->rn_mklist = m; | |
472 | return tt; | |
473 | } | |
474 | ||
475 | struct radix_node * | |
476 | rn_delete(v, netmask, head) | |
477 | caddr_t v, netmask; | |
478 | struct radix_node *head; | |
479 | { | |
480 | register struct radix_node *t, *p, *x = head; | |
481 | register struct radix_node *tt = rn_search(v, x); | |
482 | int b, head_off = x->rn_off, vlen = * (u_char *) v; | |
483 | struct radix_mask *m, *saved_m, **mp; | |
484 | struct radix_node *dupedkey, *saved_tt = tt; | |
485 | ||
486 | if (tt == 0 || | |
487 | Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) | |
488 | return (0); | |
489 | /* | |
490 | * Delete our route from mask lists. | |
491 | */ | |
492 | if (dupedkey = tt->rn_dupedkey) { | |
493 | if (netmask) | |
494 | netmask = rn_search(netmask, rn_maskhead)->rn_key; | |
495 | while (tt->rn_mask != netmask) | |
496 | if ((tt = tt->rn_dupedkey) == 0) | |
497 | return (0); | |
498 | } | |
499 | if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) | |
500 | goto on1; | |
501 | if (m->rm_mask != tt->rn_mask) { | |
502 | printf("rn_delete: inconsistent annotation\n"); | |
503 | goto on1; | |
504 | } | |
505 | if (--m->rm_refs >= 0) | |
506 | goto on1; | |
507 | b = -1 - tt->rn_b; | |
508 | t = saved_tt->rn_p; | |
509 | if (b > t->rn_b) | |
510 | goto on1; /* Wasn't lifted at all */ | |
511 | do { | |
512 | x = t; | |
513 | t = t->rn_p; | |
514 | } while (b <= t->rn_b && x != head); | |
515 | for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) | |
516 | if (m == saved_m) { | |
517 | *mp = m->rm_mklist; | |
518 | MKFree(m); | |
519 | break; | |
520 | } | |
521 | if (m == 0) | |
522 | printf("rn_delete: couldn't find our annotation\n"); | |
523 | on1: | |
524 | /* | |
525 | * Eliminate us from tree | |
526 | */ | |
527 | if (tt->rn_flags & RNF_ROOT) | |
528 | return (0); | |
529 | #ifdef RN_DEBUG | |
530 | /* Get us out of the creation list */ | |
531 | for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} | |
532 | if (t) t->rn_ybro = tt->rn_ybro; | |
533 | #endif RN_DEBUG | |
534 | t = tt->rn_p; | |
535 | if (dupedkey) { | |
536 | if (tt == saved_tt) { | |
537 | x = dupedkey; x->rn_p = t; | |
538 | if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; | |
539 | #ifndef RN_DEBUG | |
540 | x++; t = tt + 1; *x = *t; p = t->rn_p; | |
541 | #else | |
542 | x++; b = x->rn_info; t = tt + 1; *x = *t; p = t->rn_p; | |
543 | x->rn_info = b; | |
544 | #endif | |
545 | if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; | |
546 | x->rn_l->rn_p = x; x->rn_r->rn_p = x; | |
547 | } else { | |
548 | for (p = saved_tt; p && p->rn_dupedkey != tt;) | |
549 | p = p->rn_dupedkey; | |
550 | if (p) p->rn_dupedkey = tt->rn_dupedkey; | |
551 | else printf("rn_delete: couldn't find us\n"); | |
552 | } | |
553 | goto out; | |
554 | } | |
555 | if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; | |
556 | p = t->rn_p; | |
557 | if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; | |
558 | x->rn_p = p; | |
559 | /* | |
560 | * Demote routes attached to us. | |
561 | */ | |
562 | if (t->rn_mklist) { | |
563 | if (x->rn_b >= 0) { | |
564 | for (mp = &x->rn_mklist; m = *mp;) | |
565 | mp = &m->rm_mklist; | |
566 | *mp = t->rn_mklist; | |
567 | } else { | |
568 | for (m = t->rn_mklist; m;) { | |
569 | struct radix_mask *mm = m->rm_mklist; | |
570 | if (m == x->rn_mklist && (--(m->rm_refs) < 0)) { | |
571 | x->rn_mklist = 0; | |
572 | MKFree(m); | |
573 | } else | |
574 | printf("%s %x at %x\n", | |
575 | "rn_delete: Orphaned Mask", m, x); | |
576 | m = mm; | |
577 | } | |
578 | } | |
579 | } | |
580 | /* | |
581 | * We may be holding an active internal node in the tree. | |
582 | */ | |
583 | x = tt + 1; | |
584 | if (t != x) { | |
585 | #ifndef RN_DEBUG | |
586 | *t = *x; | |
587 | #else | |
588 | b = t->rn_info; *t = *x; t->rn_info = b; | |
589 | #endif | |
590 | t->rn_l->rn_p = t; t->rn_r->rn_p = t; | |
591 | p = x->rn_p; | |
592 | if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; | |
593 | } | |
594 | out: | |
595 | tt->rn_flags &= ~RNF_ACTIVE; | |
596 | tt[1].rn_flags &= ~RNF_ACTIVE; | |
597 | return (tt); | |
598 | } | |
599 | char rn_zeros[MAXKEYLEN], rn_ones[MAXKEYLEN]; | |
600 | ||
601 | rn_inithead(head, off, af) | |
602 | struct radix_node_head **head; | |
603 | int off; | |
604 | { | |
605 | register struct radix_node_head *rnh; | |
606 | register struct radix_node *t, *tt, *ttt; | |
607 | if (*head) | |
608 | return (1); | |
609 | R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); | |
610 | if (rnh == 0) | |
611 | return (0); | |
612 | Bzero(rnh, sizeof (*rnh)); | |
613 | *head = rnh; | |
614 | t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); | |
615 | ttt = rnh->rnh_nodes + 2; | |
616 | t->rn_r = ttt; | |
617 | t->rn_p = t; | |
618 | tt = t->rn_l; | |
619 | tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; | |
620 | tt->rn_b = -1 - off; | |
621 | *ttt = *tt; | |
622 | ttt->rn_key = rn_ones; | |
623 | rnh->rnh_af = af; | |
624 | rnh->rnh_treetop = t; | |
625 | if (radix_node_head == 0) { | |
626 | caddr_t cp = rn_ones, cplim = rn_ones + MAXKEYLEN; | |
627 | while (cp < cplim) | |
628 | *cp++ = -1; | |
629 | if (rn_inithead(&radix_node_head, 0, 0) == 0) { | |
630 | Free(rnh); | |
631 | *head = 0; | |
632 | return (0); | |
633 | } | |
634 | mask_rnhead = radix_node_head; | |
635 | } | |
636 | rnh->rnh_next = radix_node_head->rnh_next; | |
637 | if (radix_node_head != rnh) | |
638 | radix_node_head->rnh_next = rnh; | |
639 | return (1); | |
640 | } |