/* Copyright (C) Stephen Chung, 1991-1992.  All rights reserved. */

#include <windows.h>

#define MAGIC           0x42022667

typedef struct MemoryStruct {
	long int magic;
	void far *page;
	unsigned int size;
	BOOL allocated;
	struct MemoryStruct far *next, far *prev;
} MEMHEADER;

typedef struct PageHeaderStruct {
    long int magic;
    HANDLE handle;
    unsigned int size;
    unsigned int used;
    unsigned int overhead;
    MEMHEADER far *data, far *empty;
    struct PageHeaderStruct far *next, far *prev;
} MEMPAGEHEADER;

typedef struct {
    MEMPAGEHEADER far *pages;
    int nr_pages;
} MAINMEMHEADER;

#define PAGESIZE        (4 * 1024)
#define USEABLESIZE     (PAGESIZE - sizeof(MEMPAGEHEADER) - sizeof(MEMHEADER))


static MAINMEMHEADER header = { NULL, 0 };



static MEMPAGEHEADER far *AddPage(unsigned int n)
{
    void far *cp;
    MEMHEADER far *mp;
    MEMPAGEHEADER far *p;
    HANDLE handle = NULL;

    handle = GlobalAlloc(GHND, n);
    if (handle == NULL) {
        ErrorMessage("Out of memory: allocating %d bytes", n);
        return (NULL);
    }

    if (header.pages == NULL || header.nr_pages <= 0) {
        p = header.pages = (MEMPAGEHEADER far *) GlobalLock(handle);
        p->prev = NULL;
    } else {
        for (p = header.pages; p->next != NULL; p = p->next);
        p->next = (MEMPAGEHEADER far *) GlobalLock(handle);
        p->next->prev = p;
        p = p->next;
    }

    p->magic = MAGIC;
    p->handle = handle;
    p->next = NULL;
    p->size = n;
    p->used = 0;
    p->overhead = sizeof(MEMPAGEHEADER) + sizeof(MEMHEADER);

    cp = ((char far *) p) + sizeof(MEMPAGEHEADER);
    mp = (MEMHEADER far *) cp;

    p->data = p->empty = mp;

    mp->magic = 0L;
    mp->allocated = FALSE;
    mp->page = p;
    mp->size = p->size - p->overhead;
    mp->next = mp->prev = NULL;

    header.nr_pages++;

    return (p);
}



static void DeletePage (MEMPAGEHEADER far *p)
{
    if (p->next == NULL && p->prev == NULL) {
        header.pages = NULL;
        header.nr_pages = 0;
        GlobalFree(GlobalUnlock(p->handle));
    } else {
        if (p == header.pages) header.pages = p->next;
        header.nr_pages--;

        if (p->prev != NULL) p->prev->next = p->next;
        if (p->next != NULL) p->next->prev = p->prev;

        GlobalFree(GlobalUnlock(p->handle));
    }
}



void far *SegHeapAlloc (unsigned int n)
{
    MEMPAGEHEADER far *p;
    MEMHEADER far *mp;
    char far *cp;

    if (n >= 65535) {
        ErrorMessage("MyGlobalAlloc: size (%u) > 64K!", n);
        return (NULL);
    }

    /* Larger than page size? */

    if (n > USEABLESIZE) {
		p = AddPage(n + sizeof(MEMPAGEHEADER) + sizeof(MEMHEADER));

        mp = p->data;
        mp->magic = MAGIC;
        mp->allocated = TRUE;

        p->used = n;
        p->empty = NULL;

        cp = ((char far *) mp) + sizeof(MEMHEADER);
        return ((void far *) cp);
    }


    /* Search for the hole */

    for (p = header.pages; p != NULL; p = p->next) {
        /* Scan the chains */
        if (p->size - p->used - p->overhead <= 0) continue;
		if (p->empty == NULL) continue;

        for (mp = p->empty; mp != NULL; mp = mp->next) {
            if (!mp->allocated && mp->size >= n) break;
        }

        if (mp != NULL) break;
    }

    /* New page needed? */

    if (p == NULL) {
        p = AddPage(PAGESIZE);
		mp = p->data;
    }

    /* Do we need to break it up? */

    if (mp->size - n > sizeof(MEMHEADER)) {
        MEMHEADER far *mp2;

        cp = ((char far *) mp) + n + sizeof(MEMHEADER);
        mp2 = (MEMHEADER far *) cp;

        mp2->magic = 0L;
        mp2->allocated = FALSE;
        mp2->page = p;
        mp2->size = mp->size - n - sizeof(MEMHEADER);

        mp2->next = mp->next;
        mp2->prev = mp;
        if (mp->next != NULL) mp->next->prev = mp2;
        mp->next = mp2;


        p->overhead += sizeof(MEMHEADER);

        mp->size = n;
    }

    mp->magic = MAGIC;
    mp->allocated = TRUE;

    p->used += n;
    cp = ((char far *) mp) + sizeof(MEMHEADER);

    /* Search for the next empty hole */

    for (; mp != NULL; mp = mp->next) {
        if (!mp->allocated && mp->size > 0) break;
    }

    p->empty = mp;

    return ((void far *) cp);
}


