#include <PastryLeafSet.h>

Inheritance diagram for PastryLeafSet:

Public Member Functions
void	initializeSet (uint32_t numberOfLeaves, uint32_t bitsPerDigit, simtime_t repairTimeout, const NodeHandle &owner, BasePastry *overlay)
	Initializes the leaf set.
virtual const NodeHandle &	getDestinationNode (const OverlayKey &destination)
	gets the final node according to the Pastry routing scheme.
virtual const NodeHandle &	findCloserNode (const OverlayKey &destination, bool optimize=false)
	try to find a node numerically closer to a given key with the same shared prefix as the current node in the leaf set.
void	findCloserNodes (const OverlayKey &destination, NodeVector *nodes)
virtual const TransportAddress &	failedNode (const TransportAddress &failed)
	tells the leafset that a node has failed
virtual const TransportAddress &	repair (const PastryStateMessage msg, const PastryStateMsgProximity prox)
	attempt to repair the leafset using a received REPAIR message
bool	isClosestNode (const OverlayKey &destination) const
	checks if we are the closest node to key destination in the overlay
virtual void	dumpToStateMessage (PastryStateMessage *msg) const
	dump content of the set to a PastryStateMessage
virtual void	dumpToStateMessage (PastryLeafsetMessage *msg) const
	dump content of the set to a PastryLeafsetMessage
virtual const TransportAddress &	getRandomNode ()
	returns a random node from the leafset
bool	mergeNode (const NodeHandle &node, simtime_t prox)
	merge a node into LeafSet
const NodeHandle &	getPredecessor (void) const
	return predecessor node for visualizing
const NodeHandle &	getSuccessor (void) const
	return successor node for visualizing
bool	isValid (void) const
	check if LeafSet knows at least one node to the left and to the right
virtual void	dumpToVector (std::vector< TransportAddress > &affected) const
	appends all leaf set entries to a given vector of TransportAddresses, needed to find all Nodes to be notified after joining.
NodeVector *	createSiblingVector (const OverlayKey &key, int numSiblings) const
PastryNewLeafsMessage *	getNewLeafsMessage (void)
	generates a newLeafs-message if LeafSet changed since last call to this method.
Private Member Functions
virtual void	earlyInit (void)
	initialize watches etc.
const NodeHandle &	getBiggestNode (void) const
	return the node with the biggest key in the LeafSet or NodeHandle::UNSPECIFIED_NODE if LeafSet is empty
const OverlayKey &	getBiggestKey (void) const
	return the biggest key in the LeafSet or OverlayKey::UNSPECIFIED_KEY if LeafSet is empty
const NodeHandle &	getSmallestNode (void) const
	return the node with the smallest key in the LeafSet or NodeHandle::UNSPECIFIED_NODE if LeafSet is empty
const OverlayKey &	getSmallestKey (void) const
	return the smallest key in the LeafSet or OverlayKey::UNSPECIFIED_KEY if LeafSet is empty
bool	isLeft (const OverlayKey &key) const
	test if a given key should be placed on the left or on the right side of the leaf set
void	insertLeaf (std::vector< NodeHandle >::iterator &it, const NodeHandle &node)
	insert a leaf at a given position
bool	balanceLeafSet ()
Private Attributes
uint32_t	numberOfLeaves
simtime_t	repairTimeout
BasePastry *	overlay
	pointer to the main pastry module
std::vector< NodeHandle >	leaves
std::vector< NodeHandle >::iterator	smaller
std::vector< NodeHandle >::iterator	bigger
std::map< TransportAddress, PLSRepairData >	awaitingRepair
bool	newLeafs
bool	isFull
bool	wasFull

Detailed Description

PastryLeafSet module.

This module contains the LeafSet of the Pastry implementation.

Author:: Felix Palmen

See also:: Pastry

Definition at line 60 of file PastryLeafSet.h.

Member Function Documentation

bool PastryLeafSet::balanceLeafSet ( ) [private]

