# Zig läxa

Implementera 2ish allocators i programmeringspråket Zig.

De kan vara hur avancerade ni vill men helst mer avancerat än implementationen av en linear allocator jag ger här.

Om ni känner att en allocator ni vill implementera är väldigt komplicerad så får ni också fokusera på bara en och ni behöver inte göra en andra.

Längst ner på sidan finns exexmpel på allocators, men om ni hittar andra får ni gärna implementera dem istället.

## Zig resurser
* [Dokumentation för språket (ZigDocs)](https://ziglang.org/documentation/master/)
* [Github repo för språket](https://github.com/ziglang/zig)
* Om ni undrar över hur saker fungerar i standard library kolla under lib/std. Under lib/std/heap finns implementationer av några allocators
* [Zig learn](https://ziglearn.org/)
* Ger lite introduktion till språket, visar också hur du kan installera kompilatorn och en language server

## Allocator resurser
Allocators hanterar allokering och frigöring av minne genom olika datastrukturer och algoritmer.
Det enklaste exemplet på en allocator skulle vara en linear allocator.

En linear allocator har en pekare till en bit minne den äger, och en pekare (eller index) till nästa fria del av det minnet. När du allokerar så ger allocatorn tillbaka pekaren till nästa del fritt minne och flyttar pekaren med storleken av din allokering. Denna allocator har dock ingen möjlighet att frigöra minne som inte var en del av din sista allokering. (Denna beskrivning saknar också hantering av alignment)


#### Exempel på en linear allocator skriven i Zig:
Det här är den enklaste implementationen av en linear allocator, den hanterar t.ex inte frigöring av den senaste allokeringen och kan inte växa när minnet av buffern tar slut. Detta exempel är mer för att ge en känsla över hur en implementation kan se ut och ger en grund att börja från.

const std = @import("std");
const Allocator = std.mem.Allocator;

pub const LinearAllocator = struct {
    underlying: std.mem.Allocator,
    buffer: []u8,
    current_index: usize,

    pub fn init(underlying: std.mem.Allocator, size: usize) !LinearAllocator {
        return LinearAllocator{
            .underlying = underlying,
            .buffer = try underlying.alloc(u8, size),
            .current_index = 0,
        };
    }

    pub fn deinit(self: LinearAllocator) void {
        self.underlying.free(self.buffer);
    }

    pub fn allocator(self: *LinearAllocator) Allocator {
        return Allocator.init(self, alloc, resize, free);
    }

    fn alloc(
        self: *LinearAllocator,
        size: usize,
        ptr_align: u29,
        len_align: u29,
        ret_addr: usize,
    ) error{OutOfMemory}![]u8 {
        _ = len_align;

        // The return address is not needed, it can be used when detecting memory leaks (See GeneralPurposeAllocator)
        _ = ret_addr;

        // Align ptr to required pointer alignment
        const aligned_ptr = std.mem.alignForward(@ptrToInt(self.buffer.ptr) + self.current_index, ptr_align);

        // Calculate the index in the buffer of the aligned pointer
        const aligned_index = aligned_ptr - @ptrToInt(self.buffer.ptr);

        // Calculate the end index of the allocation
        const end_index = aligned_index + size;

        // If the end index is past the end of the allocator buffer return an OutOfMemory error
        if (end_index >= self.buffer.len) return error.OutOfMemory;

        // Create a slice of the allocator buffer for the allocation
        const allocation = self.buffer[aligned_index..end_index];

        // Set the current index to the end of the allocation buffer
        self.current_index = end_index;

        return allocation;
    }

    fn resize(
        self: *LinearAllocator,
        buf: []u8,
        buf_align: u29,
        new_size: usize,
        len_align: u29,
        ret_addr: usize,
    ) ?usize {
        _ = self;
        _ = buf_align;
        _ = ret_addr;

        // We can't grow any allocation because we might grow into another one
        if (new_size > buf.len) return null;

        // But we can shrink the allocation easily
        return std.mem.alignAllocLen(buf.len, new_size, len_align);
    }

    // The linear allocator can't free memory
    fn free(
        self: *LinearAllocator,
        buf: []u8,
        buf_align: u29,
        ret_addr: usize,
    ) void {
        _ = self;
        _ = buf_align;
        _ = ret_addr;
        _ = buf;
    }
};

### Andra typer allocators
#### Arena allocators
#### Free list
Denna allocator är relativt simpel och använder sig av en länkad lista för att hålla koll på allokeringar så att de senare kan frigöras. (Är ganska lätt att bygga ovanpå mitt linear allocator exempel).
#### Slab allocator
* https://www.kernel.org/doc/gorman/html/understand/understand011.html
#### Buddy allocator
* https://en.wikipedia.org/wiki/Buddy_memory_allocation
* https://people.kth.se/~johanmon/ose/assignments/buddy.pdf
#### Allocators in the linux kernel
* https://hammertux.github.io/slab-allocator