routert.cc

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

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

    // unlink this connection
    if (prev < 0)
	_first_conn[e].from = _conn[trav].next_from();
    else
	_conn[prev]._next_from = _conn[trav].next_from();

    // 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].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].to = _conn[trav].next_to();
    else
	_conn[prev]._next_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].kill();
    _conn[c]._next_from = _free_conn;
    _free_conn = c;
}

void
RouterT::kill_connection(int c)
{
    if (connection_live(c)) {
	unlink_connection_from(c);
	unlink_connection_to(c);
	free_connection(c);
    }
}

void
RouterT::kill_bad_connections()
{
    int nc = nconnections();
    for (int i = 0; i < nc; i++) {
	ConnectionT &c = _conn[i];
	if (c.live() && (c.from_element()->dead() || c.to_element()->dead()))
	    kill_connection(i);
    }
}

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

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

    int ei = h.eindex();
    _conn[c]._next_from = _first_conn[ei].from;
    _first_conn[ei].from = c;
}

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

    _conn[c]._to = h;
    if (h.port >= h.element->_ninputs)
	h.element->_ninputs = h.port + 1;

    int ei = h.eindex();
    _conn[c]._next_to = _first_conn[ei].to;
    _first_conn[ei].to = 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()].from;
    while (c >= 0) {
	if (_conn[c].from() == hfrom && _conn[c].to() == hto)
	    break;
	c = _conn[c].next_from();
    }
    return c;
}

bool
RouterT::find_connection_from(const PortT &h, PortT &out) const
{
    assert(h.router() == this);
    int c = _first_conn[h.eindex()].from;
    int p = h.port;
    out = PortT(0, -1);
    while (c >= 0) {
	if (_conn[c].from_port() == p) {
	    if (out.port == -1)
		out = _conn[c].to();
	    else
		out.port = -2;
	}
	c = _conn[c].next_from();
    }
    return out.port >= 0;
}

void
RouterT::find_connections_from(const PortT &h, Vector<PortT> &v) const
{
    assert(h.router() == this);
    int c = _first_conn[h.eindex()].from;
    int p = h.port;
    v.clear();
    while (c >= 0) {
	if (_conn[c].from().port == p)
	    v.push_back(_conn[c].to());
	c = _conn[c].next_from();
    }
}

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

void
RouterT::find_connections_to(const PortT &h, Vector<PortT> &v) const
{
    assert(h.router() == this);
    int c = _first_conn[h.eindex()].to;
    int p = h.port;
    v.clear();
    while (c >= 0) {
	if (_conn[c].to().port == p)
	    v.push_back(_conn[c].from());
	c = _conn[c].next_to();
    }
}

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

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

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

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

    int i = _first_conn[h.eindex()].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()].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 String &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 {
	_archive_map.insert(ae.name, _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].from;
	int next = 0;		// initialize here to avoid gcc warnings
	while (trav >= 0) {
	    int prev = _first_conn[i].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(trav);
		    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.insert(_elements[i]->name(), -1);
	    delete _elements[i];
	} else if (j != i) {
	    _element_name_map.insert(_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].from; c >= 0; c = _conn[c].next_from())
	unlink_connection_to(c);
    for (int c = _first_conn[ei].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].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].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.insert(e->name(), -1);
    e->kill();