DebugStacker::DebugStacker(const char *text)
{
	threadid_t threadid = get_current_thread_id();

	JMutexAutoLock lock(g_debug_stacks_mutex);

	core::map<threadid_t, DebugStack*>::Node *n;
	n = g_debug_stacks.find(threadid);
	if(n != NULL)
	{
		m_stack = n->getValue();
	}
	else
	{
		/*DEBUGPRINT("Creating new debug stack for thread %x\n",
				(unsigned int)threadid);*/
		m_stack = new DebugStack(threadid);
		g_debug_stacks.insert(threadid, m_stack);
	}

	if(m_stack->stack_i >= DEBUG_STACK_SIZE)
	{
		m_overflowed = true;
	}
	else
	{
		m_overflowed = false;

		snprintf(m_stack->stack[m_stack->stack_i],
				DEBUG_STACK_TEXT_SIZE, "%s", text);
		m_stack->stack_i++;
		if(m_stack->stack_i > m_stack->stack_max_i)
			m_stack->stack_max_i = m_stack->stack_i;
	}
}

void ActiveBlockList::update(core::list<v3s16> &active_positions,
		s16 radius,
		core::map<v3s16, bool> &blocks_removed,
		core::map<v3s16, bool> &blocks_added)
{
	/*
		Create the new list
	*/
	core::map<v3s16, bool> newlist;
	for(core::list<v3s16>::Iterator i = active_positions.begin();
			i != active_positions.end(); i++)
	{
		fillRadiusBlock(*i, radius, newlist);
	}

	/*
		Find out which blocks on the old list are not on the new list
	*/
	// Go through old list
	for(core::map<v3s16, bool>::Iterator i = m_list.getIterator();
			i.atEnd()==false; i++)
	{
		v3s16 p = i.getNode()->getKey();
		// If not on new list, it's been removed
		if(newlist.find(p) == NULL)
			blocks_removed.insert(p, true);
	}

	/*
		Find out which blocks on the new list are not on the old list
	*/
	// Go through new list
	for(core::map<v3s16, bool>::Iterator i = newlist.getIterator();
			i.atEnd()==false; i++)
	{
		v3s16 p = i.getNode()->getKey();
		// If not on old list, it's been added
		if(m_list.find(p) == NULL)
			blocks_added.insert(p, true);
	}

	/*
		Update m_list
	*/
	m_list.clear();
	for(core::map<v3s16, bool>::Iterator i = newlist.getIterator();
			i.atEnd()==false; i++)
	{
		v3s16 p = i.getNode()->getKey();
		m_list.insert(p, true);
	}
}

u32 TextureSource::getTextureId(const std::string &name)
{
	//infostream<<"getTextureId(): \""<<name<<"\""<<std::endl;

	{
		/*
			See if texture already exists
		*/
		JMutexAutoLock lock(m_atlaspointer_cache_mutex);
		core::map<std::string, u32>::Node *n;
		n = m_name_to_id.find(name);
		if(n != NULL)
		{
			return n->getValue();
		}
	}
	
	/*
		Get texture
	*/
	if(get_current_thread_id() == m_main_thread)
	{
		return getTextureIdDirect(name);
	}
	else
	{
		infostream<<"getTextureId(): Queued: name=\""<<name<<"\""<<std::endl;

		// We're gonna ask the result to be put into here
		ResultQueue<std::string, u32, u8, u8> result_queue;
		
		// Throw a request in
		m_get_texture_queue.add(name, 0, 0, &result_queue);
		
		infostream<<"Waiting for texture from main thread, name=\""
				<<name<<"\""<<std::endl;
		
		try
		{
			// Wait result for a second
			GetResult<std::string, u32, u8, u8>
					result = result_queue.pop_front(1000);
		
			// Check that at least something worked OK
			assert(result.key == name);

			return result.item;
		}
		catch(ItemNotFoundException &e)
		{
			infostream<<"Waiting for texture timed out."<<std::endl;
			return 0;
		}
	}
	
	infostream<<"getTextureId(): Failed"<<std::endl;

	return 0;
}

