diff options
Diffstat (limited to 'common/gal/opengl/cached_container.cpp')
| -rw-r--r-- | common/gal/opengl/cached_container.cpp | 547 |
1 files changed, 547 insertions, 0 deletions
diff --git a/common/gal/opengl/cached_container.cpp b/common/gal/opengl/cached_container.cpp new file mode 100644 index 0000000..8cf3513 --- /dev/null +++ b/common/gal/opengl/cached_container.cpp @@ -0,0 +1,547 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Maciej Suminski <maciej.suminski@cern.ch> + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * 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. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +/** + * @file cached_container.cpp + * @brief Class to store instances of VERTEX with caching. It allows storing VERTEX objects and + * associates them with VERTEX_ITEMs. This leads to a possibility of caching vertices data in the + * GPU memory and a fast reuse of that data. + */ + +#include <gal/opengl/cached_container.h> +#include <gal/opengl/vertex_manager.h> +#include <gal/opengl/vertex_item.h> +#include <gal/opengl/shader.h> +#include <confirm.h> +#include <wx/log.h> +#include <list> +#ifdef __WXDEBUG__ +#include <profile.h> +#endif /* __WXDEBUG__ */ + +using namespace KIGFX; + +CACHED_CONTAINER::CACHED_CONTAINER( unsigned int aSize ) : + VERTEX_CONTAINER( aSize ), m_item( NULL ) +{ + // In the beginning there is only free space + m_freeChunks.insert( CHUNK( aSize, 0 ) ); + + // Do not have uninitialized members: + m_chunkSize = 0; + m_chunkOffset = 0; + m_itemSize = 0; +} + + +void CACHED_CONTAINER::SetItem( VERTEX_ITEM* aItem ) +{ + wxASSERT( aItem != NULL ); + + m_item = aItem; + m_itemSize = m_item->GetSize(); + m_chunkSize = m_itemSize; + + if( m_itemSize == 0 ) + m_items.insert( m_item ); // The item was not stored before + else + m_chunkOffset = m_item->GetOffset(); + +#if CACHED_CONTAINER_TEST > 1 + wxLogDebug( wxT( "Adding/editing item 0x%08lx (size %d)" ), (long) m_item, m_itemSize ); +#endif +} + + +void CACHED_CONTAINER::FinishItem() +{ + wxASSERT( m_item != NULL ); + wxASSERT( m_item->GetSize() == m_itemSize ); + + // Finishing the previously edited item + if( m_itemSize < m_chunkSize ) + { + // There is some not used but reserved memory left, so we should return it to the pool + int itemOffset = m_item->GetOffset(); + + // Add the not used memory back to the pool + m_freeChunks.insert( CHUNK( m_chunkSize - m_itemSize, itemOffset + m_itemSize ) ); + m_freeSpace += ( m_chunkSize - m_itemSize ); + // mergeFreeChunks(); // veery slow and buggy + } + +#if CACHED_CONTAINER_TEST > 1 + wxLogDebug( wxT( "Finishing item 0x%08lx (size %d)" ), (long) m_item, m_itemSize ); + test(); + m_item = NULL; // electric fence +#endif +} + + +VERTEX* CACHED_CONTAINER::Allocate( unsigned int aSize ) +{ + wxASSERT( m_item != NULL ); + + if( m_failed ) + return NULL; + + if( m_itemSize + aSize > m_chunkSize ) + { + // There is not enough space in the currently reserved chunk, so we have to resize it + + // Reserve a bigger memory chunk for the current item and + // make it multiple of 3 to store triangles + m_chunkSize = ( 2 * m_itemSize ) + aSize + ( 3 - aSize % 3 ); + // Save the current size before reallocating + m_chunkOffset = reallocate( m_chunkSize ); + + if( m_chunkOffset > m_currentSize ) + { + m_failed = true; + return NULL; + } + } + + VERTEX* reserved = &m_vertices[m_chunkOffset + m_itemSize]; + m_itemSize += aSize; + // Now the item officially possesses the memory chunk + m_item->setSize( m_itemSize ); + + // The content has to be updated + m_dirty = true; + +#if CACHED_CONTAINER_TEST > 1 + test(); +#endif +#if CACHED_CONTAINER_TEST > 2 + showFreeChunks(); + showReservedChunks(); +#endif + + return reserved; +} + + +void CACHED_CONTAINER::Delete( VERTEX_ITEM* aItem ) +{ + wxASSERT( aItem != NULL ); + wxASSERT( m_items.find( aItem ) != m_items.end() ); + + int size = aItem->GetSize(); + int offset = aItem->GetOffset(); + +#if CACHED_CONTAINER_TEST > 1 + wxLogDebug( wxT( "Removing 0x%08lx (size %d offset %d)" ), (long) aItem, size, offset ); +#endif + + // Insert a free memory chunk entry in the place where item was stored + if( size > 0 ) + { + m_freeChunks.insert( CHUNK( size, offset ) ); + m_freeSpace += size; + // Indicate that the item is not stored in the container anymore + aItem->setSize( 0 ); + } + + m_items.erase( aItem ); + +#if CACHED_CONTAINER_TEST > 1 + test(); +#endif + + // Dynamic memory freeing, there is no point in holding + // a large amount of memory when there is no use for it + if( m_freeSpace > ( 0.75 * m_currentSize ) && m_currentSize > m_initialSize ) + { + resizeContainer( 0.5 * m_currentSize ); + } +} + + +void CACHED_CONTAINER::Clear() +{ + // Change size to the default one + m_vertices = static_cast<VERTEX*>( realloc( m_vertices, + m_initialSize * sizeof( VERTEX ) ) ); + + // Reset state variables + m_freeSpace = m_initialSize; + m_currentSize = m_initialSize; + m_failed = false; + + // Set the size of all the stored VERTEX_ITEMs to 0, so it is clear that they are not held + // in the container anymore + ITEMS::iterator it; + + for( it = m_items.begin(); it != m_items.end(); ++it ) + { + ( *it )->setSize( 0 ); + } + + m_items.clear(); + + + // Now there is only free space left + m_freeChunks.clear(); + m_freeChunks.insert( CHUNK( m_freeSpace, 0 ) ); +} + + +unsigned int CACHED_CONTAINER::reallocate( unsigned int aSize ) +{ + wxASSERT( aSize > 0 ); + +#if CACHED_CONTAINER_TEST > 2 + wxLogDebug( wxT( "Resize 0x%08lx from %d to %d" ), (long) m_item, m_itemSize, aSize ); +#endif + + // Is there enough space to store vertices? + if( m_freeSpace < aSize ) + { + bool result; + + // Would it be enough to double the current space? + if( aSize < m_freeSpace + m_currentSize ) + { + // Yes: exponential growing + result = resizeContainer( m_currentSize * 2 ); + } + else + { + // No: grow to the nearest greater power of 2 + result = resizeContainer( pow( 2, ceil( log2( m_currentSize * 2 + aSize ) ) ) ); + } + + if( !result ) + return UINT_MAX; + } + + // Look for the free space chunk of at least given size + FREE_CHUNK_MAP::iterator newChunk = m_freeChunks.lower_bound( aSize ); + + if( newChunk == m_freeChunks.end() ) + { + // In the case when there is enough space to store the vertices, + // but the free space is not continous we should defragment the container + if( !defragment() ) + return UINT_MAX; + + // Update the current offset + m_chunkOffset = m_item->GetOffset(); + + // We can take the first free chunk, as there is only one after defragmentation + // and we can be sure that it provides enough space to store the object + newChunk = m_freeChunks.begin(); + } + + // Parameters of the allocated cuhnk + unsigned int chunkSize = newChunk->first; + unsigned int chunkOffset = newChunk->second; + + wxASSERT( chunkSize >= aSize ); + wxASSERT( chunkOffset < m_currentSize ); + + // Check if the item was previously stored in the container + if( m_itemSize > 0 ) + { +#if CACHED_CONTAINER_TEST > 3 + wxLogDebug( wxT( "Moving 0x%08x from 0x%08x to 0x%08x" ), + (int) m_item, oldChunkOffset, chunkOffset ); +#endif + // The item was reallocated, so we have to copy all the old data to the new place + memcpy( &m_vertices[chunkOffset], &m_vertices[m_chunkOffset], m_itemSize * VertexSize ); + + // Free the space previously used by the chunk + wxASSERT( m_itemSize > 0 ); + m_freeChunks.insert( CHUNK( m_itemSize, m_chunkOffset ) ); + m_freeSpace += m_itemSize; + } + + // Remove the allocated chunk from the free space pool + m_freeChunks.erase( newChunk ); + + // If there is some space left, return it to the pool - add an entry for it + if( chunkSize > aSize ) + { + m_freeChunks.insert( CHUNK( chunkSize - aSize, chunkOffset + aSize ) ); + } + + m_freeSpace -= aSize; + // mergeFreeChunks(); // veery slow and buggy + + m_item->setOffset( chunkOffset ); + + return chunkOffset; +} + + +bool CACHED_CONTAINER::defragment( VERTEX* aTarget ) +{ +#if CACHED_CONTAINER_TEST > 0 + wxLogDebug( wxT( "Defragmenting" ) ); + + prof_counter totalTime; + prof_start( &totalTime ); +#endif + + if( aTarget == NULL ) + { + // No target was specified, so we have to reallocate our own space + int size = m_currentSize * sizeof( VERTEX ); + aTarget = static_cast<VERTEX*>( malloc( size ) ); + + if( aTarget == NULL ) + { + DisplayError( NULL, wxString::Format( + wxT( "CACHED_CONTAINER::defragment: Run out of memory (malloc %d bytes)" ), + size ) ); + return false; + } + } + + int newOffset = 0; + ITEMS::iterator it, it_end; + + for( it = m_items.begin(), it_end = m_items.end(); it != it_end; ++it ) + { + VERTEX_ITEM* item = *it; + int itemOffset = item->GetOffset(); + int itemSize = item->GetSize(); + + // Move an item to the new container + memcpy( &aTarget[newOffset], &m_vertices[itemOffset], itemSize * VertexSize ); + + // Update new offset + item->setOffset( newOffset ); + + // Move to the next free space + newOffset += itemSize; + } + + free( m_vertices ); + m_vertices = aTarget; + + // Now there is only one big chunk of free memory + m_freeChunks.clear(); + wxASSERT( m_freeSpace > 0 ); + m_freeChunks.insert( CHUNK( m_freeSpace, m_currentSize - m_freeSpace ) ); + +#if CACHED_CONTAINER_TEST > 0 + prof_end( &totalTime ); + + wxLogDebug( wxT( "Defragmented the container storing %d vertices / %.1f ms" ), + m_currentSize - m_freeSpace, totalTime.msecs() ); +#endif + + return true; +} + + +void CACHED_CONTAINER::mergeFreeChunks() +{ + if( m_freeChunks.size() <= 1 ) // There are no chunks that can be merged + return; + +#if CACHED_CONTAINER_TEST > 0 + prof_counter totalTime; + prof_start( &totalTime ); +#endif + + // Reversed free chunks map - this one stores chunk size with its offset as the key + std::list<CHUNK> freeChunks; + + FREE_CHUNK_MAP::const_iterator it, it_end; + + for( it = m_freeChunks.begin(), it_end = m_freeChunks.end(); it != it_end; ++it ) + { + freeChunks.push_back( std::make_pair( it->second, it->first ) ); + } + + m_freeChunks.clear(); + freeChunks.sort(); + + std::list<CHUNK>::const_iterator itf, itf_end; + unsigned int offset = freeChunks.front().first; + unsigned int size = freeChunks.front().second; + freeChunks.pop_front(); + + for( itf = freeChunks.begin(), itf_end = freeChunks.end(); itf != itf_end; ++itf ) + { + if( itf->first == offset + size ) + { + // These chunks can be merged, so just increase the current chunk size and go on + size += itf->second; + } + else + { + // These chunks cannot be merged + // So store the previous one + m_freeChunks.insert( std::make_pair( size, offset ) ); + // and let's check the next chunk + offset = itf->first; + size = itf->second; + + } + } + + // Add the last one + m_freeChunks.insert( std::make_pair( size, offset ) ); + +#if CACHED_CONTAINER_TEST > 0 + prof_end( &totalTime ); + + wxLogDebug( wxT( "Merged free chunks / %.1f ms" ), totalTime.msecs() ); +#endif + + test(); +} + + +bool CACHED_CONTAINER::resizeContainer( unsigned int aNewSize ) +{ + wxASSERT( aNewSize != m_currentSize ); + +#if CACHED_CONTAINER_TEST > 0 + wxLogDebug( wxT( "Resizing container from %d to %d" ), m_currentSize, aNewSize ); +#endif + + VERTEX* newContainer; + + if( aNewSize < m_currentSize ) + { + // Shrinking container + // Sanity check, no shrinking if we cannot fit all the data + if( reservedSpace() > aNewSize ) + return false; + + int size = aNewSize * sizeof( VERTEX ); + newContainer = static_cast<VERTEX*>( malloc( size ) ); + + if( newContainer == NULL ) + { + DisplayError( NULL, wxString::Format( + wxT( "CACHED_CONTAINER::resizeContainer:\n" + "Run out of memory (malloc %d bytes)" ), + size ) ); + return false; + } + + // Defragment directly to the new, smaller container + defragment( newContainer ); + + // We have to correct freeChunks after defragmentation + m_freeChunks.clear(); + wxASSERT( aNewSize - reservedSpace() > 0 ); + m_freeChunks.insert( CHUNK( aNewSize - reservedSpace(), reservedSpace() ) ); + } + else + { + // Enlarging container + int size = aNewSize * sizeof( VERTEX ); + newContainer = static_cast<VERTEX*>( realloc( m_vertices, size ) ); + + if( newContainer == NULL ) + { + DisplayError( NULL, wxString::Format( + wxT( "CACHED_CONTAINER::resizeContainer:\n" + "Run out of memory (realloc from %d to %d bytes)" ), + m_currentSize * sizeof( VERTEX ), size ) ); + return false; + } + + // Add an entry for the new memory chunk at the end of the container + m_freeChunks.insert( CHUNK( aNewSize - m_currentSize, m_currentSize ) ); + } + + m_vertices = newContainer; + + m_freeSpace += ( aNewSize - m_currentSize ); + m_currentSize = aNewSize; + + return true; +} + + +#ifdef CACHED_CONTAINER_TEST +void CACHED_CONTAINER::showFreeChunks() +{ + FREE_CHUNK_MAP::iterator it; + + wxLogDebug( wxT( "Free chunks:" ) ); + + for( it = m_freeChunks.begin(); it != m_freeChunks.end(); ++it ) + { + unsigned int offset = getChunkOffset( *it ); + unsigned int size = getChunkSize( *it ); + wxASSERT( size > 0 ); + + wxLogDebug( wxT( "[0x%08x-0x%08x] (size %d)" ), + offset, offset + size - 1, size ); + } +} + + +void CACHED_CONTAINER::showReservedChunks() +{ + ITEMS::iterator it; + + wxLogDebug( wxT( "Reserved chunks:" ) ); + + for( it = m_items.begin(); it != m_items.end(); ++it ) + { + VERTEX_ITEM* item = *it; + unsigned int offset = item->GetOffset(); + unsigned int size = item->GetSize(); + wxASSERT( size > 0 ); + + wxLogDebug( wxT( "[0x%08x-0x%08x] @ 0x%08lx (size %d)" ), + offset, offset + size - 1, (long) item, size ); + } +} + + +void CACHED_CONTAINER::test() +{ + // Free space check + unsigned int freeSpace = 0; + FREE_CHUNK_MAP::iterator itf; + + for( itf = m_freeChunks.begin(); itf != m_freeChunks.end(); ++itf ) + freeSpace += getChunkSize( *itf ); + + wxASSERT( freeSpace == m_freeSpace ); + + // Reserved space check + /*unsigned int reservedSpace = 0; + ITEMS::iterator itr; + for( itr = m_items.begin(); itr != m_items.end(); ++itr ) + reservedSpace += ( *itr )->GetSize(); + reservedSpace += m_itemSize; // Add the current chunk size + + wxASSERT( ( freeSpace + reservedSpace ) == m_currentSize );*/ + + // Overlapping check TBD +} + +#endif /* CACHED_CONTAINER_TEST */ |