//might not fully functional
import “io”
// each newvec allocation also dedicates four bytes:
// -3: size — (even number = unoccupied chunk, odd number = occupied chunk)
// -2: address of previous memory chunk
// -1: address of next memory chunk
// 0: (this is the address returned to user)
// 1:
// n: size — (even number = unoccupied chunk, odd number = occupied chunk)
export{ new_vec, free_vec, init_heap }
manifest
{
chunk_size = -3,
previous = -2,
next = -1
}
manifest
{
sizeof_meta_data = 3,
sizeof_all_meta_data = 4,
sizeof_array_of_lists = 42
}
manifest
{
max_size = 32768 //words
}
static { heap, next_free_address }
let error(error_code) be
{
out(“error %d\n, error_code”);
if error_code = 1 then
{
out(“newvec: requested too large of a chunk. max size = 32768 words\n”)
}
resultis 0
}
let print_memory(address) be
{
for i = 0 to 75 do
{
out(“heap ! %d = “, i);
out(“0x%x: %d / 0x%x\n”, @(address ! i), address ! i, address ! i)
}
}
//all chunks returned to user are even number of words
let set_chunk_size(size) be
{
if size rem 2 = 1 then size +:= 1;
if size > max_size then resultis error(1);
resultis size
}
//odd size signals chunk is occupied (w/ size-1 words)
let chunk_is_occupied(address) be
{
if (address ! chunk_size) rem 2 = 1 then resultis true;
resultis false
}
let get_index_in_array_of_lists(size) be
{
let index = 0, current_power_of_two = 2;
while current_power_of_two <= 8192 do
{
if size <= current_power_of_two then
{
resultis index;
}
index +:= 3;
current_power_of_two *:= 2
}
resultis index
}
let address_is_ptr_to_list(addr) be
{
if addr >= heap /\ addr < (heap + sizeof_array_of_lists) then
{
resultis true;
}
resultis false
}
let new_chunk(size, index) be
{
let prev_ptr = @(heap ! index);
let next_ptr = heap ! index;
let addr = next_free_address;
next_free_address +:= (size + sizeof_all_meta_data);
if next_ptr <> nil then
{
next_ptr ! previous := addr;
}
addr ! chunk_size := size + 1;
addr ! previous := prev_ptr;
addr ! next := next_ptr;
addr ! size := size + 1;
resultis addr
}
let move_free_chunk_to_list(addr, index) be
{
let prev_ptr = @(heap ! index);
let next_ptr = heap ! index;
let size = addr ! chunk_size;
test (addr ! previous) = @(heap ! (index + 1)) then
{
heap ! (index + 1) := addr ! next
}
else
{
(addr ! previous) ! next := addr ! next;
}
if addr ! next <> nil then
{
(addr ! next) ! previous := addr ! previous;
}
if next_ptr <> nil then
{
next_ptr ! previous := addr;
}
addr ! chunk_size := size + 1;
addr ! previous := prev_ptr;
addr ! next := next_ptr;
addr ! size := size + 1;
heap ! (index + 2) -:= 1;
resultis addr
}
let recycle_free_chunk(size, index) be
{
let prev_ptr = @(heap ! index);
let next_ptr = heap ! index;
let addr = heap ! (index + 1);
until addr = nil do
{
if addr ! chunk_size >= size then
{
resultis move_free_chunk_to_list(addr, index);
}
addr := addr ! next
}
resultis new_chunk(size, prev_ptr, next_ptr)
}
//add to front of list (either new_chunk or recycle_free_chunk)
let new_vec(size) be
{
let index, free_list_ptr, items_in_free_list;
let next_ptr, prev_ptr;
size := set_chunk_size(size);
index := get_index_in_array_of_lists(size);
items_in_free_list := heap ! (index + 2);
test items_in_free_list = 0 then
{
heap ! index := new_chunk(size, index)
}
else
{
heap ! index := recycle_free_chunk(size, index);
}
resultis (heap ! index)
}
let move_chunk_to_free_list(addr, size) be
{
let index = get_index_in_array_of_lists(size);
let prev_ptr = @(heap ! (index + 1));
let next_ptr = heap ! (index + 1);
test (addr ! previous) = @(heap ! index) then
{
heap ! index := addr ! next
}
else
{
(addr ! previous) ! next := addr ! next;
}
if addr ! next <> nil then
{
(addr ! next) ! previous := addr ! previous;
}
if next_ptr <> nil then
{
next_ptr ! previous := addr;
}
addr ! previous := prev_ptr;
addr ! next := next_ptr;
heap ! (index + 1) := addr;
heap ! (index + 2) +:= 1 }
let free_vec(addr) be
{
let size = addr ! chunk_size;
//out(“\nfree 0x%x, IS > 0x%x AND < 0x%x\n", addr, (heap + 45), next_free_address);
if addr < (heap + 45) \/ addr > next_free_address then
{
out(“Called freevec on non-heap memory\n”);
return
}
if ~chunk_is_occupied(addr) then
{
out(“memory is already free\n”);
return
}
size -:= 1;
addr ! chunk_size := size;
addr ! size := size;
move_chunk_to_free_list(addr, size)
}
let print_heap() be
{
for i = 0 to 100 do
{
out(“0x%x || “, @(heap ! i));
out(“%d: “, i);
test heap ! i < 10000 then out("%d", heap ! i)
else out("0x%x", heap ! i);
out("\n")
}
}
let init_heap(heap_address) be
{ heap := heap_address;
next_free_address := heap + sizeof_array_of_lists + sizeof_meta_data }
let strart () be
{ let x, y, z;
x := newvec(10);
y := newvec(12);
z := newvec(15);
out("x = 0x%x\n\n", x);
out("y = 0x%x\n\n", y);
out("z = 0x%x\n\n", z);
print_heap();
out("\n\n\n");
freevec(x);
freevec(y);
freevec(z);
print_heap();
out("\n\n\n");
y := newvec(12);
z := newvec(11);
print_heap();
}