Lines Matching defs:node
158 * if func is supplied, it will be called as func(node->data)
159 * before deleting the node
217 * func will be called as func(node->prefix, node->data)
221 isc_radix_node_t *node;
225 RADIX_WALK(radix->head, node) {
226 func(node->prefix, node->data);
235 isc_radix_node_t *node;
252 node = radix->head;
256 while (node->bit < bitlen) {
257 if (node->prefix)
258 stack[cnt++] = node;
260 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
261 node = node->r;
263 node = node->l;
265 if (node == NULL)
269 if (node && node->prefix)
270 stack[cnt++] = node;
273 node = stack[cnt];
275 if (prefix->bitlen < node->bit)
278 if (_comp_with_mask(isc_prefix_tochar(node->prefix),
280 node->prefix->bitlen))
283 if (node->node_num[off] != -1 &&
285 (*target)->node_num[toff] > node->node_num[off]))
287 *target = node;
304 isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
324 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
325 if (node == NULL)
327 node->bit = bitlen;
329 node->node_num[i] = -1;
330 node->prefix = NULL;
331 result = _ref_prefix(radix->mctx, &node->prefix, prefix);
333 isc_mem_put(radix->mctx, node,
337 node->parent = NULL;
338 node->l = node->r = NULL;
342 * node from an existing radix tree. To keep
350 node->node_num[i] =
353 node->data[i] = source->data[i];
360 node->node_num[i] = next;
362 node->node_num[ISC_RADIX_OFF(prefix)] = next;
365 memset(node->data, 0, sizeof(node->data));
367 radix->head = node;
369 *target = node;
374 node = radix->head;
376 while (node->bit < bitlen || node->prefix == NULL) {
377 if (node->bit < radix->maxbits &&
378 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
380 if (node->r == NULL)
382 node = node->r;
384 if (node->l == NULL)
386 node = node->l;
389 INSIST(node != NULL);
392 INSIST(node->prefix != NULL);
394 test_addr = isc_prefix_touchar(node->prefix);
396 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
417 parent = node->parent;
419 node = parent;
420 parent = node->parent;
423 if (differ_bit == bitlen && node->bit == bitlen) {
424 if (node->prefix != NULL) {
429 if (node->node_num[i] == -1 &&
431 node->node_num[i] =
434 node->data[i] = source->data[i];
442 if (node->node_num[i] == -1) {
443 node->node_num[i] =
451 if (node->node_num[off] == -1)
452 node->node_num[off] =
456 *target = node;
460 &node->prefix, prefix);
464 INSIST(node->data[0] == NULL && node->node_num[0] == -1 &&
465 node->data[1] == NULL && node->node_num[1] == -1 &&
466 node->data[2] == NULL && node->node_num[2] == -1 &&
467 node->data[3] == NULL && node->node_num[3] == -1);
469 /* Merging node */
473 node->node_num[i] =
475 node->data[i] = source->data[i];
483 node->node_num[i] = next;
485 node->node_num[ISC_RADIX_OFF(prefix)] = next;
488 *target = node;
495 if (node->bit != differ_bit && bitlen != differ_bit) {
522 /* Merging node */
543 if (node->bit == differ_bit) {
545 new_node->parent = node;
546 if (node->bit < radix->maxbits &&
547 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
549 INSIST(node->r == NULL);
550 node->r = new_node;
552 INSIST(node->l == NULL);
553 node->l = new_node;
563 new_node->r = node;
565 new_node->l = node;
567 new_node->parent = node->parent;
568 if (node->parent == NULL) {
569 INSIST(radix->head == node);
571 } else if (node->parent->r == node) {
572 node->parent->r = new_node;
574 node->parent->l = new_node;
576 node->parent = new_node;
581 glue->parent = node->parent;
590 glue->l = node;
592 glue->r = node;
597 if (node->parent == NULL) {
598 INSIST(radix->head == node);
600 } else if (node->parent->r == node) {
601 node->parent->r = glue;
603 node->parent->l = glue;
605 node->parent = glue;
613 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
617 REQUIRE(node != NULL);
619 if (node->r && node->l) {
621 * This might be a placeholder node -- have to check and
624 if (node->prefix != NULL)
625 _deref_prefix(node->prefix);
627 node->prefix = NULL;
628 memset(node->data, 0, sizeof(node->data));
632 if (node->r == NULL && node->l == NULL) {
633 parent = node->parent;
634 _deref_prefix(node->prefix);
637 INSIST(radix->head == node);
639 isc_mem_put(radix->mctx, node, sizeof(*node));
644 if (parent->r == node) {
648 INSIST(parent->l == node);
653 isc_mem_put(radix->mctx, node, sizeof(*node));
676 if (node->r) {
677 child = node->r;
679 INSIST(node->l != NULL);
680 child = node->l;
683 parent = node->parent;
686 _deref_prefix(node->prefix);
689 INSIST(radix->head == node);
691 isc_mem_put(radix->mctx, node, sizeof(*node));
696 isc_mem_put(radix->mctx, node, sizeof(*node));
699 if (parent->r == node) {
702 INSIST(parent->l == node);