Category : Files from Magazines
Archive   : DDJ0489.ZIP
Filename : MEMCMP.ASC

_A MEMORY ALLOCATION COMPACTION SYSTEM_
by Steve Peterson


[LISTING ONE]


/**** mem.h data structures for memory manager
S. Peterson programmer 12/88
*/
typedef unsigned char byte;
typedef unsigned int uint;

/* This structure is the header of a memory block. It lies before
the actual memory block. */
struct memBlkHdr {
char checkByte; /* Header validation */
byte flags; /* Flags (see below) */
byte segment;/* Segment of this block */
struct memBlkHdr *prev; /* Pointer-previous block */
uint size; /* size of block */
int pointerNum; /* Block master pointer */
void (*func)(void *, byte, uint, void *);
} ;

typedef struct memBlkHdr MEMBLK;

/* These are the definitions of each of the flags in the flags byte
of memBlkHdr. */

#define BLK_INUSE 0x01 /* Block is allocated */
#define BLK_DELETABLE 0x02 /* Block can be deleted */
#define BLK_LOCKED 0x04 /* Block is locked */
#define BLK_FUNCDELETE 0x08 /* Call block function on delete */
#define BLK_FUNCMOVE 0x10 /* Call block function on move */
#define BLK_DELETED 0x20 /* Block has been deleted */
#define BLK_LAST 0x40 /* Last block in segment */

/* freePtr is stored at the beginning of the user part of a
free block. It contains the links to next and previous free blocks
in the segment. prev is NULL if this is the first free block, and
next is NULL if this is the last block */

struct freePtr {
MEMBLK *prev; /* Pointer to previous free block */
MEMBLK *next; /* Pointer to next free block */
} ;

typedef struct freePtr FREEBLK;

/* Macro to return address of data area give block header address */

#define DATALOC(xx) ((byte *) (xx) + sizeof(MEMBLK))

/* Macro to return address of header given data area address */

#define HEADERLOC(xx) ((byte *) (xx) - sizeof(MEMBLK))

/* This is an entry in the master block table. */

struct masterSegmentEntry {
void *block; /* Address, associated block */
uint size; /* Size of block */
uint freeSpace; /* Amount of free space */
struct memBlkHdr *free; /* First free block */
struct memBlkHdr *last; /* Last reference free block */
} ;

#define DEFSEGSIZE 4096 /* Default segment size */
#define CB 'S'

/* MINREMAINDER is the smallest free block that can remain after
allocation. Making this larger reduces fragmentation but wastes
more space. */

#define MINREMAINDER 20

/* MINBLOCKDATA is the smallest block data area that can be created. This
must be at least sizeof(FREEBLK) bytes so there is space for the
next and prev pointers stored in a free block. */

#define MINBLOCKDATA (sizeof(FREEBLK))

/* Function prototypes */

#ifndef NOPROTO

int MemInit(long int, int);
int MemLocked(void **);
void MemLock(void **);
void MemUnlock(void **);
void MemDeletable(void **);
void MemUndeletable(void **);
int MemDeleted(void **);
void **MemAlloc(uint);
void **MemAllocFunc(uint,void (*)(void *,byte, uint, void *), uint);
void MemFree(void **);
uint MemGetLargest(void);
uint MemGetCurrentLargest(void);
void MemCompact(void);

#endif


[LISTING TWO]

/***** mem.c Compactible memory manager
S. Peterson programmer 12/88, 1/89
This module provides a memory management system with the following
features:
. Relocatable memory blocks
. Able to collapse fragemented free space
. Disposable blocks
. Lockable blocks
*/

#include
#include
#include
#include
#include
#include
#include
#include "mem.h"

/* Static module data */

struct masterSegmentEntry *mst = NULL; /* Master segment table */

byte numSegs = -1; /* Number of whole & partial segments */
byte lastSeg = -1; /* Index of last segment used */

void **mpt = NULL; /* Master pointer table */
int numMP = -1; /* Number of master pointers allocated */
int mpFree = -1; /* Number of master pointers free */
int lastMP = -1; /* Last master pointer used */

/* Local function declarations */

#ifndef NOPROTO

static int FindFreeBlock(int, uint, void **);
static int AllocBlock(uint, void **, byte);
static int GetFreeMP(void);
static void ReleaseMP(int);
static void CompactSeg(byte, uint, int);

