Add a real URI map implementation.

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

5 files changed, 321 insertions, 12 deletions

diff --git a/src/jalv.c b/src/jalv.c
index de50521..e13a858 100644
--- a/src/jalv.c
+++ b/src/jalv.c
@@ -64,18 +64,16 @@ struct Port {
 	bool              is_input;
 };
 
-/** URI map feature, for event types (we use only MIDI) */
-#define MIDI_EVENT_ID 1
+/**
+   Map function for URI map extension.
+*/
 uint32_t
 uri_to_id(LV2_URI_Map_Callback_Data callback_data,
           const char*               map,
           const char*               uri)
 {
-	/* Note a non-trivial host needs to use an actual dictionary here */
-	if (!strcmp(map, LV2_EVENT_URI) && !strcmp(uri, LILV_URI_MIDI_EVENT))
-		return MIDI_EVENT_ID;
-	else
-		return 0;  /* Refuse to map ID */
+	Jalv* host = (Jalv*)callback_data;
+	return symap_map(host->symap, uri);
 }
 
 #define NS_EXT "http://lv2plug.in/ns/ext/"
@@ -210,7 +208,8 @@ jack_process_cb(jack_nframes_t nframes, void* data)
 					jack_midi_event_get(&ev, buf, i);
 					lv2_event_write(&iter,
 					                ev.time, 0,
-					                MIDI_EVENT_ID, ev.size, ev.buffer);
+					                host->midi_event_id,
+					                ev.size, ev.buffer);
 				}
 			}
 		}
@@ -312,6 +311,12 @@ main(int argc, char** argv)
 	host.num_ports   = 0;
 	host.ports       = NULL;
 
+	host.symap = symap_new();
+	uri_map.callback_data = &host;
+	host.midi_event_id = uri_to_id(&host,
+	                               "http://lv2plug.in/ns/ext/event",
+	                               "http://lv2plug.in/ns/ext/midi#MidiEvent");
+
 	host.events = jack_ringbuffer_create(4096);
 	jack_ringbuffer_mlock(host.events);
 
@@ -502,6 +507,7 @@ main(int argc, char** argv)
 	lilv_node_free(host.event_class);
 	lilv_node_free(host.midi_class);
 	lilv_node_free(host.optional);
+	symap_free(host.symap);
 	suil_instance_free(ui_instance);
 	suil_host_free(ui_host);
 	lilv_world_free(world);
diff --git a/src/jalv_internal.h b/src/jalv_internal.h
index aa50df0..5ee7755 100644
--- a/src/jalv_internal.h
+++ b/src/jalv_internal.h
@@ -26,14 +26,17 @@
 
 #include "suil/suil.h"
 
