本文主要用Swift
来模拟定义对象、头、域、堆以及空闲链表,并实现标记与清除两个阶段算法来帮助理解,简单实现mark-sweep
算法思路,不包含对象分配过程。完整代码见mark-sweep.swift
参考文章 推荐
头信息定义
class HeaderInfo {
var name: String
var size: Int
var marked: Bool
init(_ name: String, size: Int) {
self.name = name
self.size = size
marked = false
}
}
对象定义
class Obj {
var head: HeaderInfo //头信息
var field: Obj? //域
init(_ headInfo: HeaderInfo) {
head = headInfo
}
}
堆定义: 用来模拟内存中堆状态
class Heap {
var usedSize: Int = 0
var maxSize: Int
private var _objs: [Obj] = [] //记录堆中对象
init(_ maxSize: Int) {
self.maxSize = maxSize
}
var objs: [Obj] {
get {return _objs}
}
func appendObj(_ obj: Obj) {
usedSize += obj.head.size
_objs.append(obj)
}
}
空闲链表定义:
class Node {
var next: Node?
var data: Obj?
}
标记阶段:
private func markPhase() {
for obj in roots {
mark(obj)
}
}
// 标记对象
private func mark(_ obj: Obj) {
if obj.head.marked == false {
obj.head.marked = true
if let child = obj.field {
mark(child)
}
}
}
清除阶段:
private func sweepPhase() {
for obj in heap.objs {
if obj.head.marked {
obj.head.marked = false
} else {
//非活动对象加入到空闲列表
obj.head.name = "FreeChunk" //需要被重新分块的对象
let freeNode = Node()
freeNode.data = obj
freeNode.next = freeList
freeList = freeNode
}
}
}
网友评论