int* p = new int;

delete p;

typedef basic_string<char, char_traits<char>, allocator<char> > string;

typedef basic_string<char, char_traits<char>, MemoryPoll<char> > mystring;

#ifndef PPX_BASE_MEMORY_POOL_H_
#define PPX_BASE_MEMORY_POOL_H_

#include <climits>
#include <cstddef>
#include <mutex>

namespace ppx {
    namespace base {
        template <typename T, size_t BlockSize = 4096, bool ZeroOnDeallocate = true>
        class MemoryPool {
        public:
            /* Member types */
            typedef T               value_type;
            typedef T*              pointer;
            typedef T&              reference;
            typedef const T*        const_pointer;
            typedef const T&        const_reference;
            typedef size_t          size_type;
            typedef ptrdiff_t       difference_type;
            typedef std::false_type propagate_on_container_copy_assignment;
            typedef std::true_type  propagate_on_container_move_assignment;
            typedef std::true_type  propagate_on_container_swap;

            template <typename U> struct rebind {
                typedef MemoryPool<U> other;
            };

            /* Member functions */
            MemoryPool() noexcept;
            MemoryPool(const MemoryPool& memoryPool) noexcept;
            MemoryPool(MemoryPool&& memoryPool) noexcept;
            template <class U> MemoryPool(const MemoryPool<U>& memoryPool) noexcept;

            ~MemoryPool() noexcept;

            MemoryPool& operator=(const MemoryPool& memoryPool) = delete;
            MemoryPool& operator=(MemoryPool&& memoryPool) noexcept;

            pointer address(reference x) const noexcept;
            const_pointer address(const_reference x) const noexcept;

            // Can only allocate one object at a time. n and hint are ignored
            pointer allocate(size_type n = 1, const_pointer hint = 0);
            void deallocate(pointer p, size_type n = 1);

            size_type max_size() const noexcept;

            template <class U, class... Args> void construct(U* p, Args&&... args);
            template <class U> void destroy(U* p);

            template <class... Args> pointer newElement(Args&&... args);
            void deleteElement(pointer p);

        private:
            struct Element_ {
                Element_* pre;
                Element_* next;
            };

            typedef char* data_pointer;
            typedef Element_ element_type;
            typedef Element_* element_pointer;

            element_pointer data_element_;
            element_pointer free_element_;

            std::recursive_mutex m_;

            size_type padPointer(data_pointer p, size_type align) const noexcept;
            void allocateBlock();

