allocator.d

// Memory management tool

import mach.sys.memory : malloc, realloc, memfree;

struct Allocator(T, size_t PageSize = 512){
    struct Page{
        enum size = PageSize;
        
        T[size] objects;
        size_t[size] references;
        size_t filled = 0;
        size_t cursor = 0;
        Page* prevPage = null;
        Page* nextPage = null;
        
        @property bool empty() const{
            return this.filled == 0;
        }
        @property bool full() const{
            return this.filled >= this.size;
        }
        @property size_t unfilled() const{
            return this.size - this.filled;
        }
        
        @property const(T)* pageBegin() const{
            return this.objects.ptr;
        }
        @property const(T)* pageEnd() const{
            return this.objects.ptr + this.size;
        }
        
        bool contains(in T* object) const{
            assert(object);
            return object >= this.pageBegin && object < this.pageEnd;
        }
        
        size_t indexOf(in T* object) const{
            assert(object);
            assert(object >= this.pageBegin && object < this.pageEnd);
            size_t index = cast(size_t) (object - this.pageBegin);
            return index;
        }
        
        // Indicate that one more place has access to this object.
        void share(in T* object){
            this.references[this.indexOf(object)]++;
        }
        
        // Indicate that one fewer place has access to this object.
        size_t release(in T* object){
            assert(object);
            assert(object >= this.pageBegin && object < this.pageEnd);
            size_t index = cast(size_t) (object - this.pageBegin);
            assert(this.references[index] > 0);
            this.references[index]--;
            if(this.references[index] == 0){
                this.filled--;
            }
            return this.references[index];
        }
        
        // Aquire an unused object reference.
        T* acquire(){
            if(this.filled >= this.size){
                return null;
            }
            version(assert){
                size_t initialCursor = this.cursor;
            }
            while(true){
                if(this.references[this.cursor] == 0){
                    this.references[this.cursor] = 1;
                    size_t allocCursor = this.cursor;
                    this.filled++;
                    this.cursor++;
                    if(this.cursor >= size){
                        this.cursor = 0;
                    }
                    return &(this.objects[allocCursor]);
                }
                this.cursor++;
                if(this.cursor >= size){
                    this.cursor = 0;
                }
                version(assert){
                    assert(this.cursor != initialCursor, "No room to allocate.");
                }
            }
        }
        
        Page* insertPage(){
            Page* newPage = malloc!Page();
            newPage.prevPage = &this;
            newPage.nextPage = this.nextPage;
            this.nextPage.prevPage = newPage;
            this.nextPage = newPage;
            return newPage;
        }
        
        void orphan(){
            this.prevPage.nextPage = this.nextPage;
            this.nextPage.prevPage = this.prevPage;
        }
    }
    
    Page* cursor = null;
    size_t totalPages = 0;
    size_t emptyPages = 0;
    size_t bufferPages = 0;
    
    enum pagePaddingBytes = Page.sizeof - (T.sizeof * PageSize);
    
    this(size_t pageCount){
        this.addInitialPages(pageCount);
    }
    
    void addInitialPages(in size_t pageCount){
        this.cursor = malloc!Page();
        this.cursor.prevPage = this.cursor;
        this.cursor.nextPage = this.cursor;
        for(size_t i = 1; i < pageCount; i++){
            this.cursor.insertPage();
        }
        this.totalPages = pageCount;
        this.emptyPages = pageCount;
        this.bufferPages = pageCount;
    }
    
    Page* addPage(){
        this.totalPages++;
        this.emptyPages++;
        return this.cursor.insertPage();
    }
    
    @property size_t pageCount() const{
        if(!this.cursor){
            return 0;
        }
        const(Page)* page = this.cursor;
        size_t count = 0;
        while(true){
            count++;
            page = page.nextPage;
            if(page == this.cursor){
                break;
            }
        }
        return count;
    }
    
    Page* getPageOf(in T* object){
        assert(object);
        assert(this.cursor);
        Page* page = this.cursor;
        while(true){
            if(page.contains(object)){
                return page;
            }
            page = page.nextPage;
            version(assert){
                if(page == this.cursor){
                    assert(false, "Object not in pool.");
                }
            }
        }
    }
    const(Page)* getPageOf(in T* object){
        assert(object);
        assert(this.cursor);
        const(Page)* page = this.cursor;
        while(true){
            if(page.contains(object)){
                return page;
            }
            page = page.nextPage;
            version(assert){
                if(page == this.cursor){
                    assert(false, "Object not in pool.");
                }
            }
        }
    }
    
    void share(in T* object){
        return this.getPageOf(object).share(object);
    }
    
    void release(in T* object){
        Page* page = this.getPageOf(object);
        size_t released = page.release(object);
        if(released == 0){
            if(page.empty){
                if(
                    this.emptyPages >= this.bufferPages &&
                    this.totalPages > this.bufferPages
                ){
                    if(this.cursor == page){
                        this.cursor = page.nextPage;
                    }
                    page.orphan();
                    memfree(page);
                }else{
                    this.emptyPages++;
                }
            }
        }
    }
    
    T* acquire(){
        assert(this.cursor);
        Page* page = this.cursor;
        while(true){
            if(!page.full){
                this.emptyPages -= page.empty;
                return page.acquire();
            }
            page = page.nextPage;
            if(page == this.cursor){
                break;
            }
        }
        Page* newPage = this.addPage();
        this.emptyPages--;
        return newPage.acquire();
    }
}

/* Test

import std.stdio;

void main(){
    Allocator!ulong allocator;
    allocator.addInitialPages(2);
    ulong*[2000] ints;
    stdio.writeln(__LINE__, " .. Pages: ", allocator.pageCount);
    for(size_t i = 0; i < 200; i++){
        ints[i] = allocator.acquire();
        *ints[i] = i * 1;
    }
    stdio.writeln(__LINE__, " .. Pages: ", allocator.pageCount);
    for(size_t i = 100; i < 200; i++){
        allocator.release(ints[i]);
        ints[i] = allocator.acquire();
        *ints[i] = i * 2;
    }
    stdio.writeln(__LINE__, " .. Pages: ", allocator.pageCount);
    for(size_t i = 200; i < 2000; i++){
        ints[i] = allocator.acquire();
        *ints[i] = i * 3;
    }
    stdio.writeln(__LINE__, " .. Pages: ", allocator.pageCount);
    for(size_t i = 500; i < 1000; i++){
        allocator.release(ints[i]);
        ints[i] = allocator.acquire();
        *ints[i] = i * 4;
    }
    stdio.writeln(__LINE__, " .. Pages: ", allocator.pageCount);
    for(size_t i = 0; i < 2000; i++){
        size_t m = 1;
        if(i >= 100) m = 2;
        if(i >= 200) m = 3;
        if(i >= 500 && i < 1000) m = 4;
        assert(*ints[i] == i * m);
    }
    stdio.writeln(__LINE__, " .. Pages: ", allocator.pageCount);
    stdio.writeln(__LINE__, " .. Empty? ", allocator.emptyPages);
    for(size_t i = 0; i < 2000; i++){
        allocator.release(ints[i]);
    }
    stdio.writeln(__LINE__, " .. Pages: ", allocator.pageCount);
    stdio.writeln(__LINE__, " .. Empty? ", allocator.emptyPages);
}
*/