/*
 * Copyright 2008, Axel Dörfler, axeld@pinc-software.de.
 * This file may be used under the terms of the MIT License.
 */


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


int32_t fLargestStart = -1;
int32_t fLargestLength = -1;
bool fLargestValid = false;
int32_t fNumBits = 100;


void
allocate(uint16_t start, int32_t length)
{
        if (start + length > fNumBits)
                return;

        if (fLargestValid) {
                bool cut = false;
                if (fLargestStart == start) {
                        // cut from start
                        fLargestStart += length;
                        fLargestLength -= length;
                        cut = true;
                } else if (start > fLargestStart
                        && start < fLargestStart + fLargestLength) {
                        // cut from end
                        fLargestLength = start - fLargestStart;
                        cut = true;
                }
                if (cut && (fLargestLength < fLargestStart
                                || fLargestLength
                                                < (int32_t)fNumBits - (fLargestStart + fLargestLength))) {
                        // might not be the largest block anymore
                        fLargestValid = false;
                }
        }
}


void
free(uint16_t start, int32_t length)
{
        if (start + length > fNumBits)
                return;

        // The range to be freed cannot be part of the valid largest range
        if (!(!fLargestValid || start + length <= fLargestStart
                || start > fLargestStart))
                printf("ASSERT failed!\n");

        if (fLargestValid
                && (start + length == fLargestStart
                        || fLargestStart + fLargestLength == start
                        || (start < fLargestStart && fLargestStart > fLargestLength)
                        || (start > fLargestStart
                                && (int32_t)fNumBits - (fLargestStart + fLargestLength)
                                                > fLargestLength))) {
                fLargestValid = false;
        }
}


void
test(int32_t num, int32_t nextLargestStart, int32_t nextLargestLength,
        bool nextLargestValid)
{
        const char* error = NULL;
        if (nextLargestValid != fLargestValid)
                error = "valid differs";
        else if (!nextLargestValid)
                return;

        if (nextLargestStart != fLargestStart)
                error = "start differ";
        else if (nextLargestLength != fLargestLength)
                error = "length differs";

        if (error == NULL)
                return;

        printf("%d: %s: is %d.%d%s, should be %d.%d%s\n", num, error, fLargestStart,
                fLargestLength, fLargestValid ? "" : " (INVALID)", nextLargestStart,
                nextLargestLength, nextLargestValid ? "" : " (INVALID)");
        exit(1);
}


void
test_allocate(int32_t num, int32_t largestStart, int32_t largestLength,
        int32_t start, int32_t length, int32_t nextLargestStart,
        int32_t nextLargestLength, bool nextLargestValid)
{
        fLargestStart = largestStart;
        fLargestLength = largestLength;
        fLargestValid = true;

        printf("Test %d: %d.%d - allocate %d.%d\n", num, fLargestStart,
                fLargestLength, start, length);

        allocate(start, length);
        test(num, nextLargestStart, nextLargestLength, nextLargestValid);
}


void
test_free(int32_t num, int32_t largestStart, int32_t largestLength, int32_t start,
        int32_t length, int32_t nextLargestStart, int32_t nextLargestLength,
        bool nextLargestValid)
{
        fLargestStart = largestStart;
        fLargestLength = largestLength;
        fLargestValid = true;

        printf("Test %d: %d.%d - free %d.%d\n", num, fLargestStart, fLargestLength,
                start, length);

        free(start, length);
        test(num, nextLargestStart, nextLargestLength, nextLargestValid);
}


int
main(int argc, char** argv)
{
        puts("------------- Allocate Tests -------------\n");
        test_allocate(1, 40, 50, 20, 20, 40, 50, true); // touch start
        test_allocate(2, 40, 50, 20, 19, 40, 50, true); // don't touch start
        test_allocate(3, 40, 10, 40, 1, 41, 9, false);  // cut start
        test_allocate(4, 40, 50, 40, 1, 41, 49, true);  // cut start
        test_allocate(5, 40, 50, 90, 1, 40, 50, true);  // touch end
        test_allocate(6, 40, 50, 89, 1, 40, 49, true);  // cut end
        test_allocate(7, 40, 20, 59, 1, 40, 19, false); // cut end
        test_allocate(8, 0, 51, 0, 1, 1, 50, true);             // cut start
        test_allocate(9, 0, 51, 0, 2, 2, 49, true);             // cut start
        test_allocate(10, 0, 51, 0, 3, 3, 48, false);   // cut start

        puts("------------- Free Tests -------------\n");
        test_free(1, 40, 50, 20, 20, 40, 50, false);    // touch start
        test_free(2, 40, 50, 20, 19, 40, 50, true);             // before start
        test_free(3, 50, 40, 20, 19, 40, 50, false);    // before start
        test_free(4, 40, 40, 80, 20, 40, 80, false);    // touch end
        test_free(5, 40, 40, 81, 20, 40, 40, true);             // after end
        test_free(6, 40, 20, 60, 20, 40, 80, false);    // touch end
        test_free(7, 40, 20, 61, 20, 40, 80, false);    // after end
        test_free(8, 40, 20, 41, 20, 40, 80, false);    // after end
        return 0;
}