Definition at line 380 of file PastryLeafSet.cc.

Referenced by failedNode(), and insertLeaf().

{
    if (isFull ||
        (!leaves.front().isUnspecified() &&
         !(leaves.end() - 2)->isUnspecified()) ||
        (!leaves.back().isUnspecified() &&
         !(leaves.begin() + 1)->isUnspecified()))
        return false;

    std::vector<NodeHandle>::iterator it_left, it_right;

    for (it_left = smaller, it_right = bigger;
         it_right != leaves.end(); --it_left, ++it_right) {
        if (it_left->isUnspecified()) {
            if (it_right->isUnspecified() ||
                (it_right + 1) == leaves.end() ||
                (it_right + 1)->isUnspecified()) return false;
            *it_left = *(it_right + 1);
            *(it_right + 1) = NodeHandle::UNSPECIFIED_NODE;
            return true;
        } else if (it_right->isUnspecified()) {

            if (it_left == leaves.begin() ||
                (it_left - 1)->isUnspecified()) return false;
            *it_right = *(it_left - 1);
            *(it_left - 1) = NodeHandle::UNSPECIFIED_NODE;
            return true;
        }
    }
    return false; // should not happen
}

NodeVector * PastryLeafSet::createSiblingVector	(	const OverlayKey &	key,
		int	numSiblings
	)			const

Definition at line 220 of file PastryLeafSet.cc.

Referenced by BasePastry::findNode(), and BasePastry::isSiblingFor().

{
    std::vector<NodeHandle>::const_iterator it;

    // create temporary comparator
    KeyDistanceComparator<KeyRingMetric>* comp =
        new KeyDistanceComparator<KeyRingMetric>( key );

    // create result vector
    NodeVector* result = new NodeVector( numSiblings, comp );

    result->add(owner);

    for (it = leaves.begin(); it != leaves.end(); it++) {
        if (!it->isUnspecified()) {
            result->add(*it);
        }
    }

    delete comp;

    if (!isValid()) {
        return result;
    }

    // if the leafset is not full, we could have a very small network
    // => return true (FIXME hack)
    if (leaves.front().isUnspecified() || leaves.back().isUnspecified()) {
        return result;
    }

    if ((result->contains(getBiggestKey())) ||
        (result->contains(getSmallestKey()))) {
        delete result;
        return NULL;
    }

    return result;
}

void PastryLeafSet::dumpToStateMessage ( PastryStateMessage * msg ) const [virtual]

dump content of the set to a PastryStateMessage

Parameters:

msg

the PastryStateMessage to be filled with entries

Implements PastryStateObject.

Definition at line 163 of file PastryLeafSet.cc.

Referenced by Bamboo::changeState(), Pastry::doSecondStage(), BasePastry::sendLeafset(), and BasePastry::sendStateTables().

{
    uint32_t i = 0;
    uint32_t size = 0;
    std::vector<NodeHandle>::const_iterator it;

    msg->setLeafSetArraySize(numberOfLeaves);
    for (it = leaves.begin(); it != leaves.end(); it++) {
        if (!it->isUnspecified()) {
            ++size;
            msg->setLeafSet(i++, *it);
        }
    }
    msg->setLeafSetArraySize(size);
}

void PastryLeafSet::dumpToStateMessage ( PastryLeafsetMessage * msg ) const [virtual]

dump content of the set to a PastryLeafsetMessage

Parameters:

msg

the PastryLeafsetMessage to be filled with entries

Definition at line 180 of file PastryLeafSet.cc.

{
    uint32_t i = 0;
    uint32_t size = 0;
    std::vector<NodeHandle>::const_iterator it;

    msg->setLeafSetArraySize(numberOfLeaves);
    for (it = leaves.begin(); it != leaves.end(); it++) {
        if (!it->isUnspecified()) {
            ++size;
            msg->setLeafSet(i++, *it);
        }
    }
    msg->setLeafSetArraySize(size);
}

