routert.cc

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

    // 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.set(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, VariableEnvironment &env, ErrorHandler *errh)
{
    assert(tor != this);
    assert(!prefix || prefix.back() == '/');

    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].landmarkt());
    }

    // 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.c_str(), 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.c_str(), me.port);
	} else {
	    errh->lerror(other_elt->landmark(),
			 "tunnel %<%s -> %s%> %s %d unused",
			 in_name.c_str(), out_name.c_str(),
			 (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);
	LandmarkT landmark = _conn[i].landmarkt(); // 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]->simple_kill();

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


void
RouterT::remove_compound_elements(ErrorHandler *errh, bool expand_vars)
{
    int nelements = _elements.size();

    // construct a fake VariableEnvironment so we preserve variable names
    // even in the presence of ${NAME-DEFAULT}
    VariableEnvironment ve(0);
    for (int i = 0; i < _scope.size(); i++)
	if (expand_vars)
	    ve.define(_scope.name(i), cp_expand(_scope.value(i), ve), true);
	else
	    ve.define(_scope.name(i), String("$") + _scope.name(i), true);

    for (int i = 0; i < nelements; i++)
	if (_elements[i]->live()) // allow deleted elements
	    ElementClassT::expand_element(_elements[i], this, String(), ve, errh);
}

void
RouterT::flatten(ErrorHandler *errh, bool expand_vars)
{
    check();
    //String s = configuration_string(); fprintf(stderr, "1.\n%s\n\n", s.c_str());
    remove_compound_elements(errh, expand_vars);
    //s = configuration_string(); fprintf(stderr, "2.\n%s\n\n", s.c_str());
    remove_tunnels(errh);
    //s = configuration_string(); fprintf(stderr, "3.\n%s\n\n", s.c_str());
    remove_dead_elements();
    //s = configuration_string(); fprintf(stderr, "4.\n%s\n\n", s.c_str());
    compact_connections();
    //s = configuration_string(); fprintf(stderr, "5.\n%s\n\n", s.c_str());
    _declared_type_map.clear();
    _declared_types.clear();
    if (expand_vars)
	_scope.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, int eindex)
{
    int n = (r ? r->nelements() : -1);
    while (eindex < n && (_e = r->element(eindex), _e->type() != _t))
	eindex++;
    if (eindex >= n)
	_e = 0;
}


//
// TYPE METHODS
//

const ElementTraits *
RouterT::find_traits(ElementMap *emap) const
{
    // Do not resolve agnostics to push, or the flow code will be wrong.
    ProcessingT pt(false, const_cast<RouterT *>(this), emap);
    *(_traits.component(Traits::D_PORT_COUNT)) = pt.compound_port_count_code();
    *(_traits.component(Traits::D_PROCESSING)) = pt.compound_processing_code();
    *(_traits.component(Traits::D_FLOW_CODE)) = pt.compound_flow_code();
    return &_traits;
}

int
RouterT::finish_type(ErrorHandler *errh)
{
    LocalErrorHandler lerrh(errh);

    if (ElementT *einput = element("input")) {
	_ninputs = einput->noutputs();
	if (einput->ninputs())
	    lerrh.lerror(_type_landmark.str(), "%<%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)
		    lerrh.lerror(_type_landmark.str(), "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())
	    lerrh.lerror(_type_landmark.str(), "%<%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)
		    lerrh.lerror(_type_landmark.str(), "compound element %<%s%> output %d unused", printable_name_c_str(), i);
	}
    } else
	_noutputs = 0;

    // resolve anonymous element names
    deanonymize_elements();

    return (lerrh.nerrors() ? -1 : 0);
}

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

inline int
RouterT::assign_arguments(const Vector<String> &args, Vector<String> *values) const
{
    return cp_assign_arguments(args, _scope.values().begin(), _scope.values().begin() + _nformals, values);
}

bool
RouterT::need_resolve() const
{
    return true;		// always resolve compound b/c of arguments
}

bool
RouterT::overloaded() const
{
    return _overload_type != 0;
}

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

    while (1) {
	nct++;
	if (r->_ninputs == ninputs && r->_noutputs == noutputs
	    && r->assign_arguments(args, &args) >= 0)
	    return r;
	else if (r->assign_arguments(args, 0) >= 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;
    }

    if (nct != 1 || !closest) {
	errh->lerror(landmark.decorated_str(), "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->decorated_landmark(), "%s", r->unparse_signature().c_str());
    }
    if (closest)
	closest->assign_arguments(args, &args);
    return closest;
}

void
RouterT::create_scope(const Vector<String> &args,
		      const VariableEnvironment &env,
		      VariableEnvironment &new_env)
{
    assert(&new_env != &env);
    new_env = VariableEnvironment(env.parent_of(_scope.depth()));
    for (int i = 0; i < _nformals && i < args.size(); i++)
	new_env.define(_scope.name(i), args[i], true);
    for (int i = args.size(); i < _nformals; i++)
	new_env.define(_scope.name(i), String(), true);
    for (int i = _nformals; i < _scope.size(); i++)
	new_env.define(_scope.name(i), cp_expand(_scope.value(i), env), true);
}

ElementT *
RouterT::complex_expand_element(
	ElementT *compound, const 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 = _nformals;
    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 += _scope.name(i);
	}
	if (errh)
	    errh->lerror(compound->landmark(),
			 "too %s arguments to compound element %<%s(%s)%>",
			 whoops, printable_name_c_str(), signature.c_str());
    }

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

    // create input/output tunnels
    if (fromr == tor)
	compound->set_type(tunnel_type());
    tor->add_tunnel(prefix + compound->name(), new_prefix + "input", compound->landmarkt(), errh);
    tor->add_tunnel(new_prefix + "output", prefix + compound->name(), compound->landmarkt(), 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(), &_scope.values(), -1, ninputs(), noutputs());
}