<commit_before>/*
This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to <http://unlicense.org/>
*/

/**
 * \file coalescingalloc.h
 * \date Jul 07, 2016
 */

#ifndef AKMALLOC_COALESCING_ALLOC_H
#define AKMALLOC_COALESCING_ALLOC_H

#include "akmalloc/assert.h"
#include "akmalloc/spinlock.h"
#include "akmalloc/inline.h"
#include "akmalloc/constants.h"
#include "akmalloc/setup.h"

/**
 * We choose a minimum alignment of 16. One could increase this, but not decrease.
 *
 * 16 byte alignment buys us a few things:
 * - The 3 low-bits of an address will be 000. Therefore we can store metadata in them.
 * - On x64, we can exactly store two pointers worth of information in any block which
 *   can be used to house an implicit free list.
 */
#define AK_COALESCE_ALIGN 16

#if !defined(AK_COALESCE_SEGMENT_GRANULARITY)
#  define AK_COALESCE_SEGMENT_GRANULARITY 65536
#endif

#if !defined(AK_COALESCE_SEGMENT_SIZE)
/* 64KB */
#  define AK_COALESCE_SEGMENT_SIZE AK_COALESCE_SEGMENT_GRANULARITY
#endif

#if defined(AK_CA_USE_LOCKS)
#  define AK_CA_LOCK_DEFINE(nm)    ak_spinlock nm
#  define AK_CA_LOCK_INIT(root)    ak_spinlock_init(ak_as_ptr((root)->LOCKED))
#  define AK_CA_LOCK_ACQUIRE(root) ak_spinlock_acquire(ak_as_ptr((root)->LOCKED))
#  define AK_CA_LOCK_RELEASE(root) ak_spinlock_release(ak_as_ptr((root)->LOCKED))
#else
#  define AK_CA_LOCK_DEFINE(nm)
#  define AK_CA_LOCK_INIT(root)
#  define AK_CA_LOCK_ACQUIRE(root)
#  define AK_CA_LOCK_RELEASE(root)
#endif

typedef ak_sz ak_alloc_info;

typedef struct ak_alloc_node_tag ak_alloc_node;

typedef struct ak_free_list_node_tag ak_free_list_node;

typedef struct ak_ca_segment_tag ak_ca_segment;

typedef struct ak_ca_root_tag ak_ca_root;

struct ak_alloc_node_tag
{
#if AKMALLOC_BITNESS == 32
    ak_alloc_info _unused0;
    ak_alloc_info _unused1;
#endif
    ak_alloc_info previnfo;
    ak_alloc_info currinfo;
};

struct ak_free_list_node_tag
{
    ak_free_list_node* bk;
    ak_free_list_node* fd;
};

struct ak_ca_segment_tag
{
    ak_ca_segment* bk;
    ak_ca_segment* fd;
    ak_sz sz;
    ak_alloc_node* head;
};

struct ak_ca_root_tag
{
    ak_ca_segment main_root;
    ak_ca_segment empty_root;

    ak_free_list_node free_root;

    ak_u32 nempty;
    ak_u32 release;

    ak_u32 RELEASE_RATE;
    ak_u32 MAX_SEGMENTS_TO_FREE;
    ak_sz MIN_SIZE_TO_SPLIT;

    AK_CA_LOCK_DEFINE(LOCKED);
};

/**************************************************************/
/* P R I V A T E                                              */
/**************************************************************/

#define ak_ca_to_sz(p) (((ak_sz)(p)) & ~(AK_COALESCE_ALIGN - 1))

#define ak_ca_is_first(p) (((ak_sz)(p)) & (AK_SZ_ONE << 0))

#define ak_ca_is_last(p) (((ak_sz)(p)) & (AK_SZ_ONE << 1))

#define ak_ca_is_free(p) (((ak_sz)(p)) & (AK_SZ_ONE << 2))

ak_inline static void ak_ca_set_sz(ak_alloc_info* p, ak_sz sz)
{
    AKMALLOC_ASSERT(sz == ak_ca_to_sz((ak_alloc_info)sz));
    // 7 because there are only 3 useful bits. the fourth bit may collect garbage.
    *p = (ak_alloc_info)((((ak_sz)*p)  &  ((ak_sz)7)) |
                                 (sz   & ~(AK_COALESCE_ALIGN - 1)));
}

