Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/npppd/npppd/../common/radish.c	Lines:	0	311	0.0 %
Date:	2017-11-13	Branches:	0	192	0.0 %


/*	$OpenBSD: radish.c,v 1.5 2017/05/30 17:52:05 yasuoka Exp $ */
/*
 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
 * 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 project 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 PROJECT 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 PROJECT 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.
 *
 */

/*
 * radish.c
 *
 * Version:	0.9
 * Created:	May     27, 1995
 * Modified:	January 28, 1997
 * Author:	Kazu YAMAMOTO
 * Email: 	kazu@is.aist-nara.ac.jp
 */

#include <sys/types.h>
#include <sys/socket.h>
#include <sys/socketvar.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>

#include "radish.h"

#include <netinet/in.h>
#include <string.h>
#include <strings.h>
#include <stdlib.h>
#include <stdio.h>

#define FATAL(x)			\
	do {				\
		fputs(x, stderr);	\
		abort();		\
	} while (0/* CONSTCOND */)

static u_char rd_bmask [] = {
	0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe,
};

static u_char rd_btest [] = {
	0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01,
};

u_char rd_deleted_km[1024];

/*
 * return 1 if success
 * return 0 if error
 */
int
rd_inithead(void **headp, int family, int slen, int off, int alen,
    int (*match)(void *, void *))
{
	struct radish_head *head;
	struct radish *new;
	struct sockaddr *masks;
	u_char *m;
	int num = alen * 8 + 1, i, j, q, r;
	int len = sizeof(*head) + sizeof(*new) + slen * num;

	if (*headp) return (1);
	R_Malloc(head, struct radish_head *, len);
	if (head == NULL)
		return 0;
	Bzero(head, len);
	new = (struct radish *)(head + 1);
	masks = (struct sockaddr *)(new +1);
	*headp = head;

	/*
	 * prepare all continuous masks
	 */
	m = (u_char *)masks;
	for (i = 0; i < num; i++, m += slen) {
		*m = slen;
		*(m + 1) = family;
		q = i >> 3;
		r = i & 7;
		for(j = 0; j < q; j++)
			*(m + off + j) = 0xff;
		*(m + off + j) = rd_bmask[r];
	}

	head->rdh_slen = slen;
	head->rdh_offset = off;
	head->rdh_alen = alen;
	head->rdh_masks = masks;
	head->rdh_match = match;
	head->rdh_top = new;

	new->rd_route = masks;
	new->rd_mask = masks;
	new->rd_btest = rd_btest[0];
	/* other nembers are 0 */

	return(1);
}

struct sockaddr *
rd_mask(struct sockaddr *m_arg, struct radish_head *head, int *maskp)
{
	u_char *mp, *masks = (u_char *)head->rdh_masks;
	int off = head->rdh_offset;
	int slen = head->rdh_slen;
	int alen = head->rdh_alen;
	int i = 0, masklen = 0;

	if (m_arg == NULL) {
		masklen = alen * 8;
		*maskp = masklen;
		return((struct sockaddr *)(masks + slen * masklen));
	}
	mp = (u_char *)m_arg + off;
	while ((i < alen) && (mp[i] == 0xff)) {
		masklen += 8;
		i++;
	}
	if (i < alen)
		switch (mp[i]) {
		case 0xfe: masklen += 7; break;
		case 0xfc: masklen += 6; break;
		case 0xf8: masklen += 5; break;
		case 0xf0: masklen += 4; break;
		case 0xe0: masklen += 3; break;
		case 0xc0: masklen += 2; break;
		case 0x80: masklen += 1; break;
		case 0x00: break;
		}
	*maskp = masklen;
	return((struct sockaddr *)(masks + slen * masklen));
}

int
rd_insert(struct sockaddr *d_arg, struct sockaddr *m_arg,
	struct radish_head *head, void *rt)
{
	struct radish *cur = head->rdh_top, *parent, *new;
	int off = head->rdh_offset;
	int slen = head->rdh_slen;
	int alen = head->rdh_alen;
	int i, lim, q, r, masklen;
	u_char *dp, *np, *rp;
	struct sockaddr *mask;

	mask = rd_mask(m_arg, head, &masklen);
	q = masklen >> 3;
	r = masklen & 7;

	/* Allocate a new radish.
	 * This may be overhead in the case that
	 * 	masklen == cur->rd_masklen
	 * and
	 *	route == dest.
	 */
	R_Malloc(new, struct radish *, sizeof(*new) + slen);
	if (new == NULL)
		return ENOBUFS;
	Bzero(new, sizeof(*new) + slen);
	new->rd_route = (struct sockaddr *)(new + 1);
	new->rd_mask = mask;
	new->rd_masklen = masklen;
	new->rd_masklim = q;
	new->rd_bmask = rd_bmask[r];
	new->rd_btest = rd_btest[r];
	new->rd_rtent = rt;

	/* masked copy from dest to route */
	np = (u_char *)new->rd_route;
	dp = (u_char *)d_arg;
	*np = *dp; /* sa_len */
	np[1] = dp[1]; /* sa_family */
	dp += off;
	np += off;
	i = 0;
	while (i < q) {
		np[i] = dp[i];
		i++;
	}
	np[i] = dp[i] & rd_bmask[r]; /* just in case */

