optimize port lookup, adding/removing/reconnecting routes

xxxAudioBackend::connected_to() is called O(N^2) when building the graph.
Mitigate this by using an O(log(N)) lookup.

This duplicates the storage (both set and map and both are kept in sync.
Changing this to a boost:bidirectional might be nice, before updating
other backends.

1 files changed, 13 insertions, 10 deletions

diff --git a/libs/backends/dummy/dummy_audiobackend.h b/libs/backends/dummy/dummy_audiobackend.h
index 95f079c4b9..0985bdace9 100644
--- a/libs/backends/dummy/dummy_audiobackend.h
+++ b/libs/backends/dummy/dummy_audiobackend.h
@@ -88,7 +88,7 @@ class DummyPort {
 		bool is_connected (const DummyPort *port) const;
 		bool is_physically_connected () const;
 
-		const std::vector<DummyPort *>& get_connections () const { return _connections; }
+		const std::set<DummyPort *>& get_connections () const { return _connections; }
 
 		int connect (DummyPort *port);
 		int disconnect (DummyPort *port);
@@ -121,7 +121,7 @@ class DummyPort {
 		const PortFlags _flags;
 		LatencyRange _capture_latency_range;
 		LatencyRange _playback_latency_range;
-		std::vector<DummyPort*> _connections;
+		std::set<DummyPort*> _connections;
 
 		void _connect (DummyPort* , bool);
 		void _disconnect (DummyPort* , bool);
@@ -447,7 +447,11 @@ class DummyAudioBackend : public AudioBackend {
 		std::vector<DummyAudioPort *> _system_outputs;
 		std::vector<DummyMidiPort *> _system_midi_in;
 		std::vector<DummyMidiPort *> _system_midi_out;
-		std::vector<DummyPort *> _ports;
+
+		typedef std::map<std::string, DummyPort *> PortMap; // fast lookup in _ports
+		typedef std::set<DummyPort *> PortIndex; // fast lookup in _ports
+		PortMap _portmap;
+		PortIndex _ports;
 
 		struct PortConnectData {
 			std::string a;
@@ -475,16 +479,15 @@ class DummyAudioBackend : public AudioBackend {
 		}
 
 		bool valid_port (PortHandle port) const {
-			return std::find (_ports.begin (), _ports.end (), (DummyPort*)port) != _ports.end ();
+			return _ports.find (static_cast<DummyPort*>(port)) != _ports.end ();
 		}
 
-		DummyPort * find_port (const std::string& port_name) const {
-			for (std::vector<DummyPort*>::const_iterator it = _ports.begin (); it != _ports.end (); ++it) {
-				if ((*it)->name () == port_name) {
-					return *it;
-				}
+		DummyPort* find_port (const std::string& port_name) const {
+			PortMap::const_iterator it = _portmap.find (port_name);
+			if (it == _portmap.end()) {
+				return NULL;
 			}
-			return NULL;
+			return (*it).second;
 		}
 
 }; // class DummyAudioBackend