#include "shapefil.h"
#include <math.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

Include dependency graph for shptree.c:

Go to the source code of this file.

Classes
struct	SHPDiskTreeInfo

Macros
#define	TRUE 1

#define	FALSE 0

#define	SHP_SPLIT_RATIO 0.55

#define	STATIC_CAST(type, x) ((type)(x))

#define	REINTERPRET_CAST(type, x) ((type)(x))

#define	CONST_CAST(type, x) ((type)(x))

#define	SHPLIB_NULLPTR NULL

Functions
static const char *	cvsid_aw ()

static void *	SfRealloc (void *pMem, int nNewSize)

static SHPTreeNode *	SHPTreeNodeCreate (double padfBoundsMin, double padfBoundsMax)

SHPTree *	SHPCreateTree (SHPHandle hSHP, int nDimension, int nMaxDepth, double padfBoundsMin, double padfBoundsMax)

static void	SHPDestroyTreeNode (SHPTreeNode *psTreeNode)

void	SHPDestroyTree (SHPTree *psTree)

int	SHPCheckBoundsOverlap (double padfBox1Min, double padfBox1Max, double padfBox2Min, double padfBox2Max, int nDimension)

static int	SHPCheckObjectContained (SHPObject psObject, int nDimension, double padfBoundsMin, double *padfBoundsMax)

static void	SHPTreeSplitBounds (double padfBoundsMinIn, double padfBoundsMaxIn, double padfBoundsMin1, double padfBoundsMax1, double padfBoundsMin2, double padfBoundsMax2)

static int	SHPTreeNodeAddShapeId (SHPTreeNode psTreeNode, SHPObject psObject, int nMaxDepth, int nDimension)

int	SHPTreeAddShapeId (SHPTree psTree, SHPObject psObject)

static void	SHPTreeCollectShapeIds (SHPTree hTree, SHPTreeNode psTreeNode, double padfBoundsMin, double padfBoundsMax, int pnShapeCount, int pnMaxShapes, int **ppanShapeList)

static int	compare_ints (const void a, const void b)

int *	SHPTreeFindLikelyShapes (SHPTree hTree, double padfBoundsMin, double padfBoundsMax, int pnShapeCount)

static int	SHPTreeNodeTrim (SHPTreeNode *psTreeNode)

void	SHPTreeTrimExtraNodes (SHPTree *hTree)

static void	SwapWord (int length, void *wordP)

SHPTreeDiskHandle	SHPOpenDiskTree (const char pszQIXFilename, SAHooks psHooks)

void	SHPCloseDiskTree (SHPTreeDiskHandle hDiskTree)

static int	SHPSearchDiskTreeNode (SHPTreeDiskHandle hDiskTree, double padfBoundsMin, double padfBoundsMax, int *ppanResultBuffer, int pnBufferMax, int *pnResultCount, int bNeedSwap, int nRecLevel)

static SAOffset	SHPTreeReadLibc (void *p, SAOffset size, SAOffset nmemb, SAFile file)

static SAOffset	SHPTreeSeekLibc (SAFile file, SAOffset offset, int whence)

int *	SHPSearchDiskTree (FILE fp, double padfBoundsMin, double padfBoundsMax, int pnShapeCount)

int *	SHPSearchDiskTreeEx (SHPTreeDiskHandle hDiskTree, double padfBoundsMin, double padfBoundsMax, int *pnShapeCount)

static int	SHPGetSubNodeOffset (SHPTreeNode *node)

static void	SHPWriteTreeNode (SAFile fp, SHPTreeNode node, SAHooks psHooks)

int	SHPWriteTree (SHPTree tree, const char filename)

int	SHPWriteTreeLL (SHPTree tree, const char filename, SAHooks *psHooks)

Variables
static const char	cpl_cvsid [] = "$Id$"

static int	bBigEndian = 0

Macro Definition Documentation

◆ CONST_CAST

#define CONST_CAST	(	type,
		x
	)	((type)(x))

Definition at line 160 of file shptree.c.

