Add efficient realloc()
diff --git a/src/kernel/alloc.c b/src/kernel/alloc.c
index 4edc791..bcd58ae 100644
--- a/src/kernel/alloc.c
+++ b/src/kernel/alloc.c
@@ -157,7 +157,8 @@
// Header of block before this one
struct heap_alloc_header *prev_h =
- (struct heap_alloc_header *)((size_t)prev_f - prev_f->size + FOOTER_SIZE);
+ (struct heap_alloc_header *)((size_t)prev_f - prev_f->size +
+ FOOTER_SIZE);
// Header of block after this one
struct heap_alloc_header *next_h =
@@ -190,3 +191,79 @@
heap_insert(&heap, entry);
}
+
+void *realloc(void *mem, size_t size)
+{
+ if (!mem)
+ return NULL; // freeing NULL ptr
+
+ struct heap_alloc_header *base =
+ (struct heap_alloc_header *)((size_t)mem - HEADER_SIZE);
+ struct heap_alloc_header *next =
+ (struct heap_alloc_header *)((size_t)base + base->size);
+
+ if (!next->allocated &&
+ next->size + base->size - HEADER_SIZE - FOOTER_SIZE >= size)
+ {
+ // Okay, we can just expand this block
+ // Actually, need to check if there is enough space remaining for an
+ // additional block, otherwise, just add that memory to this block (
+ // same as is done in malloc )
+
+ struct heap_alloc_footer *f;
+
+ size_t remaining =
+ base->size + next->size - size - HEADER_SIZE - FOOTER_SIZE;
+
+ struct heap_entry old_entry = {
+ .key = next->size,
+ .address = (size_t)next,
+ };
+
+ if (remaining <= HEADER_SIZE + FOOTER_SIZE + 8)
+ {
+ // Just join this into the same memory chunk
+ f = (struct heap_alloc_footer *)(next + next->size - FOOTER_SIZE);
+
+ heap_delete_entry(&heap, old_entry);
+ }
+ else
+ {
+ f = mem + size;
+ struct heap_alloc_header *new_h =
+ (struct heap_alloc_header *)(f + FOOTER_SIZE);
+
+ struct heap_alloc_footer *new_f =
+ (struct heap_alloc_footer *)(new_h + remaining - FOOTER_SIZE);
+
+ new_h->allocated = false;
+ new_h->size = new_f->size = remaining;
+ new_h->magic = HEAP_MAGIC;
+
+ struct heap_entry entry = {
+ .key = remaining,
+ .address = (size_t)new_h,
+ };
+
+ heap_decrease_entry(&heap, old_entry, entry);
+ }
+
+ size_t full_size = (size_t)f - (size_t)base + FOOTER_SIZE;
+
+ f->size = full_size;
+ base->size = full_size;
+ base->magic = HEAP_MAGIC;
+ base->allocated = true;
+ }
+ else
+ {
+ void *new = malloc(size);
+ if (!new)
+ return new;
+
+ memcpy(new, mem, base->size - HEADER_SIZE - FOOTER_SIZE);
+ free(mem);
+
+ return new;
+ }
+}
diff --git a/src/kernel/alloc.h b/src/kernel/alloc.h
index 4cb046d..7312ae2 100644
--- a/src/kernel/alloc.h
+++ b/src/kernel/alloc.h
@@ -9,5 +9,6 @@
void *malloc(size_t size);
void free(void *mem);
+void *realloc(void *mem, size_t size);
void init_allocator();
diff --git a/src/kernel/kheap.c b/src/kernel/kheap.c
index 31de626..3fc2f8c 100644
--- a/src/kernel/kheap.c
+++ b/src/kernel/kheap.c
@@ -136,3 +136,40 @@
return (struct heap_entry){0};
}
}
+
+static int heap_entry_index(struct min_heap *heap, struct heap_entry e)
+{
+ size_t key = e.key;
+ int i = 0;
+
+ struct heap_entry *a = heap->elements;
+
+ while (i < heap->size && a[i].key != key)
+ {
+ int left = heap_left(i),
+ right = heap_right(i);
+
+ if (left >= heap->size)
+ i = right;
+ else if (right >= heap->size)
+ i = left;
+ else
+ i = a[left].key < a[right].key ? left : right;
+ }
+
+ if (i >= heap->size)
+ return -1;
+ else
+ return i;
+}
+
+void heap_decrease_entry(struct min_heap *heap, struct heap_entry from,
+ struct heap_entry to)
+{
+ heap_decrease(heap, heap_entry_index(heap, from), to);
+}
+
+void heap_delete_entry(struct min_heap *heap, struct heap_entry e)
+{
+ heap_delete(heap, heap_entry_index(heap, e));
+}
diff --git a/src/kernel/kheap.h b/src/kernel/kheap.h
index bc42620..a8b0bb5 100644
--- a/src/kernel/kheap.h
+++ b/src/kernel/kheap.h
@@ -34,9 +34,12 @@
int heap_parent(int i);
int heap_left(int i);
int heap_right(int i);
-void heap_delete(struct min_heap *heap, int k);
+void heap_delete(struct min_heap *heap, int i);
void heap_insert(struct min_heap *heap, struct heap_entry e);
void heap_decrease(struct min_heap *heap, int k, struct heap_entry to);
+void heap_decrease_entry(struct min_heap *heap, struct heap_entry from,
+ struct heap_entry to);
+void heap_delete_entry(struct min_heap *heap, struct heap_entry e);
struct heap_entry heap_lookup_min(struct min_heap *heap, int min, bool *ok,
bool delete, int *i);