main.go

package main

import (
	"fmt"
)

const INIT_BYTES = 1 * 1024 * 1024 // 1mb

type MemBlock struct {
	// Where it starts in the byte slice
	Offset int
	// how big this block is
	Size uint
	// is this block available
	Free bool
	// Next block in the list
	Next *MemBlock
	// Previous block in the list
	Prev *MemBlock
}

type SAllocator struct {
	arena []byte
	head  *MemBlock
}

func InitAllocator(number_of_bytes uint) *SAllocator {
	sa := &SAllocator{
		arena: make([]byte, number_of_bytes),
		head: &MemBlock{
			Offset: 0,
			Size:   number_of_bytes,
			Free:   true,
			Next:   nil,
			Prev:   nil,
		},
	}
	return sa
}

func (s *SAllocator) Alloc(number_of_bytes uint) (int, error) {
	if number_of_bytes == 0 {
		return -1, fmt.Errorf("Invalid memory request of %d bytes is not allowed", number_of_bytes)
	}
	curr := s.head
	for curr != nil {
		if curr.Free && curr.Size >= number_of_bytes {
			// remainder of what we have after we share memory
			rem := curr.Size - number_of_bytes
			// if rem is 0 then use the whole block
			// else rem is not 0 then we can split this block to the next
			if rem == 0 {
				curr.Free = false
				return curr.Offset, nil
			} else {
				curr.Free = false
				curr.Size = number_of_bytes
				s.createNewNode(curr.Next, curr, rem, uint(curr.Offset)+number_of_bytes)
				return curr.Offset, nil
			}
		}
		curr = curr.Next
	}
	return -1, fmt.Errorf("Invalid memory request of %d bytes was not found ", number_of_bytes)
}

func (s *SAllocator) DeAlloc(offset uint) error {
	curr := s.head
	for curr != nil {
		if !curr.Free && curr.Offset == int(offset) {
			for curr.Next != nil && curr.Next.Free {
				// we need to delete the next node
				// update the size of this node
				s.deleteNode(curr, curr.Next)
			}
			for curr.Prev != nil && curr.Prev.Free {
				// move to that node and delete the current node im on
				curr = curr.Prev
				s.deleteNode(curr, curr.Next)
			}
			curr.Free = true
			return nil
		}
		curr = curr.Next
	}

	return fmt.Errorf("no allocated block found at offset %d", offset)
}

func (s *SAllocator) createNewNode(next, prev *MemBlock, newSize, offset uint) {
	new_node := &MemBlock{
		Offset: int(offset),
		Size:   newSize,
		Free:   true,
		Next:   next,
		Prev:   prev,
	}
	if prev != nil {
		prev.Next = new_node
	}
	if next != nil {
		next.Prev = new_node
	}
}

func (s *SAllocator) deleteNode(prev, curr *MemBlock) {
	nxt := curr.Next
	if prev != nil {
		prev.Size += curr.Size
		prev.Next = nxt
	}
	if nxt != nil {
		nxt.Prev = prev
	}
}

func (s *SAllocator) TearDown() {
	s.head = &MemBlock{
		Offset: 0,
		Size:   uint(len(s.arena)),
		Free:   true,
	}
}
func main() {
	sa := InitAllocator(1024)

	offset, err := sa.Alloc(100)
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Printf("Allocated at offset %d\n", offset)

	err = sa.DeAlloc(uint(offset))
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Printf("Deallocated offset %d\n", offset)

	sa.TearDown()
	fmt.Println("Allocator reset")
}