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

9 files changed, 160 insertions, 146 deletions

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;