#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 const TransportAddress &	getRandomNode ()
	returns a random node from the leafset
bool	mergeNode (const NodeHandle &node, simtime_t prox)
	merge a node into LeafSet
virtual bool	mergeState (const PastryStateMessage msg, const PastryStateMsgProximity prox)
	update own state based on a received PastryStateMessage
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.
OverlayKey	estimateMeanDistance ()
Public Member Functions inherited from PastryStateObject
void	handleMessage (cMessage *msg)
int	numInitStages (void) const
void	initialize (int stage)
virtual const TransportAddress &	repair (const PastryStateMessage *msg, const PastryStateMsgProximity &prox)
	attempt to repair state using a received REPAIR message
bool	isCloser (const NodeHandle &test, const OverlayKey &destination, const NodeHandle &reference=NodeHandle::UNSPECIFIED_NODE) const
	test a given NodeHandle if it is closer to a given destination
bool	specialCloserCondition (const NodeHandle &test, const OverlayKey &destination, const NodeHandle &reference=NodeHandle::UNSPECIFIED_NODE) const
	test a given NodeHandle if it is closer to a given destination, but only if the shared prefix length with the destination is at least equal to the shared prefix length with our own node

Private Member Functions
virtual void	earlyInit (void)
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

Additional Inherited Members
Static Protected Member Functions inherited from PastryStateObject
static const PastryExtendedNode &	unspecNode ()
Protected Attributes inherited from PastryStateObject
NodeHandle	owner
	stores the NodeHandle of the owner of this PastryStateObject.
uint32_t	bitsPerDigit

Detailed Description

PastryLeafSet module.

This module contains the LeafSet of the Pastry implementation.

Author: Felix Palmen, Bernhard Heep

See Also: Pastry

Definition at line 60 of file PastryLeafSet.h.

Member Function Documentation

bool PastryLeafSet::balanceLeafSet ( )

private

Definition at line 407 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;
        }
    }
    throw cRuntimeError("This should not happen!");
    return false;
}

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

Definition at line 212 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 171 of file PastryLeafSet.cc.

Referenced by BasePastry::createStateMessage().

