#include <pland/syscall.h>
#include <pland/pcrt.h>
#include <stdbool.h>
#include <stdint.h>

#define MIN_NEW_CHUNK_PAGES 16

struct desc_page_head {
  void *next_page;//0 for last one
};

struct chunk_desc {
  void *start;//0 for a desc not in use
  uint32_t length;
  bool available;
} __attribute__ ((packed));
//without packing, it is 12 bytes and we get 341 per page
//with    packing, it is  9 bytes and we get 454 per page
//maybe i should make available just the top bit of length
//then we get 511 per page, but length has a max of 2^31-1

static struct desc_page_head *first_desc_page = 0;
static struct desc_page_head *last_desc_page = 0;

#define DESCS_PER_PAGE ((4096 - sizeof(struct desc_page_head)) / sizeof(struct chunk_desc))
#define PAGE_AS_ARRAY(p) ((struct chunk_desc *)((void *)p + sizeof(struct desc_page_head)))

static char size_was_buf[] = "size was ......... kB";
//kb should be < 1 000 000 000
static void log_size_was(uint32_t kb) {
  for (int8_t d = 9; d != -1; --d) {
    size_was_buf[9 + d] = (kb % 10) + '0';
    kb /= 10;
  }
  _system_log(size_was_buf);
}

static const char *const hextab = "0123456789abcdef";
static char caller_was_buf[] = "return address is 0x........";
static void log_caller_was(void *addr) {
  const uint32_t as_int = (uint32_t)addr;
  for (uint8_t i = 0; i < 8; ++i)
    caller_was_buf[27 - i] = hextab[(as_int >> (4 * i)) & 0xf];
  _system_log(caller_was_buf);
}

static struct desc_page_head *new_desc_page() {
  struct desc_page_head *dph = _allocate_ram(1);
  if (!dph) {
    _system_log("knob heap could not allocate new descriptor page");
    log_size_was(4);
    __pcrt_quit();
  }
  dph->next_page = 0;
  if (last_desc_page)
    last_desc_page->next_page = dph;
  last_desc_page = dph;

  struct chunk_desc *const a = PAGE_AS_ARRAY(dph);
  for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i)
    a[i].start = 0;

  return dph;
}

static struct chunk_desc *unused_desc() {
  for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) {
    struct chunk_desc *const a = PAGE_AS_ARRAY(i);
    for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i)
      if (!a[i].start)
        return a + i;
  }

  return PAGE_AS_ARRAY(new_desc_page());
}

__attribute__ ((malloc))
void *get_block(uint32_t bytes) {
  if (!first_desc_page)
    first_desc_page = new_desc_page();

  struct chunk_desc *best_fit = 0;

  for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) {
    struct chunk_desc *const a = PAGE_AS_ARRAY(i);
    for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i) {
      if (!a[i].start || !a[i].available || (a[i].length < bytes))
        continue;
      if (a[i].length == bytes) {
        a[i].available = false;
        return a[i].start;
      }
      if (!best_fit || (a[i].length < best_fit->length))
        best_fit = a + i;
    }
  }

  if (!best_fit) {
    const uint32_t pages_needed = (bytes - 1) / 4096 + 1;
    const uint32_t allocating = pages_needed < MIN_NEW_CHUNK_PAGES ? MIN_NEW_CHUNK_PAGES : pages_needed;
    void *const new_chunk = _allocate_ram(allocating);
    if (!new_chunk) {
      _system_log("knob heap could not allocate new chunk");
      log_size_was(allocating * 4);
      log_caller_was(__builtin_return_address(0));
      __pcrt_quit();
    }
    best_fit = unused_desc();
    best_fit->start = new_chunk;
    best_fit->length = allocating * 4096;

    if (bytes == allocating * 4096) {
      best_fit->available = false;
      return new_chunk;
    }
  }

  void *const old_end = best_fit->start + best_fit->length;
  void *const new_end = best_fit->start + bytes;

  best_fit->length = bytes;
  best_fit->available = false;

  struct chunk_desc *const leftover = unused_desc();
  leftover->start = new_end;
  leftover->length = old_end - new_end;

  return best_fit->start;
}

void free_block(const void *block) {
  for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) {
    struct chunk_desc *const a = PAGE_AS_ARRAY(i);
    for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i)
      if (a[i].start == block) {
        //TODO: consolidate this with surrounding free chunks
        a[i].available = true;
        return;
      }
  }
}