blob: 71d1acdf27b2f909ca1ca910484ef8c8f512b972 [file] [log] [blame]
Takahiro Suzuki241c10e2020-12-17 20:17:57 +09001/*
2Package queue provides a fast, ring-buffer queue based on the version suggested by Dariusz Górecki.
3Using this instead of other, simpler, queue implementations (slice+append or linked list) provides
4substantial memory and time benefits, and fewer GC pauses.
5
6The queue implemented here is as fast as it is for an additional reason: it is *not* thread-safe.
7*/
8package queue
9
10// minQueueLen is smallest capacity that queue may have.
11// Must be power of 2 for bitwise modulus: x % n == x & (n - 1).
12const minQueueLen = 16
13
14// Queue represents a single instance of the queue data structure.
15type Queue struct {
16 buf []interface{}
17 head, tail, count int
18}
19
20// New constructs and returns a new Queue.
21func New() *Queue {
22 return &Queue{
23 buf: make([]interface{}, minQueueLen),
24 }
25}
26
27// Length returns the number of elements currently stored in the queue.
28func (q *Queue) Length() int {
29 return q.count
30}
31
32// resizes the queue to fit exactly twice its current contents
33// this can result in shrinking if the queue is less than half-full
34func (q *Queue) resize() {
35 newBuf := make([]interface{}, q.count<<1)
36
37 if q.tail > q.head {
38 copy(newBuf, q.buf[q.head:q.tail])
39 } else {
40 n := copy(newBuf, q.buf[q.head:])
41 copy(newBuf[n:], q.buf[:q.tail])
42 }
43
44 q.head = 0
45 q.tail = q.count
46 q.buf = newBuf
47}
48
49// Add puts an element on the end of the queue.
50func (q *Queue) Add(elem interface{}) {
51 if q.count == len(q.buf) {
52 q.resize()
53 }
54
55 q.buf[q.tail] = elem
56 // bitwise modulus
57 q.tail = (q.tail + 1) & (len(q.buf) - 1)
58 q.count++
59}
60
61// Peek returns the element at the head of the queue. This call panics
62// if the queue is empty.
63func (q *Queue) Peek() interface{} {
64 if q.count <= 0 {
65 panic("queue: Peek() called on empty queue")
66 }
67 return q.buf[q.head]
68}
69
70// Get returns the element at index i in the queue. If the index is
71// invalid, the call will panic. This method accepts both positive and
72// negative index values. Index 0 refers to the first element, and
73// index -1 refers to the last.
74func (q *Queue) Get(i int) interface{} {
75 // If indexing backwards, convert to positive index.
76 if i < 0 {
77 i += q.count
78 }
79 if i < 0 || i >= q.count {
80 panic("queue: Get() called with index out of range")
81 }
82 // bitwise modulus
83 return q.buf[(q.head+i)&(len(q.buf)-1)]
84}
85
86// Remove removes and returns the element from the front of the queue. If the
87// queue is empty, the call will panic.
88func (q *Queue) Remove() interface{} {
89 if q.count <= 0 {
90 panic("queue: Remove() called on empty queue")
91 }
92 ret := q.buf[q.head]
93 q.buf[q.head] = nil
94 // bitwise modulus
95 q.head = (q.head + 1) & (len(q.buf) - 1)
96 q.count--
97 // Resize down if buffer 1/4 full.
98 if len(q.buf) > minQueueLen && (q.count<<2) == len(q.buf) {
99 q.resize()
100 }
101 return ret
102}