More Code Examples
Here is a bit of code manually converted to C3 from C.
const uint OFFSET = 8;const uint BIN_COUNT = 9;const uint BIN_MAX_IDX = BIN_COUNT - 1;const uint OVERHEAD = Footer.sizeof + Node.sizeof;const usz MIN_WILDERNESS = 0x2000;const usz MAX_WILDERNESS = 0x1000000;const usz HEAP_INIT_SIZE = 0x10000;const usz HEAP_MAX_SIZE = 0xF0000;const usz HEAP_MIN_SIZE = 0x10000;const uint MIN_ALLOC_SZ = 4;
struct Node{ uint hole; uint size; Node* next; Node* prev;}
struct Footer{ Node *header;}
struct Bin{ Node* head;}
struct Heap{ uptr start; uptr end; Bin*[BIN_COUNT] bins;}
/** * @require start > 0 */fn void Heap.init(&heap, uptr start){ Node* init_region = (Node*)start; init_region.hole = 1; init_region.size = HEAP_INIT_SIZE - Node.sizeof - Footer.sizeof;
init_region.create_foot();
heap.bins[get_bin_index(init_region.size)].add_node(init_region);
heap.start = start; heap.end = start + HEAP_INIT_SIZE;}
fn void* Heap.alloc(&heap, uint size){ uint index = get_bin_index(size); Bin* temp = heap.bins[index]; Node* found = temp.get_best_fit(size);
while (!found) { temp = heap.bins[++index]; found = temp.get_best_fit(size); }
if (found.size - size > OVERHEAD + MIN_ALLOC_SZ) { Node* split = (Node*)((void*)found + Node.sizeof + Footer.sizeof) + size; split.size = found.size - size - (uint)Node.sizeof - (uint)Footer.sizeof; split.hole = 1;
split.create_foot();
uint new_idx = get_bin_index(split.size);
heap.bins[new_idx].add_node(split);
found.size = size; found.create_foot(); }
found.hole = 0; heap.bins[index].remove_node(found);
Node* wild = heap.get_wilderness(); if (wild.size < MIN_WILDERNESS) { if (!heap.expand(0x1000)) return null; } else if (wild.size > MAX_WILDERNESS) { heap.contract(0x1000); }
found.prev = null; found.next = null; return &found.next;}
/** * @param [&inout] p */fn void Heap.free(&heap, void* p){
Node* head = (void*)p - OFFSET; if (head == (Node*)heap.start) { head.hole = 1; heap.bins[get_bin_index(head.size)].add_node(head); return; }
Node* next = (void*)head.get_foot() + Footer.sizeof; Footer* f = (void*)head - Footer.sizeof; Node* prev = f.header;
Bin* list; Footer* new_foot; if (prev.hole) { list = heap.bins[get_bin_index(prev.size)]; list.remove_node(prev);
prev.size += OVERHEAD + head.size; new_foot = head.get_foot(); new_foot.header = prev;
head = prev; }
if (next.hole) { list = heap.bins[get_bin_index(next.size)]; list.remove_node(next);
head.size += OVERHEAD + next.size;
Footer* old_foot = next.get_foot(); old_foot.header = null; next.size = 0; next.hole = 0;
new_foot = head.get_foot(); new_foot.header = head; }
head.hole = 1; heap.bins[get_bin_index(head.size)].add_node(head);}
fn uint Heap.expand(&heap, usz sz){ return 0;}
fn void Heap.contract(&heap, usz sz){ return;}
fn uint get_bin_index(usz sz){ uint index = 0; sz = sz < 4 ? 4 : sz;
while (sz >>= 1) index++; index -= 2;
if (index > BIN_MAX_IDX) index = BIN_MAX_IDX; return index;}
fn void Node.create_foot(&head){ Footer* foot = head.get_foot(); foot.header = head;}
fn Footer* Node.get_foot(&node){ return (void*)node + Node.sizeof + node.size;}
fn Node* Heap.get_wilderness(&heap){ Footer* wild_foot = (void*)heap.end - Footer.sizeof; return wild_foot.header;}
fn void Bin.remove_node(&bin, Node* node){ if (!bin.head) return; if (bin.head == node) { bin.head = bin.head.next; return; }
Node* temp = bin.head.next; while (temp) { if (temp == node) { if (!temp.next) { temp.prev.next = null; } else { temp.prev.next = temp.next; temp.next.prev = temp.prev; } return; } temp = temp.next; }}
fn void Bin.add_node(&bin, Node* node){ node.next = null; node.prev = null;
Node* temp = bin.head;
if (!bin.head) { bin.head = node; return; }
Node* current = bin.head; Node* previous = null;
while (current != null && current.size <= node.size) { previous = current; current = current.next; }
if (!current) { previous.next = node; node.prev = previous; } else { if (previous) { node.next = current; previous.next = node;
node.prev = previous; current.prev = node; } else { node.next = bin.head; bin.head.prev = node; bin.head = node; } }}
fn Node* Bin.get_best_fit(&bin, usz size){ if (!bin.head) return null;
Node* temp = bin.head;
while (temp) { if (temp.size >= size) return temp; temp = temp.next; } return null;}