Hash-index event routing table

3 files changed, 109 insertions, 122 deletions

diff --git a/installer.sh b/installer.sh
index 56021c4..111c783 100755
--- a/installer.sh
+++ b/installer.sh
@@ -26,13 +26,13 @@ latest_version="$(curl --silent "https://api.github.com/repos/cbdevnet/midimonst
 # make invocation arguments
 makeargs="all"
 
-normal=$(tput sgr0)
-dim=$(tput dim)
-bold=$(tput bold)
-uline=$(tput smul)
-c_red=$(tput setaf 1)
-c_green=$(tput setaf 2)
-c_mag=$(tput setaf 5)
+normal="$(tput sgr0)"
+dim="$(tput dim)"
+bold="$(tput bold)"
+uline="$(tput smul)"
+c_red="$(tput setaf 1)"
+c_green="$(tput setaf 2)"
+c_mag="$(tput setaf 5)"
 
 DEFAULT_PREFIX="/usr"
 DEFAULT_PLUGINPATH="/lib/midimonster"
@@ -49,7 +49,7 @@ assign_defaults(){
 
 ARGS(){
 	for i in "$@"; do
-		case $i in
+		case "$i" in
 			--prefix=*)
 				VAR_PREFIX="${i#*=}"
 			;;
@@ -71,37 +71,28 @@ ARGS(){
 			-fu|--forceupdate)
 				UPDATER_FORCE="1"
 			;;
-			-supd|--selfupdate)
-				NIGHTLY=""
-				self_update
-				rmdir "$tmp_path"
+			--install-updater)
+				NIGHTLY=1 prepare_repo
+				install_script
 				exit 0
 			;;
-			-insup|--installupdater)
-				NIGHTLY=""
-				install_updater
-				rmdir "$tmp_path"
-				exit 0
-			;;
-			-insdep|--installdeps)
+			--install-dependencies)
 				install_dependencies
-				rmdir "$tmp_path"
 				exit 0
 			;;
 			-h|--help|*)
 				assign_defaults
 				printf "${bold}Usage:${normal} ${0} ${c_green}[OPTIONS]${normal}"
-				printf "\n\t${c_green} --prefix${normal} ${c_red}<path>${normal}\tSet the installation prefix\t\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_PREFIX"
-				printf "\n\t${c_green} --plugins${normal} ${c_red}<path>${normal}\tSet the plugin install path\t\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_PLUGINS"
-				printf "\n\t${c_green} --defcfg${normal} ${c_red}<path>${normal}\tSet the default configuration path\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_DEFAULT_CFG"
-				printf "\n\t${c_green} --examples${normal} ${c_red}<path>${normal}\tSet the path for example configurations\t${c_mag}Default:${normal} ${dim}%s${normal}\n" "$VAR_EXAMPLE_CFGS"
-				printf "\n\t${c_green}  --dev${normal}\t\t\tInstall nightly version"
-				printf "\n ${c_green}-d,\t  --default${normal}\t\tUse default values to install"
-				printf "\n ${c_green}-fu,\t  --forceupdate${normal}\t\tForce the updater to update without a version check"
-				printf "\n ${c_green}-supd,\t  --selfupdate${normal}\t\tUpdates this script to the newest version"
-				printf "\n ${c_green}-insup,  --installupdater${normal}\tInstall the updater (Run with midimonster-updater)"
-				printf "\n ${c_green}-insdep, --installdeps${normal}\t\tInstall dependencies and exit"
-				printf "\n ${c_green}-h,\t  --help${normal}\t\tShow this message and exit"
+				printf "\n\t${c_green}--prefix${normal} ${c_red}<path>${normal}\t\tSet the installation prefix\t\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_PREFIX"
+				printf "\n\t${c_green}--plugins${normal} ${c_red}<path>${normal}\tSet the plugin install path\t\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_PLUGINS"
+				printf "\n\t${c_green}--defcfg${normal} ${c_red}<path>${normal}\t\tSet the default configuration path\t${c_mag}Default:${normal} ${dim}%s${normal}" "$VAR_DEFAULT_CFG"
+				printf "\n\t${c_green}--examples${normal} ${c_red}<path>${normal}\tSet the path for example configurations\t${c_mag}Default:${normal} ${dim}%s${normal}\n" "$VAR_EXAMPLE_CFGS"
+				printf "\n\t${c_green}--dev${normal}\t\t\t\tInstall nightly version"
+				printf "\n\t${c_green}-d, --default${normal}\t\t\tUse default values to install"
+				printf "\n\t${c_green}-fu, --forceupdate${normal}\t\tForce the updater to update without a version check"
+				printf "\n\t${c_green}--install-updater${normal}\t\tInstall the updater (Run with midimonster-updater)"
+				printf "\n\t${c_green}--install-dependencies${normal}\t\tInstall dependencies and exit"
+				printf "\n\t${c_green}-h, --help${normal}\t\t\tShow this message and exit"
 				printf "\n\t${uline}${bold}${c_mag}Each argument can be overwritten by another, the last one is used!${normal}\n"
 				rmdir "$tmp_path"
 				exit 1
