summaryrefslogtreecommitdiffstats
path: root/src/cmake/library.cmake
blob: ad4adfcabc4f034ab8f8f7584d5b68632ef5b9ad (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
# Copyright (c) 2018 Cisco and/or its affiliates.
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at:
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

macro(add_vpp_library lib)
  cmake_parse_arguments(ARG
    "LTO"
    "COMPONENT"
    "SOURCES;MULTIARCH_SOURCES;API_FILES;LINK_LIBRARIES;INSTALL_HEADERS;DEPENDS"
    ${ARGN}
  )

  set (lo ${lib}_objs)
  add_library(${lo} OBJECT ${ARG_SOURCES})
  set_target_properties(${lo} PROPERTIES POSITION_INDEPENDENT_CODE ON)
  target_compile_options(${lo} PUBLIC ${VPP_DEFAULT_MARCH_FLAGS})

  add_library(${lib} SHARED)
  target_sources(${lib} PRIVATE $<TARGET_OBJECTS:${lo}>)

  if(VPP_LIB_VERSION)
    set_target_properties(${lib} PROPERTIES SOVERSION ${VPP_LIB_VERSION})
  endif()

  # library deps
  if(ARG_LINK_LIBRARIES)
    target_link_libraries(${lib} ${ARG_LINK_LIBRARIES})
  endif()
  # install .so
  if(NOT ARG_COMPONENT)
    set(ARG_COMPONENT vpp)
  endif()
  install(
    TARGETS ${lib}
    DESTINATION ${VPP_LIBRARY_DIR}
    COMPONENT ${ARG_COMPONENT}
  )

  if (ARG_LTO AND VPP_USE_LTO)
     set_property(TARGET ${lo} PROPERTY INTERPROCEDURAL_OPTIMIZATION TRUE)
     set_property(TARGET ${lib} PROPERTY INTERPROCEDURAL_OPTIMIZATION TRUE)
     target_compile_options (${lib} PRIVATE "-ffunction-sections")
     target_compile_options (${lib} PRIVATE "-fdata-sections")
     target_link_libraries (${lib} "-Wl,--gc-sections")
     if(compiler_flag_no_stringop_overflow)
       target_link_libraries (${lib} "-Wno-stringop-overflow")
     endif()
  endif()

  if(ARG_MULTIARCH_SOURCES)
    vpp_library_set_multiarch_sources(${lib} DEPENDS ${ARG_DEPENDS} SOURCES ${ARG_MULTIARCH_SOURCES})
  endif()

  if(ARG_API_FILES)
    vpp_add_api_files(${lib} core vpp ${ARG_API_FILES})
    foreach(file ${ARG_API_FILES})
      get_filename_component(dir ${file} DIRECTORY)
      install(
	FILES ${file} ${CMAKE_CURRENT_BINARY_DIR}/${file}.h
	${CMAKE_CURRENT_BINARY_DIR}/${file}_enum.h
	${CMAKE_CURRENT_BINARY_DIR}/${file}_types.h
	${CMAKE_CURRENT_BINARY_DIR}/${file}_tojson.h
	${CMAKE_CURRENT_BINARY_DIR}/${file}_fromjson.h
	DESTINATION include/${lib}/${dir}
	COMPONENT vpp-dev
      )
    endforeach()
  endif()

  if(NOT VPP_EXTERNAL_PROJECT)
    add_dependencies(${lo} api_headers)
  endif()

  if(VPP_EXTERNAL_PROJECT AND ARG_API_FILES)
    add_dependencies(${lo} ${lib}_api_headers)
  endif()

  if(ARG_DEPENDS)
    add_dependencies(${lo} ${ARG_DEPENDS})
  endif()

  # install headers
  if(ARG_INSTALL_HEADERS)
    foreach(file ${ARG_INSTALL_HEADERS})
      get_filename_component(dir ${file} DIRECTORY)
      install(
	FILES ${file}
	DESTINATION include/${lib}/${dir}
	COMPONENT ${ARG_COMPONENT}-dev
      )
    endforeach()
  endif()
endmacro()

##############################################################################
# header files
##############################################################################
function (add_vpp_headers path)
  foreach(file ${ARGN})
    get_filename_component(dir ${file} DIRECTORY)
    install(
      FILES ${file}
      DESTINATION include/${path}/${dir}
      COMPONENT vpp-dev
    )
  endforeach()
endfunction()

macro(add_vat_test_library lib)
  cmake_parse_arguments(TEST
    ""
    ""
    ${ARGN}
  )

  foreach(file ${ARGN})
    get_filename_component(name ${file} NAME_WE)
    set(test_lib ${lib}_${name}_plugin)
    add_library(${test_lib} SHARED ${file})
    target_compile_options(${test_lib} PUBLIC ${VPP_DEFAULT_MARCH_FLAGS})
    if(NOT VPP_EXTERNAL_PROJECT)
      add_dependencies(${test_lib} api_headers)
    endif()
    include_directories(${CMAKE_CURRENT_BINARY_DIR})
    set_target_properties(${test_lib} PROPERTIES NO_SONAME 1)
    set_target_properties(${test_lib} PROPERTIES
      PREFIX ""
      LIBRARY_OUTPUT_DIRECTORY ${CMAKE_LIBRARY_OUTPUT_DIRECTORY}/vpp_api_test_plugins)

    # install .so
    install(
      TARGETS ${test_lib}
      DESTINATION ${VPP_LIBRARY_DIR}/vpp_api_test_plugins
      COMPONENT ${ARG_COMPONENT}
    )
  endforeach()
endmacro()

macro(add_vpp_test_library lib)
  cmake_parse_arguments(TEST
    ""
    ""
    ${ARGN}
  )

  foreach(file ${ARGN})
    get_filename_component(name ${file} NAME_WE)
    set(test_lib ${lib}_${name}_plugin)
    add_library(${test_lib} SHARED ${file}_test2.c)
    target_compile_options(${test_lib} PUBLIC ${VPP_DEFAULT_MARCH_FLAGS})
    if(NOT VPP_EXTERNAL_PROJECT)
      add_dependencies(${test_lib} api_headers)
    endif()
    include_directories(${CMAKE_CURRENT_BINARY_DIR})
    set_target_properties(${test_lib} PROPERTIES NO_SONAME 1)
    set_target_properties(${test_lib} PROPERTIES
      PREFIX ""
      LIBRARY_OUTPUT_DIRECTORY ${CMAKE_LIBRARY_OUTPUT_DIRECTORY}/vat2_plugins)

    # install .so
    install(
      TARGETS ${test_lib}
      DESTINATION ${VPP_LIBRARY_DIR}/vat2_plugins
      COMPONENT ${ARG_COMPONENT}
    )
  endforeach()
endmacro()

macro(vpp_find_library var)
  find_library(${var} ${ARGN})
  mark_as_advanced(${var})
endmacro()
macro(vpp_find_path var)
  find_path(${var} ${ARGN})
  mark_as_advanced(${var})
endmacro()
72 } /* Keyword.Namespace */ .highlight .kp { color: #66d9ef } /* Keyword.Pseudo */ .highlight .kr { color: #66d9ef } /* Keyword.Reserved */ .highlight .kt { color: #66d9ef } /* Keyword.Type */ .highlight .ld { color: #e6db74 } /* Literal.Date */ .highlight .m { color: #ae81ff } /* Literal.Number */ .highlight .s { color: #e6db74 } /* Literal.String */ .highlight .na { color: #a6e22e } /* Name.Attribute */ .highlight .nb { color: #f8f8f2 } /* Name.Builtin */ .highlight .nc { color: #a6e22e } /* Name.Class */ .highlight .no { color: #66d9ef } /* Name.Constant */ .highlight .nd { color: #a6e22e } /* Name.Decorator */ .highlight .ni { color: #f8f8f2 } /* Name.Entity */ .highlight .ne { color: #a6e22e } /* Name.Exception */ .highlight .nf { color: #a6e22e } /* Name.Function */ .highlight .nl { color: #f8f8f2 } /* Name.Label */ .highlight .nn { color: #f8f8f2 } /* Name.Namespace */ .highlight .nx { color: #a6e22e } /* Name.Other */ .highlight .py { color: #f8f8f2 } /* Name.Property */ .highlight .nt { color: #f92672 } /* Name.Tag */ .highlight .nv { color: #f8f8f2 } /* Name.Variable */ .highlight .ow { color: #f92672 } /* Operator.Word */ .highlight .w { color: #f8f8f2 } /* Text.Whitespace */ .highlight .mb { color: #ae81ff } /* Literal.Number.Bin */ .highlight .mf { color: #ae81ff } /* Literal.Number.Float */ .highlight .mh { color: #ae81ff } /* Literal.Number.Hex */ .highlight .mi { color: #ae81ff } /* Literal.Number.Integer */ .highlight .mo { color: #ae81ff } /* Literal.Number.Oct */ .highlight .sa { color: #e6db74 } /* Literal.String.Affix */ .highlight .sb { color: #e6db74 } /* Literal.String.Backtick */ .highlight .sc { color: #e6db74 } /* Literal.String.Char */ .highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */ .highlight .sd { color: #e6db74 } /* Literal.String.Doc */ .highlight .s2 { color: #e6db74 } /* Literal.String.Double */ .highlight .se { color: #ae81ff } /* Literal.String.Escape */ .highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */ .highlight .si { color: #e6db74 } /* Literal.String.Interpol */ .highlight .sx { color: #e6db74 } /* Literal.String.Other */ .highlight .sr { color: #e6db74 } /* Literal.String.Regex */ .highlight .s1 { color: #e6db74 } /* Literal.String.Single */ .highlight .ss { color: #e6db74 } /* Literal.String.Symbol */ .highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #a6e22e } /* Name.Function.Magic */ .highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */ .highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */ .highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */ .highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */ .highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */ } @media (prefers-color-scheme: light) { .highlight .hll { background-color: #ffffcc } .highlight .c { color: #888888 } /* Comment */ .highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */ .highlight .k { color: #008800; font-weight: bold } /* Keyword */ .highlight .ch { color: #888888 } /* Comment.Hashbang */ .highlight .cm { color: #888888 } /* Comment.Multiline */ .highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */ .highlight .cpf { color: #888888 } /* Comment.PreprocFile */ .highlight .c1 { color: #888888 } /* Comment.Single */ .highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */ .highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */ .highlight .ge { font-style: italic } /* Generic.Emph */ .highlight .gr { color: #aa0000 } /* Generic.Error */ .highlight .gh { color: #333333 } /* Generic.Heading */ .highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */ .highlight .go { color: #888888 } /* Generic.Output */ .highlight .gp { color: #555555 } /* Generic.Prompt */ .highlight .gs { font-weight: bold } /* Generic.Strong */ .highlight .gu { color: #666666 } /* Generic.Subheading */ .highlight .gt { color: #aa0000 } /* Generic.Traceback */ .highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */ .highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */ .highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */ .highlight .kp { color: #008800 } /* Keyword.Pseudo */ .highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */ .highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */ .highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */ .highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */ .highlight .na { color: #336699 } /* Name.Attribute */ .highlight .nb { color: #003388 } /* Name.Builtin */ .highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */ .highlight .no { color: #003366; font-weight: bold } /* Name.Constant */ .highlight .nd { color: #555555 } /* Name.Decorator */ .highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */ .highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */ .highlight .nl { color: #336699; font-style: italic } /* Name.Label */ .highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */ .highlight .py { color: #336699; font-weight: bold } /* Name.Property */ .highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */ .highlight .nv { color: #336699 } /* Name.Variable */ .highlight .ow { color: #008800 } /* Operator.Word */ .highlight .w { color: #bbbbbb } /* Text.Whitespace */ .highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */ .highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */ .highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */ .highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */ .highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */ .highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */ .highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */ .highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */ .highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */ .highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */ .highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */ .highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */ .highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */ .highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */ .highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */ .highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */ .highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */ .highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */ .highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */ .highlight .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */ }
/*	$NetBSD: radix.c,v 1.47 2016/12/12 03:55:57 ozaki-r Exp $	*/

/*
 * Copyright (c) 1988, 1989, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)radix.c	8.6 (Berkeley) 10/17/95
 */

/*
 * Routines to build and maintain radix trees for routing lookups.
 */

#include <vnet/util/radix.h>

typedef void (*rn_printer_t)(void *, const char *fmt, ...);

static int max_keylen = 33; // me
struct radix_mask *rn_mkfreelist;
struct radix_node_head *mask_rnhead;
static char *addmask_key;
static const char normal_chars[] =
    {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1};
static char *rn_zeros, *rn_ones;

#define rn_masktop (mask_rnhead->rnh_treetop)

static int rn_satisfies_leaf(const char *, struct radix_node *, int);
static int rn_lexobetter(const void *, const void *);
static struct radix_mask *rn_new_radix_mask(struct radix_node *,
    struct radix_mask *);
static struct radix_node *rn_walknext(struct radix_node *, rn_printer_t,
    void *);
static struct radix_node *rn_walkfirst(struct radix_node *, rn_printer_t,
    void *);
static void rn_nodeprint(struct radix_node *, rn_printer_t, void *,
    const char *);

#define	SUBTREE_OPEN	"[ "
#define	SUBTREE_CLOSE	" ]"

#ifdef RN_DEBUG
static void rn_treeprint(struct radix_node_head *, rn_printer_t, void *);
#endif /* RN_DEBUG */

#define MIN(x,y) (((x)<(y))?(x):(y))

static struct radix_mask*
rm_alloc (void)
{
    struct radix_mask *rm = clib_mem_alloc(sizeof(struct radix_mask));

    clib_memset(rm, 0, sizeof(*rm));

    return (rm);
}

static void
rm_free (struct radix_mask *rm)
{
    clib_mem_free(rm);
}

#define R_Malloc(p, t, n)                               \
{                                                       \
    p = (t) clib_mem_alloc((unsigned int)(n));          \
    clib_memset(p, 0, n);                                    \
}
#define Free(p) clib_mem_free((p))
#define log(a,b, c...)
#define bool i32

/*
 * The data structure for the keys is a radix tree with one way
 * branching removed.  The index rn_b at an internal node n represents a bit
 * position to be tested.  The tree is arranged so that all descendants
 * of a node n have keys whose bits all agree up to position rn_b - 1.
 * (We say the index of n is rn_b.)
 *
 * There is at least one descendant which has a one bit at position rn_b,
 * and at least one with a zero there.
 *
 * A route is determined by a pair of key and mask.  We require that the
 * bit-wise logical and of the key and mask to be the key.
 * We define the index of a route to associated with the mask to be
 * the first bit number in the mask where 0 occurs (with bit number 0
 * representing the highest order bit).
 *
 * We say a mask is normal if every bit is 0, past the index of the mask.
 * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b,
 * and m is a normal mask, then the route applies to every descendant of n.
 * If the index(m) < rn_b, this implies the trailing last few bits of k
 * before bit b are all 0, (and hence consequently true of every descendant
 * of n), so the route applies to all descendants of the node as well.
 *
 * Similar logic shows that a non-normal mask m such that
 * index(m) <= index(n) could potentially apply to many children of n.
 * Thus, for each non-host route, we attach its mask to a list at an internal
 * node as high in the tree as we can go.
 *
 * The present version of the code makes use of normal routes in short-
 * circuiting an explicit mask and compare operation when testing whether
 * a key satisfies a normal route, and also in remembering the unique leaf
 * that governs a subtree.
 */

struct radix_node *
rn_search(
	const void *v_arg,
	struct radix_node *head)
{
	const u8 * const v = v_arg;
	struct radix_node *x;

	for (x = head; x->rn_b >= 0;) {
		if (x->rn_bmask & v[x->rn_off])
			x = x->rn_r;
		else
			x = x->rn_l;
	}
	return x;
}

struct radix_node *
rn_search_m(
	const void *v_arg,
	struct radix_node *head,
	const void *m_arg)
{
	struct radix_node *x;
	const u8 * const v = v_arg;
	const u8 * const m = m_arg;

	for (x = head; x->rn_b >= 0;) {
		if ((x->rn_bmask & m[x->rn_off]) &&
		    (x->rn_bmask & v[x->rn_off]))
			x = x->rn_r;
		else
			x = x->rn_l;
	}
	return x;
}

int
rn_refines(
	const void *m_arg,
	const void *n_arg)
{
	const char *m = m_arg;
	const char *n = n_arg;
	const char *lim = n + *(const u8 *)n;
	const char *lim2 = lim;
	int longer = (*(const u8 *)n++) - (int)(*(const u8 *)m++);
	int masks_are_equal = 1;

	if (longer > 0)
		lim -= longer;
	while (n < lim) {
		if (*n & ~(*m))
			return 0;
		if (*n++ != *m++)
			masks_are_equal = 0;
	}
	while (n < lim2)
		if (*n++)
			return 0;
	if (masks_are_equal && (longer < 0))
		for (lim2 = m - longer; m < lim2; )
			if (*m++)
				return 1;
	return !masks_are_equal;
}

struct radix_node *
rn_lookup(
	const void *v_arg,
	const void *m_arg,
	struct radix_node_head *head)
{
	struct radix_node *x;
	const char *netmask = NULL;

	if (m_arg) {
		if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0)
			return NULL;
		netmask = x->rn_key;
	}
	x = rn_match(v_arg, head);
	if (x != NULL && netmask != NULL) {
		while (x != NULL && x->rn_mask != netmask)
			x = x->rn_dupedkey;
	}
	return x;
}