{
    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 441 of file PastryLeafSet.cc.

Referenced by Pastry::changeState(), and BasePastry::getLeafSet().

{
    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 )

privatevirtual

Definition at line 55 of file PastryLeafSet.cc.

{
    WATCH_VECTOR(leaves);
}

OverlayKey PastryLeafSet::estimateMeanDistance ( )

Definition at line 645 of file PastryLeafSet.cc.

Referenced by BasePastry::estimateMeanDistance().

{
    std::vector<OverlayKey> temp;
    for (uint8_t i = 0; i < leaves.size() / 2; ++i) {
        if (!leaves[i].isUnspecified()) {
            temp.push_back(leaves[i].getKey());
        }
    }
    temp.push_back(owner.getKey());
    for (uint8_t i = leaves.size() / 2; i < leaves.size(); ++i) {
        if (!leaves[i].isUnspecified()) {
            temp.push_back(leaves[i].getKey());
        }
    }
    uint8_t num = 2;
    uint8_t l = 1;
    while (num < temp.size()) {
        num *= 2;
        ++l;
    }
    num /= 2;
    --l;
    OverlayKey mean = OverlayKey::ZERO;
    for (uint8_t i = 0; i < num; ++i) {
        //distances.push_back(KeyRingMetric().distance(temp[i], temp[i+1]));
        mean += (KeyRingMetric().distance(temp[i], temp[i+1]) >> l);
    }
    return mean;
}

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 521 of file PastryLeafSet.cc.

Referenced by Bamboo::handleFailedNode(), and Pastry::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 492 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 481 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 475 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 466 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 113 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 625 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 101 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 188 of file PastryLeafSet.cc.

Referenced by Bamboo::doLeafsetMaintenance().

{
    uint32_t rnd;
    int i;
    rnd = intuniform(0, numberOfLeaves - 1, 0);
    i = rnd;
    while (i < (int)leaves.size()) {
        if (!leaves[i].isUnspecified()) return leaves[i];
        else i++;
    }
    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 460 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 451 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 95 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 61 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 323 of file PastryLeafSet.cc.

Referenced by mergeNode().

{
    assert(node != overlay->getThisNode());
    LEAF_TEST();
    bool issmaller = (it <= smaller);
    if (issmaller) {
        leaves.insert(++it, node);
        if (!leaves.front().isUnspecified())  {
            assert(leaves.front() != node);
            if (leaves.back().isUnspecified()) {
                leaves.back() = leaves.front();
                EV << "[PastryLeafSet::insertLeaf() @ " << overlay->getThisNode().getIp()
                   << " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
                   << "    " << leaves.front().getIp() << " switched sides"
                   << endl;
            } else {
                EV << "[PastryLeafSet::insertLeaf() @ " << overlay->getThisNode().getIp()
                   << " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
                   << "    " << leaves.front().getIp() << " replaced with " << node.getIp()
                   << endl;
            }
        } else {
            EV << "[PastryLeafSet::insertLeaf() @ " << overlay->getThisNode().getIp()
               << " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
               << "    " << node.getIp() << " added"
               << endl;
        }
        leaves.erase(leaves.begin());
    } else {
        leaves.insert(it, node);
        if (!leaves.back().isUnspecified())  {
            assert(leaves.back() != node);
            if (leaves.front().isUnspecified()) {
                leaves.front() = leaves.back();
                EV << "[PastryLeafSet::insertLeaf() @ " << overlay->getThisNode().getIp()
                   << " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
                   << "    " << leaves.back().getIp() << " switched sides"
                   << endl;
            } else {
                EV << " [PastryLeafSet::insertLeaf() @ " << overlay->getThisNode().getIp()
                   << " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
                   << "    " << leaves.back().getIp() << " replaced with " << node.getIp()
                   << endl;
            }
        } else {
            EV << "[PastryLeafSet::insertLeaf() @ " << overlay->getThisNode().getIp()
               << " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
               << "    " << node.getIp() << " added"
               << endl;
        }
        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 143 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 107 of file PastryLeafSet.cc.

Referenced by createSiblingVector(), Pastry::doSecondStage(), Bamboo::handleFailedNode(), and Pastry::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 254 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;
}

bool PastryLeafSet::mergeState	(	const PastryStateMessage *	msg,
		const PastryStateMsgProximity *	prox
	)

virtual

update own state based on a received PastryStateMessage

Parameters

msg	the PastryStateMessage to use as source for update
prox	record of proximity values matching the state message

Returns: true if leafSet was actually changed

Reimplemented from PastryStateObject.

Definition at line 680 of file PastryLeafSet.cc.

Referenced by Pastry::handleStateMessage(), Bamboo::handleStateMessage(), Pastry::mergeState(), and repair().

{
    // LS to temp vector
    std::vector<NodeHandle> temp = leaves; //getNodeHandleVector();
    bool result = PastryStateObject::mergeState(msg, prox);
    // nothing changed -> return without sending updates
    if (!result) return false;
    // compare modified vector with temp
    const std::vector<NodeHandle>& current = leaves; //getNodeHandleVector();
    // send updates (first "left", then "joined")
    for (std::vector<NodeHandle>::const_iterator it = temp.begin();
         it != temp.end(); ++it) {
        if (it->isUnspecified()) continue;
        std::vector<NodeHandle>::const_iterator it2;
        for (it2 = current.begin(); it2 != current.end(); ++it2) {
            if (it2->isUnspecified()) continue;
            if (*it2 == *it) break;
        }
        if (it2 == current.end()) {
            overlay->callUpdate(*it, false);
        }
    }
    for (std::vector<NodeHandle>::const_iterator it = current.begin();
         it != current.end(); ++it) {
        if (it->isUnspecified()) continue;
        std::vector<NodeHandle>::const_iterator it2;
        for (it2 = temp.begin(); it2 != temp.end(); ++it2) {
            if (it2->isUnspecified()) continue;
            if (*it2 == *it) break;
        }
        if (it2 == temp.end()) {
            overlay->callUpdate(*it, true);
        }
    }
    return result;
}

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 573 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;
    }
}