ak_inline static void ak_ca_set_is_first(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 0)) | (v ? (AK_SZ_ONE << 0) : 0));
}

ak_inline static void ak_ca_set_is_last(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 1)) | (v ? (AK_SZ_ONE << 1) : 0));
}

ak_inline static void ak_ca_set_is_free(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 2)) | (v ? (AK_SZ_ONE << 2) : 0));
}

ak_inline static ak_alloc_node* ak_ca_next_node(ak_alloc_node* node)
{
    return ak_ca_is_last(node->currinfo)
                ? AK_NULLPTR
                : (ak_alloc_node*)((char*)(node + 1) + ak_ca_to_sz(node->currinfo));
}

ak_inline static ak_alloc_node* ak_ca_prev_node(ak_alloc_node* node)
{
    return ak_ca_is_first(node->currinfo)
                ? AK_NULLPTR
                : (ak_alloc_node*)((char*)(node - 1) - ak_ca_to_sz(node->previnfo));
}

ak_inline static void ak_ca_update_footer(ak_alloc_node* p)
{
    ak_alloc_node* n = ak_ca_next_node(p);
    if (n) {
        n->previnfo = p->currinfo;
    }
}

#define ak_free_list_node_unlink(node)               \
  do {                                               \
    ak_free_list_node* const sU = (node);            \
    sU->bk->fd = (sU->fd);                           \
    sU->fd->bk = (sU->bk);                           \
    sU->fd = sU->bk = AK_NULLPTR;                    \
  } while (0)

#define ak_free_list_node_link_fd(node, fwd)         \
  do {                                               \
    ak_free_list_node* const sLF = (node);           \
    ak_free_list_node* const fLF = (fwd);            \
    sLF->fd = fLF;                                   \
    fLF->bk = sLF;                                   \
  } while (0)

#define ak_free_list_node_link_bk(node, back)        \
  do {                                               \
    ak_free_list_node* const sLB = (node);           \
    ak_free_list_node* const bLB = (back);           \
    sLB->bk = bLB;                                   \
    bLB->fd = sLB;                                   \
  } while (0)

#define ak_free_list_node_link(node, fwd, back)      \
  do {                                               \
    ak_free_list_node* const sL = (node);            \
    ak_free_list_node* const fL = (fwd);             \
    ak_free_list_node* const bL = (back);            \
    ak_free_list_node_link_bk(sL, bL);               \
    ak_free_list_node_link_fd(sL, fL);               \
  } while (0)

#define ak_ca_segment_unlink(node)                   \
  do {                                               \
    ak_ca_segment* const sU = (node);                \
    sU->bk->fd = (sU->fd);                           \
    sU->fd->bk = (sU->bk);                           \
    sU->fd = sU->bk = AK_NULLPTR;                    \
  } while (0)

#define ak_ca_segment_link_fd(node, fwd)             \
  do {                                               \
    ak_ca_segment* const sLF = (node);               \
    ak_ca_segment* const fLF = (fwd);                \
    sLF->fd = fLF;                                   \
    fLF->bk = sLF;                                   \
  } while (0)

#define ak_ca_segment_link_bk(node, back)            \
  do {                                               \
    ak_ca_segment* const sLB = (node);               \
    ak_ca_segment* const bLB = (back);               \
    sLB->bk = bLB;                                   \
    bLB->fd = sLB;                                   \
  } while (0)

#define ak_ca_segment_link(node, fwd, back)          \
  do {                                               \
    ak_ca_segment* const sL = (node);                \
    ak_ca_segment* const fL = (fwd);                 \
    ak_ca_segment* const bL = (back);                \
    ak_ca_segment_link_bk(sL, bL);                   \
    ak_ca_segment_link_fd(sL, fL);                   \
  } while (0)

#define ak_circ_list_for_each(type, name, list)      \
    type* name = (list)->fd;                         \
    for(type* const iterroot = (list); name != iterroot; name = name->fd)

#define ak_ca_aligned_size(x) ((x) ? (((x) + AK_COALESCE_ALIGN - 1) & ~(AK_COALESCE_ALIGN - 1)) : AK_COALESCE_ALIGN)

#define ak_ca_aligned_segment_size(x) (((x) + (AK_COALESCE_SEGMENT_SIZE) - 1) & ~((AK_COALESCE_SEGMENT_SIZE) - 1))

