Root/monav/contractionhierarchies/blockcache.h

1/*
2Copyright 2010 Christian Vetter veaac.fdirct@gmail.com
3
4This file is part of MoNav.
5
6MoNav is free software: you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation, either version 3 of the License, or
9(at your option) any later version.
10
11MoNav is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with MoNav. If not, see <http://www.gnu.org/licenses/>.
18*/
19
20#ifndef BLOCKCACHE_H_INCLUDED
21#define BLOCKCACHE_H_INCLUDED
22
23#include <QFile>
24#include <QHash>
25#include <limits>
26#include <QtDebug>
27
28// Block must have member function / variables:
29// variable id => block id
30// function void load( const unsigned char* buffer )
31template< class Block >
32class BlockCache{
33
34public:
35
36    BlockCache()
37    {
38        m_cache = NULL;
39        m_LRU = NULL;
40        m_blocks = NULL;
41    }
42
43    bool load( const QString& filename, int cacheBlocks, unsigned blockSize )
44    {
45        m_cacheBlocks = cacheBlocks;
46        m_blockSize = blockSize;
47        m_inputFile.setFileName( filename );
48        if ( !m_inputFile.open( QIODevice::ReadOnly | QIODevice::Unbuffered ) ) {
49            qCritical() << "failed to open file:" << m_inputFile.fileName();
50            return false;
51        }
52
53        m_cache = new unsigned char[( m_cacheBlocks + 1 ) * m_blockSize];
54        m_LRU = new LRUEntry[m_cacheBlocks];
55        m_blocks = new Block[m_cacheBlocks];
56
57        m_firstLoaded = -1;
58        m_lastLoaded = -1;
59        m_loadedCount = 0;
60
61        return true;
62    }
63
64    void unload ( )
65    {
66        m_inputFile.close();
67        if ( m_cache != NULL )
68            delete[] m_cache;
69        if ( m_LRU != NULL )
70            delete[] m_LRU;
71        if ( m_blocks != NULL )
72            delete[] m_blocks;
73        m_cache = NULL;
74        m_LRU = NULL;
75        m_blocks = NULL;
76        m_index.clear();
77    }
78
79    const Block* getBlock( unsigned block )
80    {
81        int cacheID = m_index.value( block, -1 );
82        if ( cacheID == -1 )
83            return loadBlock( block );
84
85        useBlock( cacheID );
86        return m_blocks + cacheID;
87    }
88
89private:
90
91    const Block* loadBlock( unsigned block )
92    {
93        int freeBlock = m_loadedCount;
94        // cache is full => select least recently used block
95        if ( m_loadedCount == m_cacheBlocks ) {
96            assert ( m_lastLoaded != -1 );
97            freeBlock = m_lastLoaded;
98            m_index.remove( m_blocks[freeBlock].id );
99            useBlock( freeBlock );
100        } else {
101            //insert into the front of the list
102            m_LRU[freeBlock].previousLoaded = -1;
103            m_LRU[freeBlock].nextLoaded = m_firstLoaded;
104            if ( m_firstLoaded != -1 )
105                m_LRU[m_firstLoaded].previousLoaded = freeBlock;
106            if ( m_lastLoaded == -1 )
107                m_lastLoaded = freeBlock;
108            m_firstLoaded = freeBlock;
109            m_loadedCount++;
110        }
111
112        //load block
113        m_inputFile.seek( ( long long ) block * m_blockSize );
114        m_inputFile.read( ( char* ) m_cache + freeBlock * m_blockSize, m_blockSize );
115        m_blocks[freeBlock].load( block, m_cache + freeBlock * m_blockSize );
116        m_index[block] = freeBlock;
117
118        return m_blocks + freeBlock;
119    }
120
121    void useBlock( int cacheID )
122    {
123        assert( m_firstLoaded != -1 );
124        if ( m_firstLoaded == cacheID )
125            return;
126
127        LRUEntry& block = m_LRU[cacheID];
128
129        //remove block from the list to put it into the front
130        if ( block.nextLoaded != -1 )
131            m_LRU[block.nextLoaded].previousLoaded = block.previousLoaded;
132        else
133            m_lastLoaded = block.previousLoaded;
134
135        m_LRU[block.previousLoaded].nextLoaded = block.nextLoaded;
136
137        // insert block into the front
138        m_LRU[m_firstLoaded].previousLoaded = cacheID;
139        block.nextLoaded = m_firstLoaded;
140        block.previousLoaded = -1;
141        m_firstLoaded = cacheID;
142    }
143
144    struct LRUEntry{
145        int nextLoaded;
146        int previousLoaded;
147    };
148
149    Block* m_blocks;
150    LRUEntry* m_LRU;
151    unsigned char* m_cache;
152    int m_firstLoaded;
153    int m_lastLoaded;
154    int m_loadedCount;
155    int m_cacheBlocks;
156    unsigned m_blockSize;
157    QFile m_inputFile;
158    QHash< unsigned, int > m_index;
159
160};
161
162#endif // BLOCKCACHE_H_INCLUDED
163

Archive Download this file

Branches:
master



interactive