	while (cur) {
		if (masklen == cur->rd_masklen) {
			rp = (u_char *)cur->rd_route + off;
			for (i = 0; i < alen; i++)
				if (np[i] != rp[i]) {
					/*
					 * masklen == cur->rd_masklen
					 * dest != route
					 */
					return rd_glue(cur, new, i, head);
				}
			/*
			 * masklen == cur->rd_masklen
			 * dest == route
			 */
			Free(new);
			if (cur->rd_rtent != NULL)
				return EEXIST;
			cur->rd_rtent = rt;
			return 0;
		}
		/*
		 * masklen != cur->rd_masklen
		 */
		if (masklen > cur->rd_masklen) {
			/*
			 * See if dest matches with cur node.
			 * (dest & mask) == route
			 */
			rp = (u_char *)cur->rd_route + off;
			lim = cur->rd_masklim;

			/* mask is continuous, thus mask is 0xff here. */
			for (i = 0; i < lim; i++)
				if(np[i] != rp[i]) {
					/*
					 * masklen > cur->rd_masklen
					 * (dest & mask) != route
					 */
					return rd_glue(cur, new, i, head);
				}
			if (cur->rd_bmask)
				if ((np[lim] & cur->rd_bmask) != rp[lim]) {
					/*
					 * masklen > cur->rd_masklen
					 * (dest & mask) != route
					 */
					return rd_glue(cur, new, lim, head);
				}
			/*
			 * masklen > cur->rd_masklen
			 * (dest & mask) == route
			 */
			if (cur->rd_btest & np[cur->rd_masklim]) {
				if (cur->rd_r != NULL) {
					cur = cur->rd_r;
					continue;
				}
				cur->rd_r = new;
				new->rd_p = cur;
				return 0;
			} else {
				if (cur->rd_l != NULL) {
					cur = cur->rd_l;
					continue;
				}
				cur->rd_l = new;
				new->rd_p = cur;
				return 0;
			}
		}
		/*
		 * masklen < cur->rd_masklen
		 */

		/* See if route matches with dest, be carefull!
		 * 	dest == (route & dest_mask)
		 */
		rp = (u_char *)cur->rd_route + off;
		lim = new->rd_masklim;

		/* mask is continuous, thus mask is 0xff here. */
		for (i = 0; i < lim; i++)
			if(np[i] != rp[i]) {
				/*
				 * masklen < cur->rd_masklen
				 * dest != (route & dest_mask)
				 */
				return rd_glue(cur, new, i, head);
			}
		if (new->rd_bmask)
			if (np[lim] != (rp[lim] & new->rd_bmask)) {
				/*
				 * masklen < cur->rd_masklen
				 * dest != (route & dest_mask)
				 */
				return rd_glue(cur, new, lim, head);
			}
		/*
		 * masklen < cur->rd_masklen
		 * dest == (route & dest_mask)
		 */

		/* put the new radish between cur and its parent */
		parent = cur->rd_p;
		new->rd_p = parent;
		if (parent->rd_l == cur)
			parent->rd_l = new;
		else if (parent->rd_r == cur)
			parent->rd_r = new;
		else
			FATAL("rd_insert");
		if (new->rd_btest & rp[new->rd_masklim])
			new->rd_r = cur;
		else
			new->rd_l = cur;

		cur->rd_p = new;
		return 0;
	}
	return 1;
}

/*
 * Insert a glue radish between the current and its parent.
 * Let the current radish one child of glue radish.
 * Let the new radish the other child of glue radish.
 */
int
rd_glue(struct radish *cur, struct radish *new, int misbyte,
    struct radish_head *head)
{
	struct radish *parent = cur->rd_p, *glue;
	u_char *cp = (u_char *)cur->rd_route;
	u_char *np = (u_char *)new->rd_route;
	u_char *gp;
	int off = head->rdh_offset, slen = head->rdh_slen;
	int maskb, xor, i;

	/*
	 * Glue radish
	 */
	R_Malloc(glue, struct radish *, sizeof(*glue) + slen);
	if (glue == NULL) {
		Free (new);
		return ENOBUFS;
	}
	Bzero(glue, sizeof(*glue) + slen);

	/* calculate a bit to test */
	xor = (*(cp + off + misbyte) ^ *(np + off + misbyte)) & 0xff;
	maskb = 8;
	while(xor) {
		xor >>= 1;
		maskb--;
	}

	glue->rd_route = (struct sockaddr *)(glue + 1);
	glue->rd_masklen = 8 * misbyte + maskb;
	glue->rd_masklim = misbyte;
	glue->rd_bmask = rd_bmask[maskb];
	glue->rd_btest = rd_btest[maskb];
	glue->rd_rtent = NULL;
	glue->rd_p = parent;
	glue->rd_mask = (struct sockaddr *)
		((u_char *)head->rdh_masks + slen * glue->rd_masklen);

	/* masked copy of route */
	gp = (u_char *)glue->rd_route;
	*gp = *cp; /* sa_len */
	*(gp + 1) = *(cp + 1); /* sa_family */
	cp += off;
	gp += off;
	for(i = 0; i < misbyte; i++)
		gp[i] = cp[i];
	gp[misbyte] = cp[misbyte] & glue->rd_bmask;

