Improve performance for setups with many apps or ports.

(Eliminate all linear searches for items, except one case for Jack
ports which is unavoidable due to the Jack API, but is memoized,
so each port will only be searched for once between refreshes).


git-svn-id: http://svn.drobilla.net/lad/trunk/patchage@2712 a436a847-0d15-0410-975c-d299462d15a1

11 files changed, 149 insertions, 85 deletions

diff --git a/src/AlsaDriver.cpp b/src/AlsaDriver.cpp
index 8def786..c1928f5 100644
--- a/src/AlsaDriver.cpp
+++ b/src/AlsaDriver.cpp
@@ -122,7 +122,7 @@ AlsaDriver::find_or_create_module(
 	if (!m) {
 		m = boost::shared_ptr<PatchageModule>(new PatchageModule(patchage, client_name, type));
 		m->load_location();
-		_app->canvas()->add_item(m);
+		_app->canvas()->add_module(client_name, m);
 		_app->enqueue_resize(m);
 	}
 	return m;
@@ -224,7 +224,13 @@ AlsaDriver::create_port(boost::shared_ptr<PatchageModule> parent,
 {
 	boost::shared_ptr<PatchagePort> ret(
 		new PatchagePort(parent, ALSA_MIDI, name, is_input,
-			_app->state_manager()->get_port_color(ALSA_MIDI)));
+		                 _app->state_manager()->get_port_color(ALSA_MIDI)));
+	
+	boost::shared_ptr<PatchageCanvas> canvas
+		= boost::dynamic_pointer_cast<PatchageCanvas>(parent->canvas().lock());
+	if (canvas)
+		canvas->index_port(PortID(addr, is_input), ret);
+
 	ret->alsa_addr(addr);
 	return ret;
 }
diff --git a/src/JackDbusDriver.cpp b/src/JackDbusDriver.cpp
index f2ae7ed..a7a379d 100644
--- a/src/JackDbusDriver.cpp
+++ b/src/JackDbusDriver.cpp
@@ -639,7 +639,7 @@ JackDriver::find_or_create_module(
 	if (!module) {
 		module = boost::shared_ptr<PatchageModule>(new PatchageModule(_app, name, type));
 		module->load_location();
-		_app->canvas()->add_item(module);
+		_app->canvas()->add_module(name, module);
 	}
 
 	return module;
diff --git a/src/JackDriver.cpp b/src/JackDriver.cpp
index 4b2807f..9dd0029 100644
--- a/src/JackDriver.cpp
+++ b/src/JackDriver.cpp
@@ -177,7 +177,7 @@ JackDriver::create_port_view(Patchage*     patchage,
 		parent = boost::shared_ptr<PatchageModule>(
 				new PatchageModule(patchage, module_name, type));
 		parent->load_location();
-		patchage->canvas()->add_item(parent);
+		patchage->canvas()->add_module(module_name, parent);
 		parent->show();
 		resize = true;
 	}
@@ -186,7 +186,7 @@ JackDriver::create_port_view(Patchage*     patchage,
 			= boost::dynamic_pointer_cast<PatchagePort>(parent->get_port(port_name));
 
 	if (!port) {
-		port = create_port(parent, jack_port);
+		port = create_port(parent, jack_port, id);
 		port->show();
 		parent->add_port(port);
 		resize = true;
@@ -200,7 +200,7 @@ JackDriver::create_port_view(Patchage*     patchage,
 
 
 boost::shared_ptr<PatchagePort>
-JackDriver::create_port(boost::shared_ptr<PatchageModule> parent, jack_port_t* port)
+JackDriver::create_port(boost::shared_ptr<PatchageModule> parent, jack_port_t* port, PortID id)
 {
 	assert(port);
 	const char* const type_str = jack_port_type(port);
@@ -219,8 +219,15 @@ JackDriver::create_port(boost::shared_ptr<PatchageModule> parent, jack_port_t* p
 
 	boost::shared_ptr<PatchagePort> ret(
 		new PatchagePort(parent, port_type, jack_port_short_name(port),
-			(jack_port_flags(port) & JackPortIsInput),
-			_app->state_manager()->get_port_color(port_type)));
+		                 (jack_port_flags(port) & JackPortIsInput),
+		                 _app->state_manager()->get_port_color(port_type)));
+
+	if (id.type != PortID::NULL_PORT_ID) {
+		boost::shared_ptr<PatchageCanvas> canvas
+			= boost::dynamic_pointer_cast<PatchageCanvas>(parent->canvas().lock());
+		if (canvas)
+			canvas->index_port(id, ret);
+	}
 
 	return ret;
 }
@@ -286,7 +293,7 @@ JackDriver::refresh()
 		if (!m) {
 			m = boost::shared_ptr<PatchageModule>(new PatchageModule(_app, client1_name, type));
 			m->load_location();
-			_app->canvas()->add_item(m);
+			_app->canvas()->add_module(client1_name, m);
 		}
 
 		// FIXME: leak?  jack docs don't say
@@ -305,7 +312,7 @@ JackDriver::refresh()
 		}
 
 		if (!m->get_port(jack_port_short_name(port)))
-			m->add_port(create_port(m, port));
+			m->add_port(create_port(m, port, PortID()));
 
 		_app->enqueue_resize(m);
 	}
diff --git a/src/JackDriver.hpp b/src/JackDriver.hpp
index b9fb4f4..9dbcd7b 100644
--- a/src/JackDriver.hpp
+++ b/src/JackDriver.hpp
@@ -80,8 +80,9 @@ public:
 
 private:
 	boost::shared_ptr<PatchagePort> create_port(
-			boost::shared_ptr<PatchageModule> parent,
-			jack_port_t*                      port);
+		boost::shared_ptr<PatchageModule> parent,
+		jack_port_t*                      port,
+		PortID                            id);
 
 	static void error_cb(const char* msg);
 
