//-----------------------------------------------------------------------------
// Copyright © 2005 - Philip Howard - All rights reserved
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//-----------------------------------------------------------------------------
// package	libh/string
// homepage	http://libh.slashusr.org/
//-----------------------------------------------------------------------------
// author	Philip Howard
// email	libh at ipal dot org
// homepage	http://phil.ipal.org/
//-----------------------------------------------------------------------------
// This file is best viewed using a fixed spaced font such as Courier
// and in a display at least 120 columns wide.
//-----------------------------------------------------------------------------

#include <stdio.h>

#include "net_lib.h"

__FMACRO_BEGIN__
//-----------------------------------------------------------------------------
// macro	ipv4_table_iterate
//
// purpose	Iterate through all the entries in an IPv4 lookup table.
//
// arguments	1 (ipv4_table_p) pointer to IPv4 lookup table to iterate on
//		2 (void *) function to call for each entry
//		3 (void *) extra pointer to pass to this function
//
// returns	(unsigned long) sum of iteration returns
//-----------------------------------------------------------------------------
#define ipv4_table_iterate(t,f,p) ipv4_table_iterate_node((ipv4_table_node_p)(t),(ipv4_t)0,0,(f),(p))

__FMACRO_END__

__PROTO_BEGIN__
//-----------------------------------------------------------------------------
// function	ipv4_table_iterate_node (internal only)
//
// purpose	Recursively iterate through all the nodes in an IPv4 lookup
//		table.
//
// arguments	1 (ipv4_table_p) pointer to IPv4 lookup table to iterate on
//		2 (ipv4_t) address of this branch
//		3 (int) prefix of this branch
//		4 (unsigned long(*)(ipv4_t,int,void*,void*)) function
//		5 (void *) extra pointer to pass to this function
//
// returns	(unsigned long) sum of iteration returns
//
// arguments to called function
//		1 (ipv4_t) subnet base IPv4 address
//		2 (int) CIDR prefix length of subnet
//		3 (void *) pointer associated with subnet
//		4 (void *) pointer passed to iteration
//
// return from called function
//		(unsigned long) number to accumulate for the iteration return
//-----------------------------------------------------------------------------
unsigned long long
ipv4_table_iterate_node (
    ipv4_table_node_p		arg_node
    ,
    ipv4_t			arg_addr
    ,
    int				arg_prefix
    ,
    unsigned long ( *		arg_fun		)( ipv4_t, int, void *, void * )
    ,
    void *			arg_ptr
    )
__PROTO_END__
{
    unsigned long long	count		;
    ipv4_table_node_p	prev		;
    ipv4_table_node_p	this		;
    ipv4_t		addr		;
    ipv4_t		mask		;
    int			prefix		;


    if ( ! arg_node || ! arg_fun ) return 0;

    count = 0;
    prefix = 0;
    addr = 0;
    mask = 0x80000000;

    prev = NULL;
    this = arg_node;

    for (;;) {
	if ( ! this || ( ((int)this) & 3 ) ) {
	    fprintf(stderr,"bad pointer\n");
	    return 1;
	}
	if ( prev == this->prev ) {
	    if ( this->data ) count += (*arg_fun)( addr, prefix, this->data, arg_ptr );
	    if ( prefix == 31 ) {
		if ( this->next[0] ) count += (*arg_fun)( addr+0, prefix+1, (void *) ( this->next[0] ), arg_ptr );
		if ( this->next[1] ) count += (*arg_fun)( addr+1, prefix+1, (void *) ( this->next[1] ), arg_ptr );
		goto go_up;
	    }
	    goto go_down_0;
	}
	if ( prev == this->next[0] ) goto go_down_1;
	if ( prev == this->next[1] ) goto go_up;
	break;
    go_down_0:
	if ( this->next[0] ) {
	    prev = this;
	    this = this->next[0];
	    mask >>= 1;
	    ++ prefix;
	    continue;
	}
    go_down_1:
	if ( this->next[1] ) {
	    prev = this;
	    this = this->next[1];
	    addr |= mask;
	    mask >>= 1;
	    ++ prefix;
	    continue;
	}
    go_up:
	if ( this->prev ) {
	    prev = this;
	    this = this->prev;
	    addr &= ~ mask;
	    mask <<= 1;
	    -- prefix;
	    continue;
	}
	return count;
    }
    fputs( "ipv4_table_iterate: lost in corrupt ipv4 lookup tree\n", stderr );
    return 0;
}