            static_assert(BlockSize >= 2 * sizeof(element_type), "BlockSize too small.");
        };


        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::size_type
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::padPointer(data_pointer p, size_type align)
            const noexcept {
            uintptr_t result = reinterpret_cast<uintptr_t>(p);
            return ((align - result) % align);
        }



        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::MemoryPool()
            noexcept {
            data_element_ = nullptr;
            free_element_ = nullptr;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::MemoryPool(const MemoryPool& memoryPool)
            noexcept :
            MemoryPool() {
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::MemoryPool(MemoryPool&& memoryPool)
            noexcept {
            std::lock_guard<std::recursive_mutex> lock(m_);

            data_element_ = memoryPool.data_element_;
            memoryPool.data_element_ = nullptr;
            free_element_ = memoryPool.free_element_;
            memoryPool.free_element_ = nullptr;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        template<class U>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::MemoryPool(const MemoryPool<U>& memoryPool)
            noexcept :
            MemoryPool() {
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>&
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::operator=(MemoryPool&& memoryPool)
            noexcept {
            std::lock_guard<std::recursive_mutex> lock(m_);

            if (this != &memoryPool) {
                std::swap(data_element_, memoryPool.data_element_);
                std::swap(free_element_, memoryPool.free_element_);
            }
            return *this;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::~MemoryPool()
            noexcept {
            std::lock_guard<std::recursive_mutex> lock(m_);

            element_pointer curr = data_element_;
            while (curr != nullptr) {
                element_pointer prev = curr->next;
                operator delete(reinterpret_cast<void*>(curr));
                curr = prev;
            }

            curr = free_element_;
            while (curr != nullptr) {
                element_pointer prev = curr->next;
                operator delete(reinterpret_cast<void*>(curr));
                curr = prev;
            }
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::pointer
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::address(reference x)
            const noexcept {
            return &x;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::const_pointer
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::address(const_reference x)
            const noexcept {
            return &x;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::allocateBlock() {
            // Allocate space for the new block and store a pointer to the previous one
            data_pointer new_block = reinterpret_cast<data_pointer> (operator new(BlockSize));
            element_pointer new_ele_pointer = reinterpret_cast<element_pointer>(new_block);
            new_ele_pointer->pre = nullptr;
            new_ele_pointer->next = nullptr;

            if (data_element_) {
                data_element_->pre = new_ele_pointer;
            }

            new_ele_pointer->next = data_element_;
            data_element_ = new_ele_pointer;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::pointer
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::allocate(size_type n, const_pointer hint) {
            std::lock_guard<std::recursive_mutex> lock(m_);

            if (free_element_ != nullptr) {
                data_pointer body =
                    reinterpret_cast<data_pointer>(reinterpret_cast<data_pointer>(free_element_) + sizeof(element_type));

                size_type bodyPadding = padPointer(body, alignof(element_type));

                pointer result = reinterpret_cast<pointer>(reinterpret_cast<data_pointer>(body + bodyPadding));

                element_pointer tmp = free_element_;

                free_element_ = free_element_->next;

                if (free_element_)
                    free_element_->pre = nullptr;

                tmp->next = data_element_;
                if (data_element_)
                    data_element_->pre = tmp;
                tmp->pre = nullptr;
                data_element_ = tmp;

                return result;
            }
            else {
                allocateBlock();

                data_pointer body =
                    reinterpret_cast<data_pointer>(reinterpret_cast<data_pointer>(data_element_) + sizeof(element_type));

                size_type bodyPadding = padPointer(body, alignof(element_type));

                pointer result = reinterpret_cast<pointer>(reinterpret_cast<data_pointer>(body + bodyPadding));

                return result;
            }
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        inline void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::deallocate(pointer p, size_type n) {
            std::lock_guard<std::recursive_mutex> lock(m_);

            if (p != nullptr) {
                element_pointer ele_p =
                    reinterpret_cast<element_pointer>(reinterpret_cast<data_pointer>(p) - sizeof(element_type));

                if (ZeroOnDeallocate) {
                    memset(reinterpret_cast<data_pointer>(p), 0, BlockSize - sizeof(element_type));
                }

                if (ele_p->pre) {
                    ele_p->pre->next = ele_p->next;
                }

                if (ele_p->next) {
                    ele_p->next->pre = ele_p->pre;
                }

                if (ele_p->pre == nullptr) {
                    data_element_ = ele_p->next;
                }

                ele_p->pre = nullptr;
                if (free_element_) {
                    ele_p->next = free_element_;
                    free_element_->pre = ele_p;
                }
                else {
                    ele_p->next = nullptr;
                }
                free_element_ = ele_p;
            }
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::size_type
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::max_size()
            const noexcept {
            size_type maxBlocks = -1 / BlockSize;
            return (BlockSize - sizeof(data_pointer)) / sizeof(element_type) * maxBlocks;
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        template <class U, class... Args>
        inline void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::construct(U* p, Args&&... args) {
            new (p) U(std::forward<Args>(args)...);
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        template <class U>
        inline void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::destroy(U* p) {
            p->~U();
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        template <class... Args>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::pointer
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::newElement(Args&&... args) {
            std::lock_guard<std::recursive_mutex> lock(m_);
            pointer result = allocate();
            construct<value_type>(result, std::forward<Args>(args)...);
            return result;
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        inline void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::deleteElement(pointer p) {
            std::lock_guard<std::recursive_mutex> lock(m_);
            if (p != nullptr) {
                p->~value_type();
                deallocate(p);
            }
        }
    }
}

#endif // PPX_BASE_MEMORY_POOL_H_


使用示例：
#include <iostream>
#include <thread>
using namespace std;
class Apple {
public:
    Apple() {
        id_ = 0;
        cout << "Apple()" << endl;
    }

    Apple(int id) {
        id_ = id;
        cout << "Apple(" << id_ << ")" << endl;
    }

    ~Apple() {
        cout << "~Apple()" << endl;
    }

    void SetId(int id) {
        id_ = id;
    }

    int GetId() {
        return id_;
    }
private:
    int id_;
};



void ThreadProc(ppx::base::MemoryPool<char> *mp) {
    int i = 0;
    while (i++ < 100000) {
        char* p0 = (char*)mp->allocate();

        char* p1 = (char*)mp->allocate();

        mp->deallocate(p0);

        char* p2 = (char*)mp->allocate();

        mp->deallocate(p1);
        
        mp->deallocate(p2);

    }
}

int main()
{
    ppx::base::MemoryPool<char> mp;
    int i = 0;
    while (i++ < 100000) {
        char* p0 = (char*)mp.allocate();

        char* p1 = (char*)mp.allocate();

        mp.deallocate(p0);

        char* p2 = (char*)mp.allocate();

        mp.deallocate(p1);

        mp.deallocate(p2);

    }

    std::thread th0(ThreadProc, &mp);
    std::thread th1(ThreadProc, &mp);
    std::thread th2(ThreadProc, &mp);

    th0.join();
    th1.join();
    th2.join();

    Apple *apple = nullptr;
    {
        ppx::base::MemoryPool<Apple> mp2;
        apple = mp2.newElement(10);
        int a = apple->GetId();
        apple->SetId(10);
        a = apple->GetId();

        mp2.deleteElement(apple);
    }

    apple->SetId(12);
    int b = -4 % 4;

    int *a = nullptr;
    {
        ppx::base::MemoryPool<int, 18> mp3;
        a =  mp3.allocate();
        *a = 100;
        //mp3.deallocate(a);

        int *b =  mp3.allocate();
        *b = 200;
        //mp3.deallocate(b);

        mp3.deallocate(a);
        mp3.deallocate(b);

        int *c = mp3.allocate();
        *c = 300;
    }

    getchar();
    return 0;
}

#pragma once

#include "Common.h"

class ThreadCache
{
private:
	Freelist _freelist[NLISTS];//自由鏈表

public:
	//申請和釋放內存對象
	void* Allocate(size_t size);
	void Deallocate(void* ptr, size_t size);

	//從中心緩存獲取對象
	void* FetchFromCentralCache(size_t index, size_t size);

	//釋放對象時，鏈表過長時，回收內存回到中心堆
	void ListTooLong(Freelist* list, size_t size);
};

//靜態的，不是所有可見
//每個線程有個自己的指針, 用(_declspec (thread))，我們在使用時，每次來都是自己的，就不用加鎖了
//每個線程都有自己的tlslist
_declspec (thread) static ThreadCache* tlslist = nullptr;

//專門用來計算大小位置的類
class SizeClass
{
public:
	//獲取Freelist的位置
	inline static size_t _Index(size_t size, size_t align)
	{
		size_t alignnum = 1 << align;  //庫里實現的方法
		return ((size + alignnum - 1) >> align) - 1;
	}

	inline static size_t _Roundup(size_t size, size_t align)
	{
		size_t alignnum = 1 << align;
		return (size + alignnum - 1)&~(alignnum - 1);
	}

public:
	// 控制在12%左右的內碎片浪費
	// [1,128]				8byte對齊 freelist[0,16)
	// [129,1024]			16byte對齊 freelist[16,72)
	// [1025,8*1024]		128byte對齊 freelist[72,128)
	// [8*1024+1,64*1024]	1024byte對齊 freelist[128,184)

	inline static size_t Index(size_t size)
	{
		assert(size <= MAX_BYTES);

		// 每個區間有多少個鏈
		static int group_array[4] = { 16, 56, 56, 56 };
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size - 128, 4) + group_array[0];
		}
		else if (size <= 8192)
		{
			return _Index(size - 1024, 7) + group_array[0] + group_array[1];
		}
		else//if (size <= 65536)
		{
			return _Index(size - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
		}
	}

	// 對齊大小計算，向上取整
	static inline size_t Roundup(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		if (bytes <= 128){
			return _Roundup(bytes, 3);
		}
		else if (bytes <= 1024){
			return _Roundup(bytes, 4);
		}
		else if (bytes <= 8192){
			return _Roundup(bytes, 7);
		}
		else {//if (bytes <= 65536){
			return _Roundup(bytes, 10);
		}
	}

	//動態計算從中心緩存分配多少個內存對象到ThreadCache中
	static size_t NumMoveSize(size_t size)
	{
		if (size == 0)
			return 0;

		int num = (int)(MAX_BYTES / size);
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	// 根據size計算中心緩存要從頁緩存獲取多大的span對象
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num*size;
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;
		return npage;
	}
};

#pragma once

#include "Common.h"

//上面的ThreadCache里面沒有的話，要從中心獲取

/*
進行資源的均衡，對于ThreadCache的某個資源過剩的時候，可以回收ThreadCache內部的的內存
從而可以分配給其他的ThreadCache
只有一個中心緩存，對于所有的線程來獲取內存的時候都應該是一個中心緩存
所以對于中心緩存可以使用單例模式來進行創建中心緩存的類
對于中心緩存來說要加鎖
*/

//設計成單例模式
class CentralCache
{
public:
	static CentralCache* Getinstence()
	{
		return &_inst;
	}

	//從page cache獲取一個span
	Span* GetOneSpan(SpanList& spanlist, size_t byte_size);

	//從中心緩存獲取一定數量的對象給threa cache
	size_t FetchRangeObj(void*& start, void*& end, size_t n, size_t byte_size);

	//將一定數量的對象釋放給span跨度
	void ReleaseListToSpans(void* start, size_t size);

private:
	SpanList _spanlist[NLISTS];

private:
	CentralCache(){}//聲明不實現，防止默認構造，自己創建

	CentralCache(CentralCache&) = delete;
	static CentralCache _inst;
};

//Span是一個跨度，既可以分配內存出去，也是負責將內存回收回來到PageCache合并
//是一鏈式結構，定義為結構體就行，避免需要很多的友元
struct Span
{
	PageID _pageid = 0;//頁號
	size_t _npage = 0;//頁數

	Span* _prev = nullptr;
	Span* _next = nullptr;

	void* _list = nullptr;//鏈接對象的自由鏈表，后面有對象就不為空，沒有對象就是空
	size_t _objsize = 0;//對象的大小

	size_t _usecount = 0;//對象使用計數,
};

//和上面的Freelist一樣，各個接口自己實現，雙向帶頭循環的Span鏈表
class SpanList
{
public:
	Span* _head;
	std::mutex _mutex;

public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	~SpanList()//釋放鏈表的每個節點
	{
		Span * cur = _head->_next;
		while (cur != _head)
		{
			Span* next = cur->_next;
			delete cur;
			cur = next;
		}
		delete _head;
		_head = nullptr;
	}

	//防止拷貝構造和賦值構造，將其封死，沒有拷貝的必要，不然就自己會實現淺拷貝
	SpanList(const SpanList&) = delete;
	SpanList& operator=(const SpanList&) = delete;

	//左閉右開
	Span* Begin()//返回的一個數據的指針
	{
		return _head->_next;
	}

	Span* End()//最后一個的下一個指針
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	//在pos位置的前面插入一個newspan
	void Insert(Span* cur, Span* newspan)
	{
		Span* prev = cur->_prev;

		//prev newspan cur
		prev->_next = newspan;
		newspan->_next = cur;

		newspan->_prev = prev;
		cur->_prev = newspan;
	}

	//刪除pos位置的節點
	void Erase(Span* cur)//此處只是單純的把pos拿出來，并沒有釋放掉，后面還有用處
	{
		Span* prev = cur->_prev;
		Span* next = cur->_next;

		prev->_next = next;
		next->_prev = prev;
	}

	//尾插
	void PushBack(Span* newspan)
	{
		Insert(End(), newspan);
	}

	//頭插
	void PushFront(Span* newspan)
	{
		Insert(Begin(), newspan);
	}

	//尾刪
	Span* PopBack()//實際是將尾部位置的節點拿出來
	{
		Span* span = _head->_prev;
		Erase(span);

		return span;
	}

	//頭刪
	Span* PopFront()//實際是將頭部位置節點拿出來
	{
		Span* span = _head->_next;
		Erase(span);

		return span;
	}

	void Lock()
	{
		_mutex.lock();
	}

	void Unlock()
	{
		_mutex.unlock();
	}
};

#pragma once

#include "Common.h"

//對于Page Cache也要設置為單例，對于Central Cache獲取span的時候
//每次都是從同一個page數組中獲取span
//單例模式
class PageCache
{
public:
	static PageCache* GetInstence()
	{
		return &_inst;
	}

	Span* AllocBigPageObj(size_t size);
	void FreeBigPageObj(void* ptr, Span* span);

	Span* _NewSpan(size_t n);
	Span* NewSpan(size_t n);//獲取的是以頁為單位

	//獲取從對象到span的映射
	Span* MapObjectToSpan(void* obj);

	//釋放空間span回到PageCache，并合并相鄰的span
	void ReleaseSpanToPageCache(Span* span);

private:
	SpanList _spanlist[NPAGES];
	//std::map<PageID, Span*> _idspanmap;
	std::unordered_map<PageID, Span*> _idspanmap;

	std::mutex _mutex;
private:
	PageCache(){}

	PageCache(const PageCache&) = delete;
	static PageCache _inst;
};