Debian Codegraph @

src/perfect-hashing/frozen/unordered_set.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_SET_H
24 #define FROZEN_LETITGO_UNORDERED_SET_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/pmh.h"
30 #include "frozen/bits/version.h"
31 #include "frozen/random.h"
32
33 #include <utility>
34
35 namespace frozen {
36
37 namespace bits {
38
39 struct Get {
40 template <class T>
41 constexpr T const &
42 operator()(T const &key) const {
43 return key;
44 }
45 };
46
47 } // namespace bits
48
49 template <class Key, std::size_t N, typename Hash = elsa<Key>, class KeyEqual = std::equal_to<Key>> class unordered_set {
50 static constexpr std::size_t storage_size =
51 bits::next_highest_power_of_two(N) * (N < 32 ? 2 : 1); // size adjustment to prevent high collision rate for small sets
52 using container_type = bits::carray<Key, N>;
53 using tables_type = bits::pmh_tables<storage_size, Hash>;
54
55 KeyEqual const equal_;
56 container_type keys_;
57 tables_type tables_;
58
59 public:
60 /* typedefs */
61 using key_type = Key;
62 using value_type = Key;
63 using size_type = typename container_type::size_type;
64 using difference_type = typename container_type::difference_type;
65 using hasher = Hash;
66 using key_equal = KeyEqual;
67 using const_reference = typename container_type::const_reference;
68 using reference = const_reference;
69 using const_pointer = typename container_type::const_pointer;
70 using pointer = const_pointer;
71 using const_iterator = const_pointer;
72 using iterator = const_iterator;
73
74 public:
75 /* constructors */
76 unordered_set(unordered_set const &) = default;
77 constexpr unordered_set(container_type keys, Hash const &hash, KeyEqual const &equal)
78 : equal_{equal}, keys_{keys}, tables_{bits::make_pmh_tables<storage_size>(keys_, hash, bits::Get{}, default_prg_t{})} {}
79 explicit constexpr unordered_set(container_type keys) : unordered_set{keys, Hash{}, KeyEqual{}} {}
80
81 constexpr unordered_set(std::initializer_list<Key> keys) : unordered_set{keys, Hash{}, KeyEqual{}} {}
82
83 constexpr unordered_set(std::initializer_list<Key> keys, Hash const &hash, KeyEqual const &equal) : unordered_set{container_type{keys}, hash, equal} {
84 constexpr_assert(keys.size() == N, "Inconsistent initializer_list size and type size argument");
85 }
86
87 /* iterators */
88 constexpr const_iterator
89 begin() const {
90 return keys_.begin();
91 }
92 constexpr const_iterator
93 end() const {
94 return keys_.end();
95 }
96 constexpr const_iterator
97 cbegin() const {
98 return keys_.cbegin();
99 }
100 constexpr const_iterator
101 cend() const {
102 return keys_.cend();
103 }
104
105 /* capacity */
106 constexpr bool
107 empty() const {
108 return !N;
109 }
110 constexpr size_type
111 size() const {
112 return N;
113 }
114 constexpr size_type
115 max_size() const {
116 return N;
117 }
118
119 /* lookup */
120 constexpr std::size_t
121 count(Key const &key) const {
122 auto const k = lookup(key);
123 return equal_(k, key);
124 }
125 constexpr const_iterator
126 find(Key const &key) const {
127 auto const &k = lookup(key);
128 if (equal_(k, key)) return &k;
129 else return keys_.end();
130 }
131
132 constexpr std::pair<const_iterator, const_iterator>
133 equal_range(Key const &key) const {
134 auto const &k = lookup(key);
135 if (equal_(k, key)) return {&k, &k + 1};
136 else return {keys_.end(), keys_.end()};
137 }
138
139 /* bucket interface */
140 constexpr std::size_t
141 bucket_count() const {
142 return storage_size;
143 }
144 constexpr std::size_t
145 max_bucket_count() const {
146 return storage_size;
147 }
148
149 /* observers*/
150 constexpr hasher
151 hash_function() const {
152 return tables_.hash_;
153 }
154 constexpr key_equal
155 key_eq() const {
156 return equal_;
157 }
158
159 private:
160 constexpr auto const &
161 lookup(Key const &key) const {
162 return keys_[tables_.lookup(key)];
163 }
164 };
165
166 template <typename T, std::size_t N>
167 constexpr auto
168 make_unordered_set(T const (&keys)[N]) {
169 return unordered_set<T, N>{keys};
170 }
171
172 template <typename T, std::size_t N>
173 constexpr auto
174 make_unordered_set(std::array<T, N> const &keys) {
175 return unordered_set<T, N>{keys};
176 }
177
178 } // namespace frozen
179
180 #endif