cached_container.cpp 15.2 KB
Newer Older
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
/*
 * 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
 */

/**
26 27 28 29
 * @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.
30 31
 */

32 33 34 35
#include <gal/opengl/cached_container.h>
#include <gal/opengl/vertex_manager.h>
#include <gal/opengl/vertex_item.h>
#include <gal/opengl/shader.h>
36
#include <confirm.h>
37
#include <wx/log.h>
38
#include <list>
39 40 41 42
#ifdef __WXDEBUG__
#include <profile.h>
#endif /* __WXDEBUG__ */

43
using namespace KIGFX;
44

45
CACHED_CONTAINER::CACHED_CONTAINER( unsigned int aSize ) :
46
    VERTEX_CONTAINER( aSize ), m_item( NULL )
47 48
{
    // In the beginning there is only free space
Maciej Suminski's avatar
Maciej Suminski committed
49
    m_freeChunks.insert( CHUNK( aSize, 0 ) );
50 51 52
}


53
void CACHED_CONTAINER::SetItem( VERTEX_ITEM* aItem )
54
{
55
    wxASSERT( aItem != NULL );
56

57 58 59
    m_item      = aItem;
    m_itemSize  = m_item->GetSize();
    m_chunkSize = m_itemSize;
60

61 62
    if( m_itemSize == 0 )
        m_items.insert( m_item ); // The item was not stored before
63
    else
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
        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 )
79
    {
80 81
        // There is some not used but reserved memory left, so we should return it to the pool
        int itemOffset = m_item->GetOffset();
82

83
        // Add the not used memory back to the pool
Maciej Suminski's avatar
Maciej Suminski committed
84
        m_freeChunks.insert( CHUNK( m_chunkSize - m_itemSize, itemOffset + m_itemSize ) );
85 86
        m_freeSpace += ( m_chunkSize - m_itemSize );
        // mergeFreeChunks();   // veery slow and buggy
87
    }
88 89 90 91

#if CACHED_CONTAINER_TEST > 1
    wxLogDebug( wxT( "Finishing item 0x%08lx (size %d)" ), (long) m_item, m_itemSize );
    test();
92
    m_item = NULL;    // electric fence
93
#endif
94 95 96
}


97
VERTEX* CACHED_CONTAINER::Allocate( unsigned int aSize )
98
{
99
    wxASSERT( m_item != NULL );
100

101 102
    if( m_failed )
        return NULL;
103

104
    if( m_itemSize + aSize > m_chunkSize )
105
    {
106
        // There is not enough space in the currently reserved chunk, so we have to resize it
107

108 109 110 111 112
        // 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 );
113

114
        if( m_chunkOffset > m_currentSize )
115
        {
116 117
            m_failed = true;
            return NULL;
118 119 120
        }
    }

121 122
    VERTEX* reserved = &m_vertices[m_chunkOffset + m_itemSize];
    m_itemSize += aSize;
123
    // Now the item officially possesses the memory chunk
124
    m_item->setSize( m_itemSize );
125

126 127
    // The content has to be updated
    m_dirty = true;
128

129 130 131
#if CACHED_CONTAINER_TEST > 1
    test();
#endif
132 133 134 135
#if CACHED_CONTAINER_TEST > 2
    showFreeChunks();
    showReservedChunks();
#endif
136

137
    return reserved;
138 139 140
}


141
void CACHED_CONTAINER::Delete( VERTEX_ITEM* aItem )
142
{
143 144 145 146 147
    wxASSERT( aItem != NULL );
    wxASSERT( m_items.find( aItem ) != m_items.end() );

    int size   = aItem->GetSize();
    int offset = aItem->GetOffset();
148

149 150 151 152 153 154 155
#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 )
    {
Maciej Suminski's avatar
Maciej Suminski committed
156
        m_freeChunks.insert( CHUNK( size, offset ) );
157 158 159 160
        m_freeSpace += size;
        // Indicate that the item is not stored in the container anymore
        aItem->setSize( 0 );
    }
161

162 163 164 165 166
    m_items.erase( aItem );

#if CACHED_CONTAINER_TEST > 1
    test();
#endif
167 168 169

    // Dynamic memory freeing, there is no point in holding
    // a large amount of memory when there is no use for it
170
    if( m_freeSpace > ( m_currentSize / 2 ) && m_currentSize > m_initialSize )
171 172 173 174 175 176
    {
        resizeContainer( m_currentSize / 2 );
    }
}


