frozen/unordered_map.h
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Frozen | ||
| 3 | * Copyright 2016 QuarksLab | ||
| 4 | * | ||
| 5 | * Licensed to the Apache Software Foundation (ASF) under one | ||
| 6 | * or more contributor license agreements. See the NOTICE file | ||
| 7 | * distributed with this work for additional information | ||
| 8 | * regarding copyright ownership. The ASF licenses this file | ||
| 9 | * to you under the Apache License, Version 2.0 (the | ||
| 10 | * "License"); you may not use this file except in compliance | ||
| 11 | * with the License. You may obtain a copy of the License at | ||
| 12 | * | ||
| 13 | * http://www.apache.org/licenses/LICENSE-2.0 | ||
| 14 | * | ||
| 15 | * Unless required by applicable law or agreed to in writing, | ||
| 16 | * software distributed under the License is distributed on an | ||
| 17 | * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY | ||
| 18 | * KIND, either express or implied. See the License for the | ||
| 19 | * specific language governing permissions and limitations | ||
| 20 | * under the License. | ||
| 21 | */ | ||
| 22 | |||
| 23 | #ifndef FROZEN_LETITGO_UNORDERED_MAP_H | ||
| 24 | #define FROZEN_LETITGO_UNORDERED_MAP_H | ||
| 25 | |||
| 26 | #include "frozen/bits/basic_types.h" | ||
| 27 | #include "frozen/bits/elsa.h" | ||
| 28 | #include "frozen/bits/exceptions.h" | ||
| 29 | #include "frozen/bits/pmh.h" | ||
| 30 | #include "frozen/bits/version.h" | ||
| 31 | #include "frozen/random.h" | ||
| 32 | |||
| 33 | #include <tuple> | ||
| 34 | #include <functional> | ||
| 35 | #include <utility> | ||
| 36 | |||
| 37 | namespace frozen { | ||
| 38 | |||
| 39 | namespace bits { | ||
| 40 | |||
| 41 | struct GetKey { | ||
| 42 | template <class KV> constexpr auto const &operator()(KV const &kv) const { | ||
| 43 | return kv.first; | ||
| 44 | } | ||
| 45 | }; | ||
| 46 | |||
| 47 | } // namespace bits | ||
| 48 | |||
| 49 | template <class Key, class Value, std::size_t N, typename Hash = anna<Key>, | ||
| 50 | class KeyEqual = std::equal_to<Key>> | ||
| 51 | class unordered_map : private KeyEqual { | ||
| 52 | static constexpr std::size_t storage_size = | ||
| 53 | bits::next_highest_power_of_two(N) * (N < 32 ? 2 : 1); // size adjustment to prevent high collision rate for small sets | ||
| 54 | using container_type = bits::carray<std::pair<const Key, Value>, N>; | ||
| 55 | using tables_type = bits::pmh_tables<storage_size, Hash>; | ||
| 56 | |||
| 57 | container_type items_; | ||
| 58 | tables_type tables_; | ||
| 59 | |||
| 60 | public: | ||
| 61 | /* typedefs */ | ||
| 62 | using Self = unordered_map<Key, Value, N, Hash, KeyEqual>; | ||
| 63 | using key_type = Key; | ||
| 64 | using mapped_type = Value; | ||
| 65 | using value_type = typename container_type::value_type; | ||
| 66 | using size_type = typename container_type::size_type; | ||
| 67 | using difference_type = typename container_type::difference_type; | ||
| 68 | using hasher = Hash; | ||
| 69 | using key_equal = KeyEqual; | ||
| 70 | using reference = typename container_type::reference; | ||
| 71 | using const_reference = typename container_type::const_reference; | ||
| 72 | using pointer = typename container_type::pointer; | ||
| 73 | using const_pointer = typename container_type::const_pointer; | ||
| 74 | using iterator = typename container_type::iterator; | ||
| 75 | using const_iterator = typename container_type::const_iterator; | ||
| 76 | |||
| 77 | public: | ||
| 78 | /* constructors */ | ||
| 79 | unordered_map(unordered_map const &) = default; | ||
| 80 | constexpr unordered_map(container_type items, | ||
| 81 | Hash const &hash, KeyEqual const &equal) | ||
| 82 | : KeyEqual{equal} | ||
| 83 | , items_{items} | ||
| 84 | , tables_{ | ||
| 85 | bits::make_pmh_tables<storage_size>( | ||
| 86 | items_, hash, equal, bits::GetKey{}, default_prg_t{})} {} | ||
| 87 | explicit constexpr unordered_map(container_type items) | ||
| 88 | : unordered_map{items, Hash{}, KeyEqual{}} { | ||
| 89 | } | ||
| 90 | |||
| 91 | constexpr unordered_map(std::initializer_list<value_type> items, | ||
| 92 | Hash const & hash, KeyEqual const & equal) | ||
| 93 | : unordered_map{container_type{items}, hash, equal} { | ||
| 94 | } | ||
| 95 | |||
| 96 | constexpr unordered_map(std::initializer_list<value_type> items) | ||
| 97 | : unordered_map{items, Hash{}, KeyEqual{}} {} | ||
| 98 | |||
| 99 | /* iterators */ | ||
| 100 | constexpr iterator begin() { return items_.begin(); } | ||
| 101 | constexpr iterator end() { return items_.end(); } | ||
| 102 | constexpr const_iterator begin() const { return items_.begin(); } | ||
| 103 | 88443 | constexpr const_iterator end() const { return items_.end(); } | |
| 104 | constexpr const_iterator cbegin() const { return items_.begin(); } | ||
| 105 | constexpr const_iterator cend() const { return items_.end(); } | ||
| 106 | |||
| 107 | /* capacity */ | ||
| 108 | constexpr bool empty() const { return !N; } | ||
| 109 | constexpr size_type size() const { return N; } | ||
| 110 | constexpr size_type max_size() const { return N; } | ||
| 111 | |||
| 112 | /* lookup */ | ||
| 113 | template <class KeyType> | ||
| 114 | constexpr std::size_t count(KeyType const &key) const { | ||
| 115 | return find(key) != end(); | ||
| 116 | } | ||
| 117 | |||
| 118 | template <class KeyType> | ||
| 119 | constexpr Value const &at(KeyType const &key) const { | ||
| 120 | return at_impl(*this, key); | ||
| 121 | } | ||
| 122 | template <class KeyType> | ||
| 123 | constexpr Value &at(KeyType const &key) { | ||
| 124 | return at_impl(*this, key); | ||
| 125 | } | ||
| 126 | |||
| 127 | template <class KeyType> | ||
| 128 | 88443 | constexpr const_iterator find(KeyType const &key) const { | |
| 129 | 88443 | return find_impl(*this, key, hash_function(), key_eq()); | |
| 130 | } | ||
| 131 | template <class KeyType> | ||
| 132 | constexpr iterator find(KeyType const &key) { | ||
| 133 | return find_impl(*this, key, hash_function(), key_eq()); | ||
| 134 | } | ||
| 135 | |||
| 136 | template <class KeyType> | ||
| 137 | constexpr bool contains(KeyType const &key) const { | ||
| 138 | return this->find(key) != this->end(); | ||
| 139 | } | ||
| 140 | |||
| 141 | template <class KeyType> | ||
| 142 | constexpr std::pair<const_iterator, const_iterator> equal_range(KeyType const &key) const { | ||
| 143 | return equal_range_impl(*this, key); | ||
| 144 | } | ||
| 145 | template <class KeyType> | ||
| 146 | constexpr std::pair<iterator, iterator> equal_range(KeyType const &key) { | ||
| 147 | return equal_range_impl(*this, key); | ||
| 148 | } | ||
| 149 | |||
| 150 | /* bucket interface */ | ||
| 151 | constexpr std::size_t bucket_count() const { return storage_size; } | ||
| 152 | constexpr std::size_t max_bucket_count() const { return storage_size; } | ||
| 153 | |||
| 154 | /* observers*/ | ||
| 155 | 88443 | constexpr const hasher& hash_function() const { return tables_.hash_function(); } | |
| 156 | 88443 | constexpr const key_equal& key_eq() const { return static_cast<KeyEqual const&>(*this); } | |
| 157 | |||
| 158 | private: | ||
| 159 | template <class This, class KeyType> | ||
| 160 | static inline constexpr auto& at_impl(This&& self, KeyType const &key) { | ||
| 161 | auto it = self.find(key); | ||
| 162 | if (it != self.end()) | ||
| 163 | return it->second; | ||
| 164 | else | ||
| 165 | FROZEN_THROW_OR_ABORT(std::out_of_range("unknown key")); | ||
| 166 | } | ||
| 167 | |||
| 168 | template <class This, class KeyType, class Hasher, class Equal> | ||
| 169 | 88443 | static inline constexpr auto find_impl(This&& self, KeyType const &key, Hasher const &hash, Equal const &equal) { | |
| 170 | 88443 | auto const pos = self.tables_.lookup(key, hash); | |
| 171 | 88443 | auto it = self.items_.begin() + pos; | |
| 172 | 88443 | if (it != self.items_.end() && equal(it->first, key)) | |
| 173 | 31187 | return it; | |
| 174 | else | ||
| 175 | 57256 | return self.items_.end(); | |
| 176 | } | ||
| 177 | |||
| 178 | template <class This, class KeyType> | ||
| 179 | static inline constexpr auto equal_range_impl(This&& self, KeyType const &key) { | ||
| 180 | auto const it = self.find(key); | ||
| 181 | if (it != self.end()) | ||
| 182 | return std::make_pair(it, it + 1); | ||
| 183 | else | ||
| 184 | return std::make_pair(self.end(), self.end()); | ||
| 185 | } | ||
| 186 | }; | ||
| 187 | |||
| 188 | template <typename T, typename U, std::size_t N> | ||
| 189 | constexpr auto make_unordered_map(std::pair<T, U> const (&items)[N]) { | ||
| 190 | return unordered_map<T, U, N>{items}; | ||
| 191 | } | ||
| 192 | |||
| 193 | template <typename T, typename U, std::size_t N, typename Hasher, typename Equal> | ||
| 194 | constexpr auto make_unordered_map( | ||
| 195 | std::pair<T, U> const (&items)[N], | ||
| 196 | Hasher const &hash = elsa<T>{}, | ||
| 197 | Equal const &equal = std::equal_to<T>{}) { | ||
| 198 | return unordered_map<T, U, N, Hasher, Equal>{items, hash, equal}; | ||
| 199 | } | ||
| 200 | |||
| 201 | template <typename T, typename U, std::size_t N> | ||
| 202 | constexpr auto make_unordered_map(std::array<std::pair<T, U>, N> const &items) { | ||
| 203 | return unordered_map<T, U, N>{items}; | ||
| 204 | } | ||
| 205 | |||
| 206 | template <typename T, typename U, std::size_t N, typename Hasher, typename Equal> | ||
| 207 | constexpr auto make_unordered_map( | ||
| 208 | std::array<std::pair<T, U>, N> const &items, | ||
| 209 | Hasher const &hash = elsa<T>{}, | ||
| 210 | Equal const &equal = std::equal_to<T>{}) { | ||
| 211 | return unordered_map<T, U, N, Hasher, Equal>{items, hash, equal}; | ||
| 212 | } | ||
| 213 | |||
| 214 | } // namespace frozen | ||
| 215 | |||
| 216 | #endif | ||
| 217 |