static int
rn_satisfies_leaf(
	const char *trial,
	struct radix_node *leaf,
	int skip)
{
	const char *cp = trial;
	const char *cp2 = leaf->rn_key;
	const char *cp3 = leaf->rn_mask;
	const char *cplim;
	int length = MIN(*(const u8 *)cp, *(const u8 *)cp2);

	if (cp3 == 0)
		cp3 = rn_ones;
	else
		length = MIN(length, *(const u8 *)cp3);
	cplim = cp + length; cp3 += skip; cp2 += skip;
	for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
		if ((*cp ^ *cp2) & *cp3)
			return 0;
	return 1;
}

struct radix_node *
rn_match(
	const void *v_arg,
	struct radix_node_head *head)
{
	const char * const v = v_arg;
	struct radix_node *t = head->rnh_treetop;
	struct radix_node *top = t;
	struct radix_node *x;
	struct radix_node *saved_t;
	const char *cp = v;
	const char *cp2;
	const char *cplim;
	int off = t->rn_off;
	int vlen = *(const u8 *)cp;
	int matched_off;
	int test, b, rn_b;

	/*
	 * Open code rn_search(v, top) to avoid overhead of extra
	 * subroutine call.
	 */
	for (; t->rn_b >= 0; ) {
		if (t->rn_bmask & cp[t->rn_off])
			t = t->rn_r;
		else
			t = t->rn_l;
	}
	/*
	 * See if we match exactly as a host destination
	 * or at least learn how many bits match, for normal mask finesse.
	 *
	 * It doesn't hurt us to limit how many bytes to check
	 * to the length of the mask, since if it matches we had a genuine
	 * match and the leaf we have is the most specific one anyway;
	 * if it didn't match with a shorter length it would fail
	 * with a long one.  This wins big for class B&C netmasks which
	 * are probably the most common case...
	 */
	if (t->rn_mask)
		vlen = *(const u8 *)t->rn_mask;
	cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
	for (; cp < cplim; cp++, cp2++)
		if (*cp != *cp2)
			goto on1;
	/*
	 * This extra grot is in case we are explicitly asked
	 * to look up the default.  Ugh!
	 */
	if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey)
		t = t->rn_dupedkey;
	return t;
