ただの参照カウンタ方式のメモリアロケータ

結局マーク&スイープを実装する予定だったのがただの参照カウンタ方式のGCとなってしまった。一応ソースを載っけておく。

固定方式と変動方式がある。固定方式では断片化が発生せず、更にサイズの情報がなかったりフリープールが一定なので無駄な処理がないなど高速に動作する点で優れている。一方変動方式は型のサイズに因らず同じフリープールから確保できるため、メモリの節約になる。いずれにしても頻繁にfreeすることはないので、そのような条件下ではより高速に動くはず。

#include <iostream>
#include <memory>

#define ALIGNMENT_SIZE GET_ALIGNMENT_SIZE<long long>::value

namespace {
	template <class T>
	struct DUMMY { char a; T b; };

	template <class T>
	struct GET_ALIGNMENT_SIZE {
		static const int value = sizeof(DUMMY<T>) - sizeof(T);
	};

	enum MARK : unsigned short {
		FREE = 0x8000,
		UNUSED = 0x4000,
		LOCKED = 0x2000,
		MOVED = 0x1000,
		LAST = 0x0800,
	};

	struct Information {
		unsigned short f_mark;
		unsigned short count;

		inline void setFlag(unsigned short flag) {
			f_mark |= flag;
		}
		inline void clearFlag(unsigned short flag) {
			f_mark &= ~flag;
		}
		inline bool isFlag(unsigned short flag) const {
			return f_mark & flag ? true : false;
		}
	};
}

template <class T>
class FixedMemoryManager;
class FlexibleMemoryManager;

template <class T>
class f_ptr {
	friend FixedMemoryManager<T>;
	friend FlexibleMemoryManager;

public:
	f_ptr() : data(nullptr) { }
	f_ptr(const f_ptr& it) {
		data = it.data;
		information = it.information;

		if(data != nullptr) {
			++information->count;
		}
	}
	f_ptr& operator=(const f_ptr& it) {
		if(data != nullptr) {
			--information->count;

			if(information->count < 1) {
				information->setFlag(MARK::UNUSED);
			}
		}

		data = it.data;
		information = it.information;

		return *this;
	}
	f_ptr(f_ptr&& it) {
		data = it.data;
		information = it.information;
		it.data = nullptr;
	}
	f_ptr& operator=(f_ptr&& it) {
		if(data != nullptr) {
			--information->count;

			if(information->count < 1) {
				information->setFlag(MARK::UNUSED);
			}
		}

		data = it.data;
		information = it.information;
		it.data = nullptr;

		return *this;
	}
	~f_ptr() {
		if(data != nullptr) {
			--information->count;

			if(information->count < 1) {
				information->setFlag(MARK::UNUSED);
			}
		}
	}
	T& operator*() {
		return *data;
	}
	T* operator->() {
		return data;
	}
	void lock() {
		information->setFlag(MARK::LOCKED);
	}
	void unlock() {
		information->clearFlag(MARK::LOCKED);
	}
private:
	f_ptr(T* data, Information* information) :
		data(data), information(information) { }

	T* data;
	Information* information;
};

/*
	固定型メモリマネージャ
*/
namespace {
	template <class T>
	struct MemoryCell {
		MemoryCell() { }

		T data;
		Information information;
		MemoryCell* free_next;
	};

	template <class T>
	struct MemoryBlock {
		MemoryCell<T>* data;
		MemoryBlock* next;
	};
}

template <class T>
class FixedMemoryManager {
public:
	FixedMemoryManager(size_t unit_size = 32) :
		unit_size(unit_size), free_pool(nullptr) {

	}
	~FixedMemoryManager() {
		MemoryBlock<T>* at = first;
		MemoryBlock<T>* next;

		while(at != nullptr) {
			delete[] (char*)at->data;
			next = at->next;
			delete at;
			at = next;
		}
	}

	template <class ...Args>
	f_ptr<T> make(Args ...args) {
		MemoryCell<T>* memory_cell;
		
		// フリープールになければ確保
		if(free_pool == nullptr) {
			// 一回清掃を行う
			sweep();

			// それでもだめなら
			if(free_pool == nullptr) {
				allocateMemoryBlock();
			}
		}

		memory_cell = free_pool;
		free_pool = free_pool->free_next;

		// 初期化
		memory_cell->information.count = 1;
		memory_cell->information.f_mark = 0;

		return f_ptr<T>(new(&memory_cell->data) T(args...), &memory_cell->information);
	}

