stretchy component pools

2 files changed, 96 insertions, 44 deletions

diff --git a/world.cpp b/world.cpp
index 5cfd8bf..410ed04 100644
--- a/world.cpp
+++ b/world.cpp
@@ -8,12 +8,44 @@ extern "C" {
 
 static int component_sizes[max_components];
 
+void Slinky::init(Arena* a, int size) {
+	data = arena_alloc(a, size * slinky_size);
+	entities = (Entity_Id*)arena_alloc(
+		a,
+		sizeof *entities * slinky_size
+	);
+	count = 0;
+}
+
+void* Slinky::add(Entity_Id eid, int size, int& mapping) {
+	int idx = count++;
+	assert(count <= slinky_size);
+	entities[idx] = eid;
+	mapping = idx;
+	return &((char*)data)[idx * size];
+}
+
+void* Slinky::get(Entity_Id eid, int mapping, int size) {
+	char* e = &((char*)data)[mapping * size];
+	assert(eid == entities[mapping]);
+	(void)eid;
+	return e;
+}
+
+void Slinky::remove(Entity_Id eid, int mapping, int size) {
+	int end = (count - 1) * size;
+	assert(eid == entities[mapping]);
+	(void)eid;
+	memmove(
+		(char*)data + mapping * size,
+		(char*)data + end * size,
+		size
+	);
+}
+
 void Pool::init(Arena* a, Component_Mask m) {
 	int i, coff;
-	next = 0;
-	size = 0;
 	mask = m;
-	count = 0;
 	for (i = 0, coff = 0; i < max_components; i++) {
 		if (m & ((Component_Mask)1 << i)) {
 			offsets[i] = coff;
@@ -21,50 +53,49 @@ void Pool::init(Arena* a, Component_Mask m) {
 		}
 	}
 	size = coff;
-	data = arena_alloc(a, size * pool_cap);
+	slinkies[0].init(a, size);
+	slinky_count = 1;
+	count = 0;
 }
 
-void* Pool::add(Arena* a, Entity_Id eid) {
-	int idx;
-	if (next)
-		return next->add(a, eid);
-	if (count >= pool_cap) {
-		next = (Pool*)arena_alloc(a, sizeof *next);
-		next->init(a, mask);
-		return next->add(a, eid);
+Slinky& Pool::get_slinky(Arena* a) {
+	int idx = slinky_count - 1;
+	if (slinkies[idx].count < slinky_size) {
+		return slinkies[idx];
 	}
-	idx = count++;
-	entities[idx] = eid;
-	mapping[entity_index(eid)] = idx;
-	return &((char*)data)[idx * size];
+	assert(slinky_count < max_slinkies);
+	Slinky& s = slinkies[slinky_count++];
+	s.init(a, size);
+	return s;
+}
+
+void* Pool::add(Arena* a, Entity_Id eid) {
+	Slinky& slinky = get_slinky(a);
+	Mapping& m = mapping[entity_index(eid)];
+	m.slinky = &slinky - slinkies;
+	count++;
+	return slinky.add(eid, size, m.mapping);
 }
 
 void Pool::remove(Entity_Id eid) {
-	int eind = entity_index(eid);
-	int end = count - 1;
-	assert(eid == entities[mapping[eind]]);
-	memmove(
-		(char*)data + eind * size,
-		(char*)data + end * size,
-		size
-	);
-	entities[eind] = entities[count];
-	mapping[end] = eind;
-	count = end;
+	Mapping m = mapping[entity_index(eid)];
+	Slinky& s = slinkies[m.slinky];
+	s.remove(eid, m.mapping, size);
+	count--;
 }
 
 void* Pool::get(Entity_Id eid, int cid) {
-	int eind = entity_index(eid);
-	char* e = &((char*)data)[mapping[eind] * size];
-	assert(eid == entities[mapping[eind]]);
-	return &e[offsets[cid]];
+	Mapping m = mapping[entity_index(eid)];
+	Slinky& s = slinkies[m.slinky];
+	char* ptr = (char*)s.get(eid, m.mapping, size);
+	return ptr + offsets[cid];
 }
 
 void* Pool::get(Entity_Id eid) {
-	int eind = entity_index(eid);
-	void* e = &((char*)data)[mapping[eind] * size];
-	assert(eid == entities[mapping[eind]]);
-	return e;
+	Mapping m = mapping[entity_index(eid)];
+	Slinky& s = slinkies[m.slinky];
+	char* ptr = (char*)s.get(eid, m.mapping, size);
+	return ptr;
 }
 
 int get_new_component_id(int size) {
@@ -166,7 +197,6 @@ void* World::get(Entity_Id eid, int cid) {
 	int eind = entity_index(eid);
 	Pool& p = get_pool(masks[eind]);
 	assert(versions[eind] == entity_version(eid));
-	assert(p.entities[p.mapping[eind]] == eid);
 	return p.get(eid, cid);
 }
 
diff --git a/world.hpp b/world.hpp
index 267b58a..a45cf9c 100644
--- a/world.hpp
+++ b/world.hpp
@@ -12,19 +12,35 @@ using Component_Mask = uint64_t;
 using Entity_Id = uint32_t;
 
 #define max_entities 1024
-#define pool_cap 128
+#define slinky_size 128
 #define max_components 64
+#define max_slinkies (max_entities / slinky_size)
+
+struct Slinky {
+	Entity_Id* entities;
+	void* data;
+	int count;
+
+	void init(Arena* a, int size);
+	void* add(Entity_Id eid, int size, int& mapping);
+	void* get(Entity_Id eid, int mapping, int size);
+	void remove(Entity_Id eid, int mapping, int size);
+};
 
 struct Pool {
+	struct Mapping {
+		int slinky;
+		int mapping;
+	};
+
 	Component_Mask mask;
-	Pool* next;
-	void* data;
-	Entity_Id entities[pool_cap];
-	int mapping[max_entities];
+	Slinky slinkies[max_slinkies];
+	Mapping mapping[max_entities];
 	int offsets[max_components];
-	int size, count;
+	int size, count, slinky_count;
 
 	void init(Arena* a, Component_Mask m);
+	Slinky& get_slinky(Arena* a);
 	void* add(Arena* a, Entity_Id eid);
 	void* get(Entity_Id eid, int cid);
 	void* get(Entity_Id eid);
@@ -126,8 +142,11 @@ struct World {
 			template <typename C>
 			C& get() {
 				Pool* p = v->pools[ind];
+				Slinky& s = p->slinkies[ptr / slinky_size];
+				int si = &s - p->slinkies;
+				int off = ptr - (si * slinky_size);
 				return *(C*)(
-					(char*)p->data + ptr * p->size +
+					(char*)s.data + off * p->size +
 					p->offsets[v->w->get_component_id<C>()]
 				);
 			}
@@ -138,7 +157,10 @@ struct World {
 
 			Entity_Id entity() {
 				Pool* p = v->pools[ind];
-				return p->entities[ptr];
+				Slinky& s = p->slinkies[ptr / slinky_size];
+				int si = &s - p->slinkies;
+				int off = ptr - (si * slinky_size);
+				return s.entities[off];
 			}
 		};