Swap out std::map<> for Hashtable<> for main peer database in Topology. (ongoing std::map-ectomy)

5 files changed, 37 insertions, 20 deletions

diff --git a/node/Address.hpp b/node/Address.hpp
index 137e4f4f..0b38ec62 100644
--- a/node/Address.hpp
+++ b/node/Address.hpp
@@ -167,6 +167,15 @@ public:
 	}
 
 	/**
+	 * @return Hash code for use with Hashtable
+	 */
+	inline unsigned long hashCode() const
+		throw()
+	{
+		return (unsigned long)_a;
+	}
+
+	/**
 	 * @return Hexadecimal string
 	 */
 	inline std::string toString() const
@@ -197,11 +206,11 @@ public:
 
 	/**
 	 * Check if this address is reserved
-	 * 
+	 *
 	 * The all-zero null address and any address beginning with 0xff are
 	 * reserved. (0xff is reserved for future use to designate possibly
 	 * longer addresses, addresses based on IPv6 innards, etc.)
-	 * 
+	 *
 	 * @return True if address is reserved and may not be used
 	 */
 	inline bool isReserved() const
@@ -230,4 +239,3 @@ private:
 } // namespace ZeroTier
 
 #endif
-
diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp
index 6f7541c4..84b5be0e 100644
--- a/node/Hashtable.hpp
+++ b/node/Hashtable.hpp
@@ -183,10 +183,11 @@ public:
 	/**
 	 * @return Vector of all keys
 	 */
