1258945Sroberto/* 2280849Scy * Copyright (C) 2007-2009, 2011, 2012 Internet Systems Consortium, Inc. ("ISC") 3258945Sroberto * 4258945Sroberto * Permission to use, copy, modify, and/or distribute this software for any 5258945Sroberto * purpose with or without fee is hereby granted, provided that the above 6258945Sroberto * copyright notice and this permission notice appear in all copies. 7258945Sroberto * 8258945Sroberto * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9258945Sroberto * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10258945Sroberto * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11258945Sroberto * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12258945Sroberto * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13258945Sroberto * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14258945Sroberto * PERFORMANCE OF THIS SOFTWARE. 15258945Sroberto */ 16258945Sroberto 17280849Scy/* $Id$ */ 18258945Sroberto 19258945Sroberto/* 20258945Sroberto * This source was adapted from MRT's RCS Ids: 21258945Sroberto * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp 22258945Sroberto * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp 23258945Sroberto */ 24258945Sroberto 25258945Sroberto#include <config.h> 26258945Sroberto 27258945Sroberto#include <isc/mem.h> 28258945Sroberto#include <isc/types.h> 29258945Sroberto#include <isc/util.h> 30258945Sroberto#include <isc/radix.h> 31258945Sroberto 32258945Srobertostatic isc_result_t 33258945Sroberto_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, 34258945Sroberto void *dest, int bitlen); 35258945Sroberto 36258945Srobertostatic void 37258945Sroberto_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix); 38258945Sroberto 39258945Srobertostatic isc_result_t 40258945Sroberto_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix); 41258945Sroberto 42258945Srobertostatic int 43258945Sroberto_comp_with_mask(void *addr, void *dest, u_int mask); 44258945Sroberto 45258945Srobertostatic void 46258945Sroberto_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func); 47258945Sroberto 48258945Srobertostatic isc_result_t 49258945Sroberto_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest, 50258945Sroberto int bitlen) 51258945Sroberto{ 52258945Sroberto isc_prefix_t *prefix; 53258945Sroberto 54258945Sroberto REQUIRE(target != NULL); 55258945Sroberto 56258945Sroberto if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC) 57258945Sroberto return (ISC_R_NOTIMPLEMENTED); 58258945Sroberto 59258945Sroberto prefix = isc_mem_get(mctx, sizeof(isc_prefix_t)); 60258945Sroberto if (prefix == NULL) 61258945Sroberto return (ISC_R_NOMEMORY); 62258945Sroberto 63258945Sroberto if (family == AF_INET6) { 64258945Sroberto prefix->bitlen = (bitlen >= 0) ? bitlen : 128; 65258945Sroberto memcpy(&prefix->add.sin6, dest, 16); 66258945Sroberto } else { 67258945Sroberto /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */ 68258945Sroberto prefix->bitlen = (bitlen >= 0) ? bitlen : 32; 69258945Sroberto memcpy(&prefix->add.sin, dest, 4); 70258945Sroberto } 71258945Sroberto 72258945Sroberto prefix->family = family; 73258945Sroberto 74258945Sroberto isc_refcount_init(&prefix->refcount, 1); 75258945Sroberto 76258945Sroberto *target = prefix; 77258945Sroberto return (ISC_R_SUCCESS); 78258945Sroberto} 79258945Sroberto 80258945Srobertostatic void 81258945Sroberto_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix) { 82258945Sroberto int refs; 83258945Sroberto 84258945Sroberto if (prefix == NULL) 85258945Sroberto return; 86258945Sroberto 87258945Sroberto isc_refcount_decrement(&prefix->refcount, &refs); 88258945Sroberto 89258945Sroberto if (refs <= 0) { 90258945Sroberto isc_refcount_destroy(&prefix->refcount); 91258945Sroberto isc_mem_put(mctx, prefix, sizeof(isc_prefix_t)); 92258945Sroberto } 93258945Sroberto} 94258945Sroberto 95258945Srobertostatic isc_result_t 96258945Sroberto_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) { 97258945Sroberto INSIST(prefix != NULL); 98258945Sroberto INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) || 99258945Sroberto (prefix->family == AF_INET6 && prefix->bitlen <= 128) || 100258945Sroberto (prefix->family == AF_UNSPEC && prefix->bitlen == 0)); 101258945Sroberto REQUIRE(target != NULL && *target == NULL); 102258945Sroberto 103258945Sroberto /* 104258945Sroberto * If this prefix is a static allocation, copy it into new memory. 105258945Sroberto * (Note, the refcount still has to be destroyed by the calling 106258945Sroberto * routine.) 107258945Sroberto */ 108258945Sroberto if (isc_refcount_current(&prefix->refcount) == 0) { 109258945Sroberto isc_result_t ret; 110258945Sroberto ret = _new_prefix(mctx, target, prefix->family, 111258945Sroberto &prefix->add, prefix->bitlen); 112258945Sroberto return ret; 113258945Sroberto } 114258945Sroberto 115258945Sroberto isc_refcount_increment(&prefix->refcount, NULL); 116258945Sroberto 117258945Sroberto *target = prefix; 118258945Sroberto return (ISC_R_SUCCESS); 119258945Sroberto} 120258945Sroberto 121258945Srobertostatic int 122258945Sroberto_comp_with_mask(void *addr, void *dest, u_int mask) { 123258945Sroberto 124258945Sroberto /* Mask length of zero matches everything */ 125258945Sroberto if (mask == 0) 126258945Sroberto return (1); 127258945Sroberto 128258945Sroberto if (memcmp(addr, dest, mask / 8) == 0) { 129258945Sroberto int n = mask / 8; 130258945Sroberto int m = ((~0) << (8 - (mask % 8))); 131258945Sroberto 132258945Sroberto if ((mask % 8) == 0 || 133258945Sroberto (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m)) 134258945Sroberto return (1); 135258945Sroberto } 136258945Sroberto return (0); 137258945Sroberto} 138258945Sroberto 139258945Srobertoisc_result_t 140258945Srobertoisc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) { 141258945Sroberto isc_radix_tree_t *radix; 142258945Sroberto 143258945Sroberto REQUIRE(target != NULL && *target == NULL); 144258945Sroberto 145258945Sroberto radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t)); 146258945Sroberto if (radix == NULL) 147258945Sroberto return (ISC_R_NOMEMORY); 148258945Sroberto 149258945Sroberto radix->mctx = mctx; 150258945Sroberto radix->maxbits = maxbits; 151258945Sroberto radix->head = NULL; 152258945Sroberto radix->num_active_node = 0; 153258945Sroberto radix->num_added_node = 0; 154258945Sroberto RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */ 155258945Sroberto radix->magic = RADIX_TREE_MAGIC; 156258945Sroberto *target = radix; 157258945Sroberto return (ISC_R_SUCCESS); 158258945Sroberto} 159258945Sroberto 160258945Sroberto/* 161258945Sroberto * if func is supplied, it will be called as func(node->data) 162258945Sroberto * before deleting the node 163258945Sroberto */ 164258945Sroberto 165258945Srobertostatic void 166258945Sroberto_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) { 167258945Sroberto 168258945Sroberto REQUIRE(radix != NULL); 169258945Sroberto 170258945Sroberto if (radix->head != NULL) { 171258945Sroberto 172258945Sroberto isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; 173258945Sroberto isc_radix_node_t **Xsp = Xstack; 174258945Sroberto isc_radix_node_t *Xrn = radix->head; 175258945Sroberto 176258945Sroberto while (Xrn != NULL) { 177258945Sroberto isc_radix_node_t *l = Xrn->l; 178258945Sroberto isc_radix_node_t *r = Xrn->r; 179258945Sroberto 180258945Sroberto if (Xrn->prefix != NULL) { 181258945Sroberto _deref_prefix(radix->mctx, Xrn->prefix); 182258945Sroberto if (func != NULL && (Xrn->data[0] != NULL || 183258945Sroberto Xrn->data[1] != NULL)) 184258945Sroberto func(Xrn->data); 185258945Sroberto } else { 186258945Sroberto INSIST(Xrn->data[0] == NULL && 187258945Sroberto Xrn->data[1] == NULL); 188258945Sroberto } 189258945Sroberto 190258945Sroberto isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn)); 191258945Sroberto radix->num_active_node--; 192258945Sroberto 193258945Sroberto if (l != NULL) { 194258945Sroberto if (r != NULL) { 195258945Sroberto *Xsp++ = r; 196258945Sroberto } 197258945Sroberto Xrn = l; 198258945Sroberto } else if (r != NULL) { 199258945Sroberto Xrn = r; 200258945Sroberto } else if (Xsp != Xstack) { 201258945Sroberto Xrn = *(--Xsp); 202258945Sroberto } else { 203258945Sroberto Xrn = NULL; 204258945Sroberto } 205258945Sroberto } 206258945Sroberto } 207258945Sroberto RUNTIME_CHECK(radix->num_active_node == 0); 208258945Sroberto} 209258945Sroberto 210258945Sroberto 211258945Srobertovoid 212258945Srobertoisc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) 213258945Sroberto{ 214258945Sroberto REQUIRE(radix != NULL); 215258945Sroberto _clear_radix(radix, func); 216258945Sroberto isc_mem_put(radix->mctx, radix, sizeof(*radix)); 217258945Sroberto} 218258945Sroberto 219258945Sroberto 220258945Sroberto/* 221258945Sroberto * func will be called as func(node->prefix, node->data) 222258945Sroberto */ 223258945Srobertovoid 224258945Srobertoisc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) 225258945Sroberto{ 226258945Sroberto isc_radix_node_t *node; 227258945Sroberto 228258945Sroberto REQUIRE(func != NULL); 229258945Sroberto 230258945Sroberto RADIX_WALK(radix->head, node) { 231258945Sroberto func(node->prefix, node->data); 232258945Sroberto } RADIX_WALK_END; 233258945Sroberto} 234258945Sroberto 235258945Sroberto 236258945Srobertoisc_result_t 237258945Srobertoisc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, 238258945Sroberto isc_prefix_t *prefix) 239258945Sroberto{ 240258945Sroberto isc_radix_node_t *node; 241258945Sroberto isc_radix_node_t *stack[RADIX_MAXBITS + 1]; 242258945Sroberto u_char *addr; 243258945Sroberto isc_uint32_t bitlen; 244258945Sroberto int tfamily = -1; 245258945Sroberto int cnt = 0; 246258945Sroberto 247258945Sroberto REQUIRE(radix != NULL); 248258945Sroberto REQUIRE(prefix != NULL); 249258945Sroberto REQUIRE(target != NULL && *target == NULL); 250258945Sroberto RUNTIME_CHECK(prefix->bitlen <= radix->maxbits); 251258945Sroberto 252258945Sroberto *target = NULL; 253258945Sroberto 254258945Sroberto if (radix->head == NULL) { 255258945Sroberto return (ISC_R_NOTFOUND); 256258945Sroberto } 257258945Sroberto 258258945Sroberto node = radix->head; 259258945Sroberto addr = isc_prefix_touchar(prefix); 260258945Sroberto bitlen = prefix->bitlen; 261258945Sroberto 262258945Sroberto while (node->bit < bitlen) { 263258945Sroberto if (node->prefix) 264258945Sroberto stack[cnt++] = node; 265258945Sroberto 266258945Sroberto if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 267258945Sroberto node = node->r; 268258945Sroberto else 269258945Sroberto node = node->l; 270258945Sroberto 271258945Sroberto if (node == NULL) 272258945Sroberto break; 273258945Sroberto } 274258945Sroberto 275258945Sroberto if (node && node->prefix) 276258945Sroberto stack[cnt++] = node; 277258945Sroberto 278280849Scy while (cnt-- > 0) { 279258945Sroberto node = stack[cnt]; 280258945Sroberto 281258945Sroberto if (_comp_with_mask(isc_prefix_tochar(node->prefix), 282258945Sroberto isc_prefix_tochar(prefix), 283258945Sroberto node->prefix->bitlen)) { 284258945Sroberto if (node->node_num[ISC_IS6(prefix->family)] != -1 && 285258945Sroberto ((*target == NULL) || 286258945Sroberto (*target)->node_num[ISC_IS6(tfamily)] > 287258945Sroberto node->node_num[ISC_IS6(prefix->family)])) { 288258945Sroberto *target = node; 289258945Sroberto tfamily = prefix->family; 290258945Sroberto } 291258945Sroberto } 292258945Sroberto } 293258945Sroberto 294258945Sroberto if (*target == NULL) { 295258945Sroberto return (ISC_R_NOTFOUND); 296258945Sroberto } else { 297258945Sroberto return (ISC_R_SUCCESS); 298258945Sroberto } 299258945Sroberto} 300258945Sroberto 301258945Srobertoisc_result_t 302258945Srobertoisc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, 303258945Sroberto isc_radix_node_t *source, isc_prefix_t *prefix) 304258945Sroberto{ 305258945Sroberto isc_radix_node_t *node, *new_node, *parent, *glue = NULL; 306258945Sroberto u_char *addr, *test_addr; 307258945Sroberto isc_uint32_t bitlen, fam, check_bit, differ_bit; 308258945Sroberto isc_uint32_t i, j, r; 309258945Sroberto isc_result_t result; 310258945Sroberto 311258945Sroberto REQUIRE(radix != NULL); 312258945Sroberto REQUIRE(target != NULL && *target == NULL); 313258945Sroberto REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL)); 314258945Sroberto RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits); 315258945Sroberto 316258945Sroberto if (prefix == NULL) 317258945Sroberto prefix = source->prefix; 318258945Sroberto 319258945Sroberto INSIST(prefix != NULL); 320258945Sroberto 321258945Sroberto bitlen = prefix->bitlen; 322258945Sroberto fam = prefix->family; 323258945Sroberto 324258945Sroberto if (radix->head == NULL) { 325258945Sroberto node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 326258945Sroberto if (node == NULL) 327258945Sroberto return (ISC_R_NOMEMORY); 328258945Sroberto node->bit = bitlen; 329258945Sroberto node->node_num[0] = node->node_num[1] = -1; 330258945Sroberto node->prefix = NULL; 331258945Sroberto result = _ref_prefix(radix->mctx, &node->prefix, prefix); 332258945Sroberto if (result != ISC_R_SUCCESS) { 333258945Sroberto isc_mem_put(radix->mctx, node, 334258945Sroberto sizeof(isc_radix_node_t)); 335258945Sroberto return (result); 336258945Sroberto } 337258945Sroberto node->parent = NULL; 338258945Sroberto node->l = node->r = NULL; 339258945Sroberto if (source != NULL) { 340258945Sroberto /* 341258945Sroberto * If source is non-NULL, then we're merging in a 342258945Sroberto * node from an existing radix tree. To keep 343258945Sroberto * the node_num values consistent, the calling 344258945Sroberto * function will add the total number of nodes 345258945Sroberto * added to num_added_node at the end of 346258945Sroberto * the merge operation--we don't do it here. 347258945Sroberto */ 348258945Sroberto if (source->node_num[0] != -1) 349258945Sroberto node->node_num[0] = radix->num_added_node + 350258945Sroberto source->node_num[0]; 351258945Sroberto if (source->node_num[1] != -1) 352258945Sroberto node->node_num[1] = radix->num_added_node + 353258945Sroberto source->node_num[1]; 354258945Sroberto node->data[0] = source->data[0]; 355258945Sroberto node->data[1] = source->data[1]; 356258945Sroberto } else { 357258945Sroberto if (fam == AF_UNSPEC) { 358258945Sroberto /* "any" or "none" */ 359258945Sroberto node->node_num[0] = node->node_num[1] = 360258945Sroberto ++radix->num_added_node; 361258945Sroberto } else { 362258945Sroberto node->node_num[ISC_IS6(fam)] = 363258945Sroberto ++radix->num_added_node; 364258945Sroberto } 365258945Sroberto node->data[0] = NULL; 366258945Sroberto node->data[1] = NULL; 367258945Sroberto } 368258945Sroberto radix->head = node; 369258945Sroberto radix->num_active_node++; 370258945Sroberto *target = node; 371258945Sroberto return (ISC_R_SUCCESS); 372258945Sroberto } 373258945Sroberto 374258945Sroberto addr = isc_prefix_touchar(prefix); 375258945Sroberto node = radix->head; 376258945Sroberto 377258945Sroberto while (node->bit < bitlen || node->prefix == NULL) { 378258945Sroberto if (node->bit < radix->maxbits && 379258945Sroberto BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 380258945Sroberto { 381258945Sroberto if (node->r == NULL) 382258945Sroberto break; 383258945Sroberto node = node->r; 384258945Sroberto } else { 385258945Sroberto if (node->l == NULL) 386258945Sroberto break; 387258945Sroberto node = node->l; 388258945Sroberto } 389258945Sroberto 390258945Sroberto INSIST(node != NULL); 391258945Sroberto } 392258945Sroberto 393258945Sroberto INSIST(node->prefix != NULL); 394258945Sroberto 395258945Sroberto test_addr = isc_prefix_touchar(node->prefix); 396258945Sroberto /* Find the first bit different. */ 397258945Sroberto check_bit = (node->bit < bitlen) ? node->bit : bitlen; 398258945Sroberto differ_bit = 0; 399258945Sroberto for (i = 0; i*8 < check_bit; i++) { 400258945Sroberto if ((r = (addr[i] ^ test_addr[i])) == 0) { 401258945Sroberto differ_bit = (i + 1) * 8; 402258945Sroberto continue; 403258945Sroberto } 404258945Sroberto /* I know the better way, but for now. */ 405258945Sroberto for (j = 0; j < 8; j++) { 406258945Sroberto if (BIT_TEST (r, (0x80 >> j))) 407258945Sroberto break; 408258945Sroberto } 409258945Sroberto /* Must be found. */ 410258945Sroberto INSIST(j < 8); 411258945Sroberto differ_bit = i * 8 + j; 412258945Sroberto break; 413258945Sroberto } 414258945Sroberto 415258945Sroberto if (differ_bit > check_bit) 416258945Sroberto differ_bit = check_bit; 417258945Sroberto 418258945Sroberto parent = node->parent; 419258945Sroberto while (parent != NULL && parent->bit >= differ_bit) { 420258945Sroberto node = parent; 421258945Sroberto parent = node->parent; 422258945Sroberto } 423258945Sroberto 424258945Sroberto if (differ_bit == bitlen && node->bit == bitlen) { 425258945Sroberto if (node->prefix != NULL) { 426258945Sroberto /* Set node_num only if it hasn't been set before */ 427258945Sroberto if (source != NULL) { 428258945Sroberto /* Merging node */ 429258945Sroberto if (node->node_num[0] == -1 && 430258945Sroberto source->node_num[0] != -1) { 431258945Sroberto node->node_num[0] = 432258945Sroberto radix->num_added_node + 433258945Sroberto source->node_num[0]; 434258945Sroberto node->data[0] = source->data[0]; 435258945Sroberto } 436258945Sroberto if (node->node_num[1] == -1 && 437258945Sroberto source->node_num[0] != -1) { 438258945Sroberto node->node_num[1] = 439258945Sroberto radix->num_added_node + 440258945Sroberto source->node_num[1]; 441258945Sroberto node->data[1] = source->data[1]; 442258945Sroberto } 443258945Sroberto } else { 444258945Sroberto if (fam == AF_UNSPEC) { 445258945Sroberto /* "any" or "none" */ 446258945Sroberto int next = radix->num_added_node + 1; 447258945Sroberto if (node->node_num[0] == -1) { 448258945Sroberto node->node_num[0] = next; 449258945Sroberto radix->num_added_node = next; 450258945Sroberto } 451258945Sroberto if (node->node_num[1] == -1) { 452258945Sroberto node->node_num[1] = next; 453258945Sroberto radix->num_added_node = next; 454258945Sroberto } 455258945Sroberto } else { 456258945Sroberto if (node->node_num[ISC_IS6(fam)] == -1) 457258945Sroberto node->node_num[ISC_IS6(fam)] 458258945Sroberto = ++radix->num_added_node; 459258945Sroberto } 460258945Sroberto } 461258945Sroberto *target = node; 462258945Sroberto return (ISC_R_SUCCESS); 463258945Sroberto } else { 464258945Sroberto result = 465258945Sroberto _ref_prefix(radix->mctx, &node->prefix, prefix); 466258945Sroberto if (result != ISC_R_SUCCESS) 467258945Sroberto return (result); 468258945Sroberto } 469258945Sroberto INSIST(node->data[0] == NULL && node->node_num[0] == -1 && 470258945Sroberto node->data[1] == NULL && node->node_num[1] == -1); 471258945Sroberto if (source != NULL) { 472258945Sroberto /* Merging node */ 473258945Sroberto if (source->node_num[0] != -1) { 474258945Sroberto node->node_num[0] = radix->num_added_node + 475258945Sroberto source->node_num[0]; 476258945Sroberto node->data[0] = source->data[0]; 477258945Sroberto } 478258945Sroberto if (source->node_num[1] != -1) { 479258945Sroberto node->node_num[1] = radix->num_added_node + 480258945Sroberto source->node_num[1]; 481258945Sroberto node->data[1] = source->data[1]; 482258945Sroberto } 483258945Sroberto } else { 484258945Sroberto if (fam == AF_UNSPEC) { 485258945Sroberto /* "any" or "none" */ 486258945Sroberto node->node_num[0] = node->node_num[1] = 487258945Sroberto ++radix->num_added_node; 488258945Sroberto } else { 489258945Sroberto node->node_num[ISC_IS6(fam)] = 490258945Sroberto ++radix->num_added_node; 491258945Sroberto } 492258945Sroberto } 493258945Sroberto *target = node; 494258945Sroberto return (ISC_R_SUCCESS); 495258945Sroberto } 496258945Sroberto 497258945Sroberto new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 498258945Sroberto if (new_node == NULL) 499258945Sroberto return (ISC_R_NOMEMORY); 500258945Sroberto if (node->bit != differ_bit && bitlen != differ_bit) { 501258945Sroberto glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 502258945Sroberto if (glue == NULL) { 503258945Sroberto isc_mem_put(radix->mctx, new_node, 504258945Sroberto sizeof(isc_radix_node_t)); 505258945Sroberto return (ISC_R_NOMEMORY); 506258945Sroberto } 507258945Sroberto } 508258945Sroberto new_node->bit = bitlen; 509258945Sroberto new_node->prefix = NULL; 510258945Sroberto result = _ref_prefix(radix->mctx, &new_node->prefix, prefix); 511258945Sroberto if (result != ISC_R_SUCCESS) { 512258945Sroberto isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t)); 513258945Sroberto if (glue != NULL) 514258945Sroberto isc_mem_put(radix->mctx, glue, 515258945Sroberto sizeof(isc_radix_node_t)); 516258945Sroberto return (result); 517258945Sroberto } 518258945Sroberto new_node->parent = NULL; 519258945Sroberto new_node->l = new_node->r = NULL; 520258945Sroberto new_node->node_num[0] = new_node->node_num[1] = -1; 521258945Sroberto radix->num_active_node++; 522258945Sroberto 523258945Sroberto if (source != NULL) { 524258945Sroberto /* Merging node */ 525258945Sroberto if (source->node_num[0] != -1) 526258945Sroberto new_node->node_num[0] = radix->num_added_node + 527258945Sroberto source->node_num[0]; 528258945Sroberto if (source->node_num[1] != -1) 529258945Sroberto new_node->node_num[1] = radix->num_added_node + 530258945Sroberto source->node_num[1]; 531258945Sroberto new_node->data[0] = source->data[0]; 532258945Sroberto new_node->data[1] = source->data[1]; 533258945Sroberto } else { 534258945Sroberto if (fam == AF_UNSPEC) { 535258945Sroberto /* "any" or "none" */ 536258945Sroberto new_node->node_num[0] = new_node->node_num[1] = 537258945Sroberto ++radix->num_added_node; 538258945Sroberto } else { 539258945Sroberto new_node->node_num[ISC_IS6(fam)] = 540258945Sroberto ++radix->num_added_node; 541258945Sroberto } 542258945Sroberto new_node->data[0] = NULL; 543258945Sroberto new_node->data[1] = NULL; 544258945Sroberto } 545258945Sroberto 546258945Sroberto if (node->bit == differ_bit) { 547258945Sroberto INSIST(glue == NULL); 548258945Sroberto new_node->parent = node; 549258945Sroberto if (node->bit < radix->maxbits && 550258945Sroberto BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 551258945Sroberto { 552258945Sroberto INSIST(node->r == NULL); 553258945Sroberto node->r = new_node; 554258945Sroberto } else { 555258945Sroberto INSIST(node->l == NULL); 556258945Sroberto node->l = new_node; 557258945Sroberto } 558258945Sroberto *target = new_node; 559258945Sroberto return (ISC_R_SUCCESS); 560258945Sroberto } 561258945Sroberto 562258945Sroberto if (bitlen == differ_bit) { 563258945Sroberto INSIST(glue == NULL); 564258945Sroberto if (bitlen < radix->maxbits && 565258945Sroberto BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) { 566258945Sroberto new_node->r = node; 567258945Sroberto } else { 568258945Sroberto new_node->l = node; 569258945Sroberto } 570258945Sroberto new_node->parent = node->parent; 571258945Sroberto if (node->parent == NULL) { 572258945Sroberto INSIST(radix->head == node); 573258945Sroberto radix->head = new_node; 574258945Sroberto } else if (node->parent->r == node) { 575258945Sroberto node->parent->r = new_node; 576258945Sroberto } else { 577258945Sroberto node->parent->l = new_node; 578258945Sroberto } 579258945Sroberto node->parent = new_node; 580258945Sroberto } else { 581258945Sroberto INSIST(glue != NULL); 582258945Sroberto glue->bit = differ_bit; 583258945Sroberto glue->prefix = NULL; 584258945Sroberto glue->parent = node->parent; 585258945Sroberto glue->data[0] = glue->data[1] = NULL; 586258945Sroberto glue->node_num[0] = glue->node_num[1] = -1; 587258945Sroberto radix->num_active_node++; 588258945Sroberto if (differ_bit < radix->maxbits && 589258945Sroberto BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) { 590258945Sroberto glue->r = new_node; 591258945Sroberto glue->l = node; 592258945Sroberto } else { 593258945Sroberto glue->r = node; 594258945Sroberto glue->l = new_node; 595258945Sroberto } 596258945Sroberto new_node->parent = glue; 597258945Sroberto 598258945Sroberto if (node->parent == NULL) { 599258945Sroberto INSIST(radix->head == node); 600258945Sroberto radix->head = glue; 601258945Sroberto } else if (node->parent->r == node) { 602258945Sroberto node->parent->r = glue; 603258945Sroberto } else { 604258945Sroberto node->parent->l = glue; 605258945Sroberto } 606258945Sroberto node->parent = glue; 607258945Sroberto } 608258945Sroberto 609258945Sroberto *target = new_node; 610258945Sroberto return (ISC_R_SUCCESS); 611258945Sroberto} 612258945Sroberto 613258945Srobertovoid 614258945Srobertoisc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) { 615258945Sroberto isc_radix_node_t *parent, *child; 616258945Sroberto 617258945Sroberto REQUIRE(radix != NULL); 618258945Sroberto REQUIRE(node != NULL); 619258945Sroberto 620258945Sroberto if (node->r && node->l) { 621258945Sroberto /* 622258945Sroberto * This might be a placeholder node -- have to check and 623258945Sroberto * make sure there is a prefix associated with it! 624258945Sroberto */ 625258945Sroberto if (node->prefix != NULL) 626258945Sroberto _deref_prefix(radix->mctx, node->prefix); 627258945Sroberto 628258945Sroberto node->prefix = NULL; 629258945Sroberto node->data[0] = node->data[1] = NULL; 630258945Sroberto return; 631258945Sroberto } 632258945Sroberto 633258945Sroberto if (node->r == NULL && node->l == NULL) { 634258945Sroberto parent = node->parent; 635258945Sroberto _deref_prefix(radix->mctx, node->prefix); 636258945Sroberto isc_mem_put(radix->mctx, node, sizeof(*node)); 637258945Sroberto radix->num_active_node--; 638258945Sroberto 639258945Sroberto if (parent == NULL) { 640258945Sroberto INSIST(radix->head == node); 641258945Sroberto radix->head = NULL; 642258945Sroberto return; 643258945Sroberto } 644258945Sroberto 645258945Sroberto if (parent->r == node) { 646258945Sroberto parent->r = NULL; 647258945Sroberto child = parent->l; 648258945Sroberto } else { 649258945Sroberto INSIST(parent->l == node); 650258945Sroberto parent->l = NULL; 651258945Sroberto child = parent->r; 652258945Sroberto } 653258945Sroberto 654258945Sroberto if (parent->prefix) 655258945Sroberto return; 656258945Sroberto 657258945Sroberto /* We need to remove parent too. */ 658258945Sroberto 659258945Sroberto if (parent->parent == NULL) { 660258945Sroberto INSIST(radix->head == parent); 661258945Sroberto radix->head = child; 662258945Sroberto } else if (parent->parent->r == parent) { 663258945Sroberto parent->parent->r = child; 664258945Sroberto } else { 665258945Sroberto INSIST(parent->parent->l == parent); 666258945Sroberto parent->parent->l = child; 667258945Sroberto } 668258945Sroberto child->parent = parent->parent; 669258945Sroberto isc_mem_put(radix->mctx, parent, sizeof(*parent)); 670258945Sroberto radix->num_active_node--; 671258945Sroberto return; 672258945Sroberto } 673258945Sroberto 674258945Sroberto if (node->r) { 675258945Sroberto child = node->r; 676258945Sroberto } else { 677258945Sroberto INSIST(node->l != NULL); 678258945Sroberto child = node->l; 679258945Sroberto } 680258945Sroberto parent = node->parent; 681258945Sroberto child->parent = parent; 682258945Sroberto 683258945Sroberto _deref_prefix(radix->mctx, node->prefix); 684258945Sroberto isc_mem_put(radix->mctx, node, sizeof(*node)); 685258945Sroberto radix->num_active_node--; 686258945Sroberto 687258945Sroberto if (parent == NULL) { 688258945Sroberto INSIST(radix->head == node); 689258945Sroberto radix->head = child; 690258945Sroberto return; 691258945Sroberto } 692258945Sroberto 693258945Sroberto if (parent->r == node) { 694258945Sroberto parent->r = child; 695258945Sroberto } else { 696258945Sroberto INSIST(parent->l == node); 697258945Sroberto parent->l = child; 698258945Sroberto } 699258945Sroberto} 700258945Sroberto 701258945Sroberto/* 702258945SrobertoLocal Variables: 703258945Srobertoc-basic-offset: 4 704258945Srobertoindent-tabs-mode: t 705258945SrobertoEnd: 706258945Sroberto*/ 707