void PastryLeafSet::dumpToVector ( std::vector< TransportAddress > & affected ) const [virtual]

appends all leaf set entries to a given vector of TransportAddresses, needed to find all Nodes to be notified after joining.

Parameters:

affected

the vector to fill with leaf set entries

Implements PastryStateObject.

Definition at line 412 of file PastryLeafSet.cc.

Referenced by Pastry::changeState().

{
    std::vector<NodeHandle>::const_iterator it;

    for (it = leaves.begin(); it != leaves.end(); it++)
        if (!it->isUnspecified())
            affected.push_back(*it);
}

void PastryLeafSet::earlyInit ( void ) [private, virtual]

initialize watches etc.

Implements PastryStateObject.

Definition at line 53 of file PastryLeafSet.cc.

{
    WATCH_VECTOR(leaves);
}

const TransportAddress & PastryLeafSet::failedNode ( const TransportAddress & failed ) [virtual]

tells the leafset that a node has failed

Parameters:

failed

the failed node

Returns:: a node to ask for REPAIR or TransportAddress::UNSPECIFIED_NODE

Implements PastryStateObject.

Definition at line 486 of file PastryLeafSet.cc.

Referenced by Pastry::handleFailedNode(), and Bamboo::handleFailedNode().

{
    std::vector<NodeHandle>::iterator i;
    const TransportAddress* ask;
    bool left = true;

    // search failed node in leafset:
    for (i = leaves.begin(); i != leaves.end(); i++) {
        if (i == bigger) left = false;
        if ((! i->isUnspecified()) && (i->getIp() == failed.getIp())) break;
    }

    // failed node not in leafset:
    if (i == leaves.end()) return TransportAddress::UNSPECIFIED_NODE;

    overlay->callUpdate(*i, false);

    // remove failed node:
    leaves.erase(i);
    newLeafs = true;

    wasFull = isFull;
    isFull = false;

    // insert UNSPECIFIED_NODE at front or back and return correct node
    // to ask for repair:
    if (left) {
        leaves.insert(leaves.begin(), NodeHandle::UNSPECIFIED_NODE);
        bigger = leaves.begin() + (numberOfLeaves >> 1);
        smaller = bigger - 1;
        ask = static_cast<const TransportAddress*>(&(getSmallestNode()));
    } else {
        leaves.push_back(NodeHandle::UNSPECIFIED_NODE);
        bigger = leaves.begin() + (numberOfLeaves >> 1);
        smaller = bigger - 1;
        ask = static_cast<const TransportAddress*>(&(getBiggestNode()));
    }

    assert(ask->isUnspecified() || *ask != overlay->getThisNode());

    balanceLeafSet();
    LEAF_TEST();

    assert(ask->isUnspecified() || *ask != overlay->getThisNode());

    if (! ask->isUnspecified())
        awaitingRepair[*ask] = PLSRepairData(simTime(), left);

    return *ask;
}

const NodeHandle & PastryLeafSet::findCloserNode	(	const OverlayKey &	destination,
		bool	optimize = `false`
	)			`[virtual]`

try to find a node numerically closer to a given key with the same shared prefix as the current node in the leaf set.

this method is to be called, when a regular next hop couldn't be found or wasn't reachable.

Parameters:

	destination	the destination key
	optimize	if set, check all nodes and return the best/closest one

Returns:: a closer NodeHandle or NodeHandle::UNSPECIFIED_NODE if none was found

Implements PastryStateObject.

Definition at line 458 of file PastryLeafSet.cc.

Referenced by BasePastry::findNode().

