Store patch connections in a map using a lexicographic <Port*,Port*> key for

fast (logarathmic) connection searching.

Replaces all O(num_connections) searches with O(lg(num_connections))
searches.


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

10 files changed, 79 insertions, 59 deletions

diff --git a/src/engine/InputPort.cpp b/src/engine/InputPort.cpp
index fa45117d..f9ddbfe2 100644
--- a/src/engine/InputPort.cpp
+++ b/src/engine/InputPort.cpp
@@ -81,7 +81,7 @@ InputPort::set_buffer_size(Context& context, BufferFactory& bufs, size_t size)
 	PortImpl::set_buffer_size(context, bufs, size);
 
 	for (Connections::iterator c = _connections.begin(); c != _connections.end(); ++c)
-		((ConnectionImpl*)c->get())->update_buffer_size(context, bufs);
+		(*c)->update_buffer_size(context, bufs);
 }
 
 
@@ -156,8 +156,10 @@ InputPort::remove_connection(ProcessContext& context, const OutputPort* src_port
 		Connections::iterator next = i;
 		++next;
 
-		if ((*i)->src_port() == src_port)
+		if ((*i)->src_port() == src_port) {
 			connection = _connections.erase(i);
+			break;
+		}
 
 		i = next;
 	}
diff --git a/src/engine/MessageContext.cpp b/src/engine/MessageContext.cpp
index eec5acaa..ec0fedbf 100644
--- a/src/engine/MessageContext.cpp
+++ b/src/engine/MessageContext.cpp
@@ -118,7 +118,7 @@ MessageContext::execute(const Request& req)
 				lv2_contexts_port_is_valid(valid_ports, i)) {
 			PatchImpl::Connections& wires = patch->connections();
 			for (PatchImpl::Connections::iterator c = wires.begin(); c != wires.end(); ++c) {
-				ConnectionImpl* ci = dynamic_cast<ConnectionImpl*>(c->get());
+				ConnectionImpl* ci = (ConnectionImpl*)c->second.get();
 				if (ci->src_port() == p && ci->dst_port()->context() == Context::MESSAGE) {
 					_queue.insert(Request(req.time, ci->dst_port()));
 				}
diff --git a/src/engine/ObjectSender.cpp b/src/engine/ObjectSender.cpp
index 7cfa5f85..adb35f13 100644
--- a/src/engine/ObjectSender.cpp
+++ b/src/engine/ObjectSender.cpp
@@ -83,7 +83,7 @@ ObjectSender::send_patch(ClientInterface* client, const PatchImpl* patch, bool r
 		// Send connections
 		for (PatchImpl::Connections::const_iterator j = patch->connections().begin();
 				j != patch->connections().end(); ++j)
-			client->connect((*j)->src_port_path(), (*j)->dst_port_path());
+			client->connect(j->second->src_port_path(), j->second->dst_port_path());
 	}
 
 	if (bundle)
diff --git a/src/engine/PatchImpl.cpp b/src/engine/PatchImpl.cpp
index 7ee82803..309ac3f8 100644
--- a/src/engine/PatchImpl.cpp
+++ b/src/engine/PatchImpl.cpp
@@ -112,7 +112,7 @@ PatchImpl::prepare_internal_poly(BufferFactory& bufs, uint32_t poly)
 		(*i)->prepare_poly(bufs, poly);
 
 	for (Connections::iterator i = _connections.begin(); i != _connections.end(); ++i)
-		((ConnectionImpl*)i->get())->prepare_poly(bufs, poly);
+		((ConnectionImpl*)i->second.get())->prepare_poly(bufs, poly);
 
 	return true;
 }
@@ -129,7 +129,7 @@ PatchImpl::apply_internal_poly(ProcessContext& context, BufferFactory& bufs, Rau
 		(*i)->apply_poly(maid, poly);
 
 	for (Connections::iterator i = _connections.begin(); i != _connections.end(); ++i)
-		((ConnectionImpl*)i->get())->apply_poly(maid, poly);
+		((ConnectionImpl*)i->second.get())->apply_poly(maid, poly);
 
 	for (List<NodeImpl*>::iterator i = _nodes.begin(); i != _nodes.end(); ++i) {
 		for (uint32_t j = 0; j < (*i)->num_ports(); ++j) {
@@ -301,42 +301,39 @@ PatchImpl::remove_node(const Raul::Symbol& symbol)
 }
 
 
+void
+PatchImpl::add_connection(SharedPtr<ConnectionImpl> c)
+{
+	ThreadManager::assert_thread(THREAD_PRE_PROCESS);
+	_connections.insert(make_pair(make_pair(c->src_port(), c->dst_port()), c));
+}
+
+
 /** Remove a connection.
  * Preprocessing thread only.
  */
-PatchImpl::Connections::Node*
+SharedPtr<ConnectionImpl>
 PatchImpl::remove_connection(const PortImpl* src_port, const PortImpl* dst_port)
 {
 	ThreadManager::assert_thread(THREAD_PRE_PROCESS);
-	bool found = false;
-	Connections::Node* connection = NULL;
-	for (Connections::iterator i = _connections.begin(); i != _connections.end(); ++i) {
-		ConnectionImpl* const c = (ConnectionImpl*)i->get();
-		if (c->src_port() == src_port && c->dst_port() == dst_port) {
-			connection = _connections.erase(i);
-			found = true;
-			break;
-		}
-	}
-
-	if ( ! found)
+	Connections::iterator i = _connections.find(make_pair(src_port, dst_port));
+	if (i != _connections.end()) {
+		SharedPtr<ConnectionImpl> c = PtrCast<ConnectionImpl>(i->second);
+		_connections.erase(i);
+		return c;
+	} else {
 		error << "[PatchImpl::remove_connection] Connection not found" << endl;
-
-	return connection;
+		return SharedPtr<ConnectionImpl>();
+	}
 }
 
 
 bool
 PatchImpl::has_connection(const PortImpl* src_port, const PortImpl* dst_port) const
 {
-	// FIXME: Doesn't scale
-	for (Connections::const_iterator i = _connections.begin(); i != _connections.end(); ++i) {
-		ConnectionImpl* const c = (ConnectionImpl*)i->get();
-		if (c->src_port() == src_port && c->dst_port() == dst_port)
-			return true;
-	}
-
-	return false;
+	ThreadManager::assert_thread(THREAD_PRE_PROCESS);
+	Connections::const_iterator i = _connections.find(make_pair(src_port, dst_port));
+	return (i != _connections.end());
 }
 
 
@@ -479,10 +476,10 @@ PatchImpl::compile() const
 
 	// Add any queued connections that must be run after a cycle
 	for (Connections::const_iterator i = _connections.begin(); i != _connections.end(); ++i) {
-		ConnectionImpl* const c = (ConnectionImpl*)i->get();
+		SharedPtr<ConnectionImpl> c = PtrCast<ConnectionImpl>(i->second);
 		if (c->src_port()->context() == Context::AUDIO &&
 				c->dst_port()->context() == Context::MESSAGE) {
-			compiled_patch->queued_connections.push_back(c);
+			compiled_patch->queued_connections.push_back(c.get());
 		}
 	}
 
diff --git a/src/engine/PatchImpl.hpp b/src/engine/PatchImpl.hpp
index ff2f0631..9bc2614d 100644
--- a/src/engine/PatchImpl.hpp
+++ b/src/engine/PatchImpl.hpp
@@ -102,8 +102,9 @@ public:
 	Raul::List<PortImpl*>::Node* remove_port(const std::string& name);
 	void                   clear_ports();
 
-	void               add_connection(Connections::Node* c) { _connections.push_back(c); }
-	Connections::Node* remove_connection(const PortImpl* src_port, const PortImpl* dst_port);
+	void add_connection(SharedPtr<ConnectionImpl> c);
+
+	SharedPtr<ConnectionImpl> remove_connection(const PortImpl* src_port, const PortImpl* dst_port);
 
 	bool has_connection(const PortImpl* src_port, const PortImpl* dst_port) const;
 
diff --git a/src/engine/events/Connect.cpp b/src/engine/events/Connect.cpp
index fac11965..b4389438 100644
--- a/src/engine/events/Connect.cpp
+++ b/src/engine/events/Connect.cpp
@@ -52,7 +52,6 @@ Connect::Connect(Engine& engine, SharedPtr<Request> request, SampleCount timesta
 	, _src_output_port(NULL)
 	, _dst_input_port(NULL)
 	, _compiled_patch(NULL)
-	, _patch_listnode(NULL)
 	, _port_listnode(NULL)
 	, _buffers(NULL)
 {
@@ -149,8 +148,9 @@ Connect::pre_process()
 		return;
 	}
 
-	_connection = SharedPtr<ConnectionImpl>(new ConnectionImpl(*_engine.buffer_factory(), _src_port, _dst_port));
-	_patch_listnode = new PatchImpl::Connections::Node(_connection);
+	_connection = SharedPtr<ConnectionImpl>(
+			new ConnectionImpl(*_engine.buffer_factory(), _src_port, _dst_port));
+
 	_port_listnode = new InputPort::Connections::Node(_connection);
 
 	// Need to be careful about patch port connections here and adding a node's
@@ -160,7 +160,7 @@ Connect::pre_process()
 		src_node->dependants()->push_back(new Raul::List<NodeImpl*>::Node(dst_node));
 	}
 
-	_patch->add_connection(_patch_listnode);
+	_patch->add_connection(_connection);
 	_dst_input_port->increment_num_connections();
 
 	switch (_dst_input_port->num_connections()) {
diff --git a/src/engine/events/Connect.hpp b/src/engine/events/Connect.hpp
index 90fba0d9..322a5dbf 100644
--- a/src/engine/events/Connect.hpp
+++ b/src/engine/events/Connect.hpp
@@ -78,7 +78,6 @@ private:
 	CompiledPatch* _compiled_patch; ///< New process order for Patch
 
 	SharedPtr<ConnectionImpl>     _connection;
-	PatchImpl::Connections::Node* _patch_listnode;
 	InputPort::Connections::Node* _port_listnode;
 
 	Raul::Array<BufferFactory::Ref>* _buffers;
diff --git a/src/engine/events/Disconnect.cpp b/src/engine/events/Disconnect.cpp
index 653933b7..250dc234 100644
--- a/src/engine/events/Disconnect.cpp
+++ b/src/engine/events/Disconnect.cpp
@@ -51,7 +51,6 @@ Disconnect::Disconnect(
 	, _patch(NULL)
 	, _src_port(NULL)
 	, _dst_port(NULL)
-	, _patch_connection(NULL)
 	, _compiled_patch(NULL)
 	, _buffers(NULL)
 	, _internal(false)
@@ -62,12 +61,12 @@ Disconnect::Disconnect(
 
 
 Disconnect::Disconnect(
-		Engine&              engine,
-		SharedPtr<Request>   request,
-		SampleCount          timestamp,
-		PortImpl* const      src_port,
-		PortImpl* const      dst_port,
-		bool                 reconnect_dst_port)
+		Engine&            engine,
+		SharedPtr<Request> request,
+		SampleCount        timestamp,
+		PortImpl* const    src_port,
+		PortImpl* const    dst_port,
+		bool               reconnect_dst_port)
 	: QueuedEvent(engine, request, timestamp)
 	, _src_port_path(src_port->path())
 	, _dst_port_path(dst_port->path())
@@ -157,7 +156,7 @@ Disconnect::pre_process()
 			break;
 		}
 
-	_patch_connection = _patch->remove_connection(_src_port, _dst_port);
+	_connection = _patch->remove_connection(_src_port, _dst_port);
 	_dst_input_port->decrement_num_connections();
 
 	if (_dst_input_port->num_connections() == 0) {
@@ -180,9 +179,9 @@ Disconnect::execute(ProcessContext& context)
 	QueuedEvent::execute(context);
 
 	if (_error == NO_ERROR) {
-		InputPort::Connections::Node* const port_connection
+		InputPort::Connections::Node* const port_connections_node
 			= _dst_input_port->remove_connection(context, _src_output_port);
-		port_connection->elem()->recycle_buffer();
+		port_connections_node->elem()->recycle_buffer();
 		if (_reconnect_dst_port) {
 			if (_buffers)
 				_engine.maid()->push(_dst_input_port->set_buffers(_buffers));
@@ -204,13 +203,11 @@ Disconnect::execute(ProcessContext& context)
 			_dst_input_port->recycle_buffers();
 		}
 
-		if (port_connection != NULL) {
-			assert(_patch_connection);
-			assert(port_connection->elem() == _patch_connection->elem());
+		if (port_connections_node) {
+			assert(_connection);
+			assert(port_connections_node->elem() == _connection);
 
-			// Destroy list node, which will drop reference to connection itself
-			_engine.maid()->push(port_connection);
-			_engine.maid()->push(_patch_connection);
+			_engine.maid()->push(port_connections_node);
 
 			if (!_internal) {
 				_engine.maid()->push(_patch->compiled_patch());
@@ -231,8 +228,32 @@ Disconnect::post_process()
             _request->respond_ok();
         _engine.broadcaster()->disconnect(_src_port->path(), _dst_port->path());
     } else {
-        string msg = "Unable to disconnect ";
-        msg.append(_src_port_path.str() + " -> " + _dst_port_path.str());
+        string msg("Unable to disconnect ");
+        msg.append(_src_port_path.str() + " => " + _dst_port_path.str());
+		msg.append(" (");
+		switch (_error) {
+		case PARENT_PATCH_DIFFERENT:
+			msg.append("Ports exist in different patches");
+			break;
+		case PORT_NOT_FOUND:
+			msg.append("Port not found");
+			break;
+		case TYPE_MISMATCH:
+			msg.append("Ports have incompatible types");
+			break;
+		case NOT_CONNECTED:
+			msg.append("Ports are not connected");
+			break;
+		case PARENTS_NOT_FOUND:
+			msg.append("Parent node not found");
+			break;
+		case CONNECTION_NOT_FOUND:
+			msg.append("Connection not found");
+			break;
+		default:
+			break;
+		}
+		msg.append(")");
         if (_request)
             _request->respond_error(msg);
     }
diff --git a/src/engine/events/Disconnect.hpp b/src/engine/events/Disconnect.hpp
index 3a8758ec..d0376001 100644
--- a/src/engine/events/Disconnect.hpp
+++ b/src/engine/events/Disconnect.hpp
@@ -86,7 +86,7 @@ private:
 	OutputPort* _src_output_port;
 	InputPort*  _dst_input_port;
 
-	PatchImpl::Connections::Node* _patch_connection;
+	SharedPtr<ConnectionImpl> _connection;
 	CompiledPatch* _compiled_patch; ///< New process order for Patch
 
 	Raul::Array<BufferFactory::Ref>* _buffers;
diff --git a/src/engine/events/DisconnectAll.cpp b/src/engine/events/DisconnectAll.cpp
index 38ed7102..7b10b3f4 100644
--- a/src/engine/events/DisconnectAll.cpp
+++ b/src/engine/events/DisconnectAll.cpp
@@ -112,7 +112,7 @@ DisconnectAll::pre_process()
 	if (_node) {
 		for (PatchImpl::Connections::const_iterator i = _parent->connections().begin();
 				i != _parent->connections().end(); ++i) {
-			ConnectionImpl* c = (ConnectionImpl*)i->get();
+			ConnectionImpl* c = (ConnectionImpl*)i->second.get();
 			const bool reconnect_input = !_deleting || (c->dst_port()->parent_node() != _node);
 			if ((c->src_port()->parent_node() == _node || c->dst_port()->parent_node() == _node)
 					&& !c->pending_disconnection()) {
@@ -126,7 +126,7 @@ DisconnectAll::pre_process()
 	} else { // _port
 		for (PatchImpl::Connections::const_iterator i = _parent->connections().begin();
 				i != _parent->connections().end(); ++i) {
-			ConnectionImpl* c = (ConnectionImpl*)i->get();
+			ConnectionImpl* c = (ConnectionImpl*)i->second.get();
 			const bool reconnect_input = !_deleting || (c->dst_port()->parent_node() != _node);
 			if ((c->src_port() == _port || c->dst_port() == _port) && !c->pending_disconnection()) {
 				Disconnect* ev = new Disconnect(_engine,