routert.cc

COPE the first practical network coding scheme which is developped on click

    e->_tunnel_input = _free_element;
    _free_element = e;
    _n_live_elements--;

    check();
}

void
RouterT::free_dead_elements()
{
    int nelements = _elements.size();
    Vector<int> new_eindex(nelements, 0);

    // mark saved findexes
    for (int i = 0; i < nelements; i++)
	if (_elements[i]->dead())
	    new_eindex[i] = -1;

    // don't free elements that have already been freed!!
    for (ElementT *e = _free_element; e; e = e->tunnel_input())
	new_eindex[e->eindex()] = 0;

    // get rid of connections to and from dead elements
    kill_bad_connections();

    // free elements
    for (int i = 0; i < nelements; i++)
	if (new_eindex[i] < 0) {
	    ElementT *e = _elements[i];
	    if (_element_name_map[e->name()] == i)
		_element_name_map.insert(e->name(), -1);
	    assert(e->dead());
	    e->_tunnel_input = _free_element;
	    _free_element = e;
	    _n_live_elements--;
	}
}


void
RouterT::expand_into(RouterT *tor, const String &prefix, const VariableEnvironment &env, ErrorHandler *errh)
{
    assert(tor != this);

    int nelements = _elements.size();
    Vector<ElementT *> new_e(nelements, 0);

    // add tunnel pairs and expand below
    for (int i = 0; i < nelements; i++)
	if (_elements[i]->live())
	    new_e[i] = ElementClassT::expand_element(_elements[i], tor, prefix, env, errh);

    // add hookup
    int nh = _conn.size();
    for (int i = 0; i < nh; i++) {
	const PortT &hf = _conn[i].from(), &ht = _conn[i].to();
	tor->add_connection(PortT(new_e[hf.eindex()], hf.port),
			    PortT(new_e[ht.eindex()], ht.port),
			    _conn[i].landmark());
    }

    // add requirements
    for (int i = 0; i < _requirements.size(); i++)
	tor->add_requirement(_requirements[i]);

    // add archive elements
    for (int i = 0; i < _archive.size(); i++) {
	const ArchiveElement &ae = _archive[i];
	if (ae.live() && ae.name != "config") {
	    if (tor->archive_index(ae.name) >= 0)
		errh->error("expansion confict: two archive elements named '%s'", ae.name.c_str());
	    else
		tor->add_archive(ae);
	}
    }
}


static const int PORT_NOT_EXPANDED = -1;
static const int PORT_EXPANDING = -2;

void
RouterT::expand_tunnel(Vector<PortT> *port_expansions,
		       const Vector<PortT> &ports,
		       bool is_output, int which,
		       ErrorHandler *errh) const
{
    Vector<PortT> &expanded = port_expansions[which];

    // quit if circular or already expanded
    if (expanded.size() != 1 || expanded[0].port != PORT_NOT_EXPANDED)
	return;

    // expand if not expanded yet
    expanded[0].port = PORT_EXPANDING;

    const PortT &me = ports[which];
    ElementT *other_elt = (is_output ? me.element->tunnel_input() : me.element->tunnel_output());
    
    // find connections from tunnel input
    Vector<PortT> connections;
    if (is_output)
	find_connections_to(PortT(other_elt, me.port), connections);
    else			// or to tunnel output
	find_connections_from(PortT(other_elt, me.port), connections);

    // give good errors for unused or nonexistent compound element ports
    if (!connections.size()) {
	ElementT *in_elt = (is_output ? other_elt : me.element);
	ElementT *out_elt = (is_output ? me.element : other_elt);
	String in_name = in_elt->name();
	String out_name = out_elt->name();
	if (in_name + "/input" == out_name) {
	    const char *message = (is_output ? "'%s' input %d unused"
				   : "'%s' has no input %d");
	    errh->lerror(in_elt->landmark(), message, in_name.cc(), me.port);
	} else if (in_name == out_name + "/output") {
	    const char *message = (is_output ? "'%s' has no output %d"
				   : "'%s' output %d unused");
	    errh->lerror(out_elt->landmark(), message, out_name.cc(), me.port);
	} else {
	    errh->lerror(other_elt->landmark(),
			 "tunnel '%s -> %s' %s %d unused",
			 in_name.cc(), out_name.cc(),
			 (is_output ? "input" : "output"), me.port);
	}
    }

    // expand them
    Vector<PortT> store;
    for (int i = 0; i < connections.size(); i++) {
	// if connected to another tunnel, expand that recursively
	if (connections[i].element->tunnel()) {
	    int x = connections[i].index_in(ports);
	    if (x >= 0) {
		expand_tunnel(port_expansions, ports, is_output, x, errh);
		const Vector<PortT> &v = port_expansions[x];
		if (v.size() > 1 || (v.size() == 1 && v[0].port >= 0))
		    for (int j = 0; j < v.size(); j++)
			store.push_back(v[j]);
		continue;
	    }
	}
	// otherwise, just store it in list of connections
	store.push_back(connections[i]);
    }

    // save results
    expanded.swap(store);
}

