routert.cc

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

    // update port count
    if (_elements[e]->_noutputs == port + 1)
	update_noutputs(e);
}

void
RouterT::unlink_connection_to(int c)
{
    int e = _conn[c].to_eindex();
    int port = _conn[c].to_port();

    // find previous connection
    int prev = -1;
    int trav = _first_conn[e][end_to];
    while (trav >= 0 && trav != c) {
	prev = trav;
	trav = _conn[trav].next_to();
    }
    assert(trav == c);

    // unlink this connection
    if (prev < 0)
	_first_conn[e][end_to] = _conn[trav].next_to();
    else
	_conn[prev]._next[end_to] = _conn[trav].next_to();

    // update port count
    if (_elements[e]->_ninputs == port + 1)
	update_ninputs(e);
}

void
RouterT::free_connection(int c)
{
    _conn[c]._end[end_from].element = 0;	// kill();
    _conn[c]._next[end_from] = _free_conn;
    _free_conn = c;
}

void
RouterT::kill_connection(const conn_iterator &ci)
{
    if (ci != end_connections()) {
	assert(ci._conn && ci._conn >= _conn.begin() && ci._conn < _conn.end());
	int c = ci._conn - _conn.begin();
	if (ci->live()) {
	    unlink_connection_from(c);
	    unlink_connection_to(c);
	    free_connection(c);
	}
    }
}

void
RouterT::kill_bad_connections()
{
    for (conn_iterator ci = begin_connections(); ci != end_connections(); ++ci)
	if (ci->from_element()->dead() || ci->to_element()->dead())
	    kill_connection(ci);
}

void
RouterT::change_connection_from(int c, PortT h)
{
    assert(h.router() == this);
    unlink_connection_from(c);

    _conn[c]._end[end_from] = h;
    if (h.port >= h.element->_noutputs)
	h.element->_noutputs = h.port + 1;

    int ei = h.eindex();
    _conn[c]._next[end_from] = _first_conn[ei][end_from];
    _first_conn[ei][end_from] = c;
}

void
RouterT::change_connection_to(int c, PortT h)
{
    assert(h.router() == this);
    unlink_connection_to(c);

    _conn[c]._end[end_to] = h;
    if (h.port >= h.element->ninputs())
	h.element->set_ninputs(h.port + 1);

    int ei = h.eindex();
    _conn[c]._next[end_to] = _first_conn[ei][end_to];
    _first_conn[ei][end_to] = c;
}

RouterT::conn_iterator
RouterT::begin_connections_touching(int eindex, int port, bool isoutput) const
{
    assert(eindex >= 0 && eindex < nelements());
    int c = _first_conn[eindex][isoutput];
    if (port >= 0) {
	while (c >= 0 && _conn[c].port(isoutput) != port)
	    c = _conn[c].next(isoutput);
	port = (isoutput ? port + 2 : -port - 2);
    } else
	port = (isoutput ? 1 : -1);
    return (c >= 0 ? conn_iterator(&_conn[c], port) : conn_iterator());
}

void
RouterT::conn_iterator::complex_step(const RouterT *router)
{
    int c = _conn - router->_conn.begin();
    assert(c >= 0 && c < router->_conn.size());
    if (_by == 0)
	++c;
    else if (_by >= 1) {
	c = _conn->next_from();
	while (c >= 0 && _by > 1 && router->_conn[c].from_port() != _by - 2)
	    c = router->_conn[c].next_from();
    } else {
	c = _conn->next_to();
	while (c >= 0 && _by < -1 && router->_conn[c].to_port() != -_by - 2)
	    c = router->_conn[c].next_to();
    }
    if (c == router->_conn.size() || c < 0)
	_conn = 0;
    else
	_conn = &router->_conn[c];
}


int
RouterT::find_connection(const PortT &hfrom, const PortT &hto) const
{
    assert(hfrom.router() == this && hto.router() == this);
    int c = _first_conn[hfrom.eindex()][end_from];
    while (c >= 0) {
	if (_conn[c].from() == hfrom && _conn[c].to() == hto)
	    break;
	c = _conn[c].next_from();
    }
    return c;
}