on1:
	test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
	for (b = 7; (test >>= 1) > 0;)
		b--;
	matched_off = cp - v;
	b += matched_off << 3;
	rn_b = -1 - b;
	/*
	 * If there is a host route in a duped-key chain, it will be first.
	 */
	if ((saved_t = t)->rn_mask == 0)
		t = t->rn_dupedkey;
	for (; t; t = t->rn_dupedkey)
		/*
		 * Even if we don't match exactly as a host,
		 * we may match if the leaf we wound up at is
		 * a route to a net.
		 */
		if (t->rn_flags & RNF_NORMAL) {
			if (rn_b <= t->rn_b)
				return t;
		} else if (rn_satisfies_leaf(v, t, matched_off))
				return t;
	t = saved_t;
	/* start searching up the tree */
	do {
		struct radix_mask *m;
		t = t->rn_p;
		m = t->rn_mklist;
		if (m) {
			/*
			 * If non-contiguous masks ever become important
			 * we can restore the masking and open coding of
			 * the search and satisfaction test and put the
			 * calculation of "off" back before the "do".
			 */
			do {
				if (m->rm_flags & RNF_NORMAL) {
					if (rn_b <= m->rm_b)
						return m->rm_leaf;
				} else {
					off = MIN(t->rn_off, matched_off);
					x = rn_search_m(v, t, m->rm_mask);
					while (x && x->rn_mask != m->rm_mask)
						x = x->rn_dupedkey;
					if (x && rn_satisfies_leaf(v, x, off))
						return x;
				}
				m = m->rm_mklist;
			} while (m);
		}
	} while (t != top);
	return NULL;
}

