forked from cwtch.im/cwtch
1
0
Fork 0
cwtch/event/infinitequeue.go

109 lines
3.0 KiB
Go

package event
/*
This package is taken from https://github.com/eapache/channels
as per their suggestion we are not importing the entire package and instead cherry picking and adapting what is needed
It is covered by the MIT License https://github.com/eapache/channels/blob/master/LICENSE
*/
/*
Package queue provides a fast, ring-buffer queue based on the version suggested by Dariusz Górecki.
Using this instead of other, simpler, queue implementations (slice+append or linked list) provides
substantial memory and time benefits, and fewer GC pauses.
The queue implemented here is as fast as it is for an additional reason: it is *not* thread-safe.
*/
// minQueueLen is smallest capacity that queue may have.
// Must be power of 2 for bitwise modulus: x % n == x & (n - 1).
const minQueueLen = 16
// Queue represents a single instance of the queue data structure.
type infiniteQueue struct {
buf []Event
head, tail, count int
}
// New constructs and returns a new Queue.
func newInfinitQueue() *infiniteQueue {
return &infiniteQueue{
buf: make([]Event, minQueueLen),
}
}
// Length returns the number of elements currently stored in the queue.
func (q *infiniteQueue) Length() int {
return q.count
}
// resizes the queue to fit exactly twice its current contents
// this can result in shrinking if the queue is less than half-full
func (q *infiniteQueue) resize() {
newBuf := make([]Event, q.count<<1)
if q.tail > q.head {
copy(newBuf, q.buf[q.head:q.tail])
} else {
n := copy(newBuf, q.buf[q.head:])
copy(newBuf[n:], q.buf[:q.tail])
}
q.head = 0
q.tail = q.count
q.buf = newBuf
}
// Add puts an element on the end of the queue.
func (q *infiniteQueue) Add(elem Event) {
if q.count == len(q.buf) {
q.resize()
}
q.buf[q.tail] = elem
// bitwise modulus
q.tail = (q.tail + 1) & (len(q.buf) - 1)
q.count++
}
// Peek returns the element at the head of the queue. This call panics
// if the queue is empty.
func (q *infiniteQueue) Peek() Event {
if q.count <= 0 {
panic("queue: Peek() called on empty queue")
}
return q.buf[q.head]
}
// Get returns the element at index i in the queue. If the index is
// invalid, the call will panic. This method accepts both positive and
// negative index values. Index 0 refers to the first element, and
// index -1 refers to the last.
func (q *infiniteQueue) Get(i int) Event {
// If indexing backwards, convert to positive index.
if i < 0 {
i += q.count
}
if i < 0 || i >= q.count {
panic("queue: Get() called with index out of range")
}
// bitwise modulus
return q.buf[(q.head+i)&(len(q.buf)-1)]
}
// Remove removes and returns the element from the front of the queue. If the
// queue is empty, the call will panic.
func (q *infiniteQueue) Remove() Event {
if q.count <= 0 {
panic("queue: Remove() called on empty queue")
}
ret := q.buf[q.head]
//q.buf[q.head] = nil
// bitwise modulus
q.head = (q.head + 1) & (len(q.buf) - 1)
q.count--
// Resize down if buffer 1/4 full.
if len(q.buf) > minQueueLen && (q.count<<2) == len(q.buf) {
q.resize()
}
return ret
}