OverSim
Public Types | Public Member Functions | Static Public Attributes | Private Attributes | List of all members
BaseKeySortedVector< T, T_key, T_prox, T_address > Class Template Reference

A STL-vector that supports inserts sorted by an OverlayKey found somewhere in the type. More...

#include <NodeVector.h>

Inheritance diagram for BaseKeySortedVector< T, T_key, T_prox, T_address >:
vector

Public Types

typedef std::vector< T >::iterator iterator
 iterator for this vector
typedef std::vector< T >
::const_iterator 		const_iterator
 read-only iterator for this vector

Public Member Functions

 BaseKeySortedVector (uint16_t maxSize=0, const Comparator< OverlayKey > *comparator=NULL, const AbstractProxComparator *proxComparator=NULL, const AbstractProxKeyComparator *proxKeyComparator=NULL, uint16_t sizeProx=0, uint16_t sizeComb=0)
 constructor
virtual ~BaseKeySortedVector ()
 destructor
bool isAddable (const T &element) const
 indicates if an object of type T can be added to the NodeVector
bool isFull () const
 indicates if NodeVector holds maxSize nodes
bool isEmpty () const
 indicates if NodeVector holds at least one node
int add (const T &element)
 adds an element of type T in increasing order to the NodeVector and returns the position of the added element or -1 if the element was not added
const bool contains (const OverlayKey &key) const
 Searches for an OverlayKey in NodeVector and returns true, if it is found.
const T & find (const OverlayKey &key) const
 searches for an OverlayKey in NodeVector
iterator findIterator (const OverlayKey &key)
 Searches for an OberlayKey in a NodeVector and returns an appropriate iterator.
void downsizeTo (const uint32_t maxElements)
 Downsize the vector to a maximum of maxElements.
void setComparator (const Comparator< OverlayKey > *comparator)

Static Public Attributes

static const T UNSPECIFIED_ELEMENT
 unspecified element of type T

Private Attributes

const Comparator< OverlayKey > * comparator
 the OverlayKey Comparator for this vector
const AbstractProxComparator * proxComparator
const AbstractProxKeyComparator * proxKeyComparator
uint16_t maxSize
 maximum nodes this vector holds
uint16_t sizeProx
uint16_t sizeComb

Detailed Description

template<class T, class T_key, class T_prox, class T_address>
class BaseKeySortedVector< T, T_key, T_prox, T_address >

A STL-vector that supports inserts sorted by an OverlayKey found somewhere in the type.

Author
Sebastian Mies constructor
Parameters
maxSizemaximum nodes this vector holds
comparatorOverlayKey Comparator for this vector
useRttsort by rtt after sorting using the comparator destructor indicates if an object of type T can be added to the NodeVector
elementthe element to add
Returns
true if element can be added to the NodeVector, false otherwise indicates if NodeVector holds maxSize nodes
true if the actual size of NodeVector has reached its maxSize, false otherwise indicates if NodeVector holds at least one node
true if NodeVector does not hold any node, false otherwise adds an element of type T in increasing order to the NodeVector and returns the position of the added element or -1 if the element was not added
Parameters
elementthe element to add
Returns
position of the added element, -1 if the element was not added Searches for an OverlayKey in NodeVector and returns true, if it is found.
Parameters
keythe OverlayKey to find
Returns
true, if the vector contains the key searches for an OverlayKey in NodeVector
Parameters
keythe OverlayKey to find
Returns
the UNSPECIFIED_ELEMENT if there is no element with the defined key, the found element of type T otherwise Searches for an OberlayKey in a NodeVector and returns an appropriate iterator.
Parameters
keyThe key to search
Returns
iterator The iterator Downsize the vector to a maximum of maxElements.
Parameters
maxElementsThe maximum number of elements after downsizing

Definition at line 363 of file NodeVector.h.

Member Typedef Documentation

template<class T, class T_key, class T_prox, class T_address>
typedef std::vector<T>::const_iterator BaseKeySortedVector< T, T_key, T_prox, T_address >::const_iterator

read-only iterator for this vector

Definition at line 404 of file NodeVector.h.

template<class T, class T_key, class T_prox, class T_address>
typedef std::vector<T>::iterator BaseKeySortedVector< T, T_key, T_prox, T_address >::iterator

iterator for this vector

Definition at line 401 of file NodeVector.h.

Constructor & Destructor Documentation

