function void
string_pool_init(String_Pool* pool)
{
  pool->free_first.next = &pool->free_last;
  pool->free_last.prev = &pool->free_first;
}

function String_Pool_Free_List*
free_string_inner(String_Pool* pool, String_Const_u8 str)
{
  String_Pool_Free_List* free_at = (String_Pool_Free_List*)str.str;
  free_at->next = 0; free_at->prev = 0;
  free_at->size = str.size;

  String_Pool_Free_List* prev = 0;
  for (String_Pool_Free_List* at = pool->free_first.next; at != &pool->free_last; at = prev->next)
  {
    u8* addr = (u8*)at;
    if (addr < (u8*)free_at) prev = at;
    else break;
  }

  if (prev)
  {
    String_Pool_Free_List* next = prev->next;
    prev->next = free_at;
    free_at->prev = prev;
    free_at->next = next;
    next->prev = free_at;

    b8 should_merge = (u8*)prev + prev->size == (u8*)free_at;
    if (should_merge) free_at = prev;
  }
  else
  {
    String_Pool_Free_List* prev = &pool->free_first;
    String_Pool_Free_List* next = pool->free_first.next;
    prev->next = free_at;
    free_at->prev = prev;
    free_at->next = next;
    next->prev = free_at;
  }

  while ((u8*)free_at + free_at->size == (u8*)free_at->next)
  {
    String_Pool_Free_List* next = free_at->next;
    free_at->size += next->size;
    next->next->prev = free_at;
    free_at->next = next->next;
  }

  return free_at;
}

function String_Pool_Free_List*
string_pool_push_buffer(String_Pool* pool, int size_provided, Arena* backing_arena)
{
  u64 next_buffer_size = pool->last_buffer_size * 2;
  if (next_buffer_size == 0) next_buffer_size = KB(4);
  String_Const_u8 buffer_data = string_const_u8_push(backing_arena, next_buffer_size);
  pool->last_buffer_size = next_buffer_size;

  String_Pool_Buffer* buffer = (String_Pool_Buffer*)buffer_data.str;
  buffer_data.str += sizeof(String_Pool_Buffer);
  buffer_data.size -= sizeof(String_Pool_Buffer);
  buffer->data = buffer_data;
  buffer->next = pool->buffers;
  pool->buffers = buffer;

  return free_string_inner(pool, buffer_data);
}

function String_Const_u8
alloc_string(String_Pool* pool, int size_provided, Arena* backing_arena)
{
  int size = ((size_provided + STRING_POOL_ALLOC_SIZE - 1) / STRING_POOL_ALLOC_SIZE) * STRING_POOL_ALLOC_SIZE;

  String_Pool_Free_List* free_at = pool->free_first.next;
  while (free_at != &pool->free_last && free_at->size < size) free_at = free_at->next;

  if (free_at == &pool->free_last || free_at->size < size)
  {
    free_at = string_pool_push_buffer(pool, size, backing_arena);
  }
  Assert(free_at->size >= size);

  String_Const_u8 result;
  result.str = (u8*)free_at;
  result.size = size;

  String_Pool_Free_List* prev = free_at->prev;
  String_Pool_Free_List* next = free_at->next;
  if (free_at->size - size > 0)
  {
    u8* new_free_at_ptr = (u8*)free_at;
    String_Pool_Free_List* new_free_at = (String_Pool_Free_List*)(new_free_at_ptr + size);
    new_free_at->size = free_at->size - size;

    prev->next = new_free_at;
    new_free_at->prev = prev;
    new_free_at->next = next;
    next->prev = new_free_at;
  }
  else
  {
    prev->next = next;
    next->prev = prev;
  }

  block_zero(result.str, result.size);
  return result;
}

function String_Const_u8
alloc_string_copy(String_Pool* pool, String_Const_u8 src, Arena* backing_arena)
{
  String_Const_u8 dst = alloc_string(pool, src.size+1, backing_arena);
  dst.size = src.size;
  block_copy_dynamic_array(dst.str, src.str, src.size);
  dst.str[src.size] = 0;
  return dst;
}

function void
free_string(String_Pool* pool, String_Const_u8 str)
{
  free_string_inner(pool, str);
}