Store objects in wl_map data structure

The wl_map data structure is just an array with a free-list that lets the
client recycle unused client IDs and keep range of client IDs under control.

8 files changed, 160 insertions, 66 deletions

diff --git a/src/connection.c b/src/connection.c
index 6dfb0b9..e683905 100644
--- a/src/connection.c
+++ b/src/connection.c
@@ -495,7 +495,7 @@ wl_connection_vmarshal(struct wl_connection *connection,
 struct wl_closure *
 wl_connection_demarshal(struct wl_connection *connection,
 			uint32_t size,
-			struct wl_hash_table *objects,
+			struct wl_map *objects,
 			const struct wl_message *message)
 {
 	uint32_t *p, *next, *end, length;
@@ -586,7 +586,7 @@ wl_connection_demarshal(struct wl_connection *connection,
 			extra += sizeof *object;
 			closure->args[i] = object;
 
-			*object = wl_hash_table_lookup(objects, *p);
+			*object = wl_map_lookup(objects, *p);
 			if (*object == NULL && *p != 0) {
 				printf("unknown object (%d), message %s(%s)\n",
 				       *p, message->name, message->signature);
@@ -599,7 +599,7 @@ wl_connection_demarshal(struct wl_connection *connection,
 		case 'n':
 			closure->types[i] = &ffi_type_uint32;
 			closure->args[i] = p;
-			object = wl_hash_table_lookup(objects, *p);
+			object = wl_map_lookup(objects, *p);
 			if (*p == 0 || object != NULL) {
 				printf("not a new object (%d), "
 				       "message %s(%s)\n",
diff --git a/src/connection.h b/src/connection.h
index 5f4588b..1c733ff 100644
--- a/src/connection.h
+++ b/src/connection.h
@@ -53,7 +53,7 @@ wl_connection_vmarshal(struct wl_connection *connection,
 struct wl_closure *
 wl_connection_demarshal(struct wl_connection *connection,
 			uint32_t size,
-			struct wl_hash_table *objects,
+			struct wl_map *objects,
 			const struct wl_message *message);
 void
 wl_closure_invoke(struct wl_closure *closure,
diff --git a/src/wayland-client.c b/src/wayland-client.c
index 4850c9b..ed21f04 100644
--- a/src/wayland-client.c
+++ b/src/wayland-client.c
@@ -62,9 +62,8 @@ struct wl_display {
 	struct wl_proxy proxy;
 	struct wl_connection *connection;
 	int fd;
-	uint32_t id;
 	uint32_t mask;
-	struct wl_hash_table *objects;
+	struct wl_map objects;
 	struct wl_list global_listener_list;
 	struct wl_list global_list;
 
@@ -133,9 +132,8 @@ wl_proxy_create(struct wl_proxy *factory, const struct wl_interface *interface)
 
 	proxy->object.interface = interface;
 	proxy->object.implementation = NULL;
-	proxy->object.id = wl_display_allocate_id(display);
+	proxy->object.id = wl_map_insert_new(&display->objects, proxy);
 	proxy->display = display;
-	wl_hash_table_insert(display->objects, proxy->object.id, proxy);
 
 	return proxy;
 }
@@ -143,7 +141,7 @@ wl_proxy_create(struct wl_proxy *factory, const struct wl_interface *interface)
 WL_EXPORT void
 wl_proxy_destroy(struct wl_proxy *proxy)
 {
-	wl_hash_table_remove(proxy->display->objects, proxy->object.id);
+	wl_map_remove(&proxy->display->objects, proxy->object.id);
 	free(proxy);
 }
 
@@ -216,10 +214,6 @@ display_handle_global(void *data,
 	struct wl_global_listener *listener;
 	struct wl_global *global;
 
-	if (strcmp(interface, "wl_display") == 0)
-		wl_hash_table_insert(display->objects,
-				     id, &display->proxy.object);
-
 	global = malloc(sizeof *global);
 	global->id = id;
 	global->interface = strdup(interface);
@@ -324,29 +318,22 @@ wl_display_connect(const char *name)
 		return NULL;
 	}
 
-	display->objects = wl_hash_table_create();
-	if (display->objects == NULL) {
-		close(display->fd);
-		free(display);
-		return NULL;
-	}
+	wl_map_init(&display->objects);
 	wl_list_init(&display->global_listener_list);
 	wl_list_init(&display->global_list);
 
-	display->id = 1;
+	wl_map_insert_new(&display->objects, NULL);
+
 	display->proxy.object.interface = &wl_display_interface;
-	display->proxy.object.id = display->id++;
+	display->proxy.object.id = wl_map_insert_new(&display->objects, display);
 	display->proxy.display = display;
-
-	display->proxy.object.implementation =
-		(void(**)(void)) &display_listener;
+	display->proxy.object.implementation = (void(**)(void)) &display_listener;
 	display->proxy.user_data = display;
 
 	display->connection = wl_connection_create(display->fd,
-						   connection_update,
-						   display);
+						   connection_update, display);
 	if (display->connection == NULL) {
-		wl_hash_table_destroy(display->objects);
+		wl_map_release(&display->objects);
 		close(display->fd);
 		free(display);
 		return NULL;
@@ -362,7 +349,7 @@ wl_display_destroy(struct wl_display *display)
 	struct wl_global_listener *listener, *lnext;
 
 	wl_connection_destroy(display->connection);
-	wl_hash_table_destroy(display->objects);
+	wl_map_release(&display->objects);
 	wl_list_for_each_safe(global, gnext,
 			      &display->global_list, link)
 		free(global);
@@ -426,7 +413,7 @@ handle_event(struct wl_display *display,
 	if (id == 1)
 		proxy = &display->proxy;
 	else
-		proxy = wl_hash_table_lookup(display->objects, id);
+		proxy = wl_map_lookup(&display->objects, id);
 
 	if (proxy == NULL || proxy->object.implementation == NULL) {
 		wl_connection_consume(display->connection, size);
@@ -435,7 +422,7 @@ handle_event(struct wl_display *display,
 
 	message = &proxy->object.interface->events[opcode];
 	closure = wl_connection_demarshal(display->connection,
-					  size, display->objects, message);
+					  size, &display->objects, message);
 
 	if (closure == NULL) {
 		fprintf(stderr, "Error demarshalling event: %m\n");
@@ -494,12 +481,6 @@ wl_display_flush(struct wl_display *display)
 		wl_display_iterate (display, WL_DISPLAY_WRITABLE);
 }
 
-WL_EXPORT uint32_t
-wl_display_allocate_id(struct wl_display *display)
-{
-	return display->id++;
-}
-
 WL_EXPORT void *
 wl_display_bind(struct wl_display *display,
 		uint32_t name, const struct wl_interface *interface)
diff --git a/src/wayland-client.h b/src/wayland-client.h
index 53b323d..3a66c42 100644
--- a/src/wayland-client.h
+++ b/src/wayland-client.h
@@ -61,7 +61,6 @@ struct wl_display *wl_display_connect(const char *name);
 void wl_display_destroy(struct wl_display *display);
 int wl_display_get_fd(struct wl_display *display,
 		      wl_display_update_func_t update, void *data);
-uint32_t wl_display_allocate_id(struct wl_display *display);
 void wl_display_iterate(struct wl_display *display, uint32_t mask);
 void wl_display_flush(struct wl_display *display);
 void wl_display_roundtrip(struct wl_display *display);
diff --git a/src/wayland-hash.c b/src/wayland-hash.c
index e1c0b6a..1ec6be4 100644
--- a/src/wayland-hash.c
+++ b/src/wayland-hash.c
@@ -188,7 +188,7 @@ hash_table_search(struct wl_hash_table *ht, uint32_t hash)
 
 WL_EXPORT void
 wl_hash_table_for_each(struct wl_hash_table *ht,
-		       wl_hash_table_func_t func, void *data)
+		       wl_iterator_func_t func, void *data)
 {
 	struct hash_entry *entry;
 	uint32_t i;
diff --git a/src/wayland-server.c b/src/wayland-server.c
index a0d365e..61317fe 100644
--- a/src/wayland-server.c
+++ b/src/wayland-server.c
@@ -61,7 +61,7 @@ struct wl_client {
 	uint32_t id_count;
 	uint32_t mask;
 	struct wl_list link;
-	struct wl_hash_table *objects;
+	struct wl_map objects;
 };
 
 struct wl_display {
@@ -154,10 +154,9 @@ wl_client_connection_data(int fd, uint32_t mask, void *data)
 		if (len < size)
 			break;
 
-		resource = wl_hash_table_lookup(client->objects, p[0]);
+		resource = wl_map_lookup(&client->objects, p[0]);
 		if (resource == NULL) {
-			wl_client_post_error(client,
-					     &client->display->resource.object,
+			wl_client_post_error(client, &resource->object,
 					     WL_DISPLAY_ERROR_INVALID_OBJECT,
 					     "invalid object %d", p[0]);
 			wl_connection_consume(connection, size);
@@ -167,8 +166,7 @@ wl_client_connection_data(int fd, uint32_t mask, void *data)
 
 		object = &resource->object;
 		if (opcode >= object->interface->method_count) {
-			wl_client_post_error(client,
-					     &client->display->resource.object,
+			wl_client_post_error(client, &resource->object,
 					     WL_DISPLAY_ERROR_INVALID_METHOD,
 					     "invalid method %d, object %s@%d",
 					     object->interface->name,
@@ -180,12 +178,11 @@ wl_client_connection_data(int fd, uint32_t mask, void *data)
 
 		message = &object->interface->methods[opcode];
 		closure = wl_connection_demarshal(client->connection, size,
-						  client->objects, message);
+						  &client->objects, message);
 		len -= size;
 
 		if (closure == NULL && errno == EINVAL) {
-			wl_client_post_error(client,
-					     &client->display->resource.object,
+			wl_client_post_error(client, &resource->object,
 					     WL_DISPLAY_ERROR_INVALID_METHOD,
 					     "invalid arguments for %s@%d.%s",
 					     object->interface->name,
@@ -264,9 +261,10 @@ wl_client_create(struct wl_display *display, int fd)
 		return NULL;
 	}
 
-	client->objects = wl_hash_table_create();
-	if (client->objects == NULL) {
-		wl_connection_destroy(client->connection);
+	wl_map_init(&client->objects);
+
+	if (wl_map_insert_at(&client->objects, 0, NULL) < 0) {
+		wl_map_release(&client->objects);
 		free(client);
 		return NULL;
 	}
@@ -284,13 +282,13 @@ wl_client_add_resource(struct wl_client *client,
 {
 	resource->client = client;
 	wl_list_init(&resource->destroy_listener_list);
-	wl_hash_table_insert(client->objects, resource->object.id, resource);
+	wl_map_insert_at(&client->objects, resource->object.id, resource);
 }
 
 WL_EXPORT void
 wl_client_post_no_memory(struct wl_client *client)
 {
-	wl_client_post_error(client, &client->display->resource.object,
+	wl_client_post_error(client, &client->display_resource->object,
 			     WL_DISPLAY_ERROR_NO_MEMORY, "no memory");
 }
 
@@ -314,18 +312,18 @@ wl_resource_destroy(struct wl_resource *resource, uint32_t time)
 	struct wl_client *client = resource->client;
 
 	destroy_resource(resource, &time);
-	wl_hash_table_remove(client->objects, resource->object.id);
+	wl_map_insert_at(&client->objects, resource->object.id, NULL);
 }
 
 WL_EXPORT void
 wl_client_destroy(struct wl_client *client)
 {
 	uint32_t time = 0;
-
+	
 	printf("disconnect from client %p\n", client);
 
-	wl_hash_table_for_each(client->objects, destroy_resource, &time);
-	wl_hash_table_destroy(client->objects);
+	wl_map_for_each(&client->objects, destroy_resource, &time);
+	wl_map_release(&client->objects);
 	wl_event_source_remove(client->source);
 	wl_connection_destroy(client->connection);
 	wl_list_remove(&client->link);
@@ -525,7 +523,7 @@ display_bind(struct wl_client *client,
 			break;
 
 	if (&global->link == &display->global_list)
-		wl_client_post_error(client, &client->display->resource.object,
+		wl_client_post_error(client, &resource->object,
 				     WL_DISPLAY_ERROR_INVALID_OBJECT,
 				     "invalid global %d", name);
 	else
@@ -536,13 +534,12 @@ static void
 display_sync(struct wl_client *client,
 	     struct wl_resource *resource, uint32_t id)
 {
-	struct wl_resource callback;
-
-	callback.object.interface = &wl_callback_interface;
-	callback.object.id = id;
-	callback.client = client;
+	struct wl_resource *callback;
 
-	wl_resource_post_event(&callback, WL_CALLBACK_DONE, 0);
+	callback = wl_client_add_object(client,
+					&wl_callback_interface, NULL, id, NULL);
+	wl_resource_post_event(callback, WL_CALLBACK_DONE, 0);
+	wl_resource_destroy(callback, 0);
 }
 
 struct wl_display_interface display_interface = {
@@ -838,7 +835,11 @@ wl_client_add_object(struct wl_client *client,
 	resource->destroy = (void *) free;
 	wl_list_init(&resource->destroy_listener_list);
 
-	wl_hash_table_insert(client->objects, resource->object.id, resource);
+	if (wl_map_insert_at(&client->objects, resource->object.id, resource) < 0) {
+		wl_client_post_no_memory(client);
+		free(resource);
+		return NULL;
+	}
 
 	return resource;
 }
@@ -852,6 +853,8 @@ compositor_bind(struct wl_client *client,
 
 	resource = wl_client_add_object(client, &wl_compositor_interface,
 					compositor->interface, id, compositor);
+	if (resource == NULL)
+		return;
 
 	wl_resource_post_event(resource,
 			       WL_COMPOSITOR_TOKEN_VISUAL,
diff --git a/src/wayland-util.c b/src/wayland-util.c
index 3643274..0dae01b 100644
--- a/src/wayland-util.c
+++ b/src/wayland-util.c
@@ -121,3 +121,101 @@ wl_array_copy(struct wl_array *array, struct wl_array *source)
 	wl_array_add(array, source->size);
 	memcpy(array->data, source->data, source->size);
 }
+
+union map_entry {
+	uintptr_t next;
+	void *data;
+};
+
+WL_EXPORT void
+wl_map_init(struct wl_map *map)
+{
+	memset(map, 0, sizeof *map);
+}
+
+WL_EXPORT void
+wl_map_release(struct wl_map *map)
+{
+	wl_array_release(&map->entries);
+}
+
+WL_EXPORT uint32_t
+wl_map_insert_new(struct wl_map *map, void *data)
+{
+	union map_entry *start, *entry;
+
+	if (map->free_list) {
+		start = map->entries.data;
+		entry = &start[map->free_list >> 1];
+		map->free_list = entry->next;
+	} else {
+		entry = wl_array_add(&map->entries, sizeof *entry);
+		start = map->entries.data;
+	}
+
+	entry->data = data;
+
+	return entry - start;
+}
+
+WL_EXPORT int
+wl_map_insert_at(struct wl_map *map, uint32_t i, void *data)
+{
+	union map_entry *start;
+	uint32_t count;
+
+	/* assert(map->free_list == NULL */
+	count = map->entries.size / sizeof *start;
+
+	if (count < i)
+		return -1;
+
+	if (count == i)
+		wl_array_add(&map->entries, sizeof *start);
+
+	start = map->entries.data;
+	start[i].data = data;
+
+	return 0;
+}
+
+WL_EXPORT void
+wl_map_remove(struct wl_map *map, uint32_t i)
+{
+	union map_entry *start;
+	uint32_t count;
+
+	start = map->entries.data;
+	count = map->entries.size / sizeof *start;
+
+	start[i].next = map->free_list;
+	map->free_list = (i << 1) | 1;
+}
+
+WL_EXPORT void *
+wl_map_lookup(struct wl_map *map, uint32_t i)
+{
+	union map_entry *start;
+	uint32_t count;
+
+	start = map->entries.data;
+	count = map->entries.size / sizeof *start;
+
+	if (i < count && !(start[i].next & 1))
+		return start[i].data;
+
+	return NULL;
+}
+
+WL_EXPORT void
+wl_map_for_each(struct wl_map *map, wl_iterator_func_t func, void *data)
+{
+	union map_entry *start, *end, *p;
+
+	start = map->entries.data;
+	end = (union map_entry *) ((char *) map->entries.data + map->entries.size);
+
+	for (p = start; p < end; p++)
+		if (p->data && !(p->next & 1))
+			func(p->data, data);
+}
diff --git a/src/wayland-util.h b/src/wayland-util.h
index 96dc74d..76e0f1d 100644
--- a/src/wayland-util.h
+++ b/src/wayland-util.h
@@ -65,7 +65,7 @@ struct wl_object {
 	uint32_t id;
 };
 
-typedef void (*wl_hash_table_func_t)(void *element, void *data);
+typedef void (*wl_iterator_func_t)(void *element, void *data);
 
 struct wl_hash_table;
 struct wl_hash_table *wl_hash_table_create(void);
@@ -74,7 +74,7 @@ void *wl_hash_table_lookup(struct wl_hash_table *ht, uint32_t hash);
 int wl_hash_table_insert(struct wl_hash_table *ht, uint32_t hash, void *data);
 void wl_hash_table_remove(struct wl_hash_table *ht, uint32_t hash);
 void wl_hash_table_for_each(struct wl_hash_table *ht,
-			    wl_hash_table_func_t func, void *data);
+			    wl_iterator_func_t func, void *data);
 
 /**
  * wl_list - linked list
@@ -149,6 +149,19 @@ void wl_array_release(struct wl_array *array);
 void *wl_array_add(struct wl_array *array, int size);
 void wl_array_copy(struct wl_array *array, struct wl_array *source);
 
+struct wl_map {
+	struct wl_array entries;
+	uint32_t free_list;
+};
+
+void wl_map_init(struct wl_map *map);
+void wl_map_release(struct wl_map *map);
+uint32_t wl_map_insert_new(struct wl_map *map, void *data);
+int wl_map_insert_at(struct wl_map *map, uint32_t i, void *data);
+void wl_map_remove(struct wl_map *map, uint32_t i);
+void *wl_map_lookup(struct wl_map *map, uint32_t i);
+void wl_map_for_each(struct wl_map *map, wl_iterator_func_t func, void *data);
+
 #ifdef  __cplusplus
 }
 #endif