* Search for longest-prefix match in given @head */
| 271 | * Search for longest-prefix match in given @head |
| 272 | */ |
| 273 | struct radix_node * |
| 274 | rn_match(void *v_arg, struct radix_head *head) |
| 275 | { |
| 276 | caddr_t v = v_arg; |
| 277 | struct radix_node *t = head->rnh_treetop, *x; |
| 278 | caddr_t cp = v, cp2; |
| 279 | caddr_t cplim; |
| 280 | struct radix_node *saved_t, *top = t; |
| 281 | int off = t->rn_offset, vlen = LEN(cp), matched_off; |
| 282 | int test, b, rn_bit; |
| 283 | |
| 284 | /* |
| 285 | * Open code rn_search(v, top) to avoid overhead of extra |
| 286 | * subroutine call. |
| 287 | */ |
| 288 | for (; t->rn_bit >= 0; ) { |
| 289 | if (t->rn_bmask & cp[t->rn_offset]) |
| 290 | t = t->rn_right; |
| 291 | else |
| 292 | t = t->rn_left; |
| 293 | } |
| 294 | /* |
| 295 | * See if we match exactly as a host destination |
| 296 | * or at least learn how many bits match, for normal mask finesse. |
| 297 | * |
| 298 | * It doesn't hurt us to limit how many bytes to check |
| 299 | * to the length of the mask, since if it matches we had a genuine |
| 300 | * match and the leaf we have is the most specific one anyway; |
| 301 | * if it didn't match with a shorter length it would fail |
| 302 | * with a long one. This wins big for class B&C netmasks which |
| 303 | * are probably the most common case... |
| 304 | */ |
| 305 | if (t->rn_mask) |
| 306 | vlen = *(u_char *)t->rn_mask; |
| 307 | cp += off; cp2 = t->rn_key + off; cplim = v + vlen; |
| 308 | for (; cp < cplim; cp++, cp2++) |
| 309 | if (*cp != *cp2) |
| 310 | goto on1; |
| 311 | /* |
| 312 | * This extra grot is in case we are explicitly asked |
| 313 | * to look up the default. Ugh! |
| 314 | * |
| 315 | * Never return the root node itself, it seems to cause a |
| 316 | * lot of confusion. |
| 317 | */ |
| 318 | if (t->rn_flags & RNF_ROOT) |
| 319 | t = t->rn_dupedkey; |
| 320 | return (t); |
| 321 | on1: |
| 322 | test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ |
| 323 | for (b = 7; (test >>= 1) > 0;) |
| 324 | b--; |
| 325 | matched_off = cp - v; |
| 326 | b += matched_off << 3; |
| 327 | rn_bit = -1 - b; |
| 328 | /* |
| 329 | * If there is a host route in a duped-key chain, it will be first. |
| 330 | */ |
no test coverage detected