Debian Codegraph @

src/perfect-hashing/frozen/unordered_map.h

raw
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/constexpr_assert.h"
28 #include "frozen/bits/elsa.h"
29 #include "frozen/bits/exceptions.h"
30 #include "frozen/bits/pmh.h"
31 #include "frozen/bits/version.h"
32 #include "frozen/random.h"
33
34 #include <tuple>
35 #include <functional>
36
37 namespace frozen {
38
39 namespace bits {
40
41 struct GetKey {
42 template <class KV>
43 constexpr auto const &
44 operator()(KV const &kv) const {
45 return kv.first;
46 }
47 };
48
49 } // namespace bits
50
51 template <class Key, class Value, std::size_t N, typename Hash = anna<Key>, class KeyEqual = std::equal_to<Key>> class unordered_map {
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<Key, Value>, N>;
55 using tables_type = bits::pmh_tables<storage_size, Hash>;
56
57 KeyEqual const equal_;
58 container_type items_;
59 tables_type tables_;
60
61 public:
62 /* typedefs */
63 using Self = unordered_map<Key, Value, N, Hash, KeyEqual>;
64 using key_type = Key;
65 using mapped_type = Value;
66 using value_type = typename container_type::value_type;
67 using size_type = typename container_type::size_type;
68 using difference_type = typename container_type::difference_type;
69 using hasher = Hash;
70 using key_equal = KeyEqual;
71 using reference = typename container_type::reference;
72 using const_reference = typename container_type::const_reference;
73 using pointer = typename container_type::pointer;
74 using const_pointer = typename container_type::const_pointer;
75 using iterator = typename container_type::iterator;
76 using const_iterator = typename container_type::const_iterator;
77
78 public:
79 /* constructors */
80 unordered_map(unordered_map const &) = default;
81 constexpr unordered_map(container_type items, Hash const &hash, KeyEqual const &equal)
82 : equal_{equal}, items_{items}, tables_{bits::make_pmh_tables<storage_size>(items_, hash, bits::GetKey{}, default_prg_t{})} {}
83 explicit constexpr unordered_map(container_type items) : unordered_map{items, Hash{}, KeyEqual{}} {}
84
85 constexpr unordered_map(std::initializer_list<value_type> items, Hash const &hash, KeyEqual const &equal)
86 : unordered_map{container_type{items}, hash, equal} {
87 constexpr_assert(items.size() == N, "Inconsistent initializer_list size and type size argument");
88 }
89
90 constexpr unordered_map(std::initializer_list<value_type> items) : unordered_map{items, Hash{}, KeyEqual{}} {}
91
92 /* iterators */
93 constexpr iterator
94 begin() {
95 return items_.begin();
96 }
97 constexpr iterator
98 end() {
99 return items_.end();
100 }
101 constexpr const_iterator
102 begin() const {
103 return items_.begin();
104 }
105 constexpr const_iterator
106 end() const {
107 return items_.end();
108 }
109 constexpr const_iterator
110 cbegin() const {
111 return items_.cbegin();
112 }
113 constexpr const_iterator
114 cend() const {
115 return items_.cend();
116 }
117
118 /* capacity */
119 constexpr bool
120 empty() const {
121 return !N;
122 }
123 constexpr size_type
124 size() const {
125 return N;
126 }
127 constexpr size_type
128 max_size() const {
129 return N;
130 }
131
132 /* lookup */
133 constexpr std::size_t
134 count(Key const &key) const {
135 auto const &kv = lookup(key);
136 return equal_(kv.first, key);
137 }
138
139 constexpr Value const &
140 at(Key const &key) const {
141 return at_impl(*this, key);
142 }
143 constexpr Value &
144 at(Key const &key) {
145 return at_impl(*this, key);
146 }
147
148 constexpr const_iterator
149 find(Key const &key) const {
150 return find_impl(*this, key);
151 }
152 constexpr iterator
153 find(Key const &key) {
154 return find_impl(*this, key);
155 }
156
157 constexpr std::pair<const_iterator, const_iterator>
158 equal_range(Key const &key) const {
159 return equal_range_impl(*this, key);
160 }
161 constexpr std::pair<iterator, iterator>
162 equal_range(Key const &key) {
163 return equal_range_impl(*this, key);
164 }
165
166 /* bucket interface */
167 constexpr std::size_t
168 bucket_count() const {
169 return storage_size;
170 }
171 constexpr std::size_t
172 max_bucket_count() const {
173 return storage_size;
174 }
175
176 /* observers*/
177 constexpr hasher
178 hash_function() const {
179 return tables_.hash_;
180 }
181 constexpr key_equal
182 key_eq() const {
183 return equal_;
184 }
185
186 private:
187 template <class This>
188 static inline constexpr auto &
189 at_impl(This &&self, Key const &key) {
190 auto &kv = self.lookup(key);
191 if (self.equal_(kv.first, key)) return kv.second;
192 else FROZEN_THROW_OR_ABORT(std::out_of_range("unknown key"));
193 }
194
195 template <class This>
196 static inline constexpr auto
197 find_impl(This &&self, Key const &key) {
198 auto &kv = self.lookup(key);
199 if (self.equal_(kv.first, key)) return &kv;
200 else return self.items_.end();
201 }
202
203 template <class This>
204 static inline constexpr auto
205 equal_range_impl(This &&self, Key const &key) {
206 auto &kv = self.lookup(key);
207 using kv_ptr = decltype(&kv);
208 if (self.equal_(kv.first, key)) return std::pair<kv_ptr, kv_ptr>{&kv, &kv + 1};
209 else return std::pair<kv_ptr, kv_ptr>{self.items_.end(), self.items_.end()};
210 }
211
212 template <class This>
213 static inline constexpr auto &
214 lookup_impl(This &&self, Key const &key) {
215 return self.items_[self.tables_.lookup(key)];
216 }
217
218 constexpr auto const &
219 lookup(Key const &key) const {
220 return lookup_impl(*this, key);
221 }
222 constexpr auto &
223 lookup(Key const &key) {
224 return lookup_impl(*this, key);
225 }
226 };
227
228 template <typename T, typename U, std::size_t N>
229 constexpr auto
230 make_unordered_map(std::pair<T, U> const (&items)[N]) {
231 return unordered_map<T, U, N>{items};
232 }
233
234 template <typename T, typename U, std::size_t N>
235 constexpr auto
236 make_unordered_map(std::array<std::pair<T, U>, N> const &items) {
237 return unordered_map<T, U, N>{items};
238 }
239
240 } // namespace frozen
241
242 #endif