Broken wl_map

map-test.patch

diff --git a/tests/map-test.c b/tests/map-test.c
index 28a48c2..d937674 100644
--- a/tests/map-test.c
+++ b/tests/map-test.c
@@ -93,3 +93,84 @@ TEST(map_remove)
 
 	wl_map_release(&map);
 }
+
+/* Test showing how insert_at() hoses the "free_list" of wl_map. */
+TEST(map_insert_at_fail)
+{
+	struct wl_map map;
+	uint32_t a, b, c;
+
+	wl_map_init(&map);
+
+	/* Add 3 entries at position 0, 1 and 2 */
+	assert(wl_map_insert_at(&map, 0, &a) == 0);
+	assert(wl_map_insert_at(&map, 1, &b) == 0);
+	assert(wl_map_insert_at(&map, 2, &c) == 0);
+
+	/* Remove all three entries. They should now be linked in the free_list
+	 * of the wl_map so insert_new() should reuse these correctly.
+	 * This works! */
+	wl_map_remove(&map, 2);
+	wl_map_remove(&map, 1);
+	wl_map_remove(&map, 0);
+	assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, &a) == 0);
+	assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, &b) == 1);
+	assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, &c) == 2);
+
+	/* Again, remove all three entries but this time use insert_at() to add
+	 * the first object and then insert_new() to add the next 2 objects.
+	 * All three objects should be in the free list. But insert_at()
+	 * removes the object at position 0, so the free_list should only
+	 * contain 1 and 2 which should then be used by insert_new().
+	 * However, this fails as insert_at() does not modify the free list. */
+	wl_map_remove(&map, 2);
+	wl_map_remove(&map, 1);
+	wl_map_remove(&map, 0);
+	assert(wl_map_insert_at(&map, 0, &a) == 0);
+	assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, &b) == 1);
+	assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, &c) == 2);
+
+	wl_map_release(&map);
+}
+
+/* This shows the same bug as above but actually prepares the pointers that are
+ * inserted in a way that we segfault at
+ *     assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, c) == 2); */
+TEST(map_insert_at_fail_hard)
+{
+	struct wl_map map;
+	void *a, *b, *c;
+
+	/* prepare pointers to be all set but still 2-byte aligned so they are
+	 * valid pointers to add to a wl_map! */
+	a = ~1;
+	b = ~1;
+	c = ~1;
+
+	wl_map_init(&map);
+
+	/* add 3 entries */
+	assert(wl_map_insert_at(&map, 0, a) == 0);
+	assert(wl_map_insert_at(&map, 1, b) == 0);
+	assert(wl_map_insert_at(&map, 2, c) == 0);
+
+	/* show how it is supposed to work */
+	wl_map_remove(&map, 2);
+	wl_map_remove(&map, 1);
+	wl_map_remove(&map, 0);
+	assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, a) == 0);
+	assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, b) == 1);
+	assert(wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, c) == 2);
+
+	/* do this again but use insert_at() to manipulate the free_list. The
+	 * second insert_new() will then segfault because it accesses:
+	 *   map.client_entries[~1]; */
+	wl_map_remove(&map, 2);
+	wl_map_remove(&map, 1);
+	wl_map_remove(&map, 0);
+	wl_map_insert_at(&map, 0, a);
+	wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, b);
+	wl_map_insert_new(&map, WL_MAP_CLIENT_SIDE, c);
+
+	wl_map_release(&map);
+}