177
void CACHED_CONTAINER::Clear()
178
{
179 180 181
    // Change size to the default one
    m_vertices = static_cast<VERTEX*>( realloc( m_vertices,
                                                m_initialSize * sizeof( VERTEX ) ) );
182

183 184 185 186
    // Reset state variables
    m_freeSpace     = m_initialSize;
    m_currentSize   = m_initialSize;
    m_failed = false;
187

188 189
    // Set the size of all the stored VERTEX_ITEMs to 0, so it is clear that they are not held
    // in the container anymore
Maciej Suminski's avatar
Maciej Suminski committed
190
    ITEMS::iterator it;
191

192 193 194 195
    for( it = m_items.begin(); it != m_items.end(); ++it )
    {
        ( *it )->setSize( 0 );
    }
196

197
    m_items.clear();
198 199


200 201
    // Now there is only free space left
    m_freeChunks.clear();
Maciej Suminski's avatar
Maciej Suminski committed
202
    m_freeChunks.insert( CHUNK( m_freeSpace, 0 ) );
203
}
204 205


206 207 208
VERTEX* CACHED_CONTAINER::GetVertices( const VERTEX_ITEM* aItem ) const
{
    int offset = aItem->GetOffset();
209

210
    return &m_vertices[offset];
211 212
}

213

214
unsigned int CACHED_CONTAINER::reallocate( unsigned int aSize )
215
{
216 217
    wxASSERT( aSize > 0 );

218
#if CACHED_CONTAINER_TEST > 2
219
    wxLogDebug( wxT( "Resize 0x%08lx from %d to %d" ), (long) m_item, m_itemSize, aSize );
220 221
#endif

222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242
    // 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 bigger power of 2
            result = resizeContainer( getPowerOf2( m_currentSize * 2 + aSize ) );
        }

        if( !result )
            return UINT_MAX;
    }

243
    // Look for the free space chunk of at least given size
Maciej Suminski's avatar
Maciej Suminski committed
244
    FREE_CHUNK_MAP::iterator newChunk = m_freeChunks.lower_bound( aSize );
245

246
    if( newChunk == m_freeChunks.end() )
247
    {
248 249
        // In the case when there is enough space to store the vertices,
        // but the free space is not continous we should defragment the container
250
        if( !defragment() )
Maciej Suminski's avatar
Maciej Suminski committed
251
            return UINT_MAX;
252 253 254

        // Update the current offset
        m_chunkOffset = m_item->GetOffset();
255 256 257

        // 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
258
        newChunk = m_freeChunks.begin();
259 260
    }

261
    // Parameters of the allocated cuhnk
262
    unsigned int chunkSize   = newChunk->first;
263
    unsigned int chunkOffset = newChunk->second;
264 265

    wxASSERT( chunkSize >= aSize );
266 267 268 269 270
    wxASSERT( chunkOffset < m_currentSize );

    // Check if the item was previously stored in the container
    if( m_itemSize > 0 )
    {
271 272 273 274
#if CACHED_CONTAINER_TEST > 3
        wxLogDebug( wxT( "Moving 0x%08x from 0x%08x to 0x%08x" ),
                    (int) m_item, oldChunkOffset, chunkOffset );
#endif
275 276
        // 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],
277
                m_itemSize * VertexSize );
278 279

        // Free the space previously used by the chunk
280
        wxASSERT( m_itemSize > 0 );
Maciej Suminski's avatar
Maciej Suminski committed
281
        m_freeChunks.insert( CHUNK( m_itemSize, m_chunkOffset ) );
