table.go

     1  // Copyright 2024 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 maps
     6  
     7  import (
     8  	"internal/abi"
     9  	"internal/runtime/math"
    10  	"unsafe"
    11  )
    12  
    13  // Maximum size of a table before it is split at the directory level.
    14  //
    15  // TODO: Completely made up value. This should be tuned for performance vs grow
    16  // latency.
    17  // TODO: This should likely be based on byte size, as copying costs will
    18  // dominate grow latency for large objects.
    19  const maxTableCapacity = 1024
    20  
    21  // Ensure the max capacity fits in uint16, used for capacity and growthLeft
    22  // below.
    23  var _ = uint16(maxTableCapacity)
    24  
    25  // table is a Swiss table hash table structure.
    26  //
    27  // Each table is a complete hash table implementation.
    28  //
    29  // Map uses one or more tables to store entries. Extendible hashing (hash
    30  // prefix) is used to select the table to use for a specific key. Using
    31  // multiple tables enables incremental growth by growing only one table at a
    32  // time.
    33  type table struct {
    34  	// The number of filled slots (i.e. the number of elements in the table).
    35  	used uint16
    36  
    37  	// The total number of slots (always 2^N). Equal to
    38  	// `(groups.lengthMask+1)*abi.MapGroupSlots`.
    39  	capacity uint16
    40  
    41  	// The number of slots we can still fill without needing to rehash.
    42  	//
    43  	// We rehash when used + tombstones > loadFactor*capacity, including
    44  	// tombstones so the table doesn't overfill with tombstones. This field
    45  	// counts down remaining empty slots before the next rehash.
    46  	growthLeft uint16
    47  
    48  	// The number of bits used by directory lookups above this table. Note
    49  	// that this may be less then globalDepth, if the directory has grown
    50  	// but this table has not yet been split.
    51  	localDepth uint8
    52  
    53  	// Index of this table in the Map directory. This is the index of the
    54  	// _first_ location in the directory. The table may occur in multiple
    55  	// sequential indices.
    56  	//
    57  	// index is -1 if the table is stale (no longer installed in the
    58  	// directory).
    59  	index int
    60  
    61  	// groups is an array of slot groups. Each group holds abi.MapGroupSlots
    62  	// key/elem slots and their control bytes. A table has a fixed size
    63  	// groups array. The table is replaced (in rehash) when more space is
    64  	// required.
    65  	//
    66  	// TODO(prattmic): keys and elements are interleaved to maximize
    67  	// locality, but it comes at the expense of wasted space for some types
    68  	// (consider uint8 key, uint64 element). Consider placing all keys
    69  	// together in these cases to save space.
    70  	groups groupsReference
    71  }
    72  
    73  func newTable(typ *abi.MapType, capacity uint64, index int, localDepth uint8) *table {
    74  	if capacity < abi.MapGroupSlots {
    75  		capacity = abi.MapGroupSlots
    76  	}
    77  
    78  	t := &table{
    79  		index:      index,
    80  		localDepth: localDepth,
    81  	}
    82  
    83  	if capacity > maxTableCapacity {
    84  		panic("initial table capacity too large")
    85  	}
    86  
    87  	// N.B. group count must be a power of two for probeSeq to visit every
    88  	// group.
    89  	capacity, overflow := alignUpPow2(capacity)
    90  	if overflow {
    91  		panic("rounded-up capacity overflows uint64")
    92  	}
    93  
    94  	t.reset(typ, uint16(capacity))
    95  
    96  	return t
    97  }
    98  
    99  // reset resets the table with new, empty groups with the specified new total
   100  // capacity.
   101  func (t *table) reset(typ *abi.MapType, capacity uint16) {
   102  	groupCount := uint64(capacity) / abi.MapGroupSlots
   103  	t.groups = newGroups(typ, groupCount)
   104  	t.capacity = capacity
   105  	t.growthLeft = t.maxGrowthLeft()
   106  
   107  	for i := uint64(0); i <= t.groups.lengthMask; i++ {
   108  		g := t.groups.group(typ, i)
   109  		g.ctrls().setEmpty()
   110  	}
   111  }
   112  
   113  // maxGrowthLeft is the number of inserts we can do before
   114  // resizing, starting from an empty table.
   115  func (t *table) maxGrowthLeft() uint16 {
   116  	if t.capacity == 0 {
   117  		// No real reason to support zero capacity table, since an
   118  		// empty Map simply won't have a table.
   119  		panic("table must have positive capacity")
   120  	} else if t.capacity <= abi.MapGroupSlots {
   121  		// If the map fits in a single group then we're able to fill all of
   122  		// the slots except 1 (an empty slot is needed to terminate find
   123  		// operations).
   124  		//
   125  		// TODO(go.dev/issue/54766): With a special case in probing for
   126  		// single-group tables, we could fill all slots.
   127  		return t.capacity - 1
   128  	} else {
   129  		if t.capacity > math.MaxUint16/maxAvgGroupLoad {
   130  			panic("overflow")
   131  		}
   132  		return (t.capacity * maxAvgGroupLoad) / abi.MapGroupSlots
   133  	}
   134  
   135  }
   136  
   137  func (t *table) Used() uint64 {
   138  	return uint64(t.used)
   139  }
   140  
   141  // Get performs a lookup of the key that key points to. It returns a pointer to
   142  // the element, or false if the key doesn't exist.
   143  func (t *table) Get(typ *abi.MapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool) {
   144  	// TODO(prattmic): We could avoid hashing in a variety of special
   145  	// cases.
   146  	//
   147  	// - One entry maps could just directly compare the single entry
   148  	//   without hashing.
   149  	// - String keys could do quick checks of a few bytes before hashing.
   150  	hash := typ.Hasher(key, m.seed)
   151  	_, elem, ok := t.getWithKey(typ, hash, key)
   152  	return elem, ok
   153  }
   154  
   155  // getWithKey performs a lookup of key, returning a pointer to the version of
   156  // the key in the map in addition to the element.
   157  //
   158  // This is relevant when multiple different key values compare equal (e.g.,
   159  // +0.0 and -0.0). When a grow occurs during iteration, iteration perform a
   160  // lookup of keys from the old group in the new group in order to correctly
   161  // expose updated elements. For NeedsKeyUpdate keys, iteration also must return
   162  // the new key value, not the old key value.
   163  // hash must be the hash of the key.
   164  func (t *table) getWithKey(typ *abi.MapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
   165  	// To find the location of a key in the table, we compute hash(key). From
   166  	// h1(hash(key)) and the capacity, we construct a probeSeq that visits
   167  	// every group of slots in some interesting order. See [probeSeq].
   168  	//
   169  	// We walk through these indices. At each index, we select the entire
   170  	// group starting with that index and extract potential candidates:
   171  	// occupied slots with a control byte equal to h2(hash(key)). The key
   172  	// at candidate slot i is compared with key; if key == g.slot(i).key
   173  	// we are done and return the slot; if there is an empty slot in the
   174  	// group, we stop and return an error; otherwise we continue to the
   175  	// next probe index. Tombstones (ctrlDeleted) effectively behave like
   176  	// full slots that never match the value we're looking for.
   177  	//
   178  	// The h2 bits ensure when we compare a key we are likely to have
   179  	// actually found the object. That is, the chance is low that keys
   180  	// compare false. Thus, when we search for an object, we are unlikely
   181  	// to call Equal many times. This likelihood can be analyzed as follows
   182  	// (assuming that h2 is a random enough hash function).
   183  	//
   184  	// Let's assume that there are k "wrong" objects that must be examined
   185  	// in a probe sequence. For example, when doing a find on an object
   186  	// that is in the table, k is the number of objects between the start
   187  	// of the probe sequence and the final found object (not including the
   188  	// final found object). The expected number of objects with an h2 match
   189  	// is then k/128. Measurements and analysis indicate that even at high
   190  	// load factors, k is less than 32, meaning that the number of false
   191  	// positive comparisons we must perform is less than 1/8 per find.
   192  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   193  	h2Hash := h2(hash)
   194  	for ; ; seq = seq.next() {
   195  		g := t.groups.group(typ, seq.offset)
   196  
   197  		match := g.ctrls().matchH2(h2Hash)
   198  
   199  		for match != 0 {
   200  			i := match.first()
   201  
   202  			slotKey := g.key(typ, i)
   203  			if typ.IndirectKey() {
   204  				slotKey = *((*unsafe.Pointer)(slotKey))
   205  			}
   206  			if typ.Key.Equal(key, slotKey) {
   207  				slotElem := g.elem(typ, i)
   208  				if typ.IndirectElem() {
   209  					slotElem = *((*unsafe.Pointer)(slotElem))
   210  				}
   211  				return slotKey, slotElem, true
   212  			}
   213  			match = match.removeFirst()
   214  		}
   215  
   216  		match = g.ctrls().matchEmpty()
   217  		if match != 0 {
   218  			// Finding an empty slot means we've reached the end of
   219  			// the probe sequence.
   220  			return nil, nil, false
   221  		}
   222  	}
   223  }
   224  
   225  func (t *table) getWithoutKey(typ *abi.MapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool) {
   226  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   227  	h2Hash := h2(hash)
   228  	for ; ; seq = seq.next() {
   229  		g := t.groups.group(typ, seq.offset)
   230  
   231  		match := g.ctrls().matchH2(h2Hash)
   232  
   233  		for match != 0 {
   234  			i := match.first()
   235  
   236  			slotKey := g.key(typ, i)
   237  			if typ.IndirectKey() {
   238  				slotKey = *((*unsafe.Pointer)(slotKey))
   239  			}
   240  			if typ.Key.Equal(key, slotKey) {
   241  				slotElem := g.elem(typ, i)
   242  				if typ.IndirectElem() {
   243  					slotElem = *((*unsafe.Pointer)(slotElem))
   244  				}
   245  				return slotElem, true
   246  			}
   247  			match = match.removeFirst()
   248  		}
   249  
   250  		match = g.ctrls().matchEmpty()
   251  		if match != 0 {
   252  			// Finding an empty slot means we've reached the end of
   253  			// the probe sequence.
   254  			return nil, false
   255  		}
   256  	}
   257  }
   258  
   259  // PutSlot returns a pointer to the element slot where an inserted element
   260  // should be written, and ok if it returned a valid slot.
   261  //
   262  // PutSlot returns ok false if the table was split and the Map needs to find
   263  // the new table.
   264  //
   265  // hash must be the hash of key.
   266  func (t *table) PutSlot(typ *abi.MapType, m *Map, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool) {
   267  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   268  
   269  	// As we look for a match, keep track of the first deleted slot we
   270  	// find, which we'll use to insert the new entry if necessary.
   271  	var firstDeletedGroup groupReference
   272  	var firstDeletedSlot uintptr
   273  
   274  	h2Hash := h2(hash)
   275  	for ; ; seq = seq.next() {
   276  		g := t.groups.group(typ, seq.offset)
   277  		match := g.ctrls().matchH2(h2Hash)
   278  
   279  		// Look for an existing slot containing this key.
   280  		for match != 0 {
   281  			i := match.first()
   282  
   283  			slotKey := g.key(typ, i)
   284  			if typ.IndirectKey() {
   285  				slotKey = *((*unsafe.Pointer)(slotKey))
   286  			}
   287  			if typ.Key.Equal(key, slotKey) {
   288  				if typ.NeedKeyUpdate() {
   289  					typedmemmove(typ.Key, slotKey, key)
   290  				}
   291  
   292  				slotElem := g.elem(typ, i)
   293  				if typ.IndirectElem() {
   294  					slotElem = *((*unsafe.Pointer)(slotElem))
   295  				}
   296  
   297  				t.checkInvariants(typ, m)
   298  				return slotElem, true
   299  			}
   300  			match = match.removeFirst()
   301  		}
   302  
   303  		// No existing slot for this key in this group. Is this the end
   304  		// of the probe sequence?
   305  		match = g.ctrls().matchEmptyOrDeleted()
   306  		if match == 0 {
   307  			continue // nothing but filled slots. Keep probing.
   308  		}
   309  		i := match.first()
   310  		if g.ctrls().get(i) == ctrlDeleted {
   311  			// There are some deleted slots. Remember
   312  			// the first one, and keep probing.
   313  			if firstDeletedGroup.data == nil {
   314  				firstDeletedGroup = g
   315  				firstDeletedSlot = i
   316  			}
   317  			continue
   318  		}
   319  		// We've found an empty slot, which means we've reached the end of
   320  		// the probe sequence.
   321  
   322  		// If we found a deleted slot along the way, we can
   323  		// replace it without consuming growthLeft.
   324  		if firstDeletedGroup.data != nil {
   325  			g = firstDeletedGroup
   326  			i = firstDeletedSlot
   327  			t.growthLeft++ // will be decremented below to become a no-op.
   328  		}
   329  
   330  		// If we have no space left, first try to remove some tombstones.
   331  		if t.growthLeft == 0 {
   332  			t.pruneTombstones(typ, m)
   333  		}
   334  
   335  		// If there is room left to grow, just insert the new entry.
   336  		if t.growthLeft > 0 {
   337  			slotKey := g.key(typ, i)
   338  			if typ.IndirectKey() {
   339  				kmem := newobject(typ.Key)
   340  				*(*unsafe.Pointer)(slotKey) = kmem
   341  				slotKey = kmem
   342  			}
   343  			typedmemmove(typ.Key, slotKey, key)
   344  
   345  			slotElem := g.elem(typ, i)
   346  			if typ.IndirectElem() {
   347  				emem := newobject(typ.Elem)
   348  				*(*unsafe.Pointer)(slotElem) = emem
   349  				slotElem = emem
   350  			}
   351  
   352  			g.ctrls().set(i, ctrl(h2Hash))
   353  			t.growthLeft--
   354  			t.used++
   355  			m.used++
   356  
   357  			t.checkInvariants(typ, m)
   358  			return slotElem, true
   359  		}
   360  
   361  		t.rehash(typ, m)
   362  		return nil, false
   363  	}
   364  }
   365  
   366  // uncheckedPutSlot inserts an entry known not to be in the table.
   367  // This is used for grow/split where we are making a new table from
   368  // entries in an existing table.
   369  //
   370  // Decrements growthLeft and increments used.
   371  //
   372  // Requires that the entry does not exist in the table, and that the table has
   373  // room for another element without rehashing.
   374  //
   375  // Requires that there are no deleted entries in the table.
   376  //
   377  // For indirect keys and/or elements, the key and elem pointers can be
   378  // put directly into the map, they do not need to be copied. This
   379  // requires the caller to ensure that the referenced memory never
   380  // changes (by sourcing those pointers from another indirect key/elem
   381  // map).
   382  func (t *table) uncheckedPutSlot(typ *abi.MapType, hash uintptr, key, elem unsafe.Pointer) {
   383  	if t.growthLeft == 0 {
   384  		panic("invariant failed: growthLeft is unexpectedly 0")
   385  	}
   386  
   387  	// Given key and its hash hash(key), to insert it, we construct a
   388  	// probeSeq, and use it to find the first group with an unoccupied (empty
   389  	// or deleted) slot. We place the key/value into the first such slot in
   390  	// the group and mark it as full with key's H2.
   391  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   392  	for ; ; seq = seq.next() {
   393  		g := t.groups.group(typ, seq.offset)
   394  
   395  		match := g.ctrls().matchEmptyOrDeleted()
   396  		if match != 0 {
   397  			i := match.first()
   398  
   399  			slotKey := g.key(typ, i)
   400  			if typ.IndirectKey() {
   401  				*(*unsafe.Pointer)(slotKey) = key
   402  			} else {
   403  				typedmemmove(typ.Key, slotKey, key)
   404  			}
   405  
   406  			slotElem := g.elem(typ, i)
   407  			if typ.IndirectElem() {
   408  				*(*unsafe.Pointer)(slotElem) = elem
   409  			} else {
   410  				typedmemmove(typ.Elem, slotElem, elem)
   411  			}
   412  
   413  			t.growthLeft--
   414  			t.used++
   415  			g.ctrls().set(i, ctrl(h2(hash)))
   416  			return
   417  		}
   418  	}
   419  }
   420  
   421  // Delete returns true if it put a tombstone in t.
   422  func (t *table) Delete(typ *abi.MapType, m *Map, hash uintptr, key unsafe.Pointer) bool {
   423  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   424  	h2Hash := h2(hash)
   425  	for ; ; seq = seq.next() {
   426  		g := t.groups.group(typ, seq.offset)
   427  		match := g.ctrls().matchH2(h2Hash)
   428  
   429  		for match != 0 {
   430  			i := match.first()
   431  
   432  			slotKey := g.key(typ, i)
   433  			origSlotKey := slotKey
   434  			if typ.IndirectKey() {
   435  				slotKey = *((*unsafe.Pointer)(slotKey))
   436  			}
   437  
   438  			if typ.Key.Equal(key, slotKey) {
   439  				t.used--
   440  				m.used--
   441  
   442  				if typ.IndirectKey() {
   443  					// Clearing the pointer is sufficient.
   444  					*(*unsafe.Pointer)(origSlotKey) = nil
   445  				} else if typ.Key.Pointers() {
   446  					// Only bothing clear the key if there
   447  					// are pointers in it.
   448  					typedmemclr(typ.Key, slotKey)
   449  				}
   450  
   451  				slotElem := g.elem(typ, i)
   452  				if typ.IndirectElem() {
   453  					// Clearing the pointer is sufficient.
   454  					*(*unsafe.Pointer)(slotElem) = nil
   455  				} else {
   456  					// Unlike keys, always clear the elem (even if
   457  					// it contains no pointers), as compound
   458  					// assignment operations depend on cleared
   459  					// deleted values. See
   460  					// https://go.dev/issue/25936.
   461  					typedmemclr(typ.Elem, slotElem)
   462  				}
   463  
   464  				// Only a full group can appear in the middle
   465  				// of a probe sequence (a group with at least
   466  				// one empty slot terminates probing). Once a
   467  				// group becomes full, it stays full until
   468  				// rehashing/resizing. So if the group isn't
   469  				// full now, we can simply remove the element.
   470  				// Otherwise, we create a tombstone to mark the
   471  				// slot as deleted.
   472  				var tombstone bool
   473  				if g.ctrls().matchEmpty() != 0 {
   474  					g.ctrls().set(i, ctrlEmpty)
   475  					t.growthLeft++
   476  				} else {
   477  					g.ctrls().set(i, ctrlDeleted)
   478  					tombstone = true
   479  				}
   480  
   481  				t.checkInvariants(typ, m)
   482  				return tombstone
   483  			}
   484  			match = match.removeFirst()
   485  		}
   486  
   487  		match = g.ctrls().matchEmpty()
   488  		if match != 0 {
   489  			// Finding an empty slot means we've reached the end of
   490  			// the probe sequence.
   491  			return false
   492  		}
   493  	}
   494  }
   495  
   496  // pruneTombstones goes through the table and tries to remove
   497  // tombstones that are no longer needed. Best effort.
   498  // Note that it only removes tombstones, it does not move elements.
   499  // Moving elements would do a better job but is infeasbile due to
   500  // iterator semantics.
   501  //
   502  // Pruning should only succeed if it can remove O(n) tombstones.
   503  // It would be bad if we did O(n) work to find 1 tombstone to remove.
   504  // Then the next insert would spend another O(n) work to find 1 more
   505  // tombstone to remove, etc.
   506  //
   507  // We really need to remove O(n) tombstones so we can pay for the cost
   508  // of finding them. If we can't, then we need to grow (which is also O(n),
   509  // but guarantees O(n) subsequent inserts can happen in constant time).
   510  func (t *table) pruneTombstones(typ *abi.MapType, m *Map) {
   511  	if t.tombstones()*10 < t.capacity { // 10% of capacity
   512  		// Not enough tombstones to be worth the effort.
   513  		return
   514  	}
   515  
   516  	// Bit set marking all the groups whose tombstones are needed.
   517  	var needed [(maxTableCapacity/abi.MapGroupSlots + 31) / 32]uint32
   518  
   519  	// Trace the probe sequence of every full entry.
   520  	for i := uint64(0); i <= t.groups.lengthMask; i++ {
   521  		g := t.groups.group(typ, i)
   522  		match := g.ctrls().matchFull()
   523  		for match != 0 {
   524  			j := match.first()
   525  			match = match.removeFirst()
   526  			key := g.key(typ, j)
   527  			if typ.IndirectKey() {
   528  				key = *((*unsafe.Pointer)(key))
   529  			}
   530  			if !typ.Key.Equal(key, key) {
   531  				// Key not equal to itself. We never have to find these
   532  				// keys on lookup (only on iteration), so we can break
   533  				// their probe sequences at will.
   534  				continue
   535  			}
   536  			// Walk probe sequence for this key.
   537  			// Each tombstone group we need to walk past is marked required.
   538  			hash := typ.Hasher(key, m.seed)
   539  			for seq := makeProbeSeq(h1(hash), t.groups.lengthMask); ; seq = seq.next() {
   540  				if seq.offset == i {
   541  					break // reached group of element in probe sequence
   542  				}
   543  				g := t.groups.group(typ, seq.offset)
   544  				m := g.ctrls().matchEmptyOrDeleted()
   545  				if m != 0 { // must be deleted, not empty, as we haven't found our key yet
   546  					// Mark this group's tombstone as required.
   547  					needed[seq.offset/32] |= 1 << (seq.offset % 32)
   548  				}
   549  			}
   550  		}
   551  		if g.ctrls().matchEmpty() != 0 {
   552  			// Also mark non-tombstone-containing groups, so we don't try
   553  			// to remove tombstones from them below.
   554  			needed[i/32] |= 1 << (i % 32)
   555  		}
   556  	}
   557  
   558  	// First, see if we can remove enough tombstones to restore capacity.
   559  	// This function is O(n), so only remove tombstones if we can remove
   560  	// enough of them to justify the O(n) cost.
   561  	cnt := 0
   562  	for i := uint64(0); i <= t.groups.lengthMask; i++ {
   563  		if needed[i/32]>>(i%32)&1 != 0 {
   564  			continue
   565  		}
   566  		g := t.groups.group(typ, i)
   567  		m := g.ctrls().matchEmptyOrDeleted() // must be deleted
   568  		cnt += m.count()
   569  	}
   570  	if cnt*10 < int(t.capacity) { // Can we restore 10% of capacity?
   571  		return // don't bother removing tombstones. Caller will grow instead.
   572  	}
   573  
   574  	// Prune unneeded tombstones.
   575  	for i := uint64(0); i <= t.groups.lengthMask; i++ {
   576  		if needed[i/32]>>(i%32)&1 != 0 {
   577  			continue
   578  		}
   579  		g := t.groups.group(typ, i)
   580  		m := g.ctrls().matchEmptyOrDeleted() // must be deleted
   581  		for m != 0 {
   582  			k := m.first()
   583  			m = m.removeFirst()
   584  			g.ctrls().set(k, ctrlEmpty)
   585  			t.growthLeft++
   586  		}
   587  		// TODO: maybe we could convert all slots at once
   588  		// using some bitvector trickery.
   589  	}
   590  }
   591  
   592  // tombstones returns the number of deleted (tombstone) entries in the table. A
   593  // tombstone is a slot that has been deleted but is still considered occupied
   594  // so as not to violate the probing invariant.
   595  func (t *table) tombstones() uint16 {
   596  	return (t.capacity*maxAvgGroupLoad)/abi.MapGroupSlots - t.used - t.growthLeft
   597  }
   598  
   599  // Clear deletes all entries from the map resulting in an empty map.
   600  func (t *table) Clear(typ *abi.MapType) {
   601  	mgl := t.maxGrowthLeft()
   602  	if t.used == 0 && t.growthLeft == mgl { // no current entries and no tombstones
   603  		return
   604  	}
   605  	// We only want to do the work of clearing slots
   606  	// if they are full. But we also don't want to do too
   607  	// much work to figure out whether a slot is full or not,
   608  	// especially if clearing a slot is cheap.
   609  	//  1) We decide group-by-group instead of slot-by-slot.
   610  	//     If any slot in a group is full, we zero the whole group.
   611  	//  2) If groups are unlikely to be empty, don't bother
   612  	//     testing for it.
   613  	//  3) If groups are 50%/50% likely to be empty, also don't
   614  	//     bother testing, as it confuses the branch predictor. See #75097.
   615  	//  4) But if a group is really large, do the test anyway, as
   616  	//     clearing is expensive.
   617  	fullTest := uint64(t.used)*4 <= t.groups.lengthMask // less than ~0.25 entries per group -> >3/4 empty groups
   618  	if typ.SlotSize > 32 {
   619  		// For large slots, it is always worth doing the test first.
   620  		fullTest = true
   621  	}
   622  	if fullTest {
   623  		for i := uint64(0); i <= t.groups.lengthMask; i++ {
   624  			g := t.groups.group(typ, i)
   625  			if g.ctrls().anyFull() {
   626  				typedmemclr(typ.Group, g.data)
   627  			}
   628  			g.ctrls().setEmpty()
   629  		}
   630  	} else {
   631  		for i := uint64(0); i <= t.groups.lengthMask; i++ {
   632  			g := t.groups.group(typ, i)
   633  			typedmemclr(typ.Group, g.data)
   634  			g.ctrls().setEmpty()
   635  		}
   636  	}
   637  	t.used = 0
   638  	t.growthLeft = mgl
   639  }
   640  
   641  type Iter struct {
   642  	key  unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
   643  	elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
   644  	typ  *abi.MapType
   645  	m    *Map
   646  
   647  	// Randomize iteration order by starting iteration at a random slot
   648  	// offset. The offset into the directory uses a separate offset, as it
   649  	// must adjust when the directory grows.
   650  	entryOffset uint64
   651  	dirOffset   uint64
   652  
   653  	// Snapshot of Map.clearSeq at iteration initialization time. Used to
   654  	// detect clear during iteration.
   655  	clearSeq uint64
   656  
   657  	// Value of Map.globalDepth during the last call to Next. Used to
   658  	// detect directory grow during iteration.
   659  	globalDepth uint8
   660  
   661  	// dirIdx is the current directory index, prior to adjustment by
   662  	// dirOffset.
   663  	dirIdx int
   664  
   665  	// tab is the table at dirIdx during the previous call to Next.
   666  	tab *table
   667  
   668  	// group is the group at entryIdx during the previous call to Next.
   669  	group groupReference
   670  
   671  	// entryIdx is the current entry index, prior to adjustment by entryOffset.
   672  	// The lower 3 bits of the index are the slot index, and the upper bits
   673  	// are the group index.
   674  	entryIdx uint64
   675  }
   676  
   677  // Init initializes Iter for iteration.
   678  func (it *Iter) Init(typ *abi.MapType, m *Map) {
   679  	it.typ = typ
   680  
   681  	if m == nil || m.used == 0 {
   682  		return
   683  	}
   684  
   685  	dirIdx := 0
   686  	var groupSmall groupReference
   687  	if m.dirLen <= 0 {
   688  		// Use dirIdx == -1 as sentinel for small maps.
   689  		dirIdx = -1
   690  		groupSmall.data = m.dirPtr
   691  	}
   692  
   693  	it.m = m
   694  	it.entryOffset = rand()
   695  	it.dirOffset = rand()
   696  	it.globalDepth = m.globalDepth
   697  	it.dirIdx = dirIdx
   698  	it.group = groupSmall
   699  	it.clearSeq = m.clearSeq
   700  }
   701  
   702  func (it *Iter) Initialized() bool {
   703  	return it.typ != nil
   704  }
   705  
   706  // Map returns the map this iterator is iterating over.
   707  func (it *Iter) Map() *Map {
   708  	return it.m
   709  }
   710  
   711  // Key returns a pointer to the current key. nil indicates end of iteration.
   712  //
   713  // Must not be called prior to Next.
   714  func (it *Iter) Key() unsafe.Pointer {
   715  	return it.key
   716  }
   717  
   718  // Elem returns a pointer to the current element. nil indicates end of
   719  // iteration.
   720  //
   721  // Must not be called prior to Next.
   722  func (it *Iter) Elem() unsafe.Pointer {
   723  	return it.elem
   724  }
   725  
   726  func (it *Iter) nextDirIdx() {
   727  	// Skip other entries in the directory that refer to the same
   728  	// logical table. There are two cases of this:
   729  	//
   730  	// Consider this directory:
   731  	//
   732  	// - 0: *t1
   733  	// - 1: *t1
   734  	// - 2: *t2a
   735  	// - 3: *t2b
   736  	//
   737  	// At some point, the directory grew to accommodate a split of
   738  	// t2. t1 did not split, so entries 0 and 1 both point to t1.
   739  	// t2 did split, so the two halves were installed in entries 2
   740  	// and 3.
   741  	//
   742  	// If dirIdx is 0 and it.tab is t1, then we should skip past
   743  	// entry 1 to avoid repeating t1.
   744  	//
   745  	// If dirIdx is 2 and it.tab is t2 (pre-split), then we should
   746  	// skip past entry 3 because our pre-split t2 already covers
   747  	// all keys from t2a and t2b (except for new insertions, which
   748  	// iteration need not return).
   749  	//
   750  	// We can achieve both of these by using to difference between
   751  	// the directory and table depth to compute how many entries
   752  	// the table covers.
   753  	entries := 1 << (it.m.globalDepth - it.tab.localDepth)
   754  	it.dirIdx += entries
   755  	it.tab = nil
   756  	it.group = groupReference{}
   757  	it.entryIdx = 0
   758  }
   759  
   760  // Return the appropriate key/elem for key at slotIdx index within it.group, if
   761  // any.
   762  func (it *Iter) grownKeyElem(key unsafe.Pointer, slotIdx uintptr) (unsafe.Pointer, unsafe.Pointer, bool) {
   763  	newKey, newElem, ok := it.m.getWithKey(it.typ, key)
   764  	if !ok {
   765  		// Key has likely been deleted, and
   766  		// should be skipped.
   767  		//
   768  		// One exception is keys that don't
   769  		// compare equal to themselves (e.g.,
   770  		// NaN). These keys cannot be looked
   771  		// up, so getWithKey will fail even if
   772  		// the key exists.
   773  		//
   774  		// However, we are in luck because such
   775  		// keys cannot be updated and they
   776  		// cannot be deleted except with clear.
   777  		// Thus if no clear has occurred, the
   778  		// key/elem must still exist exactly as
   779  		// in the old groups, so we can return
   780  		// them from there.
   781  		//
   782  		// TODO(prattmic): Consider checking
   783  		// clearSeq early. If a clear occurred,
   784  		// Next could always return
   785  		// immediately, as iteration doesn't
   786  		// need to return anything added after
   787  		// clear.
   788  		if it.clearSeq == it.m.clearSeq && !it.typ.Key.Equal(key, key) {
   789  			elem := it.group.elem(it.typ, slotIdx)
   790  			if it.typ.IndirectElem() {
   791  				elem = *((*unsafe.Pointer)(elem))
   792  			}
   793  			return key, elem, true
   794  		}
   795  
   796  		// This entry doesn't exist anymore.
   797  		return nil, nil, false
   798  	}
   799  
   800  	return newKey, newElem, true
   801  }
   802  
   803  // Next proceeds to the next element in iteration, which can be accessed via
   804  // the Key and Elem methods.
   805  //
   806  // The table can be mutated during iteration, though there is no guarantee that
   807  // the mutations will be visible to the iteration.
   808  //
   809  // Init must be called prior to Next.
   810  func (it *Iter) Next() {
   811  	if it.m == nil {
   812  		// Map was empty at Iter.Init.
   813  		it.key = nil
   814  		it.elem = nil
   815  		return
   816  	}
   817  
   818  	if it.m.writing != 0 {
   819  		fatal("concurrent map iteration and map write")
   820  		return
   821  	}
   822  
   823  	if it.dirIdx < 0 {
   824  		// Map was small at Init.
   825  		for ; it.entryIdx < abi.MapGroupSlots; it.entryIdx++ {
   826  			k := uintptr(it.entryIdx+it.entryOffset) % abi.MapGroupSlots
   827  
   828  			if (it.group.ctrls().get(k) & ctrlEmpty) == ctrlEmpty {
   829  				// Empty or deleted.
   830  				continue
   831  			}
   832  
   833  			key := it.group.key(it.typ, k)
   834  			if it.typ.IndirectKey() {
   835  				key = *((*unsafe.Pointer)(key))
   836  			}
   837  
   838  			// As below, if we have grown to a full map since Init,
   839  			// we continue to use the old group to decide the keys
   840  			// to return, but must look them up again in the new
   841  			// tables.
   842  			grown := it.m.dirLen > 0
   843  			var elem unsafe.Pointer
   844  			if grown {
   845  				var ok bool
   846  				newKey, newElem, ok := it.m.getWithKey(it.typ, key)
   847  				if !ok {
   848  					// See comment below.
   849  					if it.clearSeq == it.m.clearSeq && !it.typ.Key.Equal(key, key) {
   850  						elem = it.group.elem(it.typ, k)
   851  						if it.typ.IndirectElem() {
   852  							elem = *((*unsafe.Pointer)(elem))
   853  						}
   854  					} else {
   855  						continue
   856  					}
   857  				} else {
   858  					key = newKey
   859  					elem = newElem
   860  				}
   861  			} else {
   862  				elem = it.group.elem(it.typ, k)
   863  				if it.typ.IndirectElem() {
   864  					elem = *((*unsafe.Pointer)(elem))
   865  				}
   866  			}
   867  
   868  			it.entryIdx++
   869  			it.key = key
   870  			it.elem = elem
   871  			return
   872  		}
   873  		it.key = nil
   874  		it.elem = nil
   875  		return
   876  	}
   877  
   878  	if it.globalDepth != it.m.globalDepth {
   879  		// Directory has grown since the last call to Next. Adjust our
   880  		// directory index.
   881  		//
   882  		// Consider:
   883  		//
   884  		// Before:
   885  		// - 0: *t1
   886  		// - 1: *t2  <- dirIdx
   887  		//
   888  		// After:
   889  		// - 0: *t1a (split)
   890  		// - 1: *t1b (split)
   891  		// - 2: *t2  <- dirIdx
   892  		// - 3: *t2
   893  		//
   894  		// That is, we want to double the current index when the
   895  		// directory size doubles (or quadruple when the directory size
   896  		// quadruples, etc).
   897  		//
   898  		// The actual (randomized) dirIdx is computed below as:
   899  		//
   900  		// dirIdx := (it.dirIdx + it.dirOffset) % it.m.dirLen
   901  		//
   902  		// Multiplication is associative across modulo operations,
   903  		// A * (B % C) = (A * B) % (A * C),
   904  		// provided that A is positive.
   905  		//
   906  		// Thus we can achieve this by adjusting it.dirIdx,
   907  		// it.dirOffset, and it.m.dirLen individually.
   908  		orders := it.m.globalDepth - it.globalDepth
   909  		it.dirIdx <<= orders
   910  		it.dirOffset <<= orders
   911  		// it.m.dirLen was already adjusted when the directory grew.
   912  
   913  		it.globalDepth = it.m.globalDepth
   914  	}
   915  
   916  	// Continue iteration until we find a full slot.
   917  	for ; it.dirIdx < it.m.dirLen; it.nextDirIdx() {
   918  		// Resolve the table.
   919  		if it.tab == nil {
   920  			dirIdx := int((uint64(it.dirIdx) + it.dirOffset) & uint64(it.m.dirLen-1))
   921  			newTab := it.m.directoryAt(uintptr(dirIdx))
   922  			if newTab.index != dirIdx {
   923  				// Normally we skip past all duplicates of the
   924  				// same entry in the table (see updates to
   925  				// it.dirIdx at the end of the loop below), so
   926  				// this case wouldn't occur.
   927  				//
   928  				// But on the very first call, we have a
   929  				// completely randomized dirIdx that may refer
   930  				// to a middle of a run of tables in the
   931  				// directory. Do a one-time adjustment of the
   932  				// offset to ensure we start at first index for
   933  				// newTable.
   934  				diff := dirIdx - newTab.index
   935  				it.dirOffset -= uint64(diff)
   936  				dirIdx = newTab.index
   937  			}
   938  			it.tab = newTab
   939  		}
   940  
   941  		// N.B. Use it.tab, not newTab. It is important to use the old
   942  		// table for key selection if the table has grown. See comment
   943  		// on grown below.
   944  
   945  		entryMask := uint64(it.tab.capacity) - 1
   946  		if it.entryIdx > entryMask {
   947  			// Continue to next table.
   948  			continue
   949  		}
   950  
   951  		// Fast path: skip matching and directly check if entryIdx is a
   952  		// full slot.
   953  		//
   954  		// In the slow path below, we perform an 8-slot match check to
   955  		// look for full slots within the group.
   956  		//
   957  		// However, with a max load factor of 7/8, each slot in a
   958  		// mostly full map has a high probability of being full. Thus
   959  		// it is cheaper to check a single slot than do a full control
   960  		// match.
   961  
   962  		entryIdx := (it.entryIdx + it.entryOffset) & entryMask
   963  		slotIdx := uintptr(entryIdx & (abi.MapGroupSlots - 1))
   964  		if slotIdx == 0 || it.group.data == nil {
   965  			// Only compute the group (a) when we switch
   966  			// groups (slotIdx rolls over) and (b) on the
   967  			// first iteration in this table (slotIdx may
   968  			// not be zero due to entryOffset).
   969  			groupIdx := entryIdx >> abi.MapGroupSlotsBits
   970  			it.group = it.tab.groups.group(it.typ, groupIdx)
   971  		}
   972  
   973  		if (it.group.ctrls().get(slotIdx) & ctrlEmpty) == 0 {
   974  			// Slot full.
   975  
   976  			key := it.group.key(it.typ, slotIdx)
   977  			if it.typ.IndirectKey() {
   978  				key = *((*unsafe.Pointer)(key))
   979  			}
   980  
   981  			grown := it.tab.index == -1
   982  			var elem unsafe.Pointer
   983  			if grown {
   984  				newKey, newElem, ok := it.grownKeyElem(key, slotIdx)
   985  				if !ok {
   986  					// This entry doesn't exist
   987  					// anymore. Continue to the
   988  					// next one.
   989  					goto next
   990  				} else {
   991  					key = newKey
   992  					elem = newElem
   993  				}
   994  			} else {
   995  				elem = it.group.elem(it.typ, slotIdx)
   996  				if it.typ.IndirectElem() {
   997  					elem = *((*unsafe.Pointer)(elem))
   998  				}
   999  			}
  1000  
  1001  			it.entryIdx++
  1002  			it.key = key
  1003  			it.elem = elem
  1004  			return
  1005  		}
  1006  
  1007  	next:
  1008  		it.entryIdx++
  1009  
  1010  		// Slow path: use a match on the control word to jump ahead to
  1011  		// the next full slot.
  1012  		//
  1013  		// This is highly effective for maps with particularly low load
  1014  		// (e.g., map allocated with large hint but few insertions).
  1015  		//
  1016  		// For maps with medium load (e.g., 3-4 empty slots per group)
  1017  		// it also tends to work pretty well. Since slots within a
  1018  		// group are filled in order, then if there have been no
  1019  		// deletions, a match will allow skipping past all empty slots
  1020  		// at once.
  1021  		//
  1022  		// Note: it is tempting to cache the group match result in the
  1023  		// iterator to use across Next calls. However because entries
  1024  		// may be deleted between calls later calls would still need to
  1025  		// double-check the control value.
  1026  
  1027  		var groupMatch bitset
  1028  		for it.entryIdx <= entryMask {
  1029  			entryIdx := (it.entryIdx + it.entryOffset) & entryMask
  1030  			slotIdx := uintptr(entryIdx & (abi.MapGroupSlots - 1))
  1031  
  1032  			if slotIdx == 0 || it.group.data == nil {
  1033  				// Only compute the group (a) when we switch
  1034  				// groups (slotIdx rolls over) and (b) on the
  1035  				// first iteration in this table (slotIdx may
  1036  				// not be zero due to entryOffset).
  1037  				groupIdx := entryIdx >> abi.MapGroupSlotsBits
  1038  				it.group = it.tab.groups.group(it.typ, groupIdx)
  1039  			}
  1040  
  1041  			if groupMatch == 0 {
  1042  				groupMatch = it.group.ctrls().matchFull()
  1043  
  1044  				if slotIdx != 0 {
  1045  					// Starting in the middle of the group.
  1046  					// Ignore earlier groups.
  1047  					groupMatch = groupMatch.removeBelow(slotIdx)
  1048  				}
  1049  
  1050  				// Skip over groups that are composed of only empty or
  1051  				// deleted slots.
  1052  				if groupMatch == 0 {
  1053  					// Jump past remaining slots in this
  1054  					// group.
  1055  					it.entryIdx += abi.MapGroupSlots - uint64(slotIdx)
  1056  					continue
  1057  				}
  1058  
  1059  				i := groupMatch.first()
  1060  				it.entryIdx += uint64(i - slotIdx)
  1061  				if it.entryIdx > entryMask {
  1062  					// Past the end of this table's iteration.
  1063  					continue
  1064  				}
  1065  				entryIdx += uint64(i - slotIdx)
  1066  				slotIdx = i
  1067  			}
  1068  
  1069  			key := it.group.key(it.typ, slotIdx)
  1070  			if it.typ.IndirectKey() {
  1071  				key = *((*unsafe.Pointer)(key))
  1072  			}
  1073  
  1074  			// If the table has changed since the last
  1075  			// call, then it has grown or split. In this
  1076  			// case, further mutations (changes to
  1077  			// key->elem or deletions) will not be visible
  1078  			// in our snapshot table. Instead we must
  1079  			// consult the new table by doing a full
  1080  			// lookup.
  1081  			//
  1082  			// We still use our old table to decide which
  1083  			// keys to lookup in order to avoid returning
  1084  			// the same key twice.
  1085  			grown := it.tab.index == -1
  1086  			var elem unsafe.Pointer
  1087  			if grown {
  1088  				newKey, newElem, ok := it.grownKeyElem(key, slotIdx)
  1089  				if !ok {
  1090  					// This entry doesn't exist anymore.
  1091  					// Continue to the next one.
  1092  					groupMatch = groupMatch.removeFirst()
  1093  					if groupMatch == 0 {
  1094  						// No more entries in this
  1095  						// group. Continue to next
  1096  						// group.
  1097  						it.entryIdx += abi.MapGroupSlots - uint64(slotIdx)
  1098  						continue
  1099  					}
  1100  
  1101  					// Next full slot.
  1102  					i := groupMatch.first()
  1103  					it.entryIdx += uint64(i - slotIdx)
  1104  					continue
  1105  				} else {
  1106  					key = newKey
  1107  					elem = newElem
  1108  				}
  1109  			} else {
  1110  				elem = it.group.elem(it.typ, slotIdx)
  1111  				if it.typ.IndirectElem() {
  1112  					elem = *((*unsafe.Pointer)(elem))
  1113  				}
  1114  			}
  1115  
  1116  			// Jump ahead to the next full slot or next group.
  1117  			groupMatch = groupMatch.removeFirst()
  1118  			if groupMatch == 0 {
  1119  				// No more entries in
  1120  				// this group. Continue
  1121  				// to next group.
  1122  				it.entryIdx += abi.MapGroupSlots - uint64(slotIdx)
  1123  			} else {
  1124  				// Next full slot.
  1125  				i := groupMatch.first()
  1126  				it.entryIdx += uint64(i - slotIdx)
  1127  			}
  1128  
  1129  			it.key = key
  1130  			it.elem = elem
  1131  			return
  1132  		}
  1133  
  1134  		// Continue to next table.
  1135  	}
  1136  
  1137  	it.key = nil
  1138  	it.elem = nil
  1139  	return
  1140  }
  1141  
  1142  // Replaces the table with one larger table or two split tables to fit more
  1143  // entries. Since the table is replaced, t is now stale and should not be
  1144  // modified.
  1145  func (t *table) rehash(typ *abi.MapType, m *Map) {
  1146  	// TODO(prattmic): SwissTables typically perform a "rehash in place"
  1147  	// operation which recovers capacity consumed by tombstones without growing
  1148  	// the table by reordering slots as necessary to maintain the probe
  1149  	// invariant while eliminating all tombstones.
  1150  	//
  1151  	// However, it is unclear how to make rehash in place work with
  1152  	// iteration. Since iteration simply walks through all slots in order
  1153  	// (with random start offset), reordering the slots would break
  1154  	// iteration.
  1155  	//
  1156  	// As an alternative, we could do a "resize" to new groups allocation
  1157  	// of the same size. This would eliminate the tombstones, but using a
  1158  	// new allocation, so the existing grow support in iteration would
  1159  	// continue to work.
  1160  
  1161  	newCapacity := 2 * t.capacity
  1162  	if newCapacity <= maxTableCapacity {
  1163  		t.grow(typ, m, newCapacity)
  1164  		return
  1165  	}
  1166  
  1167  	t.split(typ, m)
  1168  }
  1169  
  1170  // Bitmask for the last selection bit at this depth.
  1171  func localDepthMask(localDepth uint8) uintptr {
  1172  	if !Use64BitHash {
  1173  		return uintptr(1) << (32 - localDepth)
  1174  	}
  1175  	return uintptr(1) << (64 - localDepth)
  1176  }
  1177  
  1178  // split the table into two, installing the new tables in the map directory.
  1179  func (t *table) split(typ *abi.MapType, m *Map) {
  1180  	localDepth := t.localDepth
  1181  	localDepth++
  1182  
  1183  	// TODO: is this the best capacity?
  1184  	left := newTable(typ, maxTableCapacity, -1, localDepth)
  1185  	right := newTable(typ, maxTableCapacity, -1, localDepth)
  1186  
  1187  	// Split in half at the localDepth bit from the top.
  1188  	mask := localDepthMask(localDepth)
  1189  
  1190  	for i := uint64(0); i <= t.groups.lengthMask; i++ {
  1191  		g := t.groups.group(typ, i)
  1192  		for j := uintptr(0); j < abi.MapGroupSlots; j++ {
  1193  			if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
  1194  				// Empty or deleted
  1195  				continue
  1196  			}
  1197  
  1198  			key := g.key(typ, j)
  1199  			if typ.IndirectKey() {
  1200  				key = *((*unsafe.Pointer)(key))
  1201  			}
  1202  
  1203  			elem := g.elem(typ, j)
  1204  			if typ.IndirectElem() {
  1205  				elem = *((*unsafe.Pointer)(elem))
  1206  			}
  1207  
  1208  			hash := typ.Hasher(key, m.seed)
  1209  			var newTable *table
  1210  			if hash&mask == 0 {
  1211  				newTable = left
  1212  			} else {
  1213  				newTable = right
  1214  			}
  1215  			newTable.uncheckedPutSlot(typ, hash, key, elem)
  1216  		}
  1217  	}
  1218  
  1219  	m.installTableSplit(t, left, right)
  1220  	t.index = -1
  1221  }
  1222  
  1223  // grow the capacity of the table by allocating a new table with a bigger array
  1224  // and uncheckedPutting each element of the table into the new table (we know
  1225  // that no insertion here will Put an already-present value), and discard the
  1226  // old table.
  1227  func (t *table) grow(typ *abi.MapType, m *Map, newCapacity uint16) {
  1228  	newTable := newTable(typ, uint64(newCapacity), t.index, t.localDepth)
  1229  
  1230  	if t.capacity > 0 {
  1231  		for i := uint64(0); i <= t.groups.lengthMask; i++ {
  1232  			g := t.groups.group(typ, i)
  1233  			for j := uintptr(0); j < abi.MapGroupSlots; j++ {
  1234  				if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
  1235  					// Empty or deleted
  1236  					continue
  1237  				}
  1238  
  1239  				key := g.key(typ, j)
  1240  				if typ.IndirectKey() {
  1241  					key = *((*unsafe.Pointer)(key))
  1242  				}
  1243  
  1244  				elem := g.elem(typ, j)
  1245  				if typ.IndirectElem() {
  1246  					elem = *((*unsafe.Pointer)(elem))
  1247  				}
  1248  
  1249  				hash := typ.Hasher(key, m.seed)
  1250  
  1251  				newTable.uncheckedPutSlot(typ, hash, key, elem)
  1252  			}
  1253  		}
  1254  	}
  1255  
  1256  	newTable.checkInvariants(typ, m)
  1257  	m.replaceTable(newTable)
  1258  	t.index = -1
  1259  }
  1260  
  1261  // probeSeq maintains the state for a probe sequence that iterates through the
  1262  // groups in a table. The sequence is a triangular progression of the form
  1263  //
  1264  //	p(i) := (i^2 + i)/2 + hash (mod mask+1)
  1265  //
  1266  // The sequence effectively outputs the indexes of *groups*. The group
  1267  // machinery allows us to check an entire group with minimal branching.
  1268  //
  1269  // It turns out that this probe sequence visits every group exactly once if
  1270  // the number of groups is a power of two, since (i^2+i)/2 is a bijection in
  1271  // Z/(2^m). See https://en.wikipedia.org/wiki/Quadratic_probing
  1272  type probeSeq struct {
  1273  	mask   uint64
  1274  	offset uint64
  1275  	index  uint64
  1276  }
  1277  
  1278  func makeProbeSeq(hash uintptr, mask uint64) probeSeq {
  1279  	return probeSeq{
  1280  		mask:   mask,
  1281  		offset: uint64(hash) & mask,
  1282  		index:  0,
  1283  	}
  1284  }
  1285  
  1286  func (s probeSeq) next() probeSeq {
  1287  	s.index++
  1288  	s.offset = (s.offset + s.index) & s.mask
  1289  	return s
  1290  }
  1291  
  1292  func (t *table) clone(typ *abi.MapType) *table {
  1293  	// Shallow copy the table structure.
  1294  	t2 := new(table)
  1295  	*t2 = *t
  1296  	t = t2
  1297  
  1298  	// We need to just deep copy the groups.data field.
  1299  	oldGroups := t.groups
  1300  	newGroups := newGroups(typ, oldGroups.lengthMask+1)
  1301  	for i := uint64(0); i <= oldGroups.lengthMask; i++ {
  1302  		oldGroup := oldGroups.group(typ, i)
  1303  		newGroup := newGroups.group(typ, i)
  1304  		cloneGroup(typ, newGroup, oldGroup)
  1305  	}
  1306  	t.groups = newGroups
  1307  
  1308  	return t
  1309  }
  1310
View as plain text