Same-Size Allocator

//header:
#ifndef __KER__SSA_H__
#define __KER__SSA_H__

#include "defs.h"
#include "inc/types.h"

typedef struct _ssapage ssapg_s;
typedef struct _ssallocator ssa_s;

struct _ssapage
{
    ssapg_s * next, * prev;
    void * free;
    word used;
    char data[0]; // reserved[first - 4 * 4], blocks[bpp][size];
};

struct _ssallocator
{
    ssapg_s * other, * empty; // <other> serves also as lock
    word size, bpp; // block size (in bytes), blocks per page
};

#define ssa_locked(a)       ({ ssa_s * __a = (a); assert(__a); ptrlock_locked(& __a ->other); })
#define ssa_lock(a)         ({ ssa_s * __a = (a); assert(__a); ptrlock_lock(& __a ->other); })
#define ssa_trylock(a)      ({ ssa_s * __a = (a); assert(__a); ptrlock_trylock(& __a ->other); })
#define ssa_unlock(a)       ({ ssa_s * __a = (a); assert(__a); ptrlock_unlock(& __a ->other); })

// allocate block
extern void * ssa_alloc(ssa_s * a);

// release block
extern void ssa_free(ssa_s * a, void * b);

extern ssa_s ssa16w;
#define alloc16w()          ssa_alloc(& ssa16w)
#define free16w(b)          ssa_free(& ssa16w, b)

extern ssa_s ssa3w;
#define alloc3w()           ssa_alloc(& ssa3w)
#define free3w(b)           ssa_free(& ssa3w, b)

#endif

//source:
#include "out.h"
#include "ssa.h"
#include "page.h"
#include "inc/sl.h"

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// same-size-allocators
ssa_s ssa16w = {
    other:  nil,
    empty:  nil,
    size:   16 * sizeof(word),
    bpp:    (BYTES_PER_PAGE - sizeof(ssapg_s)) / (16 * sizeof(word))
};
ssa_s ssa3w = {
    other:  nil,
    empty:  nil,
    size:   3 * sizeof(word),
    bpp:    (BYTES_PER_PAGE - sizeof(ssapg_s)) / (3 * sizeof(word))
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// allocate block
void * ssa_alloc(ssa_s * a)
{
    ssapg_s * pg;

    ssa_lock(a);
    if ((pg = a ->other))
    {// we have some non-full-non-empty page

        void * b, * next;

        assert(pg ->prev == (ssapg_s *) & a ->other && pg ->used > 0 && pg ->used < a ->bpp);

    //  use the empty slot
        pg ->free = next = * (void **) (b = pg ->free);
        ++ pg ->used;

        if (! next)
        {// the page was used up

            ssapg_s * next;

            assert(pg ->used == a ->bpp);

        //  remove it from the list
            a ->other = next = pg ->next;
            if (next) next ->prev = (ssapg_s *) & a ->other;
        }

        ssa_unlock(a);
        return b;
    }
    else if ((pg = a ->empty))
    {// we have an empty page

        void * b;
        ssapg_s * next;

        assert(pg ->used == 0 && pg ->free);

    //  use the empty slot
        pg ->free = * (void **) (b = pg ->free);
        pg ->used = 1;

    //  move the page from the list of empty pages ...
        a ->empty = pg ->next;

    //  ... to the list of non-full-non-empty pages
        if ((next = a ->other)) next ->prev = pg;
        a ->other = pg;
        pg ->next = next;
        pg ->prev = (ssapg_s *) & a ->other;

        ssa_unlock(a);
        return b;
    }
    else
    {// allocate and use new page

        char * b, * stop, * next;
        unsigned size;

    //  allocate new page
        if (! (pg = pgalloc()))
            goto error;

    //  add the page to the list of non-full-non-empty pages
        assert(! a ->other);
        a ->other = pg;
        pg ->next = nil;
        pg ->prev = (ssapg_s *) & a ->other;

    //  format the page
        pg ->used = 1;
        stop = ((char *) (pg + 1)) + (size = a ->size);
        b = ((char *) pg) + BYTES_PER_PAGE;
        next = nil;
        for (;;)
        {
            b -= size;
            if (b < stop)
                break;
            * (void **) b = next;
            next = b;
        }
        pg ->free = next;

        ssa_unlock(a);
        return b;
    }

    assert(0);

error:
    assert2(0, (
        outs("desc: could not allocate block"),
        outs("\nallocator:       "), outp(a),
        outs("\nblock size:      "), outi(a ->size), outs(" bytes ("), outi(a ->size / 4), outs(" words)"),
        outs("\nblocks per page: "), outi(a ->bpp),
        outnl()
    ));
    ssa_unlock(a);
    return nil;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// release block
void ssa_free(ssa_s * a, void * b)
{
    ssapg_s * pg = page_from_pointer(b);

    ssa_lock(a);
    if (pg ->free)
    {// the page is not full

        assert(pg ->used > 0 && pg ->used < a ->bpp);

        * (void **) b = pg ->free;
        pg ->free = b;

        if (! -- pg ->used)
        {// the page is now empty

            ssapg_s * next, * prev;

        //  move it from the list of non-full-non-empty pages ...
            (prev = pg ->prev) ->next = next = pg ->next;
            if (next) next ->prev = prev;

        //  ... to the list of empty pages
            pg ->next = a ->empty;
            a ->empty = pg;
        }
    }
    else
    {// the page is now full

        ssapg_s * next;

        assert(pg ->used == a ->bpp);

        -- pg ->used;
        * (void **) b = nil;
        pg ->free = b;

    // add it to the list of non-full-non-empty pages
        pg ->next = next = a ->other;
        pg ->prev = (ssapg_s *) a ->other;
        a ->other = pg;
        if (next) next ->prev = pg;
    }
    ssa_unlock(a);
}