/*
	Lights neighbors of from_nodes, collects all them and then
	goes on recursively.

	NOTE: This is faster on small areas but will overflow the
	      stack on large areas. Thus it is not used.
*/
void VoxelManipulator::spreadLight(enum LightBank bank,
		core::map<v3s16, bool> & from_nodes)
{
	if(from_nodes.size() == 0)
		return;
	
	core::map<v3s16, bool> lighted_nodes;
	core::map<v3s16, bool>::Iterator j;
	j = from_nodes.getIterator();

	for(; j.atEnd() == false; j++)
	{
		v3s16 pos = j.getNode()->getKey();

		spreadLight(bank, pos);
	}
}

/*
	Goes recursively through the neighbours of the node.

	Alters only transparent nodes.

	If the lighting of the neighbour is lower than the lighting of
	the node was (before changing it to 0 at the step before), the
	lighting of the neighbour is set to 0 and then the same stuff
	repeats for the neighbour.

	The ending nodes of the routine are stored in light_sources.
	This is useful when a light is removed. In such case, this
	routine can be called for the light node and then again for
	light_sources to re-light the area without the removed light.

	values of from_nodes are lighting values.
*/
void VoxelManipulator::unspreadLight(enum LightBank bank,
		core::map<v3s16, u8> & from_nodes,
		core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr)
{
	if(from_nodes.size() == 0)
		return;
	
	core::map<v3s16, u8>::Iterator j;
	j = from_nodes.getIterator();

	for(; j.atEnd() == false; j++)
	{
		v3s16 pos = j.getNode()->getKey();
		
		//MapNode &n = m_data[m_area.index(pos)];
		
		u8 oldlight = j.getNode()->getValue();

		unspreadLight(bank, pos, oldlight, light_sources, nodemgr);
	}
}

/*
	Finds out what objects have been removed from
	inside a radius around a position
*/
void ServerEnvironment::getRemovedActiveObjects(v3s16 pos, s16 radius,
		core::map<u16, bool> &current_objects,
		core::map<u16, bool> &removed_objects)
{
	v3f pos_f = intToFloat(pos, BS);
	f32 radius_f = radius * BS;
	/*
		Go through current_objects; object is removed if:
		- object is not found in m_active_objects (this is actually an
		  error condition; objects should be set m_removed=true and removed
		  only after all clients have been informed about removal), or
		- object has m_removed=true, or
		- object is too far away
	*/
	for(core::map<u16, bool>::Iterator
			i = current_objects.getIterator();
			i.atEnd()==false; i++)
	{
		u16 id = i.getNode()->getKey();
		ServerActiveObject *object = getActiveObject(id);
		if(object == NULL)
		{
			dstream<<"WARNING: ServerEnvironment::getRemovedActiveObjects():"
					<<" object in current_objects is NULL"<<std::endl;
		}
		else if(object->m_removed == false)
		{
			f32 distance_f = object->getBasePosition().getDistanceFrom(pos_f);
			/*dstream<<"removed == false"
					<<"distance_f = "<<distance_f
					<<", radius_f = "<<radius_f<<std::endl;*/
			if(distance_f < radius_f)
			{
				// Not removed
				continue;
			}
		}
		removed_objects.insert(id, false);
	}
}

void debug_stacks_print_to(std::ostream &os)
{
	JMutexAutoLock lock(g_debug_stacks_mutex);

	os<<"Debug stacks:"<<std::endl;

	for(core::map<threadid_t, DebugStack*>::Iterator
			i = g_debug_stacks.getIterator();
			i.atEnd() == false; i++)
	{
		DebugStack *stack = i.getNode()->getValue();
		stack->print(os, false);
	}
}

bool isFreeClientActiveObjectId(u16 id,
		core::map<u16, ClientActiveObject*> &objects)
{
	if(id == 0)
		return false;
	
	for(core::map<u16, ClientActiveObject*>::Iterator
			i = objects.getIterator();
			i.atEnd()==false; i++)
	{
		if(i.getNode()->getKey() == id)
			return false;
	}
	return true;
}

void debug_stacks_print()
{
	JMutexAutoLock lock(g_debug_stacks_mutex);

	DEBUGPRINT("Debug stacks:\n");

	for(core::map<threadid_t, DebugStack*>::Iterator
			i = g_debug_stacks.getIterator();
			i.atEnd() == false; i++)
	{
		DebugStack *stack = i.getNode()->getValue();

		for(int i=0; i<DEBUGSTREAM_COUNT; i++)
		{
			if(g_debugstreams[i] != NULL)
				stack->print(g_debugstreams[i], true);
		}
	}
}

