• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

mlange-42 / arche / 4855766297

01 May 2023 11:07PM CUT coverage: 100.0%. Remained the same
4855766297

push

github

GitHub
Cached filters use swap-remove when removing an archetype (#253)

4 of 4 new or added lines in 1 file covered. (100.0%)

3412 of 3412 relevant lines covered (100.0%)

1875.34 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0
/ecs/archetype.go
1
package ecs
2

3
import (
4
        "math"
5
        "reflect"
6
        "unsafe"
7

8
        "github.com/mlange-42/arche/ecs/stats"
9
)
10

11
// layoutSize is the size of an archetype column layout in bytes.
12
var layoutSize = unsafe.Sizeof(layout{})
13

14
// archetypeNode is a node in the archetype graph.
15
type archetypeNode struct {
16
        mask              Mask       // Mask of the archetype
17
        Ids               []ID       // List of component IDs.
18
        archetype         *archetype // The archetype
19
        archetypes        pagedSlice[archetype]
20
        archetypeMap      map[Entity]*archetype
21
        freeIndices       []int32
22
        TransitionAdd     idMap[*archetypeNode] // Mapping from component ID to add to the resulting archetype
23
        TransitionRemove  idMap[*archetypeNode] // Mapping from component ID to remove to the resulting archetype
24
        relation          int8
25
        zeroValue         []byte         // Used as source for setting storage to zero
26
        zeroPointer       unsafe.Pointer // Points to zeroValue for fast access
27
        capacityIncrement uint32         // Capacity increment
28
}
29

30
// Creates a new archetypeNode
31
func newArchetypeNode(mask Mask, relation int8, capacityIncrement int) archetypeNode {
1,221✔
32
        var arch map[Entity]*archetype
1,221✔
33
        if relation >= 0 {
1,235✔
34
                arch = map[Entity]*archetype{}
14✔
35
        }
14✔
36
        return archetypeNode{
1,221✔
37
                mask:              mask,
1,221✔
38
                archetypeMap:      arch,
1,221✔
39
                TransitionAdd:     newIDMap[*archetypeNode](),
1,221✔
40
                TransitionRemove:  newIDMap[*archetypeNode](),
1,221✔
41
                relation:          relation,
1,221✔
42
                capacityIncrement: uint32(capacityIncrement),
1,221✔
43
        }
1,221✔
44
}
45

46
func (a *archetypeNode) Matches(f Filter) bool {
1,665✔
47
        return f.Matches(a.mask, nil)
1,665✔
48
}
1,665✔
49

50
func (a *archetypeNode) Archetypes() archetypes {
1,713✔
51
        if a.HasRelation() {
1,789✔
52
                return &a.archetypes
76✔
53
        }
76✔
54
        if a.archetype == nil {
1,783✔
55
                return nil
146✔
56
        }
146✔
57
        return batchArchetype{Archetype: a.archetype, StartIndex: 0}
1,491✔
58
}
59

60
func (a *archetypeNode) GetArchetype(id Entity) *archetype {
7,592✔
61
        if a.relation >= 0 {
12,669✔
62
                return a.archetypeMap[id]
5,077✔
63
        }
5,077✔
64
        return a.archetype
2,515✔
65
}
66

67
func (a *archetypeNode) SetArchetype(arch *archetype) {
1,177✔
68
        a.archetype = arch
1,177✔
69
}
1,177✔
70

71
func (a *archetypeNode) CreateArchetype(target Entity, components ...componentType) *archetype {
53✔
72
        var arch *archetype
53✔
73
        var archIndex int32
53✔
74
        lenFree := len(a.freeIndices)
53✔
75
        if lenFree > 0 {
55✔
76
                archIndex = a.freeIndices[lenFree-1]
2✔
77
                arch = a.archetypes.Get(archIndex)
2✔
78
                a.freeIndices = a.freeIndices[:lenFree-1]
2✔
79
                arch.Activate(target, archIndex)
2✔
80
        } else {
53✔
81
                a.archetypes.Add(archetype{})
51✔
82
                archIndex := a.archetypes.Len() - 1
51✔
83
                arch = a.archetypes.Get(archIndex)
51✔
84
                arch.Init(a, archIndex, true, target, a.relation, components...)
51✔
85
        }
51✔
86
        a.archetypeMap[target] = arch
53✔
87
        return arch
53✔
88
}
89

90
func (a *archetypeNode) DeleteArchetype(arch *archetype) {
11✔
91
        delete(a.archetypeMap, arch.Relation)
11✔
92
        idx := arch.index
11✔
93
        a.freeIndices = append(a.freeIndices, idx)
11✔
94
        a.archetypes.Get(idx).Deactivate()
11✔
95
}
11✔
96

97
func (a *archetypeNode) HasRelation() bool {
6,625✔
98
        return a.relation >= 0
6,625✔
99
}
6,625✔
100

101
// Helper for accessing data from an archetype
102
type archetypeAccess struct {
103
        Mask              Mask           // Archetype's mask
104
        basePointer       unsafe.Pointer // Pointer to the first component column layout.
105
        entityPointer     unsafe.Pointer // Pointer to the entity storage
106
        Relation          Entity
107
        RelationComponent int8
108
}
109

110
// Matches checks if the archetype matches the given mask.
111
func (a *archetype) Matches(f Filter) bool {
505✔
112
        return f.Matches(a.Mask, &a.Relation)
505✔
113
}
505✔
114

115
// GetEntity returns the entity at the given index
116
func (a *archetypeAccess) GetEntity(index uintptr) Entity {
1,723✔
117
        return *(*Entity)(unsafe.Add(a.entityPointer, entitySize*index))
1,723✔
118
}
1,723✔
119

120
// Get returns the component with the given ID at the given index
121
func (a *archetypeAccess) Get(index uintptr, id ID) unsafe.Pointer {
16,902✔
122
        return a.getLayout(id).Get(index)
16,902✔
123
}
16,902✔
124

125
// GetEntity returns the entity at the given index
126
func (a *archetypeAccess) GetRelation() Entity {
21✔
127
        return a.Relation
21✔
128
}
21✔
129

130
// HasComponent returns whether the archetype contains the given component ID.
131
func (a *archetypeAccess) HasComponent(id ID) bool {
8,179✔
132
        return a.getLayout(id).pointer != nil
8,179✔
133
}
8,179✔
134

135
// HasRelation returns whether the archetype has a relation component.
136
func (a *archetypeAccess) HasRelation() bool {
12✔
137
        return a.RelationComponent >= 0
12✔
138
}
12✔
139

140
// GetLayout returns the column layout for a component.
141
func (a *archetypeAccess) getLayout(id ID) *layout {
31,661✔
142
        return (*layout)(unsafe.Add(a.basePointer, layoutSize*uintptr(id)))
31,661✔
143
}
31,661✔
144

145
// layout specification of a component column.
146
type layout struct {
147
        pointer  unsafe.Pointer // Pointer to the first element in the component column.
148
        itemSize uintptr        // Component/step size
149
}
150

151
// Get returns a pointer to the item at the given index.
152
func (l *layout) Get(index uintptr) unsafe.Pointer {
16,900✔
153
        if l.pointer == nil {
16,901✔
154
                return nil
1✔
155
        }
1✔
156
        return unsafe.Add(l.pointer, l.itemSize*index)
16,899✔
157
}
158

159
// archetype represents an ECS archetype
160
type archetype struct {
161
        archetypeAccess                 // Access helper, passed to queries.
162
        graphNode       *archetypeNode  // Node in the archetype graph.
163
        layouts         []layout        // Column layouts by ID.
164
        indices         idMap[uint32]   // Mapping from IDs to buffer indices.
165
        buffers         []reflect.Value // Reflection arrays containing component data.
166
        entityBuffer    reflect.Value   // Reflection array containing entity data.
167
        index           int32           // Index of the archetype in the world.
168
        len             uint32          // Current number of entities
169
        cap             uint32          // Current capacity
170
}
171

172
// Init initializes an archetype
173
func (a *archetype) Init(node *archetypeNode, index int32, forStorage bool, relation Entity, relationComp int8, components ...componentType) {
1,237✔
174
        var mask Mask
1,237✔
175
        if len(components) > 0 && node.Ids == nil {
2,356✔
176
                node.Ids = make([]ID, len(components))
1,119✔
177

1,119✔
178
                var maxSize uintptr = 0
1,119✔
179
                for i, c := range components {
6,391✔
180
                        node.Ids[i] = c.ID
5,272✔
181
                        size, align := c.Type.Size(), uintptr(c.Type.Align())
5,272✔
182
                        size = (size + (align - 1)) / align * align
5,272✔
183
                        if size > maxSize {
6,389✔
184
                                maxSize = size
1,117✔
185
                        }
1,117✔
186
                }
187

188
                if maxSize > 0 {
2,234✔
189
                        node.zeroValue = make([]byte, maxSize)
1,115✔
190
                        node.zeroPointer = unsafe.Pointer(&node.zeroValue[0])
1,115✔
191
                }
1,115✔
192
        }
193

194
        a.buffers = make([]reflect.Value, len(components))
1,237✔
195
        a.layouts = make([]layout, MaskTotalBits)
1,237✔
196
        a.indices = newIDMap[uint32]()
1,237✔
197
        a.index = index
1,237✔
198

1,237✔
199
        cap := 1
1,237✔
200
        if forStorage {
2,393✔
201
                cap = int(node.capacityIncrement)
1,156✔
202
        }
1,156✔
203

204
        prev := -1
1,237✔
205
        for i, c := range components {
6,561✔
206
                if int(c.ID) <= prev {
5,325✔
207
                        panic("component arguments must be sorted by ID")
1✔
208
                }
209
                prev = int(c.ID)
5,323✔
210
                mask.Set(c.ID, true)
5,323✔
211

5,323✔
212
                size, align := c.Type.Size(), uintptr(c.Type.Align())
5,323✔
213
                size = (size + (align - 1)) / align * align
5,323✔
214

5,323✔
215
                a.buffers[i] = reflect.New(reflect.ArrayOf(cap, c.Type)).Elem()
5,323✔
216
                a.layouts[c.ID] = layout{
5,323✔
217
                        a.buffers[i].Addr().UnsafePointer(),
5,323✔
218
                        size,
5,323✔
219
                }
5,323✔
220
                a.indices.Set(c.ID, uint32(i))
5,323✔
221
        }
222
        a.entityBuffer = reflect.New(reflect.ArrayOf(cap, entityType)).Elem()
1,236✔
223

1,236✔
224
        a.archetypeAccess = archetypeAccess{
1,236✔
225
                basePointer:       unsafe.Pointer(&a.layouts[0]),
1,236✔
226
                entityPointer:     a.entityBuffer.Addr().UnsafePointer(),
1,236✔
227
                Mask:              mask,
1,236✔
228
                Relation:          relation,
1,236✔
229
                RelationComponent: relationComp,
1,236✔
230
        }
1,236✔
231

1,236✔
232
        a.graphNode = node
1,236✔
233

1,236✔
234
        a.len = 0
1,236✔
235
        a.cap = uint32(cap)
1,236✔
236
}
237

238
// Add adds an entity with optionally zeroed components to the archetype
239
func (a *archetype) Alloc(entity Entity) uintptr {
9,764✔
240
        idx := uintptr(a.len)
9,764✔
241
        a.extend(1)
9,764✔
242
        a.addEntity(idx, &entity)
9,764✔
243
        a.len++
9,764✔
244
        return idx
9,764✔
245
}
9,764✔
246

247
// Add adds storage to the archetype
248
func (a *archetype) AllocN(count uint32) {
30✔
249
        a.extend(count)
30✔
250
        a.len += count
30✔
251
}
30✔
252

253
// Add adds an entity with components to the archetype
254
func (a *archetype) Add(entity Entity, components ...Component) uintptr {
9✔
255
        if len(components) != len(a.graphNode.Ids) {
10✔
256
                panic("Invalid number of components")
1✔
257
        }
258
        idx := uintptr(a.len)
8✔
259

8✔
260
        a.extend(1)
8✔
261
        a.addEntity(idx, &entity)
8✔
262
        for _, c := range components {
24✔
263
                lay := a.getLayout(c.ID)
16✔
264
                size := lay.itemSize
16✔
265
                if size == 0 {
18✔
266
                        continue
2✔
267
                }
268
                src := reflect.ValueOf(c.Comp).UnsafePointer()
14✔
269
                dst := a.Get(uintptr(idx), c.ID)
14✔
270
                a.copy(src, dst, size)
14✔
271
        }
272
        a.len++
8✔
273
        return idx
8✔
274
}
275

276
// Remove removes an entity and its components from the archetype.
277
//
278
// Performs a swap-remove and reports whether a swap was necessary
279
// (i.e. not the last entity that was removed).
280
func (a *archetype) Remove(index uintptr) bool {
4,947✔
281
        swapped := a.removeEntity(index)
4,947✔
282

4,947✔
283
        old := uintptr(a.len - 1)
4,947✔
284

4,947✔
285
        if index != old {
5,126✔
286
                for _, id := range a.graphNode.Ids {
405✔
287
                        lay := a.getLayout(id)
226✔
288
                        size := lay.itemSize
226✔
289
                        if size == 0 {
235✔
290
                                continue
9✔
291
                        }
292
                        src := unsafe.Add(lay.pointer, old*size)
217✔
293
                        dst := unsafe.Add(lay.pointer, index*size)
217✔
294
                        a.copy(src, dst, size)
217✔
295
                }
296
        }
297
        a.ZeroAll(old)
4,947✔
298
        a.len--
4,947✔
299

4,947✔
300
        return swapped
4,947✔
301
}
302

303
// ZeroAll resets a block of storage in all buffers.
304
func (a *archetype) ZeroAll(index uintptr) {
4,947✔
305
        for _, id := range a.graphNode.Ids {
7,849✔
306
                a.Zero(index, id)
2,902✔
307
        }
2,902✔
308
}
309

310
// ZeroAll resets a block of storage in one buffer.
311
func (a *archetype) Zero(index uintptr, id ID) {
2,902✔
312
        lay := a.getLayout(id)
2,902✔
313
        size := lay.itemSize
2,902✔
314
        if size == 0 {
5,443✔
315
                return
2,541✔
316
        }
2,541✔
317
        dst := unsafe.Add(lay.pointer, index*size)
361✔
318
        a.copy(a.graphNode.zeroPointer, dst, size)
361✔
319
}
320

321
// SetEntity overwrites an entity
322
func (a *archetype) SetEntity(index uintptr, entity Entity) {
1,062✔
323
        a.addEntity(index, &entity)
1,062✔
324
}
1,062✔
325

326
// Set overwrites a component with the data behind the given pointer
327
func (a *archetype) Set(index uintptr, id ID, comp interface{}) unsafe.Pointer {
832✔
328
        lay := a.getLayout(id)
832✔
329
        dst := a.Get(index, id)
832✔
330
        size := lay.itemSize
832✔
331
        if size == 0 {
861✔
332
                return dst
29✔
333
        }
29✔
334
        rValue := reflect.ValueOf(comp)
803✔
335

803✔
336
        src := rValue.UnsafePointer()
803✔
337
        a.copy(src, dst, size)
803✔
338
        return dst
803✔
339
}
340

341
// SetPointer overwrites a component with the data behind the given pointer
342
func (a *archetype) SetPointer(index uintptr, id ID, comp unsafe.Pointer) unsafe.Pointer {
2,559✔
343
        lay := a.getLayout(id)
2,559✔
344
        dst := a.Get(index, id)
2,559✔
345
        size := lay.itemSize
2,559✔
346
        if size == 0 {
5,093✔
347
                return dst
2,534✔
348
        }
2,534✔
349

350
        a.copy(comp, dst, size)
25✔
351
        return dst
25✔
352
}
353

354
// Reset removes all entities and components.
355
//
356
// Does NOT free the reserved memory.
357
func (a *archetype) Reset() {
33✔
358
        if a.len == 0 {
49✔
359
                return
16✔
360
        }
16✔
361
        a.len = 0
17✔
362
        for _, buf := range a.buffers {
38✔
363
                buf.SetZero()
21✔
364
        }
21✔
365
}
366

367
func (a *archetype) Deactivate() {
11✔
368
        a.Reset()
11✔
369
        a.index = -1
11✔
370
}
11✔
371

372
func (a *archetype) Activate(target Entity, index int32) {
2✔
373
        a.index = index
2✔
374
        a.Relation = target
2✔
375
}
2✔
376

377
func (a *archetype) IsActive() bool {
535✔
378
        return a.index >= 0
535✔
379
}
535✔
380

381
// Components returns the component IDs for this archetype
382
func (a *archetype) Components() []ID {
2,191✔
383
        return a.graphNode.Ids
2,191✔
384
}
2,191✔
385

386
// Len reports the number of entities in the archetype
387
func (a *archetype) Len() uint32 {
5,659✔
388
        return a.len
5,659✔
389
}
5,659✔
390

391
// Cap reports the current capacity of the archetype
392
func (a *archetype) Cap() uint32 {
23✔
393
        return a.cap
23✔
394
}
23✔
395

396
// Stats generates statistics for an archetype
397
func (a *archetype) Stats(reg *componentRegistry[ID]) stats.ArchetypeStats {
6✔
398
        ids := a.Components()
6✔
399
        aCompCount := len(ids)
6✔
400
        aTypes := make([]reflect.Type, aCompCount)
6✔
401
        for j, id := range ids {
10✔
402
                aTypes[j], _ = reg.ComponentType(id)
4✔
403
        }
4✔
404

405
        cap := int(a.Cap())
6✔
406
        memPerEntity := 0
6✔
407
        for _, id := range a.graphNode.Ids {
10✔
408
                lay := a.getLayout(id)
4✔
409
                memPerEntity += int(lay.itemSize)
4✔
410
        }
4✔
411
        memory := cap * (int(entitySize) + memPerEntity)
6✔
412

6✔
413
        return stats.ArchetypeStats{
6✔
414
                IsActive:        a.IsActive(),
6✔
415
                Size:            int(a.Len()),
6✔
416
                Capacity:        cap,
6✔
417
                Components:      aCompCount,
6✔
418
                ComponentIDs:    ids,
6✔
419
                ComponentTypes:  aTypes,
6✔
420
                Memory:          memory,
6✔
421
                MemoryPerEntity: memPerEntity,
6✔
422
        }
6✔
423
}
424

425
// UpdateStats updates statistics for an archetype
426
func (a *archetype) UpdateStats(stats *stats.ArchetypeStats, reg *componentRegistry[ID]) {
7✔
427
        if stats.Dirty {
8✔
428
                ids := a.Components()
1✔
429
                aCompCount := len(ids)
1✔
430
                aTypes := make([]reflect.Type, aCompCount)
1✔
431
                for j, id := range ids {
2✔
432
                        aTypes[j], _ = reg.ComponentType(id)
1✔
433
                }
1✔
434

435
                memPerEntity := 0
1✔
436
                for _, id := range a.graphNode.Ids {
2✔
437
                        lay := a.getLayout(id)
1✔
438
                        memPerEntity += int(lay.itemSize)
1✔
439
                }
1✔
440

441
                stats.IsActive = a.IsActive()
1✔
442
                stats.Components = aCompCount
1✔
443
                stats.ComponentIDs = ids
1✔
444
                stats.ComponentTypes = aTypes
1✔
445
                stats.MemoryPerEntity = memPerEntity
1✔
446
                stats.Dirty = false
1✔
447
        }
448

449
        cap := int(a.Cap())
7✔
450
        memory := cap * (int(entitySize) + stats.MemoryPerEntity)
7✔
451

7✔
452
        stats.Size = int(a.Len())
7✔
453
        stats.Capacity = cap
7✔
454
        stats.Memory = memory
7✔
455

456
}
457

458
// copy from one pointer to another.
459
func (a *archetype) copy(src, dst unsafe.Pointer, itemSize uintptr) {
12,433✔
460
        dstSlice := (*[math.MaxInt32]byte)(dst)[:itemSize:itemSize]
12,433✔
461
        srcSlice := (*[math.MaxInt32]byte)(src)[:itemSize:itemSize]
12,433✔
462
        copy(dstSlice, srcSlice)
12,433✔
463
}
12,433✔
464

465
// extend the memory buffers if necessary for adding an entity.
466
func (a *archetype) extend(by uint32) {
9,805✔
467
        required := a.len + by
9,805✔
468
        if a.cap >= required {
19,573✔
469
                return
9,768✔
470
        }
9,768✔
471
        a.cap = capacityU32(required, a.graphNode.capacityIncrement)
37✔
472

37✔
473
        old := a.entityBuffer
37✔
474
        a.entityBuffer = reflect.New(reflect.ArrayOf(int(a.cap), entityType)).Elem()
37✔
475
        a.entityPointer = a.entityBuffer.Addr().UnsafePointer()
37✔
476
        reflect.Copy(a.entityBuffer, old)
37✔
477

37✔
478
        for _, id := range a.graphNode.Ids {
77✔
479
                lay := a.getLayout(id)
40✔
480
                if lay.itemSize == 0 {
41✔
481
                        continue
1✔
482
                }
483
                index, _ := a.indices.Get(id)
39✔
484
                old := a.buffers[index]
39✔
485
                a.buffers[index] = reflect.New(reflect.ArrayOf(int(a.cap), old.Type().Elem())).Elem()
39✔
486
                lay.pointer = a.buffers[index].Addr().UnsafePointer()
39✔
487
                reflect.Copy(a.buffers[index], old)
39✔
488
        }
489
}
490

491
// Adds an entity at the given index. Does not extend the entity buffer.
492
func (a *archetype) addEntity(index uintptr, entity *Entity) {
10,834✔
493
        dst := unsafe.Add(a.entityPointer, entitySize*index)
10,834✔
494
        src := unsafe.Pointer(entity)
10,834✔
495
        a.copy(src, dst, entitySize)
10,834✔
496
}
10,834✔
497

498
// removeEntity removes an entity from tne archetype.
499
// Components need to be removed separately.
500
func (a *archetype) removeEntity(index uintptr) bool {
4,947✔
501
        old := uintptr(a.len - 1)
4,947✔
502

4,947✔
503
        if index == old {
9,715✔
504
                return false
4,768✔
505
        }
4,768✔
506

507
        src := unsafe.Add(a.entityPointer, old*entitySize)
179✔
508
        dst := unsafe.Add(a.entityPointer, index*entitySize)
179✔
509
        a.copy(src, dst, entitySize)
179✔
510

179✔
511
        return true
179✔
512
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc