lib/isc/radix.c

	radix.c revision a05abc17674c6b528caf3082680d45a5a63d734e
1633838b8255282d10af15c5c84cee5a51466712Bob Halley/*
2dd6ffb5cb356956685484160b0fdf157e2e9787Tinderbox User * Copyright (C) 2007, 2008  Internet Systems Consortium, Inc. ("ISC")
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews *
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * Permission to use, copy, modify, and/or distribute this software for any
ec5347e2c775f027573ce5648b910361aa926c01Automatic Updater * purpose with or without fee is hereby granted, provided that the above
1633838b8255282d10af15c5c84cee5a51466712Bob Halley * copyright notice and this permission notice appear in all copies.
1633838b8255282d10af15c5c84cee5a51466712Bob Halley *
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * PERFORMANCE OF THIS SOFTWARE.
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews */
1633838b8255282d10af15c5c84cee5a51466712Bob Halley
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley/* $Id: radix.c,v 1.22 2009/01/18 00:46:01 fdupont Exp $ */
ece6c39dd823d92cf89e7e37614bd458d5d42658Mark Andrews
9c3531d72aeaad6c5f01efe6a1c82023e1379e4dDavid Lawrence/*
d25afd60ee2286cb171c4960a790f3d7041b6f85Bob Halley * This source was adapted from MRT's RCS Ids:
d25afd60ee2286cb171c4960a790f3d7041b6f85Bob Halley * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence */
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley#include <config.h>
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley#include <isc/mem.h>
9fbefe0ace2ae7dba287f914b278153004bef428Bob Halley#include <isc/types.h>
9fbefe0ace2ae7dba287f914b278153004bef428Bob Halley#include <isc/util.h>
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley#include <isc/radix.h>
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halleystatic isc_result_t
a147de10fe5e19e593d42152ffd6879eca69860dEvan Hunt_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family,
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer        void *dest, int bitlen);
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrencestatic void
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix);
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrencestatic isc_result_t
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrencestatic int
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence_comp_with_mask(void *addr, void *dest, u_int mask);
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayerstatic void
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayerstatic isc_result_t
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer        int bitlen)
27809a2ee5db141b684e53bf1d94da26e9f92d3aMark Andrews{
27809a2ee5db141b684e53bf1d94da26e9f92d3aMark Andrews    isc_prefix_t *prefix;
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    REQUIRE(target != NULL);
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC)
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley        return (ISC_R_NOTIMPLEMENTED);
27809a2ee5db141b684e53bf1d94da26e9f92d3aMark Andrews
27809a2ee5db141b684e53bf1d94da26e9f92d3aMark Andrews    prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
ea872078bfa9473cfe9c89b474dae2496377797bDavid Lawrence    if (prefix == NULL)
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley        return (ISC_R_NOMEMORY);
e76d4c91bfadf823f04dcca1c1c5bcc14c67671dAndreas Gustafsson
e76d4c91bfadf823f04dcca1c1c5bcc14c67671dAndreas Gustafsson    if (family == AF_INET6) {
e76d4c91bfadf823f04dcca1c1c5bcc14c67671dAndreas Gustafsson        prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley        memcpy(&prefix->add.sin6, dest, 16);
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer    } else {
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley        /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */
e72c1e7e465822fc9b5067b2dd3cf047f6132214Mark Andrews        prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
e72c1e7e465822fc9b5067b2dd3cf047f6132214Mark Andrews        memcpy(&prefix->add.sin, dest, 4);
e72c1e7e465822fc9b5067b2dd3cf047f6132214Mark Andrews    }
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence
e72c1e7e465822fc9b5067b2dd3cf047f6132214Mark Andrews    prefix->family = family;
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    isc_refcount_init(&prefix->refcount, 1);
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson    *target = prefix;
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    return (ISC_R_SUCCESS);
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley}
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halleystatic void
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix) {
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    int refs;
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews    if (prefix == NULL)
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews        return;
bcb68be0a8f3c3eca58d6a6a869267e5c1841de2Francis Dupont
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews    isc_refcount_decrement(&prefix->refcount, &refs);
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews    if (refs <= 0) {
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews        isc_refcount_destroy(&prefix->refcount);
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews        isc_mem_put(mctx, prefix, sizeof(isc_prefix_t));
e2c97aef510f4cdced2894ab2a5daf2b1d316e2aAutomatic Updater    }
bcb68be0a8f3c3eca58d6a6a869267e5c1841de2Francis Dupont}
e2c97aef510f4cdced2894ab2a5daf2b1d316e2aAutomatic Updater
dc1cfff92a77c5b47e5665a3c2f0153d79074f47Evan Huntstatic isc_result_t
dc1cfff92a77c5b47e5665a3c2f0153d79074f47Evan Hunt_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews    INSIST(prefix != NULL);
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews    INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
ed9ca2306508e3106e3d111d7cf39bf82f8689d0Mark Andrews           (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews           (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews    REQUIRE(target != NULL && *target == NULL);
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews    /*
8343d55b3d97923fa444ea9b92aae2ec60ffd40fMark Andrews     * If this prefix is a static allocation, copy it into new memory.
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley     * (Note, the refcount still has to be destroyed by the calling
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence     * routine.)
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley     */
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    if (isc_refcount_current(&prefix->refcount) == 0) {
355cc22e32085faeb553fe6c37de69e83b9d5191Andreas Gustafsson        isc_result_t ret;
355cc22e32085faeb553fe6c37de69e83b9d5191Andreas Gustafsson        ret = _new_prefix(mctx, target, prefix->family,
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley                  &prefix->add, prefix->bitlen);
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley        return ret;
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    }
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    isc_refcount_increment(&prefix->refcount, NULL);
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
355cc22e32085faeb553fe6c37de69e83b9d5191Andreas Gustafsson    *target = prefix;
355cc22e32085faeb553fe6c37de69e83b9d5191Andreas Gustafsson    return (ISC_R_SUCCESS);
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley}
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halleystatic int
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley_comp_with_mask(void *addr, void *dest, u_int mask) {
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    /* Mask length of zero matches everything */
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    if (mask == 0)
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley        return (1);
9fbefe0ace2ae7dba287f914b278153004bef428Bob Halley
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley    if (memcmp(addr, dest, mask / 8) == 0) {
9fbefe0ace2ae7dba287f914b278153004bef428Bob Halley        int n = mask / 8;
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley        int m = ((~0) << (8 - (mask % 8)));
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley        if ((mask % 8) == 0 ||
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence            (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson            return (1);
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    }
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    return (0);
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence}
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrenceisc_result_t
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrenceisc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    isc_radix_tree_t *radix;
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    REQUIRE(target != NULL && *target == NULL);
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer    radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence    if (radix == NULL)
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence        return (ISC_R_NOMEMORY);
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    radix->mctx = mctx;
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    radix->maxbits = maxbits;
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    radix->head = NULL;
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    radix->num_active_node = 0;
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    radix->num_added_node = 0;
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    radix->magic = RADIX_TREE_MAGIC;
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    *target = radix;
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson    return (ISC_R_SUCCESS);
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley}
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley/*
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley * if func is supplied, it will be called as func(node->data)
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley * before deleting the node
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence */
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafssonstatic void
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    REQUIRE(radix != NULL);
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley    if (radix->head != NULL) {
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley        isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer        isc_radix_node_t **Xsp = Xstack;
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence        isc_radix_node_t *Xrn = radix->head;
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence        while (Xrn != NULL) {
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence            isc_radix_node_t *l = Xrn->l;
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence            isc_radix_node_t *r = Xrn->r;
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence            if (Xrn->prefix != NULL) {
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence                _deref_prefix(radix->mctx, Xrn->prefix);
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley                if (func != NULL && (Xrn->data[0] != NULL ||
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley                             Xrn->data[1] != NULL))
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence                    func(Xrn->data);
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson            } else {
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson                INSIST(Xrn->data[0] == NULL &&
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence                       Xrn->data[1] == NULL);
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley            }
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley            isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley            radix->num_active_node--;
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley            if (l != NULL) {
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer                if (r != NULL) {
6fa1cb5754695d550a58c6e8978fda65f5146af7David Lawrence                    *Xsp++ = r;
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence                }
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence                Xrn = l;
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence            } else if (r != NULL) {
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence                Xrn = r;
585529aaeb95a71cd3d95df2602a4688fc7c3292David Lawrence            } else if (Xsp != Xstack) {
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer                Xrn = *(--Xsp);
e35c1bb3ecd9a6597360b9160b397c8053af69bfDanny Mayer            } else {
0fc87fa2f38df7b293b650deacfa5e6c3d50eff9Bob Halley                Xrn = NULL;
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley            }
d3e7d196cd14fc3095ce97846a66cd49fc6fee6dDavid Lawrence        }
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson    }
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    RUNTIME_CHECK(radix->num_active_node == 0);
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley}
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrencevoid
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrenceisc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func)
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley{
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence    REQUIRE(radix != NULL);
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley    _clear_radix(radix, func);
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley    isc_mem_put(radix->mctx, radix, sizeof(*radix));
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley}
b592e197fe354d7258dc4166fce0a9425a338b0bBob Halley
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence/*
d3e7d196cd14fc3095ce97846a66cd49fc6fee6dDavid Lawrence * func will be called as func(node->prefix, node->data)
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrence */
d3e7d196cd14fc3095ce97846a66cd49fc6fee6dDavid Lawrencevoid
d5069ac954d067aa45ad395fc338f7e499b834c1David Lawrenceisc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func)
d3e7d196cd14fc3095ce97846a66cd49fc6fee6dDavid Lawrence{
4d6964d70a114b53a11a3bd778d9b8f5179a7934Bob Halley    isc_radix_node_t *node;
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence
28b863e609ff2d97b78663b46894494cfa2ea411Mark Andrews    REQUIRE(func != NULL);
28b863e609ff2d97b78663b46894494cfa2ea411Mark Andrews
bcb68be0a8f3c3eca58d6a6a869267e5c1841de2Francis Dupont    RADIX_WALK(radix->head, node) {
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews        func(node->prefix, node->data);
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews    } RADIX_WALK_END;
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews}
28b863e609ff2d97b78663b46894494cfa2ea411Mark Andrews
bcb68be0a8f3c3eca58d6a6a869267e5c1841de2Francis Dupont
28b863e609ff2d97b78663b46894494cfa2ea411Mark Andrewsisc_result_t
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrewsisc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews         isc_prefix_t *prefix)
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews{
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews    isc_radix_node_t *node;
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews    isc_radix_node_t *stack[RADIX_MAXBITS + 1];
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews    u_char *addr;
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews    isc_uint32_t bitlen;
ece6c39dd823d92cf89e7e37614bd458d5d42658Mark Andrews    int tfamily = -1;
28b863e609ff2d97b78663b46894494cfa2ea411Mark Andrews    int cnt = 0;
28b863e609ff2d97b78663b46894494cfa2ea411Mark Andrews
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    REQUIRE(radix != NULL);
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    REQUIRE(prefix != NULL);
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    REQUIRE(target != NULL && *target == NULL);
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    *target = NULL;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    if (radix->head == NULL) {
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        return (ISC_R_NOTFOUND);
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    }
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt
f459b70c8ea8fb7aed93ff3b3104b837e009c6fdEvan Hunt    node = radix->head;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    addr = isc_prefix_touchar(prefix);
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    bitlen = prefix->bitlen;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    while (node->bit < bitlen) {
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        if (node->prefix)
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt            stack[cnt++] = node;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence            node = node->r;
6c6ceac1bc66812f6e0097dcf5fd8b901c3fecd1Andreas Gustafsson        else
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews            node = node->l;
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews        if (node == NULL)
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews            break;
1d9958c6cc291916010779792f0fbdf6cd5ba368Mark Andrews    }
11d732daac76a24a0f3e5948a2758a4b866a0825David Lawrence
ff8cd3afa7f900d7986ccbc3638235cb8ad6f1ecAndreas Gustafsson    if (node && node->prefix)
ff8cd3afa7f900d7986ccbc3638235cb8ad6f1ecAndreas Gustafsson        stack[cnt++] = node;
ff8cd3afa7f900d7986ccbc3638235cb8ad6f1ecAndreas Gustafsson
ff8cd3afa7f900d7986ccbc3638235cb8ad6f1ecAndreas Gustafsson    while (--cnt >= 0) {
ff8cd3afa7f900d7986ccbc3638235cb8ad6f1ecAndreas Gustafsson        node = stack[cnt];
b38ab99bdc833da490c0ca0cbd05fb9d54dff997Andreas Gustafsson
b38ab99bdc833da490c0ca0cbd05fb9d54dff997Andreas Gustafsson        if (_comp_with_mask(isc_prefix_tochar(node->prefix),
6ebd91a0c7f4c62a501b67adce4a6800d8b7dfacAutomatic Updater                    isc_prefix_tochar(prefix),
ff8cd3afa7f900d7986ccbc3638235cb8ad6f1ecAndreas Gustafsson                    node->prefix->bitlen)) {
ff8cd3afa7f900d7986ccbc3638235cb8ad6f1ecAndreas Gustafsson            if (node->node_num[ISC_IS6(prefix->family)] != -1 &&
b38ab99bdc833da490c0ca0cbd05fb9d54dff997Andreas Gustafsson                 ((*target == NULL) ||
fcb54ce0a4f7377486df5bec83b3aa4711bf4131Mark Andrews                  (*target)->node_num[ISC_IS6(tfamily)] >
fcb54ce0a4f7377486df5bec83b3aa4711bf4131Mark Andrews                   node->node_num[ISC_IS6(prefix->family)])) {
b38ab99bdc833da490c0ca0cbd05fb9d54dff997Andreas Gustafsson                *target = node;
b38ab99bdc833da490c0ca0cbd05fb9d54dff997Andreas Gustafsson                tfamily = prefix->family;
6ebd91a0c7f4c62a501b67adce4a6800d8b7dfacAutomatic Updater            }
b38ab99bdc833da490c0ca0cbd05fb9d54dff997Andreas Gustafsson        }
b38ab99bdc833da490c0ca0cbd05fb9d54dff997Andreas Gustafsson    }
6ebd91a0c7f4c62a501b67adce4a6800d8b7dfacAutomatic Updater
a6f0e9c985220f0e4509777e6528afb64e0ad576Mukund Sivaraman    if (*target == NULL) {
a6f0e9c985220f0e4509777e6528afb64e0ad576Mukund Sivaraman        return (ISC_R_NOTFOUND);
a6f0e9c985220f0e4509777e6528afb64e0ad576Mukund Sivaraman    } else {
a6f0e9c985220f0e4509777e6528afb64e0ad576Mukund Sivaraman        return (ISC_R_SUCCESS);
ff8cd3afa7f900d7986ccbc3638235cb8ad6f1ecAndreas Gustafsson    }
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews}
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrewsisc_result_t
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrewsisc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews         isc_radix_node_t *source, isc_prefix_t *prefix)
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews{
6ebd91a0c7f4c62a501b67adce4a6800d8b7dfacAutomatic Updater    isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt    u_char *addr, *test_addr;
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt    isc_uint32_t bitlen, fam, check_bit, differ_bit;
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews    isc_uint32_t i, j, r;
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews    isc_result_t result;
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt
99bf6a57d9f6b55da6de9c22fb6883a4bf7d569eEvan Hunt    REQUIRE(radix != NULL);
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews    REQUIRE(target != NULL && *target == NULL);
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews    REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews    RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
6ebd91a0c7f4c62a501b67adce4a6800d8b7dfacAutomatic Updater
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews    if (prefix == NULL)
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews        prefix = source->prefix;
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews    INSIST(prefix != NULL);
186e7f37c9fc985a7a7264cc8170e48a25bed434Mark Andrews
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt    bitlen = prefix->bitlen;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    fam = prefix->family;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt    if (radix->head == NULL) {
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        if (node == NULL)
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt            return (ISC_R_NOMEMORY);
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        node->bit = bitlen;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        node->node_num[0] = node->node_num[1] = -1;
a147de10fe5e19e593d42152ffd6879eca69860dEvan Hunt        node->prefix = NULL;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        result = _ref_prefix(radix->mctx, &node->prefix, prefix);
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        if (result != ISC_R_SUCCESS) {
a147de10fe5e19e593d42152ffd6879eca69860dEvan Hunt            isc_mem_put(radix->mctx, node,
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt                    sizeof(isc_radix_node_t));
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt            return (result);
dbb012765c735ee0d82dedb116cdc7cf18957814Evan Hunt        }
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        node->parent = NULL;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        node->l = node->r = NULL;
1bb2f53b9f74a8ca9812cbe9243ef41190b4da14Evan Hunt        if (source != NULL) {
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt            /*
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt             * If source is non-NULL, then we're merging in a
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt             * node from an existing radix tree.  To keep
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt             * the node_num values consistent, the calling
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt             * function will add the total number of nodes
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt             * added to num_added_node at the end of
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt             * the merge operation--we don't do it here.
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt             */
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt            if (source->node_num[0] != -1)
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt                node->node_num[0] = radix->num_added_node +
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt                            source->node_num[0];
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt            if (source->node_num[1] != -1)
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt                node->node_num[1] = radix->num_added_node +
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt                            source->node_num[1];
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt            node->data[0] = source->data[0];
8a6f41d86ac80fd1397ffee65bed5131129a84e2Mark Andrews            node->data[1] = source->data[1];
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt        } else {
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt            if (fam == AF_UNSPEC) {
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt                /* "any" or "none" */
aeff7de836558fa8002ab5db35292d2bb6450da8Evan Hunt                node->node_num[0] = node->node_num[1] =
                    ++radix->num_added_node;
            } else {
                node->node_num[ISC_IS6(fam)] =
                    ++radix->num_added_node;
            }
            node->data[0] = NULL;
            node->data[1] = NULL;
        }
        radix->head = node;
        radix->num_active_node++;
        *target = node;
        return (ISC_R_SUCCESS);
    }

    addr = isc_prefix_touchar(prefix);
    node = radix->head;

    while (node->bit < bitlen || node->prefix == NULL) {
        if (node->bit < radix->maxbits &&
            BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
        {
            if (node->r == NULL)
                break;
            node = node->r;
        } else {
            if (node->l == NULL)
                break;
            node = node->l;
        }

        INSIST(node != NULL);
    }

    INSIST(node->prefix != NULL);

    test_addr = isc_prefix_touchar(node->prefix);
    /* Find the first bit different. */
    check_bit = (node->bit < bitlen) ? node->bit : bitlen;
    differ_bit = 0;
    for (i = 0; i*8 < check_bit; i++) {
        if ((r = (addr[i] ^ test_addr[i])) == 0) {
            differ_bit = (i + 1) * 8;
            continue;
        }
        /* I know the better way, but for now. */
        for (j = 0; j < 8; j++) {
            if (BIT_TEST (r, (0x80 >> j)))
                break;
        }
        /* Must be found. */
        INSIST(j < 8);
        differ_bit = i * 8 + j;
        break;
    }

    if (differ_bit > check_bit)
        differ_bit = check_bit;

    parent = node->parent;
    while (parent != NULL && parent->bit >= differ_bit) {
        node = parent;
        parent = node->parent;
    }

    if (differ_bit == bitlen && node->bit == bitlen) {
        if (node->prefix != NULL) {
            /* Set node_num only if it hasn't been set before */
            if (source != NULL) {
                /* Merging node */
                if (node->node_num[0] == -1 &&
                    source->node_num[0] != -1) {
                    node->node_num[0] =
                        radix->num_added_node +
                        source->node_num[0];
                    node->data[0] = source->data[0];
                }
                if (node->node_num[1] == -1 &&
                    source->node_num[0] != -1) {
                    node->node_num[1] =
                        radix->num_added_node +
                        source->node_num[1];
                    node->data[1] = source->data[1];
                }
            } else {
                if (fam == AF_UNSPEC) {
                    /* "any" or "none" */
                    int next = radix->num_added_node + 1;
                    if (node->node_num[0] == -1) {
                        node->node_num[0] = next;
                        radix->num_added_node = next;
                    }
                    if (node->node_num[1] == -1) {
                        node->node_num[1] = next;
                        radix->num_added_node = next;
                    }
                } else {
                    if (node->node_num[ISC_IS6(fam)] == -1)
                        node->node_num[ISC_IS6(fam)]
                           = ++radix->num_added_node;
                }
            }
            *target = node;
            return (ISC_R_SUCCESS);
        } else {
            result =
                _ref_prefix(radix->mctx, &node->prefix, prefix);
            if (result != ISC_R_SUCCESS)
                return (result);
        }
        INSIST(node->data[0] == NULL && node->node_num[0] == -1 &&
               node->data[1] == NULL && node->node_num[1] == -1);
        if (source != NULL) {
            /* Merging node */
            if (source->node_num[0] != -1) {
                node->node_num[0] = radix->num_added_node +
                            source->node_num[0];
                node->data[0] = source->data[0];
            }
            if (source->node_num[1] != -1) {
                node->node_num[1] = radix->num_added_node +
                            source->node_num[1];
                node->data[1] = source->data[1];
            }
        } else {
            if (fam == AF_UNSPEC) {
                /* "any" or "none" */
                node->node_num[0] = node->node_num[1] =
                    ++radix->num_added_node;
            } else {
                node->node_num[ISC_IS6(fam)] =
                    ++radix->num_added_node;
            }
        }
        *target = node;
        return (ISC_R_SUCCESS);
    }

    new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
    if (new_node == NULL)
        return (ISC_R_NOMEMORY);
    if (node->bit != differ_bit && bitlen != differ_bit) {
        glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
        if (glue == NULL) {
            isc_mem_put(radix->mctx, new_node,
                    sizeof(isc_radix_node_t));
            return (ISC_R_NOMEMORY);
        }
    }
    new_node->bit = bitlen;
    new_node->prefix = NULL;
    result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
    if (result != ISC_R_SUCCESS) {
        isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
        if (glue != NULL)
            isc_mem_put(radix->mctx, glue,
                    sizeof(isc_radix_node_t));
        return (result);
    }
    new_node->parent = NULL;
    new_node->l = new_node->r = NULL;
    new_node->node_num[0] = new_node->node_num[1] = -1;
    radix->num_active_node++;

    if (source != NULL) {
        /* Merging node */
        if (source->node_num[0] != -1)
            new_node->node_num[0] = radix->num_added_node +
                        source->node_num[0];
        if (source->node_num[1] != -1)
            new_node->node_num[1] = radix->num_added_node +
                        source->node_num[1];
        new_node->data[0] = source->data[0];
        new_node->data[1] = source->data[1];
    } else {
        if (fam == AF_UNSPEC) {
            /* "any" or "none" */
            new_node->node_num[0] = new_node->node_num[1] =
                ++radix->num_added_node;
        } else {
            new_node->node_num[ISC_IS6(fam)] =
                ++radix->num_added_node;
        }
        new_node->data[0] = NULL;
        new_node->data[1] = NULL;
    }

    if (node->bit == differ_bit) {
        INSIST(glue == NULL);
        new_node->parent = node;
        if (node->bit < radix->maxbits &&
            BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
        {
            INSIST(node->r == NULL);
            node->r = new_node;
        } else {
            INSIST(node->l == NULL);
            node->l = new_node;
        }
        *target = new_node;
        return (ISC_R_SUCCESS);
    }

    if (bitlen == differ_bit) {
        INSIST(glue == NULL);
        if (bitlen < radix->maxbits &&
            BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
            new_node->r = node;
        } else {
            new_node->l = node;
        }
        new_node->parent = node->parent;
        if (node->parent == NULL) {
            INSIST(radix->head == node);
            radix->head = new_node;
        } else if (node->parent->r == node) {
            node->parent->r = new_node;
        } else {
            node->parent->l = new_node;
        }
        node->parent = new_node;
    } else {
        INSIST(glue != NULL);
        glue->bit = differ_bit;
        glue->prefix = NULL;
        glue->parent = node->parent;
        glue->data[0] = glue->data[1] = NULL;
        glue->node_num[0] = glue->node_num[1] = -1;
        radix->num_active_node++;
        if (differ_bit < radix->maxbits &&
            BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) {
            glue->r = new_node;
            glue->l = node;
        } else {
            glue->r = node;
            glue->l = new_node;
        }
        new_node->parent = glue;

        if (node->parent == NULL) {
            INSIST(radix->head == node);
            radix->head = glue;
        } else if (node->parent->r == node) {
            node->parent->r = glue;
        } else {
            node->parent->l = glue;
        }
        node->parent = glue;
    }

    *target = new_node;
    return (ISC_R_SUCCESS);
}

void
isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
    isc_radix_node_t *parent, *child;

    REQUIRE(radix != NULL);
    REQUIRE(node != NULL);

    if (node->r && node->l) {
        /*
         * This might be a placeholder node -- have to check and
         * make sure there is a prefix associated with it!
         */
        if (node->prefix != NULL)
            _deref_prefix(radix->mctx, node->prefix);

        node->prefix = NULL;
        node->data[0] = node->data[1] = NULL;
        return;
    }

    if (node->r == NULL && node->l == NULL) {
        parent = node->parent;
        _deref_prefix(radix->mctx, node->prefix);
        isc_mem_put(radix->mctx, node, sizeof(*node));
        radix->num_active_node--;

        if (parent == NULL) {
            INSIST(radix->head == node);
            radix->head = NULL;
            return;
        }

        if (parent->r == node) {
            parent->r = NULL;
            child = parent->l;
        } else {
            INSIST(parent->l == node);
            parent->l = NULL;
            child = parent->r;
        }

        if (parent->prefix)
            return;

        /* We need to remove parent too. */

        if (parent->parent == NULL) {
            INSIST(radix->head == parent);
            radix->head = child;
        } else if (parent->parent->r == parent) {
            parent->parent->r = child;
        } else {
            INSIST(parent->parent->l == parent);
            parent->parent->l = child;
        }
        child->parent = parent->parent;
        isc_mem_put(radix->mctx, parent, sizeof(*parent));
        radix->num_active_node--;
        return;
    }

    if (node->r) {
        child = node->r;
    } else {
        INSIST(node->l != NULL);
        child = node->l;
    }
    parent = node->parent;
    child->parent = parent;

    _deref_prefix(radix->mctx, node->prefix);
    isc_mem_put(radix->mctx, node, sizeof(*node));
    radix->num_active_node--;

    if (parent == NULL) {
        INSIST(radix->head == node);
        radix->head = child;
        return;
    }

    if (parent->r == node) {
        parent->r = child;
    } else {
        INSIST(parent->l == node);
        parent->l = child;
    }
}

/*
Local Variables:
c-basic-offset: 4
indent-tabs-mode: t
End:
*/