#if HAVE_CONFIG_H
#include <ntm_conf.h>
#endif

/* conditional compile switches
 */
#define SUBNET_PARANOIA         FALSE       /* slows down program exponentially! */
#define SUBNET_STATIC_ALLOC     FALSE
#define SUBNET_FIND_MEMREFCNT   TRUE
#define SUBNET_DUMPS_LINE_NUM   FALSE



/* must be defined before the first use of the macro NODE_FROM_EXTERN()
 */
static Subnet *first_external = NULL;

/* root of radix trie
 */
static POINTER_DATATYPE subnet_root;

/* contiguously allocated pool of tree nodes
 */
#if SUBNET_STATIC_ALLOC
static SubnetTree subnet_pool[ MAX_TREE_NODES ];
#else
static SubnetTree *subnet_pool = NULL;
#endif

static unsigned subnet_nodes_per_level[ 4 ];
#if SUBNET_FIND_MEMREFCNT
static unsigned subnets_found_per_level[ 4 ];
#endif

/* for PrintSubnets() and DumpRawSubnets()
 */
#define MAX_FIXUPS              100000
#define DUMP_VISITED_FLAG       1234567
static Bit32 *dump_fixup_locations[ MAX_FIXUPS ];
static Bit32 dump_fixup_values[ MAX_FIXUPS ];
static Bit32 dump_fixup_count;

/* for DumpRawSubnets()
 */
#define DUMP_SUBNET_OFFSET      0x10000000;
#define DUMP_EXTERNAL_OFFSET    0x20000000;
static Bit32 subnet_base, external_base;



/* does any lookup-method-specific initialization
 *
 * returns TRUE if successful, FALSE if failure
 */
boolean InitSubnet2( void )
{
    unsigned count;

    subnet_root = NODE_FROM_EXTERN( NULL );
       /* Alpha C compiler doesn't like expressions in declarations */

    for( count=0; count<4; count++ )
    {
        subnet_nodes_per_level[ count ] = 0;
        subnets_found_per_level[ count ] = 0;
    }

#if !SUBNET_STATIC_ALLOC
    /* allocate the memory for all possible tree nodes
     */
    subnet_pool = (SubnetTree *) flat_alloc( MAX_TREE_NODES * sizeof( SubnetTree ) );
    if( !subnet_pool )
    {
        fprintf( stderr, "InitSubnet2() error allocating %d bytes for %d subnet nodes\n",
            MAX_TREE_NODES * sizeof( SubnetTree ),
            MAX_TREE_NODES );
        return FALSE;
    }
#endif  /* !SUBNET_STATIC_ALLOC */

    /* set the subnet parms base address to high-values, so it
     * will be overwritten by the first call to InsertSubnet()
     */
    first_external = (Subnet *) -1;

    return TRUE;
}



/* accepts address in network byte order
 *
 * returns pointer to routing information,
 * or NULL if no route can be found
 */