diff --git a/src/PatchageCanvas.cpp b/src/PatchageCanvas.cpp
index 3c63503..0b5103f 100644
--- a/src/PatchageCanvas.cpp
+++ b/src/PatchageCanvas.cpp
@@ -17,6 +17,7 @@
 
 #include "patchage-config.h"
 
+#include "raul/log.hpp"
 #include "raul/SharedPtr.hpp"
 
 #if defined(HAVE_JACK_DBUS)
@@ -33,6 +34,8 @@
 #include "PatchageModule.hpp"
 #include "PatchagePort.hpp"
 
+using std::string;
+
 PatchageCanvas::PatchageCanvas(Patchage* app, int width, int height)
 	: FlowCanvas::Canvas(width, height)
 	, _app(app)
@@ -43,82 +46,55 @@ PatchageCanvas::PatchageCanvas(Patchage* app, int width, int height)
 boost::shared_ptr<PatchageModule>
 PatchageCanvas::find_module(const string& name, ModuleType type)
 {
-	for (ItemList::iterator m = _items.begin(); m != _items.end(); ++m) {
-		boost::shared_ptr<PatchageModule> pm = boost::dynamic_pointer_cast<PatchageModule>(*m);
-		if (pm && pm->name() == name && (pm->type() == type || pm->type() == InputOutput)) {
-			return pm;
+	const ModuleIndex::const_iterator i = _module_index.find(name);
+	if (i == _module_index.end())
+		return boost::shared_ptr<PatchageModule>();
+
+	boost::shared_ptr<PatchageModule> io_module;
+	for (ModuleIndex::const_iterator j = i; j != _module_index.end() && j->first == name; ++j) {
+		if (j->second->type() == type) {
+			return j->second;
+		} else if (j->second->type() == InputOutput) {
+			io_module = j->second;
 		}
 	}
 
-	return boost::shared_ptr<PatchageModule>();
+	// Return InputOutput module for Input or Output (or NULL if not found at all)
+	return io_module;
 }
 
 
 boost::shared_ptr<PatchagePort>
 PatchageCanvas::find_port(const PortID& id)
 {
-	string       module_name;
-	string       port_name;
-
-#if defined(USE_LIBJACK)
-	jack_port_t* jack_port = NULL;
-#endif
+	PortIndex::iterator i = _port_index.find(id);
+	if (i != _port_index.end())
+		return i->second;
 
-	SharedPtr<PatchageModule> module;
 	boost::shared_ptr<PatchagePort> pp;
 
-	// TODO: filthy.  keep a port map and make this O(log(n))
-	switch (id.type) {
-#if defined(USE_LIBJACK) && !defined(HAVE_JACK_DBUS)
-	case PortID::JACK_ID:
-		jack_port = jack_port_by_id(_app->jack_driver()->client(), id.id.jack_id);
-		if (!jack_port)
-			return boost::shared_ptr<PatchagePort>();
+#ifdef USE_LIBJACK
+	assert(id.type == PortID::JACK_ID); // Alsa ports are always indexed
 
-		_app->jack_driver()->port_names(id, module_name, port_name);
+	jack_port_t* jack_port = jack_port_by_id(_app->jack_driver()->client(), id.id.jack_id);
+	if (!jack_port)
+		return boost::shared_ptr<PatchagePort>();
 
-		module = find_module(module_name,
-				(jack_port_flags(jack_port) & JackPortIsInput) ? Input : Output);
+	string module_name;
+	string port_name;
+	_app->jack_driver()->port_names(id, module_name, port_name);
 
-		if (module)
-			return PtrCast<PatchagePort>(module->get_port(port_name));
-		else
-			return boost::shared_ptr<PatchagePort>();
+	SharedPtr<PatchageModule> module = find_module(module_name,
+	                     (jack_port_flags(jack_port) & JackPortIsInput) ? Input : Output);
 
-		break;
-#endif
+	if (module)
+		pp = PtrCast<PatchagePort>(module->get_port(port_name));
 
-#ifdef HAVE_ALSA
-	case PortID::ALSA_ADDR:
-		for (ItemList::iterator m = _items.begin(); m != _items.end(); ++m) {
-			SharedPtr<PatchageModule> module = PtrCast<PatchageModule>(*m);
-			if (!module)
-				continue;
-
-			for (PortVector::const_iterator p = module->ports().begin(); p != module->ports().end(); ++p) {
-				pp = boost::dynamic_pointer_cast<PatchagePort>(*p);
-				if (!pp)
-					continue;
-
-				if (pp->type() == ALSA_MIDI) {
-					if (pp->alsa_addr()
-							&& pp->alsa_addr()->client == id.id.alsa_addr.client
-							&& pp->alsa_addr()->port   == id.id.alsa_addr.port) {
-						if ((module->type() == InputOutput)
-						    || (id.id.is_input && (module->type() == Input))
-						    || (!id.id.is_input && (module->type() == Output))) {
-							return pp;
-						}
-					}
-				}
-			}
-		}
-#endif // HAVE_ALSA
-	default:
-		break;
-	}
+	if (pp)
+		index_port(id, pp);
+#endif // USE_LIBJACK
 
-	return boost::shared_ptr<PatchagePort>();
+	return pp;
 }
 
 
@@ -186,3 +162,11 @@ PatchageCanvas::status_message(const string& msg)
 {
 	_app->status_msg(string("[Canvas] ").append(msg));
 }
+
+void
+PatchageCanvas::destroy()
+{
+	_port_index.clear();
+	_module_index.clear();
+	FlowCanvas::Canvas::destroy();
+}
diff --git a/src/PatchageCanvas.hpp b/src/PatchageCanvas.hpp
index ef599ba..6d0ac9f 100644
--- a/src/PatchageCanvas.hpp
+++ b/src/PatchageCanvas.hpp
@@ -18,7 +18,7 @@
 #ifndef PATCHAGE_PATCHAGECANVAS_HPP
 #define PATCHAGE_PATCHAGECANVAS_HPP
 
-#include <string>
+#include <map>
 
 #include "patchage-config.h"
 
@@ -29,29 +29,48 @@
 #include "flowcanvas/Canvas.hpp"
 
 #include "PatchageEvent.hpp"
+#include "PatchageModule.hpp"
+#include "PortID.hpp"
 #include "StateManager.hpp"
 
 class Patchage;
 class PatchageModule;
 class PatchagePort;
 
-using std::string;
-using namespace FlowCanvas;
-
-class PatchageCanvas : public Canvas {
+class PatchageCanvas : public FlowCanvas::Canvas {
 public:
 	PatchageCanvas(Patchage* _app, int width, int height);
 
-	boost::shared_ptr<PatchageModule> find_module(const string& name, ModuleType type);
+	boost::shared_ptr<PatchageModule> find_module(const std::string& name, ModuleType type);
 	boost::shared_ptr<PatchagePort>   find_port(const PortID& id);
 
-	void connect(boost::shared_ptr<Connectable> port1, boost::shared_ptr<Connectable> port2);
-	void disconnect(boost::shared_ptr<Connectable> port1, boost::shared_ptr<Connectable> port2);
+	void connect(boost::shared_ptr<FlowCanvas::Connectable> port1,
+	             boost::shared_ptr<FlowCanvas::Connectable> port2);
+	
+	void disconnect(boost::shared_ptr<FlowCanvas::Connectable> port1,
+	                boost::shared_ptr<FlowCanvas::Connectable> port2);
+
+	void status_message(const std::string& msg);
+
+	void index_port(const PortID& id, boost::shared_ptr<PatchagePort> port) {
+		_port_index.insert(std::make_pair(id, port));
+	}
 
-	void status_message(const string& msg);
+	void add_module(const std::string& name, boost::shared_ptr<PatchageModule> module) {
+		_module_index.insert(std::make_pair(name, module));
+		add_item(module);
+	}
+	
+	void destroy();
 
 private:
 	Patchage* _app;
+
+	typedef std::map< const PortID, boost::shared_ptr<PatchagePort> > PortIndex;
+	PortIndex _port_index;
+
+	typedef std::multimap< const std::string, boost::shared_ptr<PatchageModule> > ModuleIndex;
+	ModuleIndex _module_index;
 };
 
 
diff --git a/src/PatchageEvent.cpp b/src/PatchageEvent.cpp
index 3c9a82f..cef39f2 100644
--- a/src/PatchageEvent.cpp
+++ b/src/PatchageEvent.cpp
@@ -40,10 +40,12 @@ PatchageEvent::execute(Patchage* patchage)
 {
 	if (_type == REFRESH) {
 		patchage->refresh();
+
 	} else if (_type == CLIENT_CREATION) {
 		// No empty modules (for now)
 		free(_str);
 		_str = NULL;
+
 	} else if (_type == CLIENT_DESTRUCTION) {
 		SharedPtr<PatchageModule> module = PtrCast<PatchageModule>(
 				patchage->canvas()->find_module(_str, InputOutput));
diff --git a/src/PatchageModule.hpp b/src/PatchageModule.hpp
index a2b67ee..3e7bcbd 100644
--- a/src/PatchageModule.hpp
+++ b/src/PatchageModule.hpp
@@ -26,6 +26,8 @@
 
 using namespace FlowCanvas;
 
+class Patchage;
+
 class PatchageModule : public Module
 {
 public:
diff --git a/src/PatchagePort.hpp b/src/PatchagePort.hpp
index 80e70e4..6783434 100644
--- a/src/PatchagePort.hpp
+++ b/src/PatchagePort.hpp
@@ -26,6 +26,9 @@
 #include "flowcanvas/Module.hpp"
 
 #include "patchage-config.h"
+#include "PatchageCanvas.hpp"
+#include "PortID.hpp"
+#include "StateManager.hpp"
 
 #ifdef HAVE_ALSA
   #include <alsa/asoundlib.h>
@@ -33,21 +36,23 @@
 
 using namespace FlowCanvas;
 
-enum PortType { JACK_AUDIO, JACK_MIDI, ALSA_MIDI };
-
 
 /** A Port on a PatchageModule
  */
 class PatchagePort : public FlowCanvas::Port
 {
 public:
-	PatchagePort(boost::shared_ptr<Module> module, PortType type, const std::string& name, bool is_input, int color)
+	PatchagePort(boost::shared_ptr<Module> module,
+	             PortType                  type,
+	             const std::string&        name,
+	             bool                      is_input,
+	             uint32_t                  color)
 		: Port(module, name, is_input, color)
 		, _type(type)
 	{
 #ifdef HAVE_ALSA
 		_alsa_addr.client = '\0';
-		_alsa_addr.port = '\0';
+		_alsa_addr.port   = '\0';
 #endif
 	}
 
diff --git a/src/PortID.hpp b/src/PortID.hpp
index b3c2eb6..b1f8444 100644
--- a/src/PortID.hpp
+++ b/src/PortID.hpp
@@ -34,6 +34,9 @@
 
 struct PortID {
 	PortID() : type(NULL_PORT_ID) { memset(&id, 0, sizeof(id)); }
+	PortID(const PortID& copy) : type(copy.type) {
+		memcpy(&id, &copy.id, sizeof(id));
+	}
 
 	enum { NULL_PORT_ID, JACK_ID, ALSA_ADDR } type;
 
@@ -73,7 +76,40 @@ operator<<(std::ostream& os, const PortID& id)
 		break;
 	case PortID::ALSA_ADDR:
 #ifdef HAVE_ALSA
-		return os << "alsa:" << (int)id.id.alsa_addr.client << ":" << (int)id.id.alsa_addr.port;
+		return os << "alsa:" << (int)id.id.alsa_addr.client << ":" << (int)id.id.alsa_addr.port
+		          << ":" << (id.id.is_input ? "in" : "out");
+#endif
+		break;
+	}
+	assert(false);
+}
+
+static inline bool
+operator<(const PortID& a, const PortID& b)
+{
+	if (a.type != b.type)
+		return a.type < b.type;
+
+	switch (a.type) {
+	case PortID::NULL_PORT_ID:
+		return true;
+	case PortID::JACK_ID:
+#ifdef USE_LIBJACK
+		return a.id.jack_id < b.id.jack_id;
+#endif
+		break;
+	case PortID::ALSA_ADDR:
+#ifdef HAVE_ALSA
+		if ((a.id.alsa_addr.client < b.id.alsa_addr.client)
+		    || ((a.id.alsa_addr.client == b.id.alsa_addr.client)
+		        && a.id.alsa_addr.port < b.id.alsa_addr.port)) {
+			return true;
+		} else if (a.id.alsa_addr.client == b.id.alsa_addr.client
+		           && a.id.alsa_addr.port == b.id.alsa_addr.port) {
+			return (a.id.is_input < b.id.is_input);
+		} else {
+			return false;
+		}
 #endif
 		break;
 	}
diff --git a/src/StateManager.hpp b/src/StateManager.hpp
index b8fb6cf..e2c85c3 100644
--- a/src/StateManager.hpp
+++ b/src/StateManager.hpp
@@ -21,11 +21,13 @@
 #include <string>
 #include <list>
 #include <map>
+
 #include <boost/optional.hpp>
-#include "PatchagePort.hpp"
 
 enum ModuleType { Input, Output, InputOutput };
 
+enum PortType { JACK_AUDIO, JACK_MIDI, ALSA_MIDI };
+
 struct Coord {
 	Coord(double x_=0, double y_=0) : x(x_), y(y_) {}
 	double x;