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