← Back to branch summary

~ubuntu-branches/ubuntu/trusty/qgis/trusty

« back to all changes in this revision

Viewing changes to src/core/spatialindex/rtree/BulkLoader.cc

  • Committer: Bazaar Package Importer
  • Author(s): Johan Van de Wauw
  • Date: 2010-07-11 20:23:24 UTC
  • mfrom: (3.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100711202324-5ktghxa7hracohmr
Tags: 1.4.0+12730-3ubuntu1
https://launchpad.net/bugs/540941
* Merge from Debian unstable (LP: #540941).
* Fix compilation issues with QT 4.7
* Add build-depends on libqt4-webkit-dev 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/spatialindex/rtree/BulkLoader.cc
 
1
// Spatial Index Library
 
2
//
 
3
// Copyright (C) 2002 Navel Ltd.
 
4
//
 
5
// This library is free software; you can redistribute it and/or
 
6
// modify it under the terms of the GNU Lesser General Public
 
7
// License as published by the Free Software Foundation; either
 
8
// version 2.1 of the License, or (at your option) any later version.
 
9
//
 
10
// This library is distributed in the hope that it will be useful,
 
11
// but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
13
// Lesser General Public License for more details.
 
14
//
 
15
// You should have received a copy of the GNU Lesser General Public
 
16
// License along with this library; if not, write to the Free Software
 
17
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
18
//
 
19
//  Email:
 
20
//    mhadji@gmail.com
 
21
 
 
22
#include <stdio.h>
 
23
#include <unistd.h>
 
24
#include <cstring>
 
25
 
 
26
#include "../spatialindex/SpatialIndexImpl.h"
 
27
 
 
28
#include "RTree.h"
 
29
#include "Leaf.h"
 
30
#include "Index.h"
 
31
 
 
32
#include "BulkLoader.h"
 
33
#include "qgslogger.h"
 
34
 
 
35
#ifdef _MSC_VER
 
36
// tell MSVC not to complain about exception declarations
 
37
#pragma warning(disable:4290)
 
38
#define UNUSED(symbol) symbol
 
39
#else
 
40
#define UNUSED(symbol)
 
41
#endif
 
42
 
 
43
using namespace SpatialIndex::RTree;
 
44
 
 
45
BulkLoadSource::BulkLoadSource(
 
46
  Tools::SmartPointer<IObjectStream> spStream, unsigned long howMany
 
47
) : m_spDataSource( spStream ), m_cHowMany( howMany )
 
48
{
 
49
}
 
50
 
 
51
BulkLoadSource::BulkLoadSource( IObjectStream* pStream, unsigned long howMany )
 
52
    : m_spDataSource( pStream ), m_cHowMany( howMany )
 
53
{
 
54
}
 
55
 
 
56
BulkLoadSource::BulkLoadSource( IObjectStream* pStream )
 
57
    : m_spDataSource( pStream ),
 
58
    m_cHowMany( std::numeric_limits<unsigned long>::max() )
 
59
{
 
60
}
 
61
 
 
62
BulkLoadSource::~BulkLoadSource()
 
63
{
 
64
}
 
65
 
 
66
Tools::IObject* BulkLoadSource::getNext()
 
67
{
 
68
  if ( m_cHowMany == 0 || ! m_spDataSource->hasNext() ) return 0;
 
69
  m_cHowMany--;
 
70
  return m_spDataSource->getNext();
 
71
}
 
72
 
 
73
bool BulkLoadSource::hasNext() throw()
 
74
{
 
75
  return ( m_cHowMany != 0 && m_spDataSource->hasNext() );
 
76
}
 
77
 
 
78
unsigned long BulkLoadSource::size() throw( Tools::NotSupportedException )
 
79
{
 
80
  throw Tools::NotSupportedException( "SpatialIndex::RTree::BulkLoadSource::size: this should never be called." );
 
81
}
 
82
 
 
83
void BulkLoadSource::rewind() throw( Tools::NotSupportedException )
 
84
{
 
85
  throw Tools::NotSupportedException( "SpatialIndex::RTree::BulkLoadSource::rewind: this should never be called." );
 
86
}
 
87
 
 
88
BulkLoadComparator::BulkLoadComparator( unsigned long d ) : m_compareDimension( d )
 
89
{
 
90
}
 
91
 
 
92
BulkLoadComparator::~BulkLoadComparator()
 
93
{
 
94
}
 
95
 
 
96
int BulkLoadComparator::compare( Tools::IObject* o1, Tools::IObject* o2 )
 
97
{
 
98
  IData* d1 = dynamic_cast<IData*>( o1 );
 
99
  IData* d2 = dynamic_cast<IData*>( o2 );
 
100
 
 
101
  IShape* s1; d1->getShape( &s1 );
 
102
  IShape* s2; d2->getShape( &s2 );
 
103
  Region r1; s1->getMBR( r1 );
 
104
  Region r2; s2->getMBR( r2 );
 
105
 
 
106
  int ret = 0;
 
107
  if (
 
108
    r1.m_pHigh[m_compareDimension] + r1.m_pLow[m_compareDimension] <
 
109
    r2.m_pHigh[m_compareDimension] + r2.m_pLow[m_compareDimension] ) ret = -1;
 
110
  else if (
 
111
    r1.m_pHigh[m_compareDimension] + r1.m_pLow[m_compareDimension] >
 
112
    r2.m_pHigh[m_compareDimension] + r2.m_pLow[m_compareDimension] ) ret = 1;
 
113
 
 
114
  delete s1;
 
115
  delete s2;
 
116
 
 
117
  return ret;
 
118
}
 
119
 
 
120
BulkLoader::TmpFile::TmpFile() : m_pNext( 0 )
 
121
{
 
122
}
 
123
 
 
124
BulkLoader::TmpFile::~TmpFile()
 
125
{
 
126
  if ( m_pNext != 0 ) delete m_pNext;
 
127
}
 
128
 
 
129
void BulkLoader::TmpFile::storeRecord( Region& r, long id )
 
130
{
 
131
  unsigned long len = sizeof( long ) + sizeof( unsigned long ) + 2 * r.m_dimension * sizeof( double );
 
132
  byte* data = new byte[len];
 
133
  byte* ptr = data;
 
134
 
 
135
  memcpy( ptr, &id, sizeof( long ) );
 
136
  ptr += sizeof( long );
 
137
  memcpy( ptr, &( r.m_dimension ), sizeof( unsigned long ) );
 
138
  ptr += sizeof( unsigned long );
 
139
  memcpy( ptr, r.m_pLow, r.m_dimension * sizeof( double ) );
 
140
  ptr += r.m_dimension * sizeof( double );
 
141
  memcpy( ptr, r.m_pHigh, r.m_dimension * sizeof( double ) );
 
142
 
 
143
  m_tmpFile.storeNextObject( len, data );
 
144
  delete[] data;
 
145
}
 
146
 
 
147
void BulkLoader::TmpFile::loadRecord( Region& r, long& id )
 
148
{
 
149
  unsigned long len;
 
150
  byte* data;
 
151
  m_tmpFile.loadNextObject( &data, len );
 
152
 
 
153
  byte* ptr = data;
 
154
  memcpy( &id, ptr, sizeof( long ) );
 
155
  ptr += sizeof( long );
 
156
 
 
157
  unsigned long dim;
 
158
  memcpy( &dim, ptr, sizeof( unsigned long ) );
 
159
  ptr += sizeof( unsigned long );
 
160
 
 
161
  if ( dim != r.m_dimension )
 
162
  {
 
163
    delete[] r.m_pLow;
 
164
    delete[] r.m_pHigh;
 
165
    r.m_dimension = dim;
 
166
    r.m_pLow = new double[dim];
 
167
    r.m_pHigh = new double[dim];
 
168
  }
 
169
 
 
170
  memcpy( r.m_pLow, ptr, dim * sizeof( double ) );
 
171
  ptr += dim * sizeof( double );
 
172
  memcpy( r.m_pHigh, ptr, dim * sizeof( double ) );
 
173
 
 
174
  delete[] data;
 
175
}
 
176
 
 
177
IData* BulkLoader::TmpFile::getNext()
 
178
{
 
179
  if ( m_pNext == 0 ) return 0;
 
180
 
 
181
  IData* ret = m_pNext;
 
182
 
 
183
  try
 
184
  {
 
185
    Region r;
 
186
    long id;
 
187
    loadRecord( r, id );
 
188
    m_pNext = new Data( 0, 0, r, id );
 
189
  }
 
190
  catch ( Tools::EndOfStreamException& e )
 
191
  {
 
192
    UNUSED( e );
 
193
    m_pNext = 0;
 
194
  }
 
195
  catch ( ... )
 
196
  {
 
197
    m_pNext = 0;
 
198
    throw;
 
199
  }
 
200
 
 
201
  return ret;
 
202
}
 
203
 
 
204
bool BulkLoader::TmpFile::hasNext() throw()
 
205
{
 
206
  return ( m_pNext != 0 );
 
207
}
 
208
 
 
209
unsigned long BulkLoader::TmpFile::size() throw( Tools::NotSupportedException )
 
210
{
 
211
  throw Tools::NotSupportedException( "Not supported yet." );
 
212
}
 
213
 
 
214
void BulkLoader::TmpFile::rewind()
 
215
{
 
216
  Region r;
 
217
  long id;
 
218
 
 
219
  if ( m_pNext != 0 )
 
220
  {
 
221
    delete m_pNext;
 
222
    m_pNext = 0;
 
223
  }
 
224
 
 
225
  m_tmpFile.rewindForReading();
 
226
 
 
227
  try
 
228
  {
 
229
    loadRecord( r, id );
 
230
    m_pNext = new Data( 0, 0, r, id );
 
231
  }
 
232
  catch ( Tools::EndOfStreamException& e )
 
233
  {
 
234
    UNUSED( e );
 
235
  }
 
236
}
 
237
 
 
238
void BulkLoader::bulkLoadUsingSTR(
 
239
#ifdef _MSC_VER
 
240
  // MSVC seems to find RTree* pTree ambiguous
 
241
  SpatialIndex::RTree::RTree* pTree,
 
242
#else
 
243
  RTree* pTree,
 
244
#endif//_MSC_VER
 
245
  IDataStream& stream,
 
246
  unsigned long bindex,
 
247
  unsigned long bleaf,
 
248
  unsigned long bufferSize )
 
249
{
 
250
  NodePtr n = pTree->readNode( pTree->m_rootID );
 
251
  pTree->deleteNode( n.get() );
 
252
 
 
253
  // create the leaf level first.
 
254
  TmpFile* tmpFile = new TmpFile();
 
255
  unsigned long cNodes = 0;
 
256
  unsigned long cTotalData = 0;
 
257
 
 
258
#ifdef DEBUG
 
259
  QgsDebugMsg( "Building level 0" );
 
260
#endif
 
261
 
 
262
  createLevel( pTree, stream, pTree->m_dimension, pTree->m_dimension, bleaf, 0, bufferSize, *tmpFile, cNodes, cTotalData );
 
263
 
 
264
  pTree->m_stats.m_data = cTotalData;
 
265
 
 
266
  // create index levels afterwards.
 
267
  unsigned long level = 1;
 
268
  tmpFile->rewind();
 
269
  BulkLoadSource* bs = new BulkLoadSource( tmpFile );
 
270
 
 
271
  while ( cNodes > 1 )
 
272
  {
 
273
    cNodes = 0;
 
274
    TmpFile* pTF = new TmpFile();
 
275
 
 
276
#ifndef NDEBUG
 
277
    QgsDebugMsg( QString( "Building level %1" ).arg( level ) );
 
278
#endif
 
279
    pTree->m_stats.m_nodesInLevel.push_back( 0 );
 
280
 
 
281
    createLevel( pTree, *bs, pTree->m_dimension, pTree->m_dimension, bindex, level, bufferSize, *pTF, cNodes, cTotalData );
 
282
    delete bs;
 
283
 
 
284
    level++;
 
285
    pTF->rewind();
 
286
    bs = new BulkLoadSource( pTF );
 
287
  }
 
288
 
 
289
  pTree->m_stats.m_treeHeight = level;
 
290
 
 
291
  delete bs;
 
292
 
 
293
  pTree->storeHeader();
 
294
}
 
295
 
 
296
void BulkLoader::createLevel(
 
297
#ifdef _MSC_VER
 
298
  // MSVC seems to find RTree* pTree ambiguous
 
299
  SpatialIndex::RTree::RTree* pTree,
 
300
#else
 
301
  RTree* pTree,
 
302
#endif//_MSC_VER
 
303
  Tools::IObjectStream& stream,
 
304
  unsigned long dimension,
 
305
  unsigned long k,
 
306
  unsigned long b,
 
307
  unsigned long level,
 
308
  unsigned long bufferSize,
 
309
  BulkLoader::TmpFile& tmpFile,
 
310
  unsigned long& numberOfNodes,
 
311
  unsigned long& totalData )
 
312
{
 
313
  BulkLoadComparator bc( dimension - k );
 
314
  Tools::SmartPointer<Tools::IObjectStream> es( Tools::externalSort( stream, bc, bufferSize ) );
 
315
  unsigned long r = es->size();
 
316
  totalData = r;
 
317
 
 
318
  if ( k == dimension - 1 )
 
319
  {
 
320
    // store new pages in storage manager and page information in temporary file.
 
321
 
 
322
    std::vector<Tools::SmartPointer<IData> > entries;
 
323
 
 
324
    while ( es->hasNext() )
 
325
    {
 
326
      entries.push_back( Tools::SmartPointer<IData>( static_cast<IData*>( es->getNext() ) ) );
 
327
 
 
328
      if ( entries.size() == b )
 
329
      {
 
330
        Node* n = createNode( pTree, entries, level );
 
331
        pTree->writeNode( n );
 
332
        if ( r <= b ) pTree->m_rootID = n->m_identifier;
 
333
        numberOfNodes++;
 
334
        tmpFile.storeRecord( n->m_nodeMBR, n->m_identifier );
 
335
        entries.clear();
 
336
        delete n;
 
337
      }
 
338
    }
 
339
 
 
340
    if ( ! entries.empty() )
 
341
    {
 
342
      Node* n = createNode( pTree, entries, level );
 
343
      pTree->writeNode( n );
 
344
      if ( r <= b ) pTree->m_rootID = n->m_identifier;
 
345
      numberOfNodes++;
 
346
      tmpFile.storeRecord( n->m_nodeMBR, n->m_identifier );
 
347
      entries.clear();
 
348
      delete n;
 
349
    }
 
350
  }
 
351
  else
 
352
  {
 
353
    unsigned long P = static_cast<unsigned long>( std::ceil( static_cast<double>( r ) / static_cast<double>( b ) ) );
 
354
    unsigned long D = static_cast<unsigned long>( std::ceil( std::pow( static_cast<double>( P ), static_cast<double>( k - 1 ) / static_cast<double>( k ) ) ) );
 
355
 
 
356
    while ( es->hasNext() ) // this will happen S = ceil[P^(1 / k)] times
 
357
    {
 
358
      BulkLoadSource bs( es, D * b );
 
359
      unsigned long cTotalData;
 
360
      createLevel( pTree, bs, dimension, k - 1, b, level, bufferSize, tmpFile, numberOfNodes, cTotalData );
 
361
    }
 
362
  }
 
363
}
 
364
 
 
365
#ifdef _MSC_VER
 
366
// MSVC seems to find RTree* pTree ambiguous
 
367
Node* BulkLoader::createNode( SpatialIndex::RTree::RTree* pTree, std::vector<Tools::SmartPointer<IData> >& e, unsigned long level )
 
368
#else
 
369
Node* BulkLoader::createNode( RTree* pTree, std::vector<Tools::SmartPointer<IData> >& e, unsigned long level )
 
370
#endif//_MSC_VER
 
371
{
 
372
  Node* n;
 
373
 
 
374
  if ( level == 0 ) n = new Leaf( pTree, -1 );
 
375
  else n = new Index( pTree, -1, level );
 
376
 
 
377
  for ( unsigned long cChild = 0; cChild < e.size(); cChild++ )
 
378
  {
 
379
    unsigned long len;
 
380
    byte* data;
 
381
    e[cChild]->getData( len, &data );
 
382
    IShape* s; e[cChild]->getShape( &s );
 
383
    RegionPtr mbr = pTree->m_regionPool.acquire();
 
384
    s->getMBR( *mbr );
 
385
    delete s;
 
386
    unsigned long id = e[cChild]->getIdentifier();
 
387
    n->insertEntry( len, data, *mbr, id );
 
388
  }
 
389
 
 
390
  return n;
 
391
}