radix.c

Go to the documentation of this file.

/*
 * Copyright (C) 2007-2009, 2011-2014  Internet Systems Consortium, Inc. ("ISC")
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

/* $Id$ */

/*
 * This source was adapted from MRT's RCS Ids:
 * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
 * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp
 */

#include <config.h>

#include <isc/mem.h>
#include <isc/types.h>
#include <isc/util.h>
#include <isc/radix.h>

static isc_result_t
_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family,
            void *dest, int bitlen);

static void
_deref_prefix(isc_prefix_t *prefix);

static isc_result_t
_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);

static int
_comp_with_mask(void *addr, void *dest, u_int mask);

static void
_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);

static isc_result_t
_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
            int bitlen)
{
        isc_prefix_t *prefix;

        REQUIRE(target != NULL);

        if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC)
                return (ISC_R_NOTIMPLEMENTED);

        prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
        if (prefix == NULL)
                return (ISC_R_NOMEMORY);

        if (family == AF_INET6) {
                prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
                memmove(&prefix->add.sin6, dest, 16);
        } else {
                /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */
                prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
                memmove(&prefix->add.sin, dest, 4);
        }

        prefix->family = family;
        prefix->ecs = ISC_FALSE;
        prefix->mctx = NULL;
        isc_mem_attach(mctx, &prefix->mctx);

        isc_refcount_init(&prefix->refcount, 1);

        *target = prefix;
        return (ISC_R_SUCCESS);
}

static void
_deref_prefix(isc_prefix_t *prefix) {
        int refs;

        if (prefix == NULL)
                return;

        isc_refcount_decrement(&prefix->refcount, &refs);

        if (refs <= 0) {
                isc_refcount_destroy(&prefix->refcount);
                isc_mem_putanddetach(&prefix->mctx, prefix,
                                     sizeof(isc_prefix_t));
        }
}

static isc_result_t
_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
        INSIST(prefix != NULL);
        INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
               (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
               (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
        REQUIRE(target != NULL && *target == NULL);

        /*
         * If this prefix is a static allocation, copy it into new memory.
         * (Note, the refcount still has to be destroyed by the calling
         * routine.)
         */
        if (isc_refcount_current(&prefix->refcount) == 0) {
                isc_result_t ret;
                ret = _new_prefix(mctx, target, prefix->family,
                                  &prefix->add, prefix->bitlen);
                return (ret);
        }

        isc_refcount_increment(&prefix->refcount, NULL);

        *target = prefix;
        return (ISC_R_SUCCESS);
}

static int
_comp_with_mask(void *addr, void *dest, u_int mask) {

        /* Mask length of zero matches everything */
        if (mask == 0)
                return (1);

        if (memcmp(addr, dest, mask / 8) == 0) {
                int n = mask / 8;
                int m = ((~0) << (8 - (mask % 8)));

                if ((mask % 8) == 0 ||
                    (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
                        return (1);
        }
        return (0);
}

isc_result_t
isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
        isc_radix_tree_t *radix;

        REQUIRE(target != NULL && *target == NULL);

        radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
        if (radix == NULL)
                return (ISC_R_NOMEMORY);

        radix->mctx = NULL;
        isc_mem_attach(mctx, &radix->mctx);
        radix->maxbits = maxbits;
        radix->head = NULL;
        radix->num_active_node = 0;
        radix->num_added_node = 0;
        RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
        radix->magic = RADIX_TREE_MAGIC;
        *target = radix;
        return (ISC_R_SUCCESS);
}

/*
 * if func is supplied, it will be called as func(node->data)
 * before deleting the node
 */

static void
_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {

        REQUIRE(radix != NULL);

        if (radix->head != NULL) {
                isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
                isc_radix_node_t **Xsp = Xstack;
                isc_radix_node_t *Xrn = radix->head;

                while (Xrn != NULL) {
                        isc_radix_node_t *l = Xrn->l;
                        isc_radix_node_t *r = Xrn->r;

                        if (Xrn->prefix != NULL) {
                                _deref_prefix(Xrn->prefix);
                                if (func != NULL)
                                        func(Xrn->data);
                        } else {
                                INSIST(Xrn->data[0] == NULL &&
                                       Xrn->data[1] == NULL &&
                                       Xrn->data[2] == NULL &&
                                       Xrn->data[3] == NULL);
                        }

                        isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
                        radix->num_active_node--;

                        if (l != NULL) {
                                if (r != NULL) {
                                        *Xsp++ = r;
                                }
                                Xrn = l;
                        } else if (r != NULL) {
                                Xrn = r;
                        } else if (Xsp != Xstack) {
                                Xrn = *(--Xsp);
                        } else {
                                Xrn = NULL;
                        }
                }
        }
        RUNTIME_CHECK(radix->num_active_node == 0);
}


void
isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
        REQUIRE(radix != NULL);
        _clear_radix(radix, func);
        isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix));
}


/*
 * func will be called as func(node->prefix, node->data)
 */
void
isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) {
        isc_radix_node_t *node;

        REQUIRE(func != NULL);

        RADIX_WALK(radix->head, node) {
                func(node->prefix, node->data);
        } RADIX_WALK_END;
}


isc_result_t
isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
                 isc_prefix_t *prefix)
{
        isc_radix_node_t *node;
        isc_radix_node_t *stack[RADIX_MAXBITS + 1];
        u_char *addr;
        isc_uint32_t bitlen;
        int toff = -1, cnt = 0;

        REQUIRE(radix != NULL);
        REQUIRE(prefix != NULL);
        REQUIRE(target != NULL && *target == NULL);
        RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);

        *target = NULL;

        if (radix->head == NULL) {
                return (ISC_R_NOTFOUND);
        }

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

        while (node->bit < bitlen) {
                if (node->prefix)
                        stack[cnt++] = node;

                if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
                        node = node->r;
                else
                        node = node->l;

                if (node == NULL)
                        break;
        }

        if (node && node->prefix)
                stack[cnt++] = node;

        while (cnt-- > 0) {
                node = stack[cnt];

                if (prefix->bitlen < node->bit)
                        continue;

                if (_comp_with_mask(isc_prefix_tochar(node->prefix),
                                    isc_prefix_tochar(prefix),
                                    node->prefix->bitlen))
                {
                        int off = ISC_RADIX_OFF(prefix);
                        if (node->node_num[off] != -1 &&
                            ((*target == NULL) ||
                             (*target)->node_num[toff] > node->node_num[off]))
                        {
                                *target = node;
                                toff = off;
                        }
                }
        }

        if (*target == NULL) {
                return (ISC_R_NOTFOUND);
        } else {
                return (ISC_R_SUCCESS);
        }
}

