lsa::CSmallAllocator Class Reference

Provide a more efficient way of handling allocations of small sizes. More...

#include <LSASmallAllocator.h>

List of all members.

Classes
struct	LSA_SMALL_ALLOC_BLOCKSET
Protected Types
typedef struct lsa::CSmallAllocator::LSA_SMALL_ALLOC_BLOCKSET *	LPLSA_SMALL_ALLOC_BLOCKSET
typedef struct lsa::CSmallAllocator::LSA_SMALL_ALLOC_BLOCKSET	LPCLSA_SMALL_ALLOC_BLOCKSET
Protected Member Functions
LSE_CALL	CSmallAllocator (LSVOID *_pvAddress, LSUINT32 _ui32Total256Blocks)
LSVOID LSE_CALL	Init (LSVOID *_pvAddress, LSUINT32 _ui32Total256Blocks)
LSVOID *LSE_CALL	Alloc (LSA_SIZE _sSize, LSUINT32 _ui32Align=(1UL<< 4UL))
LSBOOL LSE_CALL	Free (LSVOID *_pvAddr)
LSVOID *LSE_CALL	ReAlloc (LSVOID *_pvAddr, LSA_SIZE _sSize, LSA_SIZE &_sOldSize)
LSBOOL LSE_CALL	IsEmpty () const
LSVOID LSE_CALL	Trash ()
LSBOOL LSE_CALL	HaveAddress (const LSVOID *_pvAddr) const
Static Protected Member Functions
static LSA_SIZE LSE_CALL	GetWorkingSetSizeByNumberOf256Blocks (LSUINT32 _ui32Total256Blocks, const LSVOID *_pvAddress=NULL, LSA_SMALL_ALLOC_BLOCKSET *_psabBlocks=NULL)
static LSA_SIZE LSE_CALL	GetFullAllocatorSizeWithNumberOf256Blocks (LSVOID *_pvAddress, LSUINT32 _ui32Total256Blocks)
static LSUINT32 LSE_CALL	GetElementsFromBits (LSUINT32 _ui32Bits)
static LSUINT32 LSE_CALL	GetByteAndBitFromBit (const LSUINT32 &_ui32Bit, LSUINT32 &_ui32ReturnBit)
static LSUINT32 LSE_CALL	Find0Bit (LSA_SIZE _sValue)
static LSE_INLINE LSUINTPTR LSE_CALL	GetBlockOffset (LSUINT32 _ui32SetIndex, LSUINT32 _ui32BlockIndex)
Protected Attributes
CSmallAllocator *	m_psaNext
LSA_SMALL_ALLOC_BLOCKSET	m_pui8BlockStarts [(256/(1<< 4UL))]
LSA_SIZE	m_sLow
LSA_SIZE	m_sHi
Friends
class	CStdAllocator

---

Detailed Description

Provide a more efficient way of handling allocations of small sizes.

Class CSmallAllocator Description: Similar to CStdAllocatorHeap in purpose, but this manages only small allocations (256 bytes and below). In CStdAllocatorHeap, every allocation, no matter how small, causes 16 extra bytes to be allocated as overhead for record keeping. Because the allocations can be of variable sizes, values must be stored to indicate the size of each block. Blocks can also be variable distances apart so linked-list pointers must be inserted. In debug mode, 32 additional bytes are allocated for each allocation instead of 16. The CSmallAllocator handles small allocations separately to avoid all this needless overhead and not only improves allocation/deallocation speed but also improves RAM efficiency. This is done by organizing the blocks into fixed-sized rows. The sizes of the blocks are known already so we do not need to store this information. The blocks are stacked and are fixed in size so we know where each block is. A simple bit array tells us if a block is allocated or not. Deallocation is exceptionally fast since we only need to take the address of the block minus the start of the blocks to get a bit index, then switch that bit to 0. Searching for free blocks is also fast because a search over the bit array can check 32 blocks at once. When an array of 32 bits is found where not all bits are set to 1, a binary bit scan finds a free block.

---

Member Typedef Documentation

typedef struct lsa::CSmallAllocator::LSA_SMALL_ALLOC_BLOCKSET * lsa::CSmallAllocator::LPLSA_SMALL_ALLOC_BLOCKSET [protected]

The bocks are stored as a pointer to the free/used key bits followed by a pointer to the first block in the set.

---

Member Function Documentation

LSVOID* LSE_CALL lsa::CSmallAllocator::Alloc	(	LSA_SIZE	_sSize,
		LSUINT32	_ui32Align = (1UL<< 4UL)
	)		[protected]

Allocate a number of bytes. Returns the allocated address or NULL on error. There is no debug information to store.

Parameters:

_sSize	Size of the requested allocation.
_ui32Align	Requested alignment in bytes.

Returns:

Returns the allocated address or NULL on error.

static LSUINT32 LSE_CALL lsa::CSmallAllocator::Find0Bit

(

LSA_SIZE

_sValue

)

[static, protected]

Perform a binary search for a bit set to 0.

Parameters:

_sValue

The value to search for a 0 bit.

Returns:

Returns the first-found 0 bit. There must be at least 1 0 bit in the value.

LSBOOL LSE_CALL lsa::CSmallAllocator::Free

(

LSVOID *

_pvAddr

)

[protected]

Free an address.

Parameters:

