home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 5 Edit
/
05-Edit.zip
/
NOTEPAD2.ZIP
/
MMEM.C
< prev
next >
Wrap
C/C++ Source or Header
|
1989-02-08
|
11KB
|
398 lines
/*
* mmem.c -- Primitive memory management
*
* Created by Microsoft Corporation, 1989
*/
#include <os2.h>
#include <opendlg.h>
#include "mtypes.h"
#include "mfuncs.h"
/***********************************************************************
* Internal forward declarations
***********************************************************************/
private USHORT SizeToIndex(LONG l);
private LONG IndexToSize(USHORT i);
private VOID FreelistInsert(PED ped, PFREEBLOCK pfb);
private VOID FreelistDelete(PED ped, PFREEBLOCK pfb);
private PFREEBLOCK SplitBlock(PED ped, PFREEBLOCK pfb, USHORT usSize);
private VOID AttemptCoalesce(PED ped, PFREEBLOCK pfb);
private SEL AllocSeg(PED ped, LONG segsize);
private BOOL GrowSegs(PED ped);
private BOOL FindMoreMem(PED ped);
/***********************************************************************
* These functions map freeblock size indices to and from actual sizes.
***********************************************************************/
/* private function
*
* USHORT SizeToIndex(LONG l)
*
* returns log2(i)-5 for 32<=i<=64K
* if i<32, uses 32; if i>64K returns 12 (an error value)
* To wit:
* 0..32 => 0
* 33..64 => 1
* 65..128 => 2
* 129..256 => 3
* 257..512 => 4
* .....
* 32K+1..64K => 11
* >64K => 12
*/
private USHORT SizeToIndex(LONG l)
{
static LONG a[12] = {1<<5, 1<<6, 1<<7, 1<<8, 1<<9, 1<<10, 1<<11,
1<<12, 1<<13, 1<<14, 1<<15, 1<<16};
USHORT i;
for (i=0; ((i<12) && (a[i]<l)); i++)
/* nothing */ ;
return(i);
}
/* private function
*
* LONG IndexToSize(USHORT i)
*
* Converts a block size index (as defined in SizeToIndex above) back to
* its corresponding size.
*/
private LONG IndexToSize(USHORT i)
{
return(1<<(i+5));
}
/***********************************************************************
* Free List manipulation
*
* These functions maintain the list of free blocks
***********************************************************************/
/* private function
*
* VOID FreelistInsert(PED ped, PFREEBLOCK pfb)
*
* given a pointer to a free block, inserts that free block onto the
* free list. Assumes tag already handled.
*/
private VOID FreelistInsert(PED ped, PFREEBLOCK pfb)
{
pfb->prev = NULL;
pfb->next = ped->pfbHead;
if (ped->pfbHead == NULL) {
ped->pfbTail = pfb;
} else {
ped->pfbHead->prev = pfb;
}
ped->pfbHead = pfb;
}
/* private function
*
* VOID FreelistDelete(PED ped, PFREEBLOCK pfb)
*
* given a pointer to a free block, deletes that free block from the
* free list. Assumes tag handled elsewhere.
*/
private VOID FreelistDelete(PED ped, PFREEBLOCK pfb)
{
if (pfb->prev == NULL) {
ped->pfbHead = pfb->next;
} else {
pfb->prev->next = pfb->next;
}
if (pfb->next == NULL) {
ped->pfbTail = pfb->prev;
} else {
pfb->next->prev = pfb->prev;
}
}
/* private function
*
* VOID SplitBlock(PED ped, PFREEBLOCK pfb, USHORT usSize)
*
* given a pointer to a free block and a request size, splits the
* block in half until usSize <= size of block < 2*usSize
* As a side effect, generates lots of new freeblocks; these are put
* on the freelist so that afterwards, the smallest new freeblock
* is pointed to by the head, the second smallest new freeblock is
* second in the list, &c.
*/
private PFREEBLOCK SplitBlock(PED ped, PFREEBLOCK pfb, USHORT usSize)
{
USHORT usTag;
PFREEBLOCK pfbBuddy;
// find the size of the block we should create
usTag = SizeToIndex((LONG)usSize);
// halve the current block until we're small enough
while ((USHORT)(pfb->tag & PFB_TAGSIZE) > usTag) {
pfb->tag--; // halve freeblock size
pfbBuddy = (PFREEBLOCK)((PBYTE)pfb+freeblock_size(pfb));
*pfbBuddy = *pfb; // make its buddy
FreelistInsert(ped, pfbBuddy);
}
return(pfb);
}
/* private function
*
* VOID AttemptCoalesce(PED ped, PFREEBLOCK pfb)
*
* given a pointer to a free block, coalesces the freeblock with its
* buddy if it is also free. If so, recurses to try to continue coalescing.
*/
private VOID AttemptCoalesce(PED ped, PFREEBLOCK pfb)
{
PFREEBLOCK pfbBuddy;
ULONG ulSegSize;
// find address of buddy block
pfbBuddy = (PFREEBLOCK)((LONG)pfb ^ freeblock_size(pfb));
// stop when have coalesced all the way up the tree
if (pfbBuddy > pfb) {
DosSizeSeg(SELECTOROF(pfb),(PULONG)&ulSegSize);
if (((ULONG)(OFFSETOF(pfb)) + 2L*freeblock_size(pfb)) > ulSegSize) {
WinAlarm(HWND_DESKTOP, WA_NOTE);
return;
}
}
// Do coalesce
if (pfbBuddy->tag == pfb->tag) {
if (pfbBuddy < pfb) {
(pfbBuddy->tag)++;
FreelistDelete(ped, pfb);
AttemptCoalesce(ped, pfbBuddy);
} else {
(pfb->tag)++;
FreelistDelete(ped, pfbBuddy);
AttemptCoalesce(ped, pfb);
}
}
}
/***********************************************************************
* Allocate/Free blocks
*
* These functions allocate chunks of memory at user request and release
* them later.
***********************************************************************/
/* Public function
*
* PVOID AllocStore(PED ped, USHORT size)
*
* given a request for a certain size block of memory, allocate it
* out of the free list
*
* Returns: a pointer to the allocated memory, or NULL if can't be
* allocated.
*
* Note that at objects of size at most 32K-1 can be allocated since that is
* the largest available block after a segment is initialised
*/
public PVOID AllocStore(PED ped, USHORT size)
{
PFREEBLOCK pfb;
PVOID pv;
// find first block large enough to hold request
pfb = ped->pfbHead;
while ((pfb != NULL) && (freeblock_size(pfb) < (LONG)size+sizeof(BYTE))) {
pfb = pfb->next;
}
// if no such block could be found...
if (pfb == NULL) {
if (!(FindMoreMem(ped))) { // try to get more memory...
return NULL;
} else {
return (AllocStore(ped, size)); // ...and try again
}
} else {
// allocate out of the found block
pfb = SplitBlock(ped, pfb, size+sizeof(BYTE));
FreelistDelete(ped, pfb);
pfb->tag |= PFB_TAGRESERVED;
pv = ((PBYTE)pfb+sizeof(BYTE));
LFillStruct((PCH)pv,size,(BYTE)0xff);
return(pv);
}
}
/* public function
*
* VOID FreeStore(PED ped, PVOID p)
*
* Given a pointer previously returned by AllocStore, or internally
* synthesised so that it points one byte past a block tag, frees
* the block; it is an error to later refer to the contents at the
* pointer and behaviour is undefined.
* Marks the block as unreserved and attempts to coalesce with a "buddy"
* block (if any)
*/
public VOID FreeStore(PED ped, PVOID p)
{
PFREEBLOCK pfb;
pfb = (PFREEBLOCK)((PBYTE)p - 1);
pfb->tag &= ~PFB_TAGRESERVED;
FreelistInsert(ped, pfb);
AttemptCoalesce(ped, pfb);
}
/***********************************************************************
* Segment manipulation
*
* These functions get space from the OS (in the form of segments).
***********************************************************************/
/* Private function
*
* SEL AllocSeg(PED ped, LONG segsize)
*
* Allocate a segment from the OS and initialise it; make the segment of a
* given size (must be SEG8K, SEG16K, SEG32K, or SEG64K).
*
* Return: selector of segment (0 => error)
*/
private SEL AllocSeg(PED ped, LONG segsize)
{
SEL sel;
PSEGHDR psh;
PFREEBLOCK pfb;
// get segment from the OS memory pool
if (DosAllocSeg((USHORT)segsize, (PSEL)&sel, (USHORT)0))
return((SEL)0);
// turn the segment into all free space and insert on freelist
pfb = (PFREEBLOCK)SEGHDROF(sel);
pfb->tag = PFB_TAGSIZE & SizeToIndex(segsize);
FreelistInsert(ped,pfb);
// create a segment header for this segment
psh = (PSEGHDR)AllocStore(ped, sizeof(SEGHDR));
psh->this = sel;
psh->size = segsize;
psh->prev = NULL;
psh->next = ped->selHead;
if (ped->selHead == NULL) {
ped->selTail = psh;
} else {
ped->selHead->prev = psh;
}
ped->selHead = psh;
return(sel);
}
/* Private function
*
* BOOL GrowSegs(PED ped)
*
* Attempts to reallocate the first segment on the segment list to provide
* more memory. Obviously, the segment must double in size at each
* reallocation. If the reallocate fails, or if the segment is already
* 64K long, the function returns FALSE; otherwise the function returns
* TRUE to indicate success.
*/
private BOOL GrowSegs(PED ped)
{
PFREEBLOCK pfb;
PSEGHDR psh;
psh = ped->selHead;
if (psh == NULL) // if no segments...
return(FALSE);
if (psh->size == SEG64K) // if it can't grow further...
return(FALSE);
// try to reallocate
if (DosReallocSeg((USHORT)(psh->size*2),psh->this))
return(FALSE);
// synthesize a block header and free the block
// (will coalesce blocks as needed)
pfb = (PFREEBLOCK)(((PBYTE)SEGHDROF(psh->this))+psh->size);
pfb->tag = PFB_TAGRESERVED | (PFB_TAGSIZE & SizeToIndex(psh->size));
FreeStore(ped, (((PBYTE)pfb)+1));
psh->size *= 2;
return(TRUE);
}
/* private function
*
* BOOL FindMoreMem(PED ped)
*
* Generally looks around to try to get some more memory. First tries to
* do a reallocation; if that fails, gets a new segment. If that
* fails too then function gives up.
*/
private BOOL FindMoreMem(PED ped)
{
if (GrowSegs(ped))
return TRUE;
if (AllocSeg(ped,STORE_INITSIZE) != 0)
return TRUE;
return FALSE;
}
/***********************************************************************
* Initialisation
*
* These functions should only be called at startup. They initialise
* the memory manager.
***********************************************************************/
/* public function
*
* BOOL InitStore(PED ped)
*
* Initialise storage management
*
* Return: TRUE => initialised okay
* FALSE => problem initialising
*/
public BOOL InitStore(PED ped)
{
ped->pfbHead = NULL;
ped->pfbTail = NULL;
ped->selHead = ped->selTail = NULL;
if (0 == AllocSeg(ped, STORE_INITSIZE))
return FALSE;
}