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