性能优先的排序双向链表

说明

这是一个表头用网状的排序双向链表结构托管类
原本开发的原因是游戏服务器根据玩家战斗力排序的容器更新 & 查找效率不理想，希望有个新的方法替代
因为战斗力变化频率比较高，多个用户又可能是相同的战斗力，所以做了这个类似跳跃表的结构对数据分段

enum EN_GRIDDING_SORT
{
	en_grd_sort_up,
	en_grd_sort_down,
};
 
template<class _Ty>
struct gridding_node
{
	_Ty _value;
	struct gridding_node* _prev;
	struct gridding_node* _next;
 
	struct gridding_node* _upper;
	struct gridding_node* _downer;
 
	gridding_node()
		: _prev(NULL)
		, _next(NULL)
		, _upper(NULL)
		, _downer(NULL)
	{
	}
 
	bool is_header()
	{
		return _upper != NULL || _downer != NULL;
	}
};
 
///
/// 网状双向链表托管（类似跳跃表）
/// H1 = N11 = N12 = N13....
/// ||
/// H2 = N21 = N22....
/// ||
/// H3 = N31 = N32....
///
template<class _Ty, class _Ty_rule, EN_GRIDDING_SORT en>
class gridding_list
{
	typedef _Ty_rule(*FUNC_rule)(const _Ty& value);
	typedef bool(*FUNC_search_filter)(const _Ty& value);
private:
	gridding_node<_Ty>* m_pHeader;
	FUNC_rule m_pFuncRule;
private:
	static gridding_node<_Ty>* create_header(const _Ty & value)
	{
		gridding_node<_Ty>* pNewer = new gridding_node<_Ty>();
		pNewer->_value = value;
 
		gridding_node<_Ty>* pNewerNode = create_node(value);
		pNewer->_next = pNewerNode;
		pNewerNode->_prev = pNewer;
 
		return pNewer;
	}
	static gridding_node<_Ty>* create_node(const _Ty & value)
	{
		gridding_node<_Ty>* pNewer = new gridding_node<_Ty>();
		pNewer->_value = value;
 
		return pNewer;
	}
 
private:
	gridding_list()
	{
 
	}
 
	gridding_node<_Ty>* row_head(gridding_node<_Ty>* node)
	{
		gridding_node<_Ty>* head = node;
		if (node)
		{
			while (head->_prev)
				head = head->_prev;
		}
		return head;
	}
 
	gridding_node<_Ty>* row_end(gridding_node<_Ty>* node)
	{
		gridding_node<_Ty>* end = node;
		if (node)
		{
			while (end->_next)
				end = end->_next;
		}
		return end;
	}
 
public:
	gridding_list(FUNC_rule fnRule)
		: m_pHeader(NULL)
		, m_pFuncRule(fnRule)
	{
	}
 
	bool insert(const _Ty & value)
	{
		if (m_pFuncRule == NULL)
			return false;
		if (m_pHeader == NULL)
		{
			m_pHeader = create_header(value);
			return true;
		}
 
		gridding_node<_Ty>* pRow = NULL;
 
		if (m_pFuncRule(m_pHeader->_value) == m_pFuncRule(value))
			pRow = m_pHeader;
		else if ((m_pFuncRule(m_pHeader->_value) > m_pFuncRule(value) && en == en_grd_sort_up) 
			|| (m_pFuncRule(m_pHeader->_value) < m_pFuncRule(value) && en == en_grd_sort_down))
		{
			pRow = create_header(value);
			pRow->_downer = m_pHeader;
			m_pHeader->_upper = pRow;
			m_pHeader = pRow;
			return true;
		}
		else
		{
			gridding_node<_Ty>* pCurr = m_pHeader;
			while (pCurr->_downer)
			{
				if (m_pFuncRule(pCurr->_downer->_value) == m_pFuncRule(value))
				{
					pRow = pCurr->_downer;
					break;
				}
				else if ((m_pFuncRule(pCurr->_downer->_value) > m_pFuncRule(value) && en == en_grd_sort_up) 
					|| (m_pFuncRule(pCurr->_downer->_value) < m_pFuncRule(value) && en == en_grd_sort_down))
				{
					pRow = create_header(value);
					pRow->_downer = pCurr->_downer;
					pRow->_upper = pCurr;
					pCurr->_downer->_upper = pRow;
					pCurr->_downer = pRow;
					return true;
				}
				else
					pCurr = pCurr->_downer;
			}
			if (pRow == NULL)
			{
				if (pCurr)
				{
					pRow = create_header(value);
					pRow->_upper = pCurr;
					pCurr->_downer = pRow;
					return true;
				}
			}
		}
 
		if (pRow == NULL || pRow->_next == NULL)
			return false;
 
		gridding_node<_Ty>* pCurrNode = pRow->_next;
 
		while (pCurrNode)
		{
			if (pCurrNode->_value == value)
			{
				pCurrNode->_value.merge(value);
				return true;
			}
			else if ((pCurrNode->_value > value && en == en_grd_sort_up) 
				|| (pCurrNode->_value < value && en == en_grd_sort_down))
			{
				gridding_node<_Ty>* pCol = create_node(value);
 
				pCol->_next = pCurrNode;
				pCol->_prev = pCurrNode->_prev;
				pCurrNode->_prev->_next = pCol;
				pCurrNode->_prev = pCol;
				return true;
			}
			else
			{
				if (pCurrNode->_next == NULL)
				{
					gridding_node<_Ty>* pCol = create_node(value);
					pCurrNode->_next = pCol;
					pCol->_prev = pCurrNode;
					return true;
				}
				else
					pCurrNode = pCurrNode->_next;
			}
		}
		return false;
	}
 
