Codebase list golang-gopkg-eapache-queue.v1 / 335bf39b-508e-42a7-aaf2-5f40ff01a7e9/main
New upstream snapshot. Debian Janitor 2 years ago
4 changed file(s) with 48 addition(s) and 12 deletion(s). Raw diff Collapse all Expand all
11 =====
22
33 [![Build Status](https://travis-ci.org/eapache/queue.svg)](https://travis-ci.org/eapache/queue)
4 [![GoDoc](https://godoc.org/github.com/eapache/queue?status.png)](https://godoc.org/github.com/eapache/queue)
4 [![GoDoc](https://godoc.org/github.com/eapache/queue?status.svg)](https://godoc.org/github.com/eapache/queue)
55 [![Code of Conduct](https://img.shields.io/badge/code%20of%20conduct-active-blue.svg)](https://eapache.github.io/conduct.html)
66
77 A fast Golang queue using a ring-buffer, based on the version suggested by Dariusz Górecki.
0 golang-gopkg-eapache-queue.v1 (1.1.0+git20180227.1.093482f-1) UNRELEASED; urgency=low
1
2 * New upstream snapshot.
3
4 -- Debian Janitor <janitor@jelmer.uk> Thu, 03 Jun 2021 18:49:44 -0000
5
06 golang-gopkg-eapache-queue.v1 (1.0.2-5) unstable; urgency=medium
17
28 [ Alexandre Viau ]
66 */
77 package queue
88
9 // minQueueLen is smallest capacity that queue may have.
10 // Must be power of 2 for bitwise modulus: x % n == x & (n - 1).
911 const minQueueLen = 16
1012
1113 // Queue represents a single instance of the queue data structure.
2931 // resizes the queue to fit exactly twice its current contents
3032 // this can result in shrinking if the queue is less than half-full
3133 func (q *Queue) resize() {
32 newBuf := make([]interface{}, q.count*2)
34 newBuf := make([]interface{}, q.count<<1)
3335
3436 if q.tail > q.head {
3537 copy(newBuf, q.buf[q.head:q.tail])
5052 }
5153
5254 q.buf[q.tail] = elem
53 q.tail = (q.tail + 1) % len(q.buf)
55 // bitwise modulus
56 q.tail = (q.tail + 1) & (len(q.buf) - 1)
5457 q.count++
5558 }
5659
6467 }
6568
6669 // Get returns the element at index i in the queue. If the index is
67 // invalid, the call will panic.
70 // invalid, the call will panic. This method accepts both positive and
71 // negative index values. Index 0 refers to the first element, and
72 // index -1 refers to the last.
6873 func (q *Queue) Get(i int) interface{} {
74 // If indexing backwards, convert to positive index.
75 if i < 0 {
76 i += q.count
77 }
6978 if i < 0 || i >= q.count {
7079 panic("queue: Get() called with index out of range")
7180 }
72 return q.buf[(q.head+i)%len(q.buf)]
81 // bitwise modulus
82 return q.buf[(q.head+i)&(len(q.buf)-1)]
7383 }
7484
75 // Remove removes the element from the front of the queue. If you actually
76 // want the element, call Peek first. This call panics if the queue is empty.
77 func (q *Queue) Remove() {
85 // Remove removes and returns the element from the front of the queue. If the
86 // queue is empty, the call will panic.
87 func (q *Queue) Remove() interface{} {
7888 if q.count <= 0 {
7989 panic("queue: Remove() called on empty queue")
8090 }
91 ret := q.buf[q.head]
8192 q.buf[q.head] = nil
82 q.head = (q.head + 1) % len(q.buf)
93 // bitwise modulus
94 q.head = (q.head + 1) & (len(q.buf) - 1)
8395 q.count--
84 if len(q.buf) > minQueueLen && q.count*4 == len(q.buf) {
96 // Resize down if buffer 1/4 full.
97 if len(q.buf) > minQueueLen && (q.count<<2) == len(q.buf) {
8598 q.resize()
8699 }
100 return ret
87101 }
1111 if q.Peek().(int) != i {
1212 t.Error("peek", i, "had value", q.Peek())
1313 }
14 q.Remove()
14 x := q.Remove()
15 if x != i {
16 t.Error("remove", i, "had value", x)
17 }
1518 }
1619 }
1720
6871 }
6972 }
7073
74 func TestQueueGetNegative(t *testing.T) {
75 q := New()
76
77 for i := 0; i < 1000; i++ {
78 q.Add(i)
79 for j := 1; j <= q.Length(); j++ {
80 if q.Get(-j).(int) != q.Length()-j {
81 t.Errorf("index %d doesn't contain %d", -j, q.Length()-j)
82 }
83 }
84 }
85 }
86
7187 func TestQueueGetOutOfRangePanics(t *testing.T) {
7288 q := New()
7389
7692 q.Add(3)
7793
7894 assertPanics(t, "should panic when negative index", func() {
79 q.Get(-1)
95 q.Get(-4)
8096 })
8197
8298 assertPanics(t, "should panic when index greater than length", func() {