From 4861238c1624a193e30fc0aa78438b4977dbeb82 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Fri, 11 Feb 2011 18:15:18 +0000 Subject: Use GSequence for collections with get_by_uri search methods. Avoid constant sorting during plugin discovery. git-svn-id: http://svn.drobilla.net/lad/trunk/slv2@2919 a436a847-0d15-0410-975c-d299462d15a1 --- slv2/collections.h | 2 +- src/collections.c | 117 +++++++++++++++++++++++----------------------------- src/plugin.c | 10 ++--- src/pluginclass.c | 14 ++++--- src/plugins.c | 38 ++++------------- src/pluginui.c | 2 +- src/port.c | 2 +- src/query.c | 8 ++-- src/slv2_internal.h | 32 ++++++++++++-- src/world.c | 83 +++++++++++++++++++++++-------------- 10 files changed, 161 insertions(+), 147 deletions(-) diff --git a/slv2/collections.h b/slv2/collections.h index 4233917..9e816b0 100644 --- a/slv2/collections.h +++ b/slv2/collections.h @@ -70,7 +70,7 @@ prefix ## _size(CollType collection); \ SLV2_API \ ElemType \ prefix ## _get_at(CollType collection, \ - unsigned index); + unsigned index); SLV2_COLLECTION(SLV2PluginClasses, SLV2PluginClass, slv2_plugin_classes) SLV2_COLLECTION(SLV2ScalePoints, SLV2ScalePoint, slv2_scale_points) diff --git a/src/collections.c b/src/collections.c index 7e778a6..83c98f3 100644 --- a/src/collections.c +++ b/src/collections.c @@ -25,7 +25,9 @@ #include "slv2/pluginui.h" #include "slv2_internal.h" -#define SLV2_COLLECTION_IMPL(CollType, ElemType, prefix, free_func) \ +/* ARRAYS */ + +#define SLV2_ARRAY_IMPL(CollType, ElemType, prefix, free_func) \ \ CollType \ prefix ## _new() \ @@ -58,47 +60,63 @@ prefix ## _get_at(CollType coll, unsigned index) \ return (ElemType)g_ptr_array_index((GPtrArray*)coll, (int)index); \ } -SLV2_COLLECTION_IMPL(SLV2PluginClasses, SLV2PluginClass, - slv2_plugin_classes, &slv2_plugin_class_free) -SLV2_COLLECTION_IMPL(SLV2ScalePoints, SLV2ScalePoint, +SLV2_ARRAY_IMPL(SLV2ScalePoints, SLV2ScalePoint, slv2_scale_points, &slv2_scale_point_free) -SLV2_COLLECTION_IMPL(SLV2Values, SLV2Value, +SLV2_ARRAY_IMPL(SLV2Values, SLV2Value, slv2_values, &slv2_value_free) -SLV2_COLLECTION_IMPL(SLV2UIs, SLV2UI, - slv2_uis, &slv2_ui_free) - -/* **** PLUGIN CLASSES **** */ - -SLV2_API -SLV2PluginClass -slv2_plugin_classes_get_by_uri(SLV2PluginClasses list, SLV2Value uri) -{ - // good old fashioned binary search - int lower = 0; - int upper = ((GPtrArray*)list)->len - 1; - int i; - while (upper >= lower) { - i = lower + ((upper - lower) / 2); +/* SEQUENCE */ - SLV2PluginClass p = g_ptr_array_index(((GPtrArray*)list), i); - - const int cmp = strcmp(slv2_value_as_uri(slv2_plugin_class_get_uri(p)), - slv2_value_as_uri(uri)); +#define SLV2_SEQUENCE_IMPL(CollType, ElemType, prefix, free_func) \ +\ +CollType \ +prefix ## _new() \ +{ \ + return g_sequence_new((GDestroyNotify)free_func); \ +} \ +\ +SLV2_API \ +void \ +prefix ## _free(CollType coll) \ +{ \ + if (coll) \ + g_sequence_free((GSequence*)coll); \ +} \ +\ +SLV2_API \ +unsigned \ +prefix ## _size(CollType coll) \ +{ \ + return (coll ? g_sequence_get_length((GSequence*)coll) : 0); \ +} \ +\ +SLV2_API \ +ElemType \ +prefix ## _get_at(CollType coll, unsigned index) \ +{ \ + if (!coll || index >= prefix ## _size(coll)) { \ + return NULL; \ + } else { \ + GSequenceIter* i = g_sequence_get_iter_at_pos((GSequence*)coll, (int)index); \ + return (ElemType)g_sequence_get(i); \ + } \ +} \ +\ +SLV2_API \ +ElemType \ +prefix ## _get_by_uri(CollType coll, SLV2Value uri) \ +{ \ + return (ElemType)slv2_sequence_get_by_uri(coll, uri); \ +} - if (cmp == 0) - return p; - else if (cmp > 0) - upper = i - 1; - else - lower = i + 1; - } +SLV2_SEQUENCE_IMPL(SLV2PluginClasses, SLV2PluginClass, + slv2_plugin_classes, &slv2_plugin_class_free) +SLV2_SEQUENCE_IMPL(SLV2UIs, SLV2UI, + slv2_uis, &slv2_ui_free) - return NULL; -} -/* **** VALUES **** */ +/* VALUES */ SLV2_API bool @@ -111,34 +129,3 @@ slv2_values_contains(SLV2Values list, SLV2Value value) return false; } -/* **** PLUGIN UIS **** */ - -SLV2_API -SLV2UI -slv2_uis_get_by_uri(SLV2UIs list, SLV2Value uri) -{ - // good old fashioned binary search - - int lower = 0; - int upper = ((GPtrArray*)list)->len - 1; - int i; - - while (upper >= lower) { - i = lower + ((upper - lower) / 2); - - SLV2UI ui = g_ptr_array_index((GPtrArray*)list, i); - - const int cmp = strcmp(slv2_value_as_uri(slv2_ui_get_uri(ui)), - slv2_value_as_uri(uri)); - - if (cmp == 0) - return ui; - else if (cmp > 0) - upper = i - 1; - else - lower = i + 1; - } - - return NULL; -} - diff --git a/src/plugin.c b/src/plugin.c index 2bdae5c..279c657 100644 --- a/src/plugin.c +++ b/src/plugin.c @@ -102,7 +102,7 @@ slv2_plugin_query_node(SLV2Plugin p, SLV2Node subject, SLV2Node predicate) SLV2Node node = slv2_match_object(results); SLV2Value value = slv2_value_new_from_node(p->world, node); if (value) - g_ptr_array_add(result, value); + slv2_array_append(result, value); } slv2_match_end(results); @@ -246,7 +246,7 @@ slv2_plugin_load_ports_if_necessary(SLV2Plugin p) FOREACH_MATCH(types) { SLV2Node type = slv2_match_object(types); if (sord_node_get_type(type) == SORD_URI) { - g_ptr_array_add( + slv2_array_append( this_port->classes, slv2_value_new_from_node(p->world, type)); } else { @@ -637,9 +637,9 @@ slv2_plugin_get_supported_features(SLV2Plugin p) unsigned n_optional = slv2_values_size(optional); unsigned n_required = slv2_values_size(required); for (unsigned i = 0 ; i < n_optional; ++i) - g_ptr_array_add(result, slv2_values_get_at(optional, i)); + slv2_array_append(result, slv2_values_get_at(optional, i)); for (unsigned i = 0 ; i < n_required; ++i) - g_ptr_array_add(result, slv2_values_get_at(required, i)); + slv2_array_append(result, slv2_values_get_at(required, i)); if (optional) { free(((GPtrArray*)optional)->pdata); @@ -797,7 +797,7 @@ slv2_plugin_get_uis(SLV2Plugin p) type, binary); - g_ptr_array_add(result, slv2_ui); + slv2_sequence_insert(result, slv2_ui); } slv2_match_end(uis); diff --git a/src/pluginclass.c b/src/pluginclass.c index 27486ea..4aef8f4 100644 --- a/src/pluginclass.c +++ b/src/pluginclass.c @@ -85,14 +85,16 @@ SLV2PluginClasses slv2_plugin_class_get_children(SLV2PluginClass plugin_class) { // Returned list doesn't own categories - SLV2PluginClasses result = g_ptr_array_new(); + SLV2PluginClasses all = plugin_class->world->plugin_classes; + SLV2PluginClasses result = g_sequence_new(NULL); - for (unsigned i = 0; i < ((GPtrArray*)plugin_class->world->plugin_classes)->len; ++i) { - SLV2PluginClass c = g_ptr_array_index( - (GPtrArray*)plugin_class->world->plugin_classes, i); - SLV2Value parent = slv2_plugin_class_get_parent_uri(c); + for (GSequenceIter* i = g_sequence_get_begin_iter(all); + i != g_sequence_get_end_iter(all); + i = g_sequence_iter_next(i)) { + SLV2PluginClass c = g_sequence_get(i); + SLV2Value parent = slv2_plugin_class_get_parent_uri(c); if (parent && slv2_value_equals(slv2_plugin_class_get_uri(plugin_class), parent)) - g_ptr_array_add(result, c); + slv2_sequence_insert(result, c); } return result; diff --git a/src/plugins.c b/src/plugins.c index 0f9587f..30bc076 100644 --- a/src/plugins.c +++ b/src/plugins.c @@ -31,7 +31,7 @@ SLV2Plugins slv2_plugins_new() { - return g_ptr_array_new(); + return g_sequence_new(NULL); } SLV2_API @@ -39,52 +39,32 @@ void slv2_plugins_free(SLV2World world, SLV2Plugins list) { if (list && list != world->plugins) - g_ptr_array_unref(list); + g_sequence_free(list); } SLV2_API unsigned slv2_plugins_size(SLV2Plugins list) { - return (list ? ((GPtrArray*)list)->len : 0); + return (list ? g_sequence_get_length((GSequence*)list) : 0); \ } SLV2_API SLV2Plugin slv2_plugins_get_by_uri(SLV2Plugins list, SLV2Value uri) { - // good old fashioned binary search - - int lower = 0; - int upper = ((GPtrArray*)list)->len - 1; - int i; - - while (upper >= lower) { - i = lower + ((upper - lower) / 2); - - SLV2Plugin p = g_ptr_array_index((GPtrArray*)list, i); - - const int cmp = strcmp(slv2_value_as_uri(slv2_plugin_get_uri(p)), - slv2_value_as_uri(uri)); - - if (cmp == 0) - return p; - else if (cmp > 0) - upper = i - 1; - else - lower = i + 1; - } - - return NULL; + return (SLV2Plugin)slv2_sequence_get_by_uri(list, uri); } SLV2_API SLV2Plugin slv2_plugins_get_at(SLV2Plugins list, unsigned index) { - if (index > INT_MAX) + if (!list || index >= slv2_plugins_size(list)) { return NULL; - else - return (SLV2Plugin)g_ptr_array_index((GPtrArray*)list, (int)index); + } else { + GSequenceIter* i = g_sequence_get_iter_at_pos((GSequence*)list, (int)index); + return (SLV2Plugin)g_sequence_get(i); + } } diff --git a/src/pluginui.c b/src/pluginui.c index f4c2980..8778d3a 100644 --- a/src/pluginui.c +++ b/src/pluginui.c @@ -49,7 +49,7 @@ slv2_ui_new(SLV2World world, free(bundle); ui->classes = slv2_values_new(); - g_ptr_array_add(ui->classes, type_uri); + slv2_array_append(ui->classes, type_uri); return ui; } diff --git a/src/port.c b/src/port.c index 615d38f..fd44512 100644 --- a/src/port.c +++ b/src/port.c @@ -289,7 +289,7 @@ slv2_port_get_scale_points(SLV2Plugin p, slv2_node_copy(p->world->rdfs_label_node)); if (value && label) { - g_ptr_array_add(ret, slv2_scale_point_new(value, label)); + slv2_array_append(ret, slv2_scale_point_new(value, label)); } } slv2_match_end(points); diff --git a/src/query.c b/src/query.c index 9382fdc..4e60b41 100644 --- a/src/query.c +++ b/src/query.c @@ -94,13 +94,13 @@ slv2_values_from_stream_objects_i18n(SLV2Plugin p, if (lm == SLV2_LANG_MATCH_EXACT) { // Exact language match, add to results - g_ptr_array_add(values, slv2_value_new_from_node(p->world, value)); + slv2_array_append(values, slv2_value_new_from_node(p->world, value)); } else if (lm == SLV2_LANG_MATCH_PARTIAL) { // Partial language match, save in case we find no exact partial = value; } } else { - g_ptr_array_add(values, slv2_value_new_from_node(p->world, value)); + slv2_array_append(values, slv2_value_new_from_node(p->world, value)); } } slv2_match_end(stream); @@ -121,7 +121,7 @@ slv2_values_from_stream_objects_i18n(SLV2Plugin p, } if (best) { - g_ptr_array_add(values, slv2_value_new_from_node(p->world, best)); + slv2_array_append(values, slv2_value_new_from_node(p->world, best)); } else { // No matches whatsoever slv2_values_free(values); @@ -143,7 +143,7 @@ slv2_values_from_stream_objects(SLV2Plugin p, } else { SLV2Values values = slv2_values_new(); FOREACH_MATCH(stream) { - g_ptr_array_add( + slv2_array_append( values, slv2_value_new_from_node( p->world, diff --git a/src/slv2_internal.h b/src/slv2_internal.h index 4424467..55f5b93 100644 --- a/src/slv2_internal.h +++ b/src/slv2_internal.h @@ -91,6 +91,15 @@ void slv2_port_free(SLV2Port port); /* ********* Plugin ********* */ +/** Header of an SLV2Plugin, SLV2PluginClass, or SLV2UI. + * Any of these structs may be safely casted to _SLV2Header, which is used to + * implement sequences without code duplication (see slv2_sequence_get_by_uri). + */ +struct _SLV2Header { + struct _SLV2World* world; + SLV2Value uri; +}; + /** Record of an installed/available plugin. * * A simple reference to a plugin somewhere on the system. This just holds @@ -103,7 +112,7 @@ struct _SLV2Plugin { SLV2Value binary_uri; ///< lv2:binary SLV2Value dynman_uri; ///< dynamic manifest binary SLV2PluginClass plugin_class; - GPtrArray* data_uris; ///< rdfs::seeAlso + SLV2Values data_uris; ///< rdfs::seeAlso SLV2Port* ports; uint32_t num_ports; bool loaded; @@ -150,8 +159,8 @@ struct _SLV2UIInstanceImpl { struct _SLV2PluginClass { struct _SLV2World* world; - SLV2Value parent_uri; SLV2Value uri; + SLV2Value parent_uri; SLV2Value label; }; @@ -260,6 +269,23 @@ SLV2Value slv2_value_new(SLV2World world, SLV2ValueType type, const char* val); SLV2Value slv2_value_new_from_node(SLV2World world, SLV2Node node); SLV2Node slv2_value_as_node(SLV2Value value); +int +slv2_header_compare_by_uri(const void* a, const void* b, void* user_data); + +static inline void +slv2_sequence_insert(GSequence* seq, void* value) +{ + g_sequence_insert_sorted(seq, value, slv2_header_compare_by_uri, NULL); +} + +static inline void +slv2_array_append(GPtrArray* array, void* value) { + g_ptr_array_add(array, value); +} + +struct _SLV2Header* +slv2_sequence_get_by_uri(GSequence* seq, SLV2Value uri); + static inline SLV2Node slv2_node_copy(SLV2Node node) { return node; } @@ -279,7 +305,7 @@ SLV2ScalePoint slv2_scale_point_new(SLV2Value value, SLV2Value label); void slv2_scale_point_free(SLV2ScalePoint point); -/* ********* Query Results********* */ +/* ********* Query Results ********* */ SLV2Matches slv2_plugin_find_statements(SLV2Plugin plugin, SLV2Node subject, diff --git a/src/world.c b/src/world.c index 6cb0bad..d7dbd9d 100644 --- a/src/world.c +++ b/src/world.c @@ -141,12 +141,14 @@ slv2_world_free(SLV2World world) slv2_value_free(world->doap_name_val); slv2_value_free(world->lv2_name_val); + /* for (unsigned i = 0; i < ((GPtrArray*)world->plugins)->len; ++i) slv2_plugin_free(g_ptr_array_index((GPtrArray*)world->plugins, i)); g_ptr_array_unref(world->plugins); + */ world->plugins = NULL; - g_ptr_array_unref(world->plugin_classes); + //g_ptr_array_unref(world->plugin_classes); world->plugin_classes = NULL; sord_free(world->model); @@ -197,15 +199,44 @@ slv2_world_blank_node_prefix(SLV2World world) return (const uint8_t*)str; } -/** Comparator for sorting SLV2Plugins */ -static int -slv2_plugin_compare_by_uri(const void* a, const void* b) +/** Comparator for sequences (e.g. world->plugins). */ +int +slv2_header_compare_by_uri(const void* a, const void* b, void* user_data) +{ + const struct _SLV2Header* const header_a = (const struct _SLV2Header*)a; + const struct _SLV2Header* const header_b = (const struct _SLV2Header*)b; + return strcmp(slv2_value_as_uri(header_a->uri), + slv2_value_as_uri(header_b->uri)); +} + +/** Get an element of a sequence of any object with an SLV2Header by URI. */ +struct _SLV2Header* +slv2_sequence_get_by_uri(GSequence* seq, + SLV2Value uri) { - SLV2Plugin plugin_a = *(SLV2Plugin*)a; - SLV2Plugin plugin_b = *(SLV2Plugin*)b; + struct _SLV2Header key = { NULL, uri }; + GSequenceIter* i = g_sequence_search( + seq, &key, slv2_header_compare_by_uri, NULL); + + // i points to where plugin would be inserted (not necessarily a match) + + if (!g_sequence_iter_is_end(i)) { + SLV2Plugin p = g_sequence_get(i); + if (slv2_value_equals(slv2_plugin_get_uri(p), uri)) { + return (struct _SLV2Header*)p; + } + } + + if (!g_sequence_iter_is_begin(i)) { + // Check if i is just past a match + i = g_sequence_iter_prev(i); + SLV2Plugin p = g_sequence_get(i); + if (slv2_value_equals(slv2_plugin_get_uri(p), uri)) { + return (struct _SLV2Header*)p; + } + } - return strcmp(slv2_value_as_uri(plugin_a->plugin_uri), - slv2_value_as_uri(plugin_b->plugin_uri)); + return NULL; } SLV2_API @@ -325,11 +356,11 @@ slv2_world_load_bundle(SLV2World world, SLV2Value bundle_uri) SLV2Node plugin_node = slv2_match_subject(plug_results); SLV2Value plugin_uri = slv2_value_new_from_node(world, plugin_node); - SLV2Plugin existing = slv2_plugins_get_by_uri(world->plugins, plugin_uri); - if (existing) { + SLV2Plugin last = slv2_plugins_get_by_uri(world->plugins, plugin_uri); + if (last) { SLV2_ERRORF("Duplicate plugin <%s>\n", slv2_value_as_uri(plugin_uri)); SLV2_ERRORF("... found in %s\n", slv2_value_as_string( - slv2_plugin_get_bundle_uri(existing))); + slv2_plugin_get_bundle_uri(last))); SLV2_ERRORF("... and %s\n", sord_node_get_string(bundle_node)); slv2_value_free(plugin_uri); continue; @@ -340,8 +371,8 @@ slv2_world_load_bundle(SLV2World world, SLV2Value bundle_uri) SLV2Plugin plugin = slv2_plugin_new(world, plugin_uri, bundle_uri); // Add manifest as plugin data file (as if it were rdfs:seeAlso) - g_ptr_array_add(plugin->data_uris, - slv2_value_new_uri(world, (const char*)manifest_uri.buf)); + slv2_array_append(plugin->data_uris, + slv2_value_new_uri(world, (const char*)manifest_uri.buf)); // Add all plugin data files (rdfs:seeAlso) SLV2Matches files = slv2_world_find_statements( @@ -352,13 +383,12 @@ slv2_world_load_bundle(SLV2World world, SLV2Value bundle_uri) NULL); FOREACH_MATCH(files) { SLV2Node file_node = slv2_match_object(files); - g_ptr_array_add(plugin->data_uris, - slv2_value_new_from_node(world, file_node)); + slv2_array_append(plugin->data_uris, + slv2_value_new_from_node(world, file_node)); } - // Add plugin to world plugin list (FIXME: slow, use real data structure) - g_ptr_array_add(world->plugins, plugin); - g_ptr_array_sort(world->plugins, slv2_plugin_compare_by_uri); + // Add plugin to world plugin sequence + slv2_sequence_insert(world->plugins, plugin); } slv2_match_end(plug_results); @@ -568,22 +598,11 @@ slv2_world_load_plugin_classes(SLV2World world) slv2_match_end(labels); SLV2PluginClasses classes = world->plugin_classes; -#ifndef NDEBUG - const unsigned n_classes = ((GPtrArray*)classes)->len; - if (n_classes > 0) { - // Class results are in increasing sorted order - SLV2PluginClass prev = g_ptr_array_index((GPtrArray*)classes, - n_classes - 1); - assert(strcmp( - slv2_value_as_string(slv2_plugin_class_get_uri(prev)), - (const char*)sord_node_get_string(class_node)) < 0); - } -#endif - SLV2PluginClass pclass = slv2_plugin_class_new( + SLV2PluginClass pclass = slv2_plugin_class_new( world, parent_node, class_node, (const char*)label); if (pclass) { - g_ptr_array_add(classes, pclass); + slv2_sequence_insert(classes, pclass); } slv2_node_free(parent_node); @@ -661,7 +680,7 @@ slv2_world_get_plugins_by_filter(SLV2World world, bool (*include)(SLV2Plugin)) for (unsigned i = 0; i < n; ++i) { SLV2Plugin p = slv2_plugins_get_at(world->plugins, i); if (include(p)) - g_ptr_array_add(result, p); + slv2_sequence_insert(result, p); } return result; -- cgit v1.2.1