1290001Sglebius/* 2290001Sglebius * Copyright (C) 2007-2009, 2011, 2012 Internet Systems Consortium, Inc. ("ISC") 3290001Sglebius * 4290001Sglebius * Permission to use, copy, modify, and/or distribute this software for any 5290001Sglebius * purpose with or without fee is hereby granted, provided that the above 6290001Sglebius * copyright notice and this permission notice appear in all copies. 7290001Sglebius * 8290001Sglebius * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9290001Sglebius * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10290001Sglebius * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11290001Sglebius * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12290001Sglebius * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13290001Sglebius * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14290001Sglebius * PERFORMANCE OF THIS SOFTWARE. 15290001Sglebius */ 16290001Sglebius 17290001Sglebius/* $Id$ */ 18290001Sglebius 19290001Sglebius/* 20290001Sglebius * This source was adapted from MRT's RCS Ids: 21290001Sglebius * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp 22290001Sglebius * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp 23290001Sglebius */ 24290001Sglebius 25290001Sglebius#include <config.h> 26290001Sglebius 27290001Sglebius#include <isc/mem.h> 28290001Sglebius#include <isc/types.h> 29290001Sglebius#include <isc/util.h> 30290001Sglebius#include <isc/radix.h> 31290001Sglebius 32290001Sglebiusstatic isc_result_t 33290001Sglebius_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, 34290001Sglebius void *dest, int bitlen); 35290001Sglebius 36290001Sglebiusstatic void 37290001Sglebius_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix); 38290001Sglebius 39290001Sglebiusstatic isc_result_t 40290001Sglebius_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix); 41290001Sglebius 42290001Sglebiusstatic int 43290001Sglebius_comp_with_mask(void *addr, void *dest, u_int mask); 44290001Sglebius 45290001Sglebiusstatic void 46290001Sglebius_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func); 47290001Sglebius 48290001Sglebiusstatic isc_result_t 49290001Sglebius_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest, 50290001Sglebius int bitlen) 51290001Sglebius{ 52290001Sglebius isc_prefix_t *prefix; 53290001Sglebius 54290001Sglebius REQUIRE(target != NULL); 55290001Sglebius 56290001Sglebius if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC) 57290001Sglebius return (ISC_R_NOTIMPLEMENTED); 58290001Sglebius 59290001Sglebius prefix = isc_mem_get(mctx, sizeof(isc_prefix_t)); 60290001Sglebius if (prefix == NULL) 61290001Sglebius return (ISC_R_NOMEMORY); 62290001Sglebius 63290001Sglebius if (family == AF_INET6) { 64290001Sglebius prefix->bitlen = (bitlen >= 0) ? bitlen : 128; 65290001Sglebius memcpy(&prefix->add.sin6, dest, 16); 66290001Sglebius } else { 67290001Sglebius /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */ 68290001Sglebius prefix->bitlen = (bitlen >= 0) ? bitlen : 32; 69290001Sglebius memcpy(&prefix->add.sin, dest, 4); 70290001Sglebius } 71290001Sglebius 72290001Sglebius prefix->family = family; 73290001Sglebius 74290001Sglebius isc_refcount_init(&prefix->refcount, 1); 75290001Sglebius 76290001Sglebius *target = prefix; 77290001Sglebius return (ISC_R_SUCCESS); 78290001Sglebius} 79290001Sglebius 80290001Sglebiusstatic void 81290001Sglebius_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix) { 82290001Sglebius int refs; 83290001Sglebius 84290001Sglebius if (prefix == NULL) 85290001Sglebius return; 86290001Sglebius 87290001Sglebius isc_refcount_decrement(&prefix->refcount, &refs); 88290001Sglebius 89290001Sglebius if (refs <= 0) { 90290001Sglebius isc_refcount_destroy(&prefix->refcount); 91290001Sglebius isc_mem_put(mctx, prefix, sizeof(isc_prefix_t)); 92290001Sglebius } 93290001Sglebius} 94290001Sglebius 95290001Sglebiusstatic isc_result_t 96290001Sglebius_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) { 97290001Sglebius INSIST(prefix != NULL); 98290001Sglebius INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) || 99290001Sglebius (prefix->family == AF_INET6 && prefix->bitlen <= 128) || 100290001Sglebius (prefix->family == AF_UNSPEC && prefix->bitlen == 0)); 101290001Sglebius REQUIRE(target != NULL && *target == NULL); 102290001Sglebius 103290001Sglebius /* 104290001Sglebius * If this prefix is a static allocation, copy it into new memory. 105290001Sglebius * (Note, the refcount still has to be destroyed by the calling 106290001Sglebius * routine.) 107290001Sglebius */ 108290001Sglebius if (isc_refcount_current(&prefix->refcount) == 0) { 109290001Sglebius isc_result_t ret; 110290001Sglebius ret = _new_prefix(mctx, target, prefix->family, 111290001Sglebius &prefix->add, prefix->bitlen); 112290001Sglebius return ret; 113290001Sglebius } 114290001Sglebius 115290001Sglebius isc_refcount_increment(&prefix->refcount, NULL); 116290001Sglebius 117290001Sglebius *target = prefix; 118290001Sglebius return (ISC_R_SUCCESS); 119290001Sglebius} 120290001Sglebius 121290001Sglebiusstatic int 122290001Sglebius_comp_with_mask(void *addr, void *dest, u_int mask) { 123290001Sglebius 124290001Sglebius /* Mask length of zero matches everything */ 125290001Sglebius if (mask == 0) 126290001Sglebius return (1); 127290001Sglebius 128290001Sglebius if (memcmp(addr, dest, mask / 8) == 0) { 129290001Sglebius int n = mask / 8; 130290001Sglebius int m = ((~0) << (8 - (mask % 8))); 131290001Sglebius 132290001Sglebius if ((mask % 8) == 0 || 133290001Sglebius (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m)) 134290001Sglebius return (1); 135290001Sglebius } 136290001Sglebius return (0); 137290001Sglebius} 138290001Sglebius 139290001Sglebiusisc_result_t 140290001Sglebiusisc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) { 141290001Sglebius isc_radix_tree_t *radix; 142290001Sglebius 143290001Sglebius REQUIRE(target != NULL && *target == NULL); 144290001Sglebius 145290001Sglebius radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t)); 146290001Sglebius if (radix == NULL) 147290001Sglebius return (ISC_R_NOMEMORY); 148290001Sglebius 149290001Sglebius radix->mctx = mctx; 150290001Sglebius radix->maxbits = maxbits; 151290001Sglebius radix->head = NULL; 152290001Sglebius radix->num_active_node = 0; 153290001Sglebius radix->num_added_node = 0; 154290001Sglebius RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */ 155290001Sglebius radix->magic = RADIX_TREE_MAGIC; 156290001Sglebius *target = radix; 157290001Sglebius return (ISC_R_SUCCESS); 158290001Sglebius} 159290001Sglebius 160290001Sglebius/* 161290001Sglebius * if func is supplied, it will be called as func(node->data) 162290001Sglebius * before deleting the node 163290001Sglebius */ 164290001Sglebius 165290001Sglebiusstatic void 166290001Sglebius_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) { 167290001Sglebius 168290001Sglebius REQUIRE(radix != NULL); 169290001Sglebius 170290001Sglebius if (radix->head != NULL) { 171290001Sglebius 172290001Sglebius isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; 173290001Sglebius isc_radix_node_t **Xsp = Xstack; 174290001Sglebius isc_radix_node_t *Xrn = radix->head; 175290001Sglebius 176290001Sglebius while (Xrn != NULL) { 177290001Sglebius isc_radix_node_t *l = Xrn->l; 178290001Sglebius isc_radix_node_t *r = Xrn->r; 179290001Sglebius 180290001Sglebius if (Xrn->prefix != NULL) { 181290001Sglebius _deref_prefix(radix->mctx, Xrn->prefix); 182290001Sglebius if (func != NULL && (Xrn->data[0] != NULL || 183290001Sglebius Xrn->data[1] != NULL)) 184290001Sglebius func(Xrn->data); 185290001Sglebius } else { 186290001Sglebius INSIST(Xrn->data[0] == NULL && 187290001Sglebius Xrn->data[1] == NULL); 188290001Sglebius } 189290001Sglebius 190290001Sglebius isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn)); 191290001Sglebius radix->num_active_node--; 192290001Sglebius 193290001Sglebius if (l != NULL) { 194290001Sglebius if (r != NULL) { 195290001Sglebius *Xsp++ = r; 196290001Sglebius } 197290001Sglebius Xrn = l; 198290001Sglebius } else if (r != NULL) { 199290001Sglebius Xrn = r; 200290001Sglebius } else if (Xsp != Xstack) { 201290001Sglebius Xrn = *(--Xsp); 202290001Sglebius } else { 203290001Sglebius Xrn = NULL; 204290001Sglebius } 205290001Sglebius } 206290001Sglebius } 207290001Sglebius RUNTIME_CHECK(radix->num_active_node == 0); 208290001Sglebius} 209290001Sglebius 210290001Sglebius 211290001Sglebiusvoid 212290001Sglebiusisc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) 213290001Sglebius{ 214290001Sglebius REQUIRE(radix != NULL); 215290001Sglebius _clear_radix(radix, func); 216290001Sglebius isc_mem_put(radix->mctx, radix, sizeof(*radix)); 217290001Sglebius} 218290001Sglebius 219290001Sglebius 220290001Sglebius/* 221290001Sglebius * func will be called as func(node->prefix, node->data) 222290001Sglebius */ 223290001Sglebiusvoid 224290001Sglebiusisc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) 225290001Sglebius{ 226290001Sglebius isc_radix_node_t *node; 227290001Sglebius 228290001Sglebius REQUIRE(func != NULL); 229290001Sglebius 230290001Sglebius RADIX_WALK(radix->head, node) { 231290001Sglebius func(node->prefix, node->data); 232290001Sglebius } RADIX_WALK_END; 233290001Sglebius} 234290001Sglebius 235290001Sglebius 236290001Sglebiusisc_result_t 237290001Sglebiusisc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, 238290001Sglebius isc_prefix_t *prefix) 239290001Sglebius{ 240290001Sglebius isc_radix_node_t *node; 241290001Sglebius isc_radix_node_t *stack[RADIX_MAXBITS + 1]; 242290001Sglebius u_char *addr; 243290001Sglebius isc_uint32_t bitlen; 244290001Sglebius int tfamily = -1; 245290001Sglebius int cnt = 0; 246290001Sglebius 247290001Sglebius REQUIRE(radix != NULL); 248290001Sglebius REQUIRE(prefix != NULL); 249290001Sglebius REQUIRE(target != NULL && *target == NULL); 250290001Sglebius RUNTIME_CHECK(prefix->bitlen <= radix->maxbits); 251290001Sglebius 252290001Sglebius *target = NULL; 253290001Sglebius 254290001Sglebius if (radix->head == NULL) { 255290001Sglebius return (ISC_R_NOTFOUND); 256290001Sglebius } 257290001Sglebius 258290001Sglebius node = radix->head; 259290001Sglebius addr = isc_prefix_touchar(prefix); 260290001Sglebius bitlen = prefix->bitlen; 261290001Sglebius 262290001Sglebius while (node->bit < bitlen) { 263290001Sglebius if (node->prefix) 264290001Sglebius stack[cnt++] = node; 265290001Sglebius 266290001Sglebius if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 267290001Sglebius node = node->r; 268290001Sglebius else 269290001Sglebius node = node->l; 270290001Sglebius 271290001Sglebius if (node == NULL) 272290001Sglebius break; 273290001Sglebius } 274290001Sglebius 275290001Sglebius if (node && node->prefix) 276290001Sglebius stack[cnt++] = node; 277290001Sglebius 278290001Sglebius while (cnt-- > 0) { 279290001Sglebius node = stack[cnt]; 280290001Sglebius 281290001Sglebius if (_comp_with_mask(isc_prefix_tochar(node->prefix), 282290001Sglebius isc_prefix_tochar(prefix), 283290001Sglebius node->prefix->bitlen)) { 284290001Sglebius if (node->node_num[ISC_IS6(prefix->family)] != -1 && 285290001Sglebius ((*target == NULL) || 286290001Sglebius (*target)->node_num[ISC_IS6(tfamily)] > 287290001Sglebius node->node_num[ISC_IS6(prefix->family)])) { 288290001Sglebius *target = node; 289290001Sglebius tfamily = prefix->family; 290290001Sglebius } 291290001Sglebius } 292290001Sglebius } 293290001Sglebius 294290001Sglebius if (*target == NULL) { 295290001Sglebius return (ISC_R_NOTFOUND); 296290001Sglebius } else { 297290001Sglebius return (ISC_R_SUCCESS); 298290001Sglebius } 299290001Sglebius} 300290001Sglebius 301290001Sglebiusisc_result_t 302290001Sglebiusisc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, 303290001Sglebius isc_radix_node_t *source, isc_prefix_t *prefix) 304290001Sglebius{ 305290001Sglebius isc_radix_node_t *node, *new_node, *parent, *glue = NULL; 306290001Sglebius u_char *addr, *test_addr; 307290001Sglebius isc_uint32_t bitlen, fam, check_bit, differ_bit; 308290001Sglebius isc_uint32_t i, j, r; 309290001Sglebius isc_result_t result; 310290001Sglebius 311290001Sglebius REQUIRE(radix != NULL); 312290001Sglebius REQUIRE(target != NULL && *target == NULL); 313290001Sglebius REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL)); 314290001Sglebius RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits); 315290001Sglebius 316290001Sglebius if (prefix == NULL) 317290001Sglebius prefix = source->prefix; 318290001Sglebius 319290001Sglebius INSIST(prefix != NULL); 320290001Sglebius 321290001Sglebius bitlen = prefix->bitlen; 322290001Sglebius fam = prefix->family; 323290001Sglebius 324290001Sglebius if (radix->head == NULL) { 325290001Sglebius node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 326290001Sglebius if (node == NULL) 327290001Sglebius return (ISC_R_NOMEMORY); 328290001Sglebius node->bit = bitlen; 329290001Sglebius node->node_num[0] = node->node_num[1] = -1; 330290001Sglebius node->prefix = NULL; 331290001Sglebius result = _ref_prefix(radix->mctx, &node->prefix, prefix); 332290001Sglebius if (result != ISC_R_SUCCESS) { 333290001Sglebius isc_mem_put(radix->mctx, node, 334290001Sglebius sizeof(isc_radix_node_t)); 335290001Sglebius return (result); 336290001Sglebius } 337290001Sglebius node->parent = NULL; 338290001Sglebius node->l = node->r = NULL; 339290001Sglebius if (source != NULL) { 340290001Sglebius /* 341290001Sglebius * If source is non-NULL, then we're merging in a 342290001Sglebius * node from an existing radix tree. To keep 343290001Sglebius * the node_num values consistent, the calling 344290001Sglebius * function will add the total number of nodes 345290001Sglebius * added to num_added_node at the end of 346290001Sglebius * the merge operation--we don't do it here. 347290001Sglebius */ 348290001Sglebius if (source->node_num[0] != -1) 349290001Sglebius node->node_num[0] = radix->num_added_node + 350290001Sglebius source->node_num[0]; 351290001Sglebius if (source->node_num[1] != -1) 352290001Sglebius node->node_num[1] = radix->num_added_node + 353290001Sglebius source->node_num[1]; 354290001Sglebius node->data[0] = source->data[0]; 355290001Sglebius node->data[1] = source->data[1]; 356290001Sglebius } else { 357290001Sglebius if (fam == AF_UNSPEC) { 358290001Sglebius /* "any" or "none" */ 359290001Sglebius node->node_num[0] = node->node_num[1] = 360290001Sglebius ++radix->num_added_node; 361290001Sglebius } else { 362290001Sglebius node->node_num[ISC_IS6(fam)] = 363290001Sglebius ++radix->num_added_node; 364290001Sglebius } 365290001Sglebius node->data[0] = NULL; 366290001Sglebius node->data[1] = NULL; 367290001Sglebius } 368290001Sglebius radix->head = node; 369290001Sglebius radix->num_active_node++; 370290001Sglebius *target = node; 371290001Sglebius return (ISC_R_SUCCESS); 372290001Sglebius } 373290001Sglebius 374290001Sglebius addr = isc_prefix_touchar(prefix); 375290001Sglebius node = radix->head; 376290001Sglebius 377290001Sglebius while (node->bit < bitlen || node->prefix == NULL) { 378290001Sglebius if (node->bit < radix->maxbits && 379290001Sglebius BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 380290001Sglebius { 381290001Sglebius if (node->r == NULL) 382290001Sglebius break; 383290001Sglebius node = node->r; 384290001Sglebius } else { 385290001Sglebius if (node->l == NULL) 386290001Sglebius break; 387290001Sglebius node = node->l; 388290001Sglebius } 389290001Sglebius 390290001Sglebius INSIST(node != NULL); 391290001Sglebius } 392290001Sglebius 393290001Sglebius INSIST(node->prefix != NULL); 394290001Sglebius 395290001Sglebius test_addr = isc_prefix_touchar(node->prefix); 396290001Sglebius /* Find the first bit different. */ 397290001Sglebius check_bit = (node->bit < bitlen) ? node->bit : bitlen; 398290001Sglebius differ_bit = 0; 399290001Sglebius for (i = 0; i*8 < check_bit; i++) { 400290001Sglebius if ((r = (addr[i] ^ test_addr[i])) == 0) { 401290001Sglebius differ_bit = (i + 1) * 8; 402290001Sglebius continue; 403290001Sglebius } 404290001Sglebius /* I know the better way, but for now. */ 405290001Sglebius for (j = 0; j < 8; j++) { 406290001Sglebius if (BIT_TEST (r, (0x80 >> j))) 407290001Sglebius break; 408290001Sglebius } 409290001Sglebius /* Must be found. */ 410290001Sglebius INSIST(j < 8); 411290001Sglebius differ_bit = i * 8 + j; 412290001Sglebius break; 413290001Sglebius } 414290001Sglebius 415290001Sglebius if (differ_bit > check_bit) 416290001Sglebius differ_bit = check_bit; 417290001Sglebius 418290001Sglebius parent = node->parent; 419290001Sglebius while (parent != NULL && parent->bit >= differ_bit) { 420290001Sglebius node = parent; 421290001Sglebius parent = node->parent; 422290001Sglebius } 423290001Sglebius 424290001Sglebius if (differ_bit == bitlen && node->bit == bitlen) { 425290001Sglebius if (node->prefix != NULL) { 426290001Sglebius /* Set node_num only if it hasn't been set before */ 427290001Sglebius if (source != NULL) { 428290001Sglebius /* Merging node */ 429290001Sglebius if (node->node_num[0] == -1 && 430290001Sglebius source->node_num[0] != -1) { 431290001Sglebius node->node_num[0] = 432290001Sglebius radix->num_added_node + 433290001Sglebius source->node_num[0]; 434290001Sglebius node->data[0] = source->data[0]; 435290001Sglebius } 436290001Sglebius if (node->node_num[1] == -1 && 437290001Sglebius source->node_num[0] != -1) { 438290001Sglebius node->node_num[1] = 439290001Sglebius radix->num_added_node + 440290001Sglebius source->node_num[1]; 441290001Sglebius node->data[1] = source->data[1]; 442290001Sglebius } 443290001Sglebius } else { 444290001Sglebius if (fam == AF_UNSPEC) { 445290001Sglebius /* "any" or "none" */ 446290001Sglebius int next = radix->num_added_node + 1; 447290001Sglebius if (node->node_num[0] == -1) { 448290001Sglebius node->node_num[0] = next; 449290001Sglebius radix->num_added_node = next; 450290001Sglebius } 451290001Sglebius if (node->node_num[1] == -1) { 452290001Sglebius node->node_num[1] = next; 453290001Sglebius radix->num_added_node = next; 454290001Sglebius } 455290001Sglebius } else { 456290001Sglebius if (node->node_num[ISC_IS6(fam)] == -1) 457290001Sglebius node->node_num[ISC_IS6(fam)] 458290001Sglebius = ++radix->num_added_node; 459290001Sglebius } 460290001Sglebius } 461290001Sglebius *target = node; 462290001Sglebius return (ISC_R_SUCCESS); 463290001Sglebius } else { 464290001Sglebius result = 465290001Sglebius _ref_prefix(radix->mctx, &node->prefix, prefix); 466290001Sglebius if (result != ISC_R_SUCCESS) 467290001Sglebius return (result); 468290001Sglebius } 469290001Sglebius INSIST(node->data[0] == NULL && node->node_num[0] == -1 && 470290001Sglebius node->data[1] == NULL && node->node_num[1] == -1); 471290001Sglebius if (source != NULL) { 472290001Sglebius /* Merging node */ 473290001Sglebius if (source->node_num[0] != -1) { 474290001Sglebius node->node_num[0] = radix->num_added_node + 475290001Sglebius source->node_num[0]; 476290001Sglebius node->data[0] = source->data[0]; 477290001Sglebius } 478290001Sglebius if (source->node_num[1] != -1) { 479290001Sglebius node->node_num[1] = radix->num_added_node + 480290001Sglebius source->node_num[1]; 481290001Sglebius node->data[1] = source->data[1]; 482290001Sglebius } 483290001Sglebius } else { 484290001Sglebius if (fam == AF_UNSPEC) { 485290001Sglebius /* "any" or "none" */ 486290001Sglebius node->node_num[0] = node->node_num[1] = 487290001Sglebius ++radix->num_added_node; 488290001Sglebius } else { 489290001Sglebius node->node_num[ISC_IS6(fam)] = 490290001Sglebius ++radix->num_added_node; 491290001Sglebius } 492290001Sglebius } 493290001Sglebius *target = node; 494290001Sglebius return (ISC_R_SUCCESS); 495290001Sglebius } 496290001Sglebius 497290001Sglebius new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 498290001Sglebius if (new_node == NULL) 499290001Sglebius return (ISC_R_NOMEMORY); 500290001Sglebius if (node->bit != differ_bit && bitlen != differ_bit) { 501290001Sglebius glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 502290001Sglebius if (glue == NULL) { 503290001Sglebius isc_mem_put(radix->mctx, new_node, 504290001Sglebius sizeof(isc_radix_node_t)); 505290001Sglebius return (ISC_R_NOMEMORY); 506290001Sglebius } 507290001Sglebius } 508290001Sglebius new_node->bit = bitlen; 509290001Sglebius new_node->prefix = NULL; 510290001Sglebius result = _ref_prefix(radix->mctx, &new_node->prefix, prefix); 511290001Sglebius if (result != ISC_R_SUCCESS) { 512290001Sglebius isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t)); 513290001Sglebius if (glue != NULL) 514290001Sglebius isc_mem_put(radix->mctx, glue, 515290001Sglebius sizeof(isc_radix_node_t)); 516290001Sglebius return (result); 517290001Sglebius } 518290001Sglebius new_node->parent = NULL; 519290001Sglebius new_node->l = new_node->r = NULL; 520290001Sglebius new_node->node_num[0] = new_node->node_num[1] = -1; 521290001Sglebius radix->num_active_node++; 522290001Sglebius 523290001Sglebius if (source != NULL) { 524290001Sglebius /* Merging node */ 525290001Sglebius if (source->node_num[0] != -1) 526290001Sglebius new_node->node_num[0] = radix->num_added_node + 527290001Sglebius source->node_num[0]; 528290001Sglebius if (source->node_num[1] != -1) 529290001Sglebius new_node->node_num[1] = radix->num_added_node + 530290001Sglebius source->node_num[1]; 531290001Sglebius new_node->data[0] = source->data[0]; 532290001Sglebius new_node->data[1] = source->data[1]; 533290001Sglebius } else { 534290001Sglebius if (fam == AF_UNSPEC) { 535290001Sglebius /* "any" or "none" */ 536290001Sglebius new_node->node_num[0] = new_node->node_num[1] = 537290001Sglebius ++radix->num_added_node; 538290001Sglebius } else { 539290001Sglebius new_node->node_num[ISC_IS6(fam)] = 540290001Sglebius ++radix->num_added_node; 541290001Sglebius } 542290001Sglebius new_node->data[0] = NULL; 543290001Sglebius new_node->data[1] = NULL; 544290001Sglebius } 545290001Sglebius 546290001Sglebius if (node->bit == differ_bit) { 547290001Sglebius INSIST(glue == NULL); 548290001Sglebius new_node->parent = node; 549290001Sglebius if (node->bit < radix->maxbits && 550290001Sglebius BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 551290001Sglebius { 552290001Sglebius INSIST(node->r == NULL); 553290001Sglebius node->r = new_node; 554290001Sglebius } else { 555290001Sglebius INSIST(node->l == NULL); 556290001Sglebius node->l = new_node; 557290001Sglebius } 558290001Sglebius *target = new_node; 559290001Sglebius return (ISC_R_SUCCESS); 560290001Sglebius } 561290001Sglebius 562290001Sglebius if (bitlen == differ_bit) { 563290001Sglebius INSIST(glue == NULL); 564290001Sglebius if (bitlen < radix->maxbits && 565290001Sglebius BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) { 566290001Sglebius new_node->r = node; 567290001Sglebius } else { 568290001Sglebius new_node->l = node; 569290001Sglebius } 570290001Sglebius new_node->parent = node->parent; 571290001Sglebius if (node->parent == NULL) { 572290001Sglebius INSIST(radix->head == node); 573290001Sglebius radix->head = new_node; 574290001Sglebius } else if (node->parent->r == node) { 575290001Sglebius node->parent->r = new_node; 576290001Sglebius } else { 577290001Sglebius node->parent->l = new_node; 578290001Sglebius } 579290001Sglebius node->parent = new_node; 580290001Sglebius } else { 581290001Sglebius INSIST(glue != NULL); 582290001Sglebius glue->bit = differ_bit; 583290001Sglebius glue->prefix = NULL; 584290001Sglebius glue->parent = node->parent; 585290001Sglebius glue->data[0] = glue->data[1] = NULL; 586290001Sglebius glue->node_num[0] = glue->node_num[1] = -1; 587290001Sglebius radix->num_active_node++; 588290001Sglebius if (differ_bit < radix->maxbits && 589290001Sglebius BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) { 590290001Sglebius glue->r = new_node; 591290001Sglebius glue->l = node; 592290001Sglebius } else { 593290001Sglebius glue->r = node; 594290001Sglebius glue->l = new_node; 595290001Sglebius } 596290001Sglebius new_node->parent = glue; 597290001Sglebius 598290001Sglebius if (node->parent == NULL) { 599290001Sglebius INSIST(radix->head == node); 600290001Sglebius radix->head = glue; 601290001Sglebius } else if (node->parent->r == node) { 602290001Sglebius node->parent->r = glue; 603290001Sglebius } else { 604290001Sglebius node->parent->l = glue; 605290001Sglebius } 606290001Sglebius node->parent = glue; 607290001Sglebius } 608290001Sglebius 609290001Sglebius *target = new_node; 610290001Sglebius return (ISC_R_SUCCESS); 611290001Sglebius} 612290001Sglebius 613290001Sglebiusvoid 614290001Sglebiusisc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) { 615290001Sglebius isc_radix_node_t *parent, *child; 616290001Sglebius 617290001Sglebius REQUIRE(radix != NULL); 618290001Sglebius REQUIRE(node != NULL); 619290001Sglebius 620290001Sglebius if (node->r && node->l) { 621290001Sglebius /* 622290001Sglebius * This might be a placeholder node -- have to check and 623290001Sglebius * make sure there is a prefix associated with it! 624290001Sglebius */ 625290001Sglebius if (node->prefix != NULL) 626290001Sglebius _deref_prefix(radix->mctx, node->prefix); 627290001Sglebius 628290001Sglebius node->prefix = NULL; 629290001Sglebius node->data[0] = node->data[1] = NULL; 630290001Sglebius return; 631290001Sglebius } 632290001Sglebius 633290001Sglebius if (node->r == NULL && node->l == NULL) { 634290001Sglebius parent = node->parent; 635290001Sglebius _deref_prefix(radix->mctx, node->prefix); 636290001Sglebius isc_mem_put(radix->mctx, node, sizeof(*node)); 637290001Sglebius radix->num_active_node--; 638290001Sglebius 639290001Sglebius if (parent == NULL) { 640290001Sglebius INSIST(radix->head == node); 641290001Sglebius radix->head = NULL; 642290001Sglebius return; 643290001Sglebius } 644290001Sglebius 645290001Sglebius if (parent->r == node) { 646290001Sglebius parent->r = NULL; 647290001Sglebius child = parent->l; 648290001Sglebius } else { 649290001Sglebius INSIST(parent->l == node); 650290001Sglebius parent->l = NULL; 651290001Sglebius child = parent->r; 652290001Sglebius } 653290001Sglebius 654290001Sglebius if (parent->prefix) 655290001Sglebius return; 656290001Sglebius 657290001Sglebius /* We need to remove parent too. */ 658290001Sglebius 659290001Sglebius if (parent->parent == NULL) { 660290001Sglebius INSIST(radix->head == parent); 661290001Sglebius radix->head = child; 662290001Sglebius } else if (parent->parent->r == parent) { 663290001Sglebius parent->parent->r = child; 664290001Sglebius } else { 665290001Sglebius INSIST(parent->parent->l == parent); 666290001Sglebius parent->parent->l = child; 667290001Sglebius } 668290001Sglebius child->parent = parent->parent; 669290001Sglebius isc_mem_put(radix->mctx, parent, sizeof(*parent)); 670290001Sglebius radix->num_active_node--; 671290001Sglebius return; 672290001Sglebius } 673290001Sglebius 674290001Sglebius if (node->r) { 675290001Sglebius child = node->r; 676290001Sglebius } else { 677290001Sglebius INSIST(node->l != NULL); 678290001Sglebius child = node->l; 679290001Sglebius } 680290001Sglebius parent = node->parent; 681290001Sglebius child->parent = parent; 682290001Sglebius 683290001Sglebius _deref_prefix(radix->mctx, node->prefix); 684290001Sglebius isc_mem_put(radix->mctx, node, sizeof(*node)); 685290001Sglebius radix->num_active_node--; 686290001Sglebius 687290001Sglebius if (parent == NULL) { 688290001Sglebius INSIST(radix->head == node); 689290001Sglebius radix->head = child; 690290001Sglebius return; 691290001Sglebius } 692290001Sglebius 693290001Sglebius if (parent->r == node) { 694290001Sglebius parent->r = child; 695290001Sglebius } else { 696290001Sglebius INSIST(parent->l == node); 697290001Sglebius parent->l = child; 698290001Sglebius } 699290001Sglebius} 700290001Sglebius 701290001Sglebius/* 702290001SglebiusLocal Variables: 703290001Sglebiusc-basic-offset: 4 704290001Sglebiusindent-tabs-mode: t 705290001SglebiusEnd: 706290001Sglebius*/ 707