#endif

/** MemInit -- initalize memory manager
Entry lSize size of requested memory in bytes
nHandles number of block handles to allocate
Exit none
Returns TRUE worked
FALSE failed
**/
int
MemInit(lSize, nHandles)
long int lSize;
int nHandles;
{
byte numWhole; /* Number of whole segments to create */
uint numBytes; /* Size of partial segment */
uint createSize; /* Size to create */
MEMBLK *mbh; /* Work block header */
int i; /* Work */
FREEBLK *f; /* Free links */

/* Allocate handle list */

if ((mpt = (void **) malloc(sizeof(void *)*nHandles)) == NULL)
return FALSE;

numMP = nHandles;
for (i = 0; i < numMP; mpt[i] = NULL, i++) ;
mpFree = numMP;
lastMP = 0;

/* Determine size of segments to create */

numWhole = (byte) (lSize / (long) DEFSEGSIZE);
numBytes = (uint) (lSize % (long) DEFSEGSIZE);
numSegs = numWhole + 1;
lastSeg = 0;

if ((mst = (struct masterSegmentEntry *) malloc(sizeof
(struct masterSegmentEntry)*(numSegs))) == NULL)
return FALSE;

/* Allocate segments */

for(i = 0; i < numSegs; i++) {
if (i == numSegs - 2) { /* Second to last */
if (numBytes < DEFSEGSIZE / 4) { /* Last is small */
numBytes += DEFSEGSIZE / 4;
createSize = DEFSEGSIZE - (DEFSEGSIZE / 4);
} else {
createSize = DEFSEGSIZE;
}
} else if (i == numSegs - 1) { /* Last */
createSize = numBytes;
} else { /* Whole segment */
createSize = DEFSEGSIZE;
}
if (createSize < sizeof(MEMBLK) + 10)
return FALSE;
if ((mst[i].block = (void *) malloc(createSize)) == NULL)
return FALSE;
mst[i].size = createSize;
mst[i].freeSpace = createSize;

/* Allocate one block in segment */

mbh = (MEMBLK *) mst[i].block;
mst[i].free = mbh;
mst[i].last = mbh;

mbh->checkByte = CB;
mbh->prev = NULL;
mbh->flags = BLK_LAST;
mbh->size = mst[i].size;
mbh->segment = (byte) i;

/* Clear next and prev pointer area */

f = (FREEBLK *) DATALOC(mbh);
f->prev = NULL;
f->next = NULL;
}
return TRUE;
}

/** MemLocked -- test whether a block is locked
Entry block address of a block
Exit none
Returns TRUE block is locked
FALSE not locked
**/
int
MemLocked(block)
void **block;
{
return !(((MEMBLK *) HEADERLOC(*block))->flags & BLK_LOCKED);
}

/** MemLock -- locks a block into a particular location in memory
Entry block address of block to lock
Exit none
Returns void
**/
void
MemLock(block)
void **block;
{
((MEMBLK *) HEADERLOC(*block))->flags |= BLK_LOCKED;
}

/** MemUnlock -- unlocks a block
Entry block address of block to unlock
Exit none
Returns void
**/
void
MemUnlock(block)
void **block;
{
((MEMBLK *) HEADERLOC(*block))->flags &= ~BLK_LOCKED;
}

/** MemDeletable -- make a block deletable
Entry block address of block to mark as deletable
Exit none
Returns void
**/
void
MemDeletable(block)
void **block;
{
((MEMBLK *) HEADERLOC(*block))->flags |= BLK_DELETABLE;
}

/** MemUndeletable -- mark a block as undeletable
Entry block address of block to mark
Exit none
Returns void
**/
void
MemUndeletable(block)
void **block;
{
((MEMBLK *) HEADERLOC(*block))->flags &= ~BLK_LOCKED;
}

/** MemIsDeleted -- test whether a block has been deleted
Entry block address of a block
Exit none
Returns TRUE block is available
FALSE has been deleted
**/
int
MemDeleted(block)
void **block;
{
return (((MEMBLK *) HEADERLOC(*block))->flags & BLK_DELETED) != 0;
}


