runtime: during map delete, update entries after new last element

When we delete an element, and it was the last element in the bucket,
update the slots between the new last element and the old last element
with the marker that says "no more elements beyond here".

Change-Id: I8efeeddf4c9b9fc491c678f84220a5a5094c9c76
Reviewed-on: https://go-review.googlesource.com/c/142438
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

1 files changed, 31 insertions, 1 deletions

diff --git a/src/runtime/map_fast32.go b/src/runtime/map_fast32.go
index 063a5cbe3a..20f55e17c6 100644
--- a/src/runtime/map_fast32.go
+++ b/src/runtime/map_fast32.go
@@ -291,6 +291,7 @@ func mapdelete_fast32(t *maptype, h *hmap, key uint32) {
 		growWork_fast32(t, h, bucket)
 	}
 	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
+	bOrig := b
 search:
 	for ; b != nil; b = b.overflow(t) {
 		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) {
@@ -308,7 +309,36 @@ search:
 				memclrNoHeapPointers(v, t.elem.size)
 			}
 			b.tophash[i] = emptyOne
-			// TODO: emptyRest?
+			// If the bucket now ends in a bunch of emptyOne states,
+			// change those to emptyRest states.
+			if i == bucketCnt-1 {
+				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
+					goto notLast
+				}
+			} else {
+				if b.tophash[i+1] != emptyRest {
+					goto notLast
+				}
+			}
+			for {
+				b.tophash[i] = emptyRest
+				if i == 0 {
+					if b == bOrig {
+						break // beginning of initial bucket, we're done.
+					}
+					// Find previous bucket, continue at its last entry.
+					c := b
+					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
+					}
+					i = bucketCnt - 1
+				} else {
+					i--
+				}
+				if b.tophash[i] != emptyOne {
+					break
+				}
+			}
+		notLast:
 			h.count--
 			break search
 		}