void
RouterT::find_connections_touching(ElementT *e, bool isoutput, Vector<int> &v) const
{
    assert(e->router() == this);
    int c = _first_conn[e->eindex()][isoutput];
    v.clear();
    while (c >= 0) {
	v.push_back(c);
	c = _conn[c].next(isoutput);
    }
}

int
RouterT::find_connection_id_touching(const PortT &port, bool isoutput) const
{
    assert(port.router() == this);
    int c = _first_conn[port.eindex()][isoutput];
    int p = port.port;
    int result = -1;
    while (c >= 0) {
	if (_conn[c].port(isoutput) == p) {
	    if (result == -1)
		result = c;
	    else
		return -2;
	}
	c = _conn[c].next(isoutput);
    }
    return result;
}

void
RouterT::find_connections_touching(const PortT &port, bool isoutput, Vector<PortT> &v, bool clear) const
{
    assert(port.router() == this);
    int c = _first_conn[port.eindex()][isoutput];
    int p = port.port;
    if (clear)
	v.clear();
    while (c >= 0) {
	if (_conn[c].port(isoutput) == p)
	    v.push_back(_conn[c].end(!isoutput));
	c = _conn[c].next(isoutput);
    }
}

void
RouterT::find_connections_touching(const PortT &port, bool isoutput, Vector<int> &v) const
{
    assert(port.router() == this);
    int c = _first_conn[port.eindex()][isoutput];
    int p = port.port;
    v.clear();
    while (c >= 0) {
	if (_conn[c].port(isoutput) == p)
	    v.push_back(c);
	c = _conn[c].next(isoutput);
    }
}

void
RouterT::find_connection_vector_touching(ElementT *e, bool isoutput, Vector<int> &v) const
{
    assert(e->router() == this);
    v.clear();
    int c = _first_conn[e->eindex()][isoutput];
    while (c >= 0) {
	int p = _conn[c].port(isoutput);
	if (p >= v.size())
	    v.resize(p + 1, -1);
	if (v[p] >= 0)
	    v[p] = -2;
	else
	    v[p] = c;
	c = _conn[c].next(isoutput);
    }
}

bool
RouterT::insert_before(const PortT &inserter, const PortT &h)
{
    if (!add_connection(inserter, h))
	return false;

    int i = _first_conn[h.eindex()][end_to];
    while (i >= 0) {
	int next = _conn[i].next_to();
	if (_conn[i].to() == h && connection_live(i)
	    && _conn[i].from() != inserter)
	    change_connection_to(i, inserter);
	i = next;
    }
    return true;
}

bool
RouterT::insert_after(const PortT &inserter, const PortT &h)
{
    if (!add_connection(h, inserter))
	return false;

    int i = _first_conn[h.eindex()][end_from];
    while (i >= 0) {
	int next = _conn[i].next_from();
	if (_conn[i].from() == h && _conn[i].to() != inserter)
	    change_connection_from(i, inserter);
	i = next;
    }
    return true;
}


void
RouterT::add_tunnel(const String &namein, const String &nameout,
		    const LandmarkT &landmark, ErrorHandler *errh)
{
    if (!errh)
	errh = ErrorHandler::silent_handler();

    ElementClassT *tun = ElementClassT::tunnel_type();
    ElementT *ein = get_element(namein, tun, String(), landmark);
    ElementT *eout = get_element(nameout, tun, String(), landmark);

    bool ok = true;
    if (!ein->tunnel()) {
	ElementT::redeclaration_error(errh, "element", namein, landmark, ein->landmark());
	ok = false;
    }
    if (!eout->tunnel()) {
	ElementT::redeclaration_error(errh, "element", nameout, landmark, eout->landmark());
	ok = false;
    }
    if (ein->tunnel_output()) {
	ElementT::redeclaration_error(errh, "connection tunnel input", namein, landmark, ein->landmark());
	ok = false;
    }
    if (eout->tunnel_input()) {
	ElementT::redeclaration_error(errh, "connection tunnel output", nameout, landmark, eout->landmark());
	ok = false;
    }
    if (ok) {
	ein->_tunnel_output = eout;
	eout->_tunnel_input = ein;
    }
}