/** MemAlloc -- allocate memory block
Entry size size of block to allocate
Exit none
Returns pointer to created block, or NULL if not enough room to create
Notes The function operates by first examining the current segment
for a first fit to the requested size. It then proceeds to
the remaining blocks looking for a free block of adequate
size.
If no block exists that is large enough, it examines the
segment list looking for a segment that can be compacted
to produce enough room. The segment with the fewest
allocated blocks is favored for compaction.
Possible enhancement: if no segment has enough room, shuffle
blocks between segments.
If there is not enough room in any segment, the function
fails.
**/
void **
MemAlloc(size)
uint size;
{
byte curSeg; /* Current segment */
byte segIndex; /* Index of segment in list */
long ltotalFree = 0l; /* Total free space */
byte maxFreeSeg = 255; /* Segment, most free space */
uint maxFreeSize = 0; /* Segment space, most space */
MEMBLK *b; /* Block address to allocate */
int created = FALSE; /* Block created */
int mp; /* Master pointer */

if ((mp = GetFreeMP()) < 0)
return NULL;

if (size > DEFSEGSIZE - sizeof(MEMBLK))
return NULL;

if (size < MINBLOCKDATA) /* Smallest allocatable block */
size = MINBLOCKDATA;
size += sizeof(MEMBLK); /* Add header to block */

/* First pass -- try to allocate from current block structure */

for (segIndex = 0; (segIndex < numSegs) && (!created); segIndex++) {

curSeg = (lastSeg + segIndex) % numSegs;

/* Get stats */

ltotalFree += (long) mst[curSeg].freeSpace;

/* Is there enough space in the current segment to allocate? */

if (mst[curSeg].freeSpace >= size) {

if (maxFreeSize < mst[curSeg].freeSpace) {
maxFreeSize = mst[curSeg].freeSpace;
maxFreeSeg = curSeg;
}

/* Search free list for first fit */

if (FindFreeBlock(curSeg, size, &b)) {

/* Allocate */

if (!(created = AllocBlock(size, &b, curSeg)))
return FALSE;
}
}
}

/* Which segment could be compacted to create a block large enough?
We kept track of the segment with the most free space. This should

compact easily. */

if (!created && (maxFreeSeg != 255)) {
/* Compact to produce needed free space */

curSeg = maxFreeSeg;
CompactSeg(curSeg, size, FALSE);

if (!FindFreeBlock(curSeg, size, &b)) {
CompactSeg(curSeg, size, TRUE);

if (!FindFreeBlock(curSeg, size, &b))
return NULL;
}

if (!(created = AllocBlock(size, &b, curSeg)))
return FALSE;
}

if (created) {
mst[curSeg].freeSpace -= b->size;
mpt[mp] = DATALOC(b);
b->pointerNum = mp;
b->func = NULL;
lastSeg = curSeg;
return (void *) &(mpt[mp]);
} else {
ReleaseMP(mp);
return NULL;
}
}

/** MemAllocFunc -- allocate a memory block with an associated function
Entry size size of block to allocate
func function to call
flags following constants:
BLK_FUNCDELETE call function when block deleted
BLK_FUNMOVE call function when block moved
Exit none
Returns pointer to allocated block, or NULL if no space available
Notes Calls memAlloc to allocate memory
**/
void **
MemAllocFunc(size, func, flags)
uint size;
void (*func)(void *, byte, uint, void *);
uint flags;
{
void **aBlock; /* Allocated block */
MEMBLK *b; /* Dereferenced block header */

if ((aBlock = MemAlloc(size)) != NULL) {
b = (MEMBLK *) HEADERLOC(*aBlock);
b->flags |= flags & (BLK_FUNCMOVE | BLK_FUNCDELETE);
b->func = func;
return aBlock;
} else {
return NULL;
}
}

/** FindFreeBlock -- locate a free block in a segment
Entry seg segment to search
size bytes required for block including header
Exit b address of block header (if found)
Returns TRUE block found
FALSE no space
Notes Finds a free block in the current segment. Starts
with the last-referenced free block in the segment. This
spreads the allocations through the segment and combats
fragmentation.
The caller can save some time by first checking to see if
the segment has enough free space to allocate the block.
This algorithm uses the first-fit method, which is fast but
promotes fragmentation.
**/
static int
FindFreeBlock(seg, size, b)
int seg;
uint size;
void **b;
{
MEMBLK *m; /* Current memory block */

m = mst[seg].last;

if (m != NULL) {
while (m->size < size) {
if ((m = ((FREEBLK *) DATALOC(m))->next) == NULL) {
/* End of free list */
m = mst[seg].free;
}

if (m == mst[seg].last)
break;
}

if (m->size < size) { /* No block large enough */
*b = NULL;
return FALSE;
} else { /* Block found */
*b = m;
return TRUE;
}
} else { /* No block */
*b = NULL;
return FALSE;
}
}

