blob: 85413e0b7a9433cc3c3aebc676ba82ed9e872a67 (
plain) (
blame)
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
|
package cache
import "gopkg.in/src-d/go-git.v4/plumbing"
// queue is a basic FIFO queue based on a circular list that resize as needed.
type queue struct {
elements []plumbing.Hash
size int
head int
tail int
count int
}
// newQueue returns a queue with the specified initial size
func newQueue(size int) *queue {
return &queue{
elements: make([]plumbing.Hash, size),
size: size,
}
}
// Push adds a node to the queue.
func (q *queue) Push(h plumbing.Hash) {
if q.head == q.tail && q.count > 0 {
elements := make([]plumbing.Hash, len(q.elements)+q.size)
copy(elements, q.elements[q.head:])
copy(elements[len(q.elements)-q.head:], q.elements[:q.head])
q.head = 0
q.tail = len(q.elements)
q.elements = elements
}
q.elements[q.tail] = h
q.tail = (q.tail + 1) % len(q.elements)
q.count++
}
// Pop removes and returns a Hash from the queue in first to last order.
func (q *queue) Pop() plumbing.Hash {
if q.count == 0 {
return plumbing.ZeroHash
}
node := q.elements[q.head]
q.head = (q.head + 1) % len(q.elements)
q.count--
return node
}
|