static void* ak_ca_search_free_list(ak_free_list_node* root, ak_sz sz, ak_sz splitsz)
{
    // walk through list finding the first element that fits and split
    ak_circ_list_for_each(ak_free_list_node, node, root) {
        ak_alloc_node* n = ((ak_alloc_node*)(node)) - 1;
        AKMALLOC_ASSERT(ak_ca_is_free(n->currinfo));
        ak_sz nodesz = ak_ca_to_sz(n->currinfo);
        if (nodesz >= sz) {
            if ((nodesz - sz) > splitsz) {
                // split and assign
                ak_alloc_node* newnode = (ak_alloc_node*)(((char*)node) + sz);
                int islast = ak_ca_is_last(n->currinfo);

                ak_ca_set_sz(ak_as_ptr(n->currinfo), sz);
                ak_ca_set_is_last(ak_as_ptr(n->currinfo), 0);
                ak_ca_set_is_free(ak_as_ptr(n->currinfo), 0);
                ak_ca_update_footer(n);

                ak_ca_set_sz(ak_as_ptr(newnode->currinfo), nodesz - sz - sizeof(ak_alloc_node));
                ak_ca_set_is_first(ak_as_ptr(newnode->currinfo), 0);
                ak_ca_set_is_last(ak_as_ptr(newnode->currinfo), islast);
                ak_ca_set_is_free(ak_as_ptr(newnode->currinfo), 1);
                ak_ca_update_footer(newnode);
                
                // copy free list node from node
                ak_free_list_node* fl = (ak_free_list_node*)(newnode + 1);
                ak_free_list_node_link(fl, node->fd, node->bk);
                AKMALLOC_ASSERT(n->currinfo == newnode->previnfo);
            } else {
                // return as is
                ak_ca_set_is_free(ak_as_ptr(n->currinfo), 0);
                ak_ca_update_footer(n);
                ak_free_list_node_unlink(node);
            }
            return node;
        }
    }
    return AK_NULLPTR;
}