282 283
        m_freeSpace += m_itemSize;
    }
284

285 286
    // Remove the allocated chunk from the free space pool
    m_freeChunks.erase( newChunk );
287 288 289 290

    // If there is some space left, return it to the pool - add an entry for it
    if( chunkSize > aSize )
    {
Maciej Suminski's avatar
Maciej Suminski committed
291
        m_freeChunks.insert( CHUNK( chunkSize - aSize, chunkOffset + aSize ) );
292 293
    }

294
    m_freeSpace -= aSize;
295
    // mergeFreeChunks();   // veery slow and buggy
296

297
    m_item->setOffset( chunkOffset );
298 299 300 301 302

    return chunkOffset;
}


303
bool CACHED_CONTAINER::defragment( VERTEX* aTarget )
304
{
305 306
#if CACHED_CONTAINER_TEST > 0
    wxLogDebug( wxT( "Defragmenting" ) );
307

308 309
    prof_counter totalTime;
    prof_start( &totalTime, false );
310
#endif
311

312 313
    if( aTarget == NULL )
    {
314
        // No target was specified, so we have to reallocate our own space
315 316
        aTarget = static_cast<VERTEX*>( malloc( m_currentSize * sizeof( VERTEX ) ) );

317 318
        if( aTarget == NULL )
        {
319
            DisplayError( NULL, wxT( "Run out of memory" ) );
320 321 322 323 324
            return false;
        }
    }

    int newOffset = 0;
Maciej Suminski's avatar
Maciej Suminski committed
325
    ITEMS::iterator it, it_end;
326

327
    for( it = m_items.begin(), it_end = m_items.end(); it != it_end; ++it )
328
    {
329 330 331
        VERTEX_ITEM* item = *it;
        int itemOffset    = item->GetOffset();
        int itemSize      = item->GetSize();
332 333

        // Move an item to the new container
334
        memcpy( &aTarget[newOffset], &m_vertices[itemOffset], itemSize * VertexSize );
335

336
        // Update new offset
337
        item->setOffset( newOffset );
338 339 340 341 342

        // Move to the next free space
        newOffset += itemSize;
    }

343
    free( m_vertices );
344 345 346 347
    m_vertices = aTarget;

    // Now there is only one big chunk of free memory
    m_freeChunks.clear();
348
    wxASSERT( m_freeSpace > 0 );
Maciej Suminski's avatar
Maciej Suminski committed
349
    m_freeChunks.insert( CHUNK( m_freeSpace, m_currentSize - m_freeSpace ) );
350

351
#if CACHED_CONTAINER_TEST > 0
352 353 354 355
    prof_end( &totalTime );

    wxLogDebug( wxT( "Defragmented the container storing %d vertices / %.1f ms" ),
                m_currentSize - m_freeSpace, (double) totalTime.value / 1000.0 );
356
#endif
357 358 359 360 361

    return true;
}


362
void CACHED_CONTAINER::mergeFreeChunks()
363
{
364
    if( m_freeChunks.size() <= 1 ) // There are no chunks that can be merged
365
        return;
366

367
#if CACHED_CONTAINER_TEST > 0
368 369
    prof_counter totalTime;
    prof_start( &totalTime, false );
370
#endif
371

372
    // Reversed free chunks map - this one stores chunk size with its offset as the key
Maciej Suminski's avatar
Maciej Suminski committed
373
    std::list<CHUNK> freeChunks;
374

Maciej Suminski's avatar
Maciej Suminski committed
375
    FREE_CHUNK_MAP::const_iterator it, it_end;
376

377 378 379 380
    for( it = m_freeChunks.begin(), it_end = m_freeChunks.end(); it != it_end; ++it )
    {
        freeChunks.push_back( std::make_pair( it->second, it->first ) );
    }
381

382 383
    m_freeChunks.clear();
    freeChunks.sort();
384

Maciej Suminski's avatar
Maciej Suminski committed
385
    std::list<CHUNK>::const_iterator itf, itf_end;
386 387 388
    unsigned int offset = freeChunks.front().first;
    unsigned int size   = freeChunks.front().second;
    freeChunks.pop_front();
389

390 391 392 393 394 395 396 397 398 399 400 401 402 403 404
    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;
405

406 407 408 409 410
        }
    }

    // Add the last one
    m_freeChunks.insert( std::make_pair( size, offset ) );
