-
Notifications
You must be signed in to change notification settings - Fork 7
/
ringqueue.go
62 lines (52 loc) · 1.12 KB
/
ringqueue.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
package rinqueue
type Ringqueue struct {
nodes []interface{}
head int
tail int
cnt int
}
func NewRingqueue() *Ringqueue {
return &Ringqueue{
nodes: make([]interface{}, 2),
}
}
func (q *Ringqueue) resize(n int) {
nodes := make([]interface{}, n)
if q.head < q.tail {
copy(nodes, q.nodes[q.head:q.tail])
} else {
copy(nodes, q.nodes[q.head:])
copy(nodes[len(q.nodes)-q.head:], q.nodes[:q.tail])
}
q.tail = q.cnt % n
q.head = 0
q.nodes = nodes
}
func (q *Ringqueue) Add(i interface{}) {
if q.cnt == len(q.nodes) {
// Also tested a grow rate of 1.5, see: http://stackoverflow.com/questions/2269063/buffer-growth-strategy
// In Go this resulted in a higher memory usage.
q.resize(q.cnt * 2)
}
q.nodes[q.tail] = i
q.tail = (q.tail + 1) % len(q.nodes)
q.cnt++
}
func (q *Ringqueue) Remove() (interface{}, bool) {
if q.cnt == 0 {
return 0, false
}
i := q.nodes[q.head]
q.head = (q.head + 1) % len(q.nodes)
q.cnt--
if n := len(q.nodes) / 2; n > 2 && q.cnt <= n {
q.resize(n)
}
return i, true
}
func (q *Ringqueue) Cap() int {
return cap(q.nodes)
}
func (q *Ringqueue) Len() int {
return q.cnt
}