isc_result_t
isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
                 isc_radix_node_t *source, isc_prefix_t *prefix)
{
        isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
        u_char *addr, *test_addr;
        isc_uint32_t bitlen, fam, check_bit, differ_bit;
        isc_uint32_t i, j, r;
        isc_result_t result;

        REQUIRE(radix != NULL);
        REQUIRE(target != NULL && *target == NULL);
        REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
        RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);

        if (prefix == NULL)
                prefix = source->prefix;

        INSIST(prefix != NULL);

        bitlen = prefix->bitlen;
        fam = prefix->family;

        if (radix->head == NULL) {
                node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
                if (node == NULL)
                        return (ISC_R_NOMEMORY);
                node->bit = bitlen;
                for (i = 0; i < 4; i++)
                        node->node_num[i] = -1;
                node->prefix = NULL;
                result = _ref_prefix(radix->mctx, &node->prefix, prefix);
                if (result != ISC_R_SUCCESS) {
                        isc_mem_put(radix->mctx, node,
                                    sizeof(isc_radix_node_t));
                        return (result);
                }
                node->parent = NULL;
                node->l = node->r = NULL;
                if (source != NULL) {
                        /*
                         * If source is non-NULL, then we're merging in a
                         * node from an existing radix tree.  To keep
                         * the node_num values consistent, the calling
                         * function will add the total number of nodes
                         * added to num_added_node at the end of
                         * the merge operation--we don't do it here.
                         */
                        for (i = 0; i < 4; i++) {
                                if (source->node_num[i] != -1)
                                        node->node_num[i] =
                                                radix->num_added_node +
                                                source->node_num[i];
                                node->data[i] = source->data[i];
                        }
                } else {
                        int next = ++radix->num_added_node;
                        if (fam == AF_UNSPEC) {
                                /* "any" or "none" */
                                for (i = 0; i < 4; i++)
                                        node->node_num[i] = next;
                        } else {
                                node->node_num[ISC_RADIX_OFF(prefix)] = next;
                        }

                        memset(node->data, 0, sizeof(node->data));
                }
                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 nodes */
                                for (i = 0; i < 4; i++) {
                                        if (node->node_num[i] == -1 &&
                                            source->node_num[i] != -1) {
                                                node->node_num[i] =
                                                        radix->num_added_node +
                                                        source->node_num[i];
                                                node->data[i] = source->data[i];
                                        }
                                }
                        } else {
                                if (fam == AF_UNSPEC) {
                                        /* "any" or "none" */
                                        int next = radix->num_added_node + 1;
                                        for (i = 0; i < 4; i++)  {
                                                if (node->node_num[i] == -1) {
                                                        node->node_num[i] =
                                                                next;
                                                        radix->num_added_node =
                                                                next;
                                                }
                                        }
                                } else {
                                        int off = ISC_RADIX_OFF(prefix);
                                        if (node->node_num[off] == -1)
                                                node->node_num[off] =
                                                        ++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 &&
                       node->data[2] == NULL && node->node_num[2] == -1 &&
                       node->data[3] == NULL && node->node_num[3] == -1);
                if (source != NULL) {
                        /* Merging node */
                        for (i = 0; i < 4; i++) {
                                int cur = radix->num_added_node;
                                if (source->node_num[i] != -1) {
                                        node->node_num[i] =
                                                source->node_num[i] + cur;
                                        node->data[i] = source->data[i];
                                }
                        }
                } else {
                        int next = ++radix->num_added_node;
                        if (fam == AF_UNSPEC) {
                                /* "any" or "none" */
                                for (i = 0; i < 4; i++)
                                        node->node_num[i] = next;
                        } else {
                                node->node_num[ISC_RADIX_OFF(prefix)] = next;
                        }
                }
                *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;
        for (i = 0; i < 4; i++)
                new_node->node_num[i] = -1;
        radix->num_active_node++;

        if (source != NULL) {
                /* Merging node */
                for (i = 0; i < 4; i++) {
                        int cur = radix->num_added_node;
                        if (source->node_num[i] != -1) {
                                new_node->node_num[i] =
                                        source->node_num[i] + cur;
                                new_node->data[i] = source->data[i];
                        }
                }
        } else {
                int next = ++radix->num_added_node;
                if (fam == AF_UNSPEC) {
                        /* "any" or "none" */
                        for (i = 0; i < 4; i++)
                                new_node->node_num[i] = next;
                } else {
                        new_node->node_num[ISC_RADIX_OFF(prefix)] = next;
                }
                memset(new_node->data, 0, sizeof(new_node->data));
        }

        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;
                for (i = 0; i < 4; i++) {
                        glue->data[i] = NULL;
                        glue->node_num[i] = -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(node->prefix);

                node->prefix = NULL;
                memset(node->data, 0, sizeof(node->data));
                return;
        }

        if (node->r == NULL && node->l == NULL) {
                parent = node->parent;
                _deref_prefix(node->prefix);

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

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

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

                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(node->prefix);

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

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

        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:
*/

---