RmlUi/Source/Core/GeometryDatabase.cpp

/*
 * This source file is part of RmlUi, the HTML/CSS Interface Middleware
 *
 * For the latest information, see http://github.com/mikke89/RmlUi
 *
 * Copyright (c) 2008-2010 CodePoint Ltd, Shift Technology Ltd
 * Copyright (c) 2019 The RmlUi Team, and contributors
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 */

#include "GeometryDatabase.h"
#include "../../Include/RmlUi/Core/Geometry.h"
#include <algorithm>


namespace Rml {
namespace GeometryDatabase {

class Database {
public:
	Database() {
		constexpr size_t reserve_size = 512;
		geometry_list.reserve(reserve_size);
		free_list.reserve(reserve_size);
	}

	~Database() {
#ifdef RMLUI_TESTS_ENABLED
		RMLUI_ASSERT(geometry_list.size() == free_list.size());
		std::sort(free_list.begin(), free_list.end());
		for (size_t i = 0; i < free_list.size(); i++)
		{
			RMLUI_ASSERT(i == free_list[i]);
		}
#endif
	}

	GeometryDatabaseHandle insert(Geometry* value)
	{
		GeometryDatabaseHandle handle;
		if (free_list.empty())
		{
			handle = GeometryDatabaseHandle(geometry_list.size());
			geometry_list.push_back(value);
		}
		else
		{
			handle = free_list.back();
			free_list.pop_back();
			geometry_list[handle] = value;
		}
		return handle;
	}

	int size() const
	{
		return (int)geometry_list.size() - (int)free_list.size();
	}

	void clear() {
		geometry_list.clear();
		free_list.clear();
	}
	void erase(GeometryDatabaseHandle handle)
	{
		free_list.push_back(handle);
	}

	// Iterate over every item in the database, skipping free slots.
	template<typename Func>
	void for_each(Func func)
	{
		std::sort(free_list.begin(), free_list.end());

		size_t i_begin_next = 0;
		for (GeometryDatabaseHandle freelist_entry : free_list)
		{
			const size_t i_end = size_t(freelist_entry);
			const size_t i_begin = i_begin_next;
			i_begin_next = i_end + 1;

			for (size_t i = i_begin; i < i_end; i++)
				func(geometry_list[i]);
		}

		for (size_t i = i_begin_next; i < geometry_list.size(); i++)
				func(geometry_list[i]);
	}

private:
	// List of all active geometry, in addition to free slots.
	// Free slots (as defined by the 'free_list') may contain dangling pointers and must not be dereferenced.
	Vector<Geometry*> geometry_list;
	// Declares free slots in the 'geometry_list' as indices.
	Vector<GeometryDatabaseHandle> free_list;
};


static Database geometry_database;

GeometryDatabaseHandle Insert(Geometry* geometry)
{
	return geometry_database.insert(geometry);
}

void Erase(GeometryDatabaseHandle handle)
{
	geometry_database.erase(handle);
}

void ReleaseAll()
{
	geometry_database.for_each([](Geometry* geometry) {
		geometry->Release();
	});
}


#ifdef RMLUI_TESTS_ENABLED

bool PrepareForTests()
{
	if (geometry_database.size() > 0)
		return false;

	// Even with size()==0 we can have items in the geometry list which should all be duplicated by the free list. We want to clear them for the tests.
	geometry_database.clear();

	return true;
}

bool ListMatchesDatabase(const Vector<Geometry>& geometry_list)
{
	int i = 0;
	bool result = true;
	geometry_database.for_each([&geometry_list, &i, &result](Geometry* geometry) {
		result &= (geometry == &geometry_list[i++]);
		});
	return result;
}

#endif // RMLUI_TESTS_ENABLED

} // namespace GeometryDatabase
} // namespace Rml