411

412
#if CACHED_CONTAINER_TEST > 0
413 414 415
    prof_end( &totalTime );

    wxLogDebug( wxT( "Merged free chunks / %.1f ms" ), (double) totalTime.value / 1000.0 );
416
#endif
417 418

    test();
419 420 421
}


422
bool CACHED_CONTAINER::resizeContainer( unsigned int aNewSize )
423
{
424 425
    wxASSERT( aNewSize != m_currentSize );

426 427 428 429 430
#if CACHED_CONTAINER_TEST > 0
    wxLogDebug( wxT( "Resizing container from %d to %d" ), m_currentSize, aNewSize );
#endif

    VERTEX* newContainer;
431

432 433
    if( aNewSize < m_currentSize )
    {
434
        // Shrinking container
435
        // Sanity check, no shrinking if we cannot fit all the data
436
        if( reservedSpace() > aNewSize )
437 438
            return false;

439 440
        newContainer = static_cast<VERTEX*>( malloc( aNewSize * sizeof( VERTEX ) ) );

441 442
        if( newContainer == NULL )
        {
443
            DisplayError( NULL, wxT( "Run out of memory" ) );
444 445 446 447 448
            return false;
        }

        // Defragment directly to the new, smaller container
        defragment( newContainer );
449 450 451

        // We have to correct freeChunks after defragmentation
        m_freeChunks.clear();
452
        wxASSERT( aNewSize - reservedSpace() > 0 );
Maciej Suminski's avatar
Maciej Suminski committed
453
        m_freeChunks.insert( CHUNK( aNewSize - reservedSpace(), reservedSpace() ) );
454 455 456
    }
    else
    {
457
        // Enlarging container
458 459
        newContainer = static_cast<VERTEX*>( realloc( m_vertices, aNewSize * sizeof( VERTEX ) ) );

460 461
        if( newContainer == NULL )
        {
462
            DisplayError( NULL, wxT( "Run out of memory" ) );
463 464
            return false;
        }
465

466
        // Add an entry for the new memory chunk at the end of the container
Maciej Suminski's avatar
Maciej Suminski committed
467
        m_freeChunks.insert( CHUNK( aNewSize - m_currentSize, m_currentSize ) );
468 469
    }

470
    m_vertices = newContainer;
471

472
    m_freeSpace   += ( aNewSize - m_currentSize );
473 474 475 476
    m_currentSize = aNewSize;

    return true;
}
477 478


479
unsigned int CACHED_CONTAINER::getPowerOf2( unsigned int aNumber ) const
480
{
481
    unsigned int power = 1;
482

483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500
    while( power < aNumber && power != 0 )
        power <<= 1;

    return power;
}


#ifdef CACHED_CONTAINER_TEST
void CACHED_CONTAINER::showFreeChunks()
{
    FreeChunkMap::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 );
501
        wxASSERT( size > 0 );
502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519

        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();
520
        wxASSERT( size > 0 );
521

522 523
        wxLogDebug( wxT( "[0x%08x-0x%08x] @ 0x%08lx (size %d)" ),
                    offset, offset + size - 1, (long) item, size );
524 525 526 527 528 529 530 531 532
    }
}


void CACHED_CONTAINER::test()
{
    // Free space check
    unsigned int freeSpace = 0;
    FreeChunkMap::iterator itf;
533

534 535
    for( itf = m_freeChunks.begin(); itf != m_freeChunks.end(); ++itf )
        freeSpace += getChunkSize( *itf );
536 537

    wxASSERT( freeSpace == m_freeSpace );
538 539 540 541 542 543 544 545 546 547 548

    // 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
549
}
550

551
#endif /* CACHED_CONTAINER_TEST */