Repository: mlange-42/arche
Pull request #245 (2023-04-30 21:08:00)

Support an unlimited number of cached filters, instead of 128

coveralls: ## Pull Request Test Coverage Report for [Build 4846400148](https://coveralls.io/builds/59471442)

* **25** of **42**   **(59.52%)**  changed or added relevant lines in **2** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage decreased (**-0.5%**) to **99.458%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [ecs/pool.go](https://coveralls.io/builds/59471442/source?filename=ecs%2Fpool.go#L164) | 17 | 34 | 50.0%
<!-- | **Total:** | **25** | **42** | **59.52%** | -->


|  Totals | [![Coverage Status](https://coveralls.io/builds/59471442/badge)](https://coveralls.io/builds/59471442) |
| :-- | --: |
| Change from base [Build 4846177152](https://coveralls.io/builds/59471194): |  -0.5% |
| Covered Lines: | 3122 |
| Relevant Lines: | 3139 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index d7583a3..d37e052 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -14,6 +14,7 @@
 ### Features
 
 * Relation archetypes are removed when they are empty *and* the target entity is dead (#238, #242)
+* Support an unlimited number of cached filters, instead of 128 (#245)
 
 ### Performance
 
diff --git a/ecs/cache.go b/ecs/cache.go
index 1d21496..93b039c 100644
--- a/ecs/cache.go
+++ b/ecs/cache.go
@@ -2,7 +2,7 @@ package ecs
 
 // Cache entry for a [Filter].
 type cacheEntry struct {
-	ID         ID                // Filter ID.
+	ID         uint32            // Filter ID.
 	Filter     Filter            // The underlying filter.
 	Archetypes archetypePointers // Archetypes matching the filter.
 }
@@ -21,19 +21,18 @@ type cacheEntry struct {
 // Further, cached filters should be used for complex queries built with package [github.com/mlange-42/arche/filter].
 //
 // The overhead of tracking cached filters internally is very low, as updates are required only when new archetypes are created.
-// The number of cached filters is limited to [MaskTotalBits].
 type Cache struct {
-	indices       idMap[int]                       // Mapping from filter IDs to indices in filters
+	indices       map[uint32]int                   // Mapping from filter IDs to indices in filters
 	filters       []cacheEntry                     // The cached filters, indexed by indices
 	getArchetypes func(f Filter) archetypePointers // Callback for getting archetypes for a new filter from the world
-	bitPool       bitPool                          // Pool for filter IDs
+	intPool       intPool[uint32]                  // Pool for filter IDs
 }
 
 // newCache creates a new [Cache].
 func newCache() Cache {
 	return Cache{
-		bitPool: bitPool{},
-		indices: newIDMap[int](),
+		intPool: newIntPool[uint32](128),
+		indices: map[uint32]int{},
 		filters: []cacheEntry{},
 	}
 }
@@ -49,14 +48,14 @@ func (c *Cache) Register(f Filter) CachedFilter {
 	if _, ok := f.(*CachedFilter); ok {
 		panic("filter is already cached")
 	}
-	id := c.bitPool.Get()
+	id := c.intPool.Get()
 	c.filters = append(c.filters,
 		cacheEntry{
 			ID:         id,
 			Filter:     f,
 			Archetypes: c.getArchetypes(f),
 		})
-	c.indices.Set(id, len(c.filters)-1)
+	c.indices[id] = len(c.filters) - 1
 	return CachedFilter{f, id}
 }
 
@@ -64,17 +63,17 @@ func (c *Cache) Register(f Filter) CachedFilter {
 //
 // Returns the original filter.
 func (c *Cache) Unregister(f *CachedFilter) Filter {
-	idx, ok := c.indices.Get(f.id)
+	idx, ok := c.indices[f.id]
 	if !ok {
 		panic("no filter for id found to unregister")
 	}
 	filter := c.filters[idx].Filter
-	c.indices.Remove(f.id)
+	delete(c.indices, f.id)
 
 	last := len(c.filters) - 1
 	if idx != last {
 		c.filters[idx], c.filters[last] = c.filters[last], c.filters[idx]
-		c.indices.Set(c.filters[idx].ID, idx)
+		c.indices[c.filters[idx].ID] = idx
 	}
 	c.filters[last] = cacheEntry{}
 	c.filters = c.filters[:last]
@@ -86,7 +85,7 @@ func (c *Cache) Unregister(f *CachedFilter) Filter {
 //
 // Panics if there is no entry for the filter's ID.
 func (c *Cache) get(f *CachedFilter) *cacheEntry {
-	if idx, ok := c.indices.Get(f.id); ok {
+	if idx, ok := c.indices[f.id]; ok {
 		return &c.filters[idx]
 	}
 	panic("no filter for id found")
diff --git a/ecs/filter.go b/ecs/filter.go
index 38aa5c0..988df9d 100644
--- a/ecs/filter.go
+++ b/ecs/filter.go
@@ -39,7 +39,7 @@ func (f *RelationFilter) Matches(bits Mask, relation *Entity) bool {
 // Create it using [Cache.Register].
 type CachedFilter struct {
 	filter Filter
-	id     ID
+	id     uint32
 }
 
 // Matches matches a filter against a mask.
diff --git a/ecs/pool.go b/ecs/pool.go
index f549a74..3fc3ccf 100644
--- a/ecs/pool.go
+++ b/ecs/pool.go
@@ -4,6 +4,10 @@ import (
 	"math"
 )
 
+type number interface {
+	int | int8 | uint8 | int16 | uint16 | int32 | uint32 | int64 | uint64
+}
+
 // entityPool is an implementation using implicit linked lists.
 // Implements https://skypjack.github.io/2019-05-06-ecs-baf-part-3/
 type entityPool struct {
@@ -132,3 +136,58 @@ func (p *bitPool) Reset() {
 	p.length = 0
 	p.available = 0
 }
+
+// entityPool is an implementation using implicit linked lists.
+// Implements https://skypjack.github.io/2019-05-06-ecs-baf-part-3/
+type intPool[T number] struct {
+	pool              []T
+	next              T
+	available         uint32
+	capacityIncrement uint32
+}
+
+// newEntityPool creates a new, initialized Entity pool.
+func newIntPool[T number](capacityIncrement uint32) intPool[T] {
+	return intPool[T]{
+		pool:              make([]T, 0, capacityIncrement),
+		next:              0,
+		available:         0,
+		capacityIncrement: capacityIncrement,
+	}
+}
+
+// Get returns a fresh or recycled entity.
+func (p *intPool[T]) Get() T {
+	if p.available == 0 {
+		return p.getNew()
+	}
+	curr := p.next
+	p.next, p.pool[p.next] = p.pool[p.next], p.next
+	p.available--
+	return p.pool[curr]
+}
+
+// Allocates and returns a new entity. For internal use.
+func (p *intPool[T]) getNew() T {
+	e := T(len(p.pool))
+	if len(p.pool) == cap(p.pool) {
+		old := p.pool
+		p.pool = make([]T, len(p.pool), len(p.pool)+int(p.capacityIncrement))
+		copy(p.pool, old)
+	}
+	p.pool = append(p.pool, e)
+	return e
+}
+
+// Recycle hands an entity back for recycling.
+func (p *intPool[T]) Recycle(e T) {
+	p.next, p.pool[e] = e, p.next
+	p.available++
+}
+
+// Reset recycles all entities. Does NOT free the reserved memory.
+func (p *intPool[T]) Reset() {
+	p.pool = p.pool[:0]
+	p.next = 0
+	p.available = 0
+}


Test patch:
diff --git a/ecs/pool_test.go b/ecs/pool_test.go
index cd3aeea..60e4faa 100644
--- a/ecs/pool_test.go
+++ b/ecs/pool_test.go
@@ -133,3 +133,22 @@ func TestBitPool(t *testing.T) {
 		assert.Equal(t, i, int(p.Get()))
 	}
 }
+
+func TestIntPool(t *testing.T) {
+	p := newIntPool[int](16)
+
+	for n := 0; n < 3; n++ {
+		for i := 0; i < 32; i++ {
+			assert.Equal(t, i, p.Get())
+		}
+
+		assert.Equal(t, 32, len(p.pool))
+
+		p.Recycle(3)
+		p.Recycle(4)
+		assert.Equal(t, 4, p.Get())
+		assert.Equal(t, 3, p.Get())
+
+		p.Reset()
+	}
+}