{
    std::vector<NodeHandle>::const_iterator i;
    const NodeHandle* ret = &NodeHandle::UNSPECIFIED_NODE;

    // this will only be called after getDestinationNode() returned
    // NodeHandle::UNSPECIFIED_NODE, so a closer Node can only be the biggest
    // or the smallest node in the LeafSet.

    const NodeHandle& smallest = getSmallestNode();
    const NodeHandle& biggest = getBiggestNode();

    if ((!smallest.isUnspecified()) &&
            (specialCloserCondition(smallest, destination, *ret))) {
        if (optimize) ret = &smallest;
        else return smallest;
    }

    if ((!biggest.isUnspecified()) &&
            (specialCloserCondition(biggest, destination, *ret))) {
        if (optimize) ret = &biggest;
        else return biggest;
    }

    return *ret;
}

void PastryLeafSet::findCloserNodes	(	const OverlayKey &	destination,
		NodeVector *	nodes
	)			`[virtual]`

Implements PastryStateObject.

Definition at line 447 of file PastryLeafSet.cc.

Referenced by BasePastry::findNode().

{
    std::vector<NodeHandle>::const_iterator it;

    for (it = leaves.begin(); it != leaves.end(); it++)
        if (!it->isUnspecified())
            nodes->add(*it);

}

const OverlayKey & PastryLeafSet::getBiggestKey ( void ) const [private]

return the biggest key in the LeafSet or OverlayKey::UNSPECIFIED_KEY if LeafSet is empty

Returns:: biggest key in the set

Definition at line 442 of file PastryLeafSet.cc.

Referenced by createSiblingVector(), and getDestinationNode().

{
    return getBiggestNode().getKey();
}

const NodeHandle & PastryLeafSet::getBiggestNode ( void ) const [private]

return the node with the biggest key in the LeafSet or NodeHandle::UNSPECIFIED_NODE if LeafSet is empty

Returns:: biggest node in the set

Definition at line 434 of file PastryLeafSet.cc.

Referenced by failedNode(), findCloserNode(), getBiggestKey(), and repair().

{
    std::vector<NodeHandle>::const_iterator i = leaves.end()-1;
    while ((i->isUnspecified()) && (i != bigger)) i--;
    assert(i->isUnspecified() || *i != overlay->getThisNode());
    return *i;
}

const NodeHandle & PastryLeafSet::getDestinationNode ( const OverlayKey & destination ) [virtual]

gets the final node according to the Pastry routing scheme.

Parameters:

destination

the destination key

Returns:: the NodeHandle of the final node or NodeHandle::UNSPECIFIED_NODE if given destination key is outside the leaf set

Reimplemented from PastryStateObject.

Definition at line 106 of file PastryLeafSet.cc.

Referenced by BasePastry::findNode().

{
    std::vector<NodeHandle>::const_iterator i;
    const OverlayKey* smallest;
    const OverlayKey* biggest;
    const NodeHandle* ret = &NodeHandle::UNSPECIFIED_NODE;

    // check whether destination is inside leafSet:

    smallest = &(getSmallestKey());
    biggest = &(getBiggestKey());
    if (smallest->isUnspecified()) smallest = &(owner.getKey());
    if (biggest->isUnspecified()) biggest = &(owner.getKey());

    if (!destination.isBetweenLR(*smallest, *biggest)) return *ret;

    // find the closest node:

    for (i = leaves.begin(); i != leaves.end(); i++) {
        if (i->isUnspecified()) continue;

        // note for next line:
        // * dereferences iterator, & gets address of element.
        if (isCloser(*i, destination, *ret)) ret = &(*i);
    }

    return *ret;
}

PastryNewLeafsMessage * PastryLeafSet::getNewLeafsMessage ( void )

generates a newLeafs-message if LeafSet changed since last call to this method.

Returns:: pointer to newLeafs-message or NULL

Definition at line 588 of file PastryLeafSet.cc.

Referenced by BasePastry::newLeafs().

{
    std::vector<NodeHandle>::const_iterator it;
    PastryNewLeafsMessage* msg;
    uint32_t i = 0;

    if (! newLeafs) return NULL;
    newLeafs = false;

    msg = new PastryNewLeafsMessage("PastryNewLeafs");

    msg->setLeafsArraySize(numberOfLeaves);
    for (it = leaves.begin(); it != leaves.end(); it++)
        msg->setLeafs(i++, *it);

    msg->setBitLength(PASTRYNEWLEAFS_L(msg));
    return msg;
}