	if (glue->rd_btest & cp[misbyte]) {
		glue->rd_r = cur;
		glue->rd_l = new;
	} else {
		glue->rd_r = new;
		glue->rd_l = cur;
	}

	/*
	 * Children
	 */
	new->rd_p = cur->rd_p = glue;

	/*
	 * Parent
	 */
	if (parent->rd_l == cur)
		parent->rd_l = glue;
	else if (parent->rd_r == cur)
		parent->rd_r = glue;
	else
		FATAL("rd_insert");
	return 0;
}

/*
 * Find the longest-match radish with the destination.
 * Return 1 if success, otherwise return 0.
 */

int
rd_match(struct sockaddr *d_arg, struct radish_head *head, struct radish **rdp)
{
	return rd_match_next(d_arg, head, rdp, NULL);
}

int
rd_match_next(struct sockaddr *d_arg, struct radish_head *head,
    struct radish **rdp, struct radish *cur)
{
	struct radish *target = NULL;
	int off = head->rdh_offset, i, lim;
	u_char *dp = (u_char *)d_arg + off, *cp;

	if (cur == NULL) {
		cur = head->rdh_top;
		while (cur) {
			target = cur;
			if (cur->rd_btest & *(dp + cur->rd_masklim))
				cur = cur->rd_r;
			else
				cur = cur->rd_l;
		}
	} else {
		target = cur->rd_p;
		if (target == NULL) {
			*rdp = NULL;
			return 0;
		}
	}

	/* We are now on the leaf radish. Backtrace to find the radish
	   which contains route to match. */
	do {
		/* If this radish doesn't have route,
		   we skip it and chase the next parent. */
		if (target->rd_rtent != NULL) {
			cp = (u_char *)target->rd_route + off;
			lim = target->rd_masklim;

			/* Check the edge for slight speed up */
			if (target->rd_bmask)
				if ((*(dp + lim) & target->rd_bmask)
				    != *(cp + lim)){
				nextparent:
					continue;
				}

			/* mask is always 0xff */
			for (i = 0; i < lim; i++)
				if(dp[i] != cp[i])
					/* to break the for loop */
					goto nextparent;
			/* Matched to this radish! */
			*rdp = target;
			return 1;
		}
	} while ((target = target->rd_p));
	*rdp = NULL;
	return 0;
}

/*
 * Lookup the same radish according to a pair of destination and mask.
 * Return a pointer to rtentry if exists. Otherwise, return NULL.
 */

void *
rd_lookup(struct sockaddr *d_arg, struct sockaddr *m_arg,
    struct radish_head *head)
{
	struct radish *cur = head->rdh_top;
	int off = head->rdh_offset, i, lim, olim = 0, masklen;
	u_char *dp = (u_char *)d_arg + off, *cp;

	rd_mask(m_arg, head, &masklen);

	/* Skipping forward search */
	while (cur) {
		/* Skip a radish if it doesn't have a route */
		if (cur->rd_rtent != NULL) {
			cp = (u_char *)(cur->rd_route) + off;
			lim = cur->rd_masklim;
			/* check the edge to speed up a bit */
			if (cur->rd_bmask)
				if ((*(dp + lim) & cur->rd_bmask)
				    != *(cp + lim))
					return NULL;
			/* mask is always 0xff */
			for (i = olim; i < lim; i++)
				if(dp[i] != cp[i])
					return NULL;
			if (masklen == cur->rd_masklen)
				return cur->rd_rtent;
			olim = lim;
		}
		if (cur->rd_btest & *(dp + cur->rd_masklim))
			cur = cur->rd_r;
		else
			cur = cur->rd_l;
	}
	return NULL;
}

/*
 * Delete the radish for dest and mask.
 * Return 0 if success.
 * Return ENOENT if no such radish exists.
 * Return EFAULT if try to delete intermediate radish which doesn't have route.
 */

int
rd_delete(struct sockaddr *d_arg, struct sockaddr *m_arg,
    struct radish_head *head, void **item)
{
	struct radish *cur = head->rdh_top;
	int off = head->rdh_offset, i, lim, masklen;
	u_char *dp = (u_char *)d_arg + off, *cp;

	rd_mask(m_arg, head, &masklen);
	*item = NULL; /* just in case */