static int ak_ca_add_new_segment(ak_ca_root* root, char* mem, ak_sz sz)
{
    if (ak_likely(mem)) {
        // make segment
        ak_ca_segment* seg = (ak_ca_segment*)(mem + sz - sizeof(ak_ca_segment));
        ak_ca_segment_link(seg, root->main_root.fd, ak_as_ptr(root->main_root));
        seg->sz = sz;
        seg->head = (ak_alloc_node*)mem;
        {// add to free list
            ak_alloc_node* hd = seg->head;
            ak_sz actualsize = (sz - sizeof(ak_alloc_node) - sizeof(ak_ca_segment));
            // store actual size in previnfo
            hd->previnfo = actualsize;
            ak_ca_set_is_first(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_is_last(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_is_free(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_sz(ak_as_ptr(hd->currinfo), actualsize);
            ak_free_list_node* fl = (ak_free_list_node*)(hd + 1);
            ak_free_list_node_link(fl, root->free_root.fd, ak_as_ptr(root->free_root));
        }
        return 1;
    }
    return 0;
}

static int ak_ca_get_new_segment(ak_ca_root* root, ak_sz sz)
{
    // align to segment size multiple
    sz += sizeof(ak_ca_segment) + sizeof(ak_alloc_node) + sizeof(ak_free_list_node);
    sz = ak_ca_aligned_segment_size(sz);

    // search empty_root for a segment that is as big or more
    char* mem = AK_NULLPTR;
    ak_sz segsz = sz;
    ak_circ_list_for_each(ak_ca_segment, seg, ak_as_ptr(root->empty_root)) {
        if (seg->sz >= sz) {
            mem = (char*)(seg->head);
            segsz = seg->sz;
            ak_ca_segment_unlink(seg);
            --(root->nempty);
            break;
        }
    }

    return ak_ca_add_new_segment(root, mem ? mem : ((char*)ak_os_alloc(sz)), segsz);
}

static ak_u32 ak_ca_return_os_mem(ak_ca_segment* r, ak_u32 num)
{
    ak_u32 ct = 0;
    ak_ca_segment* next = r->fd;
    ak_ca_segment* curr = next;
    for(; curr != r; curr = next) {
        if (ct >= num) {
            break;
        }
        next = curr->fd;
        ak_ca_segment_unlink(curr);
        ak_os_free(curr->head, curr->sz);
        ++ct;
    }
    return ct;
}

/**************************************************************/
/* P U B L I C                                                */
/**************************************************************/

static void ak_ca_init_root(ak_ca_root* root, ak_u32 relrate, ak_u32 maxsegstofree)
{
    AKMALLOC_ASSERT_ALWAYS(AK_COALESCE_SEGMENT_SIZE % AK_COALESCE_SEGMENT_GRANULARITY == 0);
    AKMALLOC_ASSERT_ALWAYS(((AK_COALESCE_SEGMENT_SIZE & (AK_COALESCE_SEGMENT_SIZE - 1)) == 0) && "Segment size must be a power of 2");

    ak_ca_segment_link(&(root->main_root), &(root->main_root), &(root->main_root));
    ak_ca_segment_link(&(root->empty_root), &(root->empty_root), &(root->empty_root));
    ak_free_list_node_link(&(root->free_root), &(root->free_root), &(root->free_root));
    root->nempty = root->release = 0;

    root->RELEASE_RATE = relrate;
    root->MAX_SEGMENTS_TO_FREE = maxsegstofree;
    root->MIN_SIZE_TO_SPLIT = (sizeof(ak_alloc_node) + sizeof(ak_free_list_node));
    AK_CA_LOCK_INIT(root);
}

ak_inline static void ak_ca_init_root_default(ak_ca_root* root)
{
#if AKMALLOC_BITNESS == 32
    static const ak_u32 rate =  255;
#else
    static const ak_u32 rate = 2047;
#endif
    ak_ca_init_root(root, rate, rate);
}

static void* ak_ca_alloc(ak_ca_root* root, ak_sz s)
{<commit_msg> "Fix coalescing alloc behaviour with MIN_SPLIT_SIZE"<commit_after>/*
This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to <http://unlicense.org/>
*/

/**
 * \file coalescingalloc.h
 * \date Jul 07, 2016
 */

#ifndef AKMALLOC_COALESCING_ALLOC_H
#define AKMALLOC_COALESCING_ALLOC_H

#include "akmalloc/assert.h"
#include "akmalloc/spinlock.h"
#include "akmalloc/inline.h"
#include "akmalloc/constants.h"
#include "akmalloc/setup.h"

/**
 * We choose a minimum alignment of 16. One could increase this, but not decrease.
 *
 * 16 byte alignment buys us a few things:
 * - The 3 low-bits of an address will be 000. Therefore we can store metadata in them.
 * - On x64, we can exactly store two pointers worth of information in any block which
 *   can be used to house an implicit free list.
 */
#define AK_COALESCE_ALIGN 16

#if !defined(AK_COALESCE_SEGMENT_GRANULARITY)
#  define AK_COALESCE_SEGMENT_GRANULARITY 65536
#endif

#if !defined(AK_COALESCE_SEGMENT_SIZE)
/* 64KB */
#  define AK_COALESCE_SEGMENT_SIZE AK_COALESCE_SEGMENT_GRANULARITY
#endif

#if defined(AK_CA_USE_LOCKS)
#  define AK_CA_LOCK_DEFINE(nm)    ak_spinlock nm
#  define AK_CA_LOCK_INIT(root)    ak_spinlock_init(ak_as_ptr((root)->LOCKED))
#  define AK_CA_LOCK_ACQUIRE(root) ak_spinlock_acquire(ak_as_ptr((root)->LOCKED))
#  define AK_CA_LOCK_RELEASE(root) ak_spinlock_release(ak_as_ptr((root)->LOCKED))
#else
#  define AK_CA_LOCK_DEFINE(nm)
#  define AK_CA_LOCK_INIT(root)
#  define AK_CA_LOCK_ACQUIRE(root)
#  define AK_CA_LOCK_RELEASE(root)
#endif

typedef ak_sz ak_alloc_info;

typedef struct ak_alloc_node_tag ak_alloc_node;

typedef struct ak_free_list_node_tag ak_free_list_node;

typedef struct ak_ca_segment_tag ak_ca_segment;

typedef struct ak_ca_root_tag ak_ca_root;

struct ak_alloc_node_tag
{
#if AKMALLOC_BITNESS == 32
    ak_alloc_info _unused0;
    ak_alloc_info _unused1;
#endif
    ak_alloc_info previnfo;
    ak_alloc_info currinfo;
};

struct ak_free_list_node_tag
{
    ak_free_list_node* bk;
    ak_free_list_node* fd;
};

struct ak_ca_segment_tag
{
    ak_ca_segment* bk;
    ak_ca_segment* fd;
    ak_sz sz;
    ak_alloc_node* head;
};

struct ak_ca_root_tag
{
    ak_ca_segment main_root;
    ak_ca_segment empty_root;

    ak_free_list_node free_root;

    ak_u32 nempty;
    ak_u32 release;

    ak_u32 RELEASE_RATE;
    ak_u32 MAX_SEGMENTS_TO_FREE;
    ak_sz MIN_SIZE_TO_SPLIT;

    AK_CA_LOCK_DEFINE(LOCKED);
};

/**************************************************************/
/* P R I V A T E                                              */
/**************************************************************/

#define ak_ca_to_sz(p) (((ak_sz)(p)) & ~(AK_COALESCE_ALIGN - 1))

#define ak_ca_is_first(p) (((ak_sz)(p)) & (AK_SZ_ONE << 0))

#define ak_ca_is_last(p) (((ak_sz)(p)) & (AK_SZ_ONE << 1))

#define ak_ca_is_free(p) (((ak_sz)(p)) & (AK_SZ_ONE << 2))

ak_inline static void ak_ca_set_sz(ak_alloc_info* p, ak_sz sz)
{
    AKMALLOC_ASSERT(sz == ak_ca_to_sz((ak_alloc_info)sz));
    // 7 because there are only 3 useful bits. the fourth bit may collect garbage.
    *p = (ak_alloc_info)((((ak_sz)*p)  &  ((ak_sz)7)) |
                                 (sz   & ~(AK_COALESCE_ALIGN - 1)));
}

ak_inline static void ak_ca_set_is_first(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 0)) | (v ? (AK_SZ_ONE << 0) : 0));
}

ak_inline static void ak_ca_set_is_last(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 1)) | (v ? (AK_SZ_ONE << 1) : 0));
}

