test.c

#include <stdint.h>
#include <stdio.h>

int first_zero(uint64_t v)
{
    if (v == 0xffffffffffffffffl) return -1;

    int bits = 64;
    uint8_t h;

    do {
        bits -= 8;
        h = (uint8_t)(v >> bits);
    } while (h == 255);

    static uint8_t lookup[255] = {
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
        1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
        1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
        2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
        3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,6,6,7
    };	

    return 56 - bits + lookup[h];
}

uint64_t set(uint64_t *v, int bit, int value)
{
    static uint64_t clear[64] = {
        0x7fffffffffffffff,0xbfffffffffffffff,0xdfffffffffffffff,0xefffffffffffffff,
        0xf7ffffffffffffff,0xfbffffffffffffff,0xfdffffffffffffff,0xfeffffffffffffff,
        0xff7fffffffffffff,0xffbfffffffffffff,0xffdfffffffffffff,0xffefffffffffffff,
        0xfff7ffffffffffff,0xfffbffffffffffff,0xfffdffffffffffff,0xfffeffffffffffff,
        0xffff7fffffffffff,0xffffbfffffffffff,0xffffdfffffffffff,0xffffefffffffffff,
        0xfffff7ffffffffff,0xfffffbffffffffff,0xfffffdffffffffff,0xfffffeffffffffff,
        0xffffff7fffffffff,0xffffffbfffffffff,0xffffffdfffffffff,0xffffffefffffffff,
        0xfffffff7ffffffff,0xfffffffbffffffff,0xfffffffdffffffff,0xfffffffeffffffff,
        0xffffffff7fffffff,0xffffffffbfffffff,0xffffffffdfffffff,0xffffffffefffffff,
        0xfffffffff7ffffff,0xfffffffffbffffff,0xfffffffffdffffff,0xfffffffffeffffff,
        0xffffffffff7fffff,0xffffffffffbfffff,0xffffffffffdfffff,0xffffffffffefffff,
        0xfffffffffff7ffff,0xfffffffffffbffff,0xfffffffffffdffff,0xfffffffffffeffff,
        0xffffffffffff7fff,0xffffffffffffbfff,0xffffffffffffdfff,0xffffffffffffefff,
        0xfffffffffffff7ff,0xfffffffffffffbff,0xfffffffffffffdff,0xfffffffffffffeff,
        0xffffffffffffff7f,0xffffffffffffffbf,0xffffffffffffffdf,0xffffffffffffffef,
        0xfffffffffffffff7,0xfffffffffffffffb,0xfffffffffffffffd,0xfffffffffffffffe,
    };

    *v &= clear[bit];
    if (value == 1) *v |= ~clear[bit];
    return *v;
}

typedef struct block {
    uint64_t occupy;
    struct block *parent;
    uint8_t child_index;
    uint8_t children_count;
    uint8_t *mem;
} block;

typedef struct {
    block *blk;
} pool;

block *new_block()
{
    block *blk = (block *)malloc(sizeof(block));
    blk->occupy = 0;
    blk->parent = 0;
    blk->children_count = 0;
    blk->mem = (uint8_t *)malloc(12 * 64);
    return blk;
}

pool *new_pool()
{
    pool *p = (pool *)malloc(sizeof(pool));
    p->blk = new_block();
    return p;
}

void *pool_malloc(pool *p)
{
    block *blk = p->blk;
    if (blk->occupy != 0xffffffffffffffffl) {
        while (1) {
            int idx = first_zero(blk->occupy);
            if (blk->children_count == 0) {
                void *ptr = blk->mem + idx * 12;
                
                if (set(&blk->occupy, idx, 1) == 0xffffffffffffffffl) {
                    while (blk->parent) {
                        set(&blk->parent->occupy, blk->child_index, 1);
                        blk = blk->parent;
                    }
                }

                return ptr;
            }
            blk = (block *)(blk->mem + idx * 12);
        }

    } else {
        if (blk->children_count == 64) {

        } else {
            block *new_blk = new_block();
            *(block **)(blk->mem + blk->children_count * 12) = new_blk;
            blk->children_count++;
            blk = new_blk;
        }
    }
}

int main() 
{
    pool *p = new_pool();

    uint64_t v = 0b1111111111111111110111111111111111111111111111111111111111111111;
    printf("%d %lx\n", first_zero(v), v);
    printf("%lx\n", set(&v, 18, 1));
    return 0;
}