-
Notifications
You must be signed in to change notification settings - Fork 22
/
queueInt64.go
130 lines (115 loc) · 2.94 KB
/
queueInt64.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// Copyright 2020 rateLimit Author(https://github.com/yudeguang/ratelimit). All Rights Reserved.
//
// This Source Code Form is subject to the terms of the MIT License.
// If a copy of the MIT was not distributed with this file,
// You can obtain one at https://github.com/yudeguang/ratelimit.
package ratelimit
import (
"errors"
"sync"
"time"
)
/*
用环形队列做为底层数据结构来存储用户访问数据,暂时废弃,实际使用自动扩容环形队列代替
*/
//使用切片实现的队列
type circleQueueInt64 struct {
key interface{}
//注意，maxSize及visitorRecord长度都比实际存储长度大1
maxSize int
visitorRecord []int64
head int
tail int
//存盘时临时用到的虚拟队列的头和尾
headForCopy int
tailForCopy int
locker *sync.Mutex
}
//初始化环形队列
func newCircleQueueInt64(size int) *circleQueueInt64 {
var c circleQueueInt64
c.maxSize = size + 1
c.visitorRecord = make([]int64, c.maxSize)
c.locker = new(sync.Mutex)
return &c
}
//入对列
func (q *circleQueueInt64) push(val int64) (err error) {
q.locker.Lock()
defer q.locker.Unlock()
if q.isFull() {
return errors.New("queue is full")
}
q.visitorRecord[q.tail] = val
q.tail = (q.tail + 1) % q.maxSize
return
}
//出对列
func (q *circleQueueInt64) pop() (val int64, err error) {
q.locker.Lock()
defer q.locker.Unlock()
if q.isEmpty() {
return 0, errors.New("queue is empty")
}
val = q.visitorRecord[q.head]
q.head = (q.head + 1) % q.maxSize
return
}
//出对列
func (q *circleQueueInt64) popForCopy() (val int64, err error) {
q.locker.Lock()
defer q.locker.Unlock()
if q.isEmptyForCopy() {
return 0, errors.New("queue is empty")
}
val = q.visitorRecord[q.headForCopy]
q.headForCopy = (q.headForCopy + 1) % q.maxSize
return
}
//判断队列是否已满
func (q *circleQueueInt64) isFull() bool {
return (q.tail+1)%q.maxSize == q.head
}
//判断队列是否为空
func (q *circleQueueInt64) isEmpty() bool {
return q.tail == q.head
}
//判断队列是否为空
func (q *circleQueueInt64) isEmptyForCopy() bool {
return q.tailForCopy == q.headForCopy
}
//判断已使用多少个元素
func (q *circleQueueInt64) usedSizeForCopy() int {
return (q.tailForCopy + q.maxSize - q.headForCopy) % q.maxSize
}
//判断已使用多少个元素
func (q *circleQueueInt64) usedSize() int {
return (q.tail + q.maxSize - q.head) % q.maxSize
}
//判断队列中还有多少空间未使用
func (q *circleQueueInt64) unUsedSize() int {
return q.maxSize - 1 - q.usedSize()
}
//队列总的可用空间长度
func (q *circleQueueInt64) Len() int {
return q.maxSize - 1
}
//删除过期数据
func (q *circleQueueInt64) ueleteExpired(key interface{}) {
if q.key != key {
return
}
now := time.Now().UnixNano()
size := q.usedSize()
if size == 0 {
return
}
//依次删除过期数据
for i := 0; i < size; i++ {
if now > q.visitorRecord[q.head] {
q.head = (q.head + 1) % q.maxSize
} else {
return
}
}
}