Skip to content

Instantly share code, notes, and snippets.

@seanmiddleditch

seanmiddleditch/do1_hash_map

Last active November 23, 2016 18:47
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save seanmiddleditch/0ba0accb0322e08442d11650a40e6544 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save seanmiddleditch/0ba0accb0322e08442d11650a40e6544 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
do1_hash_map
/*
Copyright (C) 2016 Sean Middleditch <[email protected]>
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.
*/
#pragma once
#include "uhash.h"
namespace stlx
{
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT> class hash_map;
namespace _detail
{
template <typename HashResultT, typename ValueT> struct hash_map_data;
template <typename SlotT, typename ValueT> class hash_map_iterator;
}
}
template <typename SlotT, typename ValueT>
class stlx::_detail::hash_map_iterator : public std::iterator<std::forward_iterator_tag, ValueT>
{
SlotT const* _slot = nullptr;
ValueT* _value = nullptr;
public:
hash_map_iterator() = default;
hash_map_iterator& operator++() { ++_slot; ++_value; return *this; }
hash_map_iterator operator++(int) { auto tmp = *this; ++_slot; ++_value; return tmp; }
ValueT& operator*() const { return *_value; }
ValueT* operator->() const { return const_cast<ValueT*>(_value); }
bool operator==(hash_map_iterator const& rhs) const { return _slot == rhs._slot; }
bool operator!=(hash_map_iterator const& rhs) const { return _slot != rhs._slot; }
bool operator<(hash_map_iterator const& rhs) const { return _slot < rhs._slot; }
private:
explicit hash_map_iterator(SlotT const* s, ValueT* v) : _slot(s), _value(v) {}
template <typename, typename, typename, typename, typename> friend class hash_map;
};
/// Contains a map of values from KeyT to MappedT.
template <typename KeyT, typename MappedT, typename HashT = uhash<>, typename EqualT = std::equal_to<>, typename AllocatorT = stlx::default_allocator>
class stlx::hash_map : private AllocatorT
{
using slot_type = std::decay_t<decltype(HashT()(std::declval<KeyT>()))>;
using data_type = std::pair<KeyT const, MappedT>;
static constexpr slot_type kEmpty = ~static_cast<slot_type>(0);
static constexpr slot_type kHashMask = kEmpty >> 1;
static constexpr slot_type kTombstone = kHashMask;
static constexpr slot_type kLiveMask = ~kTombstone;
slot_type* _slots = nullptr;
data_type* _data = nullptr;
size_t _size = 0;
size_t _capacity = 0;
public:
using allocator_type = AllocatorT;
using size_type = size_t;
using key_type = KeyT;
using mapped_type = MappedT;
using value_type = std::pair<KeyT const, MappedT>;
using const_value_type = std::pair<KeyT const, MappedT const>;
using iterator = _detail::hash_map_iterator<slot_type, value_type>;
using const_iterator = _detail::hash_map_iterator<slot_type, const_value_type>;
hash_map() = default;
~hash_map();
hash_map(hash_map const&) = delete;
void operator=(hash_map const&) = delete;
hash_map(hash_map&&) = default;
hash_map& operator=(hash_map&&) = default;
inline iterator begin() { return iterator(_slots, _data); }
inline const_iterator begin() const { return const_iterator(_slots, _data); }
iterator end() { return iterator(_slots + _capacity, _data + _capacity); }
const_iterator end() const { return const_iterator(_slots + _capacity, reinterpret_cast<const_value_type*>(_data + _capacity)); }
bool empty() const { return _size == 0; }
size_type size() const { return _size; }
size_type capacity() const { return _capacity; }
/// Removes all values from the map.
void clear();
/// Checks if the containers holds a particular key.
bool has(KeyT const& key) const { return find(key) != end(); }
/// Inserts an element into the Map.
///
/// \param value The value to insert.
/// \returns Iterator of slot mapped to key, and a boolean indicating whether the value was inserted or not.
std::pair<iterator, bool> insert(std::pair<KeyT, MappedT>&& value) { return _insert(std::move(value)); }
/// Inserts an element into the Map.
///
/// \param value The value to insert.
/// \returns Iterator of slot mapped to key, and a boolean indicating whether the value was inserted or not.
std::pair<iterator, bool> insert(std::pair<KeyT, MappedT> const& value) { return _insert(value); }
/// Find an element with a given key, or insert it if it does not exist.
template <typename SearchT> MappedT& operator[](SearchT&& key);
MappedT& operator[](KeyT&& key) { return operator[]<KeyT>(std::forward<KeyT>(key)); }
/// Get a mutable non-const reference to the value associated with a key.
///
/// \param key The key to lookup.
/// \returns A reference to the corresponding value.
template <typename SearchT> iterator find(SearchT const& key) { return reinterpret_cast<iterator&>(const_cast<hash_map const&>(*this).find(key)); }
iterator find(KeyT const& key) { return find<KeyT>(key); }
/// Get a const reference to the value associated with a key.
///
/// \param key The key to lookup.
/// \returns A reference to the corresponding value.
template <typename SearchT> const_iterator find(SearchT const& key) const;
const_iterator find(KeyT const& key) const { return find<KeyT>(key); }
/// Removes an entry referenced by an iterator.
/// \param it The iterator to remove.
/// \returns The iterator pointing at the next element.
iterator erase(iterator it);
/// Removes a value and its assosicate key, if it exists.
/// \param key The key to remove.
/// \returns True if the key was found and an element removed, false otherwise.
template <typename SearchT> size_type erase(SearchT const& key);
private:
template <typename InsertT> std::pair<iterator, bool> _insert(InsertT&& value);
void _resize_slots(size_t capacity);
};
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT>
stlx::hash_map<KeyT, MappedT, HashT, EqualT, AllocatorT>::~hash_map()
{
clear();
this->deallocate(_slots, _capacity * sizeof(slot_type), alignof(slot_type));
this->deallocate(_data, _capacity * sizeof(value_type), alignof(value_type));
}
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT>
template <typename InsertT>
auto stlx::hash_map<KeyT, MappedT, HashT, EqualT, AllocatorT>::_insert(InsertT&& value) -> std::pair<iterator, bool>
{
// allow up to 75% utilization... this could be a better heuristic
if (_size >= (_capacity >> 1) + (_capacity >> 2))
_resize_slots(_capacity != 0 ? _capacity << 1 : 8);
auto const hash_value = HashT{}(value.first) | kLiveMask;
auto const root = hash_value % _capacity;
auto index = root;
for (; index != _capacity; ++index)
if ((_slots[index] & kLiveMask) == 0)
break;
if (index == _capacity)
for (index = 0; index != root; ++index)
if ((_slots[index] & kLiveMask) == 0)
break;
_slots[index] = hash_value;
new (_data + index) value_type(std::forward<InsertT>(value));
++_size;
return {iterator(_slots + index, _data + index), true};
}
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT>
void stlx::hash_map<KeyT, MappedT, HashT, EqualT, AllocatorT>::clear()
{
for (auto index = 0; index != _capacity; ++index)
{
if ((_slots[index] & kLiveMask) != 0)
{
_slots[index] = kEmpty;
_data[index].~value_type();
}
}
_size = 0;
}
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT>
template <typename SearchT>
MappedT& stlx::hash_map<KeyT, MappedT, HashT, EqualT, AllocatorT>::operator[](SearchT&& key)
{
// allow up to 75% utilization... this could be a better heuristic
if (_size >= (_capacity >> 1) + (_capacity >> 2))
_resize_slots(_capacity != 0 ? _capacity * 2 : 8);
auto const hash_value = HashT{}(key) | kHashMask;
auto const root = hash_value % _capacity;
// return existing value if it exists
auto index = root;
for (; index != _capacity; ++index)
{
if (_slots[index] == hash_value)
return _data[index].second;
else if (_slots[index] == kEmpty)
break;
}
if (index == _capacity)
{
for (index = 0; index != root; ++index)
{
if (_slots[index] == hash_value)
return _data[index].second;
else if (_slots[index] == kEmpty)
break;
}
}
// insert a new record if we didn't find an existing one
return _insert(std::make_pair(std::forward<SearchT>(key), MappedT{})).first->second;
}
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT>
template <typename SearchT>
auto stlx::hash_map<KeyT, MappedT, HashT, EqualT, AllocatorT>::find(SearchT const& key) const -> const_iterator
{
if (_size == 0)
return end();
auto const hashed = HashT{}(key) | kLiveMask;
auto const root = hashed % _capacity;
auto equal = EqualT{};
for (auto index = root; index != _capacity; ++index)
{
if (_slots[index] == hashed && equal(_data[index].first, key))
return const_iterator(_slots + index, reinterpret_cast<const_value_type*>(_data + index));
else if (_slots[index] == kEmpty)
return end();
}
for (auto index = 0; index != root; ++index)
{
if (_slots[index] == hashed && equal(_data[index].first, key))
return const_iterator(_slots + index, reinterpret_cast<const_value_type*>(_data + index));
else if (_slots[index] == kEmpty)
return end();
}
return end();
}
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT>
auto stlx::hash_map<KeyT, MappedT, HashT, EqualT, AllocatorT>::erase(iterator it) -> iterator
{
if (it != end())
{
auto const index = it._slot - _slots;
_slots[index] = kTombstone;
_data[index].~value_type();
--_size;
return iterator(_slots + index, _data + index);
}
else
{
return end();
}
}
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT>
template <typename SearchT>
auto stlx::hash_map<KeyT, MappedT, HashT, EqualT, AllocatorT>::erase(SearchT const& key) -> size_type
{
auto const it = find(key);
size_type const count = it != end();
erase(it);
return count;
}
template <typename KeyT, typename MappedT, typename HashT, typename EqualT, typename AllocatorT>
void stlx::hash_map<KeyT, MappedT, HashT, EqualT, AllocatorT>::_resize_slots(size_type capacity)
{
slot_type* slots = (slot_type*)this->allocate(capacity * sizeof(slot_type), alignof(slot_type));
value_type* data = (value_type*)this->allocate(capacity * sizeof(value_type), alignof(value_type));
std::memset(slots, 0, capacity * sizeof(slot_type));
for (auto index = 0; index != _capacity; ++index)
{
if ((_slots[index] & kLiveMask) != 0)
{
auto const root = _slots[index] % capacity;
auto new_index = root;
for (; new_index != _capacity; ++new_index)
if ((slots[new_index] & kLiveMask) == 0)
break;
if (new_index == _capacity)
for (new_index = 0; new_index != root; ++new_index)
if ((slots[new_index] & kLiveMask) == 0)
break;
slots[new_index] = _slots[index];
new (data + new_index) value_type(std::move(_data[index]));
}
}
this->deallocate(_slots, _capacity * sizeof(slot_type), alignof(slot_type));
this->deallocate(_data, _capacity * sizeof(value_type), alignof(value_type));
_slots = slots;
_data = data;
_capacity = capacity;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment