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