<commit_before>//
//  File: DKFixedSizeAllocator.h
//  Author: <NAME> (<EMAIL>)
//
//  Copyright (c) 2015 <NAME>. All rights reserved.
//

#pragma once
#include "../DKinclude.h"
#include "DKTypes.h"
#include "DKTypeTraits.h"
#include "DKAllocatorChain.h"
#include "DKAllocator.h"
#include "DKMemory.h"
#include "DKSpinLock.h"
#include "DKCriticalSection.h"

////////////////////////////////////////////////////////////////////////////////
// DKFixedSizeAllocator
// an allocator which can allocate memory of fixed length.
// it is useful to template collection classes like DKMap, DKSet.
////////////////////////////////////////////////////////////////////////////////

namespace DKFoundation
{
	template <
		size_t UnitSize,			// allocation size (fixed size)
		size_t MaxUnits = 32,		// max units per chunk
		typename Lock = DKSpinLock,
		typename BaseAllocator = DKMemoryDefaultAllocator // for alloc chunks.
	>
	class DKFixedSizeAllocator : public DKAllocatorChain
	{
		static_assert(UnitSize > 0, "Size must be greater than zero.");
		static_assert(DKNumMatches<MaxUnits, 8, 16, 32, 64>() == 1,
					  "MaxUnits must be one of 8,16,32,64.");

		// C++11 does not allow 'explicit spealization',
		// to compile properly, we need specify one or more types which is not
		// used but required. (type 'U' in below template struct)
		template <int, typename U=void> struct _BitMaskType;
		template <typename U> struct _BitMaskType< 8, U> { using Type = unsigned char; };
		template <typename U> struct _BitMaskType<16, U> { using Type = unsigned short; };
		template <typename U> struct _BitMaskType<32, U> { using Type = unsigned int; };
		template <typename U> struct _BitMaskType<64, U> { using Type = unsigned long long; };

		using BitMaskType = typename _BitMaskType<MaxUnits>::Type;
		static_assert(sizeof(BitMaskType) * 8 == MaxUnits, "BitMaskType is invalid.");
		static const BitMaskType fullOccupied = (BitMaskType)-1;

		enum {maxUnitsPerChunk = MaxUnits};

		using Unit = unsigned char[UnitSize];
		struct Chunk
		{
			Unit units[maxUnitsPerChunk];
			BitMaskType occupied;
			Chunk* next; /* linked-list */
		};
		static_assert(DKTypeTraits<Chunk>::IsPod(), "Invalid chunk type");

		Chunk* firstChunk;
		size_t maxAllocated;
		size_t numAllocated;
		size_t maxChunks;
		size_t numChunks;

		using CriticalSection = DKCriticalSection<Lock>;
		Lock lock;

	public:
		enum { FixedLength = UnitSize };

		static DKFixedSizeAllocator& Instance(void)
		{
			static StaticInitializer init; // extend allocator life cycle.
			static DKFixedSizeAllocator* instance = new DKFixedSizeAllocator();
			return *instance;
		}

		// DKAllocator interface. Useful to DKObject<T> allocation.
		static DKAllocator& AllocatorInstance(void)
		{
			struct AllocatorWrapper : public DKAllocator
			{
				void* Alloc(size_t s) override					{ return Instance().Alloc(s); }
				void Dealloc(void* p) override					{ return Instance().Dealloc(p); }
				DKMemoryLocation Location(void) const override	{ return (DKMemoryLocation)BaseAllocator::Location; }
			};
			static StaticInitializer init; // extend allocator life cycle.
			static AllocatorWrapper* instance = new AllocatorWrapper();
			return *instance;
		}

		void* Alloc(size_t s)
		{
			DKASSERT_STD_DEBUG(s == FixedLength);
			CriticalSection guard(lock);
			numAllocated++;
			if (maxAllocated < numAllocated)
				maxAllocated = numAllocated;

			// find unoccupied unit from each chunks
			for (Chunk* ch = firstChunk; ch; ch = ch->next)
			{
				if (ch->occupied != fullOccupied)
				{
					// chunk has one or more unoccupied units.
					for (int i = 0; i < maxUnitsPerChunk; ++i)
					{
						unsigned int occupied = (ch->occupied >> i) & 1;
						if (!occupied)
						{
							ch->occupied |= (1 << i);
							return ch->units[i];
						}
					}
				}
			}
			// no space, create new chunk.
			numChunks++;
			Chunk* ch = (Chunk*)BaseAllocator::Alloc(sizeof(Chunk));
			ch->occupied = 1;
			ch->next = NULL;
			// add chunk to linked list
			if (firstChunk == NULL)
				firstChunk = ch;
			else
			{
				Chunk* last = firstChunk;
				while (last->next)
					last = last->next;
				last->next = ch;
			}
			return ch->units[0];
		}

