<commit_before>/*
 * Copyright (c) 2012-2016 <NAME> and individual contributors.
 * License: https://github.com/taylor001/crown/blob/master/LICENSE
 */

// http://sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/

#pragma once

#include "container_types.h"
#include <algorithm> // std::swap
#include <string.h>  // memcpy

namespace crown
{
/// Functions to manipulate HashMap.
///
/// @ingroup Containers
namespace hash_map
{
	/// Returns the number of items in the map @a m.
	template <typename TKey, typename TValue, typename Hash> u32 size(const HashMap<TKey, TValue, Hash>& m);

	/// Returns whether the given @a key exists in the map @a m.
	template <typename TKey, typename TValue, typename Hash> bool has(const HashMap<TKey, TValue, Hash>& m, const TKey& key);

	/// Returns the value for the given @a key or @a deffault if
	/// the key does not exist in the map.
	template <typename TKey, typename TValue, typename Hash> const TValue& get(const HashMap<TKey, TValue, Hash>& m, const TKey& key, const TValue& deffault);

	/// Sets the @a value for the @a key in the map.
	template <typename TKey, typename TValue, typename Hash> void set(HashMap<TKey, TValue, Hash>& m, const TKey& key, const TValue& value);

	/// Removes the @a key from the map if it exists.
	template <typename TKey, typename TValue, typename Hash> void remove(HashMap<TKey, TValue, Hash>& m, const TKey& key);

	/// Removes all the items in the map.
	///
	/// @note
	/// Calls destructor on the items.
	template <typename TKey, typename TValue, typename Hash> void clear(HashMap<TKey, TValue, Hash>& m);
} // namespace hash_map

namespace hash_map_internal
{
	const u32 END_OF_LIST = 0xffffffffu;
	const u32 DELETED = 0x80000000u;
	const u32 FREE = 0x00000000u;

	template <typename TKey, class Hash>
	inline u32 hash_key(const TKey& key)
	{
		const Hash hash;
		u32 h = hash(key);

		// MSB is used to indicate a deleted elem, so
		// clear it
		h &= 0x7fffffffu;

		// Ensure that we never return 0 as a hash,
		// since we use 0 to indicate that the elem has never
		// been used at all.
		h |= h == 0u;

		return h;
	}

	inline bool is_deleted(u32 hash)
	{
		// MSB set indicates that this hash is a "tombstone"
		return (hash >> 31) != 0;
	}

	template <typename TKey, typename TValue, typename Hash>
	inline u32 probe_distance(const HashMap<TKey, TValue, Hash>& m, u32 hash, u32 slot_index)
	{
		const u32 hash_i = hash & m._mask;
		return (slot_index + m._capacity - hash_i) & m._mask;
	}

	template <typename TKey, typename TValue, typename Hash>
	u32 find(const HashMap<TKey, TValue, Hash>& m, const TKey& key)
	{
		if (m._size == 0)
			return END_OF_LIST;

		const u32 hash = hash_key<TKey, Hash>(key);
		u32 hash_i = hash & m._mask;
		u32 dist = 0;
		for(;;)
		{
			if (m._hashes[hash_i] == 0)
				return END_OF_LIST;
			else if (dist > probe_distance(m, m._hashes[hash_i], hash_i))
				return END_OF_LIST;
			else if (m._hashes[hash_i] == hash && m._data[hash_i].pair.first == key)
				return hash_i;

			hash_i = (hash_i + 1) & m._mask;
			++dist;
		}
	}

	template <typename TKey, typename TValue, typename Hash>
	void insert(HashMap<TKey, TValue, Hash>& m, u32 hash, TKey& key, TValue& value)
	{
		u32 hash_i = hash & m._mask;
		u32 dist = 0;
		for(;;)
		{
			if (m._hashes[hash_i] == FREE)
				goto INSERT_AND_RETURN;

			// If the existing elem has probed less than us, then swap places with existing
			// elem, and keep going to find another slot for that elem.
			u32 existing_elem_probe_dist = probe_distance(m, m._hashes[hash_i], hash_i);
			if (existing_elem_probe_dist < dist)
			{
				if (is_deleted(m._hashes[hash_i]))
					goto INSERT_AND_RETURN;

				std::swap(hash, m._hashes[hash_i]);
				std::swap(key, m._data[hash_i].pair.first);
				std::swap(value, m._data[hash_i].pair.second);
				dist = existing_elem_probe_dist;
			}

			hash_i = (hash_i + 1) & m._mask;
			++dist;
		}

	INSERT_AND_RETURN:
		m._data[hash_i].pair.first = key;
		m._data[hash_i].pair.second = value;
		m._hashes[hash_i] = hash;
	}

