Lines Matching refs:node
216 isc_radix_node_t *node; in isc_radix_process() local
220 RADIX_WALK(radix->head, node) { func(node->prefix, node->data); } in isc_radix_process()
227 isc_radix_node_t *node; in isc_radix_search() local
240 node = radix->head; in isc_radix_search()
242 if (node == NULL) { in isc_radix_search()
249 while (node != NULL && node->bit < bitlen) { in isc_radix_search()
250 if (node->prefix) { in isc_radix_search()
251 stack[cnt++] = node; in isc_radix_search()
254 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) in isc_radix_search()
256 node = node->r; in isc_radix_search()
258 node = node->l; in isc_radix_search()
262 if (node != NULL && node->prefix) { in isc_radix_search()
263 stack[cnt++] = node; in isc_radix_search()
267 node = stack[cnt]; in isc_radix_search()
269 if (prefix->bitlen < node->bit) { in isc_radix_search()
273 if (_comp_with_mask(isc_prefix_tochar(node->prefix), in isc_radix_search()
275 node->prefix->bitlen)) in isc_radix_search()
278 if (node->node_num[fam] != -1 && in isc_radix_search()
280 (*target)->node_num[tfam] > node->node_num[fam])) in isc_radix_search()
282 *target = node; in isc_radix_search()
298 isc_radix_node_t *node, *new_node, *parent, *glue = NULL; in isc_radix_insert() local
319 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); in isc_radix_insert()
320 node->bit = bitlen; in isc_radix_insert()
322 node->node_num[i] = -1; in isc_radix_insert()
324 node->prefix = NULL; in isc_radix_insert()
325 result = _ref_prefix(radix->mctx, &node->prefix, prefix); in isc_radix_insert()
327 isc_mem_put(radix->mctx, node, in isc_radix_insert()
331 node->parent = NULL; in isc_radix_insert()
332 node->l = node->r = NULL; in isc_radix_insert()
344 node->node_num[i] = in isc_radix_insert()
348 node->data[i] = source->data[i]; in isc_radix_insert()
355 node->node_num[i] = next; in isc_radix_insert()
358 node->node_num[ISC_RADIX_FAMILY(prefix)] = next; in isc_radix_insert()
361 memset(node->data, 0, sizeof(node->data)); in isc_radix_insert()
363 radix->head = node; in isc_radix_insert()
365 *target = node; in isc_radix_insert()
370 node = radix->head; in isc_radix_insert()
372 while (node->bit < bitlen || node->prefix == NULL) { in isc_radix_insert()
373 if (node->bit < radix->maxbits && in isc_radix_insert()
374 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) in isc_radix_insert()
376 if (node->r == NULL) { in isc_radix_insert()
379 node = node->r; in isc_radix_insert()
381 if (node->l == NULL) { in isc_radix_insert()
384 node = node->l; in isc_radix_insert()
387 INSIST(node != NULL); in isc_radix_insert()
390 INSIST(node->prefix != NULL); in isc_radix_insert()
392 test_addr = isc_prefix_touchar(node->prefix); in isc_radix_insert()
394 check_bit = (node->bit < bitlen) ? node->bit : bitlen; in isc_radix_insert()
417 parent = node->parent; in isc_radix_insert()
419 node = parent; in isc_radix_insert()
420 parent = node->parent; in isc_radix_insert()
423 if (differ_bit == bitlen && node->bit == bitlen) { in isc_radix_insert()
424 if (node->prefix != NULL) { in isc_radix_insert()
429 if (node->node_num[i] == -1 && in isc_radix_insert()
432 node->node_num[i] = in isc_radix_insert()
435 node->data[i] = source->data[i]; in isc_radix_insert()
443 if (node->node_num[i] == -1) { in isc_radix_insert()
444 node->node_num[i] = in isc_radix_insert()
452 if (node->node_num[foff] == -1) { in isc_radix_insert()
453 node->node_num[foff] = in isc_radix_insert()
458 *target = node; in isc_radix_insert()
461 result = _ref_prefix(radix->mctx, &node->prefix, in isc_radix_insert()
467 INSIST(node->data[RADIX_V4] == NULL && in isc_radix_insert()
468 node->node_num[RADIX_V4] == -1 && in isc_radix_insert()
469 node->data[RADIX_V4] == NULL && in isc_radix_insert()
470 node->node_num[RADIX_V4] == -1); in isc_radix_insert()
476 node->node_num[i] = in isc_radix_insert()
478 node->data[i] = source->data[i]; in isc_radix_insert()
486 node->node_num[i] = next; in isc_radix_insert()
489 node->node_num[ISC_RADIX_FAMILY(prefix)] = next; in isc_radix_insert()
492 *target = node; in isc_radix_insert()
497 if (node->bit != differ_bit && bitlen != differ_bit) { in isc_radix_insert()
542 if (node->bit == differ_bit) { in isc_radix_insert()
544 new_node->parent = node; in isc_radix_insert()
545 if (node->bit < radix->maxbits && in isc_radix_insert()
546 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) in isc_radix_insert()
548 INSIST(node->r == NULL); in isc_radix_insert()
549 node->r = new_node; in isc_radix_insert()
551 INSIST(node->l == NULL); in isc_radix_insert()
552 node->l = new_node; in isc_radix_insert()
563 new_node->r = node; in isc_radix_insert()
565 new_node->l = node; in isc_radix_insert()
567 new_node->parent = node->parent; in isc_radix_insert()
568 if (node->parent == NULL) { in isc_radix_insert()
569 INSIST(radix->head == node); in isc_radix_insert()
571 } else if (node->parent->r == node) { in isc_radix_insert()
572 node->parent->r = new_node; in isc_radix_insert()
574 node->parent->l = new_node; in isc_radix_insert()
576 node->parent = new_node; in isc_radix_insert()
581 glue->parent = node->parent; in isc_radix_insert()
591 glue->l = node; in isc_radix_insert()
593 glue->r = node; in isc_radix_insert()
598 if (node->parent == NULL) { in isc_radix_insert()
599 INSIST(radix->head == node); in isc_radix_insert()
601 } else if (node->parent->r == node) { in isc_radix_insert()
602 node->parent->r = glue; in isc_radix_insert()
604 node->parent->l = glue; in isc_radix_insert()
606 node->parent = glue; in isc_radix_insert()
614 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) { in isc_radix_remove() argument
618 REQUIRE(node != NULL); in isc_radix_remove()
620 if (node->r && node->l) { in isc_radix_remove()
625 if (node->prefix != NULL) { in isc_radix_remove()
626 _deref_prefix(node->prefix); in isc_radix_remove()
629 node->prefix = NULL; in isc_radix_remove()
630 memset(node->data, 0, sizeof(node->data)); in isc_radix_remove()
634 if (node->r == NULL && node->l == NULL) { in isc_radix_remove()
635 parent = node->parent; in isc_radix_remove()
636 _deref_prefix(node->prefix); in isc_radix_remove()
639 INSIST(radix->head == node); in isc_radix_remove()
641 isc_mem_put(radix->mctx, node, sizeof(*node)); in isc_radix_remove()
646 if (parent->r == node) { in isc_radix_remove()
650 INSIST(parent->l == node); in isc_radix_remove()
655 isc_mem_put(radix->mctx, node, sizeof(*node)); in isc_radix_remove()
679 if (node->r) { in isc_radix_remove()
680 child = node->r; in isc_radix_remove()
682 INSIST(node->l != NULL); in isc_radix_remove()
683 child = node->l; in isc_radix_remove()
686 parent = node->parent; in isc_radix_remove()
689 _deref_prefix(node->prefix); in isc_radix_remove()
692 INSIST(radix->head == node); in isc_radix_remove()
694 isc_mem_put(radix->mctx, node, sizeof(*node)); in isc_radix_remove()
699 isc_mem_put(radix->mctx, node, sizeof(*node)); in isc_radix_remove()
702 if (parent->r == node) { in isc_radix_remove()
705 INSIST(parent->l == node); in isc_radix_remove()