定義
該算法分為標記和整理兩個階段，標記階段會遍歷并標記活動對象，整理階段通過數次搜索堆來重新裝填活動對象，它們聚集到了堆的一端。
lisp2算法
forwarding指針表示活動對象的目標地址
過程概要
初始狀態
標記結束后
整理結束后
整理階段偽代碼
compaction_phase() {
// 設定forwarding指針
set_forwarding_ptr();
// 更新指正
adjust_ptr();
// 移動對象
move_obj();
}
// 第一次遍歷堆
// $head_start 堆起始地址
// $head_end 堆結束地址
set_forwarding_ptr() {
// 定義搜索堆的指針和指向目標地址的指針
scan = new_address = $head_start;
// 遍歷堆，進行設置
while (scan < $head_end) {
// 若是活動對象，則設置forwarding指針
if (scan.mark == TRUE) {
scan.forwarding = new_address;
new_address += scan.size;
}
scan += scan.size;
}
}
// 第二次遍歷堆
adjust_ptr() {
// 更新根對象forwarding指針
for (r : $roots) {
*r = (*r).forwarding;
}
scan = $head_start;
while (scan < $head_end) {
// 更新子對象forwarding指針
if(scan.mark == TRUE) {
for(child : children(scan)) {
*child = (*child).forwarding;
}
}
scan += scan.size;
}
}
// 第三次遍歷堆
move_obj() {
scan = $free = $heap_start;
while(scan < $heap_end) {
if(scan.mark == TRUE) {
// 將找到的對象移動到 forwarding 指針的引用目標處
new_address = scan.forwarding;
copy_data(new_address, scan, scan.size);
new_address.forwarding = NULL;
new_address.mark = FALSE;
$free += new_address.size;
}
scan += scan.size;
}
)
)
