Official cwtch.im peer and server implementations. https://cwtch.im
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

infinitequeue.go 3.0KB

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