/** AllocBlock -- allocate a block
Entry size size of block (including header) to allocate
b address of block where it will be allocated
Exit b Address of allocated block header (this is
different that the b input parameter)
Returns TRUE allocated
FALSE memory structure corrupt
Notes This function takes a block and splits it in two. If the
remaining free block is small, the entire block is allocated
and no free portion is created. This can waste some memory,
but avoids extreme fragmentation.
**/

static int
AllocBlock(size, b, segment)
uint size;
void **b;
byte segment;
{
MEMBLK *freeBlock; /* Free block */
MEMBLK *nextBlock; /* Next block */
MEMBLK *aBlock; /* Allocated block */
FREEBLK *curFree; /* Free pointers in block we are allocating */
FREEBLK *t; /* Pointer to free block we are adjusting */

freeBlock = (MEMBLK *) *b;

if ((freeBlock->size - MINREMAINDER < size)) {

/* Whole block will be allocated */

aBlock = freeBlock;
size = aBlock->size;
aBlock->flags |= BLK_INUSE;

curFree = (FREEBLK *) DATALOC(aBlock);

if (mst[segment].free == aBlock) {
/* Implicit: aBlock is first in list */
mst[segment].free = curFree->next;
}

if (curFree->next != NULL) {
t = (FREEBLK *) DATALOC(curFree->next);
t->prev = curFree->prev;
mst[segment].last = curFree->next;
} else if (curFree->prev != NULL) {
t = (FREEBLK *) DATALOC(curFree->prev);
t->next = curFree->next;
mst[segment].last = curFree->prev;
} else { /* No free block */
mst[segment].last = NULL;
mst[segment].free = NULL;
}

} else { /* Block will be split */

aBlock = (MEMBLK *) ((byte *) freeBlock +
(freeBlock->size - size));
aBlock->checkByte = CB;
aBlock->prev = freeBlock;
aBlock->flags = BLK_INUSE;
aBlock->size = size;
aBlock->segment = segment;

freeBlock->size -= size;

/* Is block last in segment? */

if ((freeBlock->flags & BLK_LAST) != 0) {
freeBlock->flags &= ~BLK_LAST;
aBlock->flags |= BLK_LAST;
} else {
nextBlock = (MEMBLK *) ((byte *) aBlock + (aBlock->size));
nextBlock->prev = aBlock;
}
}

*b = aBlock;
return TRUE;
}

/** GetFreeMP -- return next free master pointer
Entry none
Exit none
Returns index of next free master pointer
**/
static int
GetFreeMP()
{
int i;

if (mpFree == 0)
return -1;

for (i = 0; i < numMP; i++, lastMP++) {
if (lastMP >= numMP)
lastMP = 0;
if (mpt[lastMP] == 0) {
mpFree--;
return lastMP;
}
}

return -1;
}

/** ReleaseMP -- release a master pointer to free pool
Entry mp master pointer to release
Exit none
Returns void
**/
static void
ReleaseMP(mp)
int mp;
{
mpFree++;
mpt[mp] = NULL;
}