//
// REQUIREMENTS
//

void
RouterT::add_requirement(const String &s)
{
    _requirements.push_back(s);
}

void
RouterT::remove_requirement(const String &s)
{
    for (int i = 0; i < _requirements.size(); i++)
	if (_requirements[i] == s) {
	    // keep requirements in order
	    for (int j = i + 1; j < _requirements.size(); j++)
		_requirements[j-1] = _requirements[j];
	    _requirements.pop_back();
	    return;
	}
}


void
RouterT::add_archive(const ArchiveElement &ae)
{
    int &i = _archive_map[ae.name];
    if (i >= 0)
	_archive[i] = ae;
    else {
	i = _archive.size();
	_archive.push_back(ae);
    }
}


void
RouterT::remove_duplicate_connections()
{
    // 5.Dec.1999 - This function dominated the running time of click-xform.
    // Use an algorithm faster on the common case (few connections per
    // element).

    int nelem = _elements.size();
    Vector<int> removers;

    for (int i = 0; i < nelem; i++) {
	int trav = _first_conn[i][end_from];
	int next = 0;		// initialize here to avoid gcc warnings
	while (trav >= 0) {
	    int prev = _first_conn[i][end_from];
	    int trav_port = _conn[trav].from().port;
	    next = _conn[trav].next_from();
	    while (prev >= 0 && prev != trav) {
		if (_conn[prev].from().port == trav_port
		    && _conn[prev].to() == _conn[trav].to()) {
		    kill_connection(conn_iterator(&_conn[trav], 0));
		    goto duplicate;
		}
		prev = _conn[prev].next_from();
	    }
	  duplicate:
	    trav = next;
	}
    }
}


void
RouterT::remove_dead_elements(ErrorHandler *errh)
{
    if (!errh)
	errh = ErrorHandler::silent_handler();
    int nelements = _elements.size();

    // change hookup
    kill_bad_connections();

    // find new element indexes
    Vector<int> new_eindex(nelements, 0);
    int j = 0;
    for (int i = 0; i < nelements; i++)
	if (_elements[i]->dead())
	    new_eindex[i] = -1;
	else
	    new_eindex[i] = j++;
    int new_nelements = j;

    // compress element arrays
    for (int i = 0; i < nelements; i++) {
	j = new_eindex[i];
	if (j < 0) {
	    _element_name_map.set(_elements[i]->name(), -1);
	    delete _elements[i];
	} else if (j != i) {
	    _element_name_map.set(_elements[i]->name(), j);
	    _elements[j] = _elements[i];
	    _elements[j]->_eindex = j;
	    _first_conn[j] = _first_conn[i];
	}
    }

    // resize element arrays
    _elements.resize(new_nelements);
    _first_conn.resize(new_nelements);
    _n_live_elements = new_nelements;
    _free_element = 0;
}

void
RouterT::free_element(ElementT *e)
{
    assert(e->router() == this);
    int ei = e->eindex();

    // first, remove bad connections from other elements' connection lists
    Vector<int> bad_from, bad_to;
    for (int c = _first_conn[ei][end_from]; c >= 0; c = _conn[c].next_from())
	unlink_connection_to(c);
    for (int c = _first_conn[ei][end_to]; c >= 0; c = _conn[c].next_to())
	unlink_connection_from(c);

    // now, free all of this element's connections
    for (int c = _first_conn[ei][end_from]; c >= 0; ) {
	int next = _conn[c].next_from();
	if (_conn[c].to_eindex() != ei)
	    free_connection(c);
	c = next;
    }
    for (int c = _first_conn[ei][end_to]; c >= 0; ) {
	int next = _conn[c].next_to();
	free_connection(c);
	c = next;
    }
    _first_conn[ei] = Pair(-1, -1);

    // finally, free the element itself
    if (_element_name_map[e->name()] == ei)
	_element_name_map.set(e->name(), -1);
    e->simple_kill();
    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();