static void
rn_nodeprint(struct radix_node *rn, rn_printer_t printer, void *arg,
    const char *delim)
{
	(*printer)(arg, "%s(%s%p: p<%p> l<%p> r<%p>)",
	    delim, ((void *)rn == arg) ? "*" : "", rn, rn->rn_p,
	    rn->rn_l, rn->rn_r);
}

#ifdef RN_DEBUG
int	rn_debug =  1;

static void
rn_dbg_print(void *arg, const char *fmt, ...)
{
	va_list ap;

	va_start(ap, fmt);
	vlog(LOG_DEBUG, fmt, ap);
	va_end(ap);
}

static void
rn_treeprint(struct radix_node_head *h, rn_printer_t printer, void *arg)
{
	struct radix_node *dup, *rn;
	const char *delim;

	if (printer == NULL)
		return;

	rn = rn_walkfirst(h->rnh_treetop, printer, arg);
	for (;;) {
		/* Process leaves */
		delim = "";
		for (dup = rn; dup != NULL; dup = dup->rn_dupedkey) {
			if ((dup->rn_flags & RNF_ROOT) != 0)
				continue;
			rn_nodeprint(dup, printer, arg, delim);
			delim = ", ";
		}
		rn = rn_walknext(rn, printer, arg);
		if (rn->rn_flags & RNF_ROOT)
			return;
	}
	/* NOTREACHED */
}

