Takahiro Suzuki | d7bf820 | 2020-12-17 20:21:59 +0900 | [diff] [blame] | 1 | /* |
| 2 | Package queue provides a fast, ring-buffer queue based on the version suggested by Dariusz Górecki. |
| 3 | Using this instead of other, simpler, queue implementations (slice+append or linked list) provides |
| 4 | substantial memory and time benefits, and fewer GC pauses. |
| 5 | |
| 6 | The queue implemented here is as fast as it is for an additional reason: it is *not* thread-safe. |
| 7 | */ |
| 8 | package 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). |
| 12 | const minQueueLen = 16 |
| 13 | |
| 14 | // Queue represents a single instance of the queue data structure. |
| 15 | type Queue struct { |
| 16 | buf []interface{} |
| 17 | head, tail, count int |
| 18 | } |
| 19 | |
| 20 | // New constructs and returns a new Queue. |
| 21 | func 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. |
| 28 | func (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 |
| 34 | func (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. |
| 50 | func (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. |
| 63 | func (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. |
| 74 | func (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. |
| 88 | func (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 | } |