1 files changed, 46 insertions, 0 deletions
diff --git a/cache/queue.go b/cache/queue.go
new file mode 100644
index 0000000..85413e0
--- /dev/null
+++ b/cache/queue.go
@@ -0,0 +1,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
+}