Subnet *FindSubnet( register Bit32 address )
{
#if !defined(__unix__) && SUBNET_FIND_TIMING && !NETRAMET
    PentiumClock before;
#endif
    POINTER_DATATYPE node;

    address = ntohl( address );

#if !defined(__unix__) && SUBNET_FIND_TIMING && !NETRAMET
    /* remember when we started referencing memory
     */
    before.set();
#endif

#if BITS_PER_NODE == 8
#if BITS_PER_ROOT == 8
    /* use byte 3 (msb) as first index
     */
    node = subnet_pool[0].pointers[ address >> 24 ];
    if( IS_NODE_A_LEAF( node ) )
    {
#if !defined(__unix__) && SUBNET_FIND_TIMING && !NETRAMET
        /* calculate uncalibrated elapsed time
         */
        find_timing.set();
        find_timing -= before;
#endif
#if SUBNET_FIND_MEMREFCNT
        find_refcnt = 3;
        subnets_found_per_level[ 3 ]++;
#endif
        return EXTERN_FROM_NODE( node );
    }

    /* use byte 2 (2nd msb) as 2nd index
     */
    node = subnet_pool[node].pointers[ (address >> 16) & NODE_INDEX_MASK ];
    if( IS_NODE_A_LEAF( node ) )
    {
#if !defined(__unix__) && SUBNET_FIND_TIMING && !NETRAMET
        /* calculate uncalibrated elapsed time
         */
        find_timing.set();
        find_timing -= before;
#endif
#if SUBNET_FIND_MEMREFCNT
        find_refcnt = 2;
        subnets_found_per_level[ 2 ]++;
#endif
        return EXTERN_FROM_NODE( node );
    }
#else   /* BITS_PER_ROOT != 8 */
#if BITS_PER_ROOT == 16
    /* use bytes 3 (msb) and 2 (2nd msb) as first index
     */
    node = subnet_pool[0].pointers[ address >> 16 ];
    if( IS_NODE_A_LEAF( node ) )
    {
#if !defined(__unix__) && SUBNET_FIND_TIMING && !NETRAMET
        /* calculate uncalibrated elapsed time
         */
        find_timing.set();
        find_timing -= before;
#endif
#if SUBNET_FIND_MEMREFCNT
        find_refcnt = 2;
        subnets_found_per_level[ 2 ]++;
#endif
        return EXTERN_FROM_NODE( node );
    }
#else   /* BITS_PER_NODE != 16 */
#   error "This function is only implemented for 8 or 16 BITS_PER_ROOT!"
#endif
#endif  /* BITS_PER_ROOT != 8 */

    /* use byte 1 (2nd lsb) as next index
     */
    node = subnet_pool[node].pointers[ (address >> 8) & NODE_INDEX_MASK ];
    if( IS_NODE_A_LEAF( node ) )
    {
#if !defined(__unix__) && SUBNET_FIND_TIMING && !NETRAMET
        /* calculate uncalibrated elapsed time
         */
        find_timing.set();
        find_timing -= before;
#endif
#if SUBNET_FIND_MEMREFCNT
        find_refcnt = 1;
        subnets_found_per_level[ 1 ]++;
#endif
        return EXTERN_FROM_NODE( node );
    }

    /* use byte 0 (lsb) as last index
     *
     * assumes node is definitely a leaf
     */
    node = subnet_pool[node].pointers[ address & NODE_INDEX_MASK ];
#if !defined(__unix__) && SUBNET_FIND_TIMING && !NETRAMET
    /* calculate uncalibrated elapsed time
     */
    find_timing.set();
    find_timing -= before;
#endif
#if SUBNET_FIND_MEMREFCNT
    find_refcnt = 0;
    subnets_found_per_level[ 0 ]++;
#endif
    return EXTERN_FROM_NODE( node );
#else   /* BITS_PER_NODE != 8 */
#error "This function is only implemented for 8 BITS_PER_NODE!"
#endif
}



static boolean FillSpecificSubnet( Subnet *external, POINTER_DATATYPE *pnode,
    Bit32 addr, int new_mask_bits, int is_insertion )
{
    POINTER_DATATYPE node = *pnode;
    Subnet *old_external;
    int count;
    int result;
    int old_mask_bits;
    char ip_string[ 30 ];

    /* if this isn't a leaf...
     */
    if( !IS_NODE_A_LEAF( node ) )
    {
        /* change all the leaves we can find inside
         * which are less specific, to be my leaf
         */
        result = FALSE;
        for( count=0; count<POINTERS_PER_NODE; count++ )
            result |= FillSpecificSubnet( external, subnet_pool[node].pointers+count, addr, new_mask_bits, is_insertion );

        return result;
    }

    old_external = EXTERN_FROM_NODE( node );
    if( old_external != NULL )
        old_mask_bits = bits_in_mask( old_external->mask );
    else
        old_mask_bits = -1;

    if( is_insertion )
    {
        /* if there is no old leaf or we have more bits...
         */
        if( new_mask_bits > old_mask_bits )

            /* it is safe to overwrite the pointer
             */
            *pnode = NODE_FROM_EXTERN( external );

        /* otherwise if mask and address are the same...
         */
        else if( new_mask_bits == old_mask_bits )

            /* print a warning
             */
            printf( "subnet %s 0x%X '%s' originally inserted by line %d found; new insertion"
                " '%s' from line %d ignored\n", inet_ntoa(ip_string,ntohl(external->addr)),
                ntohl(external->mask), old_external->as_path,
                old_external->line, external->as_path, external->line );
    }
    else
    {
        /* if destination address and mask don't match,
         * this must be some other route, so leave it alone
         */
        if( new_mask_bits != old_mask_bits )
            return FALSE;

        /* it is safe to overwrite the pointer
         */
        *pnode = NODE_FROM_EXTERN( NULL );
    }

    return TRUE;
}