◆ FALSE

#define FALSE 0

Definition at line 136 of file shptree.c.

◆ REINTERPRET_CAST

#define REINTERPRET_CAST	(	type,
		x
	)	((type)(x))

Definition at line 159 of file shptree.c.

◆ SHP_SPLIT_RATIO

#define SHP_SPLIT_RATIO 0.55

Definition at line 150 of file shptree.c.

◆ SHPLIB_NULLPTR

#define SHPLIB_NULLPTR NULL

Definition at line 161 of file shptree.c.

◆ STATIC_CAST

#define STATIC_CAST	(	type,
		x
	)	((type)(x))

Definition at line 158 of file shptree.c.

◆ TRUE

#define TRUE 1

Definition at line 135 of file shptree.c.

Function Documentation

◆ compare_ints()

static int compare_ints	(	const void *	a,
		const void *	b
	)

static

Definition at line 710 of file shptree.c.

References a, and REINTERPRET_CAST.

Referenced by SHPSearchDiskTreeEx(), and SHPTreeFindLikelyShapes().

◆ cvsid_aw()

static const char* cvsid_aw ( )

static

Definition at line 132 of file shptree.c.

◆ SfRealloc()

static void* SfRealloc	(	void *	pMem,
		int	nNewSize
	)

static

Definition at line 171 of file shptree.c.

References SHPLIB_NULLPTR.

Referenced by SHPSearchDiskTreeNode(), SHPTreeCollectShapeIds(), and SHPTreeNodeAddShapeId().

◆ SHPCheckBoundsOverlap()

int SHPCheckBoundsOverlap	(	double *	padfBox1Min,
		double *	padfBox1Max,
		double *	padfBox2Min,
		double *	padfBox2Max,
		int	nDimension
	)

Definition at line 378 of file shptree.c.

References FALSE, and TRUE.

Referenced by SHPSearchDiskTreeNode(), and SHPTreeCollectShapeIds().

◆ SHPCheckObjectContained()

static int SHPCheckObjectContained	(	SHPObject *	psObject,
		int	nDimension,
		double *	padfBoundsMin,
		double *	padfBoundsMax
	)

static

Definition at line 403 of file shptree.c.

References tagSHPObject::dfMMax, tagSHPObject::dfMMin, tagSHPObject::dfXMax, tagSHPObject::dfXMin, tagSHPObject::dfYMax, tagSHPObject::dfYMin, tagSHPObject::dfZMax, tagSHPObject::dfZMin, FALSE, and TRUE.

Referenced by SHPTreeNodeAddShapeId().

◆ SHPCloseDiskTree()

void SHPCloseDiskTree ( SHPTreeDiskHandle hDiskTree )

Definition at line 873 of file shptree.c.

References SAHooks::FClose, SHPDiskTreeInfo::fpQIX, SHPDiskTreeInfo::sHooks, and SHPLIB_NULLPTR.

◆ SHPCreateTree()

SHPTree* SHPCreateTree	(	SHPHandle	hSHP,
		int	nDimension,
		int	nMaxDepth,
		double *	padfBoundsMin,
		double *	padfBoundsMax
	)

Definition at line 217 of file shptree.c.

References shape_tree_node::adfBoundsMax, shape_tree_node::adfBoundsMin, SHPTree::hSHP, MAX_DEFAULT_TREE_DEPTH, SHPTree::nDimension, SHPTree::nMaxDepth, SHPTree::nTotalCount, SHPTree::psRoot, SHPDestroyObject(), SHPGetInfo(), SHPLIB_NULLPTR, SHPReadObject(), SHPTreeAddShapeId(), SHPTreeNodeCreate(), and STATIC_CAST.

◆ SHPDestroyTree()

void SHPDestroyTree ( SHPTree * psTree )

Definition at line 364 of file shptree.c.

References SHPTree::psRoot, and SHPDestroyTreeNode().

◆ SHPDestroyTreeNode()

static void SHPDestroyTreeNode ( SHPTreeNode * psTreeNode )

static

Definition at line 329 of file shptree.c.

References shape_tree_node::apsSubNode, shape_tree_node::nShapeCount, shape_tree_node::nSubNodes, shape_tree_node::panShapeIds, shape_tree_node::papsShapeObj, SHPDestroyObject(), and SHPLIB_NULLPTR.

Referenced by SHPDestroyTree(), and SHPTreeNodeTrim().

◆ SHPGetSubNodeOffset()

static int SHPGetSubNodeOffset ( SHPTreeNode * node )

static

Definition at line 1139 of file shptree.c.

References shape_tree_node::apsSubNode, shape_tree_node::nShapeCount, shape_tree_node::nSubNodes, and offset.

Referenced by SHPWriteTreeNode().

◆ SHPOpenDiskTree()

SHPTreeDiskHandle SHPOpenDiskTree	(	const char *	pszQIXFilename,
		SAHooks *	psHooks
	)

Definition at line 847 of file shptree.c.

References SAHooks::FOpen, SHPDiskTreeInfo::fpQIX, SASetupDefaultHooks(), SHPDiskTreeInfo::sHooks, SHPLIB_NULLPTR, and STATIC_CAST.

◆ SHPSearchDiskTree()

int* SHPSearchDiskTree	(	FILE *	fp,
		double *	padfBoundsMin,
		double *	padfBoundsMax,
		int *	pnShapeCount
	)

Definition at line 1048 of file shptree.c.

References SHPDiskTreeInfo::fpQIX, SAHooks::FRead, SAHooks::FSeek, REINTERPRET_CAST, SHPDiskTreeInfo::sHooks, SHPSearchDiskTreeEx(), SHPTreeReadLibc(), and SHPTreeSeekLibc().

◆ SHPSearchDiskTreeEx()

int* SHPSearchDiskTreeEx	(	SHPTreeDiskHandle	hDiskTree,
		double *	padfBoundsMin,
		double *	padfBoundsMax,
		int *	pnShapeCount
	)

Definition at line 1070 of file shptree.c.

References bBigEndian, compare_ints(), FALSE, SHPDiskTreeInfo::fpQIX, SAHooks::FRead, SAHooks::FSeek, REINTERPRET_CAST, SEEK_SET, SHPDiskTreeInfo::sHooks, SHPLIB_NULLPTR, SHPSearchDiskTreeNode(), STATIC_CAST, and TRUE.

Referenced by SHPSearchDiskTree().

◆ SHPSearchDiskTreeNode()

static int SHPSearchDiskTreeNode	(	SHPTreeDiskHandle	hDiskTree,
		double *	padfBoundsMin,
		double *	padfBoundsMax,
		int **	ppanResultBuffer,
		int *	pnBufferMax,
		int *	pnResultCount,
		int	bNeedSwap,
		int	nRecLevel
	)

static

Definition at line 887 of file shptree.c.

References SAHooks::Error, FALSE, SHPDiskTreeInfo::fpQIX, SAHooks::FRead, SAHooks::FSeek, offset, SEEK_CUR, SfRealloc(), SHPDiskTreeInfo::sHooks, SHPCheckBoundsOverlap(), SHPLIB_NULLPTR, STATIC_CAST, SwapWord(), and TRUE.

Referenced by SHPSearchDiskTreeEx().

◆ SHPTreeAddShapeId()

int SHPTreeAddShapeId	(	SHPTree *	psTree,
		SHPObject *	psObject
	)

Definition at line 631 of file shptree.c.

References SHPTree::nDimension, SHPTree::nMaxDepth, SHPTree::nTotalCount, SHPTree::psRoot, and SHPTreeNodeAddShapeId().

Referenced by SHPCreateTree().

◆ SHPTreeCollectShapeIds()

static void SHPTreeCollectShapeIds	(	SHPTree *	hTree,
		SHPTreeNode *	psTreeNode,
		double *	padfBoundsMin,
		double *	padfBoundsMax,
		int *	pnShapeCount,
		int *	pnMaxShapes,
		int **	ppanShapeList
	)

static

Definition at line 648 of file shptree.c.

References shape_tree_node::adfBoundsMax, shape_tree_node::adfBoundsMin, shape_tree_node::apsSubNode, SHPTree::nDimension, shape_tree_node::nShapeCount, shape_tree_node::nSubNodes, shape_tree_node::panShapeIds, SfRealloc(), SHPCheckBoundsOverlap(), SHPLIB_NULLPTR, and STATIC_CAST.

Referenced by SHPTreeFindLikelyShapes().

◆ SHPTreeFindLikelyShapes()

int* SHPTreeFindLikelyShapes	(	SHPTree *	hTree,
		double *	padfBoundsMin,
		double *	padfBoundsMax,
		int *	pnShapeCount
	)

Definition at line 716 of file shptree.c.

References compare_ints(), SHPLIB_NULLPTR, and SHPTreeCollectShapeIds().

◆ SHPTreeNodeAddShapeId()

static int SHPTreeNodeAddShapeId	(	SHPTreeNode *	psTreeNode,
		SHPObject *	psObject,
		int	nMaxDepth,
		int	nDimension
	)

static

Definition at line 483 of file shptree.c.

References shape_tree_node::adfBoundsMax, shape_tree_node::adfBoundsMin, shape_tree_node::apsSubNode, shape_tree_node::nShapeCount, tagSHPObject::nShapeId, shape_tree_node::nSubNodes, shape_tree_node::panShapeIds, shape_tree_node::papsShapeObj, SfRealloc(), SHPCheckObjectContained(), SHPLIB_NULLPTR, SHPTreeNodeCreate(), SHPTreeSplitBounds(), STATIC_CAST, and TRUE.

Referenced by SHPTreeAddShapeId().

◆ SHPTreeNodeCreate()

static SHPTreeNode* SHPTreeNodeCreate	(	double *	padfBoundsMin,
		double *	padfBoundsMax
	)

static

Definition at line 186 of file shptree.c.

References shape_tree_node::adfBoundsMax, shape_tree_node::adfBoundsMin, shape_tree_node::nShapeCount, shape_tree_node::nSubNodes, shape_tree_node::panShapeIds, shape_tree_node::papsShapeObj, SHPLIB_NULLPTR, and STATIC_CAST.

Referenced by SHPCreateTree(), and SHPTreeNodeAddShapeId().

◆ SHPTreeNodeTrim()

static int SHPTreeNodeTrim ( SHPTreeNode * psTreeNode )

static

Definition at line 750 of file shptree.c.

References shape_tree_node::adfBoundsMax, shape_tree_node::adfBoundsMin, shape_tree_node::apsSubNode, shape_tree_node::nShapeCount, shape_tree_node::nSubNodes, shape_tree_node::panShapeIds, shape_tree_node::papsShapeObj, SHPDestroyTreeNode(), and SHPLIB_NULLPTR.

Referenced by SHPTreeTrimExtraNodes().

◆ SHPTreeReadLibc()

static SAOffset SHPTreeReadLibc	(	void *	p,
		SAOffset	size,
		SAOffset	nmemb,
		SAFile	file
	)

static

Definition at line 1023 of file shptree.c.

References REINTERPRET_CAST, size, and STATIC_CAST.

Referenced by SHPSearchDiskTree().

◆ SHPTreeSeekLibc()

static SAOffset SHPTreeSeekLibc	(	SAFile	file,
		SAOffset	offset,
		int	whence
	)

static

Definition at line 1036 of file shptree.c.

References offset, REINTERPRET_CAST, and STATIC_CAST.

Referenced by SHPSearchDiskTree().

◆ SHPTreeSplitBounds()

static void SHPTreeSplitBounds	(	double *	padfBoundsMinIn,
		double *	padfBoundsMaxIn,
		double *	padfBoundsMin1,
		double *	padfBoundsMax1,
		double *	padfBoundsMin2,
		double *	padfBoundsMax2
	)

static

Definition at line 440 of file shptree.c.

References SHP_SPLIT_RATIO.

Referenced by SHPTreeNodeAddShapeId().

◆ SHPTreeTrimExtraNodes()

void SHPTreeTrimExtraNodes ( SHPTree * hTree )

Definition at line 810 of file shptree.c.

References SHPTree::psRoot, and SHPTreeNodeTrim().

◆ SHPWriteTree()

int SHPWriteTree	(	SHPTree *	tree,
		const char *	filename
	)

Definition at line 1210 of file shptree.c.

References filename, SASetupDefaultHooks(), SHPDiskTreeInfo::sHooks, and SHPWriteTreeLL().

◆ SHPWriteTreeLL()

int SHPWriteTreeLL	(	SHPTree *	tree,
		const char *	filename,
		SAHooks *	psHooks
	)

Definition at line 1223 of file shptree.c.

References bBigEndian, FALSE, SAHooks::FClose, filename, SAHooks::FOpen, SAHooks::FWrite, SHPTree::nMaxDepth, SHPTree::nTotalCount, SHPTree::psRoot, REINTERPRET_CAST, SASetupDefaultHooks(), SHPDiskTreeInfo::sHooks, SHPLIB_NULLPTR, SHPWriteTreeNode(), and TRUE.

Referenced by SHPWriteTree().

◆ SHPWriteTreeNode()

static void SHPWriteTreeNode	(	SAFile	fp,
		SHPTreeNode *	node,
		SAHooks *	psHooks
	)

static

Definition at line 1161 of file shptree.c.

References shape_tree_node::adfBoundsMax, shape_tree_node::adfBoundsMin, shape_tree_node::apsSubNode, SAHooks::FWrite, shape_tree_node::nShapeCount, shape_tree_node::nSubNodes, offset, shape_tree_node::panShapeIds, SHPGetSubNodeOffset(), SHPLIB_NULLPTR, and STATIC_CAST.

Referenced by SHPWriteTreeLL().

◆ SwapWord()

static void SwapWord	(	int	length,
		void *	wordP
	)

static

Definition at line 822 of file shptree.c.

References STATIC_CAST.

Referenced by SHPSearchDiskTreeNode().

Variable Documentation

◆ bBigEndian

int bBigEndian = 0

static

Definition at line 139 of file shptree.c.

Referenced by SHPSearchDiskTreeEx(), and SHPWriteTreeLL().

◆ cpl_cvsid

const char cpl_cvsid[] = "$Id$"

static

Definition at line 132 of file shptree.c.

Classes

Macros

Functions

Variables

Macro Definition Documentation

◆ CONST_CAST

◆ FALSE

◆ REINTERPRET_CAST

◆ SHP_SPLIT_RATIO

◆ SHPLIB_NULLPTR

◆ STATIC_CAST

◆ TRUE

Function Documentation

◆ compare_ints()

◆ cvsid_aw()

◆ SfRealloc()

◆ SHPCheckBoundsOverlap()

◆ SHPCheckObjectContained()

◆ SHPCloseDiskTree()

◆ SHPCreateTree()

◆ SHPDestroyTree()

◆ SHPDestroyTreeNode()

◆ SHPGetSubNodeOffset()

◆ SHPOpenDiskTree()

◆ SHPSearchDiskTree()

◆ SHPSearchDiskTreeEx()

◆ SHPSearchDiskTreeNode()

◆ SHPTreeAddShapeId()

◆ SHPTreeCollectShapeIds()

◆ SHPTreeFindLikelyShapes()

◆ SHPTreeNodeAddShapeId()

◆ SHPTreeNodeCreate()

◆ SHPTreeNodeTrim()

◆ SHPTreeReadLibc()

◆ SHPTreeSeekLibc()

◆ SHPTreeSplitBounds()

◆ SHPTreeTrimExtraNodes()

◆ SHPWriteTree()

◆ SHPWriteTreeLL()

◆ SHPWriteTreeNode()

◆ SwapWord()

Variable Documentation

◆ bBigEndian

◆ cpl_cvsid