cmd/bpa-operator/vendor/github.com/prometheus/common/model/signature.go

   1 // Copyright 2014 The Prometheus Authors
   2 // Licensed under the Apache License, Version 2.0 (the "License");
   3 // you may not use this file except in compliance with the License.
   4 // You may obtain a copy of the License at
   5 //
   6 // http://www.apache.org/licenses/LICENSE-2.0
   7 //
   8 // Unless required by applicable law or agreed to in writing, software
   9 // distributed under the License is distributed on an "AS IS" BASIS,
  10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  11 // See the License for the specific language governing permissions and
  12 // limitations under the License.
  13
  14 package model
  15
  16 import (
  17         "sort"
  18 )
  19
  20 // SeparatorByte is a byte that cannot occur in valid UTF-8 sequences and is
  21 // used to separate label names, label values, and other strings from each other
  22 // when calculating their combined hash value (aka signature aka fingerprint).
  23 const SeparatorByte byte = 255
  24
  25 var (
  26         // cache the signature of an empty label set.
  27         emptyLabelSignature = hashNew()
  28 )
  29
  30 // LabelsToSignature returns a quasi-unique signature (i.e., fingerprint) for a
  31 // given label set. (Collisions are possible but unlikely if the number of label
  32 // sets the function is applied to is small.)
  33 func LabelsToSignature(labels map[string]string) uint64 {
  34         if len(labels) == 0 {
  35                 return emptyLabelSignature
  36         }
  37
  38         labelNames := make([]string, 0, len(labels))
  39         for labelName := range labels {
  40                 labelNames = append(labelNames, labelName)
  41         }
  42         sort.Strings(labelNames)
  43
  44         sum := hashNew()
  45         for _, labelName := range labelNames {
  46                 sum = hashAdd(sum, labelName)
  47                 sum = hashAddByte(sum, SeparatorByte)
  48                 sum = hashAdd(sum, labels[labelName])
  49                 sum = hashAddByte(sum, SeparatorByte)
  50         }
  51         return sum
  52 }
  53
  54 // labelSetToFingerprint works exactly as LabelsToSignature but takes a LabelSet as
  55 // parameter (rather than a label map) and returns a Fingerprint.
  56 func labelSetToFingerprint(ls LabelSet) Fingerprint {
  57         if len(ls) == 0 {
  58                 return Fingerprint(emptyLabelSignature)
  59         }
  60
  61         labelNames := make(LabelNames, 0, len(ls))
  62         for labelName := range ls {
  63                 labelNames = append(labelNames, labelName)
  64         }
  65         sort.Sort(labelNames)
  66
  67         sum := hashNew()
  68         for _, labelName := range labelNames {
  69                 sum = hashAdd(sum, string(labelName))
  70                 sum = hashAddByte(sum, SeparatorByte)
  71                 sum = hashAdd(sum, string(ls[labelName]))
  72                 sum = hashAddByte(sum, SeparatorByte)
  73         }
  74         return Fingerprint(sum)
  75 }
  76
  77 // labelSetToFastFingerprint works similar to labelSetToFingerprint but uses a
  78 // faster and less allocation-heavy hash function, which is more susceptible to
  79 // create hash collisions. Therefore, collision detection should be applied.
  80 func labelSetToFastFingerprint(ls LabelSet) Fingerprint {
  81         if len(ls) == 0 {
  82                 return Fingerprint(emptyLabelSignature)
  83         }
  84
  85         var result uint64
  86         for labelName, labelValue := range ls {
  87                 sum := hashNew()
  88                 sum = hashAdd(sum, string(labelName))
  89                 sum = hashAddByte(sum, SeparatorByte)
  90                 sum = hashAdd(sum, string(labelValue))
  91                 result ^= sum
  92         }
  93         return Fingerprint(result)
  94 }
  95
  96 // SignatureForLabels works like LabelsToSignature but takes a Metric as
  97 // parameter (rather than a label map) and only includes the labels with the
  98 // specified LabelNames into the signature calculation. The labels passed in
  99 // will be sorted by this function.
 100 func SignatureForLabels(m Metric, labels ...LabelName) uint64 {
 101         if len(labels) == 0 {
 102                 return emptyLabelSignature
 103         }
 104
 105         sort.Sort(LabelNames(labels))
 106
 107         sum := hashNew()
 108         for _, label := range labels {
 109                 sum = hashAdd(sum, string(label))
 110                 sum = hashAddByte(sum, SeparatorByte)
 111                 sum = hashAdd(sum, string(m[label]))
 112                 sum = hashAddByte(sum, SeparatorByte)
 113         }
 114         return sum
 115 }
 116
 117 // SignatureWithoutLabels works like LabelsToSignature but takes a Metric as
 118 // parameter (rather than a label map) and excludes the labels with any of the
 119 // specified LabelNames from the signature calculation.
 120 func SignatureWithoutLabels(m Metric, labels map[LabelName]struct{}) uint64 {
 121         if len(m) == 0 {
 122                 return emptyLabelSignature
 123         }
 124
 125         labelNames := make(LabelNames, 0, len(m))
 126         for labelName := range m {
 127                 if _, exclude := labels[labelName]; !exclude {
 128                         labelNames = append(labelNames, labelName)
 129                 }
 130         }
 131         if len(labelNames) == 0 {
 132                 return emptyLabelSignature
 133         }
 134         sort.Sort(labelNames)
 135
 136         sum := hashNew()
 137         for _, labelName := range labelNames {
 138                 sum = hashAdd(sum, string(labelName))
 139                 sum = hashAddByte(sum, SeparatorByte)
 140                 sum = hashAdd(sum, string(m[labelName]))
 141                 sum = hashAddByte(sum, SeparatorByte)
 142         }
 143         return sum
 144 }