1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
/*
* $Revision: 2523 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
***************************************************************/
/** \file
* \brief Declaration of memory manager for allocating small
* pieces of memory
*
* \author Carsten Gutwenger
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)<br>
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#ifdef _MSC_VER
#pragma once
#endif
#ifndef OGDF_POOL_MEMORY_ALLOCATOR_H
#define OGDF_POOL_MEMORY_ALLOCATOR_H
#ifndef OGDF_MEMORY_POOL_NTS
#include "../../basic/CriticalSection.h"
#else
#include "../../basic/System.h"
#endif
namespace ogdf {
//! The class \a PoolAllocator represents ogdf's pool memory allocator.
/**
* <H3>Usage:</H3>
*
* Adding the macro \c #OGDF_NEW_DELETE in a class declaration overloads
* new and delete operators of that class such that they use this
* memory allocator. This is useful if the size of a class is less than
* \c PoolAllocator::eTableSize bytes.
*
* Another benefit from the OGDF memory-manager is that it throws an
* InsufficientMemoryException if no more memory is available. Hence
* it is legal to omit checking if new returned 0 as long as stack-
* unwinding frees all memory allocated so far.
* It is also possible to make the usual \c new operator behave the same
* way (throwing an InsufficientMemoryException) by defining the
* macro \c #OGDF_MALLOC_NEW_DELETE in a class declaration.
*/
class PoolMemoryAllocator
{
struct MemElem {
MemElem *m_next;
};
struct MemElemEx {
MemElemEx *m_next;
MemElemEx *m_down;
};
typedef MemElem *MemElemPtr;
typedef MemElemEx *MemElemExPtr;
struct PoolVector;
struct PoolElement;
struct BlockChain;
typedef BlockChain *BlockChainPtr;
public:
enum {
eMinBytes = sizeof(MemElemPtr),
eTableSize = 256,
eBlockSize = 8192,
ePoolVectorLength = 15
};
PoolMemoryAllocator() { }
~PoolMemoryAllocator() { }
//! Initializes the memory manager.
static OGDF_EXPORT void init();
static OGDF_EXPORT void initThread();
//! Frees all memory blocks allocated by the memory manager.
static OGDF_EXPORT void cleanup();
static OGDF_EXPORT bool checkSize(size_t nBytes);
//! Allocates memory of size \a nBytes.
static OGDF_EXPORT void *allocate(size_t nBytes);
//! Deallocates memory at address \a p which is of size \a nBytes.
static OGDF_EXPORT void deallocate(size_t nBytes, void *p);
//! Deallocate a complete list starting at \a pHead and ending at \a pTail.
/**
* The elements are assumed to be chained using the first word of each element and
* elements are of size \a nBytes. This is much more efficient the deallocating
* each element separately, since the whole chain can be concatenated with the
* free list, requiring only constant effort.
*/
static OGDF_EXPORT void deallocateList(size_t nBytes, void *pHead, void *pTail);
static OGDF_EXPORT void flushPool();
static OGDF_EXPORT void flushPool(__uint16 nBytes);
//! Returns the total amount of memory (in bytes) allocated from the system.
static OGDF_EXPORT size_t memoryAllocatedInBlocks();
//! Returns the total amount of memory (in bytes) available in the global free lists.
static OGDF_EXPORT size_t memoryInGlobalFreeList();
//! Returns the total amount of memory (in bytes) available in the thread's free lists.
static OGDF_EXPORT size_t memoryInThreadFreeList();
private:
static int slicesPerBlock(__uint16 nBytes) {
int nWords;
return slicesPerBlock(nBytes,nWords);
}
static int slicesPerBlock(__uint16 nBytes, int &nWords) {
nWords = (nBytes+sizeof(MemElemPtr)-1)/sizeof(MemElemPtr);
return (eBlockSize-sizeof(MemElemPtr))/(nWords*sizeof(MemElemPtr));
}
static void incVectorSlot(PoolElement &pe);
static void flushPoolSmall(__uint16 nBytes);
static MemElemExPtr collectGroups(
__uint16 nBytes,
MemElemPtr &pRestHead,
MemElemPtr &pRestTail,
int &nRest);
static void *fillPool(MemElemPtr &pFreeBytes, __uint16 nBytes);
static MemElemPtr allocateBlock(__uint16 nBytes);
static PoolElement s_pool[eTableSize];
static MemElemPtr s_freeVectors;
static BlockChainPtr s_blocks;
#ifdef OGDF_MEMORY_POOL_NTS
static MemElemPtr s_tp[eTableSize];
#elif defined(OGDF_NO_COMPILER_TLS)
static CriticalSection *s_criticalSection;
static pthread_key_t s_tpKey;
#else
static CriticalSection *s_criticalSection;
static OGDF_DECL_THREAD MemElemPtr s_tp[eTableSize];
#endif
};
}
#endif
|
