// generated by Google Gemini Flash 3.5 (extended thinking)

#define NULL ((void*)0)
#define WASM_PAGE_SIZE 65536

typedef struct FreeNode {
  struct FreeNode* next;
} FreeNode;

typedef struct {
  unsigned long long bucket;
  unsigned long long reserved;
} Header;

extern unsigned char __heap_base;
static FreeNode* buckets[60] = {NULL};
static unsigned char* managed_end = NULL;
static unsigned char* mem_limit = NULL;

static inline int get_bucket(unsigned long long size) {
  unsigned long long needed = size + 16;
  if (needed <= 32)
    return 0;
  return 63 - __builtin_clzll(needed - 1) - 4;
}

void* malloc(unsigned long long size) {
  if (!size)
    return NULL;

  int b = get_bucket(size);

  if (buckets[b]) {
    FreeNode* node = buckets[b];
    buckets[b] = node->next;
    Header* header = (Header*)node;
    header->bucket = b;
    return (void*)(header + 1);
  }

  unsigned long long block_size = 1ULL << (b + 5);

  if (!managed_end) {
    managed_end =
        (unsigned char*)(((unsigned long long)&__heap_base + 15) & ~15);
    mem_limit =
        (unsigned char*)(__builtin_wasm_memory_size(0) * WASM_PAGE_SIZE);
  }

  if (managed_end + block_size > mem_limit) {
    unsigned long long bytes_to_grow = (managed_end + block_size) - mem_limit;
    unsigned long long pages_to_grow =
        (bytes_to_grow + WASM_PAGE_SIZE - 1) / WASM_PAGE_SIZE;
    if (__builtin_wasm_memory_grow(0, pages_to_grow) == -1ULL) {
      return NULL;
    }
    mem_limit += pages_to_grow * WASM_PAGE_SIZE;
  }

  Header* header = (Header*)managed_end;
  header->bucket = b;
  managed_end += block_size;
  return (void*)(header + 1);
}

void free(void* ptr) {
  if (!ptr)
    return;

  Header* header = (Header*)ptr - 1;
  unsigned long long b = header->bucket;

  FreeNode* node = (FreeNode*)header;
  node->next = buckets[b];
  buckets[b] = node;
}

void* realloc(void* ptr, unsigned long long size) {
  if (!ptr)
    return malloc(size);
  if (!size) {
    free(ptr);
    return NULL;
  }

  Header* header = (Header*)ptr - 1;
  unsigned long long b = header->bucket;
  unsigned long long current_max_payload = (1ULL << (b + 5)) - 16;

  if (size <= current_max_payload) {
    unsigned long long min_payload = b == 0 ? 0 : (1ULL << (b + 4)) - 16;
    if (size > min_payload) {
      return ptr;
    }
  }

  void* new_ptr = malloc(size);
  if (!new_ptr)
    return NULL;

  unsigned long long copy_size =
      current_max_payload < size ? current_max_payload : size;
  __builtin_memcpy(new_ptr, ptr, copy_size);

  free(ptr);
  return new_ptr;
}