ogdf::PoolMemoryAllocator Class Reference

Allocates memory in large chunks for better runtime. More...

#include <ogdf/basic/memory/PoolMemoryAllocator.h>

Classes
struct	MemElem
	Basic memory element used to realize a linked list of deallocated memory segments. More...

Public Member Functions
	PoolMemoryAllocator ()
	~PoolMemoryAllocator ()

Static Public Member Functions
static void *	allocate (size_t nBytes)
	Allocates memory of size nBytes.
static bool	checkSize (size_t nBytes)
	Returns true iff allocate can be invoked with nBytes.
static void	cleanup ()
	Frees all allocated memory.
static void	deallocate (size_t nBytes, void *p)
	Deallocates memory at address p which is of size nBytes.
static void	deallocateList (size_t nBytes, void *pHead, void *pTail)
	Deallocate a complete list starting at pHead and ending at pTail.
static void	defrag ()
	Defragments the global free lists.
static void	flushPool ()
	Flushes all free but allocated bytes (s_tp) to the thread-global list (s_pool) of allocated bytes.
static size_t	memoryAllocatedInBlocks ()
	Returns the total amount of memory (in bytes) allocated from the system.
static size_t	memoryInGlobalFreeList ()
	Returns the total amount of memory (in bytes) available in the global free lists.
static size_t	memoryInThreadFreeList ()
	Returns the total amount of memory (in bytes) available in the thread's free lists.

Private Types
using	MemElemPtr = MemElem *

Static Private Member Functions
static MemElemPtr	allocateBlock ()
static void	enterCS ()
static void *	fillPool (MemElemPtr &pFreeBytes, uint16_t nBytes)
static void	leaveCS ()
static void	makeSlices (MemElemPtr p, int nWords, int nSlices)
static int	slicesPerBlock (uint16_t nBytes)
static int	slicesPerBlock (uint16_t nBytes, int &nWords)
static size_t	unguardedMemGlobalFreelist ()

Static Private Attributes
static constexpr size_t	BLOCK_SIZE = 8192
static constexpr size_t	MIN_BYTES = sizeof(MemElemPtr)
static BlockChain *	s_blocks
	Holds all allocated memory independently of whether it is cleared in chunks of size BLOCK_SIZE.
static std::mutex	s_mutex
static PoolElement	s_pool [TABLE_SIZE]
	Contains allocated but free memory that may be used by all threads. Filled upon exiting a thread that allocated memory that was later freed.
static thread_local MemElemPtr	s_tp [TABLE_SIZE]
	Contains the allocated but free memory for a single thread.
static constexpr size_t	TABLE_SIZE = 256

Detailed Description

Allocates memory in large chunks for better runtime.

Possibly allocates more memory than required. Newly allocated chunks contain BLOCK_SIZE many bytes. Can allocate at most TABLE_SIZE bytes per invocation of allocate.

For each requested memory segment of n bytes, OGDF_POINTER_SIZE bytes are allocated in addition to store a pointer to another segment of memory.

This allows to store memory that is requested to be deallocated in a single linked list, and re-distribute it upon later allocation requests, instead of actually decallocating it.

Definition at line 55 of file PoolMemoryAllocator.h.

Member Typedef Documentation

MemElemPtr

using ogdf::PoolMemoryAllocator::MemElemPtr = MemElem*

private

Definition at line 61 of file PoolMemoryAllocator.h.

Constructor & Destructor Documentation

PoolMemoryAllocator()

ogdf::PoolMemoryAllocator::PoolMemoryAllocator ( )

inline

Definition at line 71 of file PoolMemoryAllocator.h.

~PoolMemoryAllocator()

ogdf::PoolMemoryAllocator::~PoolMemoryAllocator ( )

inline

Definition at line 73 of file PoolMemoryAllocator.h.

Member Function Documentation

allocate()

static void * ogdf::PoolMemoryAllocator::allocate ( size_t  nBytes )

static

Allocates memory of size nBytes.

allocateBlock()

static MemElemPtr ogdf::PoolMemoryAllocator::allocateBlock ( )

staticprivate

checkSize()

static bool ogdf::PoolMemoryAllocator::checkSize ( size_t  nBytes )

inlinestatic

Returns true iff allocate can be invoked with nBytes.

Definition at line 79 of file PoolMemoryAllocator.h.

cleanup()

static void ogdf::PoolMemoryAllocator::cleanup ( )

static

Frees all allocated memory.

deallocate()

static void ogdf::PoolMemoryAllocator::deallocate ( size_t  nBytes, void *  p  )