void
RouterT::remove_tunnels(ErrorHandler *errh)
{
    if (!errh)
	errh = ErrorHandler::silent_handler();

    // find tunnel connections, mark connections by setting index to 'magice'
    Vector<PortT> inputs, outputs;
    int nhook = _conn.size();
    for (int i = 0; i < nhook; i++) {
	const ConnectionT &c = _conn[i];
	if (c.dead())
	    continue;
	if (c.from_element()->tunnel() && c.from_element()->tunnel_input())
	    (void) c.from().force_index_in(outputs);
	if (c.to_element()->tunnel() && c.to_element()->tunnel_output())
	    (void) c.to().force_index_in(inputs);
    }

    // expand tunnels
    int nin = inputs.size(), nout = outputs.size();
    Vector<PortT> *in_expansions = new Vector<PortT>[nin];
    Vector<PortT> *out_expansions = new Vector<PortT>[nout];
    // initialize to placeholders
    for (int i = 0; i < nin; i++)
	in_expansions[i].push_back(PortT(0, PORT_NOT_EXPANDED));
    for (int i = 0; i < nout; i++)
	out_expansions[i].push_back(PortT(0, PORT_NOT_EXPANDED));
    // actually expand
    for (int i = 0; i < nin; i++)
	expand_tunnel(in_expansions, inputs, false, i, errh);
    for (int i = 0; i < nout; i++)
	expand_tunnel(out_expansions, outputs, true, i, errh);

    // get rid of connections to tunnels
    int nelements = _elements.size();
    int old_nhook = _conn.size();
    for (int i = 0; i < old_nhook; i++) {
	const PortT &hf = _conn[i].from(), &ht = _conn[i].to();

	// skip if uninteresting
	if (hf.dead() || !hf.element->tunnel() || ht.element->tunnel())
	    continue;
	int x = hf.index_in(outputs);
	if (x < 0)
	    continue;

	// add cross product
	// hf, ht are invalidated by adding new connections!
	PortT safe_ht(ht);
	String landmark = _conn[i].landmark(); // must not be reference!
	const Vector<PortT> &v = out_expansions[x];
	for (int j = 0; j < v.size(); j++)
	    add_connection(v[j], safe_ht, landmark);
    }
    
    // kill elements with tunnel type
    // but don't kill floating tunnels (like input & output)
    for (int i = 0; i < nelements; i++)
	if (_elements[i]->tunnel()
	    && (_elements[i]->tunnel_output() || _elements[i]->tunnel_input()))
	    _elements[i]->kill();

    // actually remove tunnel connections and elements
    remove_duplicate_connections();
    free_dead_elements();
}


void
RouterT::remove_compound_elements(ErrorHandler *errh)
{
    int nelements = _elements.size();
    VariableEnvironment env;
    for (int i = 0; i < nelements; i++)
	if (_elements[i]->live()) // allow deleted elements
	    ElementClassT::expand_element(_elements[i], this, String(), env, errh);
}

void
RouterT::flatten(ErrorHandler *errh)
{
    check();
    //String s = configuration_string(); fprintf(stderr, "1.\n%s\n\n", s.cc());
    remove_compound_elements(errh);
    //s = configuration_string(); fprintf(stderr, "2.\n%s\n\n", s.cc());
    remove_tunnels(errh);
    //s = configuration_string(); fprintf(stderr, "3.\n%s\n\n", s.cc());
    remove_dead_elements();
    //s = configuration_string(); fprintf(stderr, "4.\n%s\n\n", s.cc());
    compact_connections();
    //s = configuration_string(); fprintf(stderr, "5.\n%s\n\n", s.cc());
    _declared_type_map.clear();
    _declared_types.clear();
    check();
}


void
RouterT::const_iterator::step(const RouterT *r, int eindex)
{
    int n = (r ? r->nelements() : -1);
    while (eindex < n && (_e = r->element(eindex), _e->dead()))
	eindex++;
    if (eindex >= n)
	_e = 0;
}

void
RouterT::const_type_iterator::step(const RouterT *r, ElementClassT *type, int eindex)
{
    assert(type);
    int n = (r ? r->nelements() : -1);
    while (eindex < n && (_e = r->element(eindex), _e->type() != type))
	eindex++;
    if (eindex >= n)
	_e = 0;
}


//
// TYPE METHODS
//

const ElementTraits *
RouterT::find_traits() const
{
    if (ElementMap::default_map()) {
	ErrorHandler *errh = ErrorHandler::silent_handler();
	ProcessingT pt(this, errh);
	*(_traits.component(Traits::D_PROCESSING)) = pt.compound_processing_code();
	*(_traits.component(Traits::D_FLOW_CODE)) = pt.compound_flow_code(errh);
    }
    return &_traits;
}