template<class T, class T_key, class T_prox, class T_address>
BaseKeySortedVector< T, T_key, T_prox, T_address >::BaseKeySortedVector ( uint16_t  maxSize = 0,
const Comparator< OverlayKey > *  comparator = NULL,
const AbstractProxComparator *  proxComparator = NULL,
const AbstractProxKeyComparator *  proxKeyComparator = NULL,
uint16_t  sizeProx = 0,
uint16_t  sizeComb = 0 
)
inline

constructor

Parameters
maxSizemaximum nodes this vector holds
comparatorOverlayKey comparator for this vector
proxComparatorproximity comparator for this vector
proxKeyComparatorproximity/key comparator for this vector
sizeProxnumber of nodes sorted by proximity
sizeCombnumber of nodes sorted by proximity/key

Definition at line 384 of file NodeVector.h.

:
std::vector<T>(),
comparator(comparator),
proxComparator(proxComparator),
proxKeyComparator(proxKeyComparator),
maxSize(maxSize),
sizeProx(sizeProx),
sizeComb(sizeComb) { };
template<class T, class T_key, class T_prox, class T_address>
virtual BaseKeySortedVector< T, T_key, T_prox, T_address >::~BaseKeySortedVector ( )
inlinevirtual

destructor

Definition at line 401 of file NodeVector.h.

{};

Member Function Documentation

template<class T, class T_key, class T_prox, class T_address>
int BaseKeySortedVector< T, T_key, T_prox, T_address >::add ( const T &  element)
inline

adds an element of type T in increasing order to the NodeVector and returns the position of the added element or -1 if the element was not added

Parameters
elementthe element to add
Returns
position of the added element, -1 if the element was not added

Definition at line 464 of file NodeVector.h.

Referenced by IterativePathLookup::add(), BaseKeySortedVector< LookupEntry >::add(), IterativeLookup::addSibling(), IterativeLookup::checkStop(), BrooseBucket::fillVector(), PastryNeighborhoodSet::findCloserNodes(), PastryRoutingTable::findCloserNodes(), PastryLeafSet::findCloserNodes(), MyOverlay::findNode(), BasePastry::findNode(), Kademlia::findNode(), Broose::findNode(), IterativePathLookup::handleFailedNodeResponse(), DHT::handlePutRequest(), IterativePathLookup::handleTimeout(), Kademlia::refillSiblingTable(), Kademlia::routingAdd(), and NeighborCache::updateNode().

{
int pos = -1;
// check if handle is addable
if (isAddable(element)) { // yes ->
// add handle to the appropriate position
if ((std::vector<T>::size() != 0) &&
(comparator || proxComparator || proxKeyComparator)) {
iterator i;
for (i = std::vector<T>::begin(), pos=0;
i != std::vector<T>::end(); i++, pos++) {
// don't add node with same key twice
if (!T_key::key(element).isUnspecified()) {
if (T_key::key(element) == T_key::key(*i)) {
return -1;
}
} else {
if (T_address::address(element) == T_address::address(*i)) {
return -1;
}
}
if (pos < sizeProx) {
assert(proxComparator);
// only compare proximity
int compResult =
proxComparator->compare(T_prox::prox(element),
T_prox::prox(*i));
//if (T_prox::prox(element).compareTo(T_prox::prox(*i))) {
if (compResult < 0) {
iterator temp_it = std::vector<T>::insert(i, element);
int tempPos = pos;
//std::cout << std::vector<T>::size() << std::endl;
while ((tempPos < sizeProx) && (temp_it != std::vector<T>::end())) {
++temp_it;
++tempPos;
//std::cout << pos << " " << sizeProx << std::endl;
}
//std::cout << pos << " " << sizeProx
// << " " << maxSize << std::endl;
if ((tempPos >= sizeProx) && (tempPos < maxSize) &&
(temp_it != std::vector<T>::end())) {
T temp = *temp_it;
std::vector<T>::erase(temp_it);
//re-insert replaced entry into other 2 ranges
add(temp);
}
break;
}
} else if (pos < sizeProx + sizeComb) {
assert(proxKeyComparator);
// compare proximity and key distance
int compResult = proxKeyComparator->compare(ProxKey(T_prox::prox(element), T_key::key(element)),
ProxKey(T_prox::prox(*i), T_key::key(*i)));
if (compResult < 0) {
iterator temp_it = std::vector<T>::insert(i, element);
int tempPos = pos;
while ((tempPos < sizeProx + sizeComb) &&
(temp_it != std::vector<T>::end())) {
++temp_it;
++tempPos;
}
if ((tempPos >= sizeProx + sizeComb) && (pos < maxSize) &&
(temp_it != std::vector<T>::end())) {
T temp = *temp_it;
std::vector<T>::erase(temp_it);
//re-insert replaced entry into other 2 ranges
add(temp);
}
break;
}
} else {
assert(comparator);
// only consider key distance
int compResult = comparator->compare(T_key::key(element),
T_key::key(*i));
if (compResult < 0) {
std::vector<T>::insert(i, element);
break;
}
}
}
if (i == std::vector<T>::end()) {
pos = std::vector<T>::size();
this->push_back(element);
}
} else {
for (iterator i = std::vector<T>::begin(); i != std::vector<T>::end();
i++) {
std::cout << "should not happen" << std::endl;
// don't add node with same key twice
if (T_key::key(element) == T_key::key(*i)) {
return -1;
}
}
pos = std::vector<T>::size();
assert(pos == 0);
this->push_back(element);
}
// adjust size
if ((maxSize != 0) && (std::vector<T>::size() > maxSize)) {
std::vector<T>::resize(maxSize);
}
}
return pos;
};
template<class T, class T_key, class T_prox, class T_address>
const bool BaseKeySortedVector< T, T_key, T_prox, T_address >::contains ( const OverlayKey &  key) const
inline