-	inline typename std::vector<K> keys()
+	inline typename std::vector<K> keys() const
 	{
 		typename std::vector<K> k;
 		if (_s) {
+			k.reserve(_s);
 			for(unsigned long i=0;i<_bc;++i) {
 				_Bucket *b = _t[i];
 				while (b) {
@@ -201,10 +202,11 @@ public:
 	/**
 	 * @return Vector of all entries (pairs of K,V)
 	 */
-	inline typename std::vector< std::pair<K,V> > entries()
+	inline typename std::vector< std::pair<K,V> > entries() const
 	{
 		typename std::vector< std::pair<K,V> > k;
 		if (_s) {
+			k.reserve(_s);
 			for(unsigned long i=0;i<_bc;++i) {
 				_Bucket *b = _t[i];
 				while (b) {
diff --git a/node/Node.cpp b/node/Node.cpp
index 534c085d..c8c50d66 100644
--- a/node/Node.cpp
+++ b/node/Node.cpp
@@ -355,7 +355,8 @@ void Node::status(ZT1_NodeStatus *status) const
 
 ZT1_PeerList *Node::peers() const
 {
-	std::map< Address,SharedPtr<Peer> > peers(RR->topology->allPeers());
+	std::vector< std::pair< Address,SharedPtr<Peer> > > peers(RR->topology->allPeers());
+	std::sort(peers.begin(),peers.end());
 
 	char *buf = (char *)::malloc(sizeof(ZT1_PeerList) + (sizeof(ZT1_Peer) * peers.size()));
 	if (!buf)
@@ -364,7 +365,7 @@ ZT1_PeerList *Node::peers() const
 	pl->peers = (ZT1_Peer *)(buf + sizeof(ZT1_PeerList));
 
 	pl->peerCount = 0;
-	for(std::map< Address,SharedPtr<Peer> >::iterator pi(peers.begin());pi!=peers.end();++pi) {
+	for(std::vector< std::pair< Address,SharedPtr<Peer> > >::iterator pi(peers.begin());pi!=peers.end();++pi) {
 		ZT1_Peer *p = &(pl->peers[pl->peerCount++]);
 		p->address = pi->second->address().toInt();
 		p->lastUnicastFrame = pi->second->lastUnicastFrame();
diff --git a/node/Topology.cpp b/node/Topology.cpp
index b255080e..25a92acd 100644
--- a/node/Topology.cpp
+++ b/node/Topology.cpp
@@ -103,7 +103,7 @@ SharedPtr<Peer> Topology::addPeer(const SharedPtr<Peer> &peer)
 	const uint64_t now = RR->node->now();
 	Mutex::Lock _l(_lock);
 
-	SharedPtr<Peer> p(_activePeers.insert(std::pair< Address,SharedPtr<Peer> >(peer->address(),peer)).first->second);
+	SharedPtr<Peer> &p = _activePeers.set(peer->address(),peer);
 	p->use(now);
 	_saveIdentity(p->identity());
 
@@ -160,9 +160,9 @@ SharedPtr<Peer> Topology::getBestRoot(const Address *avoid,unsigned int avoidCou
 					if (++sna == _rootAddresses.end())
 						sna = _rootAddresses.begin(); // wrap around at end
 					if (*sna != RR->identity.address()) { // pick one other than us -- starting from me+1 in sorted set order
-						std::map< Address,SharedPtr<Peer> >::const_iterator p(_activePeers.find(*sna));
-						if ((p != _activePeers.end())&&(p->second->hasActiveDirectPath(now))) {
-							bestRoot = p->second;
+						SharedPtr<Peer> *p = _activePeers.get(*sna);
+						if ((p)&&((*p)->hasActiveDirectPath(now))) {
+							bestRoot = *p;
 							break;
 						}
 					}
@@ -249,10 +249,12 @@ bool Topology::isRoot(const Identity &id) const
 void Topology::clean(uint64_t now)
 {
 	Mutex::Lock _l(_lock);
-	for(std::map< Address,SharedPtr<Peer> >::iterator p(_activePeers.begin());p!=_activePeers.end();) {
-		if (((now - p->second->lastUsed()) >= ZT_PEER_IN_MEMORY_EXPIRATION)&&(std::find(_rootAddresses.begin(),_rootAddresses.end(),p->first) == _rootAddresses.end())) {
-			_activePeers.erase(p++);
-		} else ++p;
+	Hashtable< Address,SharedPtr<Peer> >::Iterator i(_activePeers);
+	Address *a = (Address *)0;
+	SharedPtr<Peer> *p = (SharedPtr<Peer> *)0;
+	while (i.next(a,p))
+		if (((now - (*p)->lastUsed()) >= ZT_PEER_IN_MEMORY_EXPIRATION)&&(std::find(_rootAddresses.begin(),_rootAddresses.end(),*a) == _rootAddresses.end())) {
+			_activePeers.erase(*a);
 	}
 }
 
diff --git a/node/Topology.hpp b/node/Topology.hpp
index 1c5cca00..3066b50c 100644
--- a/node/Topology.hpp
+++ b/node/Topology.hpp
@@ -44,6 +44,7 @@
 #include "Mutex.hpp"
 #include "InetAddress.hpp"
 #include "Dictionary.hpp"
+#include "Hashtable.hpp"
 
 namespace ZeroTier {
 
@@ -163,17 +164,20 @@ public:
 	inline void eachPeer(F f)
 	{
 		Mutex::Lock _l(_lock);
-		for(std::map< Address,SharedPtr<Peer> >::const_iterator p(_activePeers.begin());p!=_activePeers.end();++p)
-			f(*this,p->second);
+		Hashtable< Address,SharedPtr<Peer> >::Iterator i(_activePeers);
+		Address *a = (Address *)0;
+		SharedPtr<Peer> *p = (SharedPtr<Peer> *)0;
+		while (i.next(a,p))
+			f(*this,*p);
 	}
 
 	/**
 	 * @return All currently active peers by address
 	 */
-	inline std::map< Address,SharedPtr<Peer> > allPeers() const
+	inline std::vector< std::pair< Address,SharedPtr<Peer> > > allPeers() const
 	{
 		Mutex::Lock _l(_lock);
-		return _activePeers;
+		return _activePeers.entries();
 	}
 
 	/**
@@ -190,7 +194,7 @@ private:
 
 	const RuntimeEnvironment *RR;
 
-	std::map< Address,SharedPtr<Peer> > _activePeers;
+	Hashtable< Address,SharedPtr<Peer> > _activePeers;
 	std::map< Identity,std::vector<InetAddress> > _roots;
 	std::vector< Address > _rootAddresses;
 	std::vector< SharedPtr<Peer> > _rootPeers;