map.go

Documentation: sigs.k8s.io/structured-merge-diff/v4/value

     1  /*
     2  Copyright 2019 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package value
    18  
    19  import (
    20  	"sort"
    21  )
    22  
    23  // Map represents a Map or go structure.
    24  type 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.
    68  type MapTraverseOrder int
    69  
    70  const (
    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.
    80  func 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.
    88  func 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.
   102  func 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  
   113  func 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  
   144  func 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.
   200  func MapLess(lhs, rhs Map) bool {
   201  	return MapCompare(lhs, rhs) == -1
   202  }
   203  
   204  // MapCompare compares two maps lexically.
   205  func MapCompare(lhs, rhs Map) int {
   206  	return MapCompareUsing(HeapAllocator, lhs, rhs)
   207  }
   208  
   209  // MapCompareUsing uses the provided allocator and compares two maps lexically.
   210  func 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.
   246  func 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.
   254  func 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
View as plain text