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