_pvAddr

Address to free.

Returns:

Returns true if the address was freed. Returns false if the given address was not allocated by this object.

LSE_INLINE LSUINTPTR LSE_CALL lsa::CSmallAllocator::GetBlockOffset	(	LSUINT32	_ui32SetIndex,
		LSUINT32	_ui32BlockIndex
	)		[static, protected]

Get the offset from the base of a block set where the block set and block are given as indices.

Parameters:

_ui32SetIndex	Block set index.
_ui32BlockIndex	Block index.

Returns:

Returns the offset from the start of the block set where the given block can be found.

static LSUINT32 LSE_CALL lsa::CSmallAllocator::GetByteAndBitFromBit	(	const LSUINT32 &	_ui32Bit,
		LSUINT32 &	_ui32ReturnBit
	)		[static, protected]

Given a bit index into the bit array used for book keeping, return a byte and bit index.

Parameters:

_ui32Bit	Bit to be converted to a byte and bit combination.
_ui32ReturnBit	Bit part of the returned index.

Returns:

Returns the byte part of the index.

static LSUINT32 LSE_CALL lsa::CSmallAllocator::GetElementsFromBits

(

LSUINT32

_ui32Bits

)

[static, protected]

Get the number of LSA_SIZE objects needed to hold the number of bits given for use as book keeping.

Parameters:

_ui32Bits

Number of bits to convert

Returns:

Returns the number of LSA_SIZE objects needed to hold the number of bits given.

static LSA_SIZE LSE_CALL lsa::CSmallAllocator::GetFullAllocatorSizeWithNumberOf256Blocks	(	LSVOID *	_pvAddress,
		LSUINT32	_ui32Total256Blocks
	)		[static, protected]

Get the full size of a CSmallAllocator object if applied at a given address.

Parameters:

_pvAddress	The address assumed as the address where a CSmallAllocator object will be applied.
_ui32Total256Blocks	Total number of 256-byte-sized blocks to use as a guideline for calculating the size of the full working set.

Returns:

The full size of the object if used at the given address.

static LSA_SIZE LSE_CALL lsa::CSmallAllocator::GetWorkingSetSizeByNumberOf256Blocks	(	LSUINT32	_ui32Total256Blocks,
		const LSVOID *	_pvAddress = NULL,
		LSA_SMALL_ALLOC_BLOCKSET *	_psabBlocks = NULL
	)		[static, protected]

Given the number of 256-sized blocks desired, determine how much RAM will be needed to allow us to work with a set where each smaller block set consumes the same or less RAM as the 256-sized block set. In other words, if 16 256-sized blocks are given, the total size for that set will be 4,096 bytes (not including the 16 bits for record-keeping). Then, 256 16-byte blocks will be created, 128 32-byte blocks, 85 48-byte blocks, etc. The sum of all of these blocks, including the sizes of the bits needed for record keeping, is returned.

Parameters:

_ui32Total256Blocks	Total number of 256-byte-sized blocks to consider as a guideline for the rest of the working set.
_pvAddress	If not NULL, this is the address where the working set should be applied.
_psabBlocks	If not NULL, the pointers in the given LSA_SMALL_ALLOC_BLOCKSET objects are set while the size is being calculated.

Returns:

Total RAM consumed for the whole working set assuming a starting address aligned on a 16-byte boundary.

LSE_INLINE LSBOOL LSE_CALL lsa::CSmallAllocator::HaveAddress

(

const LSVOID *

_pvAddr

)

const [protected]

Is the given address in range of our heap?

Parameters:

_pvAddr

The address to check for being within our working set.

Returns:

Returns true if the address is in range of our working set.

LSVOID LSE_CALL lsa::CSmallAllocator::Init	(	LSVOID *	_pvAddress,
		LSUINT32	_ui32Total256Blocks
	)		[protected]

Initialize this object at a given location.

Parameters:

_pvAddress	Address of the working set to use.
_ui32Total256Blocks	Total number of 256-byte-sized blocks to use in the working set.

LSBOOL LSE_CALL lsa::CSmallAllocator::IsEmpty

(

)

const [protected]

Determine if this heap is empty (no allocations remain).

Returns:

Returns true is their are no allocations resident in this heap.

LSVOID* LSE_CALL lsa::CSmallAllocator::ReAlloc	(	LSVOID *	_pvAddr,
		LSA_SIZE	_sSize,
		LSA_SIZE &	_sOldSize
	)		[protected]

Reallocate a given address.

Parameters:

_pvAddr	The address to reallocate. If NULL, this behaves the same way as Alloc().
_sSize	The new size of the item to allocate.
_sOldSize	If reallocation failed but the address is valid within our working set, this receives the size of the data. Only valid if this function returns NULL.

Returns:

Returns the new address of the item or NULL if none could be allocated. If failure is caused by a reason other than the given address not being part of our working set, _sOldSize is filled with the size of the data at the given address. This allows the managing class to move the correct amount of data from the given address to the new address after it handles the reallocation itself.

LSVOID LSE_CALL lsa::CSmallAllocator::Trash

(

)

[protected]

Trash all data. The contents of the heap are completely reset and all allocations are lost.

---

The documentation for this class was generated from the following file:

• F:/My Projects/LSEngine/Modules/LSMemLib/Src/Allocators/LSASmallAllocator.h