#define	traverse(__head, __rn)	rn_treeprint((__head), rn_dbg_print, (__rn))
#endif /* RN_DEBUG */

struct radix_node *
rn_newpair(
	const void *v,
	int b,
	struct radix_node nodes[2])
{
	struct radix_node *tt = nodes;
	struct radix_node *t = tt + 1;
	t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7);
	t->rn_l = tt; t->rn_off = b >> 3;
	tt->rn_b = -1; tt->rn_key = v; tt->rn_p = t;
	tt->rn_flags = t->rn_flags = RNF_ACTIVE;
	return t;
}

struct radix_node *
rn_insert(
	const void *v_arg,
	struct radix_node_head *head,
	int *dupentry,
	struct radix_node nodes[2])
{
	struct radix_node *top = head->rnh_treetop;
	struct radix_node *t = rn_search(v_arg, top);
	struct radix_node *tt;
	const char *v = v_arg;
	int head_off = top->rn_off;
	int vlen = *((const u8 *)v);
	const char *cp = v + head_off;
	int b;
    	/*
	 * Find first bit at which v and t->rn_key differ
	 */
    {
	const char *cp2 = t->rn_key + head_off;
	const char *cplim = v + vlen;
	int cmp_res;

	while (cp < cplim)
		if (*cp2++ != *cp++)
			goto on1;
	*dupentry = 1;
	return t;
on1:
	*dupentry = 0;
	cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
	for (b = (cp - v) << 3; cmp_res; b--)
		cmp_res >>= 1;
    }
    {
	struct radix_node *p, *x = top;
	cp = v;
	do {
		p = x;
		if (cp[x->rn_off] & x->rn_bmask)
			x = x->rn_r;
		else x = x->rn_l;
	} while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */
#ifdef RN_DEBUG
	if (rn_debug)
		log(LOG_DEBUG, "%s: Going In:\n", __func__), traverse(head, p);
#endif
	t = rn_newpair(v_arg, b, nodes); tt = t->rn_l;
	if ((cp[p->rn_off] & p->rn_bmask) == 0)
		p->rn_l = t;
	else
		p->rn_r = t;
	x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */
	if ((cp[t->rn_off] & t->rn_bmask) == 0) {
		t->rn_r = x;
	} else {
		t->rn_r = tt; t->rn_l = x;
	}
#ifdef RN_DEBUG
	if (rn_debug) {
		log(LOG_DEBUG, "%s: Coming Out:\n", __func__),
		    traverse(head, p);
	}
#endif /* RN_DEBUG */
    }
	return tt;
}

struct radix_node *
rn_addmask(
	const void *n_arg,
	int search,
	int skip)
{
	const char *netmask = n_arg;
	const char *cp;
	const char *cplim;
	struct radix_node *x;
	struct radix_node *saved_x;
	int b = 0, mlen, j;
	int maskduplicated, m0, isnormal;
	static int last_zeroed = 0;

	if ((mlen = *(const u8 *)netmask) > max_keylen)
		mlen = max_keylen;
	if (skip == 0)
		skip = 1;
	if (mlen <= skip)
		return mask_rnhead->rnh_nodes;
	if (skip > 1)
		memmove(addmask_key + 1, rn_ones + 1, skip - 1);
	if ((m0 = mlen) > skip)
		memmove(addmask_key + skip, netmask + skip, mlen - skip);
	/*
	 * Trim trailing zeroes.
	 */
	for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;)
		cp--;
	mlen = cp - addmask_key;
	if (mlen <= skip) {
		if (m0 >= last_zeroed)
			last_zeroed = mlen;
		return mask_rnhead->rnh_nodes;
	}
	if (m0 < last_zeroed)
		clib_memset(addmask_key + m0, 0, last_zeroed - m0);
	*addmask_key = last_zeroed = mlen;
	x = rn_search(addmask_key, rn_masktop);
	if (memcmp(addmask_key, x->rn_key, mlen) != 0)
		x = 0;
	if (x || search)
		return x;
	R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x));
	if ((saved_x = x) == NULL)
		return NULL;
	clib_memset(x, 0, max_keylen + 2 * sizeof (*x));
	cp = netmask = (void *)(x + 2);
	memmove(x + 2, addmask_key, mlen);
	x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
	if (maskduplicated) {
                log(LOG_ERR, "rn_addmask: mask impossibly already in tree\n");
		Free(saved_x);
		return x;
	}
	/*
	 * Calculate index of mask, and check for normalcy.
	 */
	cplim = netmask + mlen; isnormal = 1;
	for (cp = netmask + skip; (cp < cplim) && *(const u8 *)cp == 0xff;)
		cp++;
	if (cp != cplim) {
		for (j = 0x80; (j & *cp) != 0; j >>= 1)
			b++;
		if (*cp != normal_chars[b] || cp != (cplim - 1))
			isnormal = 0;
	}
	b += (cp - netmask) << 3;
	x->rn_b = -1 - b;
	if (isnormal)
		x->rn_flags |= RNF_NORMAL;
	return x;
}

