Cache满载的LRU置换2

/*
* Author:  caoshanshan
* Email:   me@dreamyouxi.com

LRU for manage cache

*/

#pragma once

#include "global_def.h"
#include <iostream>
#include <unordered_map>
#include <vector>
#include "base/memory.h"
#include <assert.h>

#if _DEBUG
//debug check
void LRUIncNodeRefCount();
void LRUDecNodeRefCount();

void LRUIncRefCount();
void LRUDecRefCount();

void LRUCheckRefCount();

#endif


/**
* @brief LRU for cache ,you can use this to manage your cache-data
* @note do not copy this
*/
//内部结构采用 std::unordered_map 不适用于 数量特别大的 结构 
//大的结构需要用std::map 了 std::map 后面有需要的时候 再加吧
template<typename Key>
class LRUHashMap
{
	//double-linked list for LRU
	class delist_node
	{
	public:
		delist_node()
		{
#if _DEBUG
			LRUIncNodeRefCount();
#endif
		}
		delist_node(const delist_node&other) = delete;
		~delist_node()
		{
#if _DEBUG
			LRUIncNodeRefCount();
#endif
		}
		delist_node *pre = nullptr;
		delist_node*next = nullptr;
		Key data;
	};
public:
	LRUHashMap()
	{
#if _DEBUG
		LRUIncRefCount();
#endif
	}
	//disallow copy ctor
	LRUHashMap(const LRUHashMap&other) = delete;
	~LRUHashMap()
	{
#if _DEBUG
		Check();
		LRUDecRefCount();
#endif
		while (DeleteTail() > 1);
		//head may be is equal to tail
		if (head && head != tail)
		{
			delete head;
		}
		if (tail)
		{
			delete tail;
		}
	}
	/**
	* @brief use one element key
	* @return elements's count in the LRU
	*/
	int Use(const Key & key)
	{
#if _DEBUG
		Check();
#endif
		auto it_node = lru.find(key);
		if (it_node == lru.end())
		{
			//has not find
			auto node = new delist_node();
			node->data = key;
			node->next = head;
			if (head)
			{
				head->pre = node;
			}
			head = node;
			if (tail == nullptr)
			{
				tail = head;
			}
			lru[key] = node;
#if _DEBUG
			Check();
#endif
			return lru.size();
		}
		int size = lru.size();
		delist_node *node = it_node->second;
		//case 1
		if (size == 1)
		{
			assert(head == tail);
			assert(head->next == nullptr && head->pre == nullptr);
			head = node;
			tail = node;
			assert(node->pre == nullptr);
			assert(node->next == nullptr);
			node->next = nullptr;
			node->pre = nullptr;
		}
		//case 2
		else if (size == 2)
		{
			assert(head != tail);
			assert(head->next == tail);
			assert(tail->pre == head);
			assert(head->pre == nullptr && tail->next == nullptr);
			if (head == node)
			{
				//use is head
				assert(node->pre == nullptr);
			}
			else if (node == tail)
			{
				//use is tail
				assert(node->next == nullptr);
				assert(tail != head);
				assert(head->next == tail);
				assert(head->pre == nullptr);
				assert(tail->pre == head);
				assert(tail->next == nullptr);
				auto tmp = head;
				head = tail;
				tail = tmp;

				head->next = head->pre;
				head->pre = nullptr;

				tail->pre = tail->next;
				tail->next = nullptr;

			}
			else
			{
				assert(false);
			}
		}
		//case 3
		else
		{
			if (node == head)
			{
				//use is head

			}
			else if (node == tail)
			{
				//use is tail
				assert(node->next == nullptr);
				assert(node->pre != nullptr);
				auto tmp = tail;
				tail = tail->pre;
				tail->next = nullptr;
				head->pre = tmp;
				tmp->pre = nullptr;
				tmp->next = head;
				head = tmp;
			}
			else
			{
				assert(node->next);
				assert(node->pre);
				assert(node->next != node->pre);

				node->next->pre = node->pre;
				node->pre->next = node->next;

				node->pre = nullptr;
				head->pre = node;
				node->next = head;
				head = node;
			}
		}
#if _DEBUG
		Check();
#endif
		return lru.size();
	}

