/*
 * Copyright (c) 1998 Regents of The University of Michigan.
 * All Rights Reserved.  See COPYRIGHT.
 */

/***********          schedule.c          ***********/

#include <sys/types.h>
#include <sys/time.h>
#include <netinet/in.h>

#include <stdio.h>

#include "nefu.h"


    /* any node that needs to be added to the route to the current test
     * is placed on the stack using this function.
     */

    void
push_route( struct schedule *sched, struct test *t_node )
{
    if ( sched->s_head == NULL ) {
	/* no other nodes in route right now */
	sched->s_head = t_node;
	sched->s_tail = t_node;
	t_node->t_route_next = NULL;
	t_node->t_route_prev = NULL;
	return;
    }

    /* at least one other node in route */
    t_node->t_route_prev = sched->s_tail;
    t_node->t_route_next = NULL;
    sched->s_tail->t_route_next = t_node;
    sched->s_tail = t_node;
}


    /* pops node from "bottom" of route, and returns 0.  Returns 1 if there
     * is no node to be popped.
     */

    int
pop_route( struct schedule *sched )
{
    if ( sched->s_head == NULL ) {
	/* no nodes in route */
	return( 1 );
    }

    if ( sched->s_head == sched->s_tail ) {
	/* there is only one node in the route */
	sched->s_head = NULL;
	sched->s_tail = NULL;

    } else {
	/* more than one node in route */
	sched->s_tail = sched->s_tail->t_route_prev;
	sched->s_tail->t_route_next->t_route_prev = NULL;
	sched->s_tail->t_route_next = NULL;
    }
    return( 0 );
}


    /* Leaf nodes are:
     *  1.  nodes with no children.
     *	2.  down (tree being "trimmed" at their level)
     */

    struct test *
find_leaf( struct schedule *s, struct test *t )
{
    for ( ; ; ) {
	if (( t->t_child == NULL ) || (( t->t_status & T_DOWN_MASK ) != 0 )) {
	    return( t );
	}

	push_route( s, t );
	t = t->t_child;
    }
}


    /* find the next leaf node in the graph, if one exists */

    void
next_leaf_node( struct schedule *s )
{
    if ( s->s_test == NULL ) {
	s->s_test = find_leaf( s, root_nodes );

    } else {
	if ( s->s_test->t_child != NULL ) {
	    if (( s->s_test->t_status & T_DOWN_MASK ) == 0 ) {
		s->s_test = find_leaf( s, s->s_test );
		return;
	    }
	}

	while ( s->s_test != NULL ) {
	    if ( s->s_test->t_peer != NULL ) {
		s->s_test = find_leaf( s, s->s_test->t_peer );
		return;
	    }

	    s->s_test = s->s_tail;
	    pop_route( s );
	}
    }
}


    /* recursive function.  return zero if a branch was not reachable */

    int
was_reachable( struct test *t )
{
    if (( t->t_status == T_UP ) || ( t->t_status == T_DOWN )) {
	return( 1 );
    }

    /* if we're NO_DNS, see if anything beneath us is reachable */
    if ( t->t_status == T_NO_DNS ) {
	if ( t->t_child != NULL ) {
	    if ( was_reachable( t->t_child ) != 0 ) {
		return( 1 );
	    }
	}
    }

    /* any peer, or child of peer reachable? */
    if ( t->t_peer != NULL ) {
	return( was_reachable( t->t_peer ));
    }

    return( 0 );
}


    /* an implicit leaf node is needed for the lowest level of tests that
     * are all MAYBE_DOWN or NO_DNS.  their implicit leaf is the first
     * parent who is not NO_DNS, if one exists.
     */

    struct test *
implicit_leaf( struct schedule *s )
{
    struct test			*t;
    
    t = NULL;

    /* check for leaf if s->s_test is the first leaf node on it's level */
    if ( s->s_test->t_prev == NULL ) {

	/* return if anything on our level or below was reachable last pass */
	if ( was_reachable( s->s_test ) != 0 ) {
	    return( NULL );
	}

	/* find valid implicit leaf parent */
	for ( t = s->s_test->t_parent; t != NULL; t = t->t_parent ) {
	    if ( t->t_status != T_NO_DNS ) {

		/* has our implicit leaf has already been tested this pass? */
		if ( t->t_tested == s->s_pass ) {
		    return( NULL );
		} else {
		    break;
		}
	    }
	}
    }

    return( t );
}

    
    /* if s->s_test starts as NULL, it is the begenning of a new pass.
     * increase the pass counter and traverse the graph.
     *
     * we never allow s->s_test to be a test with NO_DNS.
     *
     * when we come to the end of the graph, s->s_test will be returned as
     * NULL.  when schedule is called again, it's the start of a new pass.
     *
     * an implicit leaf is needed if all tests at a given level or below are
     * either NO_DNS or MAYBE_DOWN.  test the implicit leaf once every pass.
     */

    void
schedule( struct schedule *s )
{
    struct test			*il;

    if ( s->s_test == NULL ) {
	s->s_pass++;
    }

    /* get the next leaf node with DNS, if one exists */
    for ( ;; ) {
	next_leaf_node( s );

	/* are we at the end of a pass? */
	if ( s->s_test == NULL ) {
	    return;
	}

	/* see if we need an implicit leaf node */
	if (( il = implicit_leaf( s )) != NULL ) {
	    /* test il if it hasn't been tested this pass */
	    if ( il->t_tested != s->s_pass ) {
		/* schedule il  */
		while ( s->s_test != il ) {
		    s->s_test = s->s_tail;
		    pop_route( s );
		}
		return;
	    }
	}

	/* if this test has DNS, we're done */
	if ( s->s_test->t_status != T_NO_DNS ) {
	    return;
	}
    }
}