// COSC-163 // Prof. Scott Kaplan // Pseudocode for a copying garbage collector // Notes: A _handle_, in this code, is a _pointer to a pointer_. That // is, a handle is the address of a space that contains a pointer. // Through this handle, we can access not only the memory to which the // pointer leads, but also modify the pointer itself. So, if we have // a handle named `h`, then the first indirection `*h` gets us to the // space that holds the pointer, and the second indirection `**h` gets // us to the space to which the pointer points. void collect () { // The `root_set` is a list of the handles to the pointers contained // in the statics and stack regions. (Don't worry about root pointers // in registers; that's a implementation detail.) traverse(root_set); } void traverse (handle_list) { while (! isEmpty(handle_list)) { handle = dequeue(handle_list); ptr = *handle; if (! ptr->visited) { // This heap block hasn't been visited, so: // 1. Mark it visited. ptr->visited = true; // 2. Copy it to a space of live blocks (e.g., to-space). new_ptr = copy(ptr); // 3. Set a forwarding address from the old copy to the new. ptr->forwarding_addr = new_ptr; // 4. Find the pointers in the new copy and add their addresses // to the list of handles. enqueue(handle_list, extract_pointers(new_ptr)); } // Update the current pointer to point to the new block location. *handle = ptr->forwarding_addr; } }