aboutsummaryrefslogtreecommitdiffstats
path: root/util/memory/pool.h
diff options
context:
space:
mode:
authorDevtools Arcadia <arcadia-devtools@yandex-team.ru>2022-02-07 18:08:42 +0300
committerDevtools Arcadia <arcadia-devtools@mous.vla.yp-c.yandex.net>2022-02-07 18:08:42 +0300
commit1110808a9d39d4b808aef724c861a2e1a38d2a69 (patch)
treee26c9fed0de5d9873cce7e00bc214573dc2195b7 /util/memory/pool.h
downloadydb-1110808a9d39d4b808aef724c861a2e1a38d2a69.tar.gz
intermediate changes
ref:cde9a383711a11544ce7e107a78147fb96cc4029
Diffstat (limited to 'util/memory/pool.h')
-rw-r--r--util/memory/pool.h431
1 files changed, 431 insertions, 0 deletions
diff --git a/util/memory/pool.h b/util/memory/pool.h
new file mode 100644
index 0000000000..13c8b6b9ed
--- /dev/null
+++ b/util/memory/pool.h
@@ -0,0 +1,431 @@
+#pragma once
+
+#include "alloc.h"
+
+#include <util/system/align.h>
+#include <util/system/yassert.h>
+#include <util/generic/bitops.h>
+#include <util/generic/utility.h>
+#include <util/generic/intrlist.h>
+#include <util/generic/strbuf.h>
+#include <util/generic/singleton.h>
+
+#include <new>
+#include <string>
+#include <utility>
+
+/**
+ * Memory pool implements a memory allocation scheme that is very fast, but
+ * limited in its usage.
+ *
+ * A common use case is when you want to allocate a bunch of small objects, and
+ * then release them all at some point of your program. Using memory pool, you
+ * can just drop them off into oblivion without calling any destructors,
+ * provided that all associated memory was allocated on the pool.
+ */
+class TMemoryPool {
+private:
+ using TBlock = IAllocator::TBlock;
+
+ class TChunk: public TIntrusiveListItem<TChunk> {
+ public:
+ inline TChunk(size_t len = 0) noexcept
+ : Cur_((char*)(this + 1))
+ , Left_(len)
+ {
+ Y_ASSERT((((size_t)Cur_) % PLATFORM_DATA_ALIGN) == 0);
+ }
+
+ inline void* Allocate(size_t len) noexcept {
+ if (Left_ >= len) {
+ char* ret = Cur_;
+
+ Cur_ += len;
+ Left_ -= len;
+
+ return ret;
+ }
+
+ return nullptr;
+ }
+
+ inline void* Allocate(size_t len, size_t align) noexcept {
+ size_t pad = AlignUp(Cur_, align) - Cur_;
+
+ void* ret = Allocate(pad + len);
+ if (ret) {
+ return static_cast<char*>(ret) + pad;
+ }
+
+ return nullptr;
+ }
+
+ inline size_t BlockLength() const noexcept {
+ return (Cur_ + Left_) - (char*)this;
+ }
+
+ inline size_t Used() const noexcept {
+ return Cur_ - (const char*)this;
+ }
+
+ inline size_t Left() const noexcept {
+ return Left_;
+ }
+
+ inline const char* Data() const noexcept {
+ return (const char*)(this + 1);
+ }
+
+ inline char* Data() noexcept {
+ return (char*)(this + 1);
+ }
+
+ inline size_t DataSize() const noexcept {
+ return Cur_ - Data();
+ }
+
+ inline void ResetChunk() noexcept {
+ size_t total = DataSize() + Left();
+ Cur_ = Data();
+ Left_ = total;
+ }
+
+ private:
+ char* Cur_;
+ size_t Left_;
+ };
+
+ using TChunkList = TIntrusiveList<TChunk>;
+
+public:
+ class IGrowPolicy {
+ public:
+ virtual ~IGrowPolicy() = default;
+
+ virtual size_t Next(size_t prev) const noexcept = 0;
+ };
+
+ class TLinearGrow: public IGrowPolicy {
+ public:
+ size_t Next(size_t prev) const noexcept override {
+ return prev;
+ }
+
+ static IGrowPolicy* Instance() noexcept;
+ };
+
+ class TExpGrow: public IGrowPolicy {
+ public:
+ size_t Next(size_t prev) const noexcept override {
+ return prev * 2;
+ }
+
+ static IGrowPolicy* Instance() noexcept;
+ };
+
+ struct TOptions {
+ bool RoundUpToNextPowerOfTwo;
+ TOptions()
+ : RoundUpToNextPowerOfTwo(true)
+ {
+ }
+ };
+
+ inline TMemoryPool(size_t initial, IGrowPolicy* grow = TExpGrow::Instance(), IAllocator* alloc = TDefaultAllocator::Instance(), const TOptions& options = TOptions())
+ : Current_(&Empty_)
+ , BlockSize_(initial)
+ , GrowPolicy_(grow)
+ , Alloc_(alloc)
+ , Options_(options)
+ , Origin_(initial)
+ , MemoryAllocatedBeforeCurrent_(0)
+ , MemoryWasteBeforeCurrent_(0)
+ {
+ }
+
+ inline ~TMemoryPool() {
+ Clear();
+ }
+
+ inline void* Allocate(size_t len) {
+ return RawAllocate(AlignUp<size_t>(len, PLATFORM_DATA_ALIGN));
+ }
+
+ inline void* Allocate(size_t len, size_t align) {
+ return RawAllocate(AlignUp<size_t>(len, PLATFORM_DATA_ALIGN), align);
+ }
+
+ template <typename T>
+ inline T* Allocate() {
+ return (T*)this->Allocate(sizeof(T), alignof(T));
+ }
+
+ template <typename T>
+ inline T* Allocate(size_t align) {
+ return (T*)this->Allocate(sizeof(T), Max(align, alignof(T)));
+ }
+
+ template <typename T>
+ inline T* AllocateArray(size_t count) {
+ return (T*)this->Allocate(sizeof(T) * count, alignof(T));
+ }
+
+ template <typename T>
+ inline T* AllocateArray(size_t count, size_t align) {
+ return (T*)this->Allocate(sizeof(T) * count, Max(align, alignof(T)));
+ }
+
+ template <typename T>
+ inline T* AllocateZeroArray(size_t count) {
+ T* ptr = AllocateArray<T>(count);
+ memset(ptr, 0, count * sizeof(T));
+ return ptr;
+ }
+
+ template <typename T>
+ inline T* AllocateZeroArray(size_t count, size_t align) {
+ T* ptr = AllocateArray<T>(count, align);
+ memset(ptr, 0, count * sizeof(T));
+ return ptr;
+ }
+
+ template <typename T, typename... Args>
+ inline T* New(Args&&... args) {
+ return new (Allocate<T>()) T(std::forward<Args>(args)...);
+ }
+
+ template <typename T>
+ inline T* NewArray(size_t count) {
+ T* arr = (T*)AllocateArray<T>(count);
+
+ for (T *ptr = arr, *end = arr + count; ptr != end; ++ptr) {
+ new (ptr) T;
+ }
+
+ return arr;
+ }
+
+ template <typename TChar>
+ inline TChar* Append(const TChar* str) {
+ return Append(str, std::char_traits<TChar>::length(str) + 1); // include terminating zero byte
+ }
+
+ template <typename TChar>
+ inline TChar* Append(const TChar* str, size_t len) {
+ TChar* ret = AllocateArray<TChar>(len);
+
+ std::char_traits<TChar>::copy(ret, str, len);
+ return ret;
+ }
+
+ template <typename TChar>
+ inline TBasicStringBuf<TChar> AppendString(const TBasicStringBuf<TChar>& buf) {
+ return TBasicStringBuf<TChar>(Append(buf.data(), buf.size()), buf.size());
+ }
+
+ template <typename TChar>
+ inline TBasicStringBuf<TChar> AppendCString(const TBasicStringBuf<TChar>& buf) {
+ TChar* ret = static_cast<TChar*>(Allocate((buf.size() + 1) * sizeof(TChar)));
+
+ std::char_traits<TChar>::copy(ret, buf.data(), buf.size());
+ *(ret + buf.size()) = 0;
+ return TBasicStringBuf<TChar>(ret, buf.size());
+ }
+
+ inline size_t Available() const noexcept {
+ return Current_->Left();
+ }
+
+ inline void Clear() noexcept {
+ DoClear(false);
+ }
+
+ inline void ClearKeepFirstChunk() noexcept {
+ DoClear(true);
+ }
+
+ inline size_t MemoryAllocated() const noexcept {
+ return MemoryAllocatedBeforeCurrent_ + (Current_ != &Empty_ ? Current_->Used() : 0);
+ }
+
+ inline size_t MemoryWaste() const noexcept {
+ return MemoryWasteBeforeCurrent_ + (Current_ != &Empty_ ? Current_->Left() : 0);
+ }
+
+ template <class TOp>
+ inline void Traverse(TOp& op) const noexcept {
+ for (TChunkList::TConstIterator i = Chunks_.Begin(); i != Chunks_.End(); ++i) {
+ op(i->Data(), i->DataSize());
+ }
+ }
+
+ inline IAllocator* RealAllocator() const noexcept {
+ return Alloc_;
+ }
+
+protected:
+ inline void* RawAllocate(size_t len) {
+ void* ret = Current_->Allocate(len);
+
+ if (ret) {
+ return ret;
+ }
+
+ AddChunk(len);
+
+ return Current_->Allocate(len);
+ }
+
+ inline void* RawAllocate(size_t len, size_t align) {
+ Y_ASSERT(align > 0);
+ void* ret = Current_->Allocate(len, align);
+
+ if (ret) {
+ return ret;
+ }
+
+ AddChunk(len + align - 1);
+
+ return Current_->Allocate(len, align);
+ }
+
+private:
+ void AddChunk(size_t hint);
+ void DoClear(bool keepfirst) noexcept;
+
+private:
+ TChunk Empty_;
+ TChunk* Current_;
+ size_t BlockSize_;
+ IGrowPolicy* GrowPolicy_;
+ IAllocator* Alloc_;
+ TOptions Options_;
+ TChunkList Chunks_;
+ const size_t Origin_;
+ size_t MemoryAllocatedBeforeCurrent_;
+ size_t MemoryWasteBeforeCurrent_;
+};
+
+template <typename TPool>
+struct TPoolableBase {
+ inline void* operator new(size_t bytes, TPool& pool) {
+ return pool.Allocate(bytes);
+ }
+
+ inline void* operator new(size_t bytes, std::align_val_t align, TPool& pool) {
+ return pool.Allocate(bytes, (size_t)align);
+ }
+
+ inline void operator delete(void*, size_t) noexcept {
+ }
+
+ inline void operator delete(void*, TPool&) noexcept {
+ }
+
+private:
+ inline void* operator new(size_t); // disallow default allocation
+};
+
+struct TPoolable: public TPoolableBase<TMemoryPool> {
+};
+
+class TMemoryPoolAllocator: public IAllocator {
+public:
+ inline TMemoryPoolAllocator(TMemoryPool* pool)
+ : Pool_(pool)
+ {
+ }
+
+ TBlock Allocate(size_t len) override {
+ TBlock ret = {Pool_->Allocate(len), len};
+
+ return ret;
+ }
+
+ void Release(const TBlock& block) override {
+ (void)block;
+ }
+
+private:
+ TMemoryPool* Pool_;
+};
+
+template <class T, class TPool>
+class TPoolAllocBase {
+public:
+ using pointer = T*;
+ using const_pointer = const T*;
+ using reference = T&;
+ using const_reference = const T&;
+ using size_type = size_t;
+ using difference_type = ptrdiff_t;
+ using value_type = T;
+
+ inline TPoolAllocBase(TPool* pool)
+ : Pool_(pool)
+ {
+ }
+
+ template <typename TOther>
+ inline TPoolAllocBase(const TPoolAllocBase<TOther, TPool>& o)
+ : Pool_(o.GetPool())
+ {
+ }
+
+ inline T* allocate(size_t n) {
+ return (T*)Pool_->Allocate(n * sizeof(T), alignof(T));
+ }
+
+ inline void deallocate(pointer /*p*/, size_t /*n*/) {
+ }
+
+ template <class T1>
+ struct rebind {
+ using other = TPoolAllocBase<T1, TPool>;
+ };
+
+ inline size_type max_size() const noexcept {
+ return size_type(-1) / sizeof(T);
+ }
+
+ template <typename... Args>
+ inline void construct(pointer p, Args&&... args) {
+ new (p) T(std::forward<Args>(args)...);
+ }
+
+ inline void destroy(pointer p) noexcept {
+ (void)p; /* Make MSVC happy. */
+ p->~T();
+ }
+
+ inline TPool* GetPool() const {
+ return Pool_;
+ }
+
+ inline friend bool operator==(const TPoolAllocBase& l, const TPoolAllocBase& r) {
+ return l.Pool_ == r.Pool_;
+ }
+
+ inline friend bool operator!=(const TPoolAllocBase& l, const TPoolAllocBase& r) {
+ return !(l == r);
+ }
+
+private:
+ TPool* Pool_;
+};
+
+template <class T>
+using TPoolAlloc = TPoolAllocBase<T, TMemoryPool>;
+
+// Any type since it is supposed to be rebound anyway.
+using TPoolAllocator = TPoolAlloc<int>;
+
+template <class T>
+inline bool operator==(const TPoolAlloc<T>&, const TPoolAlloc<T>&) noexcept {
+ return true;
+}
+
+template <class T>
+inline bool operator!=(const TPoolAlloc<T>&, const TPoolAlloc<T>&) noexcept {
+ return false;
+}