@@ -116,7 +107,7 @@ install_dependencies(){
 	for dependency in ${deps[@]}; do
 		if [ "$(dpkg-query -W -f='${Status}' "$dependency" 2>/dev/null | grep -c "ok installed")" -eq 0 ]; then
 			printf "Installing %s\n" "$dependency"
-			apt-get install $dependency
+			apt-get install "$dependency"
 		else
 			printf "%s already installed!\n" "$dependency"
 		fi
@@ -181,7 +172,7 @@ prepare_repo(){
 		printf "Finding latest stable version...\n"
 		last_tag=$(git describe --abbrev=0)
 		printf "Checking out %s...\n" "$last_tag"
-		git checkout -f -q $last_tag
+		git checkout -f -q "$last_tag"
 	fi
 }
 
@@ -207,30 +198,14 @@ save_config(){
 	printf "VAR_PREFIX=%s\nVAR_PLUGINS=%s\nVAR_DEFAULT_CFG=%s\nVAR_DESTDIR=%s\nVAR_EXAMPLE_CFGS=%s\n" "$VAR_PREFIX" "$VAR_PLUGINS" "$VAR_DEFAULT_CFG" "$VAR_DESTDIR" "$VAR_EXAMPLE_CFGS" > "$updater_dir/updater.conf"
 }
 
-# Updates this script either from the downloaded sources or the remote repository.
-self_update(){
+# Updates this script using the one from the checked out repo (containing the requested version)
+install_script(){
 	mkdir -p "$updater_dir"
-	if [ "$NIGHTLY" = "1" ]; then
-		cp -u "$tmp_path/installer.sh" "$0"
-	elif [ "$NIGHTLY" != "1" ]; then
-		wget https://raw.githubusercontent.com/cbdevnet/midimonster/master/installer.sh -O "$0"
-	fi
-	chmod +x "$0"
-}
-
-install_updater(){
-	mkdir -p "$updater_dir"
-	if [ "$NIGHTLY" = "1" ]; then
-		printf "Copying updater to %s/updater.sh\n" "$updater_dir"
-		cp -u "$tmp_path/installer.sh" "$updater_dir/updater.sh"
-	else
-		printf "Downloading updater to %s/updater.sh\n" "$updater_dir"
-		wget https://raw.githubusercontent.com/cbdevnet/midimonster/master/installer.sh -O "$updater_dir/updater.sh"
-	fi
+	printf "Copying updater to %s/updater.sh\n" "$updater_dir"
+	cp "$tmp_path/installer.sh" "$updater_dir/updater.sh"
 	chmod +x "$updater_dir/updater.sh"
 	printf "Creating symlink /usr/bin/midimonster-updater\n"
 	ln -s "$updater_dir/updater.sh" "/usr/bin/midimonster-updater"
-	printf "Done.\n"
 }
 
 error_handler(){
@@ -238,7 +213,7 @@ error_handler(){
 	exit 1
 }
 
-cleanup() {
+cleanup(){
 	if [ -d "$tmp_path" ]; then
 		printf "Cleaning up temporary files...\n"
 		rm -rf "$tmp_path"
@@ -288,7 +263,7 @@ if [ -f "$updater_dir/updater.conf" ] || [ "$UPDATER_FORCE" = "1" ]; then
 
 	# Run updater steps
 	prepare_repo
-	install_updater
+	install_script
 	save_config
 	build
 else
@@ -296,7 +271,7 @@ else
 	install_dependencies
 	prepare_repo
 	ask_questions
-	install_updater
+	install_script
 	save_config
 	build
 fi
diff --git a/midimonster.c b/midimonster.c
index 8e217e7..afb6a2b 100644
--- a/midimonster.c
+++ b/midimonster.c
@@ -29,25 +29,34 @@ typedef struct /*_mm_channel_mapping*/ {
 	channel** to;
 } channel_mapping;
 
-static size_t mappings = 0;
-static channel_mapping* map = NULL;
+static struct {
+	//routing_hash is set up for 256 buckets
+	size_t entries[256];
+	channel_mapping* map[256];
+
+	event_collection pool[2];
+	event_collection* events;
+} routing = {
+	.events = routing.pool
+};
+
 static size_t fds = 0;
 static managed_fd* fd = NULL;
 static volatile sig_atomic_t fd_set_dirty = 1;
 static uint64_t global_timestamp = 0;
 
-static event_collection event_pool[2] = {
-	{0},
-	{0}
-};
-static event_collection* primary = event_pool;
-
 volatile static sig_atomic_t shutdown_requested = 0;
 
 static void signal_handler(int signum){
 	shutdown_requested = 1;
 }
 
+static size_t routing_hash(channel* key){
+	uint64_t repr = (uint64_t) key;
+	//return 8bit hash for 256 buckets, not ideal but it works
+	return (repr ^ (repr >> 8) ^ (repr >> 16) ^ (repr >> 24) ^ (repr >> 32)) & 0xFF;
+}
+
 MM_API uint64_t mm_timestamp(){
 	return global_timestamp;
 }
@@ -67,53 +76,66 @@ static void update_timestamp(){
 }
 
 int mm_map_channel(channel* from, channel* to){
-	size_t u, m;
+	size_t u, m, bucket = routing_hash(from);
+
 	//find existing source mapping
-	for(u = 0; u < mappings; u++){
-		if(map[u].from == from){
+	for(u = 0; u < routing.entries[bucket]; u++){
+		if(routing.map[bucket][u].from == from){
 			break;
 		}
 	}
 
 	//create new entry
-	if(u == mappings){
-		map = realloc(map, (mappings + 1) * sizeof(channel_mapping));
-		if(!map){
+	if(u == routing.entries[bucket]){
+		routing.map[bucket] = realloc(routing.map[bucket], (routing.entries[bucket] + 1) * sizeof(channel_mapping));
+		if(!routing.map[bucket]){
+			routing.entries[bucket] = 0;
 			fprintf(stderr, "Failed to allocate memory\n");
 			return 1;
 		}
-		memset(map + mappings, 0, sizeof(channel_mapping));
-		mappings++;
-		map[u].from = from;
+
+		memset(routing.map[bucket] + routing.entries[bucket], 0, sizeof(channel_mapping));
+		routing.entries[bucket]++;
+		routing.map[bucket][u].from = from;
 	}
 
 	//check whether the target is already mapped
-	for(m = 0; m < map[u].destinations; m++){
-		if(map[u].to[m] == to){
+	for(m = 0; m < routing.map[bucket][u].destinations; m++){
+		if(routing.map[bucket][u].to[m] == to){
 			return 0;
 		}
 	}
 
-	map[u].to = realloc(map[u].to, (map[u].destinations + 1) * sizeof(channel*));
-	if(!map[u].to){
+	//add a mapping target
+	routing.map[bucket][u].to = realloc(routing.map[bucket][u].to, (routing.map[bucket][u].destinations + 1) * sizeof(channel*));
+	if(!routing.map[bucket][u].to){
 		fprintf(stderr, "Failed to allocate memory\n");
-		map[u].destinations = 0;
+		routing.map[bucket][u].destinations = 0;
 		return 1;
 	}
 
-	map[u].to[map[u].destinations] = to;
-	map[u].destinations++;
+	routing.map[bucket][u].to[routing.map[bucket][u].destinations] = to;
+	routing.map[bucket][u].destinations++;
 	return 0;
 }
 
-static void map_free(){
-	size_t u;
-	for(u = 0; u < mappings; u++){
-		free(map[u].to);
+static void routing_cleanup(){
+	size_t u, n;
+
+	for(u = 0; u < sizeof(routing.map) / sizeof(routing.map[0]); u++){
+		for(n = 0; n < routing.entries[u]; n++){
+			free(routing.map[u][n].to);
+		}
+		free(routing.map[u]);
+		routing.map[u] = NULL;
+		routing.entries[u] = 0;
+	}
+
+	for(u = 0; u < sizeof(routing.pool) / sizeof(routing.pool[0]); u++){
+		free(routing.pool[u].channel);
+		free(routing.pool[u].value);
+		routing.pool[u].alloc = 0;
 	}
-	free(map);
-	mappings = 0;
-	map = NULL;
 }
 
 MM_API int mm_manage_fd(int new_fd, char* back, int manage, void* impl){
@@ -170,7 +192,6 @@ MM_API int mm_manage_fd(int new_fd, char* back, int manage, void* impl){
 static void fds_free(){
 	size_t u;
 	for(u = 0; u < fds; u++){
-		//TODO free impl
 		if(fd[u].fd >= 0){
 			close(fd[u].fd);
 			fd[u].fd = -1;
@@ -182,56 +203,46 @@ static void fds_free(){
 }
 
 MM_API int mm_channel_event(channel* c, channel_value v){
-	size_t u, p;
+	size_t u, p, bucket = routing_hash(c);
 
 	//find mapped channels
-	for(u = 0; u < mappings; u++){
-		if(map[u].from == c){
+	for(u = 0; u < routing.entries[bucket]; u++){
+		if(routing.map[bucket][u].from == c){
 			break;
 		}
 	}
 
-	if(u == mappings){
+	if(u == routing.entries[bucket]){
 		//target-only channel
 		return 0;
 	}
 
 	//resize event structures to fit additional events
-	if(primary->n + map[u].destinations >= primary->alloc){
-		primary->channel = realloc(primary->channel, (primary->alloc + map[u].destinations) * sizeof(channel*));
-		primary->value = realloc(primary->value, (primary->alloc + map[u].destinations) * sizeof(channel_value));
+	if(routing.events->n + routing.map[bucket][u].destinations >= routing.events->alloc){
+		routing.events->channel = realloc(routing.events->channel, (routing.events->alloc + routing.map[bucket][u].destinations) * sizeof(channel*));
+		routing.events->value = realloc(routing.events->value, (routing.events->alloc + routing.map[bucket][u].destinations) * sizeof(channel_value));
 
-		if(!primary->channel || !primary->value){
+		if(!routing.events->channel || !routing.events->value){
 			fprintf(stderr, "Failed to allocate memory\n");
-			primary->alloc = 0;
-			primary->n = 0;
+			routing.events->alloc = 0;
+			routing.events->n = 0;
 			return 1;
 		}
 
-		primary->alloc += map[u].destinations;
+		routing.events->alloc += routing.map[bucket][u].destinations;
 	}
 
 	//enqueue channel events
 	//FIXME this might lead to one channel being mentioned multiple times in an apply call
-	for(p = 0; p < map[u].destinations; p++){
-		primary->channel[primary->n + p] = map[u].to[p];
-		primary->value[primary->n + p] = v;
+	memcpy(routing.events->channel + routing.events->n, routing.map[bucket][u].to, routing.map[bucket][u].destinations * sizeof(channel*));
+	for(p = 0; p < routing.map[bucket][u].destinations; p++){
+		routing.events->value[routing.events->n + p] = v;
 	}
 
-	primary->n += map[u].destinations;
+	routing.events->n += routing.map[bucket][u].destinations;
 	return 0;
 }
 
-static void event_free(){
-	size_t u;
-
-	for(u = 0; u < sizeof(event_pool) / sizeof(event_collection); u++){
-		free(event_pool[u].channel);
-		free(event_pool[u].value);
-		event_pool[u].alloc = 0;
-	}
-}
-
 static void version(){
 	printf("MIDIMonster %s\n", MIDIMONSTER_VERSION);
 }
@@ -336,13 +347,13 @@ static int core_process(size_t nfds, managed_fd* signaled_fds){
 		return 1;
 	}
 
-	while(primary->n){
+	while(routing.events->n){
 		//swap primary and secondary event collectors
-		DBGPF("Swapping event collectors, %lu events in primary\n", primary->n);
-		for(u = 0; u < sizeof(event_pool) / sizeof(event_collection); u++){
-			if(primary != event_pool + u){
-				secondary = primary;
-				primary = event_pool + u;
+		DBGPF("Swapping event collectors, %lu events in primary\n", routing.events->n);
+		for(u = 0; u < sizeof(routing.pool) / sizeof(routing.pool[0]); u++){
+			if(routing.events != routing.pool + u){
+				secondary = routing.events;
+				routing.events = routing.pool + u;
 				break;
 			}
 		}
@@ -466,7 +477,7 @@ int main(int argc, char** argv){
 	if(config_read(cfg_file)){
 		fprintf(stderr, "Failed to read configuration file %s\n", cfg_file);
 		backends_stop();
-		map_free();
+		routing_cleanup();
 		fds_free();
 		plugins_close();
 		config_free();
@@ -495,9 +506,8 @@ int main(int argc, char** argv){
 bail:
 	//free all data
 	backends_stop();
-	map_free();
+	routing_cleanup();
 	fds_free();
-	event_free();
 	plugins_close();
 	config_free();
 	platform_shutdown();
diff --git a/midimonster.h b/midimonster.h
index dc0e255..61467c1 100644
--- a/midimonster.h
+++ b/midimonster.h
@@ -247,6 +247,8 @@ 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.
  */
 MM_API int mm_manage_fd(int fd, char* backend, int manage, void* impl);