Line data Source code
1 : /*
2 : * Copyright (c) 2010-2015: G-CSC, Goethe University Frankfurt
3 : * Author: Sebastian Reiter
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 : #include "small_object_allocator.h"
34 :
35 :
36 0 : FixedAllocator::
37 0 : FixedAllocator(std::size_t blockSize, unsigned char numBlocksPerChunk) :
38 0 : m_blockSize(blockSize),
39 0 : m_numBlocksPerChunk(numBlocksPerChunk),
40 0 : m_allocChunk(0),
41 0 : m_emptyChunkIndex(-1),
42 0 : m_deallocChunkIndex(-1),
43 0 : m_numFreeBlocks(0)
44 : {
45 0 : }
46 :
47 0 : void* FixedAllocator::
48 : allocate()
49 : {
50 0 : if(m_numFreeBlocks == 0){
51 : //m_chunks.reserve(m_chunks.size() + 1);
52 : Chunk newChunk;
53 0 : newChunk.init(m_blockSize, m_numBlocksPerChunk);
54 0 : m_chunks.push_back(newChunk);
55 0 : m_allocChunk = &m_chunks.back();
56 0 : m_deallocChunkIndex = m_chunks.size() - 1;
57 0 : m_numFreeBlocks += m_numBlocksPerChunk;
58 : }
59 0 : else if(m_allocChunk->m_numAvailableBlocks == 0)
60 : {
61 : Chunks::iterator iter = m_chunks.begin();
62 0 : for(;iter != m_chunks.end(); ++iter){
63 0 : if(iter->m_numAvailableBlocks > 0){
64 0 : m_allocChunk = &*iter;
65 0 : break;
66 : }
67 : }
68 : }
69 :
70 : assert(m_allocChunk != 0);
71 : assert(m_allocChunk->m_numAvailableBlocks > 0);
72 :
73 0 : --m_numFreeBlocks;
74 0 : return m_allocChunk->allocate(m_blockSize);;
75 : }
76 :
77 0 : void FixedAllocator::
78 : deallocate(void* p)
79 : {
80 : assert(m_deallocChunkIndex != -1);
81 :
82 0 : if(!pointer_is_in_chunk(p, &m_chunks[m_deallocChunkIndex]))
83 : {
84 : // find the chunk in which the pointer lies
85 0 : int iDown = (int)m_deallocChunkIndex - 1;
86 0 : std::size_t iUp = m_deallocChunkIndex + 1;
87 :
88 : for(;;){
89 0 : if(iDown >= 0){
90 0 : if(pointer_is_in_chunk(p, &m_chunks[iDown])){
91 0 : m_deallocChunkIndex = (std::size_t)iDown;
92 0 : break;
93 : }
94 0 : --iDown;
95 : }
96 :
97 0 : if(iUp < m_chunks.size()){
98 : if(pointer_is_in_chunk(p, &m_chunks[iUp])){
99 0 : m_deallocChunkIndex = iUp;
100 0 : break;
101 : }
102 0 : ++iUp;
103 : }
104 :
105 0 : if(iDown < 0 && iUp == m_chunks.size()){
106 : // this can only happen if the pointer was not allocated by
107 : // this instance of FixedAllocator.
108 0 : m_deallocChunkIndex = -1;
109 0 : break;
110 : }
111 : }
112 : }
113 :
114 : assert(m_deallocChunkIndex != -1);
115 :
116 0 : Chunk* deallocChunk = &m_chunks[m_deallocChunkIndex];
117 0 : deallocChunk->deallocate(p, m_blockSize);
118 0 : if(deallocChunk->m_numAvailableBlocks == m_numBlocksPerChunk){
119 : // the chunk is empty now. if we already have an empty chunk,
120 : // we'll erase it right away and set m_deallocChunk to the middle of
121 : // all chunks.
122 : // if not, we'll set m_emptyChunkIndex to m_deallocChunkIndex
123 0 : if(m_emptyChunkIndex == -1){
124 0 : m_emptyChunkIndex = m_deallocChunkIndex;
125 : }
126 : else{
127 : // swap deallocChunk with the last chunk and erase it afterwards.
128 0 : if(m_deallocChunkIndex != (int)m_chunks.size() - 1)
129 : {
130 0 : std::swap(m_chunks[m_deallocChunkIndex], m_chunks.back());
131 : }
132 0 : if(m_chunks.size() > 1){
133 0 : m_chunks[m_chunks.size() - 1].free();
134 0 : m_chunks.erase(m_chunks.begin() + (m_chunks.size() - 1));
135 0 : m_numFreeBlocks -= m_numBlocksPerChunk;
136 : }
137 :
138 : // find the new index for deallocChunk
139 0 : m_deallocChunkIndex = m_chunks.size() / 2;
140 : }
141 : }
142 0 : ++m_numFreeBlocks;
143 0 : }
144 :
145 :
146 0 : void FixedAllocator::Chunk::
147 : init(std::size_t blockSize, unsigned char numBlocks)
148 : {
149 0 : m_pData = new unsigned char[blockSize * numBlocks];
150 0 : m_firstAvailableBlock = 0;
151 0 : m_numAvailableBlocks = numBlocks;
152 :
153 : unsigned char* p = m_pData;
154 0 : for(unsigned char i = 0; i != numBlocks; p+=blockSize)
155 0 : *p = ++i;
156 0 : }
157 :
158 0 : void FixedAllocator::Chunk::
159 : free()
160 : {
161 0 : delete[] m_pData;
162 0 : }
163 :
164 0 : void* FixedAllocator::Chunk::
165 : allocate(std::size_t blockSize)
166 : {
167 : // if(!m_numAvailableBlocks)
168 : // return 0;
169 :
170 0 : unsigned char* pResult = m_pData + (m_firstAvailableBlock * blockSize);
171 0 : m_firstAvailableBlock = *pResult;
172 0 : --m_numAvailableBlocks;
173 :
174 0 : return pResult;
175 : }
176 :
177 0 : void FixedAllocator::Chunk::
178 : deallocate(void* p, std::size_t blockSize)
179 : {
180 : assert(p >= m_pData);
181 : unsigned char* toRelease = static_cast<unsigned char*>(p);
182 : assert((toRelease - m_pData) % blockSize == 0);
183 0 : *toRelease = m_firstAvailableBlock;
184 0 : m_firstAvailableBlock = static_cast<unsigned char>((toRelease - m_pData) / blockSize);
185 : assert(m_firstAvailableBlock == (toRelease - m_pData) / blockSize);
186 0 : ++m_numAvailableBlocks;
187 0 : }
|
