package cache import "srcd.works/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 }