	_Ty * search(const _Ty& value)
	{
		if (m_pFuncRule == NULL)
			return NULL;
		gridding_node<_Ty>* pCurr = m_pHeader;
		while (pCurr)
		{
			if (pCurr)
			{
				if (m_pFuncRule(pCurr->_value) == m_pFuncRule(value))
					break;
			}
			pCurr = pCurr->_downer;
		}
 
		if (pCurr)
		{
			pCurr = pCurr->_next;
			while (pCurr)
			{
				if (pCurr->_value == value)
					return &(pCurr->_value);
				pCurr = pCurr->_next;
			}
		}
 
		return NULL;
	}
 
	// 按半径搜索
	bool search_radius(const _Ty& center, uint32_t dwRadius, std::vector<_Ty>& vecRes)
	{
		if (m_pFuncRule == NULL)
			return false;
 
		gridding_node<_Ty>* pCurr = m_pHeader;
		while (pCurr)
		{
			if (m_pFuncRule(pCurr->_value) == m_pFuncRule(center))
				break;
			pCurr = pCurr->_downer;
		}
 
		if (pCurr)
		{
			pCurr = pCurr->_next;
			while (pCurr)
			{
				if (pCurr->_value == center)
					break;
				pCurr = pCurr->_next;
			}
		}
 
		if (pCurr == NULL)
			return false;
 
		vecRes.push_back(pCurr->_value);
 
		gridding_node<_Ty>* pCenter = pCurr;
 
		// 向前
		for (uint32_t i = 1; i < dwRadius; ++i)
		{
			if (pCurr->_prev && pCurr->_prev->is_header() == false)
			{
				pCurr = pCurr->_prev;
				vecRes.push_back(pCurr->_value);
			}
			else
			{
				// upper row
				gridding_node<_Ty>* pRowHead = row_head(pCurr);
				if (pRowHead && pRowHead->_upper)
				{
					// 取尾部
					pCurr = row_end(pRowHead->_upper);
					vecRes.push_back(pCurr->_value);
				}
				else
					break;
			}
		}
 
		pCurr = pCenter;
		// 向后
		for (uint32_t i = 1; i < dwRadius; ++i)
		{
			if (pCurr->_next)
			{
				pCurr = pCurr->_next;
				vecRes.push_back(pCurr->_value);
			}
			else
			{
				// downer row
				gridding_node<_Ty>* pRowHead = row_head(pCurr);
				if (pRowHead && pRowHead->_downer)
				{
					pCurr = pRowHead->_downer->_next;
					vecRes.push_back(pCurr->_value);
				}
				else
					break;
			}
		}
		return true;
	}
 
	// 按照自定规则搜索
	bool search_filter(const _Ty& center, FUNC_search_filter fnFilter, std::vector<_Ty>& vecRes)
	{
		if (m_pFuncRule == NULL)
			return false;
 
		gridding_node<_Ty>* pRow = m_pHeader;
		while (pRow)
		{
			if (m_pFuncRule(pRow->_value) == m_pFuncRule(center))
				break;
			pRow = pRow->_downer;
		}
 
		// 这里只找行，列就不找了
 
		if (pRow == NULL)
			return false;
		
		gridding_node<_Ty>* pCurr = pRow->_next;
		if (pCurr == NULL)
			return false;
 
		if(fnFilter == NULL || fnFilter(pCurr->_value))
			vecRes.push_back(pCurr->_value);
 
		// 向前
		while(true)
		{
			if (pCurr->_prev && pCurr->_prev->is_header() == false)
			{
				pCurr = pCurr->_prev;
 
				if (fnFilter == NULL || fnFilter(pCurr->_value))
					vecRes.push_back(pCurr->_value);
				else
					break; // 因为是排序表，fnFilter认为是已知该规则的筛选，如果出现不符的，前面的都不处理了
			}
			else
			{
				// upper row
				gridding_node<_Ty>* pRowHead = row_head(pCurr);
				if (pRowHead && pRowHead->_upper)
				{
					pCurr = row_end(pRowHead->_upper);
 
					if (fnFilter == NULL || fnFilter(pCurr->_value))
						vecRes.push_back(pCurr->_value);
					else
						break; // 因为是排序表，fnFilter认为是已知该规则的筛选，如果出现不符的，前面的都不处理了
				}
				else
					break;
			}
		}
 
		pCurr = pRow->_next;
		// 向后
		while (true)
		{
			if (pCurr->_next)
			{
				pCurr = pCurr->_next;
 
				if (fnFilter == NULL || fnFilter(pCurr->_value))
					vecRes.push_back(pCurr->_value);
				else
					break; // 因为是排序表，fnFilter认为是已知该规则的筛选，如果出现不符的，后面的都不处理了
			}
			else
			{
				// downer row
				gridding_node<_Ty>* pRowHead = row_head(pCurr);
				if (pRowHead && pRowHead->_downer)
				{
					pCurr = pRowHead->_downer->_next;
 
					if (fnFilter == NULL || fnFilter(pCurr->_value))
						vecRes.push_back(pCurr->_value);
					else
						break; // 因为是排序表，fnFilter认为是已知该规则的筛选，如果出现不符的，后面的都不处理了
				}
				else
					break;
			}
		}
		return true;
	}
 
	uint32_t rank(const _Ty& value)
	{
		uint32_t dwRank = 0;
		if (m_pFuncRule == NULL)
			return dwRank;
 
		gridding_node<_Ty>* pCurr = m_pHeader;
		while (pCurr)
		{
			pCurr = pCurr->_next;
			while (pCurr)
			{
				dwRank += pCurr->_value.size();
				if (pCurr->_value == center)
					break;
				pCurr = pCurr->_next;
			}
			
			if (m_pFuncRule(pCurr->_value) == m_pFuncRule(center))
				break;
 
			pCurr = pCurr->_downer;
		}
 
		return dwRank;
	}
};
 
// 测试用例
#include <vector>
struct grid_test_data
{
	uint32_t _key;
	std::vector<uint32_t> _value;
	uint32_t _count;
 
	grid_test_data()
		: _key(0)
		, _count(1)
	{
	}
 
	grid_test_data(uint32_t a)
	{
		_key = a;
		_count = 1;
	}
 
	grid_test_data& operator = (const grid_test_data& td)
	{
		_key = td._key;
		_value.clear();
		_value = td._value;
		return *this;
	}
 
	bool operator == (const grid_test_data& td)
	{
		return _key == td._key;
	}
 
	bool operator > (const grid_test_data& td)
	{
		return _key > td._key;
	}
 
	bool operator < (const grid_test_data& td)
	{
		return _key < td._key;
	}
 
	friend std::ostream& operator << (std::ostream& out, const grid_test_data& td)
	{
		out << td._key << "(" << td._count << ")";
		return out;
	}
 
	void merge(const grid_test_data& td)
	{
		_value.insert(_value.end(), td._value.begin(), td._value.end());
		_count += td._count;
	}
 
	uint32_t key()
	{
		return _key;
	}
	uint32_t key() const
	{
		return _key;
	}
	uint32_t count()
	{
		return _count;
	}
	uint32_t count() const
	{
		return _count;
	}
 
	std::vector<uint32_t>& value()
	{
		return _value;
	}
};

测试代码

template<class _T>  
uint32_t rule_calc_row(const _T& value)  
{  
    return value.key() / 100;  
}  
  
random_help rh;  
gridding_list<grid_test_data, uint32_t, en_grd_sort_up> g_list(rule_calc_row<grid_test_data>);  
for (int i = 0; i < 1024 * 1024; ++i)  
{  
    grid_test_data td01(rh(1, 10240));  
    if (g_list.insert(td01) == false)  
    {  
        std::cout << __FUNCTION__ << "," << __LINE__ << td01.key() << std::endl;  
        break;  
    }  
}  

测试结果

上面是测试用的规则、测试代码，random_help是之前写的一个随机函数类 centos开发环境 1024 * 1024 分散量级 10240的数据实际插入耗时是4.6s 单条查找耗时 < 1ms