static int	/* XXX: arbitrary ordering for non-contiguous masks */
rn_lexobetter(
	const void *m_arg,
	const void *n_arg)
{
	const u8 *mp = m_arg;
	const u8 *np = n_arg;
	const u8 *lim;

	if (*mp > *np)
		return 1;  /* not really, but need to check longer one first */
	if (*mp == *np)
		for (lim = mp + *mp; mp < lim;)
			if (*mp++ > *np++)
				return 1;
	return 0;
}

static struct radix_mask *
rn_new_radix_mask(
	struct radix_node *tt,
	struct radix_mask *next)
{
	struct radix_mask *m;

	m = rm_alloc();
	if (m == NULL) {
		log(LOG_ERR, "Mask for route not entered\n");
		return NULL;
	}
	clib_memset(m, 0, sizeof(*m));
	m->rm_b = tt->rn_b;
	m->rm_flags = tt->rn_flags;
	if (tt->rn_flags & RNF_NORMAL)
		m->rm_leaf = tt;
	else
		m->rm_mask = tt->rn_mask;
	m->rm_mklist = next;
	tt->rn_mklist = m;
	return m;
}

struct radix_node *
rn_addroute(
	const void *v_arg,
	const void *n_arg,
	struct radix_node_head *head,
	struct radix_node treenodes[2])
{
	const char *v = v_arg, *netmask = n_arg;
	struct radix_node *t, *x = NULL, *tt;
	struct radix_node *saved_tt, *top = head->rnh_treetop;
	short b = 0, b_leaf = 0;
	int keyduplicated;
	const char *mmask;
	struct radix_mask *m, **mp;

	/*
	 * In dealing with non-contiguous masks, there may be
	 * many different routes which have the same mask.
	 * We will find it useful to have a unique pointer to
	 * the mask to speed avoiding duplicate references at
	 * nodes and possibly save time in calculating indices.
	 */
	if (netmask != NULL) {
		if ((x = rn_addmask(netmask, 0, top->rn_off)) == NULL)
			return NULL;
		b_leaf = x->rn_b;
		b = -1 - x->rn_b;
		netmask = x->rn_key;
	}
	/*
	 * Deal with duplicated keys: attach node to previous instance
	 */
	saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
	if (keyduplicated) {
		for (t = tt; tt != NULL; t = tt, tt = tt->rn_dupedkey) {
			if (tt->rn_mask == netmask)
				return NULL;
			if (netmask == NULL ||
			    (tt->rn_mask != NULL &&
			     (b_leaf < tt->rn_b || /* index(netmask) > node */
			       rn_refines(netmask, tt->rn_mask) ||
			       rn_lexobetter(netmask, tt->rn_mask))))
				break;
		}
		/*
		 * If the mask is not duplicated, we wouldn't
		 * find it among possible duplicate key entries
		 * anyway, so the above test doesn't hurt.
		 *
		 * We sort the masks for a duplicated key the same way as
		 * in a masklist -- most specific to least specific.
		 * This may require the unfortunate nuisance of relocating
		 * the head of the list.
		 *
		 * We also reverse, or doubly link the list through the
		 * parent pointer.
		 */
		if (tt == saved_tt) {
			struct	radix_node *xx = x;
			/* link in at head of list */
			(tt = treenodes)->rn_dupedkey = t;
			tt->rn_flags = t->rn_flags;
			tt->rn_p = x = t->rn_p;
			t->rn_p = tt;
			if (x->rn_l == t)
				x->rn_l = tt;
			else
				x->rn_r = tt;
			saved_tt = tt;
			x = xx;
		} else {
			(tt = treenodes)->rn_dupedkey = t->rn_dupedkey;
			t->rn_dupedkey = tt;
			tt->rn_p = t;
			if (tt->rn_dupedkey)
				tt->rn_dupedkey->rn_p = tt;
		}
		tt->rn_key = v;
		tt->rn_b = -1;
		tt->rn_flags = RNF_ACTIVE;
	}
	/*
	 * Put mask in tree.
	 */
	if (netmask != NULL) {
		tt->rn_mask = netmask;
		tt->rn_b = x->rn_b;
		tt->rn_flags |= x->rn_flags & RNF_NORMAL;
	}
	t = saved_tt->rn_p;
	if (keyduplicated)
		goto on2;
	b_leaf = -1 - t->rn_b;
	if (t->rn_r == saved_tt)
		x = t->rn_l;
	else
		x = t->rn_r;
	/* Promote general routes from below */
	if (x->rn_b < 0) {
		for (mp = &t->rn_mklist; x != NULL; x = x->rn_dupedkey) {
			if (x->rn_mask != NULL && x->rn_b >= b_leaf &&
			    x->rn_mklist == NULL) {
				*mp = m = rn_new_radix_mask(x, NULL);
				if (m != NULL)
					mp = &m->rm_mklist;
			}
		}
	} else if (x->rn_mklist != NULL) {
		/*
		 * Skip over masks whose index is > that of new node
		 */
		for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist)
			if (m->rm_b >= b_leaf)
				break;
		t->rn_mklist = m;
		*mp = NULL;
	}
