From 3e6c580c197929c126613fcfc546308abdc18c09 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sun, 19 Jun 2011 21:16:32 +0000 Subject: Add a real URI map implementation. git-svn-id: http://svn.drobilla.net/lad/trunk/jalv@3406 a436a847-0d15-0410-975c-d299462d15a1 --- src/jalv.c | 22 +++-- src/jalv_internal.h | 6 +- src/symap.c | 229 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/symap.h | 70 ++++++++++++++++ 4 files changed, 318 insertions(+), 9 deletions(-) create mode 100644 src/symap.c create mode 100644 src/symap.h (limited to 'src') 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 + + 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 +#include +#include +#include + +#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 + +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 + + 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 LV2 URI Map + @see LV2 URI Unmap +*/ + +#ifndef SYMAP_H +#define SYMAP_H + +#include + +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 */ -- cgit v1.2.1