	while (cur) {
		/* exit loop if dest does not match with the current node
		 * 	(dest & mask) != route
		 */
		cp = (u_char *)cur->rd_route + off;
		/* check the edge to speed up */
		if (cur->rd_bmask)
			if ((*(dp + cur->rd_masklim) & cur->rd_bmask)
			    != *(cp + cur->rd_masklim))
				return ENOENT;
		/* mask is always 0xff */
		lim = cur->rd_masklim;
		for (i = 0; i < lim; i++)
			if(dp[i] != cp[i])
				return ENOENT;

		/* See if cur is exactly what we delete */

		/* Check mask to speed up */
		if (cur->rd_masklen != masklen)
			goto next;

		cp = (u_char *)cur->rd_route + off;
		lim = head->rdh_alen;
		for (i = 0; i < lim; i++)
			if (dp[i] != cp[i])
				goto next;
		/*
		 * Both route and mask are the same.
		 */
		if (cur->rd_rtent == NULL) {
			/* Leaf always has route, so this radish
			 * must be intermediate.
			 * Can't delete intermediate radish which
			 * doesn't have route.
			 */
			return EFAULT;
		}
		*item = cur->rd_rtent;
		{
			/* used to report the deleted entry back */
			u_char rl = cur->rd_route->sa_len;
			u_char ml = cur->rd_mask->sa_len;

			bcopy(cur->rd_route, rd_deleted_km, rl);
			bcopy(cur->rd_mask, rd_deleted_km + rl, ml);
		}
		if (cur->rd_l && cur->rd_r) {
			/* This radish has two children */
			cur->rd_rtent = NULL;
			return 0;
		}
		/* Unlink the radish that has 0 or 1 child
		 * and surely has a route.
		 */
		rd_unlink(cur, head->rdh_top);
		return 0;

	next:
		/* seach corresponding subtree */
		if (cur->rd_btest & *(dp + cur->rd_masklim)) {
			if (cur->rd_r) {
				cur = cur->rd_r;
				continue;
			} else
				break;
		} else {
			if (cur->rd_l) {
				cur = cur->rd_l;
				continue;
			} else
				break;
		}
	}
	return ENOENT;
}

/*
 * Free radish and refine radish tree.
 * rd_unlink is called with radish which have 0 or 1 child and route.
 * Error causes panic, so return only when success.
 */

void
rd_unlink(struct radish *cur, struct radish *top)
{
	struct radish *parent, *child;

	if (cur == top) {
		cur->rd_rtent = NULL;
		return;
	}

	if ((cur->rd_l == 0) && (cur->rd_r == 0)) {
		/* No child, just delete it. */
		parent = cur->rd_p;
		if (parent->rd_l == cur) {
			parent->rd_l = NULL;
			Free(cur);
		} else if (parent->rd_r == cur) {
			parent->rd_r = NULL;
			Free(cur);
		} else
			FATAL("rd_unlink");
		if (parent->rd_rtent == NULL && parent != top)
			/* Parent is not necessary, refine radish. */
			rd_unlink(parent, top);
	} else {
		/*
		 * There is one child, never two.
		 * Make its child its parent's child.
		 */
		if (cur->rd_l)
			child = cur->rd_l;
		else
			child = cur->rd_r;
		parent = cur->rd_p;
		child->rd_p = parent;
		if (parent->rd_l == cur) {
			parent->rd_l = child;
			Free(cur);
		} else if (parent->rd_r == cur) {
			parent->rd_r = child;
			Free(cur);
		} else
			FATAL("rd_unlink");
	}
}

int
rd_walktree(struct radish_head *h, register int (*f)(struct radish *, void *),
    void *w)
{
	int error = 0;
	struct radish *par = NULL, *cur, *top = h->rdh_top;

	cur = top;
	for (;;) {
		while (cur) {
			if (cur->rd_rtent != NULL)
				if ((error = (*f)(cur, w)))
					return error;
			par = cur;
			cur = cur->rd_l;
		}
		cur = par;
		while (cur->rd_r == NULL || par == cur->rd_r) {
			par = cur;
			cur = cur->rd_p;
			if (cur == NULL) return 0;
		}
		par = cur;
		cur = cur->rd_r;
	}
}

/* This function can be mush easier in the context of radish.
 * For instance, using rd_mask. But we stay the original because
 * it works.
 */