on2:
	/* Add new route to highest possible ancestor's list */
	if (netmask == NULL || b > t->rn_b)
		return tt; /* can't lift at all */
	b_leaf = tt->rn_b;
	do {
		x = t;
		t = t->rn_p;
	} while (b <= t->rn_b && x != top);
	/*
	 * Search through routes associated with node to
	 * insert new route according to index.
	 * Need same criteria as when sorting dupedkeys to avoid
	 * double loop on deletion.
	 */
	for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) {
		if (m->rm_b < b_leaf)
			continue;
		if (m->rm_b > b_leaf)
			break;
		if (m->rm_flags & RNF_NORMAL) {
			mmask = m->rm_leaf->rn_mask;
			if (tt->rn_flags & RNF_NORMAL) {
				log(LOG_ERR, "Non-unique normal route,"
				    " mask not entered\n");
				return tt;
			}
		} else
			mmask = m->rm_mask;
		if (mmask == netmask) {
			m->rm_refs++;
			tt->rn_mklist = m;
			return tt;
		}
		if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask))
			break;
	}
	*mp = rn_new_radix_mask(tt, *mp);
	return tt;
}

struct radix_node *
rn_delete1(
	const void *v_arg,
	const void *netmask_arg,
	struct radix_node_head *head,
	struct radix_node *rn)
{
	struct radix_node *t, *p, *x, *tt;
	struct radix_mask *m, *saved_m, **mp;
	struct radix_node *dupedkey, *saved_tt, *top;
	const char *v, *netmask;
	int b, head_off, vlen;

	v = v_arg;
	netmask = netmask_arg;
	x = head->rnh_treetop;
	tt = rn_search(v, x);
	head_off = x->rn_off;
	vlen =  *(const u8 *)v;
	saved_tt = tt;
	top = x;
	if (tt == NULL ||
	    memcmp(v + head_off, tt->rn_key + head_off, vlen - head_off) != 0)
		return NULL;
	/*
	 * Delete our route from mask lists.
	 */
	if (netmask != NULL) {
		if ((x = rn_addmask(netmask, 1, head_off)) == NULL)
			return NULL;
		netmask = x->rn_key;
		while (tt->rn_mask != netmask)
			if ((tt = tt->rn_dupedkey) == NULL)
				return NULL;
	}
	if (tt->rn_mask == NULL || (saved_m = m = tt->rn_mklist) == NULL)
		goto on1;
	if (tt->rn_flags & RNF_NORMAL) {
		if (m->rm_leaf != tt || m->rm_refs > 0) {
			log(LOG_ERR, "rn_delete: inconsistent annotation\n");
			return NULL;  /* dangling ref could cause disaster */
		}
	} else {
		if (m->rm_mask != tt->rn_mask) {
			log(LOG_ERR, "rn_delete: inconsistent annotation\n");
			goto on1;
		}
		if (--m->rm_refs >= 0)
			goto on1;
	}
	b = -1 - tt->rn_b;
	t = saved_tt->rn_p;
	if (b > t->rn_b)
		goto on1; /* Wasn't lifted at all */
	do {
		x = t;
		t = t->rn_p;
	} while (b <= t->rn_b && x != top);
	for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) {
		if (m == saved_m) {
			*mp = m->rm_mklist;
			rm_free(m);
			break;
		}
	}
	if (m == NULL) {
		log(LOG_ERR, "rn_delete: couldn't find our annotation\n");
		if (tt->rn_flags & RNF_NORMAL)
			return NULL; /* Dangling ref to us */
	}
on1:
	/*
	 * Eliminate us from tree
	 */
	if (tt->rn_flags & RNF_ROOT)
		return NULL;
#ifdef RN_DEBUG
	if (rn_debug)
		log(LOG_DEBUG, "%s: Going In:\n", __func__), traverse(head, tt);
#endif
	t = tt->rn_p;
	dupedkey = saved_tt->rn_dupedkey;
	if (dupedkey != NULL) {
		/*
		 * Here, tt is the deletion target, and
		 * saved_tt is the head of the dupedkey chain.
		 */
		if (tt == saved_tt) {
			x = dupedkey;
			x->rn_p = t;
			if (t->rn_l == tt)
				t->rn_l = x;
			else
				t->rn_r = x;
		} else {
			/* find node in front of tt on the chain */
			for (x = p = saved_tt;
			     p != NULL && p->rn_dupedkey != tt;)
				p = p->rn_dupedkey;
			if (p != NULL) {
				p->rn_dupedkey = tt->rn_dupedkey;
				if (tt->rn_dupedkey != NULL)
					tt->rn_dupedkey->rn_p = p;
			} else
				log(LOG_ERR, "rn_delete: couldn't find us\n");
		}
		t = tt + 1;
		if  (t->rn_flags & RNF_ACTIVE) {
			*++x = *t;
			p = t->rn_p;
			if (p->rn_l == t)
				p->rn_l = x;
			else
				p->rn_r = x;
			x->rn_l->rn_p = x;
			x->rn_r->rn_p = x;
		}
		goto out;
	}
	if (t->rn_l == tt)
		x = t->rn_r;
	else
		x = t->rn_l;
	p = t->rn_p;
	if (p->rn_r == t)
		p->rn_r = x;
	else
		p->rn_l = x;
	x->rn_p = p;
	/*
	 * Demote routes attached to us.
	 */
	if (t->rn_mklist == NULL)
		;
	else if (x->rn_b >= 0) {
		for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist)
			;
		*mp = t->rn_mklist;
	} else {
		/* If there are any key,mask pairs in a sibling
		   duped-key chain, some subset will appear sorted
		   in the same order attached to our mklist */
		for (m = t->rn_mklist;
		     m != NULL && x != NULL;
		     x = x->rn_dupedkey) {
			if (m == x->rn_mklist) {
				struct radix_mask *mm = m->rm_mklist;
				x->rn_mklist = NULL;
				if (--(m->rm_refs) < 0)
					rm_free(m);
				m = mm;
			}
		}
		if (m != NULL) {
			log(LOG_ERR, "rn_delete: Orphaned Mask %p at %p\n",
			    m, x);
		}
	}
	/*
	 * We may be holding an active internal node in the tree.
	 */
	x = tt + 1;
	if (t != x) {
		*t = *x;
		t->rn_l->rn_p = t;
		t->rn_r->rn_p = t;
		p = x->rn_p;
		if (p->rn_l == x)
			p->rn_l = t;
		else
			p->rn_r = t;
	}
