From e22984efe9b82ab006494aea93814a592cd44ece Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 25 Feb 2010 03:40:39 +0000 Subject: Store patch connections in a map using a lexicographic 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 --- src/engine/InputPort.cpp | 6 ++-- src/engine/MessageContext.cpp | 2 +- src/engine/ObjectSender.cpp | 2 +- src/engine/PatchImpl.cpp | 51 ++++++++++++++++----------------- src/engine/PatchImpl.hpp | 5 ++-- src/engine/events/Connect.cpp | 8 +++--- src/engine/events/Connect.hpp | 1 - src/engine/events/Disconnect.cpp | 57 +++++++++++++++++++++++++------------ src/engine/events/Disconnect.hpp | 2 +- src/engine/events/DisconnectAll.cpp | 4 +-- 10 files changed, 79 insertions(+), 59 deletions(-) (limited to 'src/engine') 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(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::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 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 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 c = PtrCast(i->second); + _connections.erase(i); + return c; + } else { error << "[PatchImpl::remove_connection] Connection not found" << endl; - - return connection; + return SharedPtr(); + } } 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 c = PtrCast(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::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 c); + + SharedPtr 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, 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(new ConnectionImpl(*_engine.buffer_factory(), _src_port, _dst_port)); - _patch_listnode = new PatchImpl::Connections::Node(_connection); + _connection = SharedPtr( + 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::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 _connection; - PatchImpl::Connections::Node* _patch_listnode; InputPort::Connections::Node* _port_listnode; Raul::Array* _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, - SampleCount timestamp, - PortImpl* const src_port, - PortImpl* const dst_port, - bool reconnect_dst_port) + Engine& engine, + SharedPtr 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 _connection; CompiledPatch* _compiled_patch; ///< New process order for Patch Raul::Array* _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, -- cgit v1.2.1