static boolean AlterSubnetRecurse( Subnet *external, POINTER_DATATYPE *pnode,
    Bit32 addr, int addr_bits_left, int mask_bits_left,
    int level_bits, int level_pointers, int level_mask,
    int is_insertion )
{
    POINTER_DATATYPE node = *pnode;
    int count;
    int result;
    int original_mask_bits;
    unsigned index;
    char ip_string[ 30 ];

    /* if the caller is pointing at a leaf (NIL or actual)...
     */
    if( IS_NODE_A_LEAF( node ) )
    {
        /* if this is an deletion...
         */
        if( !is_insertion )
        {
            /* this must be a more general (or no) route, so
             * we don't have the route they are talking about
             */
            fprintf( stderr, "DeleteSubnet() found leaf node too soon,"
                " so we didn't have route %s/%d\n",
                inet_ntoa( ip_string, ntohl( external->addr ) ),
                bits_in_mask( external->mask )
            );

            return FALSE;
        }

        /* allocate a node
         */
        index = level_pointers / POINTERS_PER_NODE;
        if( subnet_node_count + index > MAX_TREE_NODES )
        {
            fprintf( stderr, "InsertSubnet() cannot allocate a node\n" );
            return FALSE;
        }
        *pnode = subnet_node_count;

        /* keep track of how many nodes there are of each kind
         */
        subnet_node_count += index;
        subnet_nodes_per_level[ level_from_bits(addr_bits_left,level_bits) ] += index;

        /* all child pointers will have parent's old value
         */
        for( count=0; count<level_pointers; count++ )
            subnet_pool[ *pnode ].pointers[ count ] = node;

        /* now we use the old node
         */
        node = *pnode;
    }

    addr_bits_left -= level_bits;
    mask_bits_left -= level_bits;

    /* calculate which pointer in the node we want to alter first
     */
    index = (addr >> addr_bits_left) & level_mask;

    /* if there are still mask bits left...
     */
    if( mask_bits_left > 0 )

        /* we just need to point at another, deeper SubnetTree
         */
        return AlterSubnetRecurse( external, subnet_pool[node].pointers+index,
            addr, addr_bits_left, mask_bits_left,
            BITS_PER_NODE, POINTERS_PER_NODE, NODE_INDEX_MASK,
            is_insertion );

    /* calculate how many pointers we have to alter
     */
    count = 1 << (-mask_bits_left);

    /* fill in all the rest of the pointers
     */
    original_mask_bits = MAX_ADDR_BITS + mask_bits_left - addr_bits_left;
    result = FALSE;
    while( --count >= 0 )
        result |= FillSpecificSubnet( external, subnet_pool[node].pointers+index+count,
            addr, original_mask_bits, is_insertion );

    if( !result )
        fprintf( stderr, "DeleteSubnet() never found the right leaf node,"
            " so we didn't have route %s/%d\n",
            inet_ntoa( ip_string, ntohl( external->addr ) ),
            original_mask_bits );

    return result;
}



/* assumes Subnet address and mask fields are in network byte order
 *
 * allows zero masks
 *
 * assumes memory pointed to by "external" argument
 * was allocated from heap and can be owned by us afterwards
 *
 * returns TRUE if successful, FALSE otherwise
 */
static boolean AlterSubnet( Subnet *external, int is_insertion )
{
    int index;
    int count;
    int mask_bits_left;
    int result;
#if SUBNET_PARANOIA
    int heap_result;
#endif
    Bit32 addr;
    Bit32 trial_node;           /* must have more bits than POINTER_DATATYPE */

#if SUBNET_PARANOIA
    heap_result = heapcheck();
    if( heap_result < 0 )
    {
        fprintf( stderr, "heapcheck() before returned %d\n", heap_result );
        return FALSE;
    }
#endif

    /* make sure the caller does not have any bits set
     * in their address that are cleared in their mask
     * (enforce the mask)
     */
    external->addr &= external->mask;

    /* get the address in host byte order
     */
    addr = ntohl( external->addr );

    /* find out how many bits are set at the beginning
     * of the IP address mask (prefix length)
     */
    mask_bits_left = bits_in_mask( external->mask );

    /* make sure that mask has some bits set
     */
    if( mask_bits_left > MAX_ADDR_BITS )
        return FALSE;

    result = AlterSubnetRecurse( external, &subnet_root,
        addr, MAX_ADDR_BITS, mask_bits_left,
        BITS_PER_ROOT, POINTERS_PER_ROOT, ROOT_INDEX_MASK,
        is_insertion );

    if( result == TRUE )
        /* keep track of how many subnets had this mask length
         */
        if( is_insertion )
            subnets_per_mask_length[ mask_bits_left - 1 ]++;
        else
            subnets_per_mask_length[ mask_bits_left - 1 ]--;

    return result;
}



/* assumes Subnet address and mask fields are in network byte order
 *
 * zero masks not allowed
 *
 * assumes memory pointed to by "external" argument
 * was allocated from heap and can be owned by us afterwards
 *
 * returns TRUE if successful, FALSE otherwise
 *
 * must be followed by a call to InsertSubnet() for the route
 * with the next-shortest mask, since the tree itself cannot
 * find that route
 */
