/*
 * Copyright (c) 2003 Research Engineering Development, Inc.
 * Author: Alfred Perlstein <alfred@FreeBSD.org>
 * 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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
 *
 * $Id: mtrie.c,v 1.6 2003/07/01 08:01:17 bright Exp $
 *
 */
#include <stdlib.h>
#include <sys/types.h>
#if !defined(__FreeBSD__) || __FreeBSD_version >= 500000
#include <stdint.h>
#endif

#include "mtrie.h"

#ifdef DEBUG
#include <stdio.h>
#endif

#ifdef __unused
#define UNUSED(x) x __unused
#else
#define UNUSED(x) x
#endif

/*
 * Head object, just a reference to the first 'row'.
 */
struct mtrie {
	struct ment	*m_trie;
};

/*
 * These are allocated in chunks of 256.
 * The 'mask' portion is required because we need to only overwrite
 * entries that are less specific.  Meaning data for a /6 overrides data
 * for a /4.
 */
struct ment {
	struct ment	*me_next;	/* next octect or NULL. */
	void		*me_data;	/* data or NULL. */
	int		me_mask;	/* mask data was entered with. */
};

#define MTRIE_SIZE	256

static void	ment_free(struct ment *ment);
static int	poweroftwo(int x);
/*
 * std allocator.
 */
int
mtrie_alloc(mtrie_t *m, UNUSED(int flags))
{

	*m = calloc(1, sizeof(**m));
	return (*m == NULL ? -1 : 0);
}

void
mtrie_free(mtrie_t m)
{

	if (m->m_trie)
		ment_free(m->m_trie);
	free(m);
}

static void
ment_free(struct ment *ment)
{
	int i;

	for (i = 0; i < MTRIE_SIZE; i++)
		if (ment->me_next != NULL)
			ment_free(ment->me_next);
	free(ment);
}

/*
 * return 2^x
 */
static int
poweroftwo(int x)
{

	return (1 << x);
}

/*
 * std debug macro.
 */
#ifdef DEBUG
#define bug(fmt, args...)						\
	do {								\
		if (getenv("DEBUG"))					\
		fprintf(stderr, "%d: " fmt "\n", __LINE__, ##args);	\
	} while (0);
#else
#define bug(fmt, args...)
#endif

/*
 * insert into the mtrie
 */
int
mtrie_insert(mtrie_t m, uint32_t ip, uint8_t mask, void *datum)
{
	unsigned char *ov;
	struct ment **place, *prev;
	int idx, pow, accum, lowrange, rem, x;

	ov = (unsigned char *)&ip;
	place = &m->m_trie;
	prev = NULL;
	idx = 3;

	for ( ;; ) {
		/*
		 * allocate a new slot if needed
		 */
		bug("looping idx = %d", idx);
		if (*place == NULL) {
			*place = calloc(MTRIE_SIZE, sizeof(**place));
			if (*place == NULL)
				return (-1);
		}
		prev = &(*place)[ov[idx]];
		bug("mask = %d", mask);
		/*
		 * If we're still greater than 8, go down another row.
		 */
		if (mask > 8) {
			mask -= 8;
			place = &prev->me_next;
			idx--;
			continue;
		}
		/*
		 * If we're exactly at 8, just fill the data.
		 */
		if (mask == 8) {
			prev->me_data = datum;
			return (0);
		}
		accum = 0;
		rem = 8 - mask;
		/*
		 * Get the next highest multiple of 2^rem over
		 * the current cell, example:
		 * poweroftwo(rem) == 8, ov[idx] = 29
		 * then we want:
		 * accum = 32, lowrange = 24.
		 */
		pow = poweroftwo(rem);
		x = ov[idx];
		lowrange = x - (x % pow);
		accum = lowrange + pow;
		/*
		 * Now fill in the entries in the row.
		 */
		while (accum-- > lowrange) {
			struct ment *mp;

			mp = (*place) + accum;
			/*
			 * If there is no data or we're an equal or
			 * more specific mask then overwrite the data.
			 */
			if (mp->me_data == NULL || mp->me_mask >= rem) {
			 	/*
				 * If we wanted to be able to delete entries
				 * we'd probably stack them here instead,
				 * it would be a good idea to do the
				 * necessary allocation up front.
				 */
				mp->me_data = datum;
				mp->me_mask = rem;
				bug("accum: %d, datum %p, mp = %p, rem = %d",
				    accum, datum, mp, rem);
			} else {
				bug("SET!!! "
				    "accum: %d, datum %p, mp = %p, rem = %d",
				    accum, datum, mp, rem);
			}
		}
		return (0);
	}
}

/*
 * lookup in the mtrie.
 */
int
mtrie_lookup(mtrie_t m, uint32_t ip, void **datap)
{
	struct ment **place, *prev;
	unsigned char *ov;
	int idx;
	void *last;

	ov = (char *)&ip;
	place = &m->m_trie;
	prev = NULL;
	*datap = NULL;
	last = NULL;
	/*
	 * Walk the octets.
	 */
	for (idx = 3 ; idx >= 0; idx--) {
		bug("looping: idx = %d, *place = %p, prev = %p",
		    idx, *place, prev);
		bug("prev->me_data == %p",
		    prev != NULL ? prev->me_data : NULL);
		if (*place == NULL)
			break;
		/*
		 * if we're going deeper into the mtrie and
		 * leaving a node that has data then we need
		 * to remember that in case we fall out of the
		 * tree at a lower level where no specific route
		 * has been entered.
		 */
		if (prev != NULL && prev->me_data != NULL)
			last = prev->me_data;
		prev = &(*place)[ov[idx]];
		place = &prev->me_next;
	}
	bug("lookup: idx = %d, *place = %p, prev = %p",
	    idx, *place, prev);
	bug("prev->me_data == %p",
	    prev != NULL ? prev->me_data : NULL);
	/* we lost, nothing matches. */
	if (prev == NULL)
		return (-1);
	/*
	 * Get the data at the node we were at before
	 * we fell out.
	 */
	*datap = prev->me_data;
	/*
	 * If it was null then take a shot at the 'last'
	 * node that had data, that will be the data
	 * entered by a route higher up in the tree.
	 */
	if (*datap == NULL)
		*datap = last;
	/* we could have still lost. */
	return (*datap == NULL ? -1 : 0);
}