objmetadata_set.go

Documentation: sigs.k8s.io/cli-utils/pkg/object

     1  // Copyright 2021 The Kubernetes Authors.
     2  // SPDX-License-Identifier: Apache-2.0
     3  //
     4  
     5  package object
     6  
     7  import (
     8  	"hash/fnv"
     9  	"sort"
    10  	"strconv"
    11  )
    12  
    13  // ObjMetadataSet is an ordered list of ObjMetadata that acts like an unordered
    14  // set for comparison purposes.
    15  type ObjMetadataSet []ObjMetadata
    16  
    17  // UnstructuredSetEquals returns true if the slice of objects in setA equals
    18  // the slice of objects in setB.
    19  func ObjMetadataSetEquals(setA []ObjMetadata, setB []ObjMetadata) bool {
    20  	return ObjMetadataSet(setA).Equal(ObjMetadataSet(setB))
    21  }
    22  
    23  // ObjMetadataSetFromMap constructs a set from a map
    24  func ObjMetadataSetFromMap(mapA map[ObjMetadata]struct{}) ObjMetadataSet {
    25  	setA := make(ObjMetadataSet, 0, len(mapA))
    26  	for f := range mapA {
    27  		setA = append(setA, f)
    28  	}
    29  	return setA
    30  }
    31  
    32  // Equal returns true if the two sets contain equivalent objects. Duplicates are
    33  // ignored.
    34  // This function satisfies the cmp.Equal interface from github.com/google/go-cmp
    35  func (setA ObjMetadataSet) Equal(setB ObjMetadataSet) bool {
    36  	mapA := make(map[ObjMetadata]struct{}, len(setA))
    37  	for _, a := range setA {
    38  		mapA[a] = struct{}{}
    39  	}
    40  	mapB := make(map[ObjMetadata]struct{}, len(setB))
    41  	for _, b := range setB {
    42  		mapB[b] = struct{}{}
    43  	}
    44  	if len(mapA) != len(mapB) {
    45  		return false
    46  	}
    47  	for b := range mapB {
    48  		if _, exists := mapA[b]; !exists {
    49  			return false
    50  		}
    51  	}
    52  	return true
    53  }
    54  
    55  // Contains checks if the provided ObjMetadata exists in the set.
    56  func (setA ObjMetadataSet) Contains(id ObjMetadata) bool {
    57  	for _, om := range setA {
    58  		if om == id {
    59  			return true
    60  		}
    61  	}
    62  	return false
    63  }
    64  
    65  // Remove the object from the set and return the updated set.
    66  func (setA ObjMetadataSet) Remove(obj ObjMetadata) ObjMetadataSet {
    67  	for i, a := range setA {
    68  		if a == obj {
    69  			setA[len(setA)-1], setA[i] = setA[i], setA[len(setA)-1]
    70  			return setA[:len(setA)-1]
    71  		}
    72  	}
    73  	return setA
    74  }
    75  
    76  // Intersection returns the set of unique objects in both set A and set B.
    77  func (setA ObjMetadataSet) Intersection(setB ObjMetadataSet) ObjMetadataSet {
    78  	var maxlen int
    79  	if len(setA) > len(setB) {
    80  		maxlen = len(setA)
    81  	} else {
    82  		maxlen = len(setB)
    83  	}
    84  	mapI := make(map[ObjMetadata]struct{}, maxlen)
    85  	mapB := setB.ToMap()
    86  	for _, a := range setA {
    87  		if _, ok := mapB[a]; ok {
    88  			mapI[a] = struct{}{}
    89  		}
    90  	}
    91  	intersection := make(ObjMetadataSet, 0, len(mapI))
    92  	// Iterate over setA & setB to retain input order and have stable output
    93  	for _, id := range setA {
    94  		if _, ok := mapI[id]; ok {
    95  			intersection = append(intersection, id)
    96  			delete(mapI, id)
    97  		}
    98  	}
    99  	for _, id := range setB {
   100  		if _, ok := mapI[id]; ok {
   101  			intersection = append(intersection, id)
   102  			delete(mapI, id)
   103  		}
   104  	}
   105  	return intersection
   106  }
   107  
   108  // Union returns the set of unique objects from the merging of set A and set B.
   109  func (setA ObjMetadataSet) Union(setB ObjMetadataSet) ObjMetadataSet {
   110  	m := make(map[ObjMetadata]struct{}, len(setA)+len(setB))
   111  	for _, a := range setA {
   112  		m[a] = struct{}{}
   113  	}
   114  	for _, b := range setB {
   115  		m[b] = struct{}{}
   116  	}
   117  	union := make(ObjMetadataSet, 0, len(m))
   118  	// Iterate over setA & setB to retain input order and have stable output
   119  	for _, id := range setA {
   120  		if _, ok := m[id]; ok {
   121  			union = append(union, id)
   122  			delete(m, id)
   123  		}
   124  	}
   125  	for _, id := range setB {
   126  		if _, ok := m[id]; ok {
   127  			union = append(union, id)
   128  			delete(m, id)
   129  		}
   130  	}
   131  	return union
   132  }
   133  
   134  // Diff returns the set of objects that exist in set A, but not in set B (A - B).
   135  func (setA ObjMetadataSet) Diff(setB ObjMetadataSet) ObjMetadataSet {
   136  	// Create a map of the elements of A
   137  	m := make(map[ObjMetadata]struct{}, len(setA))
   138  	for _, a := range setA {
   139  		m[a] = struct{}{}
   140  	}
   141  	// Remove from A each element of B
   142  	for _, b := range setB {
   143  		delete(m, b) // OK to delete even if b not in m
   144  	}
   145  	// Create/return slice from the map of remaining items
   146  	diff := make(ObjMetadataSet, 0, len(m))
   147  	// Iterate over setA to retain input order and have stable output
   148  	for _, id := range setA {
   149  		if _, ok := m[id]; ok {
   150  			diff = append(diff, id)
   151  			delete(m, id)
   152  		}
   153  	}
   154  	return diff
   155  }
   156  
   157  // Unique returns the set with duplicates removed.
   158  // Order may or may not remain consistent.
   159  func (setA ObjMetadataSet) Unique() ObjMetadataSet {
   160  	return ObjMetadataSetFromMap(setA.ToMap())
   161  }
   162  
   163  // Hash the objects in the set by serializing, sorting, concatonating, and
   164  // hashing the result with the 32-bit FNV-1a algorithm.
   165  func (setA ObjMetadataSet) Hash() string {
   166  	objStrs := make([]string, 0, len(setA))
   167  	for _, obj := range setA {
   168  		objStrs = append(objStrs, obj.String())
   169  	}
   170  	sort.Strings(objStrs)
   171  	h := fnv.New32a()
   172  	for _, obj := range objStrs {
   173  		// Hash32.Write never returns an error
   174  		// https://pkg.go.dev/hash#pkg-types
   175  		_, _ = h.Write([]byte(obj))
   176  	}
   177  	return strconv.FormatUint(uint64(h.Sum32()), 16)
   178  }
   179  
   180  // ToMap returns the set as a map, with objMeta keys and empty struct values.
   181  func (setA ObjMetadataSet) ToMap() map[ObjMetadata]struct{} {
   182  	m := make(map[ObjMetadata]struct{}, len(setA))
   183  	for _, objMeta := range setA {
   184  		m[objMeta] = struct{}{}
   185  	}
   186  	return m
   187  }
   188  
   189  // ToStringMap returns the set as a serializable map, with objMeta keys and
   190  // empty string values.
   191  func (setA ObjMetadataSet) ToStringMap() map[string]string {
   192  	stringMap := make(map[string]string, len(setA))
   193  	for _, objMeta := range setA {
   194  		stringMap[objMeta.String()] = ""
   195  	}
   196  	return stringMap
   197  }
   198  
   199  // FromStringMap returns a set from a serializable map, with objMeta keys and
   200  // empty string values. Errors if parsing fails.
   201  func FromStringMap(in map[string]string) (ObjMetadataSet, error) {
   202  	var set ObjMetadataSet
   203  	for s := range in {
   204  		objMeta, err := ParseObjMetadata(s)
   205  		if err != nil {
   206  			return nil, err
   207  		}
   208  		set = append(set, objMeta)
   209  	}
   210  	return set, nil
   211  }
   212
View as plain text