tag_store.cpp

namespace tags
{
	// TODO: Add support for "has tag" queries. Preferably through a big-ass bit vector.
	typedef unsigned Tag;

	struct TagInstance
	{
		Entity entity;
		MultiInstanceComponent::InstanceId component;
	};

	const unsigned BLOCK_SIZE = 1024;
	const unsigned PAGE_SIZE = 64 * 1024;
	const unsigned INSTANCES_PER_BLOCK = BLOCK_SIZE / sizeof(TagInstance);

	namespace
	{
		struct Page
		{
			void* p;
			unsigned used;
		};

		struct Block
		{
			TagInstance* instances;
			unsigned size;
		};
	}

	struct Store
	{
		// Not sorted for now. Sorting would allow for faster rejection of empty queries and better locality when
		// theres alot of instances for a particular tag. If the common case is that theres more that ~128 tags
		// a binary search might prove more efficient.
		// See https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/
		Array<Tag> block_tags;
		Array<Block> blocks;
		Array<Page> pages;

		Array<unsigned> sort_scratch;
		Allocator& allocator;

		explicit Store(Allocator& a) : block_tags(a), blocks(a), pages(a), sort_scratch(a), allocator(a) { };
		~Store()
		{
			for (const auto& p : pages)
				allocator.deallocate(p.p);
		}
	};

	namespace
	{
		Page make_page(Allocator& a)
		{
			Page p = { (TagInstance*)a.allocate(PAGE_SIZE), 0 };
			return p;
		}

		Block make_block(Page& p)
		{
			Block b = { (TagInstance*)memory_utilities::pointer_add(p.p, p.used), 0 };
			return b;
		}

		Block* allocate_block(Store& s, Tag t)
		{
			auto& page = s.pages.empty() || PAGE_SIZE - s.pages.back().used < BLOCK_SIZE
				? s.pages.extend() = make_page(s.allocator)
				: s.pages.back();

			auto& b = s.blocks.extend() = make_block(page);
			s.block_tags.extend() = t;
			page.used += BLOCK_SIZE;
			return &b;
		}
	}

	// Interface

	void instances(const Store& s, Tag tag, Array<TagInstance>& result)
	{
		const auto n_blocks = s.blocks.size();
		auto at = 0u;
		for (auto i = 0u; i < n_blocks; i++) {
			if (s.block_tags[i] != tag)
				continue;

			const auto& b = s.blocks[i];
			result.resize(result.size() + b.size);
			memcpy(result.begin() + at, b.instances, sizeof(*b.instances)*b.size);
			at += b.size;
		}
	}

	void tag_instance(Store& store, Entity e, MultiInstanceComponent::InstanceId c, const Tag* tags, const unsigned n_tags)
	{
		auto needs_sort = false;
		const int n_block_tags = store.block_tags.size();
		for (const auto t : range(tags, n_tags)) {
			auto* block = (Block*)nullptr;

			for (auto i = n_block_tags-1; i >= 0; i--) {
				if (store.block_tags[i] != t)
					continue;

				auto& b = store.blocks[i];
				if (b.size < INSTANCES_PER_BLOCK) {
					block = &b;
					break;
				}
			}

			if (block == nullptr)
				block = allocate_block(store, t);

			auto& inst = block->instances[block->size++];
			inst.entity = e;
			inst.component = c;
		}
	}

	void remove_instance(Store& store, MultiInstanceComponent::InstanceId c)
	{
		for (auto& block : store.blocks) {
			for (auto i = 0u; i < block.size; ++i) {
				if (block.instances[i].component == c) {
					block.instances[i] = block.instances[--block.size];
					break;
				}
			}
		}
	}

	inline Tag tag(const char* s) { return IdString32(s).id(); }
}