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 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() 151 return ts.us.Equals(other) 152} 153 154func (ts *tsafeSet) Length() int { 155 ts.m.RLock() 156 defer ts.m.RUnlock() 157 return ts.us.Length() 158} 159 160func (ts *tsafeSet) Values() (values []string) { 161 ts.m.RLock() 162 defer ts.m.RUnlock() 163 return ts.us.Values() 164} 165 166func (ts *tsafeSet) Copy() Set { 167 ts.m.RLock() 168 defer ts.m.RUnlock() 169 usResult := ts.us.Copy().(*unsafeSet) 170 return &tsafeSet{usResult, sync.RWMutex{}} 171} 172 173func (ts *tsafeSet) Sub(other Set) Set { 174 ts.m.RLock() 175 defer ts.m.RUnlock() 176 usResult := ts.us.Sub(other).(*unsafeSet) 177 return &tsafeSet{usResult, sync.RWMutex{}} 178} 179