int
rd_refines(void *m_arg, void *n_arg)
{
	register caddr_t m = m_arg, n = n_arg;
	register caddr_t lim, lim2 = lim = n + *(u_char *)n;
	int longer = (*(u_char *)n++) - (int)(*(u_char *)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);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: radish.c,v 1.5 2017/05/30 17:52:05 yasuoka Exp $ */
2			/*
3			* Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
4			* All rights reserved.
5			*
6			* Redistribution and use in source and binary forms, with or without
7			* modification, are permitted provided that the following conditions
8			* are met:
9			* 1. Redistributions of source code must retain the above copyright
10			* notice, this list of conditions and the following disclaimer.
11			* 2. Redistributions in binary form must reproduce the above copyright
12			* notice, this list of conditions and the following disclaimer in the
13			* documentation and/or other materials provided with the distribution.
14			* 3. Neither the name of the project nor the names of its contributors
15			* may be used to endorse or promote products derived from this software
16			* without specific prior written permission.
17			*
18			* THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
19			* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21			* ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
22			* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23			* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24			* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26			* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27			* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28			* SUCH DAMAGE.
29			*
30			*/
31
32			/*
33			* radish.c
34			*
35			* Version: 0.9
36			* Created: May 27, 1995
37			* Modified: January 28, 1997
38			* Author: Kazu YAMAMOTO
39			* Email: kazu@is.aist-nara.ac.jp
40			*/
41
42			#include <sys/types.h>
43			#include <sys/socket.h>
44			#include <sys/socketvar.h>
45			#include <string.h>
46			#include <stdlib.h>
47			#include <errno.h>
48
49			#include "radish.h"
50
51			#include <netinet/in.h>
52			#include <string.h>
53			#include <strings.h>
54			#include <stdlib.h>
55			#include <stdio.h>
56
57			#define FATAL(x) \
58			do { \
59			fputs(x, stderr); \
60			abort(); \
61			} while (0/* CONSTCOND */)
62
63			static u_char rd_bmask [] = {
64			0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe,
65			};
66
67			static u_char rd_btest [] = {
68			0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01,
69			};
70
71			u_char rd_deleted_km[1024];
72
73			/*
74			* return 1 if success
75			* return 0 if error
76			*/
77			int
78			rd_inithead(void **headp, int family, int slen, int off, int alen,
79			int (match)(void , void *))
80			{
81			struct radish_head *head;
82			struct radish *new;
83			struct sockaddr *masks;
84			u_char *m;
85			int num = alen * 8 + 1, i, j, q, r;
86			int len = sizeof(head) + sizeof(new) + slen * num;
87
88			if (*headp) return (1);
89			R_Malloc(head, struct radish_head *, len);
90			if (head == NULL)
91			return 0;
92			Bzero(head, len);
93			new = (struct radish *)(head + 1);
94			masks = (struct sockaddr *)(new +1);
95			*headp = head;
96
97			/*
98			* prepare all continuous masks
99			*/
100			m = (u_char *)masks;
101			for (i = 0; i < num; i++, m += slen) {
102			*m = slen;
103			*(m + 1) = family;
104			q = i >> 3;
105			r = i & 7;
106			for(j = 0; j < q; j++)
107			*(m + off + j) = 0xff;
108			*(m + off + j) = rd_bmask[r];
109			}
110
111			head->rdh_slen = slen;
112			head->rdh_offset = off;
113			head->rdh_alen = alen;
114			head->rdh_masks = masks;
115			head->rdh_match = match;
116			head->rdh_top = new;
117
118			new->rd_route = masks;
119			new->rd_mask = masks;
120			new->rd_btest = rd_btest[0];
121			/* other nembers are 0 */
122
123			return(1);
124			}
125
126			struct sockaddr *
127			rd_mask(struct sockaddr m_arg, struct radish_head head, int *maskp)
128			{
129			u_char mp, masks = (u_char *)head->rdh_masks;
130			int off = head->rdh_offset;
131			int slen = head->rdh_slen;
132			int alen = head->rdh_alen;
133			int i = 0, masklen = 0;
134
135			if (m_arg == NULL) {
136			masklen = alen * 8;
137			*maskp = masklen;
138			return((struct sockaddr )(masks + slen masklen));
139			}
140			mp = (u_char *)m_arg + off;
141			while ((i < alen) && (mp[i] == 0xff)) {
142			masklen += 8;
143			i++;
144			}
145			if (i < alen)
146			switch (mp[i]) {
147			case 0xfe: masklen += 7; break;
148			case 0xfc: masklen += 6; break;
149			case 0xf8: masklen += 5; break;
150			case 0xf0: masklen += 4; break;
151			case 0xe0: masklen += 3; break;
152			case 0xc0: masklen += 2; break;
153			case 0x80: masklen += 1; break;
154			case 0x00: break;
155			}
156			*maskp = masklen;
157			return((struct sockaddr )(masks + slen masklen));
158			}
159
160			int
161			rd_insert(struct sockaddr d_arg, struct sockaddr m_arg,
162			struct radish_head head, void rt)
163			{
164			struct radish cur = head->rdh_top, parent, *new;
165			int off = head->rdh_offset;
166			int slen = head->rdh_slen;
167			int alen = head->rdh_alen;
168			int i, lim, q, r, masklen;
169			u_char dp, np, *rp;
170			struct sockaddr *mask;
171
172			mask = rd_mask(m_arg, head, &masklen);
173			q = masklen >> 3;
174			r = masklen & 7;
175
176			/* Allocate a new radish.
177			* This may be overhead in the case that
178			* masklen == cur->rd_masklen
179			* and
180			* route == dest.
181			*/
182			R_Malloc(new, struct radish , sizeof(new) + slen);
183			if (new == NULL)
184			return ENOBUFS;
185			Bzero(new, sizeof(*new) + slen);
186			new->rd_route = (struct sockaddr *)(new + 1);
187			new->rd_mask = mask;
188			new->rd_masklen = masklen;
189			new->rd_masklim = q;
190			new->rd_bmask = rd_bmask[r];
191			new->rd_btest = rd_btest[r];
192			new->rd_rtent = rt;
193
194			/* masked copy from dest to route */
195			np = (u_char *)new->rd_route;
196			dp = (u_char *)d_arg;
197			np = dp; /* sa_len */
198			np[1] = dp[1]; /* sa_family */
199			dp += off;
200			np += off;
201			i = 0;
202			while (i < q) {
203			np[i] = dp[i];
204			i++;
205			}
206			np[i] = dp[i] & rd_bmask[r]; /* just in case */
207
208			while (cur) {
209			if (masklen == cur->rd_masklen) {
210			rp = (u_char *)cur->rd_route + off;
211			for (i = 0; i < alen; i++)
212			if (np[i] != rp[i]) {
213			/*
214			* masklen == cur->rd_masklen
215			* dest != route
216			*/
217			return rd_glue(cur, new, i, head);
218			}
219			/*
220			* masklen == cur->rd_masklen
221			* dest == route
222			*/
223			Free(new);
224			if (cur->rd_rtent != NULL)
225			return EEXIST;
226			cur->rd_rtent = rt;
227			return 0;
228			}
229			/*
230			* masklen != cur->rd_masklen
231			*/
232			if (masklen > cur->rd_masklen) {
233			/*
234			* See if dest matches with cur node.
235			* (dest & mask) == route
236			*/
237			rp = (u_char *)cur->rd_route + off;
238			lim = cur->rd_masklim;
239
240			/* mask is continuous, thus mask is 0xff here. */
241			for (i = 0; i < lim; i++)
242			if(np[i] != rp[i]) {
243			/*
244			* masklen > cur->rd_masklen
245			* (dest & mask) != route
246			*/
247			return rd_glue(cur, new, i, head);
248			}
249			if (cur->rd_bmask)
250			if ((np[lim] & cur->rd_bmask) != rp[lim]) {
251			/*
252			* masklen > cur->rd_masklen
253			* (dest & mask) != route
254			*/
255			return rd_glue(cur, new, lim, head);
256			}
257			/*
258			* masklen > cur->rd_masklen
259			* (dest & mask) == route
260			*/
261			if (cur->rd_btest & np[cur->rd_masklim]) {
262			if (cur->rd_r != NULL) {
263			cur = cur->rd_r;
264			continue;
265			}
266			cur->rd_r = new;
267			new->rd_p = cur;
268			return 0;
269			} else {
270			if (cur->rd_l != NULL) {
271			cur = cur->rd_l;
272			continue;
273			}
274			cur->rd_l = new;
275			new->rd_p = cur;
276			return 0;
277			}
278			}
279			/*
280			* masklen < cur->rd_masklen
281			*/
282
283			/* See if route matches with dest, be carefull!
284			* dest == (route & dest_mask)
285			*/
286			rp = (u_char *)cur->rd_route + off;
287			lim = new->rd_masklim;
288
289			/* mask is continuous, thus mask is 0xff here. */
290			for (i = 0; i < lim; i++)
291			if(np[i] != rp[i]) {
292			/*
293			* masklen < cur->rd_masklen
294			* dest != (route & dest_mask)
295			*/
296			return rd_glue(cur, new, i, head);
297			}
298			if (new->rd_bmask)
299			if (np[lim] != (rp[lim] & new->rd_bmask)) {
300			/*
301			* masklen < cur->rd_masklen
302			* dest != (route & dest_mask)
303			*/
304			return rd_glue(cur, new, lim, head);
305			}
306			/*
307			* masklen < cur->rd_masklen
308			* dest == (route & dest_mask)
309			*/
310
311			/* put the new radish between cur and its parent */
312			parent = cur->rd_p;
313			new->rd_p = parent;
314			if (parent->rd_l == cur)
315			parent->rd_l = new;
316			else if (parent->rd_r == cur)
317			parent->rd_r = new;
318			else
319			FATAL("rd_insert");
320			if (new->rd_btest & rp[new->rd_masklim])
321			new->rd_r = cur;
322			else
323			new->rd_l = cur;
324
325			cur->rd_p = new;
326			return 0;
327			}
328			return 1;
329			}
330
331			/*
332			* Insert a glue radish between the current and its parent.
333			* Let the current radish one child of glue radish.
334			* Let the new radish the other child of glue radish.
335			*/
336			int
337			rd_glue(struct radish cur, struct radish new, int misbyte,
338			struct radish_head *head)
339			{
340			struct radish parent = cur->rd_p, glue;
341			u_char cp = (u_char )cur->rd_route;
342			u_char np = (u_char )new->rd_route;
343			u_char *gp;
344			int off = head->rdh_offset, slen = head->rdh_slen;
345			int maskb, xor, i;
346
347			/*
348			* Glue radish
349			*/
350			R_Malloc(glue, struct radish , sizeof(glue) + slen);
351			if (glue == NULL) {
352			Free (new);
353			return ENOBUFS;
354			}
355			Bzero(glue, sizeof(*glue) + slen);
356
357			/* calculate a bit to test */
358			xor = ((cp + off + misbyte) ^ (np + off + misbyte)) & 0xff;
359			maskb = 8;
360			while(xor) {
361			xor >>= 1;
362			maskb--;
363			}
364
365			glue->rd_route = (struct sockaddr *)(glue + 1);
366			glue->rd_masklen = 8 * misbyte + maskb;
367			glue->rd_masklim = misbyte;
368			glue->rd_bmask = rd_bmask[maskb];
369			glue->rd_btest = rd_btest[maskb];
370			glue->rd_rtent = NULL;
371			glue->rd_p = parent;
372			glue->rd_mask = (struct sockaddr *)
373			((u_char )head->rdh_masks + slen glue->rd_masklen);
374
375			/* masked copy of route */
376			gp = (u_char *)glue->rd_route;
377			gp = cp; /* sa_len */
378			(gp + 1) = (cp + 1); /* sa_family */
379			cp += off;
380			gp += off;
381			for(i = 0; i < misbyte; i++)
382			gp[i] = cp[i];
383			gp[misbyte] = cp[misbyte] & glue->rd_bmask;
384
385			if (glue->rd_btest & cp[misbyte]) {
386			glue->rd_r = cur;
387			glue->rd_l = new;
388			} else {
389			glue->rd_r = new;
390			glue->rd_l = cur;
391			}
392
393			/*
394			* Children
395			*/
396			new->rd_p = cur->rd_p = glue;
397
398			/*
399			* Parent
400			*/
401			if (parent->rd_l == cur)
402			parent->rd_l = glue;
403			else if (parent->rd_r == cur)
404			parent->rd_r = glue;
405			else
406			FATAL("rd_insert");
407			return 0;
408			}
409
410			/*
411			* Find the longest-match radish with the destination.
412			* Return 1 if success, otherwise return 0.
413			*/
414
415			int
416			rd_match(struct sockaddr d_arg, struct radish_head head, struct radish **rdp)
417			{
418			return rd_match_next(d_arg, head, rdp, NULL);
419			}
420
421			int
422			rd_match_next(struct sockaddr d_arg, struct radish_head head,
423			struct radish *rdp, struct radish cur)
424			{
425			struct radish *target = NULL;
426			int off = head->rdh_offset, i, lim;
427			u_char dp = (u_char )d_arg + off, *cp;
428
429			if (cur == NULL) {
430			cur = head->rdh_top;
431			while (cur) {
432			target = cur;
433			if (cur->rd_btest & *(dp + cur->rd_masklim))
434			cur = cur->rd_r;
435			else
436			cur = cur->rd_l;
437			}
438			} else {
439			target = cur->rd_p;
440			if (target == NULL) {
441			*rdp = NULL;
442			return 0;
443			}
444			}
445
446			/* We are now on the leaf radish. Backtrace to find the radish
447			which contains route to match. */
448			do {
449			/* If this radish doesn't have route,
450			we skip it and chase the next parent. */
451			if (target->rd_rtent != NULL) {
452			cp = (u_char *)target->rd_route + off;
453			lim = target->rd_masklim;
454
455			/* Check the edge for slight speed up */
456			if (target->rd_bmask)
457			if ((*(dp + lim) & target->rd_bmask)
458			!= *(cp + lim)){
459			nextparent:
460			continue;
461			}
462
463			/* mask is always 0xff */
464			for (i = 0; i < lim; i++)
465			if(dp[i] != cp[i])
466			/* to break the for loop */
467			goto nextparent;
468			/* Matched to this radish! */
469			*rdp = target;
470			return 1;
471			}
472			} while ((target = target->rd_p));
473			*rdp = NULL;
474			return 0;
475			}
476
477			/*
478			* Lookup the same radish according to a pair of destination and mask.
479			* Return a pointer to rtentry if exists. Otherwise, return NULL.
480			*/
481
482			void *
483			rd_lookup(struct sockaddr d_arg, struct sockaddr m_arg,
484			struct radish_head *head)
485			{
486			struct radish *cur = head->rdh_top;
487			int off = head->rdh_offset, i, lim, olim = 0, masklen;
488			u_char dp = (u_char )d_arg + off, *cp;
489
490			rd_mask(m_arg, head, &masklen);
491
492			/* Skipping forward search */
493			while (cur) {
494			/* Skip a radish if it doesn't have a route */
495			if (cur->rd_rtent != NULL) {
496			cp = (u_char *)(cur->rd_route) + off;
497			lim = cur->rd_masklim;
498			/* check the edge to speed up a bit */
499			if (cur->rd_bmask)
500			if ((*(dp + lim) & cur->rd_bmask)
501			!= *(cp + lim))
502			return NULL;
503			/* mask is always 0xff */
504			for (i = olim; i < lim; i++)
505			if(dp[i] != cp[i])
506			return NULL;
507			if (masklen == cur->rd_masklen)
508			return cur->rd_rtent;
509			olim = lim;
510			}
511			if (cur->rd_btest & *(dp + cur->rd_masklim))
512			cur = cur->rd_r;
513			else
514			cur = cur->rd_l;
515			}
516			return NULL;
517			}
518
519			/*
520			* Delete the radish for dest and mask.
521			* Return 0 if success.
522			* Return ENOENT if no such radish exists.
523			* Return EFAULT if try to delete intermediate radish which doesn't have route.
524			*/
525
526			int
527			rd_delete(struct sockaddr d_arg, struct sockaddr m_arg,
528			struct radish_head head, void *item)
529			{
530			struct radish *cur = head->rdh_top;
531			int off = head->rdh_offset, i, lim, masklen;
532			u_char dp = (u_char )d_arg + off, *cp;
533
534			rd_mask(m_arg, head, &masklen);
535			item = NULL; / just in case */
536
537			while (cur) {
538			/* exit loop if dest does not match with the current node
539			* (dest & mask) != route
540			*/
541			cp = (u_char *)cur->rd_route + off;
542			/* check the edge to speed up */
543			if (cur->rd_bmask)
544			if ((*(dp + cur->rd_masklim) & cur->rd_bmask)
545			!= *(cp + cur->rd_masklim))
546			return ENOENT;
547			/* mask is always 0xff */
548			lim = cur->rd_masklim;
549			for (i = 0; i < lim; i++)
550			if(dp[i] != cp[i])
551			return ENOENT;
552
553			/* See if cur is exactly what we delete */
554
555			/* Check mask to speed up */
556			if (cur->rd_masklen != masklen)
557			goto next;
558
559			cp = (u_char *)cur->rd_route + off;
560			lim = head->rdh_alen;
561			for (i = 0; i < lim; i++)
562			if (dp[i] != cp[i])
563			goto next;
564			/*
565			* Both route and mask are the same.
566			*/
567			if (cur->rd_rtent == NULL) {
568			/* Leaf always has route, so this radish
569			* must be intermediate.
570			* Can't delete intermediate radish which
571			* doesn't have route.
572			*/
573			return EFAULT;
574			}
575			*item = cur->rd_rtent;
576			{
577			/* used to report the deleted entry back */
578			u_char rl = cur->rd_route->sa_len;
579			u_char ml = cur->rd_mask->sa_len;
580
581			bcopy(cur->rd_route, rd_deleted_km, rl);
582			bcopy(cur->rd_mask, rd_deleted_km + rl, ml);
583			}
584			if (cur->rd_l && cur->rd_r) {
585			/* This radish has two children */
586			cur->rd_rtent = NULL;
587			return 0;
588			}
589			/* Unlink the radish that has 0 or 1 child
590			* and surely has a route.
591			*/
592			rd_unlink(cur, head->rdh_top);
593			return 0;
594
595			next:
596			/* seach corresponding subtree */
597			if (cur->rd_btest & *(dp + cur->rd_masklim)) {
598			if (cur->rd_r) {
599			cur = cur->rd_r;
600			continue;
601			} else
602			break;
603			} else {
604			if (cur->rd_l) {
605			cur = cur->rd_l;
606			continue;
607			} else
608			break;
609			}
610			}
611			return ENOENT;
612			}
613
614			/*
615			* Free radish and refine radish tree.
616			* rd_unlink is called with radish which have 0 or 1 child and route.
617			* Error causes panic, so return only when success.
618			*/
619
620			void
621			rd_unlink(struct radish cur, struct radish top)
622			{
623			struct radish parent, child;
624
625			if (cur == top) {
626			cur->rd_rtent = NULL;
627			return;
628			}
629
630			if ((cur->rd_l == 0) && (cur->rd_r == 0)) {
631			/* No child, just delete it. */
632			parent = cur->rd_p;
633			if (parent->rd_l == cur) {
634			parent->rd_l = NULL;
635			Free(cur);
636			} else if (parent->rd_r == cur) {
637			parent->rd_r = NULL;
638			Free(cur);
639			} else
640			FATAL("rd_unlink");
641			if (parent->rd_rtent == NULL && parent != top)
642			/* Parent is not necessary, refine radish. */
643			rd_unlink(parent, top);
644			} else {
645			/*
646			* There is one child, never two.
647			* Make its child its parent's child.
648			*/
649			if (cur->rd_l)
650			child = cur->rd_l;
651			else
652			child = cur->rd_r;
653			parent = cur->rd_p;
654			child->rd_p = parent;
655			if (parent->rd_l == cur) {
656			parent->rd_l = child;
657			Free(cur);
658			} else if (parent->rd_r == cur) {
659			parent->rd_r = child;
660			Free(cur);
661			} else
662			FATAL("rd_unlink");
663			}
664			}
665
666			int
667			rd_walktree(struct radish_head h, register int (f)(struct radish , void ),
668			void *w)
669			{
670			int error = 0;
671			struct radish par = NULL, cur, *top = h->rdh_top;
672
673			cur = top;
674			for (;;) {
675			while (cur) {
676			if (cur->rd_rtent != NULL)
677			if ((error = (*f)(cur, w)))
678			return error;
679			par = cur;
680			cur = cur->rd_l;
681			}
682			cur = par;
683			while (cur->rd_r == NULL \|\| par == cur->rd_r) {
684			par = cur;
685			cur = cur->rd_p;
686			if (cur == NULL) return 0;
687			}
688			par = cur;
689			cur = cur->rd_r;
690			}
691			}
692
693			/* This function can be mush easier in the context of radish.
694			* For instance, using rd_mask. But we stay the original because
695			* it works.
696			*/
697			int
698			rd_refines(void m_arg, void n_arg)
699			{
700			register caddr_t m = m_arg, n = n_arg;
701			register caddr_t lim, lim2 = lim = n + (u_char )n;
702			int longer = ((u_char )n++) - (int)((u_char )m++);
703			int masks_are_equal = 1;
704
705			if (longer > 0)
706			lim -= longer;
707			while (n < lim) {
708			if (n & ~(m))
709			return 0;
710			if (n++ != m++)
711			masks_are_equal = 0;
712
713			}
714			while (n < lim2)
715			if (*n++)
716			return 0;
717			if (masks_are_equal && (longer < 0))
718			for (lim2 = m - longer; m < lim2; )
719			if (*m++)
720			return 1;
721			return (!masks_are_equal);
722			}