import io.mapping.*;
import io.paths.*;
import paged.misc.*;



//
// paged allocator global state
//

alias nullBlock = Greatest(SizeT);
nullBlock?(b) = (b == nullBlock);

alias BucketCount = Int(TypeSize(SizeT) * 8);
alias BucketArray = Array[SizeT, BucketCount];

record State (
    fileName : String,
    file : File,
    mapping : FileMapping,
    freeListBuckets : Pointer[BucketArray],
    dataBegin : Pointer[Byte],
    dataEnd : Pointer[Byte],
);

var state = State();

dataBegin() = state.dataBegin;
dataEnd() = state.dataEnd;



//
// Header (block header)
//

record Header (
    sizeAndFlag : SizeT,
    previous : SizeT,
    nextInBucket : SizeT,
    previousInBucket : SizeT,
);

private hptr(b:SizeT) = Pointer[Header](dataBegin() + b);

blockSize(b) = bitand(hptr(b)^.sizeAndFlag, bitnot(1));

blockFree?(b) = (bitand(hptr(b)^.sizeAndFlag, 1) != 0);

blockNext(b) = b + blockSize(b);

blockPrevious(b) = hptr(b)^.previous;

blockNextInBucket(b) = hptr(b)^.nextInBucket;

blockPreviousInBucket(b) = hptr(b)^.previousInBucket;

blockSetSize(b, size) {
    hptr(b)^.sizeAndFlag = bitor(SizeT(size), SizeT(blockFree?(b)));
}

blockSetFree(b, free?) {
    hptr(b)^.sizeAndFlag = bitor(blockSize(b), SizeT(free?));
}

blockSetPrevious(b, previous) {
    assert(nullBlock?(previous) or (previous <= b), "blockSetPrevious");
    hptr(b)^.previous = previous;
}

blockSetNextInBucket(b, next) {
    hptr(b)^.nextInBucket = next;
}

blockSetPreviousInBucket(b, previous) {
    hptr(b)^.previousInBucket = previous;
}

blockInit(b, size, previous, nextInBucket, previousInBucket) {
    blockSetSize(b, size);
    blockSetFree(b, true);
    blockSetPrevious(b, previous);
    blockSetNextInBucket(b, nextInBucket);
    blockSetPreviousInBucket(b, previousInBucket);
}



//
// free list
//

bucketId(size) = floorLog2(size);

bucketHead(blockSize) {
    var i = bucketId(blockSize);
    return ref state.freeListBuckets^[i];
}

pushBucket(head, b) {
    blockSetFree(b, true);
    if (not nullBlock?(head))
        blockSetPreviousInBucket(head, b);
    assert(nullBlock?(blockPreviousInBucket(b)), "pushFreeList");
    blockSetNextInBucket(b, head);
    head = b;
}

pushFreeList(b) {
    ref head = bucketHead(blockSize(b));
    pushBucket(head, b);
}

popBucket(head) {
    var b = head;
    var newHead = blockNextInBucket(head);
    if (not nullBlock?(newHead))
        blockSetPreviousInBucket(newHead, nullBlock);
    blockSetNextInBucket(b, nullBlock);
    assert(nullBlock?(blockPreviousInBucket(b)), "popBucket");
    blockSetFree(b, false);
    head = newHead;
    return b;
}

popFreeList(minSize) {
    var i = bucketId(higherPower2(minSize));
    while (i < size(state.freeListBuckets^)) {
        ref head = state.freeListBuckets^[i];
        if (not nullBlock?(head))
            return popBucket(head);
        i += 1;
    }
    return nullBlock;
}

removeFromFreeList(b) {
    var next = blockNextInBucket(b);
    var prev = blockPreviousInBucket(b);
    if (nullBlock?(prev))
        bucketHead(blockSize(b)) = next;
    else
        blockSetNextInBucket(prev, next);
    if (not nullBlock?(next))
        blockSetPreviousInBucket(next, prev);
    blockSetNextInBucket(b, nullBlock);
    blockSetPreviousInBucket(b, nullBlock);
    blockSetFree(b, false);
}



//
// initializePaging
//

resetState() {
    destroy(state);
    state <-- State();
}

initNewFile() {
    ref x = state;
    for (head in x.freeListBuckets^)
        head = nullBlock;

    var b = SizeT(0);
    var blockSize = x.dataEnd - x.dataBegin;
    blockInit(b, blockSize, nullBlock, nullBlock, nullBlock);
    pushFreeList(b);
}

