hub/manager: List the hubs in a set-like vector

This has the advantage that the hub id does no longer relate to how
things are organized in-memory. Which, in turn, allows the id to be
fairly large and/or more dynamic without affecting performance.

Since the hub list is now efficiently packed regardless of id gaps, this
should improve iteration performance a bit. And that's the operation
that matters most, since it's what hub_manager_infchange() does.

1 files changed, 63 insertions, 36 deletions

diff --git a/src/hub/manager.c b/src/hub/manager.c
index 7f4ff02..7de02e0 100644
--- a/src/hub/manager.c
+++ b/src/hub/manager.c
@@ -30,16 +30,57 @@
 typedef struct {
 	dbo_t dbo;
 	dbo_hubm_properties_t props;
-	/* TODO: In the future, hub IDs should be stable between runs, so this
-	 * should probably be a hash table. */
-	kvec_t(hub_t *) hubs;
+	/* This list forms an unordered set of hub pointers. Incides [0..hubnum-1]
+	 * contain valid pointers, [hubnum..hublen-1] are empty slots. */
+	int hubnum, hublen;
+	hub_t **hubs;
 } obj_t;
 
 static obj_t manager;
 
 
+
+
+static hub_t *hub_find(int id) {
+	int i;
+	for(i=0; i<manager.hubnum; i++)
+		if(manager.hubs[i]->id == id)
+			return manager.hubs[i];
+	return NULL;
+}
+
+
+static void hub_insert(hub_t *h) {
+	if(manager.hubnum == manager.hublen) {
+		manager.hublen = manager.hublen < 8 ? 8 : manager.hublen * 2;
+		manager.hubs = realloc(manager.hubs, manager.hublen*sizeof(hub_t *));
+	}
+	manager.hubs[manager.hubnum++] = h;
+}
+
+
+static void hub_remove(int id) {
+	int i;
+	for(i=0; i<manager.hubnum; i++)
+		if(manager.hubs[i]->id == id)
+			break;
+	manager.hubs[i] = manager.hubs[--manager.hubnum];
+}
+
+
+static int hub_newid() {
+	int i, id = 1;
+	for(i=0; i<manager.hubnum; i++)
+		if(manager.hubs[i]->id >= id)
+			id = manager.hubs[i]->id+1;
+	return id;
+}
+
+
+
+
 /* Create a hub object and register it with dbo */
-static hub_t *hub_create(int id) {
+static void hub_create(int id) {
 	char path[50];
 	assert(snprintf(path, sizeof(path), HUB_BASE_PATH"/%d", id) < (int)sizeof(path));
 	yinfo("Creating hub object: %d", id);
@@ -53,12 +94,14 @@ static hub_t *hub_create(int id) {
 	hub_hub_init(h);
 	hub_users_init(h);
 	hub_chat_init(h);
-	return h;
+
+	hub_insert(h);
 }
 
 
 static void hub_destroy(hub_t *h) {
 	yinfo("Destroying hub object: %d", h->id);
+	hub_remove(h->id);
 	hub_conn_destroy(h);
 	hub_hub_destroy(h);
 	hub_chat_destroy(h); /* chat before users, otherwise the _unref()s will fail */
@@ -69,29 +112,19 @@ static void hub_destroy(hub_t *h) {
 
 
 static void Create(obj_t *o, DBusMessage *msg) {
-	int id;
-	for(id=1; id < (int)kv_size(o->hubs); id++) {
-		if(!kv_A(o->hubs, id))
-			break;
-	}
-
-	hub_t *hub = hub_create(id);
-	if(id < (int)kv_size(o->hubs))
-		kv_A(o->hubs, id) = hub;
-	else
-		kv_push(hub_t *, o->hubs, hub);
-
+	int id = hub_newid();
+	hub_create(id);
 	dbo_hubm_Create_reply(msg, id);
 	dbo_hubm_Created_signal(o, id);
 }
 
 
 static void Delete(obj_t *o, DBusMessage *msg, uint32_t id) {
-	if(id < 1 || id >= kv_size(o->hubs) || !kv_A(o->hubs, id))
+	hub_t *h = hub_find(id);
+	if(!h)
 		dbo_sendfree(dbus_message_new_error_printf(msg, DBUS_ERROR_INVALID_ARGS, "Invalid hub identifier"));
 	else {
-		hub_destroy(kv_A(o->hubs, id));
-		kv_A(o->hubs, id) = NULL;
+		hub_destroy(h);
 		dbo_hubm_Delete_reply(msg);
 		dbo_hubm_Deleted_signal(o, id);
 	}
@@ -99,14 +132,15 @@ static void Delete(obj_t *o, DBusMessage *msg, uint32_t id) {
 
 
 static void List(obj_t *o, DBusMessage *msg) {
-	uint32_t i;
 	DBusMessageIter iter, sub;
 	DBusMessage *r = dbus_message_new_method_return(msg);
 	dbus_message_iter_init_append(r, &iter);
 	dbus_message_iter_open_container(&iter, 'a', "u", &sub);
-	for(i=1; i<kv_size(o->hubs); i++)
-		if(kv_A(o->hubs, i))
-			dbus_message_iter_append_basic(&sub, 'u', &i);
+	int i;
+	for(i=0; i<o->hubnum; i++) {
+		uint32_t n = o->hubs[i]->id;
+		dbus_message_iter_append_basic(&sub, 'u', &n);
+	}
 	dbus_message_iter_close_container(&iter, &sub);
 	dbo_sendfree(r);
 }
@@ -115,11 +149,8 @@ static void List(obj_t *o, DBusMessage *msg) {
 static void hub_manager_infchange(EV_P_ ev_idle *w, int revents) {
 	ev_idle_stop(EV_A_ w);
 	int i;
-	for(i=1; i<(int)kv_size(manager.hubs); i++) {
-		hub_t *h = kv_A(manager.hubs, i);
-		if(h)
-			hub_hub_infchange(h, false);
-	}
+	for(i=0; i<manager.hubnum; i++)
+		hub_hub_infchange(manager.hubs[i], false);
 }
 
 
@@ -168,9 +199,7 @@ void hub_manager_create() {
 	static dbo_hubm_vtable_t(obj_t) vt = dbo_hubm_funcs();
 
 	manager.props.NormalHubs = manager.props.RegHubs = manager.props.OpHubs = 0;
-	kv_init(manager.hubs);
 
-	kv_push(hub_t *, manager.hubs, NULL);
 	dbo_register(&manager.dbo, MANAGER_PATH);
 	dbo_add_itf(&manager.dbo, dbo_hubm_interface, &vt, &manager.props);
 }
@@ -179,11 +208,9 @@ void hub_manager_create() {
 void hub_manager_shutdown() {
 	/* Force disconnect all hubs. It'd be "cleaner" to do a graceful
 	 * disconnect, but we shouldn't take too long to shut down... */
-	size_t i;
-	for(i=1; i<kv_size(manager.hubs); i++) {
-		hub_t *h = kv_A(manager.hubs, i);
-		if(!h)
-			continue;
+	int i;
+	for(i=0; i<manager.hubnum; i++) {
+		hub_t *h = manager.hubs[i];
 		hub_conn_disconnect(h, HUBCD_FORCE, "net.blicky.Globster.Disconnected", "Shutting down");
 		hub_users_shutdown(h);
 	}