ak_inline static void ak_ca_set_is_free(ak_alloc_info* p, int v)
{
    *p = (ak_alloc_info)((((ak_sz)*p) & ~(AK_SZ_ONE << 2)) | (v ? (AK_SZ_ONE << 2) : 0));
}

ak_inline static ak_alloc_node* ak_ca_next_node(ak_alloc_node* node)
{
    return ak_ca_is_last(node->currinfo)
                ? AK_NULLPTR
                : (ak_alloc_node*)((char*)(node + 1) + ak_ca_to_sz(node->currinfo));
}

ak_inline static ak_alloc_node* ak_ca_prev_node(ak_alloc_node* node)
{
    return ak_ca_is_first(node->currinfo)
                ? AK_NULLPTR
                : (ak_alloc_node*)((char*)(node - 1) - ak_ca_to_sz(node->previnfo));
}

ak_inline static void ak_ca_update_footer(ak_alloc_node* p)
{
    ak_alloc_node* n = ak_ca_next_node(p);
    if (n) {
        n->previnfo = p->currinfo;
    }
}

#define ak_free_list_node_unlink(node)               \
  do {                                               \
    ak_free_list_node* const sU = (node);            \
    sU->bk->fd = (sU->fd);                           \
    sU->fd->bk = (sU->bk);                           \
    sU->fd = sU->bk = AK_NULLPTR;                    \
  } while (0)

#define ak_free_list_node_link_fd(node, fwd)         \
  do {                                               \
    ak_free_list_node* const sLF = (node);           \
    ak_free_list_node* const fLF = (fwd);            \
    sLF->fd = fLF;                                   \
    fLF->bk = sLF;                                   \
  } while (0)

#define ak_free_list_node_link_bk(node, back)        \
  do {                                               \
    ak_free_list_node* const sLB = (node);           \
    ak_free_list_node* const bLB = (back);           \
    sLB->bk = bLB;                                   \
    bLB->fd = sLB;                                   \
  } while (0)

#define ak_free_list_node_link(node, fwd, back)      \
  do {                                               \
    ak_free_list_node* const sL = (node);            \
    ak_free_list_node* const fL = (fwd);             \
    ak_free_list_node* const bL = (back);            \
    ak_free_list_node_link_bk(sL, bL);               \
    ak_free_list_node_link_fd(sL, fL);               \
  } while (0)

