path: root/plumbing/cache/queue.go

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
}