1193141Sdougb/* 2262706Serwin * Copyright (C) 2007-2009, 2011-2014 Internet Systems Consortium, Inc. ("ISC") 3193141Sdougb * 4193141Sdougb * Permission to use, copy, modify, and/or distribute this software for any 5193141Sdougb * purpose with or without fee is hereby granted, provided that the above 6193141Sdougb * copyright notice and this permission notice appear in all copies. 7193141Sdougb * 8193141Sdougb * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9193141Sdougb * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10193141Sdougb * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11193141Sdougb * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12193141Sdougb * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13193141Sdougb * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14193141Sdougb * PERFORMANCE OF THIS SOFTWARE. 15193141Sdougb */ 16193141Sdougb 17234010Sdougb/* $Id$ */ 18193141Sdougb 19193141Sdougb/* 20193141Sdougb * This source was adapted from MRT's RCS Ids: 21193141Sdougb * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp 22193141Sdougb * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp 23193141Sdougb */ 24193141Sdougb 25193141Sdougb#include <config.h> 26193141Sdougb 27193141Sdougb#include <isc/mem.h> 28193141Sdougb#include <isc/types.h> 29193141Sdougb#include <isc/util.h> 30193141Sdougb#include <isc/radix.h> 31193141Sdougb 32193141Sdougbstatic isc_result_t 33193141Sdougb_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, 34193141Sdougb void *dest, int bitlen); 35193141Sdougb 36193141Sdougbstatic void 37254897Serwin_deref_prefix(isc_prefix_t *prefix); 38193141Sdougb 39193141Sdougbstatic isc_result_t 40193141Sdougb_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix); 41193141Sdougb 42193141Sdougbstatic int 43193141Sdougb_comp_with_mask(void *addr, void *dest, u_int mask); 44193141Sdougb 45193141Sdougbstatic void 46193141Sdougb_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func); 47193141Sdougb 48193141Sdougbstatic isc_result_t 49193141Sdougb_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest, 50193141Sdougb int bitlen) 51193141Sdougb{ 52193141Sdougb isc_prefix_t *prefix; 53193141Sdougb 54193141Sdougb REQUIRE(target != NULL); 55193141Sdougb 56193141Sdougb if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC) 57193141Sdougb return (ISC_R_NOTIMPLEMENTED); 58193141Sdougb 59193141Sdougb prefix = isc_mem_get(mctx, sizeof(isc_prefix_t)); 60193141Sdougb if (prefix == NULL) 61193141Sdougb return (ISC_R_NOMEMORY); 62193141Sdougb 63193141Sdougb if (family == AF_INET6) { 64193141Sdougb prefix->bitlen = (bitlen >= 0) ? bitlen : 128; 65262706Serwin memmove(&prefix->add.sin6, dest, 16); 66193141Sdougb } else { 67193141Sdougb /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */ 68193141Sdougb prefix->bitlen = (bitlen >= 0) ? bitlen : 32; 69262706Serwin memmove(&prefix->add.sin, dest, 4); 70193141Sdougb } 71193141Sdougb 72193141Sdougb prefix->family = family; 73254897Serwin prefix->mctx = NULL; 74254897Serwin isc_mem_attach(mctx, &prefix->mctx); 75193141Sdougb 76193141Sdougb isc_refcount_init(&prefix->refcount, 1); 77193141Sdougb 78193141Sdougb *target = prefix; 79193141Sdougb return (ISC_R_SUCCESS); 80193141Sdougb} 81193141Sdougb 82193141Sdougbstatic void 83254897Serwin_deref_prefix(isc_prefix_t *prefix) { 84193141Sdougb int refs; 85193141Sdougb 86193141Sdougb if (prefix == NULL) 87193141Sdougb return; 88193141Sdougb 89193141Sdougb isc_refcount_decrement(&prefix->refcount, &refs); 90193141Sdougb 91193141Sdougb if (refs <= 0) { 92193141Sdougb isc_refcount_destroy(&prefix->refcount); 93254897Serwin isc_mem_putanddetach(&prefix->mctx, prefix, 94254897Serwin sizeof(isc_prefix_t)); 95193141Sdougb } 96193141Sdougb} 97193141Sdougb 98193141Sdougbstatic isc_result_t 99193141Sdougb_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) { 100193141Sdougb INSIST(prefix != NULL); 101193141Sdougb INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) || 102193141Sdougb (prefix->family == AF_INET6 && prefix->bitlen <= 128) || 103193141Sdougb (prefix->family == AF_UNSPEC && prefix->bitlen == 0)); 104193141Sdougb REQUIRE(target != NULL && *target == NULL); 105193141Sdougb 106193141Sdougb /* 107193141Sdougb * If this prefix is a static allocation, copy it into new memory. 108193141Sdougb * (Note, the refcount still has to be destroyed by the calling 109193141Sdougb * routine.) 110193141Sdougb */ 111193141Sdougb if (isc_refcount_current(&prefix->refcount) == 0) { 112193141Sdougb isc_result_t ret; 113193141Sdougb ret = _new_prefix(mctx, target, prefix->family, 114193141Sdougb &prefix->add, prefix->bitlen); 115254897Serwin return (ret); 116193141Sdougb } 117193141Sdougb 118193141Sdougb isc_refcount_increment(&prefix->refcount, NULL); 119193141Sdougb 120193141Sdougb *target = prefix; 121193141Sdougb return (ISC_R_SUCCESS); 122193141Sdougb} 123193141Sdougb 124193141Sdougbstatic int 125193141Sdougb_comp_with_mask(void *addr, void *dest, u_int mask) { 126193141Sdougb 127193141Sdougb /* Mask length of zero matches everything */ 128193141Sdougb if (mask == 0) 129193141Sdougb return (1); 130193141Sdougb 131193141Sdougb if (memcmp(addr, dest, mask / 8) == 0) { 132193141Sdougb int n = mask / 8; 133193141Sdougb int m = ((~0) << (8 - (mask % 8))); 134193141Sdougb 135193141Sdougb if ((mask % 8) == 0 || 136193141Sdougb (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m)) 137193141Sdougb return (1); 138193141Sdougb } 139193141Sdougb return (0); 140193141Sdougb} 141193141Sdougb 142193141Sdougbisc_result_t 143193141Sdougbisc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) { 144193141Sdougb isc_radix_tree_t *radix; 145193141Sdougb 146193141Sdougb REQUIRE(target != NULL && *target == NULL); 147193141Sdougb 148193141Sdougb radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t)); 149193141Sdougb if (radix == NULL) 150193141Sdougb return (ISC_R_NOMEMORY); 151193141Sdougb 152254897Serwin radix->mctx = NULL; 153254897Serwin isc_mem_attach(mctx, &radix->mctx); 154193141Sdougb radix->maxbits = maxbits; 155193141Sdougb radix->head = NULL; 156193141Sdougb radix->num_active_node = 0; 157193141Sdougb radix->num_added_node = 0; 158193141Sdougb RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */ 159193141Sdougb radix->magic = RADIX_TREE_MAGIC; 160193141Sdougb *target = radix; 161193141Sdougb return (ISC_R_SUCCESS); 162193141Sdougb} 163193141Sdougb 164193141Sdougb/* 165193141Sdougb * if func is supplied, it will be called as func(node->data) 166193141Sdougb * before deleting the node 167193141Sdougb */ 168193141Sdougb 169193141Sdougbstatic void 170193141Sdougb_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) { 171193141Sdougb 172193141Sdougb REQUIRE(radix != NULL); 173193141Sdougb 174193141Sdougb if (radix->head != NULL) { 175193141Sdougb isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; 176193141Sdougb isc_radix_node_t **Xsp = Xstack; 177193141Sdougb isc_radix_node_t *Xrn = radix->head; 178193141Sdougb 179193141Sdougb while (Xrn != NULL) { 180193141Sdougb isc_radix_node_t *l = Xrn->l; 181193141Sdougb isc_radix_node_t *r = Xrn->r; 182193141Sdougb 183193141Sdougb if (Xrn->prefix != NULL) { 184254897Serwin _deref_prefix(Xrn->prefix); 185193141Sdougb if (func != NULL && (Xrn->data[0] != NULL || 186193141Sdougb Xrn->data[1] != NULL)) 187193141Sdougb func(Xrn->data); 188193141Sdougb } else { 189193141Sdougb INSIST(Xrn->data[0] == NULL && 190193141Sdougb Xrn->data[1] == NULL); 191193141Sdougb } 192193141Sdougb 193193141Sdougb isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn)); 194193141Sdougb radix->num_active_node--; 195193141Sdougb 196193141Sdougb if (l != NULL) { 197193141Sdougb if (r != NULL) { 198193141Sdougb *Xsp++ = r; 199193141Sdougb } 200193141Sdougb Xrn = l; 201193141Sdougb } else if (r != NULL) { 202193141Sdougb Xrn = r; 203193141Sdougb } else if (Xsp != Xstack) { 204193141Sdougb Xrn = *(--Xsp); 205193141Sdougb } else { 206193141Sdougb Xrn = NULL; 207193141Sdougb } 208193141Sdougb } 209193141Sdougb } 210193141Sdougb RUNTIME_CHECK(radix->num_active_node == 0); 211193141Sdougb} 212193141Sdougb 213193141Sdougb 214193141Sdougbvoid 215254897Serwinisc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) { 216193141Sdougb REQUIRE(radix != NULL); 217193141Sdougb _clear_radix(radix, func); 218254897Serwin isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix)); 219193141Sdougb} 220193141Sdougb 221193141Sdougb 222193141Sdougb/* 223193141Sdougb * func will be called as func(node->prefix, node->data) 224193141Sdougb */ 225193141Sdougbvoid 226254897Serwinisc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) { 227193141Sdougb isc_radix_node_t *node; 228193141Sdougb 229193141Sdougb REQUIRE(func != NULL); 230193141Sdougb 231193141Sdougb RADIX_WALK(radix->head, node) { 232193141Sdougb func(node->prefix, node->data); 233193141Sdougb } RADIX_WALK_END; 234193141Sdougb} 235193141Sdougb 236193141Sdougb 237193141Sdougbisc_result_t 238193141Sdougbisc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, 239193141Sdougb isc_prefix_t *prefix) 240193141Sdougb{ 241193141Sdougb isc_radix_node_t *node; 242193141Sdougb isc_radix_node_t *stack[RADIX_MAXBITS + 1]; 243193141Sdougb u_char *addr; 244193141Sdougb isc_uint32_t bitlen; 245193141Sdougb int tfamily = -1; 246193141Sdougb int cnt = 0; 247193141Sdougb 248193141Sdougb REQUIRE(radix != NULL); 249193141Sdougb REQUIRE(prefix != NULL); 250193141Sdougb REQUIRE(target != NULL && *target == NULL); 251193141Sdougb RUNTIME_CHECK(prefix->bitlen <= radix->maxbits); 252193141Sdougb 253193141Sdougb *target = NULL; 254193141Sdougb 255193141Sdougb if (radix->head == NULL) { 256193141Sdougb return (ISC_R_NOTFOUND); 257193141Sdougb } 258193141Sdougb 259193141Sdougb node = radix->head; 260193141Sdougb addr = isc_prefix_touchar(prefix); 261193141Sdougb bitlen = prefix->bitlen; 262193141Sdougb 263193141Sdougb while (node->bit < bitlen) { 264193141Sdougb if (node->prefix) 265193141Sdougb stack[cnt++] = node; 266193141Sdougb 267193141Sdougb if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 268193141Sdougb node = node->r; 269193141Sdougb else 270193141Sdougb node = node->l; 271193141Sdougb 272193141Sdougb if (node == NULL) 273193141Sdougb break; 274193141Sdougb } 275193141Sdougb 276193141Sdougb if (node && node->prefix) 277193141Sdougb stack[cnt++] = node; 278193141Sdougb 279225361Sdougb while (cnt-- > 0) { 280193141Sdougb node = stack[cnt]; 281193141Sdougb 282193141Sdougb if (_comp_with_mask(isc_prefix_tochar(node->prefix), 283193141Sdougb isc_prefix_tochar(prefix), 284193141Sdougb node->prefix->bitlen)) { 285193141Sdougb if (node->node_num[ISC_IS6(prefix->family)] != -1 && 286193141Sdougb ((*target == NULL) || 287193141Sdougb (*target)->node_num[ISC_IS6(tfamily)] > 288193141Sdougb node->node_num[ISC_IS6(prefix->family)])) { 289193141Sdougb *target = node; 290193141Sdougb tfamily = prefix->family; 291193141Sdougb } 292193141Sdougb } 293193141Sdougb } 294193141Sdougb 295193141Sdougb if (*target == NULL) { 296193141Sdougb return (ISC_R_NOTFOUND); 297193141Sdougb } else { 298193141Sdougb return (ISC_R_SUCCESS); 299193141Sdougb } 300193141Sdougb} 301193141Sdougb 302193141Sdougbisc_result_t 303193141Sdougbisc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, 304193141Sdougb isc_radix_node_t *source, isc_prefix_t *prefix) 305193141Sdougb{ 306193141Sdougb isc_radix_node_t *node, *new_node, *parent, *glue = NULL; 307193141Sdougb u_char *addr, *test_addr; 308193141Sdougb isc_uint32_t bitlen, fam, check_bit, differ_bit; 309193141Sdougb isc_uint32_t i, j, r; 310193141Sdougb isc_result_t result; 311193141Sdougb 312193141Sdougb REQUIRE(radix != NULL); 313193141Sdougb REQUIRE(target != NULL && *target == NULL); 314193141Sdougb REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL)); 315193141Sdougb RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits); 316193141Sdougb 317193141Sdougb if (prefix == NULL) 318193141Sdougb prefix = source->prefix; 319193141Sdougb 320193141Sdougb INSIST(prefix != NULL); 321193141Sdougb 322193141Sdougb bitlen = prefix->bitlen; 323193141Sdougb fam = prefix->family; 324193141Sdougb 325193141Sdougb if (radix->head == NULL) { 326193141Sdougb node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 327193141Sdougb if (node == NULL) 328193141Sdougb return (ISC_R_NOMEMORY); 329193141Sdougb node->bit = bitlen; 330193141Sdougb node->node_num[0] = node->node_num[1] = -1; 331193141Sdougb node->prefix = NULL; 332193141Sdougb result = _ref_prefix(radix->mctx, &node->prefix, prefix); 333193141Sdougb if (result != ISC_R_SUCCESS) { 334193141Sdougb isc_mem_put(radix->mctx, node, 335193141Sdougb sizeof(isc_radix_node_t)); 336193141Sdougb return (result); 337193141Sdougb } 338193141Sdougb node->parent = NULL; 339193141Sdougb node->l = node->r = NULL; 340193141Sdougb if (source != NULL) { 341193141Sdougb /* 342193141Sdougb * If source is non-NULL, then we're merging in a 343193141Sdougb * node from an existing radix tree. To keep 344193141Sdougb * the node_num values consistent, the calling 345193141Sdougb * function will add the total number of nodes 346193141Sdougb * added to num_added_node at the end of 347193141Sdougb * the merge operation--we don't do it here. 348193141Sdougb */ 349193141Sdougb if (source->node_num[0] != -1) 350193141Sdougb node->node_num[0] = radix->num_added_node + 351193141Sdougb source->node_num[0]; 352193141Sdougb if (source->node_num[1] != -1) 353193141Sdougb node->node_num[1] = radix->num_added_node + 354193141Sdougb source->node_num[1]; 355193141Sdougb node->data[0] = source->data[0]; 356193141Sdougb node->data[1] = source->data[1]; 357193141Sdougb } else { 358193141Sdougb if (fam == AF_UNSPEC) { 359193141Sdougb /* "any" or "none" */ 360193141Sdougb node->node_num[0] = node->node_num[1] = 361193141Sdougb ++radix->num_added_node; 362193141Sdougb } else { 363193141Sdougb node->node_num[ISC_IS6(fam)] = 364193141Sdougb ++radix->num_added_node; 365193141Sdougb } 366193141Sdougb node->data[0] = NULL; 367193141Sdougb node->data[1] = NULL; 368193141Sdougb } 369193141Sdougb radix->head = node; 370193141Sdougb radix->num_active_node++; 371193141Sdougb *target = node; 372193141Sdougb return (ISC_R_SUCCESS); 373193141Sdougb } 374193141Sdougb 375193141Sdougb addr = isc_prefix_touchar(prefix); 376193141Sdougb node = radix->head; 377193141Sdougb 378193141Sdougb while (node->bit < bitlen || node->prefix == NULL) { 379193141Sdougb if (node->bit < radix->maxbits && 380193141Sdougb BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 381193141Sdougb { 382193141Sdougb if (node->r == NULL) 383193141Sdougb break; 384193141Sdougb node = node->r; 385193141Sdougb } else { 386193141Sdougb if (node->l == NULL) 387193141Sdougb break; 388193141Sdougb node = node->l; 389193141Sdougb } 390193141Sdougb 391193141Sdougb INSIST(node != NULL); 392193141Sdougb } 393193141Sdougb 394193141Sdougb INSIST(node->prefix != NULL); 395193141Sdougb 396193141Sdougb test_addr = isc_prefix_touchar(node->prefix); 397193141Sdougb /* Find the first bit different. */ 398193141Sdougb check_bit = (node->bit < bitlen) ? node->bit : bitlen; 399193141Sdougb differ_bit = 0; 400193141Sdougb for (i = 0; i*8 < check_bit; i++) { 401193141Sdougb if ((r = (addr[i] ^ test_addr[i])) == 0) { 402193141Sdougb differ_bit = (i + 1) * 8; 403193141Sdougb continue; 404193141Sdougb } 405193141Sdougb /* I know the better way, but for now. */ 406193141Sdougb for (j = 0; j < 8; j++) { 407193141Sdougb if (BIT_TEST (r, (0x80 >> j))) 408193141Sdougb break; 409193141Sdougb } 410193141Sdougb /* Must be found. */ 411193141Sdougb INSIST(j < 8); 412193141Sdougb differ_bit = i * 8 + j; 413193141Sdougb break; 414193141Sdougb } 415193141Sdougb 416193141Sdougb if (differ_bit > check_bit) 417193141Sdougb differ_bit = check_bit; 418193141Sdougb 419193141Sdougb parent = node->parent; 420193141Sdougb while (parent != NULL && parent->bit >= differ_bit) { 421193141Sdougb node = parent; 422193141Sdougb parent = node->parent; 423193141Sdougb } 424193141Sdougb 425193141Sdougb if (differ_bit == bitlen && node->bit == bitlen) { 426193141Sdougb if (node->prefix != NULL) { 427193141Sdougb /* Set node_num only if it hasn't been set before */ 428193141Sdougb if (source != NULL) { 429193141Sdougb /* Merging node */ 430193141Sdougb if (node->node_num[0] == -1 && 431193141Sdougb source->node_num[0] != -1) { 432193141Sdougb node->node_num[0] = 433193141Sdougb radix->num_added_node + 434193141Sdougb source->node_num[0]; 435193141Sdougb node->data[0] = source->data[0]; 436193141Sdougb } 437193141Sdougb if (node->node_num[1] == -1 && 438193141Sdougb source->node_num[0] != -1) { 439193141Sdougb node->node_num[1] = 440193141Sdougb radix->num_added_node + 441193141Sdougb source->node_num[1]; 442193141Sdougb node->data[1] = source->data[1]; 443193141Sdougb } 444193141Sdougb } else { 445193141Sdougb if (fam == AF_UNSPEC) { 446193141Sdougb /* "any" or "none" */ 447193141Sdougb int next = radix->num_added_node + 1; 448193141Sdougb if (node->node_num[0] == -1) { 449193141Sdougb node->node_num[0] = next; 450193141Sdougb radix->num_added_node = next; 451193141Sdougb } 452193141Sdougb if (node->node_num[1] == -1) { 453193141Sdougb node->node_num[1] = next; 454193141Sdougb radix->num_added_node = next; 455193141Sdougb } 456193141Sdougb } else { 457193141Sdougb if (node->node_num[ISC_IS6(fam)] == -1) 458193141Sdougb node->node_num[ISC_IS6(fam)] 459193141Sdougb = ++radix->num_added_node; 460193141Sdougb } 461193141Sdougb } 462193141Sdougb *target = node; 463193141Sdougb return (ISC_R_SUCCESS); 464193141Sdougb } else { 465254897Serwin result = _ref_prefix(radix->mctx, 466254897Serwin &node->prefix, prefix); 467193141Sdougb if (result != ISC_R_SUCCESS) 468193141Sdougb return (result); 469193141Sdougb } 470193141Sdougb INSIST(node->data[0] == NULL && node->node_num[0] == -1 && 471193141Sdougb node->data[1] == NULL && node->node_num[1] == -1); 472193141Sdougb if (source != NULL) { 473193141Sdougb /* Merging node */ 474193141Sdougb if (source->node_num[0] != -1) { 475193141Sdougb node->node_num[0] = radix->num_added_node + 476193141Sdougb source->node_num[0]; 477193141Sdougb node->data[0] = source->data[0]; 478193141Sdougb } 479193141Sdougb if (source->node_num[1] != -1) { 480193141Sdougb node->node_num[1] = radix->num_added_node + 481193141Sdougb source->node_num[1]; 482193141Sdougb node->data[1] = source->data[1]; 483193141Sdougb } 484193141Sdougb } else { 485193141Sdougb if (fam == AF_UNSPEC) { 486193141Sdougb /* "any" or "none" */ 487193141Sdougb node->node_num[0] = node->node_num[1] = 488193141Sdougb ++radix->num_added_node; 489193141Sdougb } else { 490193141Sdougb node->node_num[ISC_IS6(fam)] = 491193141Sdougb ++radix->num_added_node; 492193141Sdougb } 493193141Sdougb } 494193141Sdougb *target = node; 495193141Sdougb return (ISC_R_SUCCESS); 496193141Sdougb } 497193141Sdougb 498193141Sdougb new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 499193141Sdougb if (new_node == NULL) 500193141Sdougb return (ISC_R_NOMEMORY); 501193141Sdougb if (node->bit != differ_bit && bitlen != differ_bit) { 502193141Sdougb glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 503193141Sdougb if (glue == NULL) { 504193141Sdougb isc_mem_put(radix->mctx, new_node, 505193141Sdougb sizeof(isc_radix_node_t)); 506193141Sdougb return (ISC_R_NOMEMORY); 507193141Sdougb } 508193141Sdougb } 509193141Sdougb new_node->bit = bitlen; 510193141Sdougb new_node->prefix = NULL; 511193141Sdougb result = _ref_prefix(radix->mctx, &new_node->prefix, prefix); 512193141Sdougb if (result != ISC_R_SUCCESS) { 513193141Sdougb isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t)); 514193141Sdougb if (glue != NULL) 515193141Sdougb isc_mem_put(radix->mctx, glue, 516193141Sdougb sizeof(isc_radix_node_t)); 517193141Sdougb return (result); 518193141Sdougb } 519193141Sdougb new_node->parent = NULL; 520193141Sdougb new_node->l = new_node->r = NULL; 521193141Sdougb new_node->node_num[0] = new_node->node_num[1] = -1; 522193141Sdougb radix->num_active_node++; 523193141Sdougb 524193141Sdougb if (source != NULL) { 525193141Sdougb /* Merging node */ 526193141Sdougb if (source->node_num[0] != -1) 527193141Sdougb new_node->node_num[0] = radix->num_added_node + 528193141Sdougb source->node_num[0]; 529193141Sdougb if (source->node_num[1] != -1) 530193141Sdougb new_node->node_num[1] = radix->num_added_node + 531193141Sdougb source->node_num[1]; 532193141Sdougb new_node->data[0] = source->data[0]; 533193141Sdougb new_node->data[1] = source->data[1]; 534193141Sdougb } else { 535193141Sdougb if (fam == AF_UNSPEC) { 536193141Sdougb /* "any" or "none" */ 537193141Sdougb new_node->node_num[0] = new_node->node_num[1] = 538193141Sdougb ++radix->num_added_node; 539193141Sdougb } else { 540193141Sdougb new_node->node_num[ISC_IS6(fam)] = 541193141Sdougb ++radix->num_added_node; 542193141Sdougb } 543193141Sdougb new_node->data[0] = NULL; 544193141Sdougb new_node->data[1] = NULL; 545193141Sdougb } 546193141Sdougb 547193141Sdougb if (node->bit == differ_bit) { 548193141Sdougb INSIST(glue == NULL); 549193141Sdougb new_node->parent = node; 550193141Sdougb if (node->bit < radix->maxbits && 551193141Sdougb BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 552193141Sdougb { 553193141Sdougb INSIST(node->r == NULL); 554193141Sdougb node->r = new_node; 555193141Sdougb } else { 556193141Sdougb INSIST(node->l == NULL); 557193141Sdougb node->l = new_node; 558193141Sdougb } 559193141Sdougb *target = new_node; 560193141Sdougb return (ISC_R_SUCCESS); 561193141Sdougb } 562193141Sdougb 563193141Sdougb if (bitlen == differ_bit) { 564193141Sdougb INSIST(glue == NULL); 565193141Sdougb if (bitlen < radix->maxbits && 566193141Sdougb BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) { 567193141Sdougb new_node->r = node; 568193141Sdougb } else { 569193141Sdougb new_node->l = node; 570193141Sdougb } 571193141Sdougb new_node->parent = node->parent; 572193141Sdougb if (node->parent == NULL) { 573193141Sdougb INSIST(radix->head == node); 574193141Sdougb radix->head = new_node; 575193141Sdougb } else if (node->parent->r == node) { 576193141Sdougb node->parent->r = new_node; 577193141Sdougb } else { 578193141Sdougb node->parent->l = new_node; 579193141Sdougb } 580193141Sdougb node->parent = new_node; 581193141Sdougb } else { 582193141Sdougb INSIST(glue != NULL); 583193141Sdougb glue->bit = differ_bit; 584193141Sdougb glue->prefix = NULL; 585193141Sdougb glue->parent = node->parent; 586193141Sdougb glue->data[0] = glue->data[1] = NULL; 587193141Sdougb glue->node_num[0] = glue->node_num[1] = -1; 588193141Sdougb radix->num_active_node++; 589193141Sdougb if (differ_bit < radix->maxbits && 590193141Sdougb BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) { 591193141Sdougb glue->r = new_node; 592193141Sdougb glue->l = node; 593193141Sdougb } else { 594193141Sdougb glue->r = node; 595193141Sdougb glue->l = new_node; 596193141Sdougb } 597193141Sdougb new_node->parent = glue; 598193141Sdougb 599193141Sdougb if (node->parent == NULL) { 600193141Sdougb INSIST(radix->head == node); 601193141Sdougb radix->head = glue; 602193141Sdougb } else if (node->parent->r == node) { 603193141Sdougb node->parent->r = glue; 604193141Sdougb } else { 605193141Sdougb node->parent->l = glue; 606193141Sdougb } 607193141Sdougb node->parent = glue; 608193141Sdougb } 609193141Sdougb 610193141Sdougb *target = new_node; 611193141Sdougb return (ISC_R_SUCCESS); 612193141Sdougb} 613193141Sdougb 614193141Sdougbvoid 615193141Sdougbisc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) { 616193141Sdougb isc_radix_node_t *parent, *child; 617193141Sdougb 618193141Sdougb REQUIRE(radix != NULL); 619193141Sdougb REQUIRE(node != NULL); 620193141Sdougb 621193141Sdougb if (node->r && node->l) { 622193141Sdougb /* 623193141Sdougb * This might be a placeholder node -- have to check and 624193141Sdougb * make sure there is a prefix associated with it! 625193141Sdougb */ 626193141Sdougb if (node->prefix != NULL) 627254897Serwin _deref_prefix(node->prefix); 628193141Sdougb 629193141Sdougb node->prefix = NULL; 630193141Sdougb node->data[0] = node->data[1] = NULL; 631193141Sdougb return; 632193141Sdougb } 633193141Sdougb 634193141Sdougb if (node->r == NULL && node->l == NULL) { 635193141Sdougb parent = node->parent; 636254897Serwin _deref_prefix(node->prefix); 637193141Sdougb isc_mem_put(radix->mctx, node, sizeof(*node)); 638193141Sdougb radix->num_active_node--; 639193141Sdougb 640193141Sdougb if (parent == NULL) { 641193141Sdougb INSIST(radix->head == node); 642193141Sdougb radix->head = NULL; 643193141Sdougb return; 644193141Sdougb } 645193141Sdougb 646193141Sdougb if (parent->r == node) { 647193141Sdougb parent->r = NULL; 648193141Sdougb child = parent->l; 649193141Sdougb } else { 650193141Sdougb INSIST(parent->l == node); 651193141Sdougb parent->l = NULL; 652193141Sdougb child = parent->r; 653193141Sdougb } 654193141Sdougb 655193141Sdougb if (parent->prefix) 656193141Sdougb return; 657193141Sdougb 658193141Sdougb /* We need to remove parent too. */ 659193141Sdougb 660193141Sdougb if (parent->parent == NULL) { 661193141Sdougb INSIST(radix->head == parent); 662193141Sdougb radix->head = child; 663193141Sdougb } else if (parent->parent->r == parent) { 664193141Sdougb parent->parent->r = child; 665193141Sdougb } else { 666193141Sdougb INSIST(parent->parent->l == parent); 667193141Sdougb parent->parent->l = child; 668193141Sdougb } 669193141Sdougb child->parent = parent->parent; 670193141Sdougb isc_mem_put(radix->mctx, parent, sizeof(*parent)); 671193141Sdougb radix->num_active_node--; 672193141Sdougb return; 673193141Sdougb } 674193141Sdougb 675193141Sdougb if (node->r) { 676193141Sdougb child = node->r; 677193141Sdougb } else { 678193141Sdougb INSIST(node->l != NULL); 679193141Sdougb child = node->l; 680193141Sdougb } 681193141Sdougb parent = node->parent; 682193141Sdougb child->parent = parent; 683193141Sdougb 684254897Serwin _deref_prefix(node->prefix); 685193141Sdougb isc_mem_put(radix->mctx, node, sizeof(*node)); 686193141Sdougb radix->num_active_node--; 687193141Sdougb 688193141Sdougb if (parent == NULL) { 689193141Sdougb INSIST(radix->head == node); 690193141Sdougb radix->head = child; 691193141Sdougb return; 692193141Sdougb } 693193141Sdougb 694193141Sdougb if (parent->r == node) { 695193141Sdougb parent->r = child; 696193141Sdougb } else { 697193141Sdougb INSIST(parent->l == node); 698193141Sdougb parent->l = child; 699193141Sdougb } 700193141Sdougb} 701193141Sdougb 702193141Sdougb/* 703193141SdougbLocal Variables: 704193141Sdougbc-basic-offset: 4 705193141Sdougbindent-tabs-mode: t 706193141SdougbEnd: 707193141Sdougb*/ 708