static

Deallocates memory at address p which is of size nBytes.

deallocateList()

static void ogdf::PoolMemoryAllocator::deallocateList ( size_t  nBytes, void *  pHead, void *  pTail  )

static

Deallocate a complete list starting at pHead and ending at pTail.

The elements are assumed to be chained using the first word of each element and elements are of size nBytes. In contrasting to linear-time element-wise deallocation this method takes constant time.

defrag()

static void ogdf::PoolMemoryAllocator::defrag ( )

static

Defragments the global free lists.

This methods sorts the global free lists, so that successive elements come after each other. This can improve perfomance for data structure that allocate many elements from the pool like lists and graphs.

enterCS()

static void ogdf::PoolMemoryAllocator::enterCS ( )

inlinestaticprivate

Definition at line 117 of file PoolMemoryAllocator.h.

fillPool()

static void * ogdf::PoolMemoryAllocator::fillPool ( MemElemPtr &  pFreeBytes, uint16_t  nBytes  )

staticprivate

flushPool()

static void ogdf::PoolMemoryAllocator::flushPool ( )

static

Flushes all free but allocated bytes (s_tp) to the thread-global list (s_pool) of allocated bytes.

leaveCS()

static void ogdf::PoolMemoryAllocator::leaveCS ( )

inlinestaticprivate

Definition at line 123 of file PoolMemoryAllocator.h.

makeSlices()

static void ogdf::PoolMemoryAllocator::makeSlices ( MemElemPtr  p, int  nWords, int  nSlices  )

staticprivate

memoryAllocatedInBlocks()

static size_t ogdf::PoolMemoryAllocator::memoryAllocatedInBlocks ( )

static

Returns the total amount of memory (in bytes) allocated from the system.

memoryInGlobalFreeList()

static size_t ogdf::PoolMemoryAllocator::memoryInGlobalFreeList ( )

static

Returns the total amount of memory (in bytes) available in the global free lists.

memoryInThreadFreeList()

static size_t ogdf::PoolMemoryAllocator::memoryInThreadFreeList ( )

static

Returns the total amount of memory (in bytes) available in the thread's free lists.

slicesPerBlock() [1/2]

static int ogdf::PoolMemoryAllocator::slicesPerBlock ( uint16_t  nBytes )

inlinestaticprivate

Definition at line 129 of file PoolMemoryAllocator.h.

slicesPerBlock() [2/2]

static int ogdf::PoolMemoryAllocator::slicesPerBlock ( uint16_t  nBytes, int &  nWords  )

inlinestaticprivate

Definition at line 134 of file PoolMemoryAllocator.h.

unguardedMemGlobalFreelist()

static size_t ogdf::PoolMemoryAllocator::unguardedMemGlobalFreelist ( )

staticprivate

Member Data Documentation

BLOCK_SIZE

constexpr size_t ogdf::PoolMemoryAllocator::BLOCK_SIZE = 8192

staticconstexprprivate

Definition at line 68 of file PoolMemoryAllocator.h.

MIN_BYTES

constexpr size_t ogdf::PoolMemoryAllocator::MIN_BYTES = sizeof(MemElemPtr)

staticconstexprprivate

Definition at line 66 of file PoolMemoryAllocator.h.

s_blocks

BlockChain* ogdf::PoolMemoryAllocator::s_blocks

staticprivate

Holds all allocated memory independently of whether it is cleared in chunks of size BLOCK_SIZE.

Definition at line 151 of file PoolMemoryAllocator.h.

s_mutex

std::mutex ogdf::PoolMemoryAllocator::s_mutex

staticprivate

Definition at line 163 of file PoolMemoryAllocator.h.

s_pool

PoolElement ogdf::PoolMemoryAllocator::s_pool[TABLE_SIZE]

staticprivate

Contains allocated but free memory that may be used by all threads. Filled upon exiting a thread that allocated memory that was later freed.

Definition at line 148 of file PoolMemoryAllocator.h.

s_tp

thread_local MemElemPtr ogdf::PoolMemoryAllocator::s_tp[TABLE_SIZE]

staticprivate

Contains the allocated but free memory for a single thread.

Definition at line 165 of file PoolMemoryAllocator.h.

TABLE_SIZE

constexpr size_t ogdf::PoolMemoryAllocator::TABLE_SIZE = 256

staticconstexprprivate

Definition at line 67 of file PoolMemoryAllocator.h.

---

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

• include/ogdf/basic/memory/PoolMemoryAllocator.h