Searches for an OverlayKey in NodeVector and returns true, if it is found.

Parameters
keythe OverlayKey to find
Returns
true, if the vector contains the key

Definition at line 589 of file NodeVector.h.

Referenced by BasePastry::isSiblingFor().

{
for (const_iterator i = std::vector<T>::begin();
i != std::vector<T>::end(); i++) {
if (T_key::key(*i) == key) return true;
}
return false;
}
template<class T, class T_key, class T_prox, class T_address>
void BaseKeySortedVector< T, T_key, T_prox, T_address >::downsizeTo ( const uint32_t  maxElements)
inline

Downsize the vector to a maximum of maxElements.

Parameters
maxElementsThe maximum number of elements after downsizing

Definition at line 634 of file NodeVector.h.

Referenced by oversim::Chord::findNode().

{
if (std::vector<T>::size() > maxElements) {
std::vector<T>::erase(std::vector<T>::begin()+maxElements, std::vector<T>::end());
}
}
template<class T, class T_key, class T_prox, class T_address>
const T& BaseKeySortedVector< T, T_key, T_prox, T_address >::find ( const OverlayKey &  key) const
inline

searches for an OverlayKey in NodeVector

Parameters
keythe OverlayKey to find
Returns
the UNSPECIFIED_ELEMENT if there is no element with the defined key, the found element of type T otherwise

Definition at line 605 of file NodeVector.h.

Referenced by DHT::handleGetResponse().

{
for (const_iterator i = std::vector<T>::begin();
i != std::vector<T>::end(); i++) {
if (T_key::key(*i) == key) return *i;
}
return UNSPECIFIED_ELEMENT;
};
template<class T, class T_key, class T_prox, class T_address>
iterator BaseKeySortedVector< T, T_key, T_prox, T_address >::findIterator ( const OverlayKey &  key)
inline

Searches for an OberlayKey in a NodeVector and returns an appropriate iterator.

Parameters
keyThe key to search
Returns
iterator The iterator

Definition at line 621 of file NodeVector.h.

Referenced by IterativePathLookup::handleTimeout(), Kademlia::routingAdd(), and Kademlia::routingTimeout().

{
iterator i;
for (i = std::vector<T>::begin(); i != std::vector<T>::end(); i++)
if (T_key::key(*i) == key) break;
return i;
}
template<class T, class T_key, class T_prox, class T_address>
bool BaseKeySortedVector< T, T_key, T_prox, T_address >::isAddable ( const T &  element) const
inline

indicates if an object of type T can be added to the NodeVector

Parameters
elementthe element to add
Returns
true if element can be added to the NodeVector, false otherwise

Definition at line 417 of file NodeVector.h.

Referenced by BaseKeySortedVector< LookupEntry >::add(), IterativeLookup::addSibling(), and Kademlia::routingAdd().

