<commit_before>// http://www.apache.org/licenses/LICENSE-2.0
// Copyright 2014 <NAME> <<EMAIL>>
#include "lua_bindings/util.h"
#include "core/log.h"
#include <tolua++.h>
#include <Vector3.h>
#include <list>
#include <algorithm>
#define MODULE "lua_bindings"

#define DEF_METHOD(name){ \
		lua_pushcfunction(L, l_##name); \
		lua_setfield(L, -2, #name); \
}

#define GET_TOLUA_STUFF(result_name, index, type) \
	if(!tolua_isusertype(L, index, #type, 0, &tolua_err)){ \
		tolua_error(L, __PRETTY_FUNCTION__, &tolua_err); \
		return 0; \
	} \
	type *result_name = (type*)tolua_tousertype(L, index, 0);
#define TRY_GET_TOLUA_STUFF(result_name, index, type) \
	type *result_name = nullptr; \
	if(tolua_isusertype(L, index, #type, 0, &tolua_err)){ \
		result_name = (type*)tolua_tousertype(L, index, 0); \
	}

// Just do this; Urho3D's stuff doesn't really clash with anything in buildat
using namespace Urho3D;

namespace lua_bindings {

struct SpatialUpdateQueue
{
	struct Value {
		ss_ type;
		uint32_t node_id = -1;
	};

	struct Item { // Queue item
		Vector3 p = Vector3(0, 0, 0);
		Value value;
		float near_weight = -1.0f;
		float near_trigger_d = -1.0f;
		float far_weight = -1.0f;
		float far_trigger_d = -1.0f;
		float f = -1.0f;
		float fw = -1.0f;

		bool operator>(const Item &other) const;
	};

	// Set of values with iterators for fast access of items, so that items
	// can be removed quickly by value
	struct ValueSet
	{
		struct Entry
		{
			Value value;
			std::list<Item>::iterator it;

			Entry(const Value &value, std::list<Item>::iterator it =
					std::list<Item>::iterator()):
				value(value), it(it)
			{}
			bool operator>(const Entry &other) const {
				if(value.node_id > other.value.node_id)
					return true;
				if(value.node_id < other.value.node_id)
					return false;
				return value.type > other.value.type;
			}
		};

		// sorted list in descending node_id and type order
		std::list<Entry> m_set;

		void clear(){
			m_set.clear();
		}
		void insert(const Value &value, std::list<Item>::iterator queue_it){
			Entry entry(value, queue_it);
			auto it = std::lower_bound(m_set.begin(), m_set.end(), entry,
						std::greater<Entry>());
			if(it == m_set.end())
				m_set.insert(it, entry);
			else if(it->value.node_id != value.node_id ||
					it->value.type != value.type)
				m_set.insert(it, entry);
			else
				*it = entry;
		}
		void remove(const Value &value){
			Entry entry(value);
			auto it = std::lower_bound(m_set.begin(), m_set.end(), entry,
						std::greater<Entry>());
			if(it == m_set.end())
				return;
			m_set.erase(it);
		}
		std::list<Item>::iterator*find(const Value &value){
			Entry entry(value);
			auto it = std::lower_bound(m_set.begin(), m_set.end(), entry,
						std::greater<Entry>());
			if(it == m_set.end())
				return nullptr;
			if(it->value.node_id != value.node_id ||
					it->value.type != value.type)
				return nullptr;
			return &(it->it);
		}
	};

	Vector3 m_p;
	Vector3 m_queue_oldest_p;
	size_t m_queue_length = 0; // GCC std::list's size() is O(n)
	std::list<Item> m_queue;
	std::list<Item> m_old_queue;

	ValueSet m_value_set;

	void update(int max_operations)
	{
		if(m_old_queue.empty())
			return;
		log_d(MODULE, "SpatialUpdateQueue(): Items in old queue: %zu",
				m_old_queue.size());
		for(int i = 0; i<max_operations; i++){
			if(m_old_queue.empty())
				break;
			Item &item = m_old_queue.back();
			put_item(item);
			m_old_queue.pop_back();
		}
	}

	void set_p(const Vector3 &p)
	{
		m_p = p;
		if(m_old_queue.empty() && (m_p - m_queue_oldest_p).Length() > 20){
			m_queue_length = 0;
			m_value_set.clear();
			m_old_queue.swap(m_queue);
			m_queue_oldest_p = m_p;
		}
	}

	void put_item(Item &item)
	{
		if(item.near_trigger_d == -1.0f && item.far_trigger_d == -1.0f)
			throw Exception("Item has neither trigger");
		float d = (item.p - m_p).Length();
		item.f = -1.0f;
		item.fw = -1.0f;
		if(item.near_trigger_d != -1.0f){
			float f_near = d / item.near_trigger_d;
			float fw_near = f_near / item.near_weight;
			if(item.fw == -1.0f || (fw_near < item.fw &&
					(item.f == -1.0f || f_near < item.f))){
				item.f = f_near;
				item.fw = fw_near;
			}
		}
		if(item.far_trigger_d != -1.0f){
			float f_far = item.far_trigger_d / d;
			float fw_far = f_far / item.far_weight;
			if(item.fw == -1.0f || (fw_far < item.fw &&
					(item.f == -1.0f || f_far < item.f))){
				item.f = f_far;
				item.fw = fw_far;
			}
		}
		if(item.f == -1.0f || item.fw == -1.0f)
			throw Exception("item.f == -1.0f || item.fw == -1.0f");

		// Find old entry; if the old entry is more important, discard the new
		// one; if the old entry is less important, remove the old entry
		std::list<Item>::iterator *itp = m_value_set.find(item.value);
		if(itp != nullptr){
			Item &old_item = **itp;
			if(old_item.fw < item.fw){
				// Old item is more important
				return;
			} else {
				// New item is more important
				m_value_set.remove(item.value);
				m_queue.erase(*itp);
				m_queue_length--;
			}
		}

		auto it = std::lower_bound(m_queue.begin(), m_queue.end(),
					item, std::greater<Item>()); // position in descending order
		auto inserted_it = m_queue.insert(it, item);
		m_queue_length++;
		m_value_set.insert(item.value, inserted_it);
	}

	void put(const Vector3 &p, float near_weight, float near_trigger_d,
			float far_weight, float far_trigger_d, const Value &value)
	{
		Item item;
		item.p = p;
		item.near_weight = near_weight;
		item.near_trigger_d = near_trigger_d;
		item.far_weight = far_weight;
		item.far_trigger_d = far_trigger_d;
		item.value = value;
		put_item(item);
	}

	bool empty()
	{
		return m_queue.empty();
	}
<commit_msg>lua_bindings/spatial_update_queue: Fix invalid access of freed memory<commit_after>// http://www.apache.org/licenses/LICENSE-2.0
// Copyright 2014 <NAME> <<EMAIL>>
#include "lua_bindings/util.h"
#include "core/log.h"
#include <tolua++.h>
#include <Vector3.h>
#include <list>
#include <algorithm>
#define MODULE "lua_bindings"

#define DEF_METHOD(name){ \
		lua_pushcfunction(L, l_##name); \
		lua_setfield(L, -2, #name); \
}

#define GET_TOLUA_STUFF(result_name, index, type) \
	if(!tolua_isusertype(L, index, #type, 0, &tolua_err)){ \
		tolua_error(L, __PRETTY_FUNCTION__, &tolua_err); \
		return 0; \
	} \
	type *result_name = (type*)tolua_tousertype(L, index, 0);
#define TRY_GET_TOLUA_STUFF(result_name, index, type) \
	type *result_name = nullptr; \
	if(tolua_isusertype(L, index, #type, 0, &tolua_err)){ \
		result_name = (type*)tolua_tousertype(L, index, 0); \
	}

// Just do this; Urho3D's stuff doesn't really clash with anything in buildat
using namespace Urho3D;

namespace lua_bindings {

struct SpatialUpdateQueue
{
	struct Value {
		ss_ type;
		uint32_t node_id = -1;
	};

	struct Item { // Queue item
		Vector3 p = Vector3(0, 0, 0);
		Value value;
		float near_weight = -1.0f;
		float near_trigger_d = -1.0f;
		float far_weight = -1.0f;
		float far_trigger_d = -1.0f;
		float f = -1.0f;
		float fw = -1.0f;

		bool operator>(const Item &other) const;
	};

	// Set of values with iterators for fast access of items, so that items
	// can be removed quickly by value
	struct ValueSet
	{
		struct Entry
		{
			Value value;
			std::list<Item>::iterator it;

			Entry(const Value &value, std::list<Item>::iterator it =
					std::list<Item>::iterator()):
				value(value), it(it)
			{}
			bool operator>(const Entry &other) const {
				if(value.node_id > other.value.node_id)
					return true;
				if(value.node_id < other.value.node_id)
					return false;
				return value.type > other.value.type;
			}
		};

		// sorted list in descending node_id and type order
		std::list<Entry> m_set;

		void clear(){
			m_set.clear();
		}
		void insert(const Value &value, std::list<Item>::iterator queue_it){
			Entry entry(value, queue_it);
			auto it = std::lower_bound(m_set.begin(), m_set.end(), entry,
						std::greater<Entry>());
			if(it == m_set.end())
				m_set.insert(it, entry);
			else if(it->value.node_id != value.node_id ||
					it->value.type != value.type)
				m_set.insert(it, entry);
			else
				*it = entry;
		}
		void remove(const Value &value){
			Entry entry(value);
			auto it = std::lower_bound(m_set.begin(), m_set.end(), entry,
						std::greater<Entry>());
			if(it == m_set.end())
				return;
			m_set.erase(it);
		}
		std::list<Item>::iterator*find(const Value &value){
			Entry entry(value);
			auto it = std::lower_bound(m_set.begin(), m_set.end(), entry,
						std::greater<Entry>());
			if(it == m_set.end())
				return nullptr;
			if(it->value.node_id != value.node_id ||
					it->value.type != value.type)
				return nullptr;
			return &(it->it);
		}
	};

	Vector3 m_p;
	Vector3 m_queue_oldest_p;
	size_t m_queue_length = 0; // GCC std::list's size() is O(n)
	std::list<Item> m_queue;
	std::list<Item> m_old_queue;

	ValueSet m_value_set;

	void update(int max_operations)
	{
		if(m_old_queue.empty())
			return;
		log_d(MODULE, "SpatialUpdateQueue(): Items in old queue: %zu",
				m_old_queue.size());
		for(int i = 0; i<max_operations; i++){
			if(m_old_queue.empty())
				break;
			Item &item = m_old_queue.back();
			put_item(item);
			m_old_queue.pop_back();
		}
	}

	void set_p(const Vector3 &p)
	{
		m_p = p;
		if(m_old_queue.empty() && (m_p - m_queue_oldest_p).Length() > 20){
			m_queue_length = 0;
			m_value_set.clear();
			m_old_queue.swap(m_queue);
			m_queue_oldest_p = m_p;
		}
	}

	void put_item(Item &item)
	{
		if(item.near_trigger_d == -1.0f && item.far_trigger_d == -1.0f)
			throw Exception("Item has neither trigger");
		float d = (item.p - m_p).Length();
		item.f = -1.0f;
		item.fw = -1.0f;
		if(item.near_trigger_d != -1.0f){
			float f_near = d / item.near_trigger_d;
			float fw_near = f_near / item.near_weight;
			if(item.fw == -1.0f || (fw_near < item.fw &&
					(item.f == -1.0f || f_near < item.f))){
				item.f = f_near;
				item.fw = fw_near;
			}
		}
		if(item.far_trigger_d != -1.0f){
			float f_far = item.far_trigger_d / d;
			float fw_far = f_far / item.far_weight;
			if(item.fw == -1.0f || (fw_far < item.fw &&
					(item.f == -1.0f || f_far < item.f))){
				item.f = f_far;
				item.fw = fw_far;
			}
		}
		if(item.f == -1.0f || item.fw == -1.0f)
			throw Exception("item.f == -1.0f || item.fw == -1.0f");

		// Find old entry; if the old entry is more important, discard the new
		// one; if the old entry is less important, remove the old entry
		std::list<Item>::iterator *itp = m_value_set.find(item.value);
		if(itp != nullptr){
			Item &old_item = **itp;
			if(old_item.fw < item.fw){
				// Old item is more important
				return;
			} else {
				// New item is more important
				m_queue.erase(*itp);
				m_queue_length--;
				m_value_set.remove(item.value);
			}
		}

		auto it = std::lower_bound(m_queue.begin(), m_queue.end(),
					item, std::greater<Item>()); // position in descending order
		auto inserted_it = m_queue.insert(it, item);
		m_queue_length++;
		m_value_set.insert(item.value, inserted_it);
	}

	void put(const Vector3 &p, float near_weight, float near_trigger_d,
			float far_weight, float far_trigger_d, const Value &value)
	{
		Item item;
		item.p = p;
		item.near_weight = near_weight;
		item.near_trigger_d = near_trigger_d;
		item.far_weight = far_weight;
		item.far_trigger_d = far_trigger_d;
		item.value = value;
		put_item(item);
	}

	bool empty()
	{
		return m_queue.empty();
	}

{'fraction_non_alphanumeric': 0.15810834656784895, 'fraction_numerical': 0.01270513499205929, 'mean_word_length': 3.3529185867895546, 'pattern_counts': {'":': 0, '<': 57, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '1548532', 'n_tokens_mistral': 5133, 'n_tokens_neox': 4483, 'n_words': 982}