const NodeHandle & PastryLeafSet::getPredecessor ( void ) const

return predecessor node for visualizing

Definition at line 96 of file PastryLeafSet.cc.

Referenced by BasePastry::updateTooltip().

{
    return *smaller;
}

const TransportAddress & PastryLeafSet::getRandomNode ( ) [virtual]

returns a random node from the leafset

Returns:: a random node or TransportAddress::UNSPECIFIED_NODE

Definition at line 196 of file PastryLeafSet.cc.

Referenced by Bamboo::doLeafsetMaintenance().

{
    //std::vector<NodeHandle>::iterator i;
    uint32_t rnd;
    int i;

    rnd = intuniform(0, numberOfLeaves - 1, 0);
    i = rnd;
    //while (rnd < leaves.size()) {
    while (i < (int)leaves.size()) {
        if (!leaves[i].isUnspecified()) return leaves[i];
        else i++;//rnd++;
    }
    i = rnd;
    while (i >= 0) {
        if (!leaves[i].isUnspecified()) return leaves[i];
        else i--;
    }
    EV << "Leafset::getRandomNode() returns UNSPECIFIED_NODE"
          "Leafset empty??" << endl;
    return TransportAddress::UNSPECIFIED_NODE;

}

const OverlayKey & PastryLeafSet::getSmallestKey ( void ) const [private]

return the smallest key in the LeafSet or OverlayKey::UNSPECIFIED_KEY if LeafSet is empty

Returns:: smallest key in the set

Definition at line 429 of file PastryLeafSet.cc.

Referenced by createSiblingVector(), and getDestinationNode().

{
    return getSmallestNode().getKey();
}

const NodeHandle & PastryLeafSet::getSmallestNode ( void ) const [private]

return the node with the smallest key in the LeafSet or NodeHandle::UNSPECIFIED_NODE if LeafSet is empty

Returns:: smallest node in the set

Definition at line 421 of file PastryLeafSet.cc.

Referenced by failedNode(), findCloserNode(), getSmallestKey(), and repair().

{
    std::vector<NodeHandle>::const_iterator i = leaves.begin();
    while ((i->isUnspecified()) && (i != smaller)) i++;
    assert(i->isUnspecified() || *i != overlay->getThisNode());
    return *i;
}

const NodeHandle & PastryLeafSet::getSuccessor ( void ) const

return successor node for visualizing

Definition at line 91 of file PastryLeafSet.cc.

Referenced by BasePastry::updateTooltip().

{
    return *bigger;
}

void PastryLeafSet::initializeSet	(	uint32_t	numberOfLeaves,
		uint32_t	bitsPerDigit,
		simtime_t	repairTimeout,
		const NodeHandle &	owner,
		BasePastry *	overlay
	)

Initializes the leaf set.

This should be called on startup

Parameters:

	numberOfLeaves	Pastry configuration parameter
	bitsPerDigit	number of bits per digits
	repairTimeout	Pastry configuration parameter
	owner	the node this table belongs to
	overlay	pointer to the pastry main module

Definition at line 58 of file PastryLeafSet.cc.

Referenced by BasePastry::baseChangeState().

{
    if (numberOfLeaves % 2) throw "numberOfLeaves must be even.";

    this->owner = owner;
    this->numberOfLeaves = numberOfLeaves;
    this->repairTimeout = repairTimeout;
    this->bitsPerDigit = bitsPerDigit;
    this->overlay = overlay;

    if (!leaves.empty()) leaves.clear();

    // fill Set with unspecified node handles
    for (uint32_t i = numberOfLeaves; i>0; i--)
        leaves.push_back(NodeHandle::UNSPECIFIED_NODE);

    // initialize iterators to mark the beginning of bigger/smaller keys
    // in the set
    bigger = leaves.begin() + (numberOfLeaves >> 1);
    smaller = bigger - 1;

    // reset repair marker:
    if (!awaitingRepair.empty()) awaitingRepair.clear();

    newLeafs = false;
    isFull = false;
    wasFull = false;
}