/** MemFree -- free a block of memory
Entry blockPtr pointer to mpt entry for block
Exit none
Returns none
**/
void
MemFree(blockPtr)
void **blockPtr;
{
MEMBLK *cur; /* Actual block */
FREEBLK *curFree; /* Free block in current block */
MEMBLK *workMem; /* Work block in memory */
FREEBLK *workFree; /* Work block in next block */
int combined = FALSE; /* Has been combined */

cur = (MEMBLK *) HEADERLOC(*blockPtr);

if (cur->checkByte != CB)
return;

ReleaseMP(cur->pointerNum); /* blockPtr no longer valid */

curFree = (FREEBLK *) DATALOC(cur);

/* Mark block as unallocated */

cur->flags &= ~BLK_INUSE;
mst[cur->segment].freeSpace += cur->size;

/* Combine with subsequent block? */

if ((cur->flags & BLK_LAST) == 0) {
workMem = (MEMBLK *) ((byte *) cur + cur->size);

if ((workMem->flags & BLK_INUSE) == 0) { /* unallocated */
combined = TRUE;

if ((workMem->flags & BLK_LAST) != 0)
cur->flags |= BLK_LAST;

workFree = (FREEBLK *) DATALOC(workMem);
curFree->next = workFree->next;
curFree->prev = workFree->prev;
cur->size += workMem->size;

/* New top of free list? */

if (workMem == mst[cur->segment].free)
mst[cur->segment].free = cur;

if (workMem == mst[cur->segment].last)
mst[cur->segment].last = cur;

/* Adjust pointers in free chain. Point to new block */

if (curFree->next != NULL) {
workFree = (FREEBLK *) DATALOC(curFree->next);

workFree->prev = cur;
}

if (curFree->prev != NULL) {
workFree = (FREEBLK *) DATALOC(curFree->prev);
workFree->next = cur;
}

/* Adjust previous block chain */

if ((cur->flags & BLK_LAST) == 0) {
workMem = (MEMBLK *) ((byte *) workMem +
workMem->size);
workMem->prev = cur;
}
}
}

/* Combine with previous block? */

if (cur->prev != NULL) {
workMem = cur->prev;

if ((workMem->flags & BLK_INUSE) == 0) { /* unallocated */
workMem->size += cur->size;

if ((cur->flags & BLK_LAST) != 0)
workMem->flags |= BLK_LAST;
cur->checkByte = '\0';

if (combined) {

/* Eliminate free block from links */

workFree = (FREEBLK *) DATALOC(workMem);
workFree->next = curFree->next;

if (workFree->next != NULL) {
workFree = (FREEBLK *)
DATALOC(workFree->next);
workFree->prev = workMem;
}

} else {

/* Free block already linked */

combined = TRUE;
}

/* Connect block chain */

if ((cur->flags & BLK_LAST) == 0) {
workMem = (MEMBLK *) ((byte *) cur + cur->size);
workMem->prev = cur->prev;
}

if (cur == mst[cur->segment].free)
mst[cur->segment].free = workMem;

if (cur == mst[cur->segment].last)
mst[cur->segment].last = workMem;

}
}

/* If not combined, link into free chain */

if (!combined) {

/* We scan backwards looking for the last block that
is free */

workMem = cur->prev;

while ((workMem != NULL) && ((workMem->flags &
BLK_INUSE) != 0)) {
workMem = workMem->prev;
}

/* A block is prior to the free block in memory */

if (workMem != NULL) {
workFree = (FREEBLK *) DATALOC(workMem);
curFree->prev = workMem;
curFree->next = workFree->next;
workFree->next = cur;

if (curFree->next != NULL) {
workFree = (FREEBLK *) DATALOC(curFree->next);
workFree->prev = cur;
}
} else { /* Place at beginning of list */
curFree->prev = NULL;
curFree->next = mst[cur->segment].free;

if (mst[cur->segment].free != NULL) {
workFree=(FREEBLK *) DATALOC(mst[cur->segment].free);
workFree->prev = cur;
}
mst[cur->segment].free = cur;
}
}

if (mst[cur->segment].last == NULL) {
mst[cur->segment].last = cur;
mst[cur->segment].free = cur;
}
}

/** MemGetLargest -- returns size of largest block available after
compaction
Entry none
Exit none
Returns Free space in segment with most free space, less the size of
one block header.
**/
uint
MemGetLargest()
{
byte seg; /* Current segment */
uint largest = 0; /* Free space */

for (seg = 0; seg < numSegs; seg++)
if (largest < mst[seg].freeSpace)
largest = mst[seg].freeSpace;

if (largest < sizeof(MEMBLK))
return 0;
else
return largest - sizeof(MEMBLK);
}

/** MemGetCurrentLargest -- returns size of largest available block
Entry none
Exit none
Returns size of largest available block
**/
uint
MemGetCurrentLargest()
{
byte seg; /* Current segment */
MEMBLK *curBlock; /* Current block */
FREEBLK *curFree; /* Current free block */
uint largest = 0; /* Largest block found */

for (seg = 0; seg < numSegs; seg++) {
curBlock = mst[seg].free;
while (curBlock != NULL) {
if (curBlock->size > largest) {
largest = curBlock->size;
}
curFree = (FREEBLK *) DATALOC(curBlock);
curBlock = curFree->next;
}
}

if (largest < sizeof(MEMBLK))
return 0;
else
return largest - sizeof(MEMBLK);
}

