in freelist.go [236:294]
func (f *freelist) AddRegion(reg region) {
if len(f.regions) == 0 {
f.regions = regionList{reg}
f.avail += uint(reg.count)
return
}
i := sort.Search(len(f.regions), func(i int) bool {
_, end := f.regions[i].Range()
return reg.id < end
})
total := uint(reg.count)
switch {
case len(f.regions) <= i: // add to end of region list?
last := len(f.regions) - 1
if regionsMergable(f.regions[last], reg) {
f.regions[last] = mergeRegions(f.regions[last], reg)
} else {
f.regions.Add(reg)
}
case i == 0: // add to start of region list?
if regionsMergable(reg, f.regions[0]) {
f.regions[0] = mergeRegions(reg, f.regions[0])
} else {
f.regions = append(f.regions, region{})
copy(f.regions[1:], f.regions)
f.regions[0] = reg
}
default: // insert in middle of region list
// try to merge region with already existing regions
mergeBefore := regionsMergable(f.regions[i-1], reg)
if mergeBefore {
reg = mergeRegions(f.regions[i-1], reg)
}
mergeAfter := regionsMergable(reg, f.regions[i])
if mergeAfter {
reg = mergeRegions(reg, f.regions[i])
}
// update region list
switch {
case mergeBefore && mergeAfter: // combine adjacent regions -> shrink list
f.regions[i-1] = reg
copy(f.regions[i:], f.regions[i+1:])
f.regions = f.regions[:len(f.regions)-1]
case mergeBefore:
f.regions[i-1] = reg
case mergeAfter:
f.regions[i] = reg
default: // no adjacent entries -> grow list
f.regions = append(f.regions, region{})
copy(f.regions[i+1:], f.regions[i:])
f.regions[i] = reg
}
}
f.avail += total
}