void PastryLeafSet::insertLeaf	(	std::vector< NodeHandle >::iterator &	it,
		const NodeHandle &	node
	)			`[private]`

insert a leaf at a given position

Parameters:

	it	iterator where to insert the new leaf
	node	NodeHandle of new leaf

Definition at line 329 of file PastryLeafSet.cc.

Referenced by mergeNode().

{
    assert(node != overlay->getThisNode());

    LEAF_TEST();
    bool issmaller = (it <= smaller);
    if (issmaller) {
        if (!leaves.front().isUnspecified())  {
            overlay->callUpdate(leaves.front(), false);
        }
        overlay->callUpdate(node, true);

        leaves.insert(++it, node);
        NodeHandle& temp = leaves.front();
        if (!temp.isUnspecified() && leaves.back().isUnspecified()) {
            leaves.back() = temp;
        }
        leaves.erase(leaves.begin());


    } else {
        if (!leaves.back().isUnspecified())  {
            overlay->callUpdate(leaves.back(), false);
        }
        overlay->callUpdate(node, true);

        leaves.insert(it, node);
        NodeHandle& temp = leaves.back();
        if (!temp.isUnspecified() && leaves.front().isUnspecified()) {
            leaves.front() = temp;
        }
        leaves.pop_back();
    }

    if (!leaves.front().isUnspecified() &&
        !leaves.back().isUnspecified()) {
        isFull = true;
    } else isFull = false;

    newLeafs = true;
    bigger = leaves.begin() + (numberOfLeaves >> 1);
    smaller = bigger - 1;

    // ensure balance in leafset
    if (!isFull) {
        balanceLeafSet();
    }
    LEAF_TEST();
}

bool PastryLeafSet::isClosestNode ( const OverlayKey & destination ) const

checks if we are the closest node to key destination in the overlay

Parameters:

destination

the key to check

Returns:: true if we are closest to given key

Definition at line 136 of file PastryLeafSet.cc.

Referenced by BasePastry::findNode(), and BasePastry::isSiblingFor().

{
    // check for simple cases first
    if (owner.getKey() == destination) {
        return true;
    }

    if (bigger->isUnspecified() && smaller->isUnspecified()) {
        return true;
    }

    // check if the next bigger or smaller node in the set is closer
    // than own node
    bool biggerIsCloser = false;
    bool smallerIsCloser = false;

    if (! bigger->isUnspecified()) {
        biggerIsCloser = isCloser(*bigger, destination);
    }
    if (! smaller->isUnspecified()) {
        smallerIsCloser = isCloser(*smaller, destination);
    }

    // return true if both are not closer
    return ((!biggerIsCloser) && (!smallerIsCloser));
}

bool PastryLeafSet::isLeft ( const OverlayKey & key ) const [private]

test if a given key should be placed on the left or on the right side of the leaf set

Parameters:

key

key to test

Returns:: true if key belongs to the left

bool PastryLeafSet::isValid ( void ) const

check if LeafSet knows at least one node to the left and to the right

Definition at line 101 of file PastryLeafSet.cc.

Referenced by createSiblingVector(), Pastry::doSecondStage(), Pastry::handleFailedNode(), and Bamboo::handleFailedNode().

{
    return (!(smaller->isUnspecified() || bigger->isUnspecified()));
}

bool PastryLeafSet::mergeNode	(	const NodeHandle &	node,
		simtime_t	prox
	)			`[virtual]`

merge a node into LeafSet

Parameters:

	node	the node to merge
	prox	the proximity value of the node

Returns:: true if node was merged

Implements PastryStateObject.

Definition at line 261 of file PastryLeafSet.cc.

