blob: e7a3cdc9ab6d6c04ed4ba215e383eee840d7366c [file] [log] [blame]
William Kurkianea869482019-04-09 15:16:11 -04001// 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 types
16
17import (
18 "reflect"
19 "sort"
20 "sync"
21)
22
23type Set interface {
24 Add(string)
25 Remove(string)
26 Contains(string) bool
27 Equals(Set) bool
28 Length() int
29 Values() []string
30 Copy() Set
31 Sub(Set) Set
32}
33
34func NewUnsafeSet(values ...string) *unsafeSet {
35 set := &unsafeSet{make(map[string]struct{})}
36 for _, v := range values {
37 set.Add(v)
38 }
39 return set
40}
41
42func NewThreadsafeSet(values ...string) *tsafeSet {
43 us := NewUnsafeSet(values...)
44 return &tsafeSet{us, sync.RWMutex{}}
45}
46
47type unsafeSet struct {
48 d map[string]struct{}
49}
50
51// Add adds a new value to the set (no-op if the value is already present)
52func (us *unsafeSet) Add(value string) {
53 us.d[value] = struct{}{}
54}
55
56// Remove removes the given value from the set
57func (us *unsafeSet) Remove(value string) {
58 delete(us.d, value)
59}
60
61// Contains returns whether the set contains the given value
62func (us *unsafeSet) Contains(value string) (exists bool) {
63 _, exists = us.d[value]
64 return exists
65}
66
67// ContainsAll returns whether the set contains all given values
68func (us *unsafeSet) ContainsAll(values []string) bool {
69 for _, s := range values {
70 if !us.Contains(s) {
71 return false
72 }
73 }
74 return true
75}
76
77// Equals returns whether the contents of two sets are identical
78func (us *unsafeSet) Equals(other Set) bool {
79 v1 := sort.StringSlice(us.Values())
80 v2 := sort.StringSlice(other.Values())
81 v1.Sort()
82 v2.Sort()
83 return reflect.DeepEqual(v1, v2)
84}
85
86// Length returns the number of elements in the set
87func (us *unsafeSet) Length() int {
88 return len(us.d)
89}
90
91// Values returns the values of the Set in an unspecified order.
92func (us *unsafeSet) Values() (values []string) {
93 values = make([]string, 0)
94 for val := range us.d {
95 values = append(values, val)
96 }
97 return values
98}
99
100// Copy creates a new Set containing the values of the first
101func (us *unsafeSet) Copy() Set {
102 cp := NewUnsafeSet()
103 for val := range us.d {
104 cp.Add(val)
105 }
106
107 return cp
108}
109
110// Sub removes all elements in other from the set
111func (us *unsafeSet) Sub(other Set) Set {
112 oValues := other.Values()
113 result := us.Copy().(*unsafeSet)
114
115 for _, val := range oValues {
116 if _, ok := result.d[val]; !ok {
117 continue
118 }
119 delete(result.d, val)
120 }
121
122 return result
123}
124
125type tsafeSet struct {
126 us *unsafeSet
127 m sync.RWMutex
128}
129
130func (ts *tsafeSet) Add(value string) {
131 ts.m.Lock()
132 defer ts.m.Unlock()
133 ts.us.Add(value)
134}
135
136func (ts *tsafeSet) Remove(value string) {
137 ts.m.Lock()
138 defer ts.m.Unlock()
139 ts.us.Remove(value)
140}
141
142func (ts *tsafeSet) Contains(value string) (exists bool) {
143 ts.m.RLock()
144 defer ts.m.RUnlock()
145 return ts.us.Contains(value)
146}
147
148func (ts *tsafeSet) Equals(other Set) bool {
149 ts.m.RLock()
150 defer ts.m.RUnlock()
David Bainbridge788e5202019-10-21 18:49:40 +0000151
152 // If ts and other represent the same variable, avoid calling
153 // ts.us.Equals(other), to avoid double RLock bug
154 if _other, ok := other.(*tsafeSet); ok {
155 if _other == ts {
156 return true
157 }
158 }
William Kurkianea869482019-04-09 15:16:11 -0400159 return ts.us.Equals(other)
160}
161
162func (ts *tsafeSet) Length() int {
163 ts.m.RLock()
164 defer ts.m.RUnlock()
165 return ts.us.Length()
166}
167
168func (ts *tsafeSet) Values() (values []string) {
169 ts.m.RLock()
170 defer ts.m.RUnlock()
171 return ts.us.Values()
172}
173
174func (ts *tsafeSet) Copy() Set {
175 ts.m.RLock()
176 defer ts.m.RUnlock()
177 usResult := ts.us.Copy().(*unsafeSet)
178 return &tsafeSet{usResult, sync.RWMutex{}}
179}
180
181func (ts *tsafeSet) Sub(other Set) Set {
182 ts.m.RLock()
183 defer ts.m.RUnlock()
David Bainbridge788e5202019-10-21 18:49:40 +0000184
185 // If ts and other represent the same variable, avoid calling
186 // ts.us.Sub(other), to avoid double RLock bug
187 if _other, ok := other.(*tsafeSet); ok {
188 if _other == ts {
189 usResult := NewUnsafeSet()
190 return &tsafeSet{usResult, sync.RWMutex{}}
191 }
192 }
William Kurkianea869482019-04-09 15:16:11 -0400193 usResult := ts.us.Sub(other).(*unsafeSet)
194 return &tsafeSet{usResult, sync.RWMutex{}}
195}