1// Copyright 2015 The etcd Authors 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package store 16 17import ( 18 "container/heap" 19) 20 21// An TTLKeyHeap is a min-heap of TTLKeys order by expiration time 22type ttlKeyHeap struct { 23 array []*node 24 keyMap map[*node]int 25} 26 27func newTtlKeyHeap() *ttlKeyHeap { 28 h := &ttlKeyHeap{keyMap: make(map[*node]int)} 29 heap.Init(h) 30 return h 31} 32 33func (h ttlKeyHeap) Len() int { 34 return len(h.array) 35} 36 37func (h ttlKeyHeap) Less(i, j int) bool { 38 return h.array[i].ExpireTime.Before(h.array[j].ExpireTime) 39} 40 41func (h ttlKeyHeap) Swap(i, j int) { 42 // swap node 43 h.array[i], h.array[j] = h.array[j], h.array[i] 44 45 // update map 46 h.keyMap[h.array[i]] = i 47 h.keyMap[h.array[j]] = j 48} 49 50func (h *ttlKeyHeap) Push(x interface{}) { 51 n, _ := x.(*node) 52 h.keyMap[n] = len(h.array) 53 h.array = append(h.array, n) 54} 55 56func (h *ttlKeyHeap) Pop() interface{} { 57 old := h.array 58 n := len(old) 59 x := old[n-1] 60 // Set slice element to nil, so GC can recycle the node. 61 // This is due to golang GC doesn't support partial recycling: 62 // https://github.com/golang/go/issues/9618 63 old[n-1] = nil 64 h.array = old[0 : n-1] 65 delete(h.keyMap, x) 66 return x 67} 68 69func (h *ttlKeyHeap) top() *node { 70 if h.Len() != 0 { 71 return h.array[0] 72 } 73 return nil 74} 75 76func (h *ttlKeyHeap) pop() *node { 77 x := heap.Pop(h) 78 n, _ := x.(*node) 79 return n 80} 81 82func (h *ttlKeyHeap) push(x interface{}) { 83 heap.Push(h, x) 84} 85 86func (h *ttlKeyHeap) update(n *node) { 87 index, ok := h.keyMap[n] 88 if ok { 89 heap.Remove(h, index) 90 heap.Push(h, n) 91 } 92} 93 94func (h *ttlKeyHeap) remove(n *node) { 95 index, ok := h.keyMap[n] 96 if ok { 97 heap.Remove(h, index) 98 } 99} 100