boolean DeleteSubnet( Subnet *external )
{
    return AlterSubnet( external, FALSE );
}



/* assumes Subnet address and mask fields are in network byte order
 *
 * allows zero masks
 *
 * assumes memory pointed to by "external" argument
 * was allocated from heap and can be owned by us afterwards
 *
 * returns TRUE if successful, FALSE otherwise
 */
boolean InsertSubnet( Subnet *external )
{
    Bit32 trial_node;           /* must have more bits than POINTER_DATATYPE */

    /* make sure this subnet can be represented as a leaf pointer
     */
    trial_node = NODE_FROM_EXTERN( external );
    if( trial_node > POINTER_MAX )
    {
        fprintf( stderr, "error: cannot insert subnet %d > %d\n", trial_node, MAX_TREE_NODES );
        return FALSE;
    }

    return AlterSubnet( external, TRUE );
}



/* calls a function for each node, in order of preference for routing
 *
 * note: when we are using direct indexing instead of a patricia tree,
 * this function needs one more argument to tell it size of node
 */
static boolean WalkSubnetsRecurse( WalkSubnetFunction function, void *args,
    POINTER_DATATYPE node, unsigned num_pointers )
{
    int result;
    unsigned count;
    Subnet *external;
    Bit32 *pflag;

    /* if this node is a leaf...
     */
    if( IS_NODE_A_LEAF( node ) )
    {
        /* if this is a NIL pointer, nothing more to do
         */
        external = EXTERN_FROM_NODE( node );
        if( external == NULL )
            return TRUE;

        /* if we already visited this leaf, nothing more to do
         */
        pflag = (Bit32 *) external;
        if( *pflag == DUMP_VISITED_FLAG )
            return TRUE;

        /* give it to the user function and return whatever he does
         */
        result = function( TRUE, external, args );
        if( result )
            result = function( FALSE, external, args );

        /* mark this leaf as visited
         */
        if( dump_fixup_count >= MAX_FIXUPS )
        {
            fprintf( stderr, "out of walk fixup trackers!\n" );
            return FALSE;
        }
        dump_fixup_locations[dump_fixup_count] = pflag;
        dump_fixup_values[dump_fixup_count] = *pflag;
        dump_fixup_count++;
        *pflag = DUMP_VISITED_FLAG;

        return result;
    }


    /* for every one of our child nodes...
     *
     * warning: one child may be listed many times if it is a leaf,
     * and this code doesn't enforce uniqueness!
     */
    for( count=0; count<num_pointers; count++ )
    {
        if( !WalkSubnetsRecurse( function, args, subnet_pool[node].pointers[count], POINTERS_PER_NODE ) )
            return FALSE;
    }

    return TRUE;
}



/* call a user-defined function once for each routing,
 * in order of preference
 *
 * returns TRUE if successful, FALSE if failure
 */
boolean WalkSubnets( WalkSubnetFunction function, void *args )
{
    int result;
    unsigned count;

    /* we must check the no-root error before recursion
     */
    if( subnet_root == NODE_FROM_EXTERN( NULL ) )
        return FALSE;

    /* nothing flagged yet
     */
    dump_fixup_count = 0;

    result = WalkSubnetsRecurse( function, args, subnet_root, POINTERS_PER_ROOT );

    /* undo all our flagging
     */
    for( count=0; count<dump_fixup_count; count++ )
        *dump_fixup_locations[count] = dump_fixup_values[count];

    return result;
}



