Skip to content

Instantly share code, notes, and snippets.

@kvk1920
Created March 26, 2018 19:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kvk1920/02986d4bcef67c2199091cc2ac36522e to your computer and use it in GitHub Desktop.
Save kvk1920/02986d4bcef67c2199091cc2ac36522e to your computer and use it in GitHub Desktop.
Ломанный англо-саксонский + работает без дебаг-вывода в 1.5 раз дольше стандартного аллокатора. Ну и ещё могу сказать точно: аллокаторы копируются, в них можно хранить инфу. А ещё практика показала, что в качестве WORD лучше всего брать int или long.
#include <memory>
#include <iostream>
#include <fstream>
#include <list>
/*
* If function isn't safe, its name looks like a "__FunctionName"
*/
namespace VDebugTools {
template <typename Function>
inline void VRep(size_t n, Function f) {
/*
* It repeats function f() n times.
*/
for (size_t i(0); i < n; ++i)
f();
}
std::ofstream ferr("log.txt");//log file
class {
/*
* It's global class for debug output.
* VDbg(a, b, c) ~ ferr << a << b << c << std::endl
*/
private:
std::ostream& ostream_ = ferr; //You can fast change error stream to std::cerr by "= std::cerr"
size_t indent_size_ = 0;
bool on_ = false; //Set this car false if you want turn off debug output.
template <typename T>
void Print(const T& object) {
ostream_ << object;
}
template <typename T, typename ...Args>
void Print(const T& object, const Args& ...args) {
Print(object);
Print(args...);
}
public:
void IIndent(size_t n = 1) { indent_size_ += n; } //Increase size of indent
void DIndent(size_t n = 1) { indent_size_ -= n; } //...
template <typename ...Args>
void operator()(const Args& ...args) {
if (on_) {
VRep(indent_size_, [this](){ ostream_ << " "; });
Print(args...);
ostream_ << std::endl;
}
}
template <typename ...Args>
void In(const Args& ...args) {
operator ()(args...);
IIndent();
}
template <typename ...Args>
void Out(const Args& ...args) {
DIndent();
operator ()(args...);
}
} VDbg;
}
namespace VDebugToolsOff {
struct {
template <typename ...Args>
void operator ()(const Args ...) {}
template <typename ...Args>
void In(const Args ...) {}
template <typename ...Args>
void Out(const Args ...) {}
} VDbg;
}
/* <----------------------------------------------------------------------------> */
//using VDebugToolsOff::VDbg;
namespace MemoryTools {
typedef long WORD;
const size_t WORD_LENGTH = sizeof (WORD);
class MemoryBlock {
private:
size_t used_, size_;
WORD* buffer_;
public:
MemoryBlock(const MemoryBlock&) = delete; //Do you realy want copy this l a r g e block?
MemoryBlock(MemoryBlock&&) = delete;
MemoryBlock& operator =(const MemoryBlock&) = delete;
MemoryBlock& operator =(MemoryBlock&&) = delete;
explicit MemoryBlock(size_t n) :
used_(0), size_(n),
buffer_(reinterpret_cast<WORD*>(::operator new[](n * sizeof(WORD)))){
//VDbg("Created new MBlock ", this, " with ", n, " words");
} //O(malloc)
~MemoryBlock() {
//VDbg.In("Try to destruct MBlock ", this, " ...");
::operator delete[](buffer_);
//VDbg("Buffer cleared");
//VDbg.Out("MBlock deleted");
} //O(free)
size_t size() const { return size_; } //O(1)
bool CanAllocate(size_t bytes) { return (size_ - used_) * WORD_LENGTH >= bytes; } //O(1)
void* New(size_t bytes) { //O(1)
//VDbg.In("In MBlock ", this, " allocating ", bytes, " bytes...");
size_t number_of_words = (bytes % WORD_LENGTH == 0)
? bytes / WORD_LENGTH
: bytes / WORD_LENGTH + 1;
//VDbg("It's ", number_of_words, " words");
used_ += number_of_words;
void* result = reinterpret_cast<void*>(buffer_ + used_ - number_of_words);
//VDbg.Out("Memory Allocated");
return result;
}
};
template <typename T>
class DynamicArrayOfPointers {
/*
* It's a dynamic (only expansive) storage of pointers.
* You can put here ONLY a pointers to a SINGLE(no C-style array) object.
*/
private:
T** buffer_;
size_t used_, size_;
void Reallocate() { //O(malloc + used_)
//VDbg.In("Array ", this, " reallocating...");
//VDbg("Current used: ", used_);
//VDbg("Current size: ", size_);
T** new_buffer = reinterpret_cast<T**>(::operator new[](size_ * 2 * sizeof (T*)));
//VDbg("New buffer created");
std::copy(buffer_, buffer_ + used_, new_buffer); //We copy (not move) it because it just pointers
//VDbg("Data copied");
::operator delete[](buffer_);
//VDbg("Old buffer deleted");
buffer_ = new_buffer;
size_ *= 2;
//VDbg("Current size: ", size_);
//VDbg.Out("Array reallocated");
}
bool CanAllocate() { //O(1)
return used_ != size_;
}
void __DeleteData() {
//VDbg.In("Array's data of array ", this, " deleting...");
::operator delete[](buffer_);
buffer_ = nullptr;
//VDbg.Out("Array's data deleted");
}
void __ResetData() { //Clear data without deleting
//VDbg.In("Array's data of array ", this, " resetting...");
used_ = 0;
size_ = 1;
buffer_ = reinterpret_cast<T**>(::operator new[](sizeof(T*)));
//VDbg("Current used: ", used_);
//VDbg("Current size: ", size_);
//VDbg.Out("Data resetted");
}
public:
DynamicArrayOfPointers(const DynamicArrayOfPointers& other) : //O(other.used_ + malloc)
used_(other.used_), size_(other.size_) {
//VDbg.In("Creating array ", this, " by copy of ", &other, " ...");
buffer_ = reinterpret_cast<T**>(::operator new[](size_ * sizeof(T*)));
std::copy(other.buffer_, other.buffer_ + other.used_, buffer_);
//VDbg("Current used: ", used_);
//VDbg("Current size: ", size_);
//VDbg.Out("Array Created");
}
DynamicArrayOfPointers(DynamicArrayOfPointers&& other) : //O(1)
buffer_(other.buffer_), used_(other.used_), size_(other.size_) {
//VDbg.In("Creating array ", this, " by move of ", &other, " ...");
other.__ResetData();
//VDbg("Current used: ", used_);
//VDbg("Current size: ", size_);
//VDbg.Out("Array Created");
}
DynamicArrayOfPointers& operator =(DynamicArrayOfPointers&& other) {//O(1)
//VDbg.In("Moving pointers from ", &other, " to ", this, " ...");
__DeleteData();
used_ = other.used_;
size_ = other.size_;
buffer_ = other.buffer_;
other.__ResetData();
//VDbg("Current used: ", used_);
//VDbg("Current size: ", size_);
//VDbg.Out("Move done");
return *this;
}
DynamicArrayOfPointers& operator =(const DynamicArrayOfPointers& other) { //O(size...)
//VDbg.In("Copiing pointers from ", &other, " to ", this, " ...");
__DeleteData();
used_ = other.used_;
size_ = other.size_;
buffer_ = reinterpret_cast<T**>(::operator new[](size_ * sizeof(T*)));
std::copy(other.buffer_, other.buffer_ + other.used_, buffer_);
//VDbg("Current used: ", used_);
//VDbg("Current size: ", size_);
//VDbg.Out("Copy done");
return *this;
}
DynamicArrayOfPointers() {
//VDbg.In("Creating array ", this, " ...");
__ResetData();
//VDbg.Out("Array created");
}
~DynamicArrayOfPointers() {
//VDbg.In("Destroing array ", this, " ...");
__DeleteData();
//VDbg.Out("Array deleted");
}
size_t size() const { return used_; } //O(1)
T& operator[](size_t i) { return *buffer_[i]; } //O(1)
const T& operator[](size_t i) const { return *buffer_[i]; } //O(1)
T& back() { return *buffer_[used_ - 1]; } //O(1)
const T& back() const { return *buffer_[used_ - 1]; } //O(1)
template <typename ...Args> //~O(1)
void emplace_back(Args&& ...args) {
//VDbg.In("Creating element at array ", this, " ...");
//VDbg("Current used: ", used_);
//VDbg("Current size: ", size_);
if (!CanAllocate())
Reallocate();
//VDbg("Current used: ", used_);
//VDbg("Current size: ", size_);
buffer_[used_++] = new T(std::forward<Args>(args)...);
//VDbg.Out("Element created");
}
};
class MemoryStack {
private:
DynamicArrayOfPointers<MemoryBlock> buffer_;
public:
MemoryStack(const MemoryStack&) = delete;
MemoryStack& operator =(const MemoryStack&) = delete;
MemoryStack(MemoryStack&& other) : buffer_(std::move(other.buffer_)) {}
MemoryStack& operator =(MemoryStack&& other) {
//VDbg.In("Moving Stack from ", &other, " to ", this, " ...");
buffer_ = std::move(other.buffer_);
//VDbg.Out("Stack moved");
return *this;
}
MemoryStack() {
//VDbg.In("Creating new Stack ", this, " ...");
buffer_.emplace_back(256);
//VDbg.Out("Stack created");
}
~MemoryStack() {
//VDbg("Stack ", this, " deleted");
}
void* New(size_t bytes) {
//VDbg.In("Allocating ", bytes, " bytes at stack ", this, " ...");
for (size_t i(0); i < buffer_.size(); ++i)
if (buffer_[i].CanAllocate(bytes))
{
//VDbg.Out("Memory allocated");
return buffer_[i].New(bytes);
}
//VDbg("Free block hasn't found, creating new blocks...");
while (!buffer_.back().CanAllocate(bytes))
buffer_.emplace_back(buffer_.back().size() * 2);
void* result = buffer_.back().New(bytes);
//VDbg.Out("Memory alocated");
return result;
}
};
}
namespace SmartPointerTools {
template <typename T>
struct LinkCounter {
size_t counter;
T object;
template <typename ...Args>
LinkCounter(Args&& ...args) : counter(0), object(std::forward<Args>(args)...) {}
};
template <typename T>
void AddLink(LinkCounter<T>* data) { if (data) ++data->counter; }
template <typename T>
void RemoveLink(LinkCounter<T>* data) {
if (data == nullptr)
return;
if (--data->counter == 0)
delete data;
}
}
template <typename T>
class SmartPointer {
private:
SmartPointerTools::LinkCounter<T>* data_;
public:
explicit SmartPointer(SmartPointerTools::LinkCounter<T>* data) :
data_(data) {
SmartPointerTools::AddLink(data_);
}
SmartPointer() : data_(nullptr) {}
SmartPointer(const SmartPointer& other) :
data_(other.data_) {
SmartPointerTools::AddLink(data_);
}
SmartPointer(SmartPointer&& other) :
data_(other.data_) {
other.data_ = nullptr;
}
SmartPointer& operator =(const SmartPointer& other) {
SmartPointerTools::RemoveLink(data_);
data_ = other.data_;
SmartPointerTools::AddLink(data_);
}
SmartPointer& operator =(SmartPointer&& other) {
SmartPointerTools::RemoveLink(data_);
data_ = other.data_;
other.data_ = nullptr;
return *this;
}
~SmartPointer() { SmartPointerTools::RemoveLink(data_); }
T& operator *() { return data_->object; }
const T& operator *() const { return data_->object; }
T* operator ->() { return &data_->object; }
explicit operator bool()
{
return data_ != nullptr;
}
SmartPointer(std::nullptr_t) : data_(nullptr) {}
};
template <typename U, typename ...Args>
inline SmartPointer<U> Make(Args&& ...args) {
return SmartPointer<U>(new SmartPointerTools::LinkCounter<U>(std::forward<Args>(args)...));
}
template <typename T>
class StackSmartAllocator {
public:
SmartPointer<MemoryTools::MemoryStack> pool_;
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
template <typename U>
struct rebind { typedef StackSmartAllocator<U> other; };
explicit StackSmartAllocator(decltype(pool_) pool = nullptr) : pool_(pool) {
if (!pool_)
pool_ = Make<MemoryTools::MemoryStack>();
}
T* allocate(size_t n) {
return reinterpret_cast<T*>(pool_->New(n * sizeof(T)));
}
void deallocate(T*, size_t) {}
template <typename U>
StackSmartAllocator(const StackSmartAllocator<U>& other) : pool_(other.pool_) {
if (!pool_)
pool_ = Make<MemoryTools::MemoryStack>();
}
template <typename U, typename ...Args>
void construct(U *p, Args&& ...args) {
new(p) U(std::forward<Args>(args)...);
}
template <typename U>
void destroy(U *p) {
p->~U();
}
};
template <typename T>
class StackAllocator {
public:
MemoryTools::MemoryStack* pool_;
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
template <typename U>
struct rebind { typedef StackAllocator<U> other; };
explicit StackAllocator(decltype(pool_) pool = nullptr) : pool_(pool) {
if (!pool_)
pool_ = new MemoryTools::MemoryStack();
}
T* allocate(size_t n) {
return reinterpret_cast<T*>(pool_->New(n * sizeof(T)));
}
void deallocate(T*, size_t) {}
template <typename U>
StackAllocator(const StackAllocator<U>& other) : pool_(other.pool_) {
if (!pool_)
pool_ = Make<MemoryTools::MemoryStack>();
}
template <typename U, typename ...Args>
void construct(U *p, Args&& ...args) {
new(p) U(std::forward<Args>(args)...);
}
template <typename U>
void destroy(U *p) {
p->~U();
}
};
void f1()
{
double start = clock();
std::list<int, StackSmartAllocator<int>> list;
for (int i(0); i < 100000; ++i)
list.push_back(i);
list.clear();
std::cout << clock() - start << std::endl;
}
void f2()
{
double start = clock();
std::list<int> list;
for (int i(0); i < 100000; ++i)
list.push_back(i);
list.clear();
std::cout << clock() - start << std::endl;
}
void f3()
{
double start = clock();
std::list<int, StackAllocator<int>> list;
for (int i(0); i < 100000; ++i)
list.push_back(i);
list.clear();
std::cout << clock() - start << std::endl;
}
int main()
{
f1();
f2();
f3();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment