/*
===============
idClipModel::Link_r
===============
*/
void idClipModel::Link_r( struct clipSector_s *node ) {
	clipLink_t *link;

	while( node->axis != -1 ) {
		if ( absBounds[0][node->axis] > node->dist ) {
			node = node->children[0];
		} else if ( absBounds[1][node->axis] < node->dist ) {
			node = node->children[1];
		} else {
			Link_r( node->children[0] );
			node = node->children[1];
		}
	}

	link = clipLinkAllocator.Alloc();
	link->clipModel = this;
	link->sector = node;
	link->nextInSector = node->clipLinks;
	link->prevInSector = NULL;
	if ( node->clipLinks ) {
		node->clipLinks->prevInSector = link;
	}
	node->clipLinks = link;
	link->nextLink = clipLinks;
	clipLinks = link;
}

/*
============
FreePathTree_r
============
*/
void FreePathTree_r( pathNode_t *node ) {
	if ( node->children[0] ) {
		FreePathTree_r( node->children[0] );
	}
	if ( node->children[1] ) {
		FreePathTree_r( node->children[1] );
	}
	pathNodeAllocator.Free( node );
}

/*
===============
idClip::Shutdown
===============
*/
void idClip::Shutdown( void ) {
	delete[] clipSectors;
	clipSectors = NULL;
	// free the trace model used for the temporaryClipModel
	if( temporaryClipModel.traceModelIndex != -1 ) {
		idClipModel::FreeTraceModel( temporaryClipModel.traceModelIndex );
		temporaryClipModel.traceModelIndex = -1;
	}
	// free the trace model used for the defaultClipModel
	if( defaultClipModel.traceModelIndex != -1 ) {
		idClipModel::FreeTraceModel( defaultClipModel.traceModelIndex );
		defaultClipModel.traceModelIndex = -1;
	}
	clipLinkAllocator.Shutdown();
}

/*
===============
idClipModel::Unlink
===============
*/
void idClipModel::Unlink( void ) {
	clipLink_t *link;
	for( link = clipLinks; link; link = clipLinks ) {
		clipLinks = link->nextLink;
		if( link->prevInSector ) {
			link->prevInSector->nextInSector = link->nextInSector;
		} else {
			link->sector->clipLinks = link->nextInSector;
		}
		if( link->nextInSector ) {
			link->nextInSector->prevInSector = link->prevInSector;
		}
		clipLinkAllocator.Free( link );
	}
}

/*
============
idAI::FreeObstacleAvoidanceNodes
============
*/
void idAI::FreeObstacleAvoidanceNodes( void ) {
	pathNodeAllocator.Shutdown();
}

