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`. More...

static bool	checkSize (size_t nBytes)
	Returns true iff allocate can be invoked with `nBytes`. More...

static void	cleanup ()
	Frees all allocated memory. More...

static void	deallocate (size_t nBytes, void *p)
	Deallocates memory at address `p` which is of size `nBytes`. More...

static void	deallocateList (size_t nBytes, void pHead, void pTail)
	Deallocate a complete list starting at `pHead` and ending at `pTail`. More...

static void	defrag ()
	Defragments the global free lists. More...

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

static size_t	memoryAllocatedInBlocks ()
	Returns the total amount of memory (in bytes) allocated from the system. More...

static size_t	memoryInGlobalFreeList ()
	Returns the total amount of memory (in bytes) available in the global free lists. More...

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

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. More...

static long long	s_globallyAllocatedBytes
	Holds the number of globally allocated bytes for debugging. More...

static thread_local long long	s_locallyAllocatedBytes
	Holds the number of thread-locally allocated bytes for debugging. More...

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. More...

static thread_local MemElemPtr	s_tp [TABLE_SIZE]
	Contains the allocated but free memory for a single thread. More...

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 58 of file PoolMemoryAllocator.h.

Member Typedef Documentation

◆ MemElemPtr

using ogdf::PoolMemoryAllocator::MemElemPtr = MemElem*

private

Definition at line 64 of file PoolMemoryAllocator.h.

Constructor & Destructor Documentation

◆ PoolMemoryAllocator()

ogdf::PoolMemoryAllocator::PoolMemoryAllocator ( )

inline

Definition at line 74 of file PoolMemoryAllocator.h.

◆ ~PoolMemoryAllocator()

ogdf::PoolMemoryAllocator::~PoolMemoryAllocator ( )

inline

Definition at line 76 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 )

static

Returns true iff allocate can be invoked with nBytes.

◆ 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 120 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 126 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 132 of file PoolMemoryAllocator.h.

◆ slicesPerBlock() [2/2]

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

inlinestaticprivate

Definition at line 137 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 71 of file PoolMemoryAllocator.h.

◆ MIN_BYTES

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

staticconstexprprivate

Definition at line 69 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 154 of file PoolMemoryAllocator.h.

◆ s_globallyAllocatedBytes

long long ogdf::PoolMemoryAllocator::s_globallyAllocatedBytes

staticprivate

Holds the number of globally allocated bytes for debugging.

Definition at line 158 of file PoolMemoryAllocator.h.

◆ s_locallyAllocatedBytes

thread_local long long ogdf::PoolMemoryAllocator::s_locallyAllocatedBytes

staticprivate

Holds the number of thread-locally allocated bytes for debugging.

Definition at line 160 of file PoolMemoryAllocator.h.

◆ s_mutex

std::mutex ogdf::PoolMemoryAllocator::s_mutex

staticprivate

Definition at line 166 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 151 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 168 of file PoolMemoryAllocator.h.

◆ TABLE_SIZE

constexpr size_t ogdf::PoolMemoryAllocator::TABLE_SIZE = 256

staticconstexprprivate

Definition at line 70 of file PoolMemoryAllocator.h.

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

include/ogdf/basic/memory/PoolMemoryAllocator.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Static Public Member Functions

Private Types

Static Private Member Functions

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ MemElemPtr

Constructor & Destructor Documentation

◆ PoolMemoryAllocator()

◆ ~PoolMemoryAllocator()

Member Function Documentation

◆ allocate()

◆ allocateBlock()

◆ checkSize()

◆ cleanup()

◆ deallocate()

◆ deallocateList()

◆ defrag()

◆ enterCS()

◆ fillPool()

◆ flushPool()

◆ leaveCS()

◆ makeSlices()

◆ memoryAllocatedInBlocks()

◆ memoryInGlobalFreeList()

◆ memoryInThreadFreeList()

◆ slicesPerBlock() [1/2]

◆ slicesPerBlock() [2/2]

◆ unguardedMemGlobalFreelist()

Member Data Documentation

◆ BLOCK_SIZE

◆ MIN_BYTES

◆ s_blocks

◆ s_globallyAllocatedBytes

◆ s_locallyAllocatedBytes

◆ s_mutex

◆ s_pool

◆ s_tp

◆ TABLE_SIZE

Open
Graph Drawing
Framework