initializePaging(fileName, fileSize) {
    resetState();
    var newFile? = not pathExists?(fileName);
    var fileMode = READ_WRITE;
    if (newFile?)
        fileMode = CREATE;

    ref x = state;
    x.fileName = String(fileName);
    x.file = File(fileName, fileMode);
    if (newFile?)
        resizeFile(x.file, SizeT(fileSize));
    x.mapping = FileMapping(x.file, MAP_READ_WRITE);
    x.dataBegin = mappingAddress(x.mapping) + TypeSize(BucketArray);
    x.dataEnd = mappingAddress(x.mapping) + mappingLength(x.mapping);
    x.freeListBuckets = Pointer[BucketArray](mappingAddress(x.mapping));

    if (newFile?)
        initNewFile();
}



//
// PagedPointer
//

record PagedPointer[T] (
    offset : SizeT
);

[T]
overload ContiguousCoordinate?(static PagedPointer[T]) = true;

[T]
overload PagedPointer[T]() = PagedPointer[T](SizeT(0));

[T,I | Integer?(I)]
overload add(p:PagedPointer[T], i:I) = PagedPointer[T](p.offset + i*TypeSize(T));

[T,I | Integer?(I)]
overload subtract(p:PagedPointer[T], i:I) = PagedPointer[T](p.offset - i*TypeSize(T));

[T]
overload subtract(a:PagedPointer[T], b:PagedPointer[T]) {
    return (PtrInt(a.offset) - PtrInt(b.offset)) / PtrInt(TypeSize(T));
}

[T]
overload inc(p:PagedPointer[T]) {
    p += 1;
}

[T]
overload dec(p:PagedPointer[T]) {
    p -= 1;
}

[T]
overload dereference(p : PagedPointer[T]) {
    return ref Pointer[T](p.offset + dataBegin())^;
}

[T]
overload null?(p : PagedPointer[T]) = (p.offset == 0);

[T]
nullPaged(static T) = PagedPointer[T]();



//
// allocatePaged
//

splitBlock?(b, n) {
    assert(blockSize(b) >= n, "splitBlock?");
    var remaining = blockSize(b) - n;
    return remaining > (TypeSize(Header) + 16);
}

[T,I | Integer?(I)]
allocatePaged(static T, n_:I) {
    var n = SizeT(n_) * TypeSize(T);

    // include header in size and align up to 16
    n += TypeSize(Header);
    n = alignUp(n, 16u);

    var b = popFreeList(n);
    if (nullBlock?(b)) {
        errorNoThrow("out of paged memory: allocatePaged(", T, ", ", n_, ")");
        return nullPaged(T);
    }
    if (splitBlock?(b,n)) {
        if (not lastBlock?(b))
            blockSetPrevious(blockNext(b), b+n);
        blockInit(b+n, blockSize(b)-n, b, nullBlock, nullBlock);
        blockSetSize(b, n);
        pushFreeList(b+n);
    }
    assert(not blockFree?(b), "allocatePaged");
    return PagedPointer[T](b + TypeSize(Header));
}



//
// freePaged
//

firstBlock?(b) = (b == 0);
lastBlock?(b) = (blockNext(b) == dataEnd() - dataBegin());

mergePrevious?(b) = (not firstBlock?(b)) and blockFree?(blockPrevious(b));
mergeNext?(b) = (not lastBlock?(b)) and blockFree?(blockNext(b));

mergePrevious(b) {
    var prev = blockPrevious(b);
    removeFromFreeList(prev);
    if (not lastBlock?(b))
        blockSetPrevious(blockNext(b), prev);
    blockSetSize(prev, blockSize(prev) + blockSize(b));
    return prev;
}

mergeNext(b) {
    var next = blockNext(b);
    removeFromFreeList(next);
    if (not lastBlock?(next))
        blockSetPrevious(blockNext(next), b);
    blockSetSize(b, blockSize(b) + blockSize(next));
    return b;
}

[T]
freePaged(p:PagedPointer[T]) {
    if (null?(p)) return;
    var b = p.offset - TypeSize(Header);
    assert(not blockFree?(b), "freePaged");
    if (mergePrevious?(b))
        b = mergePrevious(b);
    if (mergeNext?(b))
        b = mergeNext(b);
    pushFreeList(b);
}



//
// display state
//

printPagingState() {
    ref x = state;
    println("fileName = ", x.fileName);
    for (i in range(size(x.freeListBuckets^)))
        printBucket(bitshl(SizeT(1), i));
}

printBucket(i) {
    print("bucket ", i, ": ");
    var b = bucketHead(i);
    while (not nullBlock?(b)) {
        printBlock(b);
        print(", ");
        b = blockNextInBucket(b);
    }
    println();
}

printBlock(b) {
    print("(offset=", b,
          ",size=", blockSize(b),
          ",free?=", blockFree?(b),
          ",prev=", blockPrevious(b),
          ",next=", blockNext(b),
          ")");
}
