C++基础：内存池

  1 #pragma once
  2 
  3 #ifndef __LC_LIST_H
  4     #define __LC_LIST_H
  5 
  6 namespace LC
  7 {
  8     
  9 template<typename T>
 10 class Node final
 11 {
 12 public:
 13     Node(){}
 14     explicit Node(Node<T>* next, T&& data) noexcept : _data(std::move(data)), _next(next) {}
 15     explicit Node(Node<T>* next, const T& data) noexcept : _data(data), _next(next) {}
 16     explicit Node(Node<T>* pre, Node<T>* next, const T& data) noexcept : _pre(pre), _data(data), _next(next) {}
 17 
 18 public:
 19     inline T& data() noexcept { return _data; }
 20 
 21     template <typename... TArgs>
 22     inline void emplace(TArgs&& ...args){ new(&_data)T(args...); }
 23 
 24     inline void pack(T&& data) noexcept { _data = std::move(data); }
 25     inline void pack(const T& data) noexcept { _data = data; }
 26 
 27     inline void link(Node<T>* next) noexcept { _next = next; if(next != nullptr) next->_pre = this; }
 28 
 29 public:
 30     T _data;
 31     Node<T>* _next = nullptr;
 32     Node<T>* _pre = nullptr;
 33 };
 34 
 35 template<typename T>
 36 class List
 37 {
 38 public:
 39     List() {}  //init head.
 40     ~List() { while(_size > 0) pop(); }
 41 
 42 public:
 43     //insert at beginning.
 44     bool push(Node<T>* node)
 45     {
 46         if(node == nullptr)
 47             return false;
 48 
 49         Node<T>* first = _root._next;
 50         _root.link(node);
 51         node->link(first);
 52         ++_size;
 53         return true;
 54     }
 55 
 56     bool insert(const T& data) 
 57     { 
 58         Node<T>* ins = alloc();
 59         if(ins == nullptr) 
 60             return false;
 61 
 62         ins->pack(data);
 63 
 64         return push(ins);
 65     };
 66 
 67     bool insert(T&& data) 
 68     { 
 69         Node<T>* ins = alloc();
 70         
 71         if(ins == nullptr) 
 72             return false;
 73 
 74         ins->pack(std::move(data));
 75         
 76         return push(ins);
 77     };
 78 
 79     template<typename... TArgs> 
 80     bool emplace(TArgs&& ...args)
 81     {
 82         Node<T>* ins = alloc(args...);
 83         Node<T>* first = nullptr;
 84         if(ins == nullptr) return false;
 85 
 86         return push(ins);
 87     }
 88     
 89     inline Node<T>* begin() noexcept { return _root._next; }
 90     inline void pop() noexcept 
 91     { 
 92         delete pop_not_free();
 93     }
 94 
 95     inline Node<T>* pop_not_free() noexcept
 96     {
 97         Node<T>* first = begin();
 98         if(first == nullptr)
 99             return nullptr;
100 
101         Node<T>* second = first->_next;
102         _root.link(second);
103         --_size;
104 
105         return first;
106     }
107 
108     inline void erase(Node<T>* node) noexcept
109     {
110         if(node == nullptr || node->_pre == nullptr)
111             return;
112 
113         node->_pre->link(node->_next);
114         --_size;
115         delete node;
116     }
117 
118     inline size_t size() const noexcept { return _size; }
119 
120 private:
121     template<typename... TArgs> 
122     inline Node<T>* alloc(TArgs&& ...args) 
123     { 
124         Node<T>* ret = new(std::nothrow) Node<T>(); 
125         if(ret != nullptr) ret->emplace(args...);
126         return ret;
127     }
128 
129     inline Node<T>* alloc() { return new(std::nothrow) Node<T>(); }
130 
131 public:
132     Node<T> _root;
133     size_t _size = 0;
134 };
135 
136 }; // namespace LC
137 #endif

  1 /**
  2  * @brief Memory pool, it‘s not thread-safe.
  3  * @author Even
  4  * @date 2021-06-07 
  5  * 
  6  */
  7 
  8 #pragma once
  9 
 10 #ifndef __MEM_POOL_H_
 11     #define __MEM_POOL_H_
 12 
 13 #include <memory>
 14 
 15 #include "./list/list.h"
 16 
 17 namespace LC
 18 {
 19 
 20 inline static constexpr int ALIGN = 8;
 21 inline static constexpr int BLOCK_MAX = 1024;
 22 inline static constexpr int BLOCK_CAP = BLOCK_MAX / ALIGN;
 23 inline static constexpr int BUCKET_CAP = BLOCK_MAX;
 24 
 25 static_assert(ALIGN % 8 == 0);
 26 static_assert(BLOCK_MAX % ALIGN == 0);
 27 
 28 inline constexpr int __Align(int num_) noexcept { return (num_ + ALIGN - 1) & ~(ALIGN - 1); }
 29 inline constexpr int __Sit(int index_) noexcept { return (index_ + 1) * ALIGN; }
 30 inline constexpr int __Index(int num_) noexcept { return (num_ + ALIGN - 1) / ALIGN - 1; }
 31 
 32 struct __Block 
 33 { 
 34     __Block* _next = nullptr; 
 35 };
 36 
 37 struct __CacheBlock
 38 {
 39     __CacheBlock(){}
 40     __CacheBlock(char* ptr, int size) 
 41         : _ptr(ptr), _size(size){}
 42 
 43     std::unique_ptr<char[]> _ptr;
 44     int _size = 0;
 45 };
 46 
 47 class __MemCache
 48 {
 49 private:
 50     __MemCache(){}
 51     ~__MemCache(){}
 52 
 53 private:
 54     inline void Create(int size) { size = __Align(size); _cache.emplace((char*)malloc(size), size); }
 55 
 56     //@return list.
 57     struct ApplyRet{__Block* _b; __Block* _e;};
 58     ApplyRet Apply(int& block_size, int& count);
 59     
 60 private:
 61     friend class MemPool;
 62     List<__CacheBlock> _cache;
 63 };
 64 
 65 class MemPool
 66 {
 67 public:
 68     MemPool();
 69     ~MemPool();
 70 
 71 public:
 72     static inline MemPool& Instance() noexcept { static MemPool ins_; return ins_; }
 73 
 74 public:
 75     void* Alloc(int size);
 76     template<typename T> void* Alloc() { return Alloc(sizeof(T)); }
 77 
 78     void Free(void* ptr, int size);
 79     template<typename T> void Free(T* ptr) { Free(ptr, sizeof(T)); }
 80 
 81 private:
 82     void Fill(int index, int count);
 83 
 84 private:
 85     __MemCache _mem_cache;
 86     __Block* _free[BLOCK_CAP];
 87 };
 88 
 89 #define __BUCKET_COUNT (64)
 90 
 91 class MemPoolThreadSafe
 92 {
 93 public:
 94     struct __ThreadMemPool
 95     {
 96         __ThreadMemPool(){}
 97         __ThreadMemPool(int id, MemPool* pool) : _id(id), _pool(pool) {}
 98         int _id = 0;
 99         std::unique_ptr<MemPool> _pool;
100     };
101 
102 public:
103     MemPoolThreadSafe() noexcept;
104     ~MemPoolThreadSafe();
105 
106 public:
107     inline static MemPoolThreadSafe& Instance() noexcept { static MemPoolThreadSafe ins_; return ins_; }
108     uint32_t GetThreadID();
109 
110 public:
111     void* Alloc(int size);
112     void Free(void* ptr, int size);
113 
114     template<typename T> void* Alloc() { return Alloc(sizeof(T)); }
115     template<typename T> void Free(T* ptr) { Free(ptr, sizeof(T)); }
116 
117 private:
118     List<__ThreadMemPool> _forThreadMemPool[__BUCKET_COUNT];
119 };
120 
121 #define G_MemoryPool LC::MemPoolThreadSafe::Instance()
122 
123 
124 };
125 
126 #endif //!__MEM_POOL_H_

  1 #include "lc_mempool.h"
  2 #include <thread>
  3 
  4 #define DEFAULT_EACH_BLOCK_STORE 16
  5 
  6 namespace LC
  7 {
  8 
  9 __MemCache::ApplyRet __MemCache::Apply(int& block_size, int& count)
 10 {
 11     block_size = __Align(block_size);
 12     int need_size = block_size * count;
 13 
 14     {
 15         int def_size = block_size * DEFAULT_EACH_BLOCK_STORE;
 16 
 17         auto* node = _cache.begin();
 18         if(node == nullptr || node->data()._size <= 0)
 19             Create(need_size > def_size ? need_size : def_size);
 20     }
 21 
 22     __CacheBlock& block = _cache.begin()->data();
 23     char* ptr = block._ptr.get();
 24     int& size = block._size;
 25 
 26     if(size <= block_size)
 27     {
 28         block_size = size;
 29         count = 1;
 30         return ApplyRet{(__Block*)(ptr), (__Block*)(ptr)};
 31     }
 32 
 33     __Block * list = nullptr,
 34             * begin = nullptr,
 35             * end = nullptr;
 36 
 37     int ret_count = 0;
 38     for (;size >= block_size;)
 39     {
 40         char* block_ptr = ptr + size - block_size;
 41 
 42         if(list == nullptr)
 43         {
 44             list = (__Block*)(block_ptr);
 45             begin = end = list;
 46         }
 47         else
 48         {
 49             list->_next = (__Block*)(block_ptr);
 50             end = list = list->_next;
 51         }
 52 
 53         size -= block_size;
 54         ++ret_count;
 55 
 56         if(ret_count >= count)
 57         {
 58             count = ret_count;
 59             return ApplyRet{begin, end};
 60         }
 61     }
 62     return ApplyRet{begin, end};
 63 }
 64 
 65 MemPool::MemPool()
 66 {
 67     std::memset(_free, 0, sizeof(_free));
 68 }
 69 
 70 MemPool::~MemPool()
 71 {
 72 }
 73 
 74 void MemPool::Fill(int index, int count)
 75 {
 76     int size = __Sit(index);
 77     auto ret = _mem_cache.Apply(size, count);
 78 
 79     __Block*& p = _free[__Index(size)];
 80     ret._e->_next = p;
 81     p = ret._b;
 82 }
 83 
 84 void* MemPool::Alloc(int size)
 85 {
 86     if(size > BLOCK_MAX)
 87         return malloc(size);
 88 
 89     if(size <= 0)
 90         return nullptr;
 91         
 92 LABLE_ALLOC:
 93     const int index = __Index(size);
 94     __Block* block = _free[index];
 95     if(block == nullptr)
 96     {
 97         Fill(index, DEFAULT_EACH_BLOCK_STORE);
 98         goto LABLE_ALLOC;
 99     }
100 
101     block = _free[index];
102     _free[index] = block->_next;
103 
104     return block;
105 }
106 
107 void MemPool::Free(void* ptr, int size)
108 {
109     if(ptr == nullptr)
110         return;
111     
112     if(size > BLOCK_MAX)
113     {
114         free(ptr);
115         return;
116     }
117 
118     const int index = __Index(size);
119     __Block* block = (__Block*)(ptr);
120 
121     block->_next = _free[index];
122     _free[index] = block;
123 }
124 
125 MemPoolThreadSafe::MemPoolThreadSafe() noexcept
126 {
127 
128 }
129 
130 MemPoolThreadSafe::~MemPoolThreadSafe()
131 {
132     
133 }
134 
135 uint32_t MemPoolThreadSafe::GetThreadID()
136 {
137     static __thread uint32_t id = 0;
138     if(id != 0) return id;
139     id = std::hash<std::thread::id>()(std::this_thread::get_id());
140     return id;
141 }
142 
143 void* MemPoolThreadSafe::Alloc(int size)
144 {
145     uint32_t id = GetThreadID();
146     uint32_t index = id % __BUCKET_COUNT;
147     auto& list = _forThreadMemPool[index];
148 
149     auto* node = list.begin();
150     for (; node != nullptr; )
151     {
152         if(node->data()._id != id)
153         {
154             node = node->_next;
155             continue;
156         }
157         break;
158     }
159     
160     if(node == nullptr)
161     {
162         list.emplace(id, new MemPool());
163         node = list.begin();
164     }
165 
166     return node->data()._pool->Alloc(size);
167 }
168 
169 void MemPoolThreadSafe::Free(void* ptr, int size)
170 {
171     if(ptr == nullptr)
172         return;
173 
174     if(size <= 0)
175     {
176         free(ptr);
177         return;
178     }
179 
180     uint32_t id = GetThreadID();
181     uint32_t index = id % __BUCKET_COUNT;
182 
183     auto& list = _forThreadMemPool[index];
184     if(list.size() <= 0)
185         list.emplace(id, new MemPool());
186 
187     auto* node = list.begin();
188     for (; node != nullptr; )
189     {
190         if(node->data()._id != id)
191         {
192             node = node->_next;
193             continue;
194         }
195 
196         break;
197     }
198     
199     if(node == nullptr)
200         exit(3);
201 
202     return node->data()._pool->Free(ptr, size);
203 }
204 
205 };