KiCad PCB EDA Suite
cached_container.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright 2013-2017 CERN
5 * Copyright (C) 2020-2021 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Maciej Suminski <[email protected]>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, you may find one here:
21 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22 * or you may search the http://www.gnu.org website for the version 2 license,
23 * or you may write to the Free Software Foundation, Inc.,
24 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 */
26
37#include <gal/opengl/utils.h>
38
39#include <list>
40#include <algorithm>
41#include <cassert>
42
43#ifdef KICAD_GAL_PROFILE
44#include <wx/log.h>
45#include <profile.h>
46#endif /* KICAD_GAL_PROFILE */
47
48using namespace KIGFX;
49
50CACHED_CONTAINER::CACHED_CONTAINER( unsigned int aSize ) :
51 VERTEX_CONTAINER( aSize ),
52 m_item( nullptr ),
53 m_chunkSize( 0 ),
54 m_chunkOffset( 0 ),
55 m_maxIndex( 0 )
56{
57 // In the beginning there is only free space
58 m_freeChunks.insert( std::make_pair( aSize, 0 ) );
59}
60
61
63{
64 assert( aItem != nullptr );
65
66 unsigned int itemSize = aItem->GetSize();
67 m_item = aItem;
68 m_chunkSize = itemSize;
69
70 // Get the previously set offset if the item was stored previously
71 m_chunkOffset = itemSize > 0 ? aItem->GetOffset() : -1;
72}
73
74
76{
77 assert( m_item != nullptr );
78
79 unsigned int itemSize = m_item->GetSize();
80
81 // Finishing the previously edited item
82 if( itemSize < m_chunkSize )
83 {
84 // There is some not used but reserved memory left, so we should return it to the pool
85 int itemOffset = m_item->GetOffset();
86
87 // Add the not used memory back to the pool
88 addFreeChunk( itemOffset + itemSize, m_chunkSize - itemSize );
89 // mergeFreeChunks(); // veery slow and buggy
90
91 m_maxIndex = std::max( itemOffset + itemSize, m_maxIndex );
92 }
93
94 if( itemSize > 0 )
95 m_items.insert( m_item );
96
97 m_item = nullptr;
98 m_chunkSize = 0;
99 m_chunkOffset = 0;
100
101#if CACHED_CONTAINER_TEST > 1
102 test();
103#endif
104}
105
106
107VERTEX* CACHED_CONTAINER::Allocate( unsigned int aSize )
108{
109 assert( m_item != nullptr );
110 assert( IsMapped() );
111
112 if( m_failed )
113 return nullptr;
114
115 unsigned int itemSize = m_item->GetSize();
116 unsigned int newSize = itemSize + aSize;
117
118 if( newSize > m_chunkSize )
119 {
120 // There is not enough space in the currently reserved chunk, so we have to resize it
121 if( !reallocate( newSize ) )
122 {
123 m_failed = true;
124 return nullptr;
125 }
126 }
127
128 VERTEX* reserved = &m_vertices[m_chunkOffset + itemSize];
129
130 // Now the item officially possesses the memory chunk
131 m_item->setSize( newSize );
132
133 // The content has to be updated
134 m_dirty = true;
135
136#if CACHED_CONTAINER_TEST > 0
137 test();
138#endif
139#if CACHED_CONTAINER_TEST > 2
142#endif
143
144 return reserved;
145}
146
147
149{
150 assert( aItem != nullptr );
151 assert( m_items.find( aItem ) != m_items.end() || aItem->GetSize() == 0 );
152
153 int size = aItem->GetSize();
154
155 if( size == 0 )
156 return; // Item is not stored here
157
158 int offset = aItem->GetOffset();
159
160 // Insert a free memory chunk entry in the place where item was stored
161 addFreeChunk( offset, size );
162
163 // Indicate that the item is not stored in the container anymore
164 aItem->setSize( 0 );
165
166 m_items.erase( aItem );
167
168#if CACHED_CONTAINER_TEST > 0
169 test();
170#endif
171
172 // This dynamic memory freeing optimize memory usage, but in fact can create
173 // out of memory issues because freeing and reallocation large chunks of memory
174 // can create memory fragmentation and no room to reallocate large chunks
175 // after many free/reallocate cycles during a session using the same complex board
176 // So it can be disable.
177 // Currently: it is disable to avoid "out of memory" issues
178#if 0
179 // Dynamic memory freeing, there is no point in holding
180 // a large amount of memory when there is no use for it
182 {
184 }
185#endif
186}
187
188
190{
192 m_maxIndex = 0;
193 m_failed = false;
194
195 // Set the size of all the stored VERTEX_ITEMs to 0, so it is clear that they are not held
196 // in the container anymore
197 for( ITEMS::iterator it = m_items.begin(); it != m_items.end(); ++it )
198 ( *it )->setSize( 0 );
199
200 m_items.clear();
201
202 // Now there is only free space left
203 m_freeChunks.clear();
204 m_freeChunks.insert( std::make_pair( m_freeSpace, 0 ) );
205}
206
207
208bool CACHED_CONTAINER::reallocate( unsigned int aSize )
209{
210 assert( aSize > 0 );
211 assert( IsMapped() );
212
213 unsigned int itemSize = m_item->GetSize();
214
215 // Find a free space chunk >= aSize
216 FREE_CHUNK_MAP::iterator newChunk = m_freeChunks.lower_bound( aSize );
217
218 // Is there enough space to store vertices?
219 if( newChunk == m_freeChunks.end() )
220 {
221 bool result;
222
223 // Would it be enough to double the current space?
224 if( aSize < m_freeSpace + m_currentSize )
225 {
226 // Yes: exponential growing
227 result = defragmentResize( m_currentSize * 2 );
228 }
229 else
230 {
231 // No: grow to the nearest greater power of 2
232 result = defragmentResize( pow( 2, ceil( log2( m_currentSize * 2 + aSize ) ) ) );
233 }
234
235 if( !result )
236 return false;
237
238 newChunk = m_freeChunks.lower_bound( aSize );
239 assert( newChunk != m_freeChunks.end() );
240 }
241
242 // Parameters of the allocated chunk
243 unsigned int newChunkSize = getChunkSize( *newChunk );
244 unsigned int newChunkOffset = getChunkOffset( *newChunk );
245
246 assert( newChunkSize >= aSize );
247 assert( newChunkOffset < m_currentSize );
248
249 // Check if the item was previously stored in the container
250 if( itemSize > 0 )
251 {
252 // The item was reallocated, so we have to copy all the old data to the new place
253 memcpy( &m_vertices[newChunkOffset], &m_vertices[m_chunkOffset], itemSize * VERTEX_SIZE );
254
255 // Free the space used by the previous chunk
257 }
258
259 // Remove the new allocated chunk from the free space pool
260 m_freeChunks.erase( newChunk );
261 m_freeSpace -= newChunkSize;
262
263 m_chunkSize = newChunkSize;
264 m_chunkOffset = newChunkOffset;
265
267
268 return true;
269}
270
271
273{
274 // Defragmentation
275 ITEMS::iterator it, it_end;
276 int newOffset = 0;
277
278 for( VERTEX_ITEM* item : m_items )
279 {
280 int itemOffset = item->GetOffset();
281 int itemSize = item->GetSize();
282
283 // Move an item to the new container
284 memcpy( &aTarget[newOffset], &m_vertices[itemOffset], itemSize * VERTEX_SIZE );
285
286 // Update new offset
287 item->setOffset( newOffset );
288
289 // Move to the next free space
290 newOffset += itemSize;
291 }
292
293 // Move the current item and place it at the end
294 if( m_item->GetSize() > 0 )
295 {
296 memcpy( &aTarget[newOffset], &m_vertices[m_item->GetOffset()],
298 m_item->setOffset( newOffset );
299 m_chunkOffset = newOffset;
300 }
301
303}
304
305
307{
308 if( m_freeChunks.size() <= 1 ) // There are no chunks that can be merged
309 return;
310
311#ifdef KICAD_GAL_PROFILE
312 PROF_COUNTER totalTime;
313#endif /* KICAD_GAL_PROFILE */
314
315 // Reversed free chunks map - this one stores chunk size with its offset as the key
316 std::list<CHUNK> freeChunks;
317
318 FREE_CHUNK_MAP::const_iterator it, it_end;
319
320 for( it = m_freeChunks.begin(), it_end = m_freeChunks.end(); it != it_end; ++it )
321 {
322 freeChunks.emplace_back( it->second, it->first );
323 }
324
325 m_freeChunks.clear();
326 freeChunks.sort();
327
328 std::list<CHUNK>::const_iterator itf, itf_end;
329 unsigned int offset = freeChunks.front().first;
330 unsigned int size = freeChunks.front().second;
331 freeChunks.pop_front();
332
333 for( itf = freeChunks.begin(), itf_end = freeChunks.end(); itf != itf_end; ++itf )
334 {
335 if( itf->first == offset + size )
336 {
337 // These chunks can be merged, so just increase the current chunk size and go on
338 size += itf->second;
339 }
340 else
341 {
342 // These chunks cannot be merged
343 // So store the previous one
344 m_freeChunks.insert( std::make_pair( size, offset ) );
345 // and let's check the next chunk
346 offset = itf->first;
347 size = itf->second;
348 }
349 }
350
351 // Add the last one
352 m_freeChunks.insert( std::make_pair( size, offset ) );
353
354#if CACHED_CONTAINER_TEST > 0
355 test();
356#endif
357}
358
359
360void CACHED_CONTAINER::addFreeChunk( unsigned int aOffset, unsigned int aSize )
361{
362 assert( aOffset + aSize <= m_currentSize );
363 assert( aSize > 0 );
364
365 m_freeChunks.insert( std::make_pair( aSize, aOffset ) );
366 m_freeSpace += aSize;
367}
368
369
371{
372}
373
374
376{
377}
378
379
381{
382#ifdef KICAD_GAL_PROFILE
383 // Free space check
384 unsigned int freeSpace = 0;
385 FREE_CHUNK_MAP::iterator itf;
386
387 for( itf = m_freeChunks.begin(); itf != m_freeChunks.end(); ++itf )
388 freeSpace += getChunkSize( *itf );
389
390 assert( freeSpace == m_freeSpace );
391
392 // Used space check
393 unsigned int used_space = 0;
394 ITEMS::iterator itr;
395
396 for( itr = m_items.begin(); itr != m_items.end(); ++itr )
397 used_space += ( *itr )->GetSize();
398
399 // If we have a chunk assigned, then there must be an item edited
400 assert( m_chunkSize == 0 || m_item );
401
402 // Currently reserved chunk is also counted as used
403 used_space += m_chunkSize;
404
405 assert( ( m_freeSpace + used_space ) == m_currentSize );
406
407 // Overlapping check TODO
408#endif /* KICAD_GAL_PROFILE */
409}
unsigned int m_chunkOffset
Maximal vertex index number stored in the container.
void addFreeChunk(unsigned int aOffset, unsigned int aSize)
Add a chunk marked as a free space.
int getChunkSize(const CHUNK &aChunk) const
Return the size of a chunk.
void mergeFreeChunks()
Look for consecutive free memory chunks and merges them, decreasing fragmentation of memory.
void showFreeChunks()
Debug & test functions.
VERTEX_ITEM * m_item
Properties of currently modified chunk & item.
FREE_CHUNK_MAP m_freeChunks
Stored VERTEX_ITEMs.
void defragment(VERTEX *aTarget)
Transfer all stored data to a new buffer, removing empty spaces between the data chunks in the contai...
virtual void FinishItem() override
Clean up after adding an item.
virtual void Delete(VERTEX_ITEM *aItem) override
Remove all data stored in the container and restores its original state.
unsigned int getChunkOffset(const CHUNK &aChunk) const
Return the offset of a chunk.
virtual VERTEX * Allocate(unsigned int aSize) override
Return allocated space for the requested number of vertices associated with the current item (set wit...
virtual void Clear() override
Remove all data stored in the container and restores its original state.
virtual bool defragmentResize(unsigned int aNewSize)=0
Remove empty spaces between chunks and optionally resizes the container.
virtual void SetItem(VERTEX_ITEM *aItem) override
Clean up after adding an item.
virtual bool IsMapped() const =0
Return true if vertex buffer is currently mapped.
ITEMS m_items
Currently modified item.
bool reallocate(unsigned int aSize)
Resize the chunk that stores the current item to the given size.
unsigned int m_initialSize
Actual storage memory.
unsigned int m_currentSize
Store the initial size, so it can be resized to this on Clear()
unsigned int m_freeSpace
Current container size, expressed in vertices.
unsigned int usedSpace() const
Return size of the used memory space.
bool m_dirty
Default initial size of a container (expressed in vertices)
void setSize(unsigned int aSize)
Set data size in the container.
Definition: vertex_item.h:94
void setOffset(unsigned int aOffset)
Set data offset in the container.
Definition: vertex_item.h:84
unsigned int GetOffset() const
Return data offset in the container.
Definition: vertex_item.h:68
unsigned int GetSize() const
Return information about number of vertices stored.
Definition: vertex_item.h:58
A thread-safe event counter.
Definition: profile.h:226
The Cairo implementation of the graphics abstraction layer.
Definition: color4d.cpp:243
static constexpr size_t VERTEX_SIZE
Definition: vertex_common.h:67
Class to handle an item held in a container.