1 : /******************************************************************************
2 : * $Id: shptree.c,v 1.17 2012-01-27 21:09:26 fwarmerdam Exp $
3 : *
4 : * Project: Shapelib
5 : * Purpose: Implementation of quadtree building and searching functions.
6 : * Author: Frank Warmerdam, warmerdam@pobox.com
7 : *
8 : ******************************************************************************
9 : * Copyright (c) 1999, Frank Warmerdam
10 : *
11 : * This software is available under the following "MIT Style" license,
12 : * or at the option of the licensee under the LGPL (see LICENSE.LGPL). This
13 : * option is discussed in more detail in shapelib.html.
14 : *
15 : * --
16 : *
17 : * Permission is hereby granted, free of charge, to any person obtaining a
18 : * copy of this software and associated documentation files (the "Software"),
19 : * to deal in the Software without restriction, including without limitation
20 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
21 : * and/or sell copies of the Software, and to permit persons to whom the
22 : * Software is furnished to do so, subject to the following conditions:
23 : *
24 : * The above copyright notice and this permission notice shall be included
25 : * in all copies or substantial portions of the Software.
26 : *
27 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
28 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
29 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
30 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
31 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
32 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
33 : * DEALINGS IN THE SOFTWARE.
34 : ******************************************************************************
35 : *
36 : * $Log: shptree.c,v $
37 : * Revision 1.17 2012-01-27 21:09:26 fwarmerdam
38 : * optimize .qix output (gdal #4472)
39 : *
40 : * Revision 1.16 2011-12-11 22:26:46 fwarmerdam
41 : * upgrade .qix access code to use SAHooks (gdal #3365)
42 : *
43 : * Revision 1.15 2011-07-24 05:59:25 fwarmerdam
44 : * minimize use of CPLError in favor of SAHooks.Error()
45 : *
46 : * Revision 1.14 2010-08-27 23:43:27 fwarmerdam
47 : * add SHPAPI_CALL attribute in code
48 : *
49 : * Revision 1.13 2010-06-29 05:50:15 fwarmerdam
50 : * fix sign of Z/M comparisons in SHPCheckObjectContained (#2223)
51 : *
52 : * Revision 1.12 2008-11-12 15:39:50 fwarmerdam
53 : * improve safety in face of buggy .shp file.
54 : *
55 : * Revision 1.11 2007/10/27 03:31:14 fwarmerdam
56 : * limit default depth of tree to 12 levels (gdal ticket #1594)
57 : *
58 : * Revision 1.10 2005/01/03 22:30:13 fwarmerdam
59 : * added support for saved quadtrees
60 : *
61 : * Revision 1.9 2003/01/28 15:53:41 warmerda
62 : * Avoid build warnings.
63 : *
64 : * Revision 1.8 2002/05/07 13:07:45 warmerda
65 : * use qsort() - patch from Bernhard Herzog
66 : *
67 : * Revision 1.7 2002/01/15 14:36:07 warmerda
68 : * updated email address
69 : *
70 : * Revision 1.6 2001/05/23 13:36:52 warmerda
71 : * added use of SHPAPI_CALL
72 : *
73 : * Revision 1.5 1999/11/05 14:12:05 warmerda
74 : * updated license terms
75 : *
76 : * Revision 1.4 1999/06/02 18:24:21 warmerda
77 : * added trimming code
78 : *
79 : * Revision 1.3 1999/06/02 17:56:12 warmerda
80 : * added quad'' subnode support for trees
81 : *
82 : * Revision 1.2 1999/05/18 19:11:11 warmerda
83 : * Added example searching capability
84 : *
85 : * Revision 1.1 1999/05/18 17:49:20 warmerda
86 : * New
87 : *
88 : */
89 :
90 : #include "shapefil.h"
91 :
92 : #include <math.h>
93 : #include <assert.h>
94 : #include <stdlib.h>
95 : #include <string.h>
96 :
97 : #ifdef USE_CPL
98 : #include "cpl_error.h"
99 : #endif
100 :
101 : SHP_CVSID("$Id: shptree.c,v 1.17 2012-01-27 21:09:26 fwarmerdam Exp $")
102 :
103 : #ifndef TRUE
104 : # define TRUE 1
105 : # define FALSE 0
106 : #endif
107 :
108 : static int bBigEndian = 0;
109 :
110 :
111 : /* -------------------------------------------------------------------- */
112 : /* If the following is 0.5, nodes will be split in half. If it */
113 : /* is 0.6 then each subnode will contain 60% of the parent */
114 : /* node, with 20% representing overlap. This can be help to */
115 : /* prevent small objects on a boundary from shifting too high */
116 : /* up the tree. */
117 : /* -------------------------------------------------------------------- */
118 :
119 : #define SHP_SPLIT_RATIO 0.55
120 :
121 : /************************************************************************/
122 : /* SfRealloc() */
123 : /* */
124 : /* A realloc cover function that will access a NULL pointer as */
125 : /* a valid input. */
126 : /************************************************************************/
127 :
128 39430 : static void * SfRealloc( void * pMem, int nNewSize )
129 :
130 : {
131 39430 : if( pMem == NULL )
132 38024 : return( (void *) malloc(nNewSize) );
133 : else
134 1406 : return( (void *) realloc(pMem,nNewSize) );
135 : }
136 :
137 : /************************************************************************/
138 : /* SHPTreeNodeInit() */
139 : /* */
140 : /* Initialize a tree node. */
141 : /************************************************************************/
142 :
143 302742 : static SHPTreeNode *SHPTreeNodeCreate( double * padfBoundsMin,
144 : double * padfBoundsMax )
145 :
146 : {
147 : SHPTreeNode *psTreeNode;
148 :
149 302742 : psTreeNode = (SHPTreeNode *) malloc(sizeof(SHPTreeNode));
150 302742 : if( NULL == psTreeNode )
151 0 : return NULL;
152 :
153 302742 : psTreeNode->nShapeCount = 0;
154 302742 : psTreeNode->panShapeIds = NULL;
155 302742 : psTreeNode->papsShapeObj = NULL;
156 :
157 302742 : psTreeNode->nSubNodes = 0;
158 :
159 302742 : if( padfBoundsMin != NULL )
160 302728 : memcpy( psTreeNode->adfBoundsMin, padfBoundsMin, sizeof(double) * 4 );
161 :
162 302742 : if( padfBoundsMax != NULL )
163 302728 : memcpy( psTreeNode->adfBoundsMax, padfBoundsMax, sizeof(double) * 4 );
164 :
165 302742 : return psTreeNode;
166 : }
167 :
168 :
169 : /************************************************************************/
170 : /* SHPCreateTree() */
171 : /************************************************************************/
172 :
173 : SHPTree SHPAPI_CALL1(*)
174 14 : SHPCreateTree( SHPHandle hSHP, int nDimension, int nMaxDepth,
175 : double *padfBoundsMin, double *padfBoundsMax )
176 :
177 : {
178 : SHPTree *psTree;
179 :
180 14 : if( padfBoundsMin == NULL && hSHP == NULL )
181 0 : return NULL;
182 :
183 : /* -------------------------------------------------------------------- */
184 : /* Allocate the tree object */
185 : /* -------------------------------------------------------------------- */
186 14 : psTree = (SHPTree *) malloc(sizeof(SHPTree));
187 14 : if( NULL == psTree )
188 : {
189 0 : return NULL;
190 : }
191 :
192 14 : psTree->hSHP = hSHP;
193 14 : psTree->nMaxDepth = nMaxDepth;
194 14 : psTree->nDimension = nDimension;
195 14 : psTree->nTotalCount = 0;
196 :
197 : /* -------------------------------------------------------------------- */
198 : /* If no max depth was defined, try to select a reasonable one */
199 : /* that implies approximately 8 shapes per node. */
200 : /* -------------------------------------------------------------------- */
201 14 : if( psTree->nMaxDepth == 0 && hSHP != NULL )
202 : {
203 14 : int nMaxNodeCount = 1;
204 : int nShapeCount;
205 :
206 14 : SHPGetInfo( hSHP, &nShapeCount, NULL, NULL, NULL );
207 82 : while( nMaxNodeCount*4 < nShapeCount )
208 : {
209 54 : psTree->nMaxDepth += 1;
210 54 : nMaxNodeCount = nMaxNodeCount * 2;
211 : }
212 :
213 : #ifdef USE_CPL
214 14 : CPLDebug( "Shape",
215 : "Estimated spatial index tree depth: %d",
216 : psTree->nMaxDepth );
217 : #endif
218 :
219 : /* NOTE: Due to problems with memory allocation for deep trees,
220 : * automatically estimated depth is limited up to 12 levels.
221 : * See Ticket #1594 for detailed discussion.
222 : */
223 14 : if( psTree->nMaxDepth > MAX_DEFAULT_TREE_DEPTH )
224 : {
225 0 : psTree->nMaxDepth = MAX_DEFAULT_TREE_DEPTH;
226 :
227 : #ifdef USE_CPL
228 0 : CPLDebug( "Shape",
229 : "Falling back to max number of allowed index tree levels (%d).",
230 : MAX_DEFAULT_TREE_DEPTH );
231 : #endif
232 : }
233 : }
234 :
235 : /* -------------------------------------------------------------------- */
236 : /* Allocate the root node. */
237 : /* -------------------------------------------------------------------- */
238 14 : psTree->psRoot = SHPTreeNodeCreate( padfBoundsMin, padfBoundsMax );
239 14 : if( NULL == psTree->psRoot )
240 : {
241 0 : return NULL;
242 : }
243 :
244 : /* -------------------------------------------------------------------- */
245 : /* Assign the bounds to the root node. If none are passed in, */
246 : /* use the bounds of the provided file otherwise the create */
247 : /* function will have already set the bounds. */
248 : /* -------------------------------------------------------------------- */
249 14 : assert( NULL != psTree );
250 14 : assert( NULL != psTree->psRoot );
251 :
252 14 : if( padfBoundsMin == NULL )
253 : {
254 28 : SHPGetInfo( hSHP, NULL, NULL,
255 14 : psTree->psRoot->adfBoundsMin,
256 14 : psTree->psRoot->adfBoundsMax );
257 : }
258 :
259 : /* -------------------------------------------------------------------- */
260 : /* If we have a file, insert all it's shapes into the tree. */
261 : /* -------------------------------------------------------------------- */
262 14 : if( hSHP != NULL )
263 : {
264 : int iShape, nShapeCount;
265 :
266 14 : SHPGetInfo( hSHP, &nShapeCount, NULL, NULL, NULL );
267 :
268 27038 : for( iShape = 0; iShape < nShapeCount; iShape++ )
269 : {
270 : SHPObject *psShape;
271 :
272 27024 : psShape = SHPReadObject( hSHP, iShape );
273 27024 : if( psShape != NULL )
274 : {
275 27024 : SHPTreeAddShapeId( psTree, psShape );
276 27024 : SHPDestroyObject( psShape );
277 : }
278 : }
279 : }
280 :
281 14 : return psTree;
282 : }
283 :
284 : /************************************************************************/
285 : /* SHPDestroyTreeNode() */
286 : /************************************************************************/
287 :
288 241359 : static void SHPDestroyTreeNode( SHPTreeNode * psTreeNode )
289 :
290 : {
291 : int i;
292 :
293 241359 : assert( NULL != psTreeNode );
294 :
295 281350 : for( i = 0; i < psTreeNode->nSubNodes; i++ )
296 : {
297 39991 : if( psTreeNode->apsSubNode[i] != NULL )
298 39991 : SHPDestroyTreeNode( psTreeNode->apsSubNode[i] );
299 : }
300 :
301 241359 : if( psTreeNode->panShapeIds != NULL )
302 25708 : free( psTreeNode->panShapeIds );
303 :
304 241359 : if( psTreeNode->papsShapeObj != NULL )
305 : {
306 0 : for( i = 0; i < psTreeNode->nShapeCount; i++ )
307 : {
308 0 : if( psTreeNode->papsShapeObj[i] != NULL )
309 0 : SHPDestroyObject( psTreeNode->papsShapeObj[i] );
310 : }
311 :
312 0 : free( psTreeNode->papsShapeObj );
313 : }
314 :
315 241359 : free( psTreeNode );
316 241359 : }
317 :
318 : /************************************************************************/
319 : /* SHPDestroyTree() */
320 : /************************************************************************/
321 :
322 : void SHPAPI_CALL
323 14 : SHPDestroyTree( SHPTree * psTree )
324 :
325 : {
326 14 : SHPDestroyTreeNode( psTree->psRoot );
327 14 : free( psTree );
328 14 : }
329 :
330 : /************************************************************************/
331 : /* SHPCheckBoundsOverlap() */
332 : /* */
333 : /* Do the given boxes overlap at all? */
334 : /************************************************************************/
335 :
336 : int SHPAPI_CALL
337 525334 : SHPCheckBoundsOverlap( double * padfBox1Min, double * padfBox1Max,
338 : double * padfBox2Min, double * padfBox2Max,
339 : int nDimension )
340 :
341 : {
342 : int iDim;
343 :
344 987180 : for( iDim = 0; iDim < nDimension; iDim++ )
345 : {
346 815639 : if( padfBox2Max[iDim] < padfBox1Min[iDim] )
347 199892 : return FALSE;
348 :
349 615747 : if( padfBox1Max[iDim] < padfBox2Min[iDim] )
350 153901 : return FALSE;
351 : }
352 :
353 171541 : return TRUE;
354 : }
355 :
356 : /************************************************************************/
357 : /* SHPCheckObjectContained() */
358 : /* */
359 : /* Does the given shape fit within the indicated extents? */
360 : /************************************************************************/
361 :
362 984296 : static int SHPCheckObjectContained( SHPObject * psObject, int nDimension,
363 : double * padfBoundsMin, double * padfBoundsMax )
364 :
365 : {
366 2883441 : if( psObject->dfXMin < padfBoundsMin[0]
367 2883441 : || psObject->dfXMax > padfBoundsMax[0] )
368 416526 : return FALSE;
369 :
370 1700167 : if( psObject->dfYMin < padfBoundsMin[1]
371 1700167 : || psObject->dfYMax > padfBoundsMax[1] )
372 227066 : return FALSE;
373 :
374 340704 : if( nDimension == 2 )
375 340704 : return TRUE;
376 :
377 0 : if( psObject->dfZMin < padfBoundsMin[2]
378 0 : || psObject->dfZMax > padfBoundsMax[2] )
379 0 : return FALSE;
380 :
381 0 : if( nDimension == 3 )
382 0 : return TRUE;
383 :
384 0 : if( psObject->dfMMin < padfBoundsMin[3]
385 0 : || psObject->dfMMax > padfBoundsMax[3] )
386 0 : return FALSE;
387 :
388 0 : return TRUE;
389 : }
390 :
391 : /************************************************************************/
392 : /* SHPTreeSplitBounds() */
393 : /* */
394 : /* Split a region into two subregion evenly, cutting along the */
395 : /* longest dimension. */
396 : /************************************************************************/
397 :
398 : void SHPAPI_CALL
399 257052 : SHPTreeSplitBounds( double *padfBoundsMinIn, double *padfBoundsMaxIn,
400 : double *padfBoundsMin1, double * padfBoundsMax1,
401 : double *padfBoundsMin2, double * padfBoundsMax2 )
402 :
403 : {
404 : /* -------------------------------------------------------------------- */
405 : /* The output bounds will be very similar to the input bounds, */
406 : /* so just copy over to start. */
407 : /* -------------------------------------------------------------------- */
408 257052 : memcpy( padfBoundsMin1, padfBoundsMinIn, sizeof(double) * 4 );
409 257052 : memcpy( padfBoundsMax1, padfBoundsMaxIn, sizeof(double) * 4 );
410 257052 : memcpy( padfBoundsMin2, padfBoundsMinIn, sizeof(double) * 4 );
411 257052 : memcpy( padfBoundsMax2, padfBoundsMaxIn, sizeof(double) * 4 );
412 :
413 : /* -------------------------------------------------------------------- */
414 : /* Split in X direction. */
415 : /* -------------------------------------------------------------------- */
416 514104 : if( (padfBoundsMaxIn[0] - padfBoundsMinIn[0])
417 257052 : > (padfBoundsMaxIn[1] - padfBoundsMinIn[1]) )
418 : {
419 164338 : double dfRange = padfBoundsMaxIn[0] - padfBoundsMinIn[0];
420 :
421 164338 : padfBoundsMax1[0] = padfBoundsMinIn[0] + dfRange * SHP_SPLIT_RATIO;
422 164338 : padfBoundsMin2[0] = padfBoundsMaxIn[0] - dfRange * SHP_SPLIT_RATIO;
423 : }
424 :
425 : /* -------------------------------------------------------------------- */
426 : /* Otherwise split in Y direction. */
427 : /* -------------------------------------------------------------------- */
428 : else
429 : {
430 92714 : double dfRange = padfBoundsMaxIn[1] - padfBoundsMinIn[1];
431 :
432 92714 : padfBoundsMax1[1] = padfBoundsMinIn[1] + dfRange * SHP_SPLIT_RATIO;
433 92714 : padfBoundsMin2[1] = padfBoundsMaxIn[1] - dfRange * SHP_SPLIT_RATIO;
434 : }
435 257052 : }
436 :
437 : /************************************************************************/
438 : /* SHPTreeNodeAddShapeId() */
439 : /************************************************************************/
440 :
441 : static int
442 367728 : SHPTreeNodeAddShapeId( SHPTreeNode * psTreeNode, SHPObject * psObject,
443 : int nMaxDepth, int nDimension )
444 :
445 : {
446 : int i;
447 :
448 : /* -------------------------------------------------------------------- */
449 : /* If there are subnodes, then consider wiether this object */
450 : /* will fit in them. */
451 : /* -------------------------------------------------------------------- */
452 367734 : if( nMaxDepth > 1 && psTreeNode->nSubNodes > 0 )
453 : {
454 721947 : for( i = 0; i < psTreeNode->nSubNodes; i++ )
455 : {
456 1443882 : if( SHPCheckObjectContained(psObject, nDimension,
457 721941 : psTreeNode->apsSubNode[i]->adfBoundsMin,
458 721941 : psTreeNode->apsSubNode[i]->adfBoundsMax))
459 : {
460 265022 : return SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[i],
461 : psObject, nMaxDepth-1,
462 : nDimension );
463 : }
464 : }
465 : }
466 :
467 : /* -------------------------------------------------------------------- */
468 : /* Otherwise, consider creating four subnodes if could fit into */
469 : /* them, and adding to the appropriate subnode. */
470 : /* -------------------------------------------------------------------- */
471 : #if MAX_SUBNODE == 4
472 102700 : else if( nMaxDepth > 1 && psTreeNode->nSubNodes == 0 )
473 : {
474 : double adfBoundsMinH1[4], adfBoundsMaxH1[4];
475 : double adfBoundsMinH2[4], adfBoundsMaxH2[4];
476 : double adfBoundsMin1[4], adfBoundsMax1[4];
477 : double adfBoundsMin2[4], adfBoundsMax2[4];
478 : double adfBoundsMin3[4], adfBoundsMax3[4];
479 : double adfBoundsMin4[4], adfBoundsMax4[4];
480 :
481 85684 : SHPTreeSplitBounds( psTreeNode->adfBoundsMin,
482 : psTreeNode->adfBoundsMax,
483 : adfBoundsMinH1, adfBoundsMaxH1,
484 : adfBoundsMinH2, adfBoundsMaxH2 );
485 :
486 85684 : SHPTreeSplitBounds( adfBoundsMinH1, adfBoundsMaxH1,
487 : adfBoundsMin1, adfBoundsMax1,
488 : adfBoundsMin2, adfBoundsMax2 );
489 :
490 85684 : SHPTreeSplitBounds( adfBoundsMinH2, adfBoundsMaxH2,
491 : adfBoundsMin3, adfBoundsMax3,
492 : adfBoundsMin4, adfBoundsMax4 );
493 :
494 262355 : if( SHPCheckObjectContained(psObject, nDimension,
495 : adfBoundsMin1, adfBoundsMax1)
496 85684 : || SHPCheckObjectContained(psObject, nDimension,
497 : adfBoundsMin2, adfBoundsMax2)
498 75431 : || SHPCheckObjectContained(psObject, nDimension,
499 : adfBoundsMin3, adfBoundsMax3)
500 60749 : || SHPCheckObjectContained(psObject, nDimension,
501 40491 : adfBoundsMin4, adfBoundsMax4) )
502 : {
503 75682 : psTreeNode->nSubNodes = 4;
504 75682 : psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
505 : adfBoundsMax1 );
506 75682 : psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
507 : adfBoundsMax2 );
508 75682 : psTreeNode->apsSubNode[2] = SHPTreeNodeCreate( adfBoundsMin3,
509 : adfBoundsMax3 );
510 75682 : psTreeNode->apsSubNode[3] = SHPTreeNodeCreate( adfBoundsMin4,
511 : adfBoundsMax4 );
512 :
513 : /* recurse back on this node now that it has subnodes */
514 75682 : return( SHPTreeNodeAddShapeId( psTreeNode, psObject,
515 : nMaxDepth, nDimension ) );
516 : }
517 : }
518 : #endif /* MAX_SUBNODE == 4 */
519 :
520 : /* -------------------------------------------------------------------- */
521 : /* Otherwise, consider creating two subnodes if could fit into */
522 : /* them, and adding to the appropriate subnode. */
523 : /* -------------------------------------------------------------------- */
524 : #if MAX_SUBNODE == 2
525 : else if( nMaxDepth > 1 && psTreeNode->nSubNodes == 0 )
526 : {
527 : double adfBoundsMin1[4], adfBoundsMax1[4];
528 : double adfBoundsMin2[4], adfBoundsMax2[4];
529 :
530 : SHPTreeSplitBounds( psTreeNode->adfBoundsMin, psTreeNode->adfBoundsMax,
531 : adfBoundsMin1, adfBoundsMax1,
532 : adfBoundsMin2, adfBoundsMax2 );
533 :
534 : if( SHPCheckObjectContained(psObject, nDimension,
535 : adfBoundsMin1, adfBoundsMax1))
536 : {
537 : psTreeNode->nSubNodes = 2;
538 : psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
539 : adfBoundsMax1 );
540 : psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
541 : adfBoundsMax2 );
542 :
543 : return( SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[0], psObject,
544 : nMaxDepth - 1, nDimension ) );
545 : }
546 : else if( SHPCheckObjectContained(psObject, nDimension,
547 : adfBoundsMin2, adfBoundsMax2) )
548 : {
549 : psTreeNode->nSubNodes = 2;
550 : psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
551 : adfBoundsMax1 );
552 : psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
553 : adfBoundsMax2 );
554 :
555 : return( SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[1], psObject,
556 : nMaxDepth - 1, nDimension ) );
557 : }
558 : }
559 : #endif /* MAX_SUBNODE == 2 */
560 :
561 : /* -------------------------------------------------------------------- */
562 : /* If none of that worked, just add it to this nodes list. */
563 : /* -------------------------------------------------------------------- */
564 27024 : psTreeNode->nShapeCount++;
565 :
566 54048 : psTreeNode->panShapeIds = (int *)
567 27024 : SfRealloc( psTreeNode->panShapeIds,
568 : sizeof(int) * psTreeNode->nShapeCount );
569 27024 : psTreeNode->panShapeIds[psTreeNode->nShapeCount-1] = psObject->nShapeId;
570 :
571 27024 : if( psTreeNode->papsShapeObj != NULL )
572 : {
573 0 : psTreeNode->papsShapeObj = (SHPObject **)
574 0 : SfRealloc( psTreeNode->papsShapeObj,
575 : sizeof(void *) * psTreeNode->nShapeCount );
576 0 : psTreeNode->papsShapeObj[psTreeNode->nShapeCount-1] = NULL;
577 : }
578 :
579 27024 : return TRUE;
580 : }
581 :
582 : /************************************************************************/
583 : /* SHPTreeAddShapeId() */
584 : /* */
585 : /* Add a shape to the tree, but don't keep a pointer to the */
586 : /* object data, just keep the shapeid. */
587 : /************************************************************************/
588 :
589 : int SHPAPI_CALL
590 27024 : SHPTreeAddShapeId( SHPTree * psTree, SHPObject * psObject )
591 :
592 : {
593 27024 : psTree->nTotalCount++;
594 :
595 27024 : return( SHPTreeNodeAddShapeId( psTree->psRoot, psObject,
596 : psTree->nMaxDepth, psTree->nDimension ) );
597 : }
598 :
599 : /************************************************************************/
600 : /* SHPTreeCollectShapesIds() */
601 : /* */
602 : /* Work function implementing SHPTreeFindLikelyShapes() on a */
603 : /* tree node by tree node basis. */
604 : /************************************************************************/
605 :
606 : void SHPAPI_CALL
607 0 : SHPTreeCollectShapeIds( SHPTree *hTree, SHPTreeNode * psTreeNode,
608 : double * padfBoundsMin, double * padfBoundsMax,
609 : int * pnShapeCount, int * pnMaxShapes,
610 : int ** ppanShapeList )
611 :
612 : {
613 : int i;
614 :
615 : /* -------------------------------------------------------------------- */
616 : /* Does this node overlap the area of interest at all? If not, */
617 : /* return without adding to the list at all. */
618 : /* -------------------------------------------------------------------- */
619 0 : if( !SHPCheckBoundsOverlap( psTreeNode->adfBoundsMin,
620 : psTreeNode->adfBoundsMax,
621 : padfBoundsMin,
622 : padfBoundsMax,
623 : hTree->nDimension ) )
624 0 : return;
625 :
626 : /* -------------------------------------------------------------------- */
627 : /* Grow the list to hold the shapes on this node. */
628 : /* -------------------------------------------------------------------- */
629 0 : if( *pnShapeCount + psTreeNode->nShapeCount > *pnMaxShapes )
630 : {
631 0 : *pnMaxShapes = (*pnShapeCount + psTreeNode->nShapeCount) * 2 + 20;
632 0 : *ppanShapeList = (int *)
633 0 : SfRealloc(*ppanShapeList,sizeof(int) * *pnMaxShapes);
634 : }
635 :
636 : /* -------------------------------------------------------------------- */
637 : /* Add the local nodes shapeids to the list. */
638 : /* -------------------------------------------------------------------- */
639 0 : for( i = 0; i < psTreeNode->nShapeCount; i++ )
640 : {
641 0 : (*ppanShapeList)[(*pnShapeCount)++] = psTreeNode->panShapeIds[i];
642 : }
643 :
644 : /* -------------------------------------------------------------------- */
645 : /* Recurse to subnodes if they exist. */
646 : /* -------------------------------------------------------------------- */
647 0 : for( i = 0; i < psTreeNode->nSubNodes; i++ )
648 : {
649 0 : if( psTreeNode->apsSubNode[i] != NULL )
650 0 : SHPTreeCollectShapeIds( hTree, psTreeNode->apsSubNode[i],
651 : padfBoundsMin, padfBoundsMax,
652 : pnShapeCount, pnMaxShapes,
653 : ppanShapeList );
654 : }
655 : }
656 :
657 : /************************************************************************/
658 : /* SHPTreeFindLikelyShapes() */
659 : /* */
660 : /* Find all shapes within tree nodes for which the tree node */
661 : /* bounding box overlaps the search box. The return value is */
662 : /* an array of shapeids terminated by a -1. The shapeids will */
663 : /* be in order, as hopefully this will result in faster (more */
664 : /* sequential) reading from the file. */
665 : /************************************************************************/
666 :
667 : /* helper for qsort */
668 : static int
669 892856 : compare_ints( const void * a, const void * b)
670 : {
671 892856 : return (*(int*)a) - (*(int*)b);
672 : }
673 :
674 : int SHPAPI_CALL1(*)
675 0 : SHPTreeFindLikelyShapes( SHPTree * hTree,
676 : double * padfBoundsMin, double * padfBoundsMax,
677 : int * pnShapeCount )
678 :
679 : {
680 0 : int *panShapeList=NULL, nMaxShapes = 0;
681 :
682 : /* -------------------------------------------------------------------- */
683 : /* Perform the search by recursive descent. */
684 : /* -------------------------------------------------------------------- */
685 0 : *pnShapeCount = 0;
686 :
687 0 : SHPTreeCollectShapeIds( hTree, hTree->psRoot,
688 : padfBoundsMin, padfBoundsMax,
689 : pnShapeCount, &nMaxShapes,
690 : &panShapeList );
691 :
692 : /* -------------------------------------------------------------------- */
693 : /* Sort the id array */
694 : /* -------------------------------------------------------------------- */
695 :
696 0 : qsort(panShapeList, *pnShapeCount, sizeof(int), compare_ints);
697 :
698 0 : return panShapeList;
699 : }
700 :
701 : /************************************************************************/
702 : /* SHPTreeNodeTrim() */
703 : /* */
704 : /* This is the recurve version of SHPTreeTrimExtraNodes() that */
705 : /* walks the tree cleaning it up. */
706 : /************************************************************************/
707 :
708 302742 : static int SHPTreeNodeTrim( SHPTreeNode * psTreeNode )
709 :
710 : {
711 : int i;
712 :
713 : /* -------------------------------------------------------------------- */
714 : /* Trim subtrees, and free subnodes that come back empty. */
715 : /* -------------------------------------------------------------------- */
716 605470 : for( i = 0; i < psTreeNode->nSubNodes; i++ )
717 : {
718 302728 : if( SHPTreeNodeTrim( psTreeNode->apsSubNode[i] ) )
719 : {
720 201354 : SHPDestroyTreeNode( psTreeNode->apsSubNode[i] );
721 :
722 402708 : psTreeNode->apsSubNode[i] =
723 201354 : psTreeNode->apsSubNode[psTreeNode->nSubNodes-1];
724 :
725 201354 : psTreeNode->nSubNodes--;
726 :
727 201354 : i--; /* process the new occupant of this subnode entry */
728 : }
729 : }
730 :
731 : /* -------------------------------------------------------------------- */
732 : /* If the current node has 1 subnode and no shapes, promote that */
733 : /* subnode to the current node position. */
734 : /* -------------------------------------------------------------------- */
735 302742 : if( psTreeNode->nSubNodes == 1 && psTreeNode->nShapeCount == 0)
736 : {
737 61383 : SHPTreeNode* psSubNode = psTreeNode->apsSubNode[0];
738 :
739 61383 : memcpy(psTreeNode->adfBoundsMin, psSubNode->adfBoundsMin,
740 : sizeof(psSubNode->adfBoundsMin));
741 61383 : memcpy(psTreeNode->adfBoundsMax, psSubNode->adfBoundsMax,
742 : sizeof(psSubNode->adfBoundsMax));
743 61383 : psTreeNode->nShapeCount = psSubNode->nShapeCount;
744 61383 : assert(psTreeNode->panShapeIds == NULL);
745 61383 : psTreeNode->panShapeIds = psSubNode->panShapeIds;
746 61383 : assert(psTreeNode->papsShapeObj == NULL);
747 61383 : psTreeNode->papsShapeObj = psSubNode->papsShapeObj;
748 61383 : psTreeNode->nSubNodes = psSubNode->nSubNodes;
749 62975 : for( i = 0; i < psSubNode->nSubNodes; i++ )
750 1592 : psTreeNode->apsSubNode[i] = psSubNode->apsSubNode[i];
751 61383 : free(psSubNode);
752 : }
753 :
754 : /* -------------------------------------------------------------------- */
755 : /* We should be trimmed if we have no subnodes, and no shapes. */
756 : /* -------------------------------------------------------------------- */
757 302742 : return( psTreeNode->nSubNodes == 0 && psTreeNode->nShapeCount == 0 );
758 : }
759 :
760 : /************************************************************************/
761 : /* SHPTreeTrimExtraNodes() */
762 : /* */
763 : /* Trim empty nodes from the tree. Note that we never trim an */
764 : /* empty root node. */
765 : /************************************************************************/
766 :
767 : void SHPAPI_CALL
768 14 : SHPTreeTrimExtraNodes( SHPTree * hTree )
769 :
770 : {
771 14 : SHPTreeNodeTrim( hTree->psRoot );
772 14 : }
773 :
774 : /************************************************************************/
775 : /* SwapWord() */
776 : /* */
777 : /* Swap a 2, 4 or 8 byte word. */
778 : /************************************************************************/
779 :
780 0 : static void SwapWord( int length, void * wordP )
781 :
782 : {
783 : int i;
784 : unsigned char temp;
785 :
786 0 : for( i=0; i < length/2; i++ )
787 : {
788 0 : temp = ((unsigned char *) wordP)[i];
789 0 : ((unsigned char *)wordP)[i] = ((unsigned char *) wordP)[length-i-1];
790 0 : ((unsigned char *) wordP)[length-i-1] = temp;
791 : }
792 0 : }
793 :
794 :
795 : struct SHPDiskTreeInfo
796 : {
797 : SAHooks sHooks;
798 : SAFile fpQIX;
799 : };
800 :
801 : /************************************************************************/
802 : /* SHPOpenDiskTree() */
803 : /************************************************************************/
804 :
805 1287 : SHPTreeDiskHandle SHPOpenDiskTree( const char* pszQIXFilename,
806 : SAHooks *psHooks )
807 : {
808 : SHPTreeDiskHandle hDiskTree;
809 :
810 1287 : hDiskTree = (SHPTreeDiskHandle) calloc(sizeof(struct SHPDiskTreeInfo),1);
811 :
812 1287 : if (psHooks == NULL)
813 1287 : SASetupDefaultHooks( &(hDiskTree->sHooks) );
814 : else
815 0 : memcpy( &(hDiskTree->sHooks), psHooks, sizeof(SAHooks) );
816 :
817 1287 : hDiskTree->fpQIX = hDiskTree->sHooks.FOpen(pszQIXFilename, "rb");
818 1287 : if (hDiskTree->fpQIX == NULL)
819 : {
820 1258 : free(hDiskTree);
821 1258 : return NULL;
822 : }
823 :
824 29 : return hDiskTree;
825 : }
826 :
827 : /***********************************************************************/
828 : /* SHPCloseDiskTree() */
829 : /************************************************************************/
830 :
831 29 : void SHPCloseDiskTree( SHPTreeDiskHandle hDiskTree )
832 : {
833 29 : if (hDiskTree == NULL)
834 0 : return;
835 :
836 29 : hDiskTree->sHooks.FClose(hDiskTree->fpQIX);
837 29 : free(hDiskTree);
838 : }
839 :
840 : /************************************************************************/
841 : /* SHPSearchDiskTreeNode() */
842 : /************************************************************************/
843 :
844 : static int
845 525334 : SHPSearchDiskTreeNode( SHPTreeDiskHandle hDiskTree, double *padfBoundsMin, double *padfBoundsMax,
846 : int **ppanResultBuffer, int *pnBufferMax,
847 : int *pnResultCount, int bNeedSwap, int nRecLevel )
848 :
849 : {
850 : unsigned int i;
851 : unsigned int offset;
852 : unsigned int numshapes, numsubnodes;
853 : double adfNodeBoundsMin[2], adfNodeBoundsMax[2];
854 : int nFReadAcc;
855 :
856 : /* -------------------------------------------------------------------- */
857 : /* Read and unswap first part of node info. */
858 : /* -------------------------------------------------------------------- */
859 525334 : nFReadAcc = (int)hDiskTree->sHooks.FRead( &offset, 4, 1, hDiskTree->fpQIX );
860 525334 : if ( bNeedSwap ) SwapWord ( 4, &offset );
861 :
862 525334 : nFReadAcc += (int)hDiskTree->sHooks.FRead( adfNodeBoundsMin, sizeof(double), 2, hDiskTree->fpQIX );
863 525334 : nFReadAcc += (int)hDiskTree->sHooks.FRead( adfNodeBoundsMax, sizeof(double), 2, hDiskTree->fpQIX );
864 525334 : if ( bNeedSwap )
865 : {
866 0 : SwapWord( 8, adfNodeBoundsMin + 0 );
867 0 : SwapWord( 8, adfNodeBoundsMin + 1 );
868 0 : SwapWord( 8, adfNodeBoundsMax + 0 );
869 0 : SwapWord( 8, adfNodeBoundsMax + 1 );
870 : }
871 :
872 525334 : nFReadAcc += (int)hDiskTree->sHooks.FRead( &numshapes, 4, 1, hDiskTree->fpQIX );
873 525334 : if ( bNeedSwap ) SwapWord ( 4, &numshapes );
874 :
875 : /* Check that we could read all previous values */
876 525334 : if( nFReadAcc != 1 + 2 + 2 + 1 )
877 : {
878 0 : hDiskTree->sHooks.Error("I/O error");
879 0 : return FALSE;
880 : }
881 :
882 : /* Sanity checks to avoid int overflows in later computation */
883 525334 : if( offset > INT_MAX - sizeof(int) )
884 : {
885 0 : hDiskTree->sHooks.Error("Invalid value for offset");
886 0 : return FALSE;
887 : }
888 :
889 1050668 : if( numshapes > (INT_MAX - offset - sizeof(int)) / sizeof(int) ||
890 525334 : numshapes > INT_MAX / sizeof(int) - *pnResultCount )
891 : {
892 0 : hDiskTree->sHooks.Error("Invalid value for numshapes");
893 0 : return FALSE;
894 : }
895 :
896 : /* -------------------------------------------------------------------- */
897 : /* If we don't overlap this node at all, we can just fseek() */
898 : /* pass this node info and all subnodes. */
899 : /* -------------------------------------------------------------------- */
900 525334 : if( !SHPCheckBoundsOverlap( adfNodeBoundsMin, adfNodeBoundsMax,
901 : padfBoundsMin, padfBoundsMax, 2 ) )
902 : {
903 353793 : offset += numshapes*sizeof(int) + sizeof(int);
904 353793 : hDiskTree->sHooks.FSeek(hDiskTree->fpQIX, offset, SEEK_CUR);
905 353793 : return TRUE;
906 : }
907 :
908 : /* -------------------------------------------------------------------- */
909 : /* Add all the shapeids at this node to our list. */
910 : /* -------------------------------------------------------------------- */
911 171541 : if(numshapes > 0)
912 : {
913 24641 : if( *pnResultCount + numshapes > *pnBufferMax )
914 : {
915 : int* pNewBuffer;
916 :
917 12406 : *pnBufferMax = (*pnResultCount + numshapes + 100) * 5 / 4;
918 :
919 12406 : if( *pnBufferMax > INT_MAX / sizeof(int) )
920 0 : *pnBufferMax = *pnResultCount + numshapes;
921 :
922 24812 : pNewBuffer = (int *)
923 24812 : SfRealloc( *ppanResultBuffer, *pnBufferMax * sizeof(int) );
924 :
925 12406 : if( pNewBuffer == NULL )
926 : {
927 0 : hDiskTree->sHooks.Error("Out of memory error");
928 0 : return FALSE;
929 : }
930 :
931 12406 : *ppanResultBuffer = pNewBuffer;
932 : }
933 :
934 24641 : if( hDiskTree->sHooks.FRead( *ppanResultBuffer + *pnResultCount,
935 : sizeof(int), numshapes, hDiskTree->fpQIX ) != numshapes )
936 : {
937 0 : hDiskTree->sHooks.Error("I/O error");
938 0 : return FALSE;
939 : }
940 :
941 24641 : if (bNeedSwap )
942 : {
943 0 : for( i=0; i<numshapes; i++ )
944 0 : SwapWord( 4, *ppanResultBuffer + *pnResultCount + i );
945 : }
946 :
947 24641 : *pnResultCount += numshapes;
948 : }
949 :
950 : /* -------------------------------------------------------------------- */
951 : /* Process the subnodes. */
952 : /* -------------------------------------------------------------------- */
953 171541 : if( hDiskTree->sHooks.FRead( &numsubnodes, 4, 1, hDiskTree->fpQIX ) != 1 )
954 : {
955 0 : hDiskTree->sHooks.Error("I/O error");
956 0 : return FALSE;
957 : }
958 171541 : if ( bNeedSwap ) SwapWord ( 4, &numsubnodes );
959 171541 : if( numsubnodes > 0 && nRecLevel == 32 )
960 : {
961 0 : hDiskTree->sHooks.Error("Shape tree is too deep");
962 0 : return FALSE;
963 : }
964 :
965 684559 : for(i=0; i<numsubnodes; i++)
966 : {
967 513018 : if( !SHPSearchDiskTreeNode( hDiskTree, padfBoundsMin, padfBoundsMax,
968 : ppanResultBuffer, pnBufferMax,
969 : pnResultCount, bNeedSwap, nRecLevel + 1 ) )
970 0 : return FALSE;
971 : }
972 :
973 171541 : return TRUE;
974 : }
975 :
976 : /************************************************************************/
977 : /* SHPTreeReadLibc() */
978 : /************************************************************************/
979 :
980 : static
981 0 : SAOffset SHPTreeReadLibc( void *p, SAOffset size, SAOffset nmemb, SAFile file )
982 :
983 : {
984 0 : return (SAOffset) fread( p, (size_t) size, (size_t) nmemb,
985 : (FILE *) file );
986 : }
987 :
988 : /************************************************************************/
989 : /* SHPTreeSeekLibc() */
990 : /************************************************************************/
991 :
992 : static
993 0 : SAOffset SHPTreeSeekLibc( SAFile file, SAOffset offset, int whence )
994 :
995 : {
996 0 : return (SAOffset) fseek( (FILE *) file, (long) offset, whence );
997 : }
998 :
999 : /************************************************************************/
1000 : /* SHPSearchDiskTree() */
1001 : /************************************************************************/
1002 :
1003 : int SHPAPI_CALL1(*)
1004 0 : SHPSearchDiskTree( FILE *fp,
1005 : double *padfBoundsMin, double *padfBoundsMax,
1006 : int *pnShapeCount )
1007 : {
1008 : struct SHPDiskTreeInfo sDiskTree;
1009 0 : memset(&sDiskTree.sHooks, 0, sizeof(sDiskTree.sHooks));
1010 :
1011 : /* We do not use SASetupDefaultHooks() because the FILE* */
1012 : /* is a libc FILE* */
1013 0 : sDiskTree.sHooks.FSeek = SHPTreeSeekLibc;
1014 0 : sDiskTree.sHooks.FRead = SHPTreeReadLibc;
1015 :
1016 0 : sDiskTree.fpQIX = (SAFile)fp;
1017 :
1018 0 : return SHPSearchDiskTreeEx( &sDiskTree, padfBoundsMin, padfBoundsMax,
1019 : pnShapeCount );
1020 : }
1021 :
1022 : /***********************************************************************/
1023 : /* SHPSearchDiskTreeEx() */
1024 : /************************************************************************/
1025 :
1026 12316 : int* SHPSearchDiskTreeEx( SHPTreeDiskHandle hDiskTree,
1027 : double *padfBoundsMin, double *padfBoundsMax,
1028 : int *pnShapeCount )
1029 :
1030 : {
1031 12316 : int i, bNeedSwap, nBufferMax = 0;
1032 : unsigned char abyBuf[16];
1033 12316 : int *panResultBuffer = NULL;
1034 :
1035 12316 : *pnShapeCount = 0;
1036 :
1037 : /* -------------------------------------------------------------------- */
1038 : /* Establish the byte order on this machine. */
1039 : /* -------------------------------------------------------------------- */
1040 12316 : i = 1;
1041 12316 : if( *((unsigned char *) &i) == 1 )
1042 12316 : bBigEndian = FALSE;
1043 : else
1044 0 : bBigEndian = TRUE;
1045 :
1046 : /* -------------------------------------------------------------------- */
1047 : /* Read the header. */
1048 : /* -------------------------------------------------------------------- */
1049 12316 : hDiskTree->sHooks.FSeek( hDiskTree->fpQIX, 0, SEEK_SET );
1050 12316 : hDiskTree->sHooks.FRead( abyBuf, 16, 1, hDiskTree->fpQIX );
1051 :
1052 12316 : if( memcmp( abyBuf, "SQT", 3 ) != 0 )
1053 0 : return NULL;
1054 :
1055 49264 : if( (abyBuf[3] == 2 && bBigEndian)
1056 24632 : || (abyBuf[3] == 1 && !bBigEndian) )
1057 12316 : bNeedSwap = FALSE;
1058 : else
1059 0 : bNeedSwap = TRUE;
1060 :
1061 : /* -------------------------------------------------------------------- */
1062 : /* Search through root node and it's decendents. */
1063 : /* -------------------------------------------------------------------- */
1064 12316 : if( !SHPSearchDiskTreeNode( hDiskTree, padfBoundsMin, padfBoundsMax,
1065 : &panResultBuffer, &nBufferMax,
1066 : pnShapeCount, bNeedSwap, 0 ) )
1067 : {
1068 0 : if( panResultBuffer != NULL )
1069 0 : free( panResultBuffer );
1070 0 : *pnShapeCount = 0;
1071 0 : return NULL;
1072 : }
1073 : /* -------------------------------------------------------------------- */
1074 : /* Sort the id array */
1075 : /* -------------------------------------------------------------------- */
1076 12316 : qsort(panResultBuffer, *pnShapeCount, sizeof(int), compare_ints);
1077 :
1078 : /* To distinguish between empty intersection from error case */
1079 12316 : if( panResultBuffer == NULL )
1080 0 : panResultBuffer = (int*) calloc(1, sizeof(int));
1081 :
1082 12316 : return panResultBuffer;
1083 : }
1084 :
1085 : /************************************************************************/
1086 : /* SHPGetSubNodeOffset() */
1087 : /* */
1088 : /* Determine how big all the subnodes of this node (and their */
1089 : /* children) will be. This will allow disk based searchers to */
1090 : /* seek past them all efficiently. */
1091 : /************************************************************************/
1092 :
1093 320600 : static int SHPGetSubNodeOffset( SHPTreeNode *node)
1094 : {
1095 : int i;
1096 320600 : long offset=0;
1097 :
1098 601195 : for(i=0; i<node->nSubNodes; i++ )
1099 : {
1100 280595 : if(node->apsSubNode[i])
1101 : {
1102 280595 : offset += 4*sizeof(double)
1103 280595 : + (node->apsSubNode[i]->nShapeCount+3)*sizeof(int);
1104 280595 : offset += SHPGetSubNodeOffset(node->apsSubNode[i]);
1105 : }
1106 : }
1107 :
1108 320600 : return(offset);
1109 : }
1110 :
1111 : /************************************************************************/
1112 : /* SHPWriteTreeNode() */
1113 : /************************************************************************/
1114 :
1115 40005 : static void SHPWriteTreeNode( SAFile fp, SHPTreeNode *node, SAHooks* psHooks)
1116 : {
1117 : int i,j;
1118 : int offset;
1119 40005 : unsigned char *pabyRec = NULL;
1120 40005 : assert( NULL != node );
1121 :
1122 40005 : offset = SHPGetSubNodeOffset(node);
1123 :
1124 40005 : pabyRec = (unsigned char *)
1125 : malloc(sizeof(double) * 4
1126 : + (3 * sizeof(int)) + (node->nShapeCount * sizeof(int)) );
1127 40005 : if( NULL == pabyRec )
1128 : {
1129 : #ifdef USE_CPL
1130 0 : CPLError( CE_Fatal, CPLE_OutOfMemory, "Memory allocation failure");
1131 : #endif
1132 0 : assert( 0 );
1133 : return;
1134 : }
1135 :
1136 40005 : memcpy( pabyRec, &offset, 4);
1137 :
1138 : /* minx, miny, maxx, maxy */
1139 40005 : memcpy( pabyRec+ 4, node->adfBoundsMin+0, sizeof(double) );
1140 40005 : memcpy( pabyRec+12, node->adfBoundsMin+1, sizeof(double) );
1141 40005 : memcpy( pabyRec+20, node->adfBoundsMax+0, sizeof(double) );
1142 40005 : memcpy( pabyRec+28, node->adfBoundsMax+1, sizeof(double) );
1143 :
1144 40005 : memcpy( pabyRec+36, &node->nShapeCount, 4);
1145 40005 : j = node->nShapeCount * sizeof(int);
1146 40005 : memcpy( pabyRec+40, node->panShapeIds, j);
1147 40005 : memcpy( pabyRec+j+40, &node->nSubNodes, 4);
1148 :
1149 40005 : psHooks->FWrite( pabyRec, 44+j, 1, fp );
1150 40005 : free (pabyRec);
1151 :
1152 79996 : for(i=0; i<node->nSubNodes; i++ )
1153 : {
1154 39991 : if(node->apsSubNode[i])
1155 39991 : SHPWriteTreeNode( fp, node->apsSubNode[i], psHooks);
1156 : }
1157 : }
1158 :
1159 : /************************************************************************/
1160 : /* SHPWriteTree() */
1161 : /************************************************************************/
1162 :
1163 14 : int SHPAPI_CALL SHPWriteTree(SHPTree *tree, const char *filename )
1164 : {
1165 : SAHooks sHooks;
1166 :
1167 14 : SASetupDefaultHooks( &sHooks );
1168 :
1169 14 : return SHPWriteTreeLL(tree, filename, &sHooks);
1170 : }
1171 :
1172 : /************************************************************************/
1173 : /* SHPWriteTreeLL() */
1174 : /************************************************************************/
1175 :
1176 14 : int SHPWriteTreeLL(SHPTree *tree, const char *filename, SAHooks* psHooks )
1177 : {
1178 14 : char signature[4] = "SQT";
1179 : int i;
1180 : char abyBuf[32];
1181 : SAFile fp;
1182 :
1183 : SAHooks sHooks;
1184 14 : if (psHooks == NULL)
1185 : {
1186 0 : SASetupDefaultHooks( &sHooks );
1187 0 : psHooks = &sHooks;
1188 : }
1189 :
1190 : /* -------------------------------------------------------------------- */
1191 : /* Open the output file. */
1192 : /* -------------------------------------------------------------------- */
1193 14 : fp = psHooks->FOpen(filename, "wb");
1194 14 : if( fp == NULL )
1195 : {
1196 0 : return FALSE;
1197 : }
1198 :
1199 : /* -------------------------------------------------------------------- */
1200 : /* Establish the byte order on this machine. */
1201 : /* -------------------------------------------------------------------- */
1202 14 : i = 1;
1203 14 : if( *((unsigned char *) &i) == 1 )
1204 14 : bBigEndian = FALSE;
1205 : else
1206 0 : bBigEndian = TRUE;
1207 :
1208 : /* -------------------------------------------------------------------- */
1209 : /* Write the header. */
1210 : /* -------------------------------------------------------------------- */
1211 14 : memcpy( abyBuf+0, signature, 3 );
1212 :
1213 14 : if( bBigEndian )
1214 0 : abyBuf[3] = 2; /* New MSB */
1215 : else
1216 14 : abyBuf[3] = 1; /* New LSB */
1217 :
1218 14 : abyBuf[4] = 1; /* version */
1219 14 : abyBuf[5] = 0; /* next 3 reserved */
1220 14 : abyBuf[6] = 0;
1221 14 : abyBuf[7] = 0;
1222 :
1223 14 : psHooks->FWrite( abyBuf, 8, 1, fp );
1224 :
1225 14 : psHooks->FWrite( &(tree->nTotalCount), 4, 1, fp );
1226 :
1227 : /* write maxdepth */
1228 :
1229 14 : psHooks->FWrite( &(tree->nMaxDepth), 4, 1, fp );
1230 :
1231 : /* -------------------------------------------------------------------- */
1232 : /* Write all the nodes "in order". */
1233 : /* -------------------------------------------------------------------- */
1234 :
1235 14 : SHPWriteTreeNode( fp, tree->psRoot, psHooks );
1236 :
1237 14 : psHooks->FClose( fp );
1238 :
1239 14 : return TRUE;
1240 : }
|