void SegHeapFree (void far *vp)
{
	MEMPAGEHEADER far *p;
	MEMHEADER far *mp, far *mp2;
	char far *cp;

	cp = ((char far *) vp) - sizeof(MEMHEADER);
	mp = (MEMHEADER far *) cp;

    if (mp->magic != MAGIC || !mp->allocated) {
        ErrorMessage("Trying to deallocate invalid memory block [%Fp, %u byte%s]!\n",
                        vp, mp->size, (mp->size > 1) ? "s" : "");
		return;
	}

	p = (MEMPAGEHEADER far *) mp->page;
	p->used -= mp->size;

    mp->magic = 0L;
    mp->allocated = FALSE;

	/* Merge? */

    mp2 = mp->prev;

    if (mp2 != NULL && !mp2->allocated) {
        mp2->next = mp->next;
        if (mp->next != NULL) mp->next->prev = mp2;
        mp2->size += mp->size + sizeof(MEMHEADER);

        p->overhead -= sizeof(MEMHEADER);

        mp = mp2;
    }

    mp2 = mp->next;

    if (mp2 != NULL && !mp2->allocated) {
        mp->next = mp2->next;
        if (mp2->next != NULL) mp2->next->prev = mp;

        mp->size += mp2->size + sizeof(MEMHEADER);

		p->overhead -= sizeof(MEMHEADER);
	}

    if (mp->prev == NULL && mp->next == NULL) {
        DeletePage(p);
    } else {
        if (p->empty == NULL || mp < p->empty) p->empty = mp;
    }
}



void far *SegHeapRealloc (void far *p, unsigned int n)
{
	MEMHEADER far *mp;
	char far *cp;

	/* Block already large enough? */

	cp = ((char far *) p) - sizeof(MEMHEADER);
	mp = (MEMHEADER far *) cp;

	if (mp->magic != MAGIC) {
        ErrorMessage("Trying to reallocate invalid memory block [%Fp, %u byte%s]!\n",
                        p, mp->size, (mp->size > 1) ? "s" : "");
        return (p);
    }

    if (mp->size >= n) return (p);      /* No need to do anything */

    /* Else swap to another block */

    cp = SegHeapAlloc(n);
    _fmemcpy(cp, p, (mp->size >= n) ? n : mp->size);
    SegHeapFree(p);

    /* This is not really safe
    SegHeapFree(p);
    cp = SegHeapAlloc(n);
    if ((void far *) cp != p) {
        _fmemcpy(cp, p, (mp->size >= n) ? n : mp->size);
    }
    */

    return ((void far *) cp);
}



unsigned int SegHeapGetSize (void far *p)
{
	MEMHEADER far *mp;
	char far *cp;

	cp = ((char far *) p) - sizeof(MEMHEADER);

	mp = (MEMHEADER far *) cp;

	if (mp->magic != MAGIC) {
        ErrorMessage("Trying to get size of invalid memory block [%Fp, %u byte%s]!\n",
                        p, mp->size, (mp->size > 1) ? "s" : "");
		return (0);
    }

    return (mp->size);
}



void far *SegHeapDuplicate (void far *p)
{
    unsigned int len;
    void far *p1;

    len = SegHeapGetSize(p);
    p1 = SegHeapAlloc(len);
	_fmemcpy(p1, p, len);

    return (p1);
}



void MemoryStatistics (long int *allocated, long int *used, long int *overhead)
{
    MEMPAGEHEADER far *p;

    *allocated = *used = *overhead = 0L;

    for (p = header.pages; p != NULL; p = p->next) {
        *allocated += p->size;
        *used += p->used;
        *overhead += p->overhead;
    }
}


void FreeAllMemory (void)
{
    MEMPAGEHEADER far *p, far *p1;

    for (p = header.pages; p != NULL; ) {
        p1 = p->next;
        GlobalFree(GlobalUnlock(p->handle));
        p = p1;
    }

    header.pages = NULL;
    header.nr_pages = 0;
}


#ifdef DEBUG

/* For debugging purposes...  not very pretty */

void PrintMemoryChains(void)
{
    MEMPAGEHEADER far *p;
	MEMHEADER far *mp;
	char far *cp;
    char buffer[100];

	/* Block already large enough? */


    for (p = header.pages; p != NULL; p = p->next) {
        for (mp = p->data; mp != NULL; mp = mp->next) {
            sprintf(buffer, "%Fp | %u | %s", mp, mp->size, mp->allocated ? "Alloc" : "Free");
            MessageBox (NULL, buffer, "Memory Chain", MB_ICONEXCLAMATION | MB_OK);
        }
    }
}

#endif DEBUG