/*
============
BuildPathTree
============
*/
pathNode_t *BuildPathTree( const obstacle_t *obstacles, int numObstacles, const idBounds &clipBounds, const idVec2 &startPos, const idVec2 &seekPos, obstaclePath_t &path ) {
	int blockingEdgeNum, blockingObstacle, obstaclePoints, bestNumNodes = MAX_OBSTACLE_PATH;
	float blockingScale;
	pathNode_t *root, *node, *child;
	// gcc 4.0
	idQueueTemplate<pathNode_t, offsetof( pathNode_t, next ) > pathNodeQueue, treeQueue;
	root = pathNodeAllocator.Alloc();
	root->Init();
	root->pos = startPos;

	root->delta = seekPos - root->pos;
	root->numNodes = 0;
	pathNodeQueue.Add( root );

	for ( node = pathNodeQueue.Get(); node && pathNodeAllocator.GetAllocCount() < MAX_PATH_NODES; node = pathNodeQueue.Get() ) {

		treeQueue.Add( node );

		// if this path has more than twice the number of nodes than the best path so far
		if ( node->numNodes > bestNumNodes * 2 ) {
			continue;
		}

		// don't move outside of the clip bounds
		idVec2 endPos = node->pos + node->delta;
		if ( endPos.x - CLIP_BOUNDS_EPSILON < clipBounds[0].x || endPos.x + CLIP_BOUNDS_EPSILON > clipBounds[1].x ||
				endPos.y - CLIP_BOUNDS_EPSILON < clipBounds[0].y || endPos.y + CLIP_BOUNDS_EPSILON > clipBounds[1].y ) {
			continue;
		}

		// if an obstacle is blocking the path
		if ( GetFirstBlockingObstacle( obstacles, numObstacles, node->obstacle, node->pos, node->delta, blockingScale, blockingObstacle, blockingEdgeNum ) ) {

			if ( path.firstObstacle == NULL ) {
				path.firstObstacle = obstacles[blockingObstacle].entity;
			}

			node->delta *= blockingScale;

			if ( node->edgeNum == -1 ) {
				node->children[0] = pathNodeAllocator.Alloc();
				node->children[0]->Init();
				node->children[1] = pathNodeAllocator.Alloc();
				node->children[1]->Init();
				node->children[0]->dir = 0;
				node->children[1]->dir = 1;
				node->children[0]->parent = node->children[1]->parent = node;
				node->children[0]->pos = node->children[1]->pos = node->pos + node->delta;
				node->children[0]->obstacle = node->children[1]->obstacle = blockingObstacle;
				node->children[0]->edgeNum = node->children[1]->edgeNum = blockingEdgeNum;
				node->children[0]->numNodes = node->children[1]->numNodes = node->numNodes + 1;
				if ( GetPathNodeDelta( node->children[0], obstacles, seekPos, true ) ) {
					pathNodeQueue.Add( node->children[0] );
				}
				if ( GetPathNodeDelta( node->children[1], obstacles, seekPos, true ) ) {
					pathNodeQueue.Add( node->children[1] );
				}
			} else {
				node->children[node->dir] = child = pathNodeAllocator.Alloc();
				child->Init();
				child->dir = node->dir;
				child->parent = node;
				child->pos = node->pos + node->delta;
				child->obstacle = blockingObstacle;
				child->edgeNum = blockingEdgeNum;
				child->numNodes = node->numNodes + 1;
				if ( GetPathNodeDelta( child, obstacles, seekPos, true ) ) {
					pathNodeQueue.Add( child );
				}
			}
		} else {
			node->children[node->dir] = child = pathNodeAllocator.Alloc();
			child->Init();
			child->dir = node->dir;
			child->parent = node;
			child->pos = node->pos + node->delta;
			child->numNodes = node->numNodes + 1;

			// there is a free path towards goal
			if ( node->edgeNum == -1 ) {
				if ( node->numNodes < bestNumNodes ) {
					bestNumNodes = node->numNodes;
				}
				continue;
			}

			child->obstacle = node->obstacle;
			obstaclePoints = obstacles[node->obstacle].winding.GetNumPoints();
			child->edgeNum = ( node->edgeNum + obstaclePoints + ( 2 * node->dir - 1 ) ) % obstaclePoints;

			if ( GetPathNodeDelta( child, obstacles, seekPos, false ) ) {
				pathNodeQueue.Add( child );
			}
		}
	}
//.........这里部分代码省略.........

/*
====================
idSampleDecoder::Free
====================
*/
void idSampleDecoder::Free( idSampleDecoder *decoder ) {
	idSampleDecoderLocal *localDecoder = static_cast<idSampleDecoderLocal *>( decoder );
	localDecoder->ClearDecoder();
	sampleDecoderAllocator.Free( localDecoder );
}

/*
====================
idSampleDecoder::Alloc
====================
*/
idSampleDecoder *idSampleDecoder::Alloc( void ) {
	idSampleDecoderLocal *decoder = sampleDecoderAllocator.Alloc();
	decoder->Clear();
	return decoder;
}

/*
====================
idSampleDecoder::Shutdown
====================
*/
void idSampleDecoder::Shutdown( void ) {
	decoderMemoryAllocator.Shutdown();
	sampleDecoderAllocator.Shutdown();
}