{
    assert(node != overlay->getThisNode());

    std::vector<NodeHandle>::iterator it, it_left, it_right;
    const OverlayKey* last_left = &(owner.getKey());
    const OverlayKey* last_right = &(owner.getKey());

    it_left = smaller;
    it_right = bigger;

    // avoid duplicates
    for (it = leaves.begin(); it != leaves.end(); ++it) {
        if (it->isUnspecified()) {
            isFull = false;
            continue;
        }
        if (it->getKey() == node.getKey()) return false;
    }

    // look for correct position in left and right half of leafset
    while (true) {
        if(!isFull) {
            // both sides free
            if(it_left->getKey().isUnspecified() &&
               it_right->getKey().isUnspecified()) {
                insertLeaf(it_left, node);
                return true;
            }
            if (it_left->getKey().isUnspecified() &&
                !node.getKey().isBetween(*last_right, it_right->getKey())) {
                // end of smaller entries found
                insertLeaf(it_left, node);
                return true;
            }
            if (it_right->getKey().isUnspecified() &&
                !node.getKey().isBetween(it_left->getKey(), *last_left)) {
                // end of bigger entries found
                insertLeaf(it_right, node);
                return true;
            }
        }
        // left side
        if (node.getKey().isBetween(it_left->getKey(), *last_left)) {
            // found correct position for inserting the new entry between
            // existing ones
            insertLeaf(it_left, node);
            return true;
        }
        // right side
        if (node.getKey().isBetween(*last_right, it_right->getKey())) {
            // found correct position for inserting the new entry between
            // existing ones
            insertLeaf(it_right, node);
            return true;
        }

        last_right = &(it_right->getKey());
        ++it_right;

        if (it_right == leaves.end()) break;

        last_left = &(it_left->getKey());
        --it_left;
    }
    return false;
}

const TransportAddress & PastryLeafSet::repair	(	const PastryStateMessage *	msg,
		const PastryStateMsgProximity *	prox
	)			`[virtual]`

attempt to repair the leafset using a received REPAIR message

Parameters:

	msg	the state message of type REPAIR
	prox	record of proximity values matching the state message

Returns:: another node to ask for REPAIR or TransportAddress::UNSPECIFIED_NODE

Definition at line 537 of file PastryLeafSet.cc.

Referenced by Pastry::handleStateMessage().

{
    std::map<TransportAddress, PLSRepairData>::iterator it;
    const TransportAddress* ask;
    bool left;

    simtime_t now = simTime();

    // first eliminate outdated entries in awaitingRepair:
    for (it = awaitingRepair.begin(); it != awaitingRepair.end();) {
        if (it->second.ts < (now - repairTimeout)) {
            awaitingRepair.erase(it++);
        }
        else it++;
    }

    // don't expect any more repair messages:
    if (awaitingRepair.empty()) return TransportAddress::UNSPECIFIED_NODE;

    // look for source node in our list:
    if ( (it = awaitingRepair.find(msg->getSender())) == awaitingRepair.end() )
        return TransportAddress::UNSPECIFIED_NODE;

    // which side of the LeafSet is affected:
    left = it->second.left;

    // remove source node from list:
    awaitingRepair.erase(it);

    // merge info from repair message:
    if (mergeState(msg, prox) || isFull || !wasFull) {
        EV << "[PastryLeafSet::repair()]\n"
           << "    LeafSet repair was successful."
           << endl;
        return TransportAddress::UNSPECIFIED_NODE;
    } else {
        // repair did not succeed, try again:
        ask = &( left ? getSmallestNode() : getBiggestNode() );
        if (ask->isUnspecified() || *ask == msg->getSender()) {
            EV << "[PastryLeafSet::repair()]\n"
               << "    LeafSet giving up repair attempt."
               << endl;
            return TransportAddress::UNSPECIFIED_NODE;
        } else {
            awaitingRepair[*ask] = PLSRepairData(simTime(), left);
        }
        return *ask;
    }
}