Refactor global channel store

2 files changed, 74 insertions, 61 deletions

diff --git a/backend.c b/backend.c
index 9e7989e..003980f 100644
--- a/backend.c
+++ b/backend.c
@@ -16,9 +16,21 @@ static struct {
 	.n = 0
 };
 
-//TODO move channel store into registry
-static size_t nchannels = 0;
-static channel** channels = NULL;
+//the global channel store was converted from a naive list to a hashmap of lists for performance reasons
+static struct {
+	//channelstore hash is set up for 256 buckets
+	size_t n[256];
+	channel** entry[256];
+} channels = {
+	.n = {
+		0
+	}
+};
+
+static size_t channelstore_hash(instance* inst, uint64_t ident){
+	uint64_t repr = ((uint64_t) inst) ^ ident;
+	return (repr ^ (repr >> 8) ^ (repr >> 16) ^ (repr >> 24) ^ (repr >> 32)) & 0xFF;
+}
 
 int backends_handle(size_t nfds, managed_fd* fds){
 	size_t u, p, n;
@@ -81,11 +93,12 @@ int backends_notify(size_t nev, channel** c, channel_value* v){
 }
 
 MM_API channel* mm_channel(instance* inst, uint64_t ident, uint8_t create){
-	size_t u;
-	for(u = 0; u < nchannels; u++){
-		if(channels[u]->instance == inst && channels[u]->ident == ident){
-			DBGPF("Requested channel %" PRIu64 " on instance %s already exists, reusing\n", ident, inst->name);
-			return channels[u];
+	size_t u, bucket = channelstore_hash(inst, ident);
+	for(u = 0; u < channels.n[bucket]; u++){
+		if(channels.entry[bucket][u]->instance == inst
+				&& channels.entry[bucket][u]->ident == ident){
+			DBGPF("Requested channel %" PRIu64 " on instance %s already exists, reusing (%" PRIsize_t " search steps)\n", ident, inst->name, u);
+			return channels.entry[bucket][u];
 		}
 	}
 
@@ -94,24 +107,23 @@ MM_API channel* mm_channel(instance* inst, uint64_t ident, uint8_t create){
 		return NULL;
 	}
 
-	DBGPF("Creating previously unknown channel %" PRIu64 " on instance %s\n", ident, inst->name);
-	channel** new_chan = realloc(channels, (nchannels + 1) * sizeof(channel*));
-	if(!new_chan){
+	DBGPF("Creating previously unknown channel %" PRIu64 " on instance %s, bucket %" PRIsize_t "\n", ident, inst->name, bucket);
+	channels.entry[bucket] = realloc(channels.entry[bucket], (channels.n[bucket] + 1) * sizeof(channel*));
+	if(!channels.entry[bucket]){
 		fprintf(stderr, "Failed to allocate memory\n");
-		nchannels = 0;
+		channels.n[bucket] = 0;
 		return NULL;
 	}
 
-	channels = new_chan;
-	channels[nchannels] = calloc(1, sizeof(channel));
-	if(!channels[nchannels]){
+	channels.entry[bucket][channels.n[bucket]] = calloc(1, sizeof(channel));
+	if(!channels.entry[bucket][channels.n[bucket]]){
 		fprintf(stderr, "Failed to allocate memory\n");
 		return NULL;
 	}
 
-	channels[nchannels]->instance = inst;
-	channels[nchannels]->ident = ident;
-	return channels[nchannels++];
+	channels.entry[bucket][channels.n[bucket]]->instance = inst;
+	channels.entry[bucket][channels.n[bucket]]->ident = ident;
+	return channels.entry[bucket][(channels.n[bucket]++)];
 }
 
 instance* mm_instance(backend* b){
@@ -191,21 +203,6 @@ MM_API int mm_backend_instances(char* name, size_t* ninst, instance*** inst){
 	return 1;
 }
 
-void channels_free(){
-	size_t u;
-	for(u = 0; u < nchannels; u++){
-		DBGPF("Destroying channel %" PRIu64 " on instance %s\n", channels[u]->ident, channels[u]->instance->name);
-		if(channels[u]->impl && channels[u]->instance->backend->channel_free){
-			channels[u]->instance->backend->channel_free(channels[u]);
-		}
-		free(channels[u]);
-		channels[u] = NULL;
-	}
-	free(channels);
-	nchannels = 0;
-}
-
-
 backend* backend_match(char* name){
 	size_t u;
 	for(u = 0; u < registry.n; u++){
@@ -306,6 +303,24 @@ int backends_start(){
 	return rv;
 }
 
+static void channels_free(){
+	size_t u, p;
+	for(u = 0; u < sizeof(channels.n) / sizeof(channels.n[0]); u++){
+		DBGPF("Cleaning up channel registry bucket %" PRIsize_t " with %" PRIsize_t " channels", u, channels.n[u]);
+		for(p = 0; p < channels.n[u]; p++){
+			DBGPF("Destroying channel %" PRIu64 " on instance %s\n", channels.entry[u][p]->ident, channels.entry[u][p]->instance->name);
+			//call the channel_free function if the backend supports it
+			if(channels.entry[u][p]->impl && channels.entry[u][p]->instance->backend->channel_free){
+				channels.entry[u][p]->instance->backend->channel_free(channels.entry[u][p]);
+			}
+			free(channels.entry[u][p]);
+		}
+		free(channels.entry[u]);
+		channels.entry[u] = NULL;
+		channels.n[u] = 0;
+	}
+}
+
 int backends_stop(){
 	size_t u, n;
 	instance** inst = NULL;
diff --git a/midimonster.h b/midimonster.h
index 61467c1..75eb30a 100644
--- a/midimonster.h
+++ b/midimonster.h
@@ -192,8 +192,8 @@ typedef struct _backend_instance {
 
 /* 
  * Instance channel structure
- * Backends may either manage their own channel registry
- * or use the memory returned by mm_channel()
+ * Backends may either manage their own channel registry or use the global
+ * channel store via the mm_channel() API
  */
 typedef struct _backend_channel {
 	instance* instance;
@@ -218,25 +218,24 @@ MM_API int mm_backend_register(backend b);
 
 /*
  * Finds an instance matching the specified backend and identifier.
- * Since setting an identifier for an instance is optional,
- * this may not work depending on the backend.
- * Instance identifiers may for example be set in the backends
- * mmbackend_start call.
+ * Since setting an identifier for an instance is optional, this may not work
+ * depending on the backend. Instance identifiers may for example be set in the
+ * backends mmbackend_start call.
  */
 MM_API instance* mm_instance_find(char* backend, uint64_t ident);
 
 /*
- * Provides a pointer to a channel structure, pre-filled with
- * the provided instance reference and identifier.
- * The `create` parameter is a boolean flag indicating whether
- * a channel matching the `ident` parameter should be created if
- * none exists. If the instance already registered a channel
- * matching `ident`, a pointer to it is returned.
- * This API is just a convenience function. The array of channels is
- * only used for mapping internally, creating and managing your own
- * channel store is possible. When returning pointers from a
- * backend-local channel store, the returned pointers must stay
- * valid over the lifetime of the instance.
+ * Provides a pointer to a channel structure, pre-filled with the provided
+ * instance reference and identifier.
+ * The `create` parameter is a boolean flag indicating whether a channel
+ * matching the `ident` parameter should be created in the global channel store
+ * if none exists yet. If the instance already registered a channel matching
+ * `ident`, a pointer to the existing channel is returned.
+ * This API is just a convenience function. Creating and managing a
+ * backend-internal channel store is possible (and encouraged for performance
+ * reasons). When returning pointers from a backend-local channel store, the
+ * returned pointers must stay valid over the lifetime of the instance and
+ * provide valid `instance` members, as they are used for callbacks.
  * For each channel with a non-NULL `impl` field registered using
  * this function, the backend will receive a call to its channel_free
  * function (if it exists).
@@ -244,17 +243,16 @@ MM_API instance* mm_instance_find(char* backend, uint64_t ident);
 MM_API channel* mm_channel(instance* i, uint64_t ident, uint8_t create);
 
 /*
- * Register (manage = 1) or unregister (manage = 0) a file descriptor
- * to be selected on. The backend will be notified when the descriptor
- * becomes ready to read via its registered mmbackend_process_fd call.
- * The `impl` argument will be provided within the corresponding
- * managed_fd structure upon callback.
+ * Register (manage = 1) or unregister (manage = 0) a file descriptor to be
+ * selected on. The backend will be notified when the descriptor becomes ready
+ * to read via its registered mmbackend_process_fd call. The `impl` argument
+ * will be provided within the corresponding managed_fd structure upon callback.
  */
 MM_API int mm_manage_fd(int fd, char* backend, int manage, void* impl);
 
 /*
- * Notifies the core of a channel event. Called by backends to
- * inject events gathered from their backing implementation.
+ * Notifies the core of a channel event. Called by backends to inject events
+ * gathered from their backing implementation.
  */
 MM_API int mm_channel_event(channel* c, channel_value v);
 
@@ -266,14 +264,14 @@ MM_API int mm_backend_instances(char* backend, size_t* n, instance*** i);
 
 /*
  * Query an internal timestamp, which is updated every core iteration.
- * This timestamp should not be used as a performance counter, but can be
- * used for timeouting. Resolution is milliseconds.
+ * This timestamp should not be used as a performance counter, but can be used
+ * for timeouting. Resolution is milliseconds.
  */
 MM_API uint64_t mm_timestamp();
 
 /*
- * Create a channel-to-channel mapping. This API should not
- * be used by backends. It is only exported for core modules.
+ * Create a channel-to-channel mapping. This API should not be used by backends.
+ * It is only exported for core modules.
  */
 int mm_map_channel(channel* from, channel* to);
 #endif