/** MemCompact -- invoke compaction routine
Entry none
Exit none
Returns none
**/
void
MemCompact()
{
byte seg;

for (seg = 0; seg < numSegs; seg++) {
CompactSeg(seg, DEFSEGSIZE, FALSE);
}
}

/** CompactSeg -- compact a segment
Entry seg segment to compact
size desired free block size
deletable TRUE if deletable segments should be deleted
FALSE otherwise
Exit none
Returns none
**/
static void
CompactSeg(seg, size, deletable)
byte seg;
uint size;
int deletable;
{
MEMBLK *copyLoc = NULL; /* Next place to copy */
FREEBLK *copyFree; /* Free pointers */
MEMBLK *curBlk; /* First block */
MEMBLK *saveBlk; /* Saved block location */
MEMBLK *prevBlk = NULL; /* Previous block */
MEMBLK *nextFree = NULL; /* Saved next free block */
MEMBLK *prevFree = NULL; /* Saved prev. free block */
FREEBLK *tmpFree; /* Temporary free pointer */
uint spaceRecovered = 0; /* Amount space recovered */
int last = FALSE; /* Last record found */

curBlk = mst[seg].block;

while ((spaceRecovered < size) && (!last)) {

last = (curBlk->flags & BLK_LAST) != 0;

if (((curBlk->flags & BLK_DELETABLE) != 0) && (deletable) &&
(curBlk->size > sizeof(MEMBLK) + MINBLOCKDATA)) {
spaceRecovered += curBlk->size - sizeof(MEMBLK) -
MINBLOCKDATA;

if (copyLoc != NULL) {

if ((curBlk->flags & BLK_FUNCDELETE) != 0)
(*(curBlk->func))(curBlk, BLK_FUNCDELETE
| BLK_FUNCMOVE, curBlk->size, copyLoc);

/* Save location of block */

saveBlk = curBlk;

/* Move block header to new location */
memmove(copyLoc, curBlk, sizeof(MEMBLK));

/* Set up new pointer to previous block */

copyLoc->prev = prevBlk;
copyLoc->flags &= ~BLK_LAST;
copyLoc->flags |= BLK_DELETED;
copyLoc->size = sizeof(MEMBLK) + MINBLOCKDATA;
mpt[copyLoc->pointerNum] = DATALOC(copyLoc);
prevBlk = copyLoc;
curBlk = (MEMBLK *) ((byte *) saveBlk +
copyLoc->size);
copyLoc = (MEMBLK *) ((byte *) copyLoc +
copyLoc->size);

} else {
if ((curBlk->flags & BLK_FUNCDELETE) != 0)
(*(curBlk->func))(curBlk,
BLK_FUNCDELETE, curBlk->size, NULL);

/* Initialize free area after block */

curBlk->flags &= ~BLK_LAST;
curBlk->flags |= BLK_DELETED;
saveBlk = curBlk;
prevBlk = curBlk;
curBlk = (MEMBLK *) ((byte *) curBlk +
curBlk->size);
saveBlk->size = sizeof(MEMBLK) + MINBLOCKDATA;
copyLoc = (MEMBLK *) DATALOC(saveBlk);

}

} else if ((curBlk->flags & BLK_INUSE) != 0) {
if (copyLoc == NULL) {
prevBlk = curBlk;
curBlk = (MEMBLK *) ((byte *) curBlk +
curBlk->size);
} else {
if ((curBlk->flags & BLK_LOCKED) == 0) {
if ((curBlk->flags & BLK_FUNCMOVE) != 0)
(*(curBlk->func))(curBlk,
BLK_FUNCMOVE, curBlk->size,
copyLoc);

/* Move block to new location */

saveBlk = curBlk;
memmove(copyLoc, curBlk, curBlk->size);

copyLoc->prev = prevBlk;
copyLoc->flags &= ~BLK_LAST;
prevBlk = copyLoc;

mpt[copyLoc->pointerNum] =
DATALOC(copyLoc);

/* Move pointer to next block */

curBlk = (MEMBLK *) ((byte *)saveBlk +
copyLoc->size);
copyLoc = (MEMBLK *) ((byte *)copyLoc +
copyLoc->size);

} else { /* Close up current free block */

curBlk = (MEMBLK *) ((byte *) curBlk +
curBlk->size);

copyLoc->flags = 0;
copyLoc->checkByte = CB;
copyLoc->prev = prevBlk;
copyLoc->size = spaceRecovered;
copyLoc->pointerNum = 0;
copyLoc->segment = seg;
saveBlk =(MEMBLK *) ((byte *)copyLoc +
copyLoc->size);
saveBlk->prev = copyLoc;
spaceRecovered = 0;

copyFree =(FREEBLK *)DATALOC(copyLoc);
copyFree->prev = prevFree;
if (prevFree != NULL) {
tmpFree = (FREEBLK *)
DATALOC(prevFree);
tmpFree->next = copyLoc;
}

copyFree->next = nextFree;
if (nextFree != NULL) {
tmpFree = (FREEBLK *)
DATALOC(nextFree);
tmpFree->prev = copyLoc;
}

prevBlk = copyLoc;
prevFree = copyLoc;
copyLoc = NULL;
}
}
} else { /* Free */
if (copyLoc == NULL)
copyLoc = curBlk;

spaceRecovered += curBlk->size;

nextFree = (MEMBLK *) (((FREEBLK *)
DATALOC(curBlk))->next);
curBlk = (MEMBLK *) ((byte *) curBlk + curBlk->size);
}
}

/* At this point copyLoc points to the beginning of the free area,
spaceRecovered is the size of the new free block, and saveBlk
points to the next free block in the segment */

if (copyLoc != NULL) {
copyLoc->checkByte = CB;
copyLoc->prev = prevBlk;
copyLoc->size = spaceRecovered;
copyLoc->pointerNum = 0;
copyLoc->segment = seg;

if (last) {
copyLoc->flags = BLK_LAST;
} else {
copyLoc->flags = 0;
saveBlk = (MEMBLK *)((byte *) copyLoc + copyLoc->size);
saveBlk->prev = copyLoc;
}

copyFree = (FREEBLK *) DATALOC(copyLoc);
copyFree->prev = prevFree;
if (prevFree != NULL) {
tmpFree = (FREEBLK *) DATALOC(prevFree);
tmpFree->next = copyLoc;
}
copyFree->next = nextFree;
if (nextFree != NULL) {
tmpFree = (FREEBLK *) DATALOC(nextFree);
tmpFree->prev = copyLoc;
}
mst[seg].free = copyLoc;
mst[seg].last = copyLoc;
}
}


