188 lines
5.6 KiB
C
188 lines
5.6 KiB
C
/*++
|
||
|
||
Copyright (c) 1991 Microsoft Corporation
|
||
|
||
Module Name:
|
||
|
||
heap.c
|
||
|
||
Abstract:
|
||
|
||
Contains a heap allocator function.
|
||
|
||
Author:
|
||
|
||
Dan Lafferty (danl) 10-Jul-1991
|
||
|
||
Environment:
|
||
|
||
User Mode - Win32
|
||
|
||
Revision History:
|
||
|
||
10-Jul-1991 danl
|
||
Ported from LM2.0
|
||
|
||
--*/
|
||
|
||
// static char *SCCSID = "@(#)heap.c 9.1 86/10/12";
|
||
//
|
||
// Simple heap allocator for small heaps in shared memory areas.
|
||
//
|
||
|
||
#include <windef.h> // USHORT definitions
|
||
#include <heap.h> // Constants, macros, etc.
|
||
#include <align.h> // ROUND_UP_COUNT
|
||
|
||
LPBYTE heap = 0; // Pointer to start of heap
|
||
DWORD heapln = 0; // Length of heap
|
||
|
||
|
||
/*
|
||
* Msgheapalloc - simple heap allocator
|
||
*
|
||
* This function allocates blocks out of a far heap.
|
||
* It assumes that when it is called the static variable
|
||
* heap points to the far heap and the static variable heapln
|
||
* contains the length of the far heap.
|
||
*
|
||
* Msgheapalloc (cb)
|
||
*
|
||
* ENTRY
|
||
* cb - number of bytes to allocate including header
|
||
*
|
||
* RETURN
|
||
* index in far heap to start of block of length cb, or
|
||
* INULL if no such block can be found or if cb < sizeof(HEAPHDR).
|
||
*
|
||
* This function maintains a heap in which all
|
||
* blocks are implicitly linked. The header of a block is
|
||
* three bytes long. It contains the size of the block including
|
||
* the header and a one-byte flag which indicates whether the block
|
||
* is allocated or not. Any non-zero value indicates that a block
|
||
* is allocated. Note: Msgheapalloc() does NOT set the flag when it
|
||
* returns a block. It is up to the caller to mark a block as
|
||
* allocated. Unlike most heap allocators, Msgheapalloc() returns a
|
||
* pointer (index) to the header rather than just past the header.
|
||
* It does this because the message logging routines will need to
|
||
* know the lengths of blocks they process. Also, in addition to
|
||
* indicating that a block is allocated, the flag byte will be used
|
||
* to indicate the type of the block (i.e. single block message,
|
||
* multi-block message header, etc.). Since the logging routines
|
||
* will use the size of a block, it must be exactly the size
|
||
* requested.
|
||
*
|
||
* The algorithm used was chosen to minimize the size of the
|
||
* heap managing routines and to conform to the requirements
|
||
* of the logging routines.
|
||
*
|
||
* SIDE EFFECTS
|
||
*
|
||
* Changes the structure of the heap.
|
||
*/
|
||
|
||
DWORD
|
||
Msgheapalloc(
|
||
IN DWORD NumBytes // No. of bytes to allocate
|
||
)
|
||
{
|
||
DWORD i; // Index to return
|
||
DWORD newi; // New block index
|
||
DWORD nexti; // Next block index
|
||
DWORD numBytesNew; // New block size
|
||
|
||
//
|
||
// Must request at least siz bytes
|
||
//
|
||
if(NumBytes < sizeof(HEAPHDR)) {
|
||
return(INULL);
|
||
}
|
||
|
||
//
|
||
// *ALIGNMENT*
|
||
// If necessary, increase the requested size to cause the allocated
|
||
// block to fall on a 4-byte aligned boundary.
|
||
//
|
||
|
||
NumBytes = ROUND_UP_COUNT(NumBytes,4);
|
||
|
||
//
|
||
// This loop is used to traverse the heap by following the
|
||
// chain of blocks until either the end of the heap is reached
|
||
// or a free block of suitable size is found. Coalescing of
|
||
// adjacent free blocks is performed herein also.
|
||
//
|
||
//
|
||
// Loop to allocate block
|
||
//
|
||
for(i = 0; i < heapln; i += HP_SIZE(*HPTR(i))) {
|
||
//
|
||
// If free block found (hp_flag=0 indicates free),
|
||
//
|
||
if(HP_FLAG(*HPTR(i)) == 0) {
|
||
//
|
||
// A free block was found.
|
||
// At this point, check to see if the current block can be
|
||
// coalesced with the next block. We start with the offset of
|
||
// the current block.
|
||
|
||
nexti = i;
|
||
|
||
//
|
||
// Add to it the size of the next consecutive
|
||
// free blocks until we reach the end of the heap, or an
|
||
// allocated block is found.
|
||
//
|
||
while( (nexti < heapln) && (HP_FLAG(*HPTR(nexti))==0) ) {
|
||
nexti += HP_SIZE(*HPTR(nexti));
|
||
}
|
||
|
||
//
|
||
// Coalesce blocks all free blocks found thus far
|
||
//
|
||
HP_SIZE(*HPTR(i)) = nexti - i;
|
||
|
||
//
|
||
// At this point, attempt to allocate from the current
|
||
// free block. The current free block must be exactly
|
||
// the size we want or large enough to split, since we
|
||
// must return a block whose size is EXACTLY the size
|
||
// requested.
|
||
//
|
||
if(HP_SIZE(*HPTR(i)) == NumBytes) {
|
||
//
|
||
// Size is perfect
|
||
//
|
||
return(i);
|
||
}
|
||
|
||
if(HP_SIZE(*HPTR(i)) >= NumBytes + sizeof(HEAPHDR)) {
|
||
//
|
||
// If block is splittable, then get the index and size of
|
||
// the block that is left over after taking out what is
|
||
// needed from this allocate request.
|
||
//
|
||
newi = i + NumBytes;
|
||
numBytesNew = HP_SIZE(*HPTR(i)) - NumBytes;
|
||
|
||
//
|
||
// Create a header for the left-over block by marking
|
||
// it as free, and inserting the size.
|
||
//
|
||
HP_SIZE(*HPTR(newi)) = numBytesNew;
|
||
HP_FLAG(*HPTR(newi)) = 0;
|
||
|
||
//
|
||
// Update the header for the allocated block and
|
||
// return its index to the caller.
|
||
// NOTE: The caller is responsible for marking this block
|
||
// as allocated.
|
||
//
|
||
HP_SIZE(*HPTR(i)) = NumBytes;
|
||
return(i);
|
||
}
|
||
}
|
||
}
|
||
return(INULL); // Heap full
|
||
}
|
||
|