1 files changed, 71 insertions, 0 deletions
diff --git a/vendor/github.com/ReneKroon/ttlcache/priority_queue.go b/vendor/github.com/ReneKroon/ttlcache/priority_queue.go
new file mode 100644
index 000000000..11b9c3140
--- /dev/null
+++ b/vendor/github.com/ReneKroon/ttlcache/priority_queue.go
@@ -0,0 +1,71 @@
+package ttlcache
+
+import (
+	"container/heap"
+)
+
+func newPriorityQueue() *priorityQueue {
+	queue := &priorityQueue{}
+	heap.Init(queue)
+	return queue
+}
+
+type priorityQueue struct {
+	items []*item
+}
+
+func (pq *priorityQueue) update(item *item) {
+	heap.Fix(pq, item.queueIndex)
+}
+
+func (pq *priorityQueue) push(item *item) {
+	heap.Push(pq, item)
+}
+
+func (pq *priorityQueue) pop() *item {
+	if pq.Len() == 0 {
+		return nil
+	}
+	return heap.Pop(pq).(*item)
+}
+
+func (pq *priorityQueue) remove(item *item) {
+	heap.Remove(pq, item.queueIndex)
+}
+
+func (pq priorityQueue) Len() int {
+	length := len(pq.items)
+	return length
+}
+
+// Less will consider items with time.Time default value (epoch start) as more than set items.
+func (pq priorityQueue) Less(i, j int) bool {
+	if pq.items[i].expireAt.IsZero() {
+		return false
+	}
+	if pq.items[j].expireAt.IsZero() {
+		return true
+	}
+	return pq.items[i].expireAt.Before(pq.items[j].expireAt)
+}
+
+func (pq priorityQueue) Swap(i, j int) {
+	pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
+	pq.items[i].queueIndex = i
+	pq.items[j].queueIndex = j
+}
+
+func (pq *priorityQueue) Push(x interface{}) {
+	item := x.(*item)
+	item.queueIndex = len(pq.items)
+	pq.items = append(pq.items, item)
+}
+
+func (pq *priorityQueue) Pop() interface{} {
+	old := pq.items
+	n := len(old)
+	item := old[n-1]
+	item.queueIndex = -1
+	pq.items = old[0 : n-1]
+	return item
+}