out:
#ifdef RN_DEBUG
	if (rn_debug) {
		log(LOG_DEBUG, "%s: Coming Out:\n", __func__),
		    traverse(head, tt);
	}
#endif /* RN_DEBUG */
	tt->rn_flags &= ~RNF_ACTIVE;
	tt[1].rn_flags &= ~RNF_ACTIVE;
	return tt;
}

struct radix_node *
rn_delete(
	const void *v_arg,
	const void *netmask_arg,
	struct radix_node_head *head)
{
	return rn_delete1(v_arg, netmask_arg, head, NULL);
}

static struct radix_node *
rn_walknext(struct radix_node *rn, rn_printer_t printer, void *arg)
{
	/* If at right child go back up, otherwise, go right */
	while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) {
		if (printer != NULL)
			(*printer)(arg, SUBTREE_CLOSE);
		rn = rn->rn_p;
	}
	if (printer)
		rn_nodeprint(rn->rn_p, printer, arg, "");
	/* Find the next *leaf* since next node might vanish, too */
	for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) {
		if (printer != NULL)
			(*printer)(arg, SUBTREE_OPEN);
		rn = rn->rn_l;
	}
	return rn;
}

static struct radix_node *
rn_walkfirst(struct radix_node *rn, rn_printer_t printer, void *arg)
{
	/* First time through node, go left */
	while (rn->rn_b >= 0) {
		if (printer != NULL)
			(*printer)(arg, SUBTREE_OPEN);
		rn = rn->rn_l;
	}
	return rn;
}

int
rn_walktree(
	struct radix_node_head *h,
	int (*f)(struct radix_node *, void *),
	void *w)
{
	int error;
	struct radix_node *base, *next, *rn;
	/*
	 * This gets complicated because we may delete the node
	 * while applying the function f to it, so we need to calculate
	 * the successor node in advance.
	 */
	rn = rn_walkfirst(h->rnh_treetop, NULL, NULL);
	for (;;) {
		base = rn;
		next = rn_walknext(rn, NULL, NULL);
		/* Process leaves */
		while ((rn = base) != NULL) {
			base = rn->rn_dupedkey;
			if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w)))
				return error;
		}
		rn = next;
		if (rn->rn_flags & RNF_ROOT)
			return 0;
	}
	/* NOTREACHED */
}

struct radix_node *
rn_search_matched(struct radix_node_head *h,
    int (*matcher)(struct radix_node *, void *), void *w)
{
	bool matched;
	struct radix_node *base, *next, *rn;
	/*
	 * This gets complicated because we may delete the node
	 * while applying the function f to it, so we need to calculate
	 * the successor node in advance.
	 */
	rn = rn_walkfirst(h->rnh_treetop, NULL, NULL);
	for (;;) {
		base = rn;
		next = rn_walknext(rn, NULL, NULL);
		/* Process leaves */
		while ((rn = base) != NULL) {
			base = rn->rn_dupedkey;
			if (!(rn->rn_flags & RNF_ROOT)) {
				matched = (*matcher)(rn, w);
				if (matched)
					return rn;
			}
		}
		rn = next;
		if (rn->rn_flags & RNF_ROOT)
			return NULL;
	}
	/* NOTREACHED */
}

int
rn_inithead(void **head, int off)
{
	struct radix_node_head *rnh;

	if (*head != NULL)
		return 1;
	R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));
	if (rnh == NULL)
		return 0;
	*head = rnh;
	return rn_inithead0(rnh, off);
}

int
rn_inithead0(struct radix_node_head *rnh, int off)
{
	struct radix_node *t;
	struct radix_node *tt;
	struct radix_node *ttt;

	clib_memset(rnh, 0, sizeof(*rnh));
	t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);
	ttt = rnh->rnh_nodes + 2;
	t->rn_r = ttt;
	t->rn_p = t;
	tt = t->rn_l;
	tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;
	tt->rn_b = -1 - off;
	*ttt = *tt;
	ttt->rn_key = rn_ones;
	rnh->rnh_addaddr = rn_addroute;
	rnh->rnh_deladdr = rn_delete;
	rnh->rnh_matchaddr = rn_match;
	rnh->rnh_lookup = rn_lookup;
	rnh->rnh_treetop = t;
	return 1;
}

static clib_error_t *
rn_module_init (vlib_main_t * vm)
{
	char *cp, *cplim;

	R_Malloc(rn_zeros, char *, 3 * max_keylen);
	if (rn_zeros == NULL)
            return (clib_error_return (0, "RN Zeros..."));

	clib_memset(rn_zeros, 0, 3 * max_keylen);
	rn_ones = cp = rn_zeros + max_keylen;
	addmask_key = cplim = rn_ones + max_keylen;
	while (cp < cplim)
		*cp++ = -1;
	if (rn_inithead((void *)&mask_rnhead, 0) == 0)
            return (clib_error_return (0, "RN Init 2"));

        return (NULL);
}

VLIB_INIT_FUNCTION(rn_module_init);