godot/core/templates/oa_hash_map.h

/**************************************************************************/
/*  oa_hash_map.h                                                         */
/**************************************************************************/
/*                         This file is part of:                          */
/*                             GODOT ENGINE                               */
/*                        https://godotengine.org                         */
/**************************************************************************/
/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur.                  */
/*                                                                        */
/* 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.                 */
/**************************************************************************/

#ifndef OA_HASH_MAP_H
#define OA_HASH_MAP_H

#include "core/math/math_funcs.h"
#include "core/os/memory.h"
#include "core/templates/hashfuncs.h"

/**
 * A HashMap implementation that uses open addressing with Robin Hood hashing.
 * Robin Hood hashing swaps out entries that have a smaller probing distance
 * than the to-be-inserted entry, that evens out the average probing distance
 * and enables faster lookups. Backward shift deletion is employed to further
 * improve the performance and to avoid infinite loops in rare cases.
 *
 * The entries are stored inplace, so huge keys or values might fill cache lines
 * a lot faster.
 *
 * Only used keys and values are constructed. For free positions there's space
 * in the arrays for each, but that memory is kept uninitialized.
 *
 * The assignment operator copy the pairs from one map to the other.
 */
template <typename TKey, typename TValue,
		typename Hasher = HashMapHasherDefault,
		typename Comparator = HashMapComparatorDefault<TKey>>
class OAHashMap {
private:
	TValue *values = nullptr;
	TKey *keys = nullptr;
	uint32_t *hashes = nullptr;

	uint32_t capacity = 0;

	uint32_t num_elements = 0;

	static const uint32_t EMPTY_HASH = 0;

	_FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const { … }

	_FORCE_INLINE_ uint32_t _get_probe_length(uint32_t p_pos, uint32_t p_hash) const { … }

	_FORCE_INLINE_ void _construct(uint32_t p_pos, uint32_t p_hash, const TKey &p_key, const TValue &p_value) { … }

	bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const { … }

	void _insert_with_hash(uint32_t p_hash, const TKey &p_key, const TValue &p_value) { … }

	void _resize_and_rehash(uint32_t p_new_capacity) { … }

	void _resize_and_rehash() { … }

public:
	_FORCE_INLINE_ uint32_t get_capacity() const { … }
	_FORCE_INLINE_ uint32_t get_num_elements() const { … }

	bool is_empty() const { … }

	void clear() { … }

	void insert(const TKey &p_key, const TValue &p_value) { … }

	void set(const TKey &p_key, const TValue &p_data) { … }

	/**
	 * returns true if the value was found, false otherwise.
	 *
	 * if r_data is not nullptr then the value will be written to the object
	 * it points to.
	 */
	bool lookup(const TKey &p_key, TValue &r_data) const { … }

	const TValue *lookup_ptr(const TKey &p_key) const { … }

	TValue *lookup_ptr(const TKey &p_key) { … }

	_FORCE_INLINE_ bool has(const TKey &p_key) const { … }

	void remove(const TKey &p_key) { … }

	/**
	 * reserves space for a number of elements, useful to avoid many resizes and rehashes
	 *  if adding a known (possibly large) number of elements at once, must be larger than old
	 *  capacity.
	 **/
	void reserve(uint32_t p_new_capacity) { … }

	struct Iterator {
		bool valid;

		const TKey *key;
		TValue *value = nullptr;

	private:
		uint32_t pos;
		friend class OAHashMap;
	};

	Iterator iter() const { … }

	Iterator next_iter(const Iterator &p_iter) const { … }

	OAHashMap(const OAHashMap &p_other) { … }

	void operator=(const OAHashMap &p_other) { … }

	OAHashMap(uint32_t p_initial_capacity = 64) { … }

	~OAHashMap() { … }
};

#endif // OA_HASH_MAP_H