Method mergeSpans

internal/freelist/hashmap.go:173–219

(ids common.Pgids)

}

func (f *hashMap) mergeSpans(ids common.Pgids) {
	if len(ids) == 0 {
		return
	}
	sort.Sort(ids)

	common.Verify(func() {
		ids1Freemap := f.idsFromFreemaps()
		ids2Forward := f.idsFromForwardMap()
		ids3Backward := f.idsFromBackwardMap()

		if !reflect.DeepEqual(ids1Freemap, ids2Forward) {
			panic(fmt.Sprintf("Detected mismatch, f.freemaps: %v, f.forwardMap: %v", f.freemaps, f.forwardMap))
		}
		if !reflect.DeepEqual(ids1Freemap, ids3Backward) {
			panic(fmt.Sprintf("Detected mismatch, f.freemaps: %v, f.backwardMap: %v", f.freemaps, f.backwardMap))
		}

		prev := common.Pgid(0)
		for _, id := range ids {
			// The ids shouldn't have duplicated free ID.
			if prev == id {
				panic(fmt.Sprintf("detected duplicated free ID: %d in ids: %v", id, ids))
			}
			prev = id

			// The ids shouldn't have any overlap with the existing f.freemaps.
			if _, ok := ids1Freemap[id]; ok {
				panic(fmt.Sprintf("detected overlapped free page ID: %d between ids: %v and existing f.freemaps: %v", id, ids, f.freemaps))
			}
		}
	})

	start := ids[0]
	end := ids[0]
	for i := 1; i < len(ids); i++ {
		id := ids[i]
		if id == end+1 {
			end = id
			continue
		}

		f.mergeWithExistingSpan(start, end)
		start, end = id, id
	}
	f.mergeWithExistingSpan(start, end)
}

// mergeWithExistingSpan merges free span [start, end] with adjacent existing free spans (both backward and forward).
func (f *hashMap) mergeWithExistingSpan(start, end common.Pgid) {