Answer Happy

I need to change this first fit algorithm to best fit and a
compaction algorithm ( join fre space together) any help?
import array, random
mem_size = (64*1024)
MAGIC_ALLOCATED_BLOCK = 12345
MAGIC_NO_NEXT_FREE_BLOCK = 99999999
# Our memory is 64K unsigned 32-bit integers (so, 256 kB)
memory = array.array('L', [0] * mem_size)
# memory cell 0 will be always pointing to the first free
block
# free block layout:
# memory[start] = size
# memory[start+1] = address_of_the_next_block
# allocated block layout:
# memory[start-2] = size
# memory[start-1] = MAGIC_ALLOCATED_BLOCK
# the user data can be written from the start
def init_free_block(location, size, next_free_block,
where_to_place_pointer_to_this_block):
memory[location] = size
memory[location + 1] = next_free_block # next
block
memory[where_to_place_pointer_to_this_block] =
location
def allocate(size):
free_block_ptr_address = 0
free_block_header_ptr =
memory[free_block_ptr_address]
while free_block_header_ptr !=
MAGIC_NO_NEXT_FREE_BLOCK:
block_size =
memory[free_block_header_ptr]
if block_size >= size:
if block_size >=
size+3:

init_free_block(free_block_header_ptr + 2 + size, block_size - size
- 2, memory[free_block_header_ptr+1], free_block_ptr_address)

memory[free_block_header_ptr] = size
else:

memory[free_block_ptr_address] =
memory[free_block_header_ptr+1]

memory[free_block_header_ptr+1] = MAGIC_ALLOCATED_BLOCK
return
free_block_header_ptr+2
free_block_ptr_address =
free_block_header_ptr + 1
free_block_header_ptr =
memory[free_block_ptr_address]
raise Exception(f"could not allocate requested {size}
elements of memory space")
def free(pointer):
assert memory[pointer - 1] ==
MAGIC_ALLOCATED_BLOCK
init_free_block(pointer - 2, memory[pointer - 2],
memory[0], 0)
def max_object_can_allocate():
pointer = memory[0]
m = 0
while pointer != MAGIC_NO_NEXT_FREE_BLOCK:
block_size = memory[pointer]
if block_size > m:
m = block_size
pointer = memory[pointer + 1]
return m
def total_free_ram():
pointer = memory[0]
s = 0
while pointer != MAGIC_NO_NEXT_FREE_BLOCK:
block_size = memory[pointer]
s += block_size
pointer = memory[pointer + 1]
return s
def stats():
pointer = memory[0]
m = 0
count = 0
total = 0
while pointer != MAGIC_NO_NEXT_FREE_BLOCK:
block_size = memory[pointer]
if block_size > m:
m = block_size
total += block_size
count += 1
pointer = memory[pointer + 1]
return dict(
total_free_ram=total,
max_free_block=m,
overhead=count*2,
)
def ensure_no_overlaps(block_pointers):
# inefficient but simple check
all_used_cells = set()
for p in block_pointers:
assert memory[p - 1] ==
MAGIC_ALLOCATED_BLOCK
size = memory[p - 2]
used_cells = set(range(p,
p+size))
assert len(all_used_cells &
used_cells) == 0
all_used_cells.update(used_cells)
init_free_block(1, mem_size - 3, MAGIC_NO_NEXT_FREE_BLOCK, 0)
print(stats())
all_allocated_blocks = []
for i in range(50):
a = allocate(random.randint(10, 50)*16)
b = allocate(random.randint(10, 50)*16)
c = allocate(random.randint(10, 50)*16)
d = allocate(random.randint(10, 50)*16)
e = allocate(random.randint(10, 50)*16)
ensure_no_overlaps(all_allocated_blocks +
[a,b,c,d,e])
free(a)
free(b)
free(c)
free(d)
all_allocated_blocks.append(e)
print(stats())