		void Dealloc(void* ptr)
		{
			uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
			CriticalSection guard(lock);
			for (Chunk* ch = firstChunk; ch; ch = ch->next)
			{
				uintptr_t rangeBegin = reinterpret_cast<uintptr_t>(ch->units[0]);
				uintptr_t rangeEnd = reinterpret_cast<uintptr_t>(ch->units[maxUnitsPerChunk-1]);
				if (addr >= rangeBegin && addr <= rangeEnd)
				{
					unsigned int index = (unsigned int)((addr - rangeBegin) / sizeof(Unit));
					ch->occupied ^= (1 << index);
					numAllocated--;
					return;
				}
			}
			// error: ptr was not allocated from this allocator!
			DKASSERT_STD_DESC_DEBUG(false, "Given address was not allocated from this allocator!");
		}

		void Purge(void)	// delete unoccupied chunks
		{
			CriticalSection guard(lock);
			for (Chunk* ch = firstChunk; ch; ch = ch->next)
			{
				if (ch->next && ch->next->occupied == 0)
				{
					Chunk* freeChunk = ch->next;
					ch->next = freeChunk->next;
					BaseAllocator::Free(freeChunk);
					numChunks--;
				}
			}
			if (firstChunk && firstChunk->occupied == 0)
			{
				Chunk* freeChunk = firstChunk;
				firstChunk = freeChunk->next;
				BaseAllocator::Free(freeChunk);
				numChunks--;
			}
		}