HeightPoint ground_height(u64 seed, v2s16 p2d)
{
	core::map<v2s16, HeightPoint>::Node *n = g_heights.find(p2d);
	if(n)
		return n->getValue();
	HeightPoint hp;
	s16 level = mapgen::find_ground_level_from_noise(seed, p2d, 3);
	hp.gh = (level-4)*BS;
	hp.ma = (4)*BS;
	/*hp.gh = BS*base_rock_level_2d(seed, p2d);
	hp.ma = BS*get_mud_add_amount(seed, p2d);*/
	hp.have_sand = mapgen::get_have_sand(seed, p2d);
	if(hp.gh > BS*WATER_LEVEL)
		hp.tree_amount = mapgen::tree_amount_2d(seed, p2d);
	else
		hp.tree_amount = 0;
	// No mud has been added if mud amount is less than 1
	if(hp.ma < 1.0*BS)
		hp.ma = 0.0;
	//hp.gh -= BS*3; // Lower a bit so that it is not that much in the way
	g_heights[p2d] = hp;
	return hp;
}

static bool testErase()
{
	{
		core::array<SDummy> aaa;
		aaa.push_back(SDummy(0));
		aaa.push_back(SDummy(1));
		aaa.push_back(SDummy(2));
		aaa.push_back(SDummy(3));
		aaa.push_back(SDummy(4));
		aaa.push_back(SDummy(5));

		aaa.erase(0,2);
	}

	for ( core::map<int,int>::Iterator it = countReferences.getIterator(); !it.atEnd(); it++ )
	{
		if ( it->getValue() != 0 )
		{
			logTestString("testErase: wrong count for %d, it's: %d\n", it->getKey(), it->getValue());
			return false;
		}
	}
	return true;
}

/*
	Lights neighbors of from_nodes, collects all them and then
	goes on recursively.
*/
void VoxelManipulator::spreadLight(enum LightBank bank,
		core::map<v3s16, bool> & from_nodes, INodeDefManager *nodemgr)
{
	const v3s16 dirs[6] = {
		v3s16(0,0,1), // back
		v3s16(0,1,0), // top
		v3s16(1,0,0), // right
		v3s16(0,0,-1), // front
		v3s16(0,-1,0), // bottom
		v3s16(-1,0,0), // left
	};

	if(from_nodes.size() == 0)
		return;
	
	core::map<v3s16, bool> lighted_nodes;
	core::map<v3s16, bool>::Iterator j;
	j = from_nodes.getIterator();

	for(; j.atEnd() == false; j++)
	{
		v3s16 pos = j.getNode()->getKey();

		emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));

		u32 i = m_area.index(pos);
		
		if(m_flags[i] & VOXELFLAG_INEXISTENT)
			continue;

		MapNode &n = m_data[i];

		u8 oldlight = n.getLight(bank, nodemgr);
		u8 newlight = diminish_light(oldlight);

		// Loop through 6 neighbors
		for(u16 i=0; i<6; i++)
		{
			// Get the position of the neighbor node
			v3s16 n2pos = pos + dirs[i];
			
			try
			{
				u32 n2i = m_area.index(n2pos);

				if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
					continue;

				MapNode &n2 = m_data[n2i];

				u8 light2 = n2.getLight(bank, nodemgr);
				
				/*
					If the neighbor is brighter than the current node,
					add to list (it will light up this node on its turn)
				*/
				if(light2 > undiminish_light(oldlight))
				{
					lighted_nodes.insert(n2pos, true);
				}
				/*
					If the neighbor is dimmer than how much light this node
					would spread on it, add to list
				*/
				if(light2 < newlight)
				{
					if(nodemgr->get(n2).light_propagates)
					{
						n2.setLight(bank, newlight, nodemgr);
						lighted_nodes.insert(n2pos, true);
					}
				}
			}
			catch(InvalidPositionException &e)
			{
				continue;
			}
		}
	}

	/*dstream<<"spreadLight(): Changed block "
			<<blockchangecount<<" times"
			<<" for "<<from_nodes.size()<<" nodes"
			<<std::endl;*/
	
	if(lighted_nodes.size() > 0)
		spreadLight(bank, lighted_nodes, nodemgr);
}

void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
		core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr)
{
	v3s16 dirs[6] = {
		v3s16(0,0,1), // back
		v3s16(0,1,0), // top
		v3s16(1,0,0), // right
		v3s16(0,0,-1), // front
		v3s16(0,-1,0), // bottom
		v3s16(-1,0,0), // left
	};
	
	emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));

	// Loop through 6 neighbors
	for(u16 i=0; i<6; i++)
	{
		// Get the position of the neighbor node
		v3s16 n2pos = p + dirs[i];
		
		u32 n2i = m_area.index(n2pos);

		if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
			continue;

		MapNode &n2 = m_data[n2i];
		
		/*
			If the neighbor is dimmer than what was specified
			as oldlight (the light of the previous node)
		*/
		u8 light2 = n2.getLight(bank, nodemgr);
		if(light2 < oldlight)
		{
			/*
				And the neighbor is transparent and it has some light
			*/
			if(nodemgr->get(n2).light_propagates && light2 != 0)
			{
				/*
					Set light to 0 and add to queue
				*/

				n2.setLight(bank, 0, nodemgr);
				
				unspreadLight(bank, n2pos, light2, light_sources, nodemgr);
				
				/*
					Remove from light_sources if it is there
					NOTE: This doesn't happen nearly at all
				*/
				/*if(light_sources.find(n2pos))
				{
					std::cout<<"Removed from light_sources"<<std::endl;
					light_sources.remove(n2pos);
				}*/
			}
		}
		else{
			light_sources.insert(n2pos, true);
		}
	}
}

