Heap V1

assignment 6

// *************************
// HEAP
// *************************/

// HEAP is an array of bytes (JS ArrayBuffer)

const word_size = 8

// heap_make allocates a heap of given size 
// (in bytes) and returns a DataView of that, 
// see https://www.javascripture.com/DataView
const heap_make = words => {
    const data = new ArrayBuffer(words * word_size)
    const view = new DataView(data)
    return view
}

// for convenience, HEAP is global variable
// initialized in initialize_machine()
let HEAP 

// free is the next free index in HEAP
// we keep allocating as if there was no tomorrow
let free 

// for debugging: display all bits of the heap
const heap_display = () => {
    display("", "heap:")
    for (let i = 0; i < heap_size; i++) {
        display(word_to_string(heap_get(i)), 
                stringify(i) + " " +
                stringify(heap_get(i)) +
                " ")
    }
}

// heap_allocate allocates a given number of words 
// on the heap and marks the first word with a 1-byte tag.
// the last two bytes of the first word indicate the number
// of children (addresses) that follow the tag word:
// [1 byte tag, 4 bytes payload (depending on node type), 
//  2 bytes #children, 1 byte unused] 
// Note: payload depends on the type of node
const size_offset = 5

const heap_allocate =
    (tag, size) => {
        
        // This is using the cheney 
        // if (free + size >= top_of_space) {
        //     display(free, "FLIP! free:")
        //     flip()
        // }
        // if (free + size >= top_of_space) {
        //     error("heap memory exhausted")
        // }
        // const address = free 
        // free += size 
        // HEAP.setInt8(address * word_size, tag)
        // HEAP.setUint16(address * word_size + 
        //               size_offset,
        //               size)
        // return address
        
        
        return new_node()
    }
    
    

/// Mark-sweep
const NEXT = 1; // The offset of the next pointer within the node, in words
const NEXT_BYTE_OFFSET = NEXT * word_size; // Convert word offset to byte offset
const NIL = -1;

let heap_bottom
let Freelist = 0

/// Allocate for mark_sweep
// The allocate function attempts to take a node from the free list
// If successful, it returns the address of the node, otherwise it returns NIL
const allocate = (tag, size) => {
    if (Freelist === NIL) {
        return NIL; // No free nodes available
    }
    const allocatedNode = Freelist;
    // Assuming that the first word (8 bytes) of the node contains the next free address
    Freelist = HEAP.getInt32(Freelist * word_size);
    return allocatedNode;
};

// // The free function takes an index 'n' and adds that node back to the free list
// const free = (n) => {
//     // Convert the current head of the free list to a byte offset and store it at the next position of node 'n'
//     HEAP.setFloat64(n * word_size + NEXT_BYTE_OFFSET, Freelist);

//     // Update the head of the free list to be node 'n'
//     Freelist = n;
// }

// // The free function adds a node back to the free list
// const free = (n) => {
//     HEAP.setInt32(n * word_size, Freelist);
//     Freelist = n;
// };

// Sweep function
const sweep = () => {
    let address = 0;
    while (address < heap_size) {
        if (get_mark_bit(address) === UNMARKED) {
            free(address);
        } else {
            clear_mark_bit(address);
        }
        address += 1; // Move to the next node
    }
}

// Mark function
const mark = (address) => {
    if (address < 0) { // Ignore illegal addresses
        return;
    }
    if (get_mark_bit(address) === MARKED) {
        return; // Already marked
    }
    set_mark_bit(address);
    const numberOfChildren = heap_get_number_of_children(address);
    for (let childIndex = 0; childIndex < numberOfChildren; childIndex++) {
        const childAddress = heap_get_child(address, childIndex);
        mark(childAddress);
    }
}

// The mark-sweep function
const mark_sweep = () => {
    for (const root of ROOTS) {
        mark(root);
    }
    sweep();
    if (Freelist === NIL) {
        throw new Error("memory exhausted");
    }
}

// Integrate into existing allocation function
const new_node = () => {
    if (Freelist === NIL) {
        mark_sweep();
    }
    const newNodeAddress = allocate();
    if (newNodeAddress === NIL) {
        throw new Error("memory exhausted");
    }
    return newNodeAddress;
}

// ///////////////////////////////////
// Cheney's Copying Garbage Collection
// ///////////////////////////////////

// initialize spaces for Cheney's algorithm

let space_size
let to_space
let from_space
let top_of_space
// next free slot in heap; declared above
free
// scan pointer in Cheney
let scan
// the size of the heap is fixed
let heap_size
// smallest heap address
let temp_root

let running

function initialize_machine(heapsize_words) {
    OS = []
    PC = 0
    RTS = []
    HEAP = heap_make(heapsize_words)
    heap_size = heapsize_words
    heap_bottom = 0
    space_size = heap_size / 2
    to_space = heap_bottom
    from_space = to_space + space_size
    top_of_space = to_space + space_size - 1
    free = to_space
    temp_root = -1
    PC = 0
    allocate_literal_values()
    E = heap_allocate_Environment(0)
    const global_frame = allocate_global_frame()
    E = heap_Environment_extend(global_frame, E)
    initialize_freelist(heapsize_words)
}


// Initialize the free list with all addresses in the heap
const initialize_freelist = (heapSizeWords) => {
    heap_bottom = 0;
    Freelist = heap_bottom;
    let current = Freelist;
    for (let address = current + NODE_SIZE_WORDS; address < heapSizeWords; address += NODE_SIZE_WORDS) {
        HEAP.setInt32(current * word_size, address);
        current = address;
    }
    // Terminate the free list with NIL
    HEAP.setInt32(current * word_size, NIL);
};