		virtual ~DKFixedSizeAllocator(void)
		{
			DKASSERT_STD_DEBUG(numAllocated == 0);
			Chunk* nextChunk = firstChunk;<commit_msg>no message<commit_after>//
//  File: DKFixedSizeAllocator.h
//  Author: <NAME> (<EMAIL>)
//
//  Copyright (c) 2015 <NAME>. All rights reserved.
//

#pragma once
#include "../DKinclude.h"
#include "DKTypes.h"
#include "DKTypeTraits.h"
#include "DKAllocatorChain.h"
#include "DKAllocator.h"
#include "DKMemory.h"
#include "DKSpinLock.h"
#include "DKCriticalSection.h"

////////////////////////////////////////////////////////////////////////////////
// DKFixedSizeAllocator
// an allocator which can allocate memory of fixed length.
// it is useful to template collection classes like DKMap, DKSet.
////////////////////////////////////////////////////////////////////////////////

namespace DKFoundation
{
	template <
		size_t UnitSize,			// allocation size (fixed size)
		size_t MaxUnits = 32,		// max units per chunk
		typename Lock = DKSpinLock,
		typename BaseAllocator = DKMemoryDefaultAllocator // for alloc chunks.
	>
	class DKFixedSizeAllocator : public DKAllocatorChain
	{
		static_assert(UnitSize > 0, "Size must be greater than zero.");
		static_assert(DKNumMatches<MaxUnits, 8, 16, 32, 64>() == 1,
					  "MaxUnits must be one of 8,16,32,64.");

		// C++11 does not allow 'explicit spealization',
		// to compile properly, we need specify one or more types which is not
		// used but required. (type 'U' in below template struct)
		template <int, typename U=void> struct _BitMaskType;
		template <typename U> struct _BitMaskType< 8, U> { using Type = unsigned char; };
		template <typename U> struct _BitMaskType<16, U> { using Type = unsigned short; };
		template <typename U> struct _BitMaskType<32, U> { using Type = unsigned int; };
		template <typename U> struct _BitMaskType<64, U> { using Type = unsigned long long; };

		using BitMaskType = typename _BitMaskType<MaxUnits>::Type;
		static_assert(sizeof(BitMaskType) * 8 == MaxUnits, "BitMaskType is invalid.");
		static const BitMaskType fullOccupied = (BitMaskType)-1;

		enum {MaxUnitsPerChunk = MaxUnits};

		using Unit = unsigned char[UnitSize];
		struct Chunk
		{
			Unit units[MaxUnitsPerChunk];
			BitMaskType occupied;
			Chunk* next; /* linked-list */
		};
		static_assert(DKTypeTraits<Chunk>::IsPod(), "Invalid chunk type");

		Chunk* firstChunk;
		size_t maxAllocated;
		size_t numAllocated;
		size_t maxChunks;
		size_t numChunks;

		using CriticalSection = DKCriticalSection<Lock>;
		Lock lock;

	public:
		enum { FixedLength = UnitSize };

		static DKFixedSizeAllocator& Instance(void)
		{
			static StaticInitializer init; // extend allocator life cycle.
			static DKFixedSizeAllocator* instance = new DKFixedSizeAllocator();
			return *instance;
		}

		// DKAllocator interface. Useful to DKObject<T> allocation.
		static DKAllocator& AllocatorInstance(void)
		{
			struct AllocatorWrapper : public DKAllocator
			{
				void* Alloc(size_t s) override					{ return Instance().Alloc(s); }
				void Dealloc(void* p) override					{ return Instance().Dealloc(p); }
				DKMemoryLocation Location(void) const override	{ return (DKMemoryLocation)BaseAllocator::Location; }
			};
			static StaticInitializer init; // extend allocator life cycle.
			static AllocatorWrapper* instance = new AllocatorWrapper();
			return *instance;
		}

		void* Alloc(size_t s)
		{
			DKASSERT_STD_DEBUG(s <= FixedLength);
			CriticalSection guard(lock);
			numAllocated++;
			if (maxAllocated < numAllocated)
				maxAllocated = numAllocated;

			// find unoccupied unit from each chunks
			for (Chunk* ch = firstChunk; ch; ch = ch->next)
			{
				if (ch->occupied != fullOccupied)
				{
					// chunk has one or more unoccupied units.
					for (int i = 0; i < MaxUnitsPerChunk; ++i)
					{
						unsigned int occupied = (ch->occupied >> i) & 1;
						if (!occupied)
						{
							ch->occupied |= (1 << i);
							return ch->units[i];
						}
					}
				}
			}
			// no space, create new chunk.
			numChunks++;
			Chunk* ch = (Chunk*)BaseAllocator::Alloc(sizeof(Chunk));
			ch->occupied = 1;
			ch->next = NULL;
			// add chunk to linked list
			if (firstChunk == NULL)
				firstChunk = ch;
			else
			{
				Chunk* last = firstChunk;
				while (last->next)
					last = last->next;
				last->next = ch;
			}
			if (maxChunks < numChunks)
				maxChunks = numChunks;
			return ch->units[0];
		}

		void Dealloc(void* ptr)
		{
			uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
			CriticalSection guard(lock);
			for (Chunk* ch = firstChunk; ch; ch = ch->next)
			{
				uintptr_t rangeBegin = reinterpret_cast<uintptr_t>(ch->units[0]);
				uintptr_t rangeEnd = reinterpret_cast<uintptr_t>(ch->units[MaxUnitsPerChunk-1]);
				if (addr >= rangeBegin && addr <= rangeEnd)
				{
					unsigned int index = (unsigned int)((addr - rangeBegin) / sizeof(Unit));
					ch->occupied ^= (1 << index);
					numAllocated--;
					return;
				}
			}
			// error: ptr was not allocated from this allocator!
			DKASSERT_STD_DESC_DEBUG(false, "Given address was not allocated from this allocator!");
		}

		void Reserve(size_t n)		// preallocate
		{
			CriticalSection guard(lock);
			size_t numAllocs = 0;
			if (numAllocs < n)
			{				
				if (firstChunk == NULL)
				{
					firstChunk = (Chunk*)BaseAllocator::Alloc(sizeof(Chunk));
					firstChunk->occupied = 0;
					firstChunk->next = NULL;
					numAllocs += MaxUnitsPerChunk;
					numChunks++;
				}
				Chunk* lastChunk = firstChunk;
				while (lastChunk->next)
				{
					numAllocs += MaxUnitsPerChunk;
					lastChunk = lastChunk->next;
				}
				while (numAllocs < n)
				{
					lastChunk->next = (Chunk*)BaseAllocator::Alloc(sizeof(Chunk));
					lastChunk = lastChunk->next;
					lastChunk->occupied = 0;
					lastChunk->next = NULL;

					numAllocs += MaxUnitsPerChunk;
					numChunks++;
				}
				if (maxChunks < numChunks)
					maxChunks = numChunks;
			}
		}

		void Reserve(size_t n)
		{
			CriticalSection guard(lock);
			size_t numAllocs = 0;
			if (numAllocs < n)
			{
				Chunk* lastChunk = firstChunk;
				if (lastChunk == NULL)
				{
					Chunk* ch = (Chunk*)BaseAllocator::Alloc(sizeof(Chunk));
					ch->occupied = 0;
					ch->next = NULL;
					firstChunk = ch;
					lastChunk = ch;
					numAllocs += MaxUnitsPerChunk;
					numChunks++;
				}
				while (lastChunk->next)
				{
					numAllocs += MaxUnitsPerChunk;
					lastChunk = lastChunk->next;
				}

				while (numAllocs < n)
				{
					numAllocs += MaxUnitsPerChunk;
					numChunks++;
					lastChunk->next = (Chunk*)BaseAllocator::Alloc(sizeof(Chunk));
					lastChunk = lastChunk->next;
					lastChunk->occupied = 0;
					lastChunk->next = NULL;
				}
			}
		}


		void Purge(void)	// delete unoccupied chunks
		{
			CriticalSection guard(lock);
			for (Chunk* ch = firstChunk; ch; ch = ch->next)
			{
				if (ch->next && ch->next->occupied == 0)
				{
					Chunk* freeChunk = ch->next;
					ch->next = freeChunk->next;
					BaseAllocator::Free(freeChunk);
					numChunks--;
				}
			}
			if (firstChunk && firstChunk->occupied == 0)
			{
				Chunk* freeChunk = firstChunk;
				firstChunk = freeChunk->next;
				BaseAllocator::Free(freeChunk);
				numChunks--;
			}
		}

		virtual ~DKFixedSizeAllocator(void)
		{
			DKASSERT_STD_DEBUG(numAllocated == 0);
			Chunk* nextChunk = firstChunk;
{'fraction_non_alphanumeric': 0.14506830924741373, 'fraction_numerical': 0.007423201453052199, 'mean_word_length': 2.9146831530139106, 'pattern_counts': {'":': 0, '<': 66, '<?xml version=': 0, '>': 117, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7375878', 'n_tokens_mistral': 5048, 'n_tokens_neox': 4042, 'n_words': 1070}