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 
36 #include <gal/opengl/vertex_item.h>
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 
48 using namespace KIGFX;
49 
50 CACHED_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 
107 VERTEX* 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
140  showFreeChunks();
141  showUsedChunks();
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
181  if( m_freeSpace > ( 0.75 * m_currentSize ) && m_currentSize > m_initialSize )
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 
208 bool 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()],
297  m_item->GetSize() * VERTEX_SIZE );
298  m_item->setOffset( newOffset );
299  m_chunkOffset = newOffset;
300  }
301 
302  m_maxIndex = usedSpace();
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 
360 void 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_initialSize
Actual storage memory.
void showFreeChunks()
Debug & test functions.
void addFreeChunk(unsigned int aOffset, unsigned int aSize)
Add a chunk marked as a free space.
The Cairo implementation of the graphics abstraction layer.
Definition: color4d.cpp:236
unsigned int GetSize() const
Return information about number of vertices stored.
Definition: vertex_item.h:58
unsigned int getChunkOffset(const CHUNK &aChunk) const
Return the offset of a chunk.
void defragment(VERTEX *aTarget)
Transfer all stored data to a new buffer, removing empty spaces between the data chunks in the contai...
unsigned int m_currentSize
Store the initial size, so it can be resized to this on Clear()
A small class to help profiling.
Definition: profile.h:45
virtual void SetItem(VERTEX_ITEM *aItem) override
Clean up after adding an item.
void setSize(unsigned int aSize)
Set data size in the container.
Definition: vertex_item.h:94
ITEMS m_items
Currently modified item.
VERTEX_ITEM * m_item
Properties of currently modified chunk & item.
virtual void FinishItem() override
Clean up after adding an item.
unsigned int m_freeSpace
Current container size, expressed in vertices.
int getChunkSize(const CHUNK &aChunk) const
Return the size of a chunk.
void setOffset(unsigned int aOffset)
Set data offset in the container.
Definition: vertex_item.h:84
void mergeFreeChunks()
Look for consecutive free memory chunks and merges them, decreasing fragmentation of memory.
virtual void Clear() override
Remove all data stored in the container and restores its original state.
virtual VERTEX * Allocate(unsigned int aSize) override
Return allocated space for the requested number of vertices associated with the current item (set wit...
FREE_CHUNK_MAP m_freeChunks
Stored VERTEX_ITEMs.
CACHED_CONTAINER(unsigned int aSize=DEFAULT_SIZE)
bool reallocate(unsigned int aSize)
Resize the chunk that stores the current item to the given size.
bool m_dirty
Default initial size of a container (expressed in vertices)
unsigned int usedSpace() const
Return size of the used memory space.
Class to handle an item held in a container.
static constexpr size_t VERTEX_SIZE
Definition: vertex_common.h:67
unsigned int GetOffset() const
Return data offset in the container.
Definition: vertex_item.h:68
virtual bool IsMapped() const =0
Return true if vertex buffer is currently mapped.
unsigned int m_chunkOffset
Maximal vertex index number stored in the container.
virtual void Delete(VERTEX_ITEM *aItem) 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.