1/* 2Copyright 2019 The Kubernetes Authors. 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15*/ 16 17package value 18 19import ( 20 "sort" 21) 22 23// Map represents a Map or go structure. 24type Map interface { 25 // Set changes or set the value of the given key. 26 Set(key string, val Value) 27 // Get returns the value for the given key, if present, or (nil, false) otherwise. 28 Get(key string) (Value, bool) 29 // GetUsing uses the provided allocator and returns the value for the given key, 30 // if present, or (nil, false) otherwise. 31 // The returned Value should be given back to the Allocator when no longer needed 32 // by calling Allocator.Free(Value). 33 GetUsing(a Allocator, key string) (Value, bool) 34 // Has returns true if the key is present, or false otherwise. 35 Has(key string) bool 36 // Delete removes the key from the map. 37 Delete(key string) 38 // Equals compares the two maps, and return true if they are the same, false otherwise. 39 // Implementations can use MapEquals as a general implementation for this methods. 40 Equals(other Map) bool 41 // EqualsUsing uses the provided allocator and compares the two maps, and return true if 42 // they are the same, false otherwise. Implementations can use MapEqualsUsing as a general 43 // implementation for this methods. 44 EqualsUsing(a Allocator, other Map) bool 45 // Iterate runs the given function for each key/value in the 46 // map. Returning false in the closure prematurely stops the 47 // iteration. 48 Iterate(func(key string, value Value) bool) bool 49 // IterateUsing uses the provided allocator and runs the given function for each key/value 50 // in the map. Returning false in the closure prematurely stops the iteration. 51 IterateUsing(Allocator, func(key string, value Value) bool) bool 52 // Length returns the number of items in the map. 53 Length() int 54 // Empty returns true if the map is empty. 55 Empty() bool 56 // Zip iterates over the entries of two maps together. If both maps contain a value for a given key, fn is called 57 // with the values from both maps, otherwise it is called with the value of the map that contains the key and nil 58 // for the map that does not contain the key. Returning false in the closure prematurely stops the iteration. 59 Zip(other Map, order MapTraverseOrder, fn func(key string, lhs, rhs Value) bool) bool 60 // ZipUsing uses the provided allocator and iterates over the entries of two maps together. If both maps 61 // contain a value for a given key, fn is called with the values from both maps, otherwise it is called with 62 // the value of the map that contains the key and nil for the map that does not contain the key. Returning 63 // false in the closure prematurely stops the iteration. 64 ZipUsing(a Allocator, other Map, order MapTraverseOrder, fn func(key string, lhs, rhs Value) bool) bool 65} 66 67// MapTraverseOrder defines the map traversal ordering available. 68type MapTraverseOrder int 69 70const ( 71 // Unordered indicates that the map traversal has no ordering requirement. 72 Unordered = iota 73 // LexicalKeyOrder indicates that the map traversal is ordered by key, lexically. 74 LexicalKeyOrder 75) 76 77// MapZip iterates over the entries of two maps together. If both maps contain a value for a given key, fn is called 78// with the values from both maps, otherwise it is called with the value of the map that contains the key and nil 79// for the other map. Returning false in the closure prematurely stops the iteration. 80func MapZip(lhs, rhs Map, order MapTraverseOrder, fn func(key string, lhs, rhs Value) bool) bool { 81 return MapZipUsing(HeapAllocator, lhs, rhs, order, fn) 82} 83 84// MapZipUsing uses the provided allocator and iterates over the entries of two maps together. If both maps 85// contain a value for a given key, fn is called with the values from both maps, otherwise it is called with 86// the value of the map that contains the key and nil for the other map. Returning false in the closure 87// prematurely stops the iteration. 88func MapZipUsing(a Allocator, lhs, rhs Map, order MapTraverseOrder, fn func(key string, lhs, rhs Value) bool) bool { 89 if lhs != nil { 90 return lhs.ZipUsing(a, rhs, order, fn) 91 } 92 if rhs != nil { 93 return rhs.ZipUsing(a, lhs, order, func(key string, rhs, lhs Value) bool { // arg positions of lhs and rhs deliberately swapped 94 return fn(key, lhs, rhs) 95 }) 96 } 97 return true 98} 99 100// defaultMapZip provides a default implementation of Zip for implementations that do not need to provide 101// their own optimized implementation. 102func defaultMapZip(a Allocator, lhs, rhs Map, order MapTraverseOrder, fn func(key string, lhs, rhs Value) bool) bool { 103 switch order { 104 case Unordered: 105 return unorderedMapZip(a, lhs, rhs, fn) 106 case LexicalKeyOrder: 107 return lexicalKeyOrderedMapZip(a, lhs, rhs, fn) 108 default: 109 panic("Unsupported map order") 110 } 111} 112 113func unorderedMapZip(a Allocator, lhs, rhs Map, fn func(key string, lhs, rhs Value) bool) bool { 114 if (lhs == nil || lhs.Empty()) && (rhs == nil || rhs.Empty()) { 115 return true 116 } 117 118 if lhs != nil { 119 ok := lhs.IterateUsing(a, func(key string, lhsValue Value) bool { 120 var rhsValue Value 121 if rhs != nil { 122 if item, ok := rhs.GetUsing(a, key); ok { 123 rhsValue = item 124 defer a.Free(rhsValue) 125 } 126 } 127 return fn(key, lhsValue, rhsValue) 128 }) 129 if !ok { 130 return false 131 } 132 } 133 if rhs != nil { 134 return rhs.IterateUsing(a, func(key string, rhsValue Value) bool { 135 if lhs == nil || !lhs.Has(key) { 136 return fn(key, nil, rhsValue) 137 } 138 return true 139 }) 140 } 141 return true 142} 143 144func lexicalKeyOrderedMapZip(a Allocator, lhs, rhs Map, fn func(key string, lhs, rhs Value) bool) bool { 145 var lhsLength, rhsLength int 146 var orderedLength int // rough estimate of length of union of map keys 147 if lhs != nil { 148 lhsLength = lhs.Length() 149 orderedLength = lhsLength 150 } 151 if rhs != nil { 152 rhsLength = rhs.Length() 153 if rhsLength > orderedLength { 154 orderedLength = rhsLength 155 } 156 } 157 if lhsLength == 0 && rhsLength == 0 { 158 return true 159 } 160 161 ordered := make([]string, 0, orderedLength) 162 if lhs != nil { 163 lhs.IterateUsing(a, func(key string, _ Value) bool { 164 ordered = append(ordered, key) 165 return true 166 }) 167 } 168 if rhs != nil { 169 rhs.IterateUsing(a, func(key string, _ Value) bool { 170 if lhs == nil || !lhs.Has(key) { 171 ordered = append(ordered, key) 172 } 173 return true 174 }) 175 } 176 sort.Strings(ordered) 177 for _, key := range ordered { 178 var litem, ritem Value 179 if lhs != nil { 180 litem, _ = lhs.GetUsing(a, key) 181 } 182 if rhs != nil { 183 ritem, _ = rhs.GetUsing(a, key) 184 } 185 ok := fn(key, litem, ritem) 186 if litem != nil { 187 a.Free(litem) 188 } 189 if ritem != nil { 190 a.Free(ritem) 191 } 192 if !ok { 193 return false 194 } 195 } 196 return true 197} 198 199// MapLess compares two maps lexically. 200func MapLess(lhs, rhs Map) bool { 201 return MapCompare(lhs, rhs) == -1 202} 203 204// MapCompare compares two maps lexically. 205func MapCompare(lhs, rhs Map) int { 206 return MapCompareUsing(HeapAllocator, lhs, rhs) 207} 208 209// MapCompareUsing uses the provided allocator and compares two maps lexically. 210func MapCompareUsing(a Allocator, lhs, rhs Map) int { 211 c := 0 212 var llength, rlength int 213 if lhs != nil { 214 llength = lhs.Length() 215 } 216 if rhs != nil { 217 rlength = rhs.Length() 218 } 219 if llength == 0 && rlength == 0 { 220 return 0 221 } 222 i := 0 223 MapZipUsing(a, lhs, rhs, LexicalKeyOrder, func(key string, lhs, rhs Value) bool { 224 switch { 225 case i == llength: 226 c = -1 227 case i == rlength: 228 c = 1 229 case lhs == nil: 230 c = 1 231 case rhs == nil: 232 c = -1 233 default: 234 c = CompareUsing(a, lhs, rhs) 235 } 236 i++ 237 return c == 0 238 }) 239 return c 240} 241 242// MapEquals returns true if lhs == rhs, false otherwise. This function 243// acts on generic types and should not be used by callers, but can help 244// implement Map.Equals. 245// WARN: This is a naive implementation, calling lhs.Equals(rhs) is typically the most efficient. 246func MapEquals(lhs, rhs Map) bool { 247 return MapEqualsUsing(HeapAllocator, lhs, rhs) 248} 249 250// MapEqualsUsing uses the provided allocator and returns true if lhs == rhs, 251// false otherwise. This function acts on generic types and should not be used 252// by callers, but can help implement Map.Equals. 253// WARN: This is a naive implementation, calling lhs.EqualsUsing(allocator, rhs) is typically the most efficient. 254func MapEqualsUsing(a Allocator, lhs, rhs Map) bool { 255 if lhs == nil && rhs == nil { 256 return true 257 } 258 if lhs == nil || rhs == nil { 259 return false 260 } 261 if lhs.Length() != rhs.Length() { 262 return false 263 } 264 return MapZipUsing(a, lhs, rhs, Unordered, func(key string, lhs, rhs Value) bool { 265 if lhs == nil || rhs == nil { 266 return false 267 } 268 return EqualsUsing(a, lhs, rhs) 269 }) 270} 271