#define ak_ca_segment_unlink(node)                   \
  do {                                               \
    ak_ca_segment* const sU = (node);                \
    sU->bk->fd = (sU->fd);                           \
    sU->fd->bk = (sU->bk);                           \
    sU->fd = sU->bk = AK_NULLPTR;                    \
  } while (0)

#define ak_ca_segment_link_fd(node, fwd)             \
  do {                                               \
    ak_ca_segment* const sLF = (node);               \
    ak_ca_segment* const fLF = (fwd);                \
    sLF->fd = fLF;                                   \
    fLF->bk = sLF;                                   \
  } while (0)

#define ak_ca_segment_link_bk(node, back)            \
  do {                                               \
    ak_ca_segment* const sLB = (node);               \
    ak_ca_segment* const bLB = (back);               \
    sLB->bk = bLB;                                   \
    bLB->fd = sLB;                                   \
  } while (0)

#define ak_ca_segment_link(node, fwd, back)          \
  do {                                               \
    ak_ca_segment* const sL = (node);                \
    ak_ca_segment* const fL = (fwd);                 \
    ak_ca_segment* const bL = (back);                \
    ak_ca_segment_link_bk(sL, bL);                   \
    ak_ca_segment_link_fd(sL, fL);                   \
  } while (0)

#define ak_circ_list_for_each(type, name, list)      \
    type* name = (list)->fd;                         \
    for(type* const iterroot = (list); name != iterroot; name = name->fd)

#define ak_ca_aligned_size(x) ((x) ? (((x) + AK_COALESCE_ALIGN - 1) & ~(AK_COALESCE_ALIGN - 1)) : AK_COALESCE_ALIGN)

#define ak_ca_aligned_segment_size(x) (((x) + (AK_COALESCE_SEGMENT_SIZE) - 1) & ~((AK_COALESCE_SEGMENT_SIZE) - 1))

static void* ak_ca_search_free_list(ak_free_list_node* root, ak_sz sz, ak_sz splitsz)
{
    AKMALLOC_ASSERT(splitsz >= sizeof(ak_free_list_node));
    AKMALLOC_ASSERT(splitsz % AK_COALESCE_ALIGN == 0);

    // add the overhead per node
    splitsz += sizeof(ak_alloc_node);

    // walk through list finding the first element that fits and split if required
    ak_circ_list_for_each(ak_free_list_node, node, root) {
        ak_alloc_node* n = ((ak_alloc_node*)(node)) - 1;
        AKMALLOC_ASSERT(ak_ca_is_free(n->currinfo));
        ak_sz nodesz = ak_ca_to_sz(n->currinfo);
        if (nodesz >= sz) {
            if ((nodesz - sz) > splitsz) {
                // split and assign
                ak_alloc_node* newnode = (ak_alloc_node*)(((char*)node) + sz);
                int islast = ak_ca_is_last(n->currinfo);

                ak_ca_set_sz(ak_as_ptr(n->currinfo), sz);
                ak_ca_set_is_last(ak_as_ptr(n->currinfo), 0);
                ak_ca_set_is_free(ak_as_ptr(n->currinfo), 0);
                ak_ca_update_footer(n);

                ak_ca_set_sz(ak_as_ptr(newnode->currinfo), nodesz - sz - sizeof(ak_alloc_node));
                ak_ca_set_is_first(ak_as_ptr(newnode->currinfo), 0);
                ak_ca_set_is_last(ak_as_ptr(newnode->currinfo), islast);
                ak_ca_set_is_free(ak_as_ptr(newnode->currinfo), 1);
                ak_ca_update_footer(newnode);
                
                // copy free list node from node
                ak_free_list_node* fl = (ak_free_list_node*)(newnode + 1);
                ak_free_list_node_link(fl, node->fd, node->bk);
                AKMALLOC_ASSERT(n->currinfo == newnode->previnfo);
            } else {
                // return as is
                ak_ca_set_is_free(ak_as_ptr(n->currinfo), 0);
                ak_ca_update_footer(n);
                ak_free_list_node_unlink(node);
            }
            return node;
        }
    }
    return AK_NULLPTR;
}

