mapping.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package http
     6  
     7  // A mapping is a collection of key-value pairs where the keys are unique.
     8  // A zero mapping is empty and ready to use.
     9  // A mapping tries to pick a representation that makes [mapping.find] most efficient.
    10  type mapping[K comparable, V any] struct {
    11  	s []entry[K, V] // for few pairs
    12  	m map[K]V       // for many pairs
    13  }
    14  
    15  type entry[K comparable, V any] struct {
    16  	key   K
    17  	value V
    18  }
    19  
    20  // maxSlice is the maximum number of pairs for which a slice is used.
    21  // It is a variable for benchmarking.
    22  var maxSlice int = 8
    23  
    24  // add adds a key-value pair to the mapping.
    25  func (h *mapping[K, V]) add(k K, v V) {
    26  	if h.m == nil && len(h.s) < maxSlice {
    27  		h.s = append(h.s, entry[K, V]{k, v})
    28  	} else {
    29  		if h.m == nil {
    30  			h.m = map[K]V{}
    31  			for _, e := range h.s {
    32  				h.m[e.key] = e.value
    33  			}
    34  			h.s = nil
    35  		}
    36  		h.m[k] = v
    37  	}
    38  }
    39  
    40  // find returns the value corresponding to the given key.
    41  // The second return value is false if there is no value
    42  // with that key.
    43  func (h *mapping[K, V]) find(k K) (v V, found bool) {
    44  	if h == nil {
    45  		return v, false
    46  	}
    47  	if h.m != nil {
    48  		v, found = h.m[k]
    49  		return v, found
    50  	}
    51  	for _, e := range h.s {
    52  		if e.key == k {
    53  			return e.value, true
    54  		}
    55  	}
    56  	return v, false
    57  }
    58  
    59  // eachPair calls f for each pair in the mapping.
    60  // If f returns false, pairs returns immediately.
    61  func (h *mapping[K, V]) eachPair(f func(k K, v V) bool) {
    62  	if h == nil {
    63  		return
    64  	}
    65  	if h.m != nil {
    66  		for k, v := range h.m {
    67  			if !f(k, v) {
    68  				return
    69  			}
    70  		}
    71  	} else {
    72  		for _, e := range h.s {
    73  			if !f(e.key, e.value) {
    74  				return
    75  			}
    76  		}
    77  	}
    78  }
    79
View as plain text