-
Notifications
You must be signed in to change notification settings - Fork 175
/
pool.go
346 lines (289 loc) · 11.1 KB
/
pool.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
package heropool
import (
"math/rand"
"github.com/onflow/flow-go/model/flow"
)
type EjectionMode string
const (
RandomEjection = EjectionMode("random-ejection")
LRUEjection = EjectionMode("lru-ejection")
NoEjection = EjectionMode("no-ejection")
)
// EIndex is data type representing an entity index in Pool.
type EIndex uint32
// poolEntity represents the data type that is maintained by
type poolEntity struct {
PoolEntity
// owner maintains an external reference to the key associated with this entity.
// The key is maintained by the HeroCache, and entity is maintained by Pool.
owner uint64
// node keeps the link to the previous and next entities.
// When this entity is allocated, the node maintains the connections it to the next and previous (used) pool entities.
// When this entity is unallocated, the node maintains the connections to the next and previous unallocated (free) pool entities.
node link
}
type PoolEntity struct {
// Identity associated with this entity.
id flow.Identifier
// Actual entity itself.
entity flow.Entity
}
func (p PoolEntity) Id() flow.Identifier {
return p.id
}
func (p PoolEntity) Entity() flow.Entity {
return p.entity
}
type Pool struct {
size uint32
free state // keeps track of free slots.
used state // keeps track of allocated slots to cachedEntities.
poolEntities []poolEntity
ejectionMode EjectionMode
}
func NewHeroPool(sizeLimit uint32, ejectionMode EjectionMode) *Pool {
l := &Pool{
free: state{
head: poolIndex{index: 0},
tail: poolIndex{index: 0},
},
used: state{
head: poolIndex{index: 0},
tail: poolIndex{index: 0},
},
poolEntities: make([]poolEntity, sizeLimit),
ejectionMode: ejectionMode,
}
l.initFreeEntities()
return l
}
// initFreeEntities initializes the free double linked-list with the indices of all cached entity poolEntities.
func (p *Pool) initFreeEntities() {
p.free.head.setPoolIndex(0)
p.free.tail.setPoolIndex(0)
for i := 1; i < len(p.poolEntities); i++ {
// appends slice index i to tail of free linked list
p.connect(p.free.tail, EIndex(i))
// and updates its tail
p.free.tail.setPoolIndex(EIndex(i))
}
}
// Add writes given entity into a poolEntity on the underlying entities linked-list.
//
// The first boolean return value (slotAvailable) says whether pool has an available slot. Pool goes out of available slots if
// it is full and no ejection is set.
//
// If the pool has an available slot (either empty or by ejection), then the second boolean returned value (ejectionOccurred)
// determines whether an ejection happened to make one slot free or not. Ejection happens if there is no available
// slot, and there is an ejection mode set.
func (p *Pool) Add(entityId flow.Identifier, entity flow.Entity, owner uint64) (i EIndex, slotAvailable bool, ejectionOccurred bool) {
entityIndex, slotAvailable, ejectionHappened := p.sliceIndexForEntity()
if slotAvailable {
p.poolEntities[entityIndex].entity = entity
p.poolEntities[entityIndex].id = entityId
p.poolEntities[entityIndex].owner = owner
p.poolEntities[entityIndex].node.next.setUndefined()
p.poolEntities[entityIndex].node.prev.setUndefined()
if p.used.head.isUndefined() {
// used list is empty, hence setting head of used list to current entityIndex.
p.used.head.setPoolIndex(entityIndex)
p.poolEntities[p.used.head.getSliceIndex()].node.prev.setUndefined()
}
if !p.used.tail.isUndefined() {
// links new entity to the tail
p.connect(p.used.tail, entityIndex)
}
// since we are appending to the used list, entityIndex also acts as tail of the list.
p.used.tail.setPoolIndex(entityIndex)
p.size++
}
return entityIndex, slotAvailable, ejectionHappened
}
// Get returns entity corresponding to the entity index from the underlying list.
func (p Pool) Get(entityIndex EIndex) (flow.Identifier, flow.Entity, uint64) {
return p.poolEntities[entityIndex].id, p.poolEntities[entityIndex].entity, p.poolEntities[entityIndex].owner
}
// All returns all stored entities in this pool.
func (p Pool) All() []PoolEntity {
all := make([]PoolEntity, p.size)
next := p.used.head
for i := uint32(0); i < p.size; i++ {
e := p.poolEntities[next.getSliceIndex()]
all[i] = e.PoolEntity
next = e.node.next
}
return all
}
// Head returns the head of used items. Assuming no ejection happened and pool never goes beyond limit, Head returns
// the first inserted element.
func (p Pool) Head() (flow.Entity, bool) {
if p.used.head.isUndefined() {
return nil, false
}
e := p.poolEntities[p.used.head.getSliceIndex()]
return e.Entity(), true
}
// sliceIndexForEntity returns a slice index which hosts the next entity to be added to the list.
//
// The first boolean return value (hasAvailableSlot) says whether pool has an available slot.
// Pool goes out of available slots if it is full and no ejection is set.
//
// If the pool has an available slot (either empty or by ejection), then the second boolean returned value
// (ejectionOccurred) determines whether an ejection happened to make one slot free or not.
// Ejection happens if there is no available slot, and there is an ejection mode set.
func (p *Pool) sliceIndexForEntity() (i EIndex, hasAvailableSlot bool, ejectionOccurred bool) {
if p.free.head.isUndefined() {
// the free list is empty, so we are out of space, and we need to eject.
switch p.ejectionMode {
case NoEjection:
// pool is set for no ejection, hence, no slice index is selected, abort immediately.
return 0, false, false
case LRUEjection:
// LRU ejection
// the used head is the oldest entity, so we turn the used head to a free head here.
p.invalidateUsedHead()
return p.claimFreeHead(), true, true
case RandomEjection:
// we only eject randomly when the pool is full and random ejection is on.
randomIndex := EIndex(rand.Uint32() % p.size)
p.invalidateEntityAtIndex(randomIndex)
return p.claimFreeHead(), true, true
}
}
// claiming the head of free list as the slice index for the next entity to be added
return p.claimFreeHead(), true, false // returning false for no ejection.
}
// Size returns total number of entities that this list maintains.
func (p Pool) Size() uint32 {
return p.size
}
// getHeads returns entities corresponding to the used and free heads.
func (p Pool) getHeads() (*poolEntity, *poolEntity) {
var usedHead, freeHead *poolEntity
if !p.used.head.isUndefined() {
usedHead = &p.poolEntities[p.used.head.getSliceIndex()]
}
if !p.free.head.isUndefined() {
freeHead = &p.poolEntities[p.free.head.getSliceIndex()]
}
return usedHead, freeHead
}
// getTails returns entities corresponding to the used and free tails.
func (p Pool) getTails() (*poolEntity, *poolEntity) {
var usedTail, freeTail *poolEntity
if !p.used.tail.isUndefined() {
usedTail = &p.poolEntities[p.used.tail.getSliceIndex()]
}
if !p.free.tail.isUndefined() {
freeTail = &p.poolEntities[p.free.tail.getSliceIndex()]
}
return usedTail, freeTail
}
// connect links the prev and next nodes as the adjacent nodes in the double-linked list.
func (p *Pool) connect(prev poolIndex, next EIndex) {
p.poolEntities[prev.getSliceIndex()].node.next.setPoolIndex(next)
p.poolEntities[next].node.prev = prev
}
// invalidateUsedHead moves current used head forward by one node. It
// also removes the entity the invalidated head is presenting and appends the
// node represented by the used head to the tail of the free list.
func (p *Pool) invalidateUsedHead() EIndex {
headSliceIndex := p.used.head.getSliceIndex()
p.invalidateEntityAtIndex(headSliceIndex)
return headSliceIndex
}
// claimFreeHead moves the free head forward, and returns the slice index of the
// old free head to host a new entity.
func (p *Pool) claimFreeHead() EIndex {
oldFreeHeadIndex := p.free.head.getSliceIndex()
// moves head forward
p.free.head = p.poolEntities[oldFreeHeadIndex].node.next
// new head should point to an undefined prev,
// but we first check if list is not empty, i.e.,
// head itself is not undefined.
if !p.free.head.isUndefined() {
p.poolEntities[p.free.head.getSliceIndex()].node.prev.setUndefined()
}
// also, we check if the old head and tail are aligned and, if so, update the
// tail as well. This happens when we claim the only existing
// node of the free list.
if p.free.tail.getSliceIndex() == oldFreeHeadIndex {
p.free.tail.setUndefined()
}
// clears pointers of claimed head
p.poolEntities[oldFreeHeadIndex].node.next.setUndefined()
p.poolEntities[oldFreeHeadIndex].node.prev.setUndefined()
return oldFreeHeadIndex
}
// Remove removes entity corresponding to given getSliceIndex from the list.
func (p *Pool) Remove(sliceIndex EIndex) {
p.invalidateEntityAtIndex(sliceIndex)
}
// invalidateEntityAtIndex invalidates the given getSliceIndex in the linked list by
// removing its corresponding linked-list node from the used linked list, and appending
// it to the tail of the free list. It also removes the entity that the invalidated node is presenting.
func (p *Pool) invalidateEntityAtIndex(sliceIndex EIndex) {
prev := p.poolEntities[sliceIndex].node.prev
next := p.poolEntities[sliceIndex].node.next
if sliceIndex != p.used.head.getSliceIndex() && sliceIndex != p.used.tail.getSliceIndex() {
// links next and prev elements for non-head and non-tail element
p.connect(prev, next.getSliceIndex())
}
if sliceIndex == p.used.head.getSliceIndex() {
// invalidating used head
// moves head forward
oldUsedHead, _ := p.getHeads()
p.used.head = oldUsedHead.node.next
// new head should point to an undefined prev,
// but we first check if list is not empty, i.e.,
// head itself is not undefined.
if !p.used.head.isUndefined() {
usedHead, _ := p.getHeads()
usedHead.node.prev.setUndefined()
}
}
if sliceIndex == p.used.tail.getSliceIndex() {
// invalidating used tail
// moves tail backward
oldUsedTail, _ := p.getTails()
p.used.tail = oldUsedTail.node.prev
// new head should point tail to an undefined next,
// but we first check if list is not empty, i.e.,
// tail itself is not undefined.
if !p.used.tail.isUndefined() {
usedTail, _ := p.getTails()
usedTail.node.next.setUndefined()
}
}
// invalidates entity and adds it to free entities.
p.poolEntities[sliceIndex].id = flow.ZeroID
p.poolEntities[sliceIndex].entity = nil
p.poolEntities[sliceIndex].node.next.setUndefined()
p.poolEntities[sliceIndex].node.prev.setUndefined()
p.appendToFreeList(sliceIndex)
// decrements Size
p.size--
}
// appendToFreeList appends linked-list node represented by getSliceIndex to tail of free list.
func (p *Pool) appendToFreeList(sliceIndex EIndex) {
if p.free.head.isUndefined() {
// free list is empty
p.free.head.setPoolIndex(sliceIndex)
p.free.tail.setPoolIndex(sliceIndex)
return
}
// appends to the tail, and updates the tail
p.connect(p.free.tail, sliceIndex)
p.free.tail.setPoolIndex(sliceIndex)
}
// isInvalidated returns true if linked-list node represented by getSliceIndex does not contain
// a valid entity.
func (p Pool) isInvalidated(sliceIndex EIndex) bool {
if p.poolEntities[sliceIndex].id != flow.ZeroID {
return false
}
if p.poolEntities[sliceIndex].entity != nil {
return false
}
return true
}