	void dump() {
		MemoryBlock<T>* at = first;

		while(at != nullptr) {
			for(int offset = 0, rest = sizeof(MemoryCell<T>) * unit_size; rest > 0;) {
				
				const int limited_rest = rest > 16 ? 16 : rest;
				for(int i = 0; i < limited_rest; ++i) {
					printf("%02x ", *((unsigned char*)at->data + offset));
					++offset;
				}

				rest -= 16;

				std::cout << std::endl;
			}
			std::cout << std::endl;

			at = at->next;
		}
	}

private:
	void allocateMemoryBlock() {
		std::unique_ptr<MemoryBlock<T>> _new_block(new MemoryBlock<T>);
		_new_block->data = (MemoryCell<T>*)(new char[sizeof(MemoryCell<T>) * unit_size]);
		_new_block->next = nullptr;

		// newの成功につき戻す
		MemoryBlock<T>* new_block = _new_block.release();

		if(first == nullptr) {
			first = new_block;
		}
		else {
			last->next = new_block;
		}
		last = new_block;

		for(size_t i = 0; i < unit_size; ++i) {
			MemoryCell<T>* cell = &new_block->data[i];

			// 次を前のfree_poolに設定
			cell->free_next = free_pool;
			// 今をfree_poolに設定
			free_pool = cell;
		}
	}

	void sweep() {
		MemoryBlock<T>* at = first;

		while(at != nullptr) {
			// UNUSEDフラグが立っていたらフリープールに繋ぐ
			for(size_t i = 0; i < unit_size; ++i) {
				MemoryCell<T>* cell = &at->data[i];

				if(cell->information.isFlag(MARK::UNUSED)) {
					cell->free_next = free_pool;
					free_pool = cell;

					cell->data.~T();
					cell->information.clearFlag(MARK::UNUSED);
				}
			}

			at = at->next;
		}
	}

	MemoryBlock<T>* first;
	MemoryBlock<T>* last;
	MemoryCell<T>* free_pool;
	size_t unit_size;
};

/*
	可変メモリマネージャ
*/
namespace {
	template <class T>
	struct MemoryCell_F {
		size_t size;
		Information information;
		void* next;
		T data;
	}; 
	
	struct MemoryBlock_F {
		char* data;
		MemoryBlock_F* next;
		size_t block_size;
	};
}
class FlexibleMemoryManager {
public:
	FlexibleMemoryManager(size_t unit_size = 32) :
		unit_size((unit_size / ALIGNMENT_SIZE + 1) * ALIGNMENT_SIZE),
		free_pool(nullptr) {

	}
	~FlexibleMemoryManager() {
		MemoryBlock_F* at = first;
		MemoryBlock_F* next;

		while(at != nullptr) {
			delete[] at->data;
			next = at->next;
			delete at;
			at = next;
		}
	}

	template <class T, class ...Args>
	f_ptr<T> make(Args ...args) {
		MemoryCell_F<T>* memory_cell;
		size_t size = sizeof(MemoryCell_F<T>);

		// フリープールになければ確保
		if(free_pool == nullptr) {
			sweep();
			
			// それでもだめならメモリブロックの確保
			if(free_pool == nullptr) {
				allocateMemoryBlock(size);
			}
		}

		memory_cell = (MemoryCell_F<T>*)free_pool;

		// 以下memory_cellは一端フリープールから外してあとであまりを付け加える

		// 容量が足りていればフリープールの位置を一端初期化
		if(memory_cell->size >= size) {
			free_pool = nullptr;
		}
		// 空き容量が足りなければ次を探す
		else {
			// 一応清掃しておく
			sweep(); // free_poolの変更
			memory_cell = (MemoryCell_F<T>*)free_pool;

			MemoryCell_F<T>* previus_memory_cell = memory_cell;
			memory_cell = (MemoryCell_F<T>*)memory_cell->next;

			while(memory_cell != nullptr) {
				// あった
				if(memory_cell->size >= size) {
					// 前のnextは今のnext
					previus_memory_cell->next = memory_cell->next;
					break;
				}

				// 次のフリーリスト
				previus_memory_cell = memory_cell;
				memory_cell = (MemoryCell_F<T>*)memory_cell->next;
			};

			// 最終的に容量が足りなければ新たに確保
			if(memory_cell == nullptr) {
				memory_cell = (MemoryCell_F<T>*)allocateMemoryBlock(sizeof(MemoryCell_F<T>))->data;
			}
		}

		// 初期化
		size_t before_size = memory_cell->size;

		memory_cell = new(memory_cell) MemoryCell_F<T>;
		
		memory_cell->size = size;
		memory_cell->information.count = 1;
		memory_cell->information.f_mark = 0;
		memory_cell->next = nullptr;

		// 残り領域の計算
		// 残りも使えそうな領域だったら
		size_t rest_size = before_size - size;
		MemoryCell_F<void*>* new_free_cell = (MemoryCell_F<void*>*)((char*)memory_cell + size);

		if(rest_size >= sizeof(MemoryCell_F<void*>)) {
			new_free_cell->size = rest_size;
			new_free_cell->information.count = 0;
			new_free_cell->information.f_mark = 0;

			new_free_cell->next = free_pool; // 付け替え
			free_pool = new_free_cell;
		}
		// 数バイトと残っていたら無効領域として使用しないこととする
		else if(rest_size >= sizeof(size_t)) {
			memory_cell->size = before_size;
		}

		return f_ptr<T>(new(&memory_cell->data) T(args...), &memory_cell->information);
	}

	void dump() {
		MemoryBlock_F* at = first;

		void* memory_cell = free_pool;

		while(memory_cell != nullptr) {
			std::cout << memory_cell << std::endl;
			memory_cell = ((MemoryCell_F<void*>*)memory_cell)->next;
		};

		while(at != nullptr) {
			for(int offset = 0, rest = at->block_size; rest > 0;) {
				const int limited_rest = rest > 16 ? 16 : rest;
				std::cout << "at " << (void*)((unsigned char*)at->data + offset) << std::endl;
				for(int i = 0; i < limited_rest; ++i) {
					printf("%02x ", *((unsigned char*)at->data + offset));
					++offset;
				}

				rest -= 16;

				std::cout << std::endl;
			}
			std::cout << std::endl;

			at = at->next;
		}
	}
	
private:
	MemoryBlock_F* allocateMemoryBlock(size_t allocate_size) {
		std::unique_ptr<MemoryBlock_F> _new_block(new MemoryBlock_F);

		if(allocate_size < unit_size) {
			allocate_size = unit_size;
		}

		_new_block->data = new char[allocate_size];
		_new_block->block_size = allocate_size;
		_new_block->next = nullptr;

		// newの成功につき戻す
		MemoryBlock_F* new_block = _new_block.release();

		if(first == nullptr) {
			first = new_block;
		}
		else {
			last->next = new_block;
		}

		last = new_block;

		// 確保した先頭をfree_poolに設定
		MemoryCell_F<void*>* cell = (MemoryCell_F<void*>*)new_block->data;
		cell->next = free_pool;
		// 今をfree_poolに設定
		free_pool = cell;
		// 空き容量を設定(管理領域含む)
		cell->size = allocate_size;

		return new_block;
	}

	void sweep() {
		MemoryBlock_F* at = first;
		MemoryCell_F<void*>* cell;

		while(at != nullptr) {
			// 先頭から順次サイズを足してアクセスしていく
			cell = (MemoryCell_F<void*>*)at->data;
			
			while(cell != nullptr) {
				// もしも解放して良ければ
				if(cell->information.isFlag(MARK::UNUSED)) {
					// フリーリストにつなぐ
					cell->next = free_pool;
					free_pool = cell;
				}
				if(cell->information.isFlag(MARK::LAST)) {
					break;
				}
				cell = (MemoryCell_F<void*>*)((char*)cell + cell->size);
			}

			at = at->next;
		}
	}

	// 断片化防止のため新しい領域にコピー
	void move(MemoryCell_F<void*>* it) {

	}

	MemoryBlock_F* first;
	MemoryBlock_F* last;
	void* free_pool;
	size_t unit_size;
};

#undef ALIGNMENT_SIZE