/
ordered_set.go
71 lines (59 loc) · 1.43 KB
/
ordered_set.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
package common
import (
"errors"
"sync"
)
// OrderedSet is a set with limited capacity.
// Items are evicted according to their insertion order.
type OrderedSet struct {
capacity int
set map[interface{}]struct{}
queue []interface{}
start int
end int
lock sync.RWMutex
}
// NewOrderedSet creates an ordered set with given capacity
func NewOrderedSet(capacity int) (*OrderedSet, error) {
if capacity < 1 {
return nil, errors.New("capacity must be a positive integer")
}
return &OrderedSet{
capacity: capacity,
set: map[interface{}]struct{}{},
queue: make([]interface{}, capacity),
end: -1,
}, nil
}
// Add inserts items into the set.
// If capacity is reached, oldest items are evicted
func (os *OrderedSet) Add(items ...interface{}) {
os.lock.Lock()
defer os.lock.Unlock()
for _, item := range items {
if _, ok := os.set[item]; ok {
continue
}
next := (os.end + 1) % os.capacity
if os.end != -1 && next == os.start {
delete(os.set, os.queue[os.start])
os.start = (os.start + 1) % os.capacity
}
os.end = next
os.queue[os.end] = item
os.set[item] = struct{}{}
}
}
// Has checks if certain items exists in the set
func (os *OrderedSet) Has(item interface{}) bool {
os.lock.RLock()
defer os.lock.RUnlock()
_, ok := os.set[item]
return ok
}
// Size returns the size of the set
func (os *OrderedSet) Size() int {
os.lock.RLock()
defer os.lock.RUnlock()
return len(os.set)
}