	template <typename TKey, typename TValue, typename Hash>
	void rehash(HashMap<TKey, TValue, Hash>& m, u32 new_capacity)
	{
		typedef typename HashMap<TKey, TValue, Hash>::Entry Entry;

		HashMap<TKey, TValue, Hash> nm(*m._allocator);
		nm._hashes = (u32*)nm._allocator->allocate(new_capacity*sizeof(u32), alignof(u32));
		nm._data = (Entry*)nm._allocator->allocate(new_capacity*sizeof(Entry), alignof(Entry));<commit_msg>Call constructors on ALLOCATOR_AWARE objects<commit_after>/*
 * Copyright (c) 2012-2016 <NAME> and individual contributors.
 * License: https://github.com/taylor001/crown/blob/master/LICENSE
 */

// http://sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/

#pragma once

#include "container_types.h"
#include <algorithm> // std::swap
#include <new>
#include <string.h>  // memcpy

namespace crown
{
/// Functions to manipulate HashMap.
///
/// @ingroup Containers
namespace hash_map
{
	/// Returns the number of items in the map @a m.
	template <typename TKey, typename TValue, typename Hash> u32 size(const HashMap<TKey, TValue, Hash>& m);

	/// Returns whether the given @a key exists in the map @a m.
	template <typename TKey, typename TValue, typename Hash> bool has(const HashMap<TKey, TValue, Hash>& m, const TKey& key);

	/// Returns the value for the given @a key or @a deffault if
	/// the key does not exist in the map.
	template <typename TKey, typename TValue, typename Hash> const TValue& get(const HashMap<TKey, TValue, Hash>& m, const TKey& key, const TValue& deffault);

	/// Sets the @a value for the @a key in the map.
	template <typename TKey, typename TValue, typename Hash> void set(HashMap<TKey, TValue, Hash>& m, const TKey& key, const TValue& value);

	/// Removes the @a key from the map if it exists.
	template <typename TKey, typename TValue, typename Hash> void remove(HashMap<TKey, TValue, Hash>& m, const TKey& key);

	/// Removes all the items in the map.
	///
	/// @note
	/// Calls destructor on the items.
	template <typename TKey, typename TValue, typename Hash> void clear(HashMap<TKey, TValue, Hash>& m);
} // namespace hash_map

namespace hash_map_internal
{
	const u32 END_OF_LIST = 0xffffffffu;
	const u32 DELETED = 0x80000000u;
	const u32 FREE = 0x00000000u;

	template <typename TKey, class Hash>
	inline u32 hash_key(const TKey& key)
	{
		const Hash hash;
		u32 h = hash(key);

		// MSB is used to indicate a deleted elem, so
		// clear it
		h &= 0x7fffffffu;

		// Ensure that we never return 0 as a hash,
		// since we use 0 to indicate that the elem has never
		// been used at all.
		h |= h == 0u;

		return h;
	}

	inline bool is_deleted(u32 hash)
	{
		// MSB set indicates that this hash is a "tombstone"
		return (hash >> 31) != 0;
	}

	template <typename TKey, typename TValue, typename Hash>
	inline u32 probe_distance(const HashMap<TKey, TValue, Hash>& m, u32 hash, u32 slot_index)
	{
		const u32 hash_i = hash & m._mask;
		return (slot_index + m._capacity - hash_i) & m._mask;
	}

	template <typename TKey, typename TValue, typename Hash>
	u32 find(const HashMap<TKey, TValue, Hash>& m, const TKey& key)
	{
		if (m._size == 0)
			return END_OF_LIST;

		const u32 hash = hash_key<TKey, Hash>(key);
		u32 hash_i = hash & m._mask;
		u32 dist = 0;
		for(;;)
		{
			if (m._hashes[hash_i] == 0)
				return END_OF_LIST;
			else if (dist > probe_distance(m, m._hashes[hash_i], hash_i))
				return END_OF_LIST;
			else if (m._hashes[hash_i] == hash && m._data[hash_i].pair.first == key)
				return hash_i;

			hash_i = (hash_i + 1) & m._mask;
			++dist;
		}
	}

	template <typename TKey, typename TValue, typename Hash>
	void insert(HashMap<TKey, TValue, Hash>& m, u32 hash, TKey& key, TValue& value)
	{
		u32 hash_i = hash & m._mask;
		u32 dist = 0;
		for(;;)
		{
			if (m._hashes[hash_i] == FREE)
				goto INSERT_AND_RETURN;

			// If the existing elem has probed less than us, then swap places with existing
			// elem, and keep going to find another slot for that elem.
			u32 existing_elem_probe_dist = probe_distance(m, m._hashes[hash_i], hash_i);
			if (existing_elem_probe_dist < dist)
			{
				if (is_deleted(m._hashes[hash_i]))
					goto INSERT_AND_RETURN;

				std::swap(hash, m._hashes[hash_i]);
				std::swap(key, m._data[hash_i].pair.first);
				std::swap(value, m._data[hash_i].pair.second);
				dist = existing_elem_probe_dist;
			}

			hash_i = (hash_i + 1) & m._mask;
			++dist;
		}

	INSERT_AND_RETURN:
		new (m._data + hash_i) typename HashMap<TKey, TValue, Hash>::Entry(*m._allocator);
		m._data[hash_i].pair.first = key;
		m._data[hash_i].pair.second = value;
		m._hashes[hash_i] = hash;
	}

	template <typename TKey, typename TValue, typename Hash>
	void rehash(HashMap<TKey, TValue, Hash>& m, u32 new_capacity)
	{
		typedef typename HashMap<TKey, TValue, Hash>::Entry Entry;

		HashMap<TKey, TValue, Hash> nm(*m._allocator);
		nm._hashes = (u32*)nm._allocator->allocate(new_capacity*sizeof(u32), alignof(u32));
		nm._data = (Entry*)nm._allocator->allocate(new_capacity*sizeof(Entry), alignof(Entry));
{'fraction_non_alphanumeric': 0.12757065874848786, 'fraction_numerical': 0.01979544704717915, 'mean_word_length': 3.724155844155844, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 69, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 8, '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': '7462576', 'n_tokens_mistral': 3619, 'n_tokens_neox': 3206, 'n_words': 1008}