<commit_before>#ifndef _H_BIT_MAP_ALLOC
#define _H_BIT_MAP_ALLOC

#include "alloc-common.h"
#include <cstdint>
#include <cassert>
#include <mutex>

template<class backing, size_t blockSize, size_t numBlocks>
class BitMapAlloc: private backing {
private:
	Block root;
	std::mutex mapMutex;
	uint8_t map[numBlocks/8];

	void markFree(size_t num) {
		map[getMapByteNum(num)] ^= getMapBit(num);
	}

	void markUsed(size_t num) {

		map[getMapByteNum(num)] |= getMapBit(num);
	}

	bool isUsed(size_t num) {

		return map[getMapByteNum(num)] & getMapBit(num);
	}

	void * getBlkPtr(size_t blkNum) {
		return (void*)((char *)root.ptr + (blkNum * blockSize));
	}

	size_t getBlkNum(void * ptr) {
		return ((size_t)ptr - (size_t)root.ptr)/ blockSize;
	}

	static constexpr size_t getMapByteNum(size_t num) {
		return num / 8;
	}

	static constexpr size_t getMapBit(size_t num) {
		return (1 << (8-(num % 8)));
	}

public:
	BitMapAlloc():root(backing::allocate(numBlocks*blockSize)) {
		assert(root.ptr != nullptr);
	}

	Block allocate(size_t size) {
		std::lock_guard<std::mutex> lock(mapMutex);
		const auto blocksNeeded = goodSize(size)/blockSize;

		for(size_t start = 0; start<numBlocks; start++) {
			if (!isUsed(start))
			{
				size_t freeCount = 0;
				for(size_t end = start; (end < numBlocks) && (freeCount < blocksNeeded); end++) {
					if (isUsed(end))
					{
						break;
					}
					freeCount++;
				}
				if (freeCount == blocksNeeded) {
					for (size_t i = (start - (size_t)root.ptr); i < start + blocksNeeded; i++) {
						markUsed(i);
					}
					return {getBlkPtr(start), goodSize(size)};
				}
			}
		}

		return {nullptr, 0};
	}

	void deallocate(Block blk) {
		std::lock_guard<std::mutex> lock(mapMutex);
		const auto startNum = getBlkNum(blk.ptr);
		const auto endNum = startNum + blk.size / blockSize;
		for(size_t i = startNum; i < endNum; i++) {
			markFree(i);
		}
	}

	constexpr static size_t alignment() {
		return 16;
	}

	static_assert(blockSize % alignment() == 0, "Blocks must be aligned");

	constexpr static size_t goodSize(size_t a) {
		return a  + (blockSize - (a % blockSize));<commit_msg>Remove the mutex. To be added via its own allocator.<commit_after>#ifndef _H_BIT_MAP_ALLOC
#define _H_BIT_MAP_ALLOC

#include "alloc-common.h"
#include <cstdint>
#include <cassert>
#include <mutex>

template<class backing, size_t blockSize, size_t numBlocks>
class BitMapAlloc: private backing {
private:
	Block root;
	uint8_t map[numBlocks/8];

	void markFree(size_t num) {
		map[getMapByteNum(num)] ^= getMapBit(num);
	}

	void markUsed(size_t num) {

		map[getMapByteNum(num)] |= getMapBit(num);
	}

	bool isUsed(size_t num) {

		return map[getMapByteNum(num)] & getMapBit(num);
	}

	void * getBlkPtr(size_t blkNum) {
		return (void*)((char *)root.ptr + (blkNum * blockSize));
	}

	size_t getBlkNum(void * ptr) {
		return ((size_t)ptr - (size_t)root.ptr)/ blockSize;
	}

	static constexpr size_t getMapByteNum(size_t num) {
		return num / 8;
	}

	static constexpr size_t getMapBit(size_t num) {
		return (1 << (8-(num % 8)));
	}

public:
	BitMapAlloc():root(backing::allocate(numBlocks*blockSize)) {
		assert(root.ptr != nullptr);
	}

	Block allocate(size_t size) {
		const auto blocksNeeded = goodSize(size)/blockSize;

		for(size_t start = 0; start<numBlocks; start++) {
			if (!isUsed(start))
			{
				size_t freeCount = 0;
				for(size_t end = start; (end < numBlocks) && (freeCount < blocksNeeded); end++) {
					if (isUsed(end))
					{
						break;
					}
					freeCount++;
				}
				if (freeCount == blocksNeeded) {
					for (size_t i = (start - (size_t)root.ptr); i < start + blocksNeeded; i++) {
						markUsed(i);
					}
					return {getBlkPtr(start), goodSize(size)};
				}
			}
		}

		return {nullptr, 0};
	}

	void deallocate(Block blk) {
		const auto startNum = getBlkNum(blk.ptr);
		const auto endNum = startNum + blk.size / blockSize;
		for(size_t i = startNum; i < endNum; i++) {
			markFree(i);
		}
	}

	constexpr static size_t alignment() {
		return 16;
	}

	static_assert(blockSize % alignment() == 0, "Blocks must be aligned");

	constexpr static size_t goodSize(size_t a) {
		return a  + (blockSize - (a % blockSize));
{'fraction_non_alphanumeric': 0.14491708723864455, 'fraction_numerical': 0.005767844268204758, 'mean_word_length': 3.8227114716106603, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 13, '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': '564065', 'n_tokens_mistral': 1779, 'n_tokens_neox': 1569, 'n_words': 354}