{
if (maxSize == 0) {
return true;
}
return (std::vector<T>::size() != maxSize ||
(comparator &&
(comparator->compare(T_key::key(element),
T_key::key(std::vector<T>::back())) <= 0 )) ||
(proxComparator &&
(proxComparator->compare(T_prox::prox(element),
T_prox::prox(std::vector<T>::back())) <= 0 )) ||
(proxKeyComparator &&
(proxKeyComparator->compare(ProxKey(T_prox::prox(element),
T_key::key(element)),
ProxKey(T_prox::prox(std::vector<T>::back()),
T_key::key(std::vector<T>::back()))) <= 0 )));
};
template<class T, class T_key, class T_prox, class T_address>
bool BaseKeySortedVector< T, T_key, T_prox, T_address >::isEmpty ( ) const
inline

indicates if NodeVector holds at least one node

Returns
true if NodeVector does not hold any node, false otherwise

Definition at line 452 of file NodeVector.h.

Referenced by Kademlia::findNode().

{
return(std::vector<T>::size() == 0);
};
template<class T, class T_key, class T_prox, class T_address>
bool BaseKeySortedVector< T, T_key, T_prox, T_address >::isFull ( ) const
inline

indicates if NodeVector holds maxSize nodes

Returns
true if the actual size of NodeVector has reached its maxSize, false otherwise

Definition at line 442 of file NodeVector.h.

Referenced by IterativeLookup::addSibling(), Kademlia::findNode(), Kademlia::isSiblingFor(), Kademlia::refillSiblingTable(), and Kademlia::routingAdd().

{
return(std::vector<T>::size() == maxSize);
};
template<class T, class T_key, class T_prox, class T_address>
void BaseKeySortedVector< T, T_key, T_prox, T_address >::setComparator ( const Comparator< OverlayKey > *  comparator)
inline

Definition at line 641 of file NodeVector.h.

Referenced by Broose::findNode(), and Kademlia::routingInit().

{
this->comparator = comparator;
}

Member Data Documentation

template<class T, class T_key, class T_prox, class T_address>
const Comparator<OverlayKey>* BaseKeySortedVector< T, T_key, T_prox, T_address >::comparator
private

the OverlayKey Comparator for this vector

Definition at line 366 of file NodeVector.h.

Referenced by BaseKeySortedVector< LookupEntry >::add(), BaseKeySortedVector< LookupEntry >::isAddable(), and BaseKeySortedVector< LookupEntry >::setComparator().

template<class T, class T_key, class T_prox, class T_address>
uint16_t BaseKeySortedVector< T, T_key, T_prox, T_address >::maxSize
private

maximum nodes this vector holds

Definition at line 369 of file NodeVector.h.

Referenced by BaseKeySortedVector< LookupEntry >::add(), BaseKeySortedVector< LookupEntry >::isAddable(), and BaseKeySortedVector< LookupEntry >::isFull().

template<class T, class T_key, class T_prox, class T_address>
const AbstractProxComparator* BaseKeySortedVector< T, T_key, T_prox, T_address >::proxComparator
private

Definition at line 367 of file NodeVector.h.

Referenced by BaseKeySortedVector< LookupEntry >::add(), and BaseKeySortedVector< LookupEntry >::isAddable().

template<class T, class T_key, class T_prox, class T_address>
const AbstractProxKeyComparator* BaseKeySortedVector< T, T_key, T_prox, T_address >::proxKeyComparator
private

Definition at line 368 of file NodeVector.h.

Referenced by BaseKeySortedVector< LookupEntry >::add(), and BaseKeySortedVector< LookupEntry >::isAddable().

template<class T, class T_key, class T_prox, class T_address>
uint16_t BaseKeySortedVector< T, T_key, T_prox, T_address >::sizeComb
private

Definition at line 371 of file NodeVector.h.

Referenced by BaseKeySortedVector< LookupEntry >::add().

template<class T, class T_key, class T_prox, class T_address>
uint16_t BaseKeySortedVector< T, T_key, T_prox, T_address >::sizeProx
private

Definition at line 370 of file NodeVector.h.

Referenced by BaseKeySortedVector< LookupEntry >::add().

template<class T, class T_key, class T_prox, class T_address>
const T BaseKeySortedVector< T, T_key, T_rtt, T_address >::UNSPECIFIED_ELEMENT
static

unspecified element of type T

an unspecified element of the NodeVector

Definition at line 406 of file NodeVector.h.

Referenced by BaseKeySortedVector< LookupEntry >::find().

The documentation for this class was generated from the following file: