queue

README

介绍

队列库，提供优先队列，延迟队列基础操作

功能

• priority_queue: 优先队列，基于container/heap实现，采用min heap结构，提供Push，Pop, Top, PeekAndShift, Update 等操作函数接口
• delay_queue: 延迟队列, 基于优先队列，提供Offer, Poll, Do 操作函数，Offer（添加 bucket）和 Poll（获取并删除 bucket）的运作方式，

tips

heap 使用场景：最小顶堆，最大顶堆；优先级队列；有序小文件合并成大文件；定时任务； golang timer采用最小顶堆实现；

Documentation

Overview

from: https://github.com/RussellLuo/timingwheel/blob/master/delayqueue/delayqueue.go

Index

• type DelayQueue
  • func NewDelayQueue(size int) *DelayQueue
  • func (dq *DelayQueue) Do(exitC chan struct{}, do func(interface{}))
  • func (dq *DelayQueue) Offer(elem interface{}, expiration int64)
  • func (dq *DelayQueue) Poll(exitC chan struct{}, nowF func() int64)
• type Item
• type PriorityQueue
  • func NewPriorityQueue(capacity int) PriorityQueue
  • func (pq PriorityQueue) Len() int
  • func (pq PriorityQueue) Less(i, j int) bool
  • func (pq *PriorityQueue) PeekAndShift(max int64) (*Item, int64)
  • func (pq *PriorityQueue) Pop() interface{}
  • func (pq *PriorityQueue) Push(x interface{})
  • func (pq PriorityQueue) Swap(i, j int)
  • func (pq *PriorityQueue) Top() (top *Item)
  • func (pq *PriorityQueue) Update(item *Item, value interface{}, priority int64)

Types

type DelayQueue

type DelayQueue struct {
	C chan interface{}
	// contains filtered or unexported fields
}

DelayQueue is an unbounded blocking queue of *Delayed* elements, in which an element can only be taken when its delay has expired. The head of the queue is the *Delayed* element whose delay expired furthest in the past.

func NewDelayQueue

func NewDelayQueue(size int) *DelayQueue

New creates an instance of delayQueue with the specified size.

func (*DelayQueue) Do

func (dq *DelayQueue) Do(exitC chan struct{}, do func(interface{}))

from delay queue ch get elem to do

func (*DelayQueue) Offer

func (dq *DelayQueue) Offer(elem interface{}, expiration int64)

Offer inserts the element into the current queue.

func (*DelayQueue) Poll

func (dq *DelayQueue) Poll(exitC chan struct{}, nowF func() int64)

Poll starts an infinite loop, in which it continually waits for an element to expire and then send the expired element to the channel C.

type Item

type Item struct {
	Value    interface{}
	Priority int64
	Index    int
}

type PriorityQueue

type PriorityQueue []*Item

this is a priority queue as implemented by a min heap ie. the 0th element is the *lowest* value

func NewPriorityQueue

func NewPriorityQueue(capacity int) PriorityQueue

func (PriorityQueue) Len

func (pq PriorityQueue) Len() int

func (PriorityQueue) Less

func (pq PriorityQueue) Less(i, j int) bool

min heap

func (*PriorityQueue) PeekAndShift

func (pq *PriorityQueue) PeekAndShift(max int64) (*Item, int64)

func (*PriorityQueue) Pop

func (pq *PriorityQueue) Pop() interface{}

heap pop interface impl

func (*PriorityQueue) Push

func (pq *PriorityQueue) Push(x interface{})

heap push interface impl

func (PriorityQueue) Swap

func (pq PriorityQueue) Swap(i, j int)

func (*PriorityQueue) Top

func (pq *PriorityQueue) Top() (top *Item)

func (*PriorityQueue) Update

func (pq *PriorityQueue) Update(item *Item, value interface{}, priority int64)

update item priority