[LISTING THREE]

/***** demo.c Demonstration program for memory manager
S. Peterson programmer 1/89
This program demonstrates the features of the memory manager.
**/
#include
#include
#include
#include
#include "mem.h"

void blockFunc(void *, byte, uint, void *); /* Prototype, block function */
int main(void);

int
main()
{
void **p; /* Double pointer to block */
void *q; /* Single pointer to block */

/* Allocate a 30K buffer and 100 master pointers */

if (MemInit(30000l, 100) != TRUE)
exit(1);

/* Allocate a buffer of 1024 bytes. It is created as moveable and
undeletable */

if ((p = MemAlloc(1024)) == NULL)
printf("Error allocating 1024 bytes.\n");

MemLock(p); /* Make the block unmoveable */
q = *p; /* Get pointer to memory block */
memset(q, 0, 1024); /* Initialize block to 0 */

MemUnlock(p); /* Make the block moveable */
/* Note: q no longer valid */

MemCompact(); /* Cause memory to be compacted */

MemFree(p); /* Deallocate p */

/* Allocate a block with an associated function. */

if ((p = MemAllocFunc(1024, blockFunc, BLK_FUNCDELETE |
BLK_FUNCMOVE)) == NULL)
exit(2);

MemFree(p); /* Deallocate p */

return 0;
}

void
blockFunc(blockPtr, flags, length, newLoc)
void *blockPtr;
byte flags;
uint length;
void *newLoc;
{
if ((flags & BLK_FUNCMOVE) != 0) {
/* Perform some action when block moves */
}

if ((flags & BLK_FUNCDELETE) != 0) {
/* Perform some action when block is deleted */
}
}