+#include "symap.h"
+
 #ifdef __cplusplus
 extern "C" {
 #endif
 
 typedef struct {
 	LilvWorld*         world;         /**< Lilv World */
+	Symap*             symap;         /**< Symbol (URI) map */
 	jack_client_t*     jack_client;   /**< Jack client */
-	jack_ringbuffer_t* events;        /***< Control change events */
+	jack_ringbuffer_t* events;        /**< Control change events */
 	sem_t*             done;          /**< Exit semaphore */
 	const LilvPlugin*  plugin;        /**< Plugin class (RDF data) */
 	LilvInstance*      instance;      /**< Plugin instance (shared library) */
@@ -46,6 +49,7 @@ typedef struct {
 	LilvNode*          event_class;   /**< Event port class (URI) */
 	LilvNode*          midi_class;    /**< MIDI event class (URI) */
 	LilvNode*          optional;      /**< lv2:connectionOptional port property */
+	uint32_t           midi_event_id; /**< MIDI event class ID */
 } Jalv;
 
 void
diff --git a/src/symap.c b/src/symap.c
new file mode 100644
index 0000000..cbbb590
--- /dev/null
+++ b/src/symap.c
@@ -0,0 +1,229 @@
+/*
+  Copyright 2011 David Robillard <http://drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "symap.h"
+
+/**
+  @file symap.c Implementation of Symap, a basic symbol map (string interner).
+
+  This implementation is primitive, but has some desirable qualities: good
+  (O(lg(n)) lookup performance for already-mapped symbols, minimal space
+  overhead, extremely fast (O(1)) reverse mapping (ID to string), simple code,
+  no dependencies.
+
+  The tradeoff is that mapping new symbols may be quite slow.  In other words,
+  this implementation is ideal for use cases with a relatively limited set of
+  symbols, or where most symbols are mapped early.  It will not fare so well
+  with very dynamic sets of symbols.  For that, you're better off with a
+  tree-based implementation (and the associated space cost, especially if you
+  need reverse mapping).
+*/
+
+struct SymapImpl {
+	/**
+	   Unsorted array of strings, such that the symbol for ID i is found
+	   at symbols[i - 1].
+	*/
+	char** symbols;
+
+	/**
+	   Array of IDs, sorted by corresponding string in @ref symbols.
+	*/
+	uint32_t* index;
+
+	/**
+	   Number of symbols (number of items in @ref symbols and @ref index).
+	*/
+	uint32_t size;
+};
+
+Symap*
+symap_new()
+{
+	Symap* map = (Symap*)malloc(sizeof(Symap));
+	map->symbols = NULL;
+	map->index   = NULL;
+	map->size    = 0;
+	return map;
+}
+
+void
+symap_free(Symap* map)
+{
+	for (uint32_t i = 0; i < map->size; ++i) {
+		free(map->symbols[i]);
+	}
+
+	free(map->symbols);
+	free(map->index);
+	free(map);
+}
+
+static char*
+symap_strdup(const char* str)
+{
+	const size_t len  = strlen(str);
+	char*        copy = malloc(len + 1);
+	memcpy(copy, str, len + 1);
+	return copy;
+}
+
+/**
+   Return the index into map->index (not the ID) corresponding to @c sym,
+   or the index where a new entry for @c sym should be inserted.
+*/
+static uint32_t
+symap_search(const Symap* map, const char* sym, bool* exact)
+{
+	*exact = false;
+	if (map->size == 0) {
+		return 0;  // Empty map, insert at 0
+	} else if (strcmp(map->symbols[map->index[map->size - 1] - 1], sym) < 0) {
+		return map->size;  // Greater than last element, append
+	}
+
+	uint32_t lower = 0;
+	uint32_t upper = map->size - 1;
+	uint32_t i     = upper;
+	int      cmp;
+
+	while (upper >= lower) {
+		i   = lower + ((upper - lower) / 2);
+		cmp = strcmp(map->symbols[map->index[i] - 1], sym);
+
+		if (cmp == 0) {
+			*exact = true;
+			return i;
+		} else if (cmp > 0) {
+			if (i == 0) {
+				break;  // Avoid underflow
+			}
+			upper = i - 1;
+		} else {
+			lower = i + 1;
+		}
+	}
+
+	assert(strcmp(map->symbols[map->index[i] - 1], sym) > 0);
+	return i;
+}
+
+uint32_t
+symap_try_map(Symap* map, const char* sym)
+{
+	bool           exact;
+	const uint32_t index = symap_search(map, sym, &exact);
+	if (exact) {
+		assert(!strcmp(map->symbols[map->index[index]], sym));
+		return map->index[index];
+	}
+
+	return 0;
+}
+
+uint32_t
+symap_map(Symap* map, const char* sym)
+{
+	bool           exact;
+	const uint32_t index = symap_search(map, sym, &exact);
+	if (exact) {
+		assert(!strcmp(map->symbols[map->index[index] - 1], sym));
+		return map->index[index];
+	}
+
+	const uint32_t id  = ++map->size;
+	char* const    str = symap_strdup(sym);
+
+	/* Append new symbol to symbols array */
+	map->symbols = realloc(map->symbols, map->size * sizeof(char*));
+	map->symbols[id - 1] = str;
+
+	/* Insert new index element into sorted index */
+	map->index = realloc(map->index, map->size * sizeof(uint32_t));
+	if (index < map->size - 1) {
+		memmove(map->index + index + 1,
+		        map->index + index,
+		        (map->size - index - 1) * sizeof(uint32_t));
+	}
+
+	map->index[index] = id;
+
+	return id;
+}
+
+const char*
+symap_unmap(Symap* map, uint32_t id)
+{
+	if (id <= map->size) {
+		return map->symbols[id - 1];
+	}
+	return NULL;
+}
+
+#ifdef STANDALONE
+
+#include <stdio.h>
+
+static void
+symap_dump(Symap* map)
+{
+	fprintf(stderr, "{\n");
+	for (uint32_t i = 0; i < map->size; ++i) {
+		fprintf(stderr, "\t%u = %s\n", map->index[i], map->symbols[map->index[i] - 1]);
+	}
+	fprintf(stderr, "}\n");
+}
+
+
+int
+main()
+{
+	#define N_SYMS 5
+	char* syms[N_SYMS] = {
+		"hello", "bonjour", "goodbye", "aloha", "salut"
+	};
+
+	Symap* map = symap_new();
+	for (int i = 0; i < N_SYMS; ++i) {
+		if (symap_try_map(map, syms[i])) {
+			fprintf(stderr, "error: Symbol already mapped\n");
+			return 1;
+		}
+		
+		const uint32_t id = symap_map(map, syms[i]);
+		if (strcmp(map->symbols[id - 1], syms[i])) {
+			fprintf(stderr, "error: Corrupt symbol table\n");
+			return 1;			
+		}
+
+		if (symap_map(map, syms[i]) != id) {
+			fprintf(stderr, "error: Remapped symbol to a different ID\n");
+			return 1;
+		}
+		
+		symap_dump(map);
+	}
+
+	symap_free(map);
+	return 0;
+}
+
+#endif /* STANDALONE */
diff --git a/src/symap.h b/src/symap.h
new file mode 100644
index 0000000..15a271a
--- /dev/null
+++ b/src/symap.h
@@ -0,0 +1,70 @@
+/*
+  Copyright 2011 David Robillard <http://drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+/**
+   @file symap.h API for Symap, a basic symbol map (string interner).
+
+   Particularly useful and intended for implementation of the LV2 URI map and
+   URI unmap extensions.
+
+   @see <a href="http://lv2plug.in/ns/ext/uri-map/">LV2 URI Map</a>
+   @see <a href="http://lv2plug.in/ns/ext/uri-unmap/">LV2 URI Unmap</a>
+*/
+    
+#ifndef SYMAP_H
+#define SYMAP_H
+
+#include <stdint.h>
+
+struct SymapImpl;
+
+typedef struct SymapImpl Symap;
+
+/**
+   Create a new symbol map.
+*/
+Symap*
+symap_new();
+
+/**
+   Free a symbol map.
+*/
+void
+symap_free(Symap* map);
+
+/**
+   Map a string to a symbol ID if it is already mapped, otherwise return 0.
+*/
+uint32_t
+symap_try_map(Symap* map, const char* sym);
+
+/**
+   Map a string to a symbol ID.
+
+   Note that 0 is never a valid symbol ID.
+*/
+uint32_t
+symap_map(Symap* map, const char* sym);
+
+/**
+   Unmap a symbol ID back to a symbol, or NULL if no such ID exists.
+
+   Note that 0 is never a valid symbol ID.
+*/
+const char*
+symap_unmap(Symap* map, uint32_t id);
+
+#endif /* SYMAP_H */
diff --git a/wscript b/wscript
index e0a6fee..9240ed7 100644
--- a/wscript
+++ b/wscript
@@ -69,7 +69,7 @@ def build(bld):
 
     # Non-GUI version
     obj = bld(features     = 'c cprogram',
-              source       = 'src/jalv.c src/jalv_console.c',
+              source       = 'src/jalv.c src/symap.c src/jalv_console.c',
               target       = 'jalv',
               install_path = '${BINDIR}')
     autowaf.use_lib(bld, obj, libs)
@@ -77,7 +77,7 @@ def build(bld):
     # Gtk version
     if bld.is_defined('HAVE_GTK2'):
         obj = bld(features     = 'c cprogram',
-                  source       = 'src/jalv.c src/jalv_gtk2.c',
+                  source       = 'src/jalv.c src/symap.c src/jalv_gtk2.c',
                   target       = 'jalv.gtk',
                   install_path = '${BINDIR}')
         autowaf.use_lib(bld, obj, libs + ' GTK2')
@@ -85,7 +85,7 @@ def build(bld):
     # Qt version
     if bld.is_defined('HAVE_QT4'):
         obj = bld(features     = 'c cxx cxxprogram',
-                  source       = 'src/jalv.c src/jalv_qt4.cpp',
+                  source       = 'src/jalv.c src/symap.c src/jalv_qt4.cpp',
                   target       = 'jalv.qt',
                   install_path = '${BINDIR}')
         autowaf.use_lib(bld, obj, libs + ' QT4')