replace _networks map by vector

_networks is usually quite small, using binary search on a vector might be faster comapred to std::map.
This is especially true when using uClibc++, which uses a list.

2 files changed, 38 insertions, 23 deletions

diff --git a/node/Node.cpp b/node/Node.cpp
index 9f195a10..8e00071f 100644
--- a/node/Node.cpp
+++ b/node/Node.cpp
@@ -236,13 +236,14 @@ ZT1_ResultCode Node::processBackgroundTasks(uint64_t now,volatile uint64_t *next
 			std::vector< SharedPtr<Network> > needConfig;
 			{
 				Mutex::Lock _l(_networks_m);
-				for(std::map< uint64_t,SharedPtr<Network> >::const_iterator n(_networks.begin());n!=_networks.end();++n) {
-					SharedPtr<NetworkConfig> nc(n->second->config2());
-					if (((now - n->second->lastConfigUpdate()) >= ZT_NETWORK_AUTOCONF_DELAY)||(!nc))
-						needConfig.push_back(n->second);
+				for(std::vector< SharedPtr<Network> >::const_iterator n(_networks.begin());n!=_networks.end();++n) {
+					SharedPtr<NetworkConfig> nc((*n)->config2());
+					if (((now - (*n)->lastConfigUpdate()) >= ZT_NETWORK_AUTOCONF_DELAY)||(!nc))
+						needConfig.push_back(*n);
 					if (nc)
 						networkRelays.insert(networkRelays.end(),nc->relays().begin(),nc->relays().end());
 				}
+				std::sort(_networks.begin(),_networks.end());
 			}
 
 			// Request updated configuration for networks that need it
@@ -310,19 +311,24 @@ ZT1_ResultCode Node::processBackgroundTasks(uint64_t now,volatile uint64_t *next
 ZT1_ResultCode Node::join(uint64_t nwid)
 {
 	Mutex::Lock _l(_networks_m);
-	SharedPtr<Network> &nwe = _networks[nwid];
-	if (!nwe)
-		nwe = SharedPtr<Network>(new Network(RR,nwid));
+	std::vector< SharedPtr<Network> >::const_iterator nwi = std::lower_bound(_networks.begin(), _networks.end(), nwid, NetworkComparator());
+	if(nwi == _networks.end() || (*nwi)->id() != nwid) {
+		_networks.push_back(SharedPtr<Network>(new Network(RR,nwid)));
+		std::sort(_networks.begin(),_networks.end());
+	}
 	return ZT1_RESULT_OK;
 }
 
 ZT1_ResultCode Node::leave(uint64_t nwid)
 {
 	Mutex::Lock _l(_networks_m);
-	std::map< uint64_t,SharedPtr<Network> >::iterator nw(_networks.find(nwid));
-	if (nw != _networks.end()) {
-		nw->second->destroy();
-		_networks.erase(nw);
+	std::vector< SharedPtr<Network> >::iterator nwi = std::lower_bound(_networks.begin(), _networks.end(), nwid, NetworkComparator());
+	if(nwi != _networks.end() && (*nwi)->id() == nwid) {
+		(*nwi)->destroy();
+		// erase element (replace by last)
+		*nwi = _networks.back();
+		_networks.pop_back();
+		std::sort(_networks.begin(),_networks.end());
 	}
 	return ZT1_RESULT_OK;
 }
@@ -406,10 +412,10 @@ ZT1_PeerList *Node::peers() const
 ZT1_VirtualNetworkConfig *Node::networkConfig(uint64_t nwid) const
 {
 	Mutex::Lock _l(_networks_m);
-	std::map< uint64_t,SharedPtr<Network> >::const_iterator nw(_networks.find(nwid));
-	if (nw != _networks.end()) {
+	std::vector< SharedPtr<Network> >::const_iterator nwi = std::lower_bound(_networks.begin(), _networks.end(), nwid, NetworkComparator());
+	if(nwi != _networks.end() && (*nwi)->id() == nwid) {
 		ZT1_VirtualNetworkConfig *nc = (ZT1_VirtualNetworkConfig *)::malloc(sizeof(ZT1_VirtualNetworkConfig));
-		nw->second->externalConfig(nc);
+		(*nwi)->externalConfig(nc);
 		return nc;
 	}
 	return (ZT1_VirtualNetworkConfig *)0;
@@ -426,8 +432,8 @@ ZT1_VirtualNetworkList *Node::networks() const
 	nl->networks = (ZT1_VirtualNetworkConfig *)(buf + sizeof(ZT1_VirtualNetworkList));
 
 	nl->networkCount = 0;
-	for(std::map< uint64_t,SharedPtr<Network> >::const_iterator n(_networks.begin());n!=_networks.end();++n)
-		n->second->externalConfig(&(nl->networks[nl->networkCount++]));
+	for(std::vector< SharedPtr<Network> >::const_iterator n(_networks.begin());n!=_networks.end();++n)
+		(*n)->externalConfig(&(nl->networks[nl->networkCount++]));
 
 	return nl;
 }
diff --git a/node/Node.hpp b/node/Node.hpp
index 1d9372e4..6ef306eb 100644
--- a/node/Node.hpp
+++ b/node/Node.hpp
@@ -155,19 +155,21 @@ public:
 			len);
 	}
 
-	inline SharedPtr<Network> network(uint64_t nwid)
+	inline SharedPtr<Network> network(uint64_t nwid) const
 	{
 		Mutex::Lock _l(_networks_m);
-		std::map< uint64_t,SharedPtr<Network> >::iterator nw(_networks.find(nwid));
-		return ((nw == _networks.end()) ? SharedPtr<Network>() : nw->second);
+		std::vector< SharedPtr<Network> >::const_iterator iter = std::lower_bound(_networks.begin(), _networks.end(), nwid, NetworkComparator());
+		if(iter != _networks.end() && (*iter)->id() == nwid) {
+			return *iter;
+		} else {
+			return SharedPtr<Network>();
+		}
 	}
 
 	inline std::vector< SharedPtr<Network> > allNetworks() const
 	{
 		Mutex::Lock _l(_networks_m);
-		std::vector< SharedPtr<Network> > nw;
-		for(std::map< uint64_t,SharedPtr<Network> >::const_iterator n(_networks.begin());n!=_networks.end();++n)
-			nw.push_back(n->second);
+		std::vector< SharedPtr<Network> > nw(_networks);
 		return nw;
 	}
 
@@ -208,6 +210,13 @@ public:
 #endif
 
 private:
+	// for binary search on _networks
+	struct NetworkComparator {
+		bool operator()(const SharedPtr<Network> &n,uint64_t nwid) const {
+			return n->id() < nwid;
+		}
+	};
+
 	RuntimeEnvironment _RR;
 	RuntimeEnvironment *RR;
 
@@ -223,7 +232,7 @@ private:
 	//Dictionary _localConfig; // persisted as local.conf
 	//Mutex _localConfig_m;
 
-	std::map< uint64_t,SharedPtr<Network> > _networks;
+	std::vector< SharedPtr<Network> > _networks;
 	Mutex _networks_m;
 
 	Mutex _backgroundTasksLock;