void TextureSource::buildMainAtlas(class IGameDef *gamedef) 
{
	assert(gamedef->tsrc() == this);
	INodeDefManager *ndef = gamedef->ndef();

	infostream<<"TextureSource::buildMainAtlas()"<<std::endl;

	//return; // Disable (for testing)
	
	video::IVideoDriver* driver = m_device->getVideoDriver();
	assert(driver);

	JMutexAutoLock lock(m_atlaspointer_cache_mutex);

	// Create an image of the right size
	core::dimension2d<u32> atlas_dim(1024,1024);
	video::IImage *atlas_img =
			driver->createImage(video::ECF_A8R8G8B8, atlas_dim);
	//assert(atlas_img);
	if(atlas_img == NULL)
	{
		errorstream<<"TextureSource::buildMainAtlas(): Failed to create atlas "
				"image; not building texture atlas."<<std::endl;
		return;
	}

	/*
		Grab list of stuff to include in the texture atlas from the
		main content features
	*/

	core::map<std::string, bool> sourcelist;

	for(u16 j=0; j<MAX_CONTENT+1; j++)
	{
		if(j == CONTENT_IGNORE || j == CONTENT_AIR)
			continue;
		const ContentFeatures &f = ndef->get(j);
		for(u32 i=0; i<6; i++)
		{
			std::string name = f.tname_tiles[i];
			sourcelist[name] = true;
		}
	}
	
	infostream<<"Creating texture atlas out of textures: ";
	for(core::map<std::string, bool>::Iterator
			i = sourcelist.getIterator();
			i.atEnd() == false; i++)
	{
		std::string name = i.getNode()->getKey();
		infostream<<"\""<<name<<"\" ";
	}
	infostream<<std::endl;

	// Padding to disallow texture bleeding
	s32 padding = 16;

	s32 column_width = 256;
	s32 column_padding = 16;

	/*
		First pass: generate almost everything
	*/
	core::position2d<s32> pos_in_atlas(0,0);
	
	pos_in_atlas.Y = padding;

	for(core::map<std::string, bool>::Iterator
			i = sourcelist.getIterator();
			i.atEnd() == false; i++)
	{
		std::string name = i.getNode()->getKey();

		// Generate image by name
		video::IImage *img2 = generate_image_from_scratch(name, m_device,
				&m_sourcecache);
		if(img2 == NULL)
		{
			errorstream<<"TextureSource::buildMainAtlas(): "
					<<"Couldn't generate image \""<<name<<"\""<<std::endl;
			continue;
		}

		core::dimension2d<u32> dim = img2->getDimension();

		// Don't add to atlas if image is large
		core::dimension2d<u32> max_size_in_atlas(32,32);
		if(dim.Width > max_size_in_atlas.Width
		|| dim.Height > max_size_in_atlas.Height)
		{
			infostream<<"TextureSource::buildMainAtlas(): Not adding "
					<<"\""<<name<<"\" because image is large"<<std::endl;
			continue;
		}

		// Wrap columns and stop making atlas if atlas is full
		if(pos_in_atlas.Y + dim.Height > atlas_dim.Height)
		{
			if(pos_in_atlas.X > (s32)atlas_dim.Width - 256 - padding){
//.........这里部分代码省略.........

/*
	Propagates sunlight down through the block.
	Doesn't modify nodes that are not affected by sunlight.
	
	Returns false if sunlight at bottom block is invalid.
	Returns true if sunlight at bottom block is valid.
	Returns true if bottom block doesn't exist.

	If there is a block above, continues from it.
	If there is no block above, assumes there is sunlight, unless
	is_underground is set or highest node is water.

	All sunlighted nodes are added to light_sources.

	if remove_light==true, sets non-sunlighted nodes black.

	if black_air_left!=NULL, it is set to true if non-sunlighted
	air is left in block.
*/
bool MapBlock::propagateSunlight(core::map<v3s16, bool> & light_sources,
		bool remove_light, bool *black_air_left)
{
	INodeDefManager *nodemgr = m_gamedef->ndef();

	// Whether the sunlight at the top of the bottom block is valid
	bool block_below_is_valid = true;
	
	v3s16 pos_relative = getPosRelative();
	
	for(s16 x=0; x<MAP_BLOCKSIZE; x++)
	{
		for(s16 z=0; z<MAP_BLOCKSIZE; z++)
		{
#if 1
			bool no_sunlight = false;
			bool no_top_block = false;
			// Check if node above block has sunlight
			try{
				MapNode n = getNodeParent(v3s16(x, MAP_BLOCKSIZE, z));
				if(n.getContent() == CONTENT_IGNORE)
				{
					// Trust heuristics
					no_sunlight = is_underground;
				}
				else if(n.getLight(LIGHTBANK_DAY, m_gamedef->ndef()) != LIGHT_SUN)
				{
					no_sunlight = true;
				}
			}
			catch(InvalidPositionException &e)
			{
				no_top_block = true;
				
				// NOTE: This makes over-ground roofed places sunlighted
				// Assume sunlight, unless is_underground==true
				if(is_underground)
				{
					no_sunlight = true;
				}
				else
				{
					MapNode n = getNode(v3s16(x, MAP_BLOCKSIZE-1, z));
					if(m_gamedef->ndef()->get(n).sunlight_propagates == false)
					{
						no_sunlight = true;
					}
				}
				// NOTE: As of now, this just would make everything dark.
				// No sunlight here
				//no_sunlight = true;
			}
#endif
#if 0 // Doesn't work; nothing gets light.
			bool no_sunlight = true;
			bool no_top_block = false;
			// Check if node above block has sunlight
			try{
				MapNode n = getNodeParent(v3s16(x, MAP_BLOCKSIZE, z));
				if(n.getLight(LIGHTBANK_DAY) == LIGHT_SUN)
				{
					no_sunlight = false;
				}
			}
			catch(InvalidPositionException &e)
			{
				no_top_block = true;
			}
#endif

			/*std::cout<<"("<<x<<","<<z<<"): "
					<<"no_top_block="<<no_top_block
					<<", is_underground="<<is_underground
					<<", no_sunlight="<<no_sunlight
					<<std::endl;*/
		
			s16 y = MAP_BLOCKSIZE-1;
			
			// This makes difference to diminishing in water.
			bool stopped_to_solid_object = false;
			
//.........这里部分代码省略.........

DebugStacker::~DebugStacker()
{
	JMutexAutoLock lock(g_debug_stacks_mutex);
	
	if(m_overflowed == true)
		return;
	
	m_stack->stack_i--;

	if(m_stack->stack_i == 0)
	{
		threadid_t threadid = m_stack->threadid;
		/*DEBUGPRINT("Deleting debug stack for thread %x\n",
				(unsigned int)threadid);*/
		delete m_stack;
		g_debug_stacks.remove(threadid);
	}
}

	SDummy() : x(0)
	{
		countReferences.insert(x,1);
	}