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 implements Go's builtin map type.
     6  package maps
     7  
     8  import (
     9  	"internal/abi"
    10  	"internal/goarch"
    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.SwissMapGroupSlots`.
    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 indicies.
    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.SwissMapGroupSlots
    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.SwissMapType, capacity uint64, index int, localDepth uint8) *table {
    75  	if capacity < abi.SwissMapGroupSlots {
    76  		capacity = abi.SwissMapGroupSlots
    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.SwissMapType, capacity uint16) {
   103  	groupCount := uint64(capacity) / abi.SwissMapGroupSlots
   104  	t.groups = newGroups(typ, groupCount)
   105  	t.capacity = capacity
   106  	t.resetGrowthLeft()
   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  // Preconditions: table must be empty.
   115  func (t *table) resetGrowthLeft() {
   116  	var growthLeft 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.SwissMapGroupSlots {
   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  		growthLeft = t.capacity - 1
   129  	} else {
   130  		if t.capacity*maxAvgGroupLoad < t.capacity {
   131  			// TODO(prattmic): Do something cleaner.
   132  			panic("overflow")
   133  		}
   134  		growthLeft = (t.capacity * maxAvgGroupLoad) / abi.SwissMapGroupSlots
   135  	}
   136  	t.growthLeft = growthLeft
   137  }
   138  
   139  func (t *table) Used() uint64 {
   140  	return uint64(t.used)
   141  }
   142  
   143  // Get performs a lookup of the key that key points to. It returns a pointer to
   144  // the element, or false if the key doesn't exist.
   145  func (t *table) Get(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool) {
   146  	// TODO(prattmic): We could avoid hashing in a variety of special
   147  	// cases.
   148  	//
   149  	// - One entry maps could just directly compare the single entry
   150  	//   without hashing.
   151  	// - String keys could do quick checks of a few bytes before hashing.
   152  	hash := typ.Hasher(key, m.seed)
   153  	_, elem, ok := t.getWithKey(typ, hash, key)
   154  	return elem, ok
   155  }
   156  
   157  // getWithKey performs a lookup of key, returning a pointer to the version of
   158  // the key in the map in addition to the element.
   159  //
   160  // This is relevant when multiple different key values compare equal (e.g.,
   161  // +0.0 and -0.0). When a grow occurs during iteration, iteration perform a
   162  // lookup of keys from the old group in the new group in order to correctly
   163  // expose updated elements. For NeedsKeyUpdate keys, iteration also must return
   164  // the new key value, not the old key value.
   165  // hash must be the hash of the key.
   166  func (t *table) getWithKey(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
   167  	// To find the location of a key in the table, we compute hash(key). From
   168  	// h1(hash(key)) and the capacity, we construct a probeSeq that visits
   169  	// every group of slots in some interesting order. See [probeSeq].
   170  	//
   171  	// We walk through these indices. At each index, we select the entire
   172  	// group starting with that index and extract potential candidates:
   173  	// occupied slots with a control byte equal to h2(hash(key)). The key
   174  	// at candidate slot i is compared with key; if key == g.slot(i).key
   175  	// we are done and return the slot; if there is an empty slot in the
   176  	// group, we stop and return an error; otherwise we continue to the
   177  	// next probe index. Tombstones (ctrlDeleted) effectively behave like
   178  	// full slots that never match the value we're looking for.
   179  	//
   180  	// The h2 bits ensure when we compare a key we are likely to have
   181  	// actually found the object. That is, the chance is low that keys
   182  	// compare false. Thus, when we search for an object, we are unlikely
   183  	// to call Equal many times. This likelihood can be analyzed as follows
   184  	// (assuming that h2 is a random enough hash function).
   185  	//
   186  	// Let's assume that there are k "wrong" objects that must be examined
   187  	// in a probe sequence. For example, when doing a find on an object
   188  	// that is in the table, k is the number of objects between the start
   189  	// of the probe sequence and the final found object (not including the
   190  	// final found object). The expected number of objects with an h2 match
   191  	// is then k/128. Measurements and analysis indicate that even at high
   192  	// load factors, k is less than 32, meaning that the number of false
   193  	// positive comparisons we must perform is less than 1/8 per find.
   194  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   195  	for ; ; seq = seq.next() {
   196  		g := t.groups.group(typ, seq.offset)
   197  
   198  		match := g.ctrls().matchH2(h2(hash))
   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.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool) {
   227  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   228  	for ; ; seq = seq.next() {
   229  		g := t.groups.group(typ, seq.offset)
   230  
   231  		match := g.ctrls().matchH2(h2(hash))
   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.SwissMapType, 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  	for ; ; seq = seq.next() {
   275  		g := t.groups.group(typ, seq.offset)
   276  		match := g.ctrls().matchH2(h2(hash))
   277  
   278  		// Look for an existing slot containing this key.
   279  		for match != 0 {
   280  			i := match.first()
   281  
   282  			slotKey := g.key(typ, i)
   283  			if typ.IndirectKey() {
   284  				slotKey = *((*unsafe.Pointer)(slotKey))
   285  			}
   286  			if typ.Key.Equal(key, slotKey) {
   287  				if typ.NeedKeyUpdate() {
   288  					typedmemmove(typ.Key, slotKey, key)
   289  				}
   290  
   291  				slotElem := g.elem(typ, i)
   292  				if typ.IndirectElem() {
   293  					slotElem = *((*unsafe.Pointer)(slotElem))
   294  				}
   295  
   296  				t.checkInvariants(typ, m)
   297  				return slotElem, true
   298  			}
   299  			match = match.removeFirst()
   300  		}
   301  
   302  		// No existing slot for this key in this group. Is this the end
   303  		// of the probe sequence?
   304  		match = g.ctrls().matchEmptyOrDeleted()
   305  		if match == 0 {
   306  			continue // nothing but filled slots. Keep probing.
   307  		}
   308  		i := match.first()
   309  		if g.ctrls().get(i) == ctrlDeleted {
   310  			// There are some deleted slots. Remember
   311  			// the first one, and keep probing.
   312  			if firstDeletedGroup.data == nil {
   313  				firstDeletedGroup = g
   314  				firstDeletedSlot = i
   315  			}
   316  			continue
   317  		}
   318  		// We've found an empty slot, which means we've reached the end of
   319  		// the probe sequence.
   320  
   321  		// If we found a deleted slot along the way, we can
   322  		// replace it without consuming growthLeft.
   323  		if firstDeletedGroup.data != nil {
   324  			g = firstDeletedGroup
   325  			i = firstDeletedSlot
   326  			t.growthLeft++ // will be decremented below to become a no-op.
   327  		}
   328  
   329  		// If there is room left to grow, just insert the new entry.
   330  		if t.growthLeft > 0 {
   331  			slotKey := g.key(typ, i)
   332  			if typ.IndirectKey() {
   333  				kmem := newobject(typ.Key)
   334  				*(*unsafe.Pointer)(slotKey) = kmem
   335  				slotKey = kmem
   336  			}
   337  			typedmemmove(typ.Key, slotKey, key)
   338  
   339  			slotElem := g.elem(typ, i)
   340  			if typ.IndirectElem() {
   341  				emem := newobject(typ.Elem)
   342  				*(*unsafe.Pointer)(slotElem) = emem
   343  				slotElem = emem
   344  			}
   345  
   346  			g.ctrls().set(i, ctrl(h2(hash)))
   347  			t.growthLeft--
   348  			t.used++
   349  			m.used++
   350  
   351  			t.checkInvariants(typ, m)
   352  			return slotElem, true
   353  		}
   354  
   355  		t.rehash(typ, m)
   356  		return nil, false
   357  	}
   358  }
   359  
   360  // uncheckedPutSlot inserts an entry known not to be in the table, returning an
   361  // entry to the element slot where the element should be written. Used by
   362  // PutSlot after it has failed to find an existing entry to overwrite duration
   363  // insertion.
   364  //
   365  // Updates growthLeft if necessary, but does not update used.
   366  //
   367  // Requires that the entry does not exist in the table, and that the table has
   368  // room for another element without rehashing.
   369  //
   370  // Requires that there are no deleted entries in the table.
   371  //
   372  // Never returns nil.
   373  func (t *table) uncheckedPutSlot(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer {
   374  	if t.growthLeft == 0 {
   375  		panic("invariant failed: growthLeft is unexpectedly 0")
   376  	}
   377  
   378  	// Given key and its hash hash(key), to insert it, we construct a
   379  	// probeSeq, and use it to find the first group with an unoccupied (empty
   380  	// or deleted) slot. We place the key/value into the first such slot in
   381  	// the group and mark it as full with key's H2.
   382  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   383  	for ; ; seq = seq.next() {
   384  		g := t.groups.group(typ, seq.offset)
   385  
   386  		match := g.ctrls().matchEmptyOrDeleted()
   387  		if match != 0 {
   388  			i := match.first()
   389  
   390  			slotKey := g.key(typ, i)
   391  			if typ.IndirectKey() {
   392  				kmem := newobject(typ.Key)
   393  				*(*unsafe.Pointer)(slotKey) = kmem
   394  				slotKey = kmem
   395  			}
   396  			typedmemmove(typ.Key, slotKey, key)
   397  
   398  			slotElem := g.elem(typ, i)
   399  			if typ.IndirectElem() {
   400  				emem := newobject(typ.Elem)
   401  				*(*unsafe.Pointer)(slotElem) = emem
   402  				slotElem = emem
   403  			}
   404  
   405  			t.growthLeft--
   406  			g.ctrls().set(i, ctrl(h2(hash)))
   407  			return slotElem
   408  		}
   409  	}
   410  }
   411  
   412  func (t *table) Delete(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer) {
   413  	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
   414  	for ; ; seq = seq.next() {
   415  		g := t.groups.group(typ, seq.offset)
   416  		match := g.ctrls().matchH2(h2(hash))
   417  
   418  		for match != 0 {
   419  			i := match.first()
   420  
   421  			slotKey := g.key(typ, i)
   422  			origSlotKey := slotKey
   423  			if typ.IndirectKey() {
   424  				slotKey = *((*unsafe.Pointer)(slotKey))
   425  			}
   426  
   427  			if typ.Key.Equal(key, slotKey) {
   428  				t.used--
   429  				m.used--
   430  
   431  				if typ.IndirectKey() {
   432  					// Clearing the pointer is sufficient.
   433  					*(*unsafe.Pointer)(origSlotKey) = nil
   434  				} else if typ.Key.Pointers() {
   435  					// Only bothing clear the key if there
   436  					// are pointers in it.
   437  					typedmemclr(typ.Key, slotKey)
   438  				}
   439  
   440  				slotElem := g.elem(typ, i)
   441  				if typ.IndirectElem() {
   442  					// Clearing the pointer is sufficient.
   443  					*(*unsafe.Pointer)(slotElem) = nil
   444  				} else {
   445  					// Unlike keys, always clear the elem (even if
   446  					// it contains no pointers), as compound
   447  					// assignment operations depend on cleared
   448  					// deleted values. See
   449  					// https://go.dev/issue/25936.
   450  					typedmemclr(typ.Elem, slotElem)
   451  				}
   452  
   453  				// Only a full group can appear in the middle
   454  				// of a probe sequence (a group with at least
   455  				// one empty slot terminates probing). Once a
   456  				// group becomes full, it stays full until
   457  				// rehashing/resizing. So if the group isn't
   458  				// full now, we can simply remove the element.
   459  				// Otherwise, we create a tombstone to mark the
   460  				// slot as deleted.
   461  				if g.ctrls().matchEmpty() != 0 {
   462  					g.ctrls().set(i, ctrlEmpty)
   463  					t.growthLeft++
   464  				} else {
   465  					g.ctrls().set(i, ctrlDeleted)
   466  				}
   467  
   468  				t.checkInvariants(typ, m)
   469  				return
   470  			}
   471  			match = match.removeFirst()
   472  		}
   473  
   474  		match = g.ctrls().matchEmpty()
   475  		if match != 0 {
   476  			// Finding an empty slot means we've reached the end of
   477  			// the probe sequence.
   478  			return
   479  		}
   480  	}
   481  }
   482  
   483  // tombstones returns the number of deleted (tombstone) entries in the table. A
   484  // tombstone is a slot that has been deleted but is still considered occupied
   485  // so as not to violate the probing invariant.
   486  func (t *table) tombstones() uint16 {
   487  	return (t.capacity*maxAvgGroupLoad)/abi.SwissMapGroupSlots - t.used - t.growthLeft
   488  }
   489  
   490  // Clear deletes all entries from the map resulting in an empty map.
   491  func (t *table) Clear(typ *abi.SwissMapType) {
   492  	for i := uint64(0); i <= t.groups.lengthMask; i++ {
   493  		g := t.groups.group(typ, i)
   494  		typedmemclr(typ.Group, g.data)
   495  		g.ctrls().setEmpty()
   496  	}
   497  
   498  	t.used = 0
   499  	t.resetGrowthLeft()
   500  }
   501  
   502  type Iter struct {
   503  	key  unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
   504  	elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
   505  	typ  *abi.SwissMapType
   506  	m    *Map
   507  
   508  	// Randomize iteration order by starting iteration at a random slot
   509  	// offset. The offset into the directory uses a separate offset, as it
   510  	// must adjust when the directory grows.
   511  	entryOffset uint64
   512  	dirOffset   uint64
   513  
   514  	// Snapshot of Map.clearSeq at iteration initialization time. Used to
   515  	// detect clear during iteration.
   516  	clearSeq uint64
   517  
   518  	// Value of Map.globalDepth during the last call to Next. Used to
   519  	// detect directory grow during iteration.
   520  	globalDepth uint8
   521  
   522  	// dirIdx is the current directory index, prior to adjustment by
   523  	// dirOffset.
   524  	dirIdx int
   525  
   526  	// tab is the table at dirIdx during the previous call to Next.
   527  	tab *table
   528  
   529  	// group is the group at entryIdx during the previous call to Next.
   530  	group groupReference
   531  
   532  	// entryIdx is the current entry index, prior to adjustment by entryOffset.
   533  	// The lower 3 bits of the index are the slot index, and the upper bits
   534  	// are the group index.
   535  	entryIdx uint64
   536  }
   537  
   538  // Init initializes Iter for iteration.
   539  func (it *Iter) Init(typ *abi.SwissMapType, m *Map) {
   540  	it.typ = typ
   541  
   542  	if m == nil || m.used == 0 {
   543  		return
   544  	}
   545  
   546  	dirIdx := 0
   547  	var groupSmall groupReference
   548  	if m.dirLen <= 0 {
   549  		// Use dirIdx == -1 as sentinal for small maps.
   550  		dirIdx = -1
   551  		groupSmall.data = m.dirPtr
   552  	}
   553  
   554  	it.m = m
   555  	it.entryOffset = rand()
   556  	it.dirOffset = rand()
   557  	it.globalDepth = m.globalDepth
   558  	it.dirIdx = dirIdx
   559  	it.group = groupSmall
   560  	it.clearSeq = m.clearSeq
   561  }
   562  
   563  func (it *Iter) Initialized() bool {
   564  	return it.typ != nil
   565  }
   566  
   567  // Map returns the map this iterator is iterating over.
   568  func (it *Iter) Map() *Map {
   569  	return it.m
   570  }
   571  
   572  // Key returns a pointer to the current key. nil indicates end of iteration.
   573  //
   574  // Must not be called prior to Next.
   575  func (it *Iter) Key() unsafe.Pointer {
   576  	return it.key
   577  }
   578  
   579  // Key returns a pointer to the current element. nil indicates end of
   580  // iteration.
   581  //
   582  // Must not be called prior to Next.
   583  func (it *Iter) Elem() unsafe.Pointer {
   584  	return it.elem
   585  }
   586  
   587  func (it *Iter) nextDirIdx() {
   588  	// Skip other entries in the directory that refer to the same
   589  	// logical table. There are two cases of this:
   590  	//
   591  	// Consider this directory:
   592  	//
   593  	// - 0: *t1
   594  	// - 1: *t1
   595  	// - 2: *t2a
   596  	// - 3: *t2b
   597  	//
   598  	// At some point, the directory grew to accomodate a split of
   599  	// t2. t1 did not split, so entries 0 and 1 both point to t1.
   600  	// t2 did split, so the two halves were installed in entries 2
   601  	// and 3.
   602  	//
   603  	// If dirIdx is 0 and it.tab is t1, then we should skip past
   604  	// entry 1 to avoid repeating t1.
   605  	//
   606  	// If dirIdx is 2 and it.tab is t2 (pre-split), then we should
   607  	// skip past entry 3 because our pre-split t2 already covers
   608  	// all keys from t2a and t2b (except for new insertions, which
   609  	// iteration need not return).
   610  	//
   611  	// We can achieve both of these by using to difference between
   612  	// the directory and table depth to compute how many entries
   613  	// the table covers.
   614  	entries := 1 << (it.m.globalDepth - it.tab.localDepth)
   615  	it.dirIdx += entries
   616  	it.tab = nil
   617  	it.group = groupReference{}
   618  	it.entryIdx = 0
   619  }
   620  
   621  // Return the appropriate key/elem for key at slotIdx index within it.group, if
   622  // any.
   623  func (it *Iter) grownKeyElem(key unsafe.Pointer, slotIdx uintptr) (unsafe.Pointer, unsafe.Pointer, bool) {
   624  	newKey, newElem, ok := it.m.getWithKey(it.typ, key)
   625  	if !ok {
   626  		// Key has likely been deleted, and
   627  		// should be skipped.
   628  		//
   629  		// One exception is keys that don't
   630  		// compare equal to themselves (e.g.,
   631  		// NaN). These keys cannot be looked
   632  		// up, so getWithKey will fail even if
   633  		// the key exists.
   634  		//
   635  		// However, we are in luck because such
   636  		// keys cannot be updated and they
   637  		// cannot be deleted except with clear.
   638  		// Thus if no clear has occurred, the
   639  		// key/elem must still exist exactly as
   640  		// in the old groups, so we can return
   641  		// them from there.
   642  		//
   643  		// TODO(prattmic): Consider checking
   644  		// clearSeq early. If a clear occurred,
   645  		// Next could always return
   646  		// immediately, as iteration doesn't
   647  		// need to return anything added after
   648  		// clear.
   649  		if it.clearSeq == it.m.clearSeq && !it.typ.Key.Equal(key, key) {
   650  			elem := it.group.elem(it.typ, slotIdx)
   651  			if it.typ.IndirectElem() {
   652  				elem = *((*unsafe.Pointer)(elem))
   653  			}
   654  			return key, elem, true
   655  		}
   656  
   657  		// This entry doesn't exist anymore.
   658  		return nil, nil, false
   659  	}
   660  
   661  	return newKey, newElem, true
   662  }
   663  
   664  // Next proceeds to the next element in iteration, which can be accessed via
   665  // the Key and Elem methods.
   666  //
   667  // The table can be mutated during iteration, though there is no guarantee that
   668  // the mutations will be visible to the iteration.
   669  //
   670  // Init must be called prior to Next.
   671  func (it *Iter) Next() {
   672  	if it.m == nil {
   673  		// Map was empty at Iter.Init.
   674  		it.key = nil
   675  		it.elem = nil
   676  		return
   677  	}
   678  
   679  	if it.m.writing != 0 {
   680  		fatal("concurrent map iteration and map write")
   681  		return
   682  	}
   683  
   684  	if it.dirIdx < 0 {
   685  		// Map was small at Init.
   686  		for ; it.entryIdx < abi.SwissMapGroupSlots; it.entryIdx++ {
   687  			k := uintptr(it.entryIdx+it.entryOffset) % abi.SwissMapGroupSlots
   688  
   689  			if (it.group.ctrls().get(k) & ctrlEmpty) == ctrlEmpty {
   690  				// Empty or deleted.
   691  				continue
   692  			}
   693  
   694  			key := it.group.key(it.typ, k)
   695  			if it.typ.IndirectKey() {
   696  				key = *((*unsafe.Pointer)(key))
   697  			}
   698  
   699  			// As below, if we have grown to a full map since Init,
   700  			// we continue to use the old group to decide the keys
   701  			// to return, but must look them up again in the new
   702  			// tables.
   703  			grown := it.m.dirLen > 0
   704  			var elem unsafe.Pointer
   705  			if grown {
   706  				var ok bool
   707  				newKey, newElem, ok := it.m.getWithKey(it.typ, key)
   708  				if !ok {
   709  					// See comment below.
   710  					if it.clearSeq == it.m.clearSeq && !it.typ.Key.Equal(key, key) {
   711  						elem = it.group.elem(it.typ, k)
   712  						if it.typ.IndirectElem() {
   713  							elem = *((*unsafe.Pointer)(elem))
   714  						}
   715  					} else {
   716  						continue
   717  					}
   718  				} else {
   719  					key = newKey
   720  					elem = newElem
   721  				}
   722  			} else {
   723  				elem = it.group.elem(it.typ, k)
   724  				if it.typ.IndirectElem() {
   725  					elem = *((*unsafe.Pointer)(elem))
   726  				}
   727  			}
   728  
   729  			it.entryIdx++
   730  			it.key = key
   731  			it.elem = elem
   732  			return
   733  		}
   734  		it.key = nil
   735  		it.elem = nil
   736  		return
   737  	}
   738  
   739  	if it.globalDepth != it.m.globalDepth {
   740  		// Directory has grown since the last call to Next. Adjust our
   741  		// directory index.
   742  		//
   743  		// Consider:
   744  		//
   745  		// Before:
   746  		// - 0: *t1
   747  		// - 1: *t2  <- dirIdx
   748  		//
   749  		// After:
   750  		// - 0: *t1a (split)
   751  		// - 1: *t1b (split)
   752  		// - 2: *t2  <- dirIdx
   753  		// - 3: *t2
   754  		//
   755  		// That is, we want to double the current index when the
   756  		// directory size doubles (or quadruple when the directory size
   757  		// quadruples, etc).
   758  		//
   759  		// The actual (randomized) dirIdx is computed below as:
   760  		//
   761  		// dirIdx := (it.dirIdx + it.dirOffset) % it.m.dirLen
   762  		//
   763  		// Multiplication is associative across modulo operations,
   764  		// A * (B % C) = (A * B) % (A * C),
   765  		// provided that A is positive.
   766  		//
   767  		// Thus we can achieve this by adjusting it.dirIdx,
   768  		// it.dirOffset, and it.m.dirLen individually.
   769  		orders := it.m.globalDepth - it.globalDepth
   770  		it.dirIdx <<= orders
   771  		it.dirOffset <<= orders
   772  		// it.m.dirLen was already adjusted when the directory grew.
   773  
   774  		it.globalDepth = it.m.globalDepth
   775  	}
   776  
   777  	// Continue iteration until we find a full slot.
   778  	for ; it.dirIdx < it.m.dirLen; it.nextDirIdx() {
   779  		// Resolve the table.
   780  		if it.tab == nil {
   781  			dirIdx := int((uint64(it.dirIdx) + it.dirOffset) & uint64(it.m.dirLen-1))
   782  			newTab := it.m.directoryAt(uintptr(dirIdx))
   783  			if newTab.index != dirIdx {
   784  				// Normally we skip past all duplicates of the
   785  				// same entry in the table (see updates to
   786  				// it.dirIdx at the end of the loop below), so
   787  				// this case wouldn't occur.
   788  				//
   789  				// But on the very first call, we have a
   790  				// completely randomized dirIdx that may refer
   791  				// to a middle of a run of tables in the
   792  				// directory. Do a one-time adjustment of the
   793  				// offset to ensure we start at first index for
   794  				// newTable.
   795  				diff := dirIdx - newTab.index
   796  				it.dirOffset -= uint64(diff)
   797  				dirIdx = newTab.index
   798  			}
   799  			it.tab = newTab
   800  		}
   801  
   802  		// N.B. Use it.tab, not newTab. It is important to use the old
   803  		// table for key selection if the table has grown. See comment
   804  		// on grown below.
   805  
   806  		if it.entryIdx > it.tab.groups.entryMask {
   807  			// Continue to next table.
   808  			continue
   809  		}
   810  
   811  		// Fast path: skip matching and directly check if entryIdx is a
   812  		// full slot.
   813  		//
   814  		// In the slow path below, we perform an 8-slot match check to
   815  		// look for full slots within the group.
   816  		//
   817  		// However, with a max load factor of 7/8, each slot in a
   818  		// mostly full map has a high probability of being full. Thus
   819  		// it is cheaper to check a single slot than do a full control
   820  		// match.
   821  
   822  		entryIdx := (it.entryIdx + it.entryOffset) & it.tab.groups.entryMask
   823  		slotIdx := uintptr(entryIdx & (abi.SwissMapGroupSlots - 1))
   824  		if slotIdx == 0 || it.group.data == nil {
   825  			// Only compute the group (a) when we switch
   826  			// groups (slotIdx rolls over) and (b) on the
   827  			// first iteration in this table (slotIdx may
   828  			// not be zero due to entryOffset).
   829  			groupIdx := entryIdx >> abi.SwissMapGroupSlotsBits
   830  			it.group = it.tab.groups.group(it.typ, groupIdx)
   831  		}
   832  
   833  		if (it.group.ctrls().get(slotIdx) & ctrlEmpty) == 0 {
   834  			// Slot full.
   835  
   836  			key := it.group.key(it.typ, slotIdx)
   837  			if it.typ.IndirectKey() {
   838  				key = *((*unsafe.Pointer)(key))
   839  			}
   840  
   841  			grown := it.tab.index == -1
   842  			var elem unsafe.Pointer
   843  			if grown {
   844  				newKey, newElem, ok := it.grownKeyElem(key, slotIdx)
   845  				if !ok {
   846  					// This entry doesn't exist
   847  					// anymore. Continue to the
   848  					// next one.
   849  					goto next
   850  				} else {
   851  					key = newKey
   852  					elem = newElem
   853  				}
   854  			} else {
   855  				elem = it.group.elem(it.typ, slotIdx)
   856  				if it.typ.IndirectElem() {
   857  					elem = *((*unsafe.Pointer)(elem))
   858  				}
   859  			}
   860  
   861  			it.entryIdx++
   862  			it.key = key
   863  			it.elem = elem
   864  			return
   865  		}
   866  
   867  next:
   868  		it.entryIdx++
   869  
   870  		// Slow path: use a match on the control word to jump ahead to
   871  		// the next full slot.
   872  		//
   873  		// This is highly effective for maps with particularly low load
   874  		// (e.g., map allocated with large hint but few insertions).
   875  		//
   876  		// For maps with medium load (e.g., 3-4 empty slots per group)
   877  		// it also tends to work pretty well. Since slots within a
   878  		// group are filled in order, then if there have been no
   879  		// deletions, a match will allow skipping past all empty slots
   880  		// at once.
   881  		//
   882  		// Note: it is tempting to cache the group match result in the
   883  		// iterator to use across Next calls. However because entries
   884  		// may be deleted between calls later calls would still need to
   885  		// double-check the control value.
   886  
   887  		var groupMatch bitset
   888  		for it.entryIdx <= it.tab.groups.entryMask {
   889  			entryIdx := (it.entryIdx + it.entryOffset) & it.tab.groups.entryMask
   890  			slotIdx := uintptr(entryIdx & (abi.SwissMapGroupSlots - 1))
   891  
   892  			if slotIdx == 0 || it.group.data == nil {
   893  				// Only compute the group (a) when we switch
   894  				// groups (slotIdx rolls over) and (b) on the
   895  				// first iteration in this table (slotIdx may
   896  				// not be zero due to entryOffset).
   897  				groupIdx := entryIdx >> abi.SwissMapGroupSlotsBits
   898  				it.group = it.tab.groups.group(it.typ, groupIdx)
   899  			}
   900  
   901  			if groupMatch == 0 {
   902  				groupMatch = it.group.ctrls().matchFull()
   903  
   904  				if slotIdx != 0 {
   905  					// Starting in the middle of the group.
   906  					// Ignore earlier groups.
   907  					groupMatch = groupMatch.removeBelow(slotIdx)
   908  				}
   909  
   910  				// Skip over groups that are composed of only empty or
   911  				// deleted slots.
   912  				if groupMatch == 0 {
   913  					// Jump past remaining slots in this
   914  					// group.
   915  					it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
   916  					continue
   917  				}
   918  
   919  				i := groupMatch.first()
   920  				it.entryIdx += uint64(i - slotIdx)
   921  				if it.entryIdx > it.tab.groups.entryMask {
   922  					// Past the end of this table's iteration.
   923  					continue
   924  				}
   925  				entryIdx += uint64(i - slotIdx)
   926  				slotIdx = i
   927  			}
   928  
   929  			key := it.group.key(it.typ, slotIdx)
   930  			if it.typ.IndirectKey() {
   931  				key = *((*unsafe.Pointer)(key))
   932  			}
   933  
   934  			// If the table has changed since the last
   935  			// call, then it has grown or split. In this
   936  			// case, further mutations (changes to
   937  			// key->elem or deletions) will not be visible
   938  			// in our snapshot table. Instead we must
   939  			// consult the new table by doing a full
   940  			// lookup.
   941  			//
   942  			// We still use our old table to decide which
   943  			// keys to lookup in order to avoid returning
   944  			// the same key twice.
   945  			grown := it.tab.index == -1
   946  			var elem unsafe.Pointer
   947  			if grown {
   948  				newKey, newElem, ok := it.grownKeyElem(key, slotIdx)
   949  				if !ok {
   950  					// This entry doesn't exist anymore.
   951  					// Continue to the next one.
   952  					groupMatch = groupMatch.removeFirst()
   953  					if groupMatch == 0 {
   954  						// No more entries in this
   955  						// group. Continue to next
   956  						// group.
   957  						it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
   958  						continue
   959  					}
   960  
   961  					// Next full slot.
   962  					i := groupMatch.first()
   963  					it.entryIdx += uint64(i - slotIdx)
   964  					continue
   965  				} else {
   966  					key = newKey
   967  					elem = newElem
   968  				}
   969  			} else {
   970  				elem = it.group.elem(it.typ, slotIdx)
   971  				if it.typ.IndirectElem() {
   972  					elem = *((*unsafe.Pointer)(elem))
   973  				}
   974  			}
   975  
   976  			// Jump ahead to the next full slot or next group.
   977  			groupMatch = groupMatch.removeFirst()
   978  			if groupMatch == 0 {
   979  				// No more entries in
   980  				// this group. Continue
   981  				// to next group.
   982  				it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
   983  			} else {
   984  				// Next full slot.
   985  				i := groupMatch.first()
   986  				it.entryIdx += uint64(i - slotIdx)
   987  			}
   988  
   989  			it.key = key
   990  			it.elem = elem
   991  			return
   992  		}
   993  
   994  		// Continue to next table.
   995  	}
   996  
   997  	it.key = nil
   998  	it.elem = nil
   999  	return
  1000  }
  1001  
  1002  // Replaces the table with one larger table or two split tables to fit more
  1003  // entries. Since the table is replaced, t is now stale and should not be
  1004  // modified.
  1005  func (t *table) rehash(typ *abi.SwissMapType, m *Map) {
  1006  	// TODO(prattmic): SwissTables typically perform a "rehash in place"
  1007  	// operation which recovers capacity consumed by tombstones without growing
  1008  	// the table by reordering slots as necessary to maintain the probe
  1009  	// invariant while eliminating all tombstones.
  1010  	//
  1011  	// However, it is unclear how to make rehash in place work with
  1012  	// iteration. Since iteration simply walks through all slots in order
  1013  	// (with random start offset), reordering the slots would break
  1014  	// iteration.
  1015  	//
  1016  	// As an alternative, we could do a "resize" to new groups allocation
  1017  	// of the same size. This would eliminate the tombstones, but using a
  1018  	// new allocation, so the existing grow support in iteration would
  1019  	// continue to work.
  1020  
  1021  	newCapacity := 2 * t.capacity
  1022  	if newCapacity <= maxTableCapacity {
  1023  		t.grow(typ, m, newCapacity)
  1024  		return
  1025  	}
  1026  
  1027  	t.split(typ, m)
  1028  }
  1029  
  1030  // Bitmask for the last selection bit at this depth.
  1031  func localDepthMask(localDepth uint8) uintptr {
  1032  	if goarch.PtrSize == 4 {
  1033  		return uintptr(1) << (32 - localDepth)
  1034  	}
  1035  	return uintptr(1) << (64 - localDepth)
  1036  }
  1037  
  1038  // split the table into two, installing the new tables in the map directory.
  1039  func (t *table) split(typ *abi.SwissMapType, m *Map) {
  1040  	localDepth := t.localDepth
  1041  	localDepth++
  1042  
  1043  	// TODO: is this the best capacity?
  1044  	left := newTable(typ, maxTableCapacity, -1, localDepth)
  1045  	right := newTable(typ, maxTableCapacity, -1, localDepth)
  1046  
  1047  	// Split in half at the localDepth bit from the top.
  1048  	mask := localDepthMask(localDepth)
  1049  
  1050  	for i := uint64(0); i <= t.groups.lengthMask; i++ {
  1051  		g := t.groups.group(typ, i)
  1052  		for j := uintptr(0); j < abi.SwissMapGroupSlots; j++ {
  1053  			if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
  1054  				// Empty or deleted
  1055  				continue
  1056  			}
  1057  
  1058  			key := g.key(typ, j)
  1059  			if typ.IndirectKey() {
  1060  				key = *((*unsafe.Pointer)(key))
  1061  			}
  1062  
  1063  			elem := g.elem(typ, j)
  1064  			if typ.IndirectElem() {
  1065  				elem = *((*unsafe.Pointer)(elem))
  1066  			}
  1067  
  1068  			hash := typ.Hasher(key, m.seed)
  1069  			var newTable *table
  1070  			if hash&mask == 0 {
  1071  				newTable = left
  1072  			} else {
  1073  				newTable = right
  1074  			}
  1075  			// TODO(prattmic): For indirect key/elem, this is
  1076  			// allocating new objects for key/elem. That is
  1077  			// unnecessary; the new table could simply point to the
  1078  			// existing object.
  1079  			slotElem := newTable.uncheckedPutSlot(typ, hash, key)
  1080  			typedmemmove(typ.Elem, slotElem, elem)
  1081  			newTable.used++
  1082  		}
  1083  	}
  1084  
  1085  	m.installTableSplit(t, left, right)
  1086  	t.index = -1
  1087  }
  1088  
  1089  // grow the capacity of the table by allocating a new table with a bigger array
  1090  // and uncheckedPutting each element of the table into the new table (we know
  1091  // that no insertion here will Put an already-present value), and discard the
  1092  // old table.
  1093  func (t *table) grow(typ *abi.SwissMapType, m *Map, newCapacity uint16) {
  1094  	newTable := newTable(typ, uint64(newCapacity), t.index, t.localDepth)
  1095  
  1096  	if t.capacity > 0 {
  1097  		for i := uint64(0); i <= t.groups.lengthMask; i++ {
  1098  			g := t.groups.group(typ, i)
  1099  			for j := uintptr(0); j < abi.SwissMapGroupSlots; j++ {
  1100  				if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
  1101  					// Empty or deleted
  1102  					continue
  1103  				}
  1104  
  1105  				key := g.key(typ, j)
  1106  				if typ.IndirectKey() {
  1107  					key = *((*unsafe.Pointer)(key))
  1108  				}
  1109  
  1110  				elem := g.elem(typ, j)
  1111  				if typ.IndirectElem() {
  1112  					elem = *((*unsafe.Pointer)(elem))
  1113  				}
  1114  
  1115  				hash := typ.Hasher(key, m.seed)
  1116  
  1117  				// TODO(prattmic): For indirect key/elem, this is
  1118  				// allocating new objects for key/elem. That is
  1119  				// unnecessary; the new table could simply point to the
  1120  				// existing object.
  1121  				slotElem := newTable.uncheckedPutSlot(typ, hash, key)
  1122  				typedmemmove(typ.Elem, slotElem, elem)
  1123  				newTable.used++
  1124  			}
  1125  		}
  1126  	}
  1127  
  1128  	newTable.checkInvariants(typ, m)
  1129  	m.replaceTable(newTable)
  1130  	t.index = -1
  1131  }
  1132  
  1133  // probeSeq maintains the state for a probe sequence that iterates through the
  1134  // groups in a table. The sequence is a triangular progression of the form
  1135  //
  1136  //	p(i) := (i^2 + i)/2 + hash (mod mask+1)
  1137  //
  1138  // The sequence effectively outputs the indexes of *groups*. The group
  1139  // machinery allows us to check an entire group with minimal branching.
  1140  //
  1141  // It turns out that this probe sequence visits every group exactly once if
  1142  // the number of groups is a power of two, since (i^2+i)/2 is a bijection in
  1143  // Z/(2^m). See https://en.wikipedia.org/wiki/Quadratic_probing
  1144  type probeSeq struct {
  1145  	mask   uint64
  1146  	offset uint64
  1147  	index  uint64
  1148  }
  1149  
  1150  func makeProbeSeq(hash uintptr, mask uint64) probeSeq {
  1151  	return probeSeq{
  1152  		mask:   mask,
  1153  		offset: uint64(hash) & mask,
  1154  		index:  0,
  1155  	}
  1156  }
  1157  
  1158  func (s probeSeq) next() probeSeq {
  1159  	s.index++
  1160  	s.offset = (s.offset + s.index) & s.mask
  1161  	return s
  1162  }
  1163
View as plain text