-
Notifications
You must be signed in to change notification settings - Fork 0
/
arena_queue.go
184 lines (166 loc) · 4.57 KB
/
arena_queue.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
package cbytecache
import (
"unsafe"
"github.com/koykov/cbyte"
)
// Circular queue of bucket's arenas.
type arenaQueue struct {
// Head, actual and tail arenas indexes pointers.
// Manipulation of these pointers implements circular queue patterns.
head_, act_, tail_ int64
// Arenas list storage.
buf []arena
}
// Get length of arenas storage.
func (q *arenaQueue) len() int {
return len(q.buf)
}
// Get statistics of arenas (total, full and empty counts).
func (q *arenaQueue) stat() (t, f, e uint32) {
l := q.len()
if l == 0 {
return
}
_ = q.buf[l-1]
for i := 0; i < l; i++ {
t++
switch {
case q.buf[i].full():
f++
case q.buf[i].empty():
e++
}
}
return
}
// Alloc new arena.
//
// Search in buf for old arena, available to reuse (realloc) or create (alloc) new arena and it to the storage.
func (q *arenaQueue) alloc(prev *arena, cap uint32) (a *arena) {
for i := 0; i < len(q.buf); i++ {
if q.buf[i].released() {
a = &q.buf[i]
break
}
}
if a == nil {
// No arena available on buf, so create new one and add in to the buf.
a1 := arena{
id: uint32(q.len()),
qp: q.ptr(),
p: -1,
n: -1,
}
q.buf = append(q.buf, a1)
a = &q.buf[q.len()-1]
}
// Alloc memory.
a.h = cbyte.InitHeader(0, int(cap))
// Link prev/new arena.
a.setPrev(prev)
if prev != nil {
prev.setNext(a)
}
// Mark new arena as tail.
q.setTail(a)
return
}
// Set head arena.
func (q *arenaQueue) setHead(a *arena) *arenaQueue {
q.head_ = -1
if a != nil {
q.head_ = int64(a.id)
}
return q
}
// Set actual arena.
func (q *arenaQueue) setAct(a *arena) *arenaQueue {
q.act_ = -1
if a != nil {
q.act_ = int64(a.id)
}
return q
}
// Set tail arena.
func (q *arenaQueue) setTail(a *arena) *arenaQueue {
q.tail_ = -1
if a != nil {
q.tail_ = int64(a.id)
}
return q
}
// Get head arena.
func (q *arenaQueue) head() *arena {
return q.get(q.head_)
}
// Get actual arena.
func (q *arenaQueue) act() *arena {
return q.get(q.act_)
}
// Get tail arena.
func (q *arenaQueue) tail() *arena {
return q.get(q.tail_)
}
func (q *arenaQueue) get(id int64) *arena {
if id == -1 {
return nil
}
if id >= int64(len(q.buf)) {
return nil
}
return &q.buf[id]
}
// Recycle arenas using lo as starting arena.
//
// After recycle arenas contains unexpired entries will shift to the head, all other arenas will shift to the end.
func (q *arenaQueue) recycle(lo *arena) {
if lo == nil {
return
}
// Old arena sequence:
// ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
// │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
// └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
// ▲ ▲ ▲ ▲
// │ │ │ │
// head │ │ │
// low ────┘ │ │
// actual ─────────────┘ │
// tail ───────────────────────────────┘
// low is a last arena contains only expired entries.
oh, ot := q.head(), q.tail()
// Set low+1 as head since it contains at least one unexpired entry.
q.setHead(lo.next())
q.head().setPrev(nil)
// low became new tail.
q.setTail(lo)
// Old head previous arena became old tail.
oh.setPrev(ot)
// Old tail next arena became old head.
ot.setNext(oh)
q.tail().setNext(nil)
// New sequence:
// ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
// │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 0 │ 1 │ 2 │
// └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
// ▲ ▲ ▲
// │ │ │
// head │ │
// actual ─┘ │
// tail ───────────────────────────────┘
// Arena #3 contains at least one unexpired entry, so it became new head.
// Arena #2 became new tail.
//
// Arenas schema:
// * [6..9] - potentially empty, but they will reset anyway
// * [0..2] - contains expired entries, so empty them
//
// Recycle end.
}
// Get raw unsafe pointer of arena list.
//
// Caution! Pointer receiver strongly required here.
func (q *arenaQueue) ptr() uintptr {
uptr := unsafe.Pointer(q)
return uintptr(uptr)
}