美文网首页
Swift实现mark-sweep算法及相关文章推荐

Swift实现mark-sweep算法及相关文章推荐

作者: 黄二瓜 | 来源:发表于2020-11-18 18:07 被阅读0次

    本文主要用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
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:Swift实现mark-sweep算法及相关文章推荐

          本文链接:https://www.haomeiwen.com/subject/mvcfiktx.html