static int ak_ca_add_new_segment(ak_ca_root* root, char* mem, ak_sz sz)
{
    if (ak_likely(mem)) {
        // make segment
        ak_ca_segment* seg = (ak_ca_segment*)(mem + sz - sizeof(ak_ca_segment));
        ak_ca_segment_link(seg, root->main_root.fd, ak_as_ptr(root->main_root));
        seg->sz = sz;
        seg->head = (ak_alloc_node*)mem;
        {// add to free list
            ak_alloc_node* hd = seg->head;
            ak_sz actualsize = (sz - sizeof(ak_alloc_node) - sizeof(ak_ca_segment));
            // store actual size in previnfo
            hd->previnfo = actualsize;
            ak_ca_set_is_first(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_is_last(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_is_free(ak_as_ptr(hd->currinfo), 1);
            ak_ca_set_sz(ak_as_ptr(hd->currinfo), actualsize);
            ak_free_list_node* fl = (ak_free_list_node*)(hd + 1);
            ak_free_list_node_link(fl, root->free_root.fd, ak_as_ptr(root->free_root));
        }
        return 1;
    }
    return 0;
}

static int ak_ca_get_new_segment(ak_ca_root* root, ak_sz sz)
{
    // align to segment size multiple
    sz += sizeof(ak_ca_segment) + sizeof(ak_alloc_node) + sizeof(ak_free_list_node);
    sz = ak_ca_aligned_segment_size(sz);

    // search empty_root for a segment that is as big or more
    char* mem = AK_NULLPTR;
    ak_sz segsz = sz;
    ak_circ_list_for_each(ak_ca_segment, seg, ak_as_ptr(root->empty_root)) {
        if (seg->sz >= sz) {
            mem = (char*)(seg->head);
            segsz = seg->sz;
            ak_ca_segment_unlink(seg);
            --(root->nempty);
            break;
        }
    }

    return ak_ca_add_new_segment(root, mem ? mem : ((char*)ak_os_alloc(sz)), segsz);
}

static ak_u32 ak_ca_return_os_mem(ak_ca_segment* r, ak_u32 num)
{
    ak_u32 ct = 0;
    ak_ca_segment* next = r->fd;
    ak_ca_segment* curr = next;
    for(; curr != r; curr = next) {
        if (ct >= num) {
            break;
        }
        next = curr->fd;
        ak_ca_segment_unlink(curr);
        ak_os_free(curr->head, curr->sz);
        ++ct;
    }
    return ct;
}

/**************************************************************/
/* P U B L I C                                                */
/**************************************************************/

static void ak_ca_init_root(ak_ca_root* root, ak_u32 relrate, ak_u32 maxsegstofree)
{
    AKMALLOC_ASSERT_ALWAYS(AK_COALESCE_SEGMENT_SIZE % AK_COALESCE_SEGMENT_GRANULARITY == 0);
    AKMALLOC_ASSERT_ALWAYS(((AK_COALESCE_SEGMENT_SIZE & (AK_COALESCE_SEGMENT_SIZE - 1)) == 0) && "Segment size must be a power of 2");

    ak_ca_segment_link(&(root->main_root), &(root->main_root), &(root->main_root));
    ak_ca_segment_link(&(root->empty_root), &(root->empty_root), &(root->empty_root));
    ak_free_list_node_link(&(root->free_root), &(root->free_root), &(root->free_root));
    root->nempty = root->release = 0;

    root->RELEASE_RATE = relrate;
    root->MAX_SEGMENTS_TO_FREE = maxsegstofree;
    root->MIN_SIZE_TO_SPLIT = sizeof(ak_free_list_node);
    AK_CA_LOCK_INIT(root);
}

ak_inline static void ak_ca_init_root_default(ak_ca_root* root)
{
#if AKMALLOC_BITNESS == 32
    static const ak_u32 rate =  255;
#else
    static const ak_u32 rate = 2047;
#endif
    ak_ca_init_root(root, rate, rate);
}

static void* ak_ca_alloc(ak_ca_root* root, ak_sz s)
{
{'fraction_non_alphanumeric': 0.12597323382727565, 'fraction_numerical': 0.007929388970614617, 'mean_word_length': 2.294562647754137, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 184, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 60, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3811438', 'n_tokens_mistral': 10249, 'n_tokens_neox': 9732, 'n_words': 2063}