-
Notifications
You must be signed in to change notification settings - Fork 0
/
zlist.go
171 lines (153 loc) · 3.39 KB
/
zlist.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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
package ds
import (
"fmt"
"github.com/qizong007/ware-kv/warekv/util"
"sync"
"unsafe"
)
// ZList sorted-list
type ZList struct {
Base
skipList *util.SkipList
rw sync.RWMutex
}
var zListStructMemUsage int
func init() {
zListStructMemUsage = int(unsafe.Sizeof(ZList{}))
}
type ZElement struct {
Val interface{}
Score float64
}
func (zl *ZList) GetValue() interface{} {
zl.rw.RLock()
defer zl.rw.RUnlock()
val := zl.skipList.GetList()
return val
}
func (zl *ZList) Size() int {
size := zListStructMemUsage
if zl.ExpireTime != nil {
size += 8
}
zl.rw.RLock()
defer zl.rw.RUnlock()
if rSize := util.GetRealSizeOf(zl.skipList); rSize > 0 {
size += rSize
}
return size
}
func MakeZList(list []util.SlElement) *ZList {
sl := util.NewSkipList()
for i := range list {
sl.Insert(list[i].Score, list[i].Val)
}
return &ZList{
Base: *NewBase(util.ZListDS),
skipList: sl,
}
}
// GetListBetween Left-Close and Right-Open
func (zl *ZList) GetListBetween(left int, right int) ([]util.SlElement, error) {
zl.rw.RLock()
defer zl.rw.RUnlock()
zlLen := zl.GetLen()
if left < 0 || left >= zlLen || right < 0 {
return nil, fmt.Errorf("array out of bounds")
}
if left >= right {
return nil, fmt.Errorf("left should not be larger than(or equal to) right")
}
if right >= zlLen {
right = zlLen
}
list := zl.skipList.GetList()
return list[left:right], nil
}
func (zl *ZList) GetListStartWith(left int) ([]util.SlElement, error) {
zl.rw.RLock()
defer zl.rw.RUnlock()
zlLen := zl.GetLen()
if left < 0 || left >= zlLen {
return nil, fmt.Errorf("array out of bounds")
}
list := zl.skipList.GetList()
return list[left:], nil
}
func (zl *ZList) GetListEndAt(right int) ([]util.SlElement, error) {
zl.rw.RLock()
defer zl.rw.RUnlock()
zlLen := zl.GetLen()
if right < 0 || right >= zlLen {
return nil, fmt.Errorf("array out of bounds")
}
list := zl.skipList.GetList()
return list[:right+1], nil
}
func (zl *ZList) GetElementAt(pos int) (*util.SlElement, error) {
zl.rw.RLock()
defer zl.rw.RUnlock()
if pos < 0 || pos >= zl.GetLen() {
return nil, fmt.Errorf("pos out of bounds")
}
list := zl.skipList.GetList()
return &list[pos], nil
}
func (zl *ZList) GetListInScore(min float64, max float64) ([]util.SlElement, error) {
zl.rw.RLock()
defer zl.rw.RUnlock()
if min > max {
return nil, fmt.Errorf("min should not be larger than max")
}
list := zl.skipList.GetList()
res := make([]util.SlElement, 0)
for i := range list {
if list[i].Score > max {
break
}
if list[i].Score >= min && list[i].Score <= max {
res = append(res, list[i])
}
}
return res, nil
}
func (zl *ZList) Add(list []util.SlElement) {
zl.rw.Lock()
defer zl.rw.Unlock()
zl.Update()
for i := range list {
zl.skipList.Insert(list[i].Score, list[i].Val)
}
}
func (zl *ZList) RemoveScore(score float64) {
zl.rw.Lock()
defer zl.rw.Unlock()
zl.Update()
zl.skipList.Delete(score)
}
func (zl *ZList) RemoveScores(scores []float64) {
zl.rw.Lock()
defer zl.rw.Unlock()
zl.Update()
for i := range scores {
zl.skipList.Delete(scores[i])
}
}
func (zl *ZList) RemoveInScore(min float64, max float64) error {
list, err := zl.GetListInScore(min, max)
if err != nil {
return err
}
zl.rw.Lock()
defer zl.rw.Unlock()
zl.Update()
for i := range list {
zl.skipList.Delete(list[i].Score)
}
return nil
}
func (zl *ZList) GetLen() int {
zl.rw.RLock()
defer zl.rw.RUnlock()
return zl.skipList.Len()
}