int
RouterT::finish_type(ErrorHandler *errh)
{
    if (!errh)
	errh = ErrorHandler::silent_handler();
    int before_nerrors = errh->nerrors();

    if (ElementT *einput = element("input")) {
	_ninputs = einput->noutputs();
	if (einput->ninputs())
	    errh->lerror(_type_landmark, "'%s' pseudoelement 'input' may only be used as output", printable_name_c_str());

	if (_ninputs) {
	    Vector<int> used;
	    find_connection_vector_from(einput, used);
	    assert(used.size() == _ninputs);
	    for (int i = 0; i < _ninputs; i++)
		if (used[i] == -1)
		    errh->lerror(_type_landmark, "compound element '%s' input %d unused", printable_name_c_str(), i);
	}
    } else
	_ninputs = 0;

    if (ElementT *eoutput = element("output")) {
	_noutputs = eoutput->ninputs();
	if (eoutput->noutputs())
	    errh->lerror(_type_landmark, "'%s' pseudoelement 'output' may only be used as input", printable_name_c_str());

	if (_noutputs) {
	    Vector<int> used;
	    find_connection_vector_to(eoutput, used);
	    assert(used.size() == _noutputs);
	    for (int i = 0; i < _noutputs; i++)
		if (used[i] == -1)
		    errh->lerror(_type_landmark, "compound element '%s' output %d unused", printable_name_c_str(), i);
	}
    } else
	_noutputs = 0;

    // resolve anonymous element names
    deanonymize_elements();

    return (errh->nerrors() == before_nerrors ? 0 : -1);
}

void
RouterT::set_overload_type(ElementClassT *t)
{
    assert(!_overload_type);
    _overload_type = t;
    if (_overload_type)
	_overload_type->use();
}

ElementClassT *
RouterT::resolve(int ninputs, int noutputs, Vector<String> &args, ErrorHandler *errh, const String &landmark)
{
    // Try to return an element class, even if it is wrong -- the error
    // messages are friendlier
    RouterT *r = this;
    RouterT *closest = 0;

    while (1) {
	if (r->_ninputs == ninputs && r->_noutputs == noutputs
	    && cp_assign_arguments(args, r->_formal_types, &args) >= 0)
	    return r;
	else if (cp_assign_arguments(args, r->_formal_types) >= 0)
	    closest = r;

	ElementClassT *overload = r->_overload_type;
	if (!overload)
	    break;
	else if (RouterT *next = overload->cast_router())
	    r = next;
	else if (ElementClassT *result = overload->resolve(ninputs, noutputs, args, errh, landmark))
	    return result;
	else
	    break;
    }

    errh->lerror(landmark, "no match for '%s'", ElementClassT::unparse_signature(name(), 0, args.size(), ninputs, noutputs).c_str());
    ContextErrorHandler cerrh(errh, "candidates are:", "  ");
    for (r = this; r; r = (r->_overload_type ? r->_overload_type->cast_router() : 0))
	cerrh.lmessage(r->landmark(), "%s", r->unparse_signature().c_str());
    if (closest)
	cp_assign_arguments(args, closest->_formal_types, &args);
    return closest;
}

ElementT *
RouterT::complex_expand_element(
	ElementT *compound, const String &, Vector<String> &args,
	RouterT *tor, const String &prefix,
	const VariableEnvironment &env, ErrorHandler *errh)
{
    RouterT *fromr = compound->router();
    assert(fromr != this && tor != this);
    assert(!_circularity_flag);
    // ensure we don't delete ourselves before we're done!
    use();
    _circularity_flag = true;

    // parse configuration string
    int nargs = _formals.size();
    if (args.size() != nargs) {
	const char *whoops = (args.size() < nargs ? "few" : "many");
	String signature;
	for (int i = 0; i < nargs; i++) {
	    if (i) signature += ", ";
	    signature += _formals[i];
	}
	if (errh)
	    errh->lerror(compound->landmark(),
			 "too %s arguments to compound element '%s(%s)'",
			 whoops, printable_name_c_str(), signature.c_str());
	for (int i = args.size(); i < nargs; i++)
	    args.push_back("");
    }

    // create prefix
    assert(compound->name());
    VariableEnvironment new_env(env);
    String new_prefix = prefix + compound->name(); // includes previous prefix
    if (new_prefix.back() != '/')
	new_prefix += '/';
    new_env.limit_depth(_declaration_depth);
    new_env.enter(_formals, args, _declaration_depth);

    // create input/output tunnels
    if (fromr == tor)
	compound->set_type(tunnel_type());
    tor->add_tunnel(prefix + compound->name(), new_prefix + "input", compound->landmark(), errh);
    tor->add_tunnel(new_prefix + "output", prefix + compound->name(), compound->landmark(), errh);
    ElementT *new_e = tor->element(prefix + compound->name());

    // dump compound router into 'tor'
    expand_into(tor, new_prefix, new_env, errh);

    // yes, we expanded it
    _circularity_flag = false;
    unuse();
    return new_e;
}

String
RouterT::unparse_signature() const
{
    return ElementClassT::unparse_signature(name(), &_formal_types, -1, ninputs(), noutputs());
}


#include <click/vector.cc>