static int DumpRawSubnetsRecurse( POINTER_DATATYPE node,
    int addr_bits_left, int level_bits, int level_pointers )
{
    unsigned count;
    Subnet *external;
    Bit32 *pflag;
    char temp[ 16 ];
    POINTER_DATATYPE node2, future_node;
    unsigned future_node_num;

    if( IS_NODE_A_LEAF( node ) )
    {
        external = EXTERN_FROM_NODE( node );
        pflag = (Bit32 *) external;
        if( *pflag == DUMP_VISITED_FLAG )
            return TRUE;

        printf( "leaf 0x%X"
#if SUBNET_DUMPS_LINE_NUM
            " BGP line %d,"
#endif
            " %s/%d\n",
            XLATE_PTR(external,external_base),
#if SUBNET_DUMPS_LINE_NUM
            external->line,
#endif
            inet_ntoa( temp, ntohl( external->addr ) ),
            bits_in_mask( external->mask ) );
    }
    else
    {
        pflag = (Bit32 *) (subnet_pool + node);
        if( *pflag == DUMP_VISITED_FLAG )
        {
            fprintf( stderr, "error: DumpRawSubnetsRecurse() already visited node %d\n", node );
            return FALSE;
        }

        printf( "level %d node 0x%X\n", level_from_bits(addr_bits_left,level_bits), XLATE_PTR(PTR_FROM_NODE(node),subnet_base) );
        for( count=0; count<level_pointers; count=future_node_num )
        {
            future_node_num = count + 1;
            node2 = subnet_pool[node].pointers[ count ];
            if( node2 != NODE_FROM_EXTERN( NULL ) )
            {
                while( future_node_num < level_pointers )
                {
                    future_node = subnet_pool[ node ].pointers[ future_node_num ];
                    if( future_node != node2 )
                        break;

                    future_node_num++;
                }

                if( future_node_num - 1 == count )
                    printf( "%d:0x%X\n", count, XLATE_PTR_COND(node2,external_base,subnet_base) );
                else
                    printf( "%d-%d:0x%X\n", count, future_node_num-1, XLATE_PTR_COND(node2,external_base,subnet_base) );
            }
        }

        for( count=0; count<level_pointers; count++ )
        {
            node2 = subnet_pool[ node ].pointers[ count ];
            if( node2 != NODE_FROM_EXTERN( NULL ) )
                if( !DumpRawSubnetsRecurse( node2, addr_bits_left-level_bits, BITS_PER_NODE, POINTERS_PER_NODE ) )
                    return FALSE;
        }
    }

    /* mark this node as visited, if possible
     */
    if( dump_fixup_count >= MAX_FIXUPS )
    {
        fprintf( stderr, "out of dump fixup trackers!\n" );
        return FALSE;
    }
    dump_fixup_locations[dump_fixup_count] = pflag;
    dump_fixup_values[dump_fixup_count] = *pflag;
    dump_fixup_count++;
    *pflag = DUMP_VISITED_FLAG;

    return TRUE;
}



/* used for comparison of internal state with other implementations
 * of same algorithm for same data structures, or different inputs
 *
 * temporarily destroys the first word in each node or leaf, to know
 * whether it was visited yet
 */
void DumpRawSubnets( void )
{
    unsigned count;

    /* make sure the root node exists
     */
    if( subnet_root == NODE_FROM_EXTERN( NULL ) )
    {
        fprintf( stdout, "no SubnetTree's have been allocated yet\n" );
        return;
    }

    /* nothing flagged yet
     */
    dump_fixup_count = 0;

    /* calculate base addresses we want to use for printing pointers
     */
    subnet_base = (POINTER_DATATYPE)(subnet_pool+subnet_root) - DUMP_SUBNET_OFFSET;
    external_base = (POINTER_DATATYPE)first_external - DUMP_EXTERNAL_OFFSET;

    printf( "raw internal SubnetTree state follows:\n" );
    printf( "(0x%.8X was subtracted from all node pointers)\n", subnet_base );
    printf( "(0x%.8X was subtracted from all leaf pointers)\n", external_base );

    DumpRawSubnetsRecurse( subnet_root, MAX_ADDR_BITS, BITS_PER_ROOT, POINTERS_PER_ROOT );

    /* undo all our flagging
     */
    for( count=0; count<dump_fixup_count; count++ )
        *dump_fixup_locations[count] = dump_fixup_values[count];
}



void ShowSubnetStatistics( void )
{
    int count;

    fprintf( stdout, "\n" );
    for( count=3; count>=0; count-- )
        fprintf( stdout, "%4d subnet nodes for byte %d\n", subnet_nodes_per_level[count], count );

#if SUBNET_FIND_MEMREFCNT
    fprintf( stdout, "\n" );
    for( count=3; count>=0; count-- )
        fprintf( stdout, "%8d subnets found with %d memory accesses\n", subnets_found_per_level[count], MAX_SUBNET_MEMREFS-count );
#endif

    fprintf( stdout, "\n" );
    for( count=0; count<MAX_ADDR_BITS; count++ )
        fprintf( stdout, "%5d subnets had mask length %2d\n", subnets_per_mask_length[count], count+1 );
}


#if !NETRAMET & !OCX
void ForceSubnetCaching( void )
{
    unsigned count;
    POINTER_DATATYPE value, value2;

    for( count=0; count<POINTERS_PER_ROOT; count++ )
    {
        value = subnet_pool[ 0 ].pointers[ count ];
        value2 = value;
    }
}
#endif


/* tells this module the base address of all Subnet pointers
 * that will be passed to InsertSubnet, which assumes they
 * are all part of a contiguous array
 */
void SetSubnetExternalBase( Subnet *base )
{
    first_external = base;
}