	/**
	* @brief delete key use
	*/
	void Delete(const Key & key)
	{
#if _DEBUG
		Check();
#endif
		int size = lru.size();
		if (size == 0)
		{
			assert(head == nullptr);
			assert(tail == nullptr);

			head = nullptr;
			tail = nullptr;
			return;
		}
		else if (size == 1)
		{
			assert(head == tail);
			assert(head->next == nullptr);
			assert(head->pre == nullptr);
			assert(tail->next == nullptr);
			assert(tail->pre == nullptr);
			if (head->data == key)
			{
				delete lru.begin()->second;
				lru.clear();
				head = nullptr;
				tail = nullptr;
			}
#if _DEBUG
			Check();
#endif
			return;
		}
		auto it_node = lru.find(key);
		if (it_node == lru.end())
		{
			//this key is not exist ignore it
		}
		else
		{
			//has been exist 
			delist_node *node = it_node->second;
			if (size == 2)
			{
				assert(head->pre == nullptr);
				assert(tail->next == nullptr);
				assert(head != tail);

				if (head->data == key)
				{
					//delete is head
					lru.erase(it_node);
					delete head;
					head = tail;
					tail->pre = nullptr;
				}
				else if (tail->data == key)
				{
					//delete is tail
					lru.erase(it_node);
					delete tail;
					tail = head;
					head->next = nullptr;
				}
				else
				{
					assert(false);
				}
			}
			else
			{
				//case 1
				if (node == head)
				{
					//delete is head
					assert(head->next);
					assert(head->pre == nullptr);
					auto new_head = head->next;
					delete head;
					head = new_head;
					head->pre = nullptr;
					lru.erase(it_node);
				}
				else if (node == tail)
				{
					//delete is tail
					assert(node->next == nullptr);
					assert(node->pre);
					auto new_tail = node->pre;
					delete tail;
					lru.erase(it_node);
					tail = new_tail;
					tail->next = nullptr;
				}
				else
				{
					node->next->pre = node->pre;
					node->pre->next = node->next;
					delete node;
					lru.erase(it_node);
				}
			}
		}
#if _DEBUG
		Check();
#endif
	}
	int Size()
	{
		return lru.size();
	}

	int DeleteTail()
	{
#if _DEBUG
		Check();
#endif
		if (tail)
		{
			assert(lru.find(tail->data) != lru.end());
			assert(tail->next == nullptr);
			if (tail->pre)
			{
				assert(tail->pre->next == tail);
				assert(lru.size() > 1);
				lru.erase(tail->data);
				auto new_tail = tail->pre;
				new_tail->next = nullptr;
				delete tail;
				tail = new_tail;
			}
			else
			{
				assert(lru.size() == 1);
				delete tail;
				lru.clear();
				tail = nullptr;
				head = nullptr;
			}
		}
		else
		{
			assert(lru.size() == 0);
			lru.clear();
			if (head)
			{
				assert(false);
				delete head;
			}
			tail = nullptr;
			head = nullptr;
		}
#if _DEBUG
		Check();
#endif
		return lru.size();
	}

	bool HasTail()
	{
		return tail != nullptr;
	}
	/**
	* @brief please call this after HasTail() == true
	*/
	const Key & GetTail()
	{
		if (tail)
		{
			return tail->data;
		}
		return Key();
	}
#if _DEBUG
	void Check()
	{
		if (lru.size() == 0)
		{
			assert(head == nullptr);
			assert(tail == nullptr);
		}
		else if (lru.size() == 1)
		{
			assert(head&&head == tail);
			assert(head->next == nullptr);
			assert(head->pre == nullptr);
		}
		else if (lru.size() == 2)
		{
			assert(head != tail);
			assert(head->next == tail);
			assert(head->pre == nullptr);
			assert(tail->next == nullptr);
			assert(tail->pre == head);
		}
		else
		{
			//check head can reach tail
			{
				int loop = lru.size() + 3;
				auto node = head;
				while (node != tail)
				{
					--loop;
					if (loop < 0)
					{
						assert(false);
					}
					node = node->next;
				}
			}
			//check tail can reach head
			{
				int loop = lru.size() + 3;
				auto node = tail;
				while (node != head)
				{
					--loop;
					if (loop < 0)
					{
						assert(false);
					}
					node = node->pre;
				}
			}
		}
	}

	//------------------------------------------------------test case
	void AutoTest()
	{
		Use(1);
		Use(1);

		Use(2);
		Use(2);
		Use(1);

		for (int i = 0; i < 1000; i++)
		{
			Use(rand() % 10000 + 1);
			if (rand() % 3 == 2)
			{
				Delete(rand() % 20000);
			}
			if (rand() % 10 == 3)
			{
				DeleteTail();
			}
		}
		while (DeleteTail());

		for (int i = 0; i < 3; i++)
		{
			Use(rand() % 10 + 1);
		}
	}
	void PrintStatus()
	{
		std::vector <Key> _data;
		{
			auto node = head;
			while (node)
			{
				//	std::cout << node->data << std::endl;
				_data.push_back(node->data);
				node = node->next;
			}
			//	std::cout << "         111 " << std::endl;
		}
		std::vector<Key>_data2;
		_data2.resize(_data.size());
		int index = _data.size();
		{
			auto node = tail;
			while (node)
			{
				//	std::cout << node->data << std::endl;
				_data2[--index] = node->data;
				node = node->pre;
			}
			//	std::cout << "         222 " << std::endl;
		}
		{
			//检查 乱序否
			int id = _data2.size();
			for (int i = 0; i < _data2.size(); i++)
			{
				assert(_data2[i] == _data[i]);
			}
		}
	}
#endif

private:
	std::unordered_map<Key, delist_node*> lru;
	delist_node *head = nullptr;//least use
	delist_node*tail = nullptr;// has long time not use
};