Debian Codegraph @

src/perfect-hashing/frozen/bits/pmh.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 // inspired from http://stevehanov.ca/blog/index.php?id=119
24 #ifndef FROZEN_LETITGO_PMH_H
25 #define FROZEN_LETITGO_PMH_H
26
27 #include "frozen/bits/algorithms.h"
28 #include "frozen/bits/basic_types.h"
29
30 #include <array>
31 #include <limits>
32
33 namespace frozen {
34
35 namespace bits {
36
37 // Function object for sorting buckets in decreasing order of size
38 struct bucket_size_compare {
39 template <typename B>
40 bool constexpr
41 operator()(B const &b0, B const &b1) const {
42 return b0.size() > b1.size();
43 }
44 };
45
46 // Step One in pmh routine is to take all items and hash them into buckets,
47 // with some collisions. Then process those buckets further to build a perfect
48 // hash function.
49 // pmh_buckets represents the initial placement into buckets.
50
51 template <size_t M> struct pmh_buckets {
52 // Step 0: Bucket max is 2 * sqrt M
53 // TODO: Come up with justification for this, should it not be O(log M)?
54 static constexpr auto bucket_max = 2 * (1u << (log(M) / 2));
55
56 using bucket_t = cvector<std::size_t, bucket_max>;
57 carray<bucket_t, M> buckets;
58 uint64_t seed;
59
60 // Represents a reference to a bucket. This is used because the buckets
61 // have to be sorted, but buckets are big, making it slower than sorting refs
62 struct bucket_ref {
63 unsigned hash;
64 const bucket_t *ptr;
65
66 // Forward some interface of bucket
67 using value_type = typename bucket_t::value_type;
68 using const_iterator = typename bucket_t::const_iterator;
69
70 constexpr auto
71 size() const {
72 return ptr->size();
73 }
74 constexpr const auto &
75 operator[](std::size_t idx) const {
76 return (*ptr)[idx];
77 }
78 constexpr auto
79 begin() const {
80 return ptr->begin();
81 }
82 constexpr auto
83 end() const {
84 return ptr->end();
85 }
86 };
87
88 // Make a bucket_ref for each bucket
89 template <std::size_t... Is> carray<bucket_ref, M> constexpr make_bucket_refs(std::index_sequence<Is...>) const {
90 return {{bucket_ref{Is, &buckets[Is]}...}};
91 }
92
93 // Makes a bucket_ref for each bucket and sorts them by size
94 carray<bucket_ref, M> constexpr get_sorted_buckets() const {
95 carray<bucket_ref, M> result{this->make_bucket_refs(std::make_index_sequence<M>())};
96 bits::quicksort(result.begin(), result.end() - 1, bucket_size_compare{});
97 return result;
98 }
99 };
100
101 template <size_t M, class Item, size_t N, class Hash, class Key, class PRG>
102 pmh_buckets<M> constexpr make_pmh_buckets(const carray<Item, N> &items, Hash const &hash, Key const &key, PRG &prg) {
103 using result_t = pmh_buckets<M>;
104 result_t result{};
105 bool rejected = false;
106 // Continue until all items are placed without exceeding bucket_max
107 while (1) {
108 for (auto &b : result.buckets) { b.clear(); }
109 result.seed = prg();
110 rejected = false;
111 for (std::size_t i = 0; i < N; ++i) {
112 auto &bucket = result.buckets[hash(key(items[i]), static_cast<size_t>(result.seed)) % M];
113 if (bucket.size() >= result_t::bucket_max) {
114 rejected = true;
115 break;
116 }
117 bucket.push_back(i);
118 }
119 if (!rejected) { return result; }
120 }
121 }
122
123 // Check if an item appears in a cvector
124 template <class T, size_t N>
125 constexpr bool
126 all_different_from(cvector<T, N> &data, T &a) {
127 for (std::size_t i = 0; i < data.size(); ++i)
128 if (data[i] == a) return false;
129
130 return true;
131 }
132
133 // Represents either an index to a data item array, or a seed to be used with
134 // a hasher. Seed must have high bit of 1, value has high bit of zero.
135 struct seed_or_index {
136 using value_type = uint64_t;
137
138 private:
139 static constexpr value_type MINUS_ONE = std::numeric_limits<value_type>::max();
140 static constexpr value_type HIGH_BIT = ~(MINUS_ONE >> 1);
141
142 value_type value_ = 0;
143
144 public:
145 constexpr value_type
146 value() const {
147 return value_;
148 }
149 constexpr bool
150 is_seed() const {
151 return value_ & HIGH_BIT;
152 }
153
154 constexpr seed_or_index(bool is_seed, value_type value) : value_(is_seed ? (value | HIGH_BIT) : (value & ~HIGH_BIT)) {}
155
156 constexpr seed_or_index() = default;
157 constexpr seed_or_index(const seed_or_index &) = default;
158 constexpr seed_or_index &operator=(const seed_or_index &) = default;
159 };
160
161 // Represents the perfect hash function created by pmh algorithm
162 template <std::size_t M, class Hasher> struct pmh_tables {
163 uint64_t first_seed_;
164 carray<seed_or_index, M> first_table_;
165 carray<std::size_t, M> second_table_;
166 Hasher hash_;
167
168 // Looks up a given key, to find its expected index in carray<Item, N>
169 // Always returns a valid index, must use KeyEqual test after to confirm.
170 template <typename KeyType>
171 constexpr std::size_t
172 lookup(const KeyType &key) const {
173 auto const d = first_table_[hash_(key, static_cast<size_t>(first_seed_)) % M];
174 if (!d.is_seed()) {
175 return static_cast<std::size_t>(d.value());
176 } // this is narrowing uint64 -> size_t but should be fine
177 else {
178 return second_table_[hash_(key, static_cast<std::size_t>(d.value())) % M];
179 }
180 }
181 };
182
183 // Make pmh tables for given items, hash function, prg, etc.
184 template <std::size_t M, class Item, std::size_t N, class Hash, class Key, class PRG>
185 pmh_tables<M, Hash> constexpr make_pmh_tables(const carray<Item, N> &items, Hash const &hash, Key const &key, PRG prg) {
186 // Step 1: Place all of the keys into buckets
187 auto step_one = make_pmh_buckets<M>(items, hash, key, prg);
188
189 // Step 2: Sort the buckets to process the ones with the most items first.
190 auto buckets = step_one.get_sorted_buckets();
191
192 // G becomes the first hash table in the resulting pmh function
193 carray<seed_or_index, M> G; // Default constructed to "index 0"
194
195 // H becomes the second hash table in the resulting pmh function
196 constexpr std::size_t UNUSED = std::numeric_limits<std::size_t>::max();
197 carray<std::size_t, M> H;
198 H.fill(UNUSED);
199
200 // Step 3: Map the items in buckets into hash tables.
201 for (const auto &bucket : buckets) {
202 auto const bsize = bucket.size();
203
204 if (bsize == 1) {
205 // Store index to the (single) item in G
206 // assert(bucket.hash == hash(key(items[bucket[0]]), step_one.seed) % M);
207 G[bucket.hash] = {false, static_cast<uint64_t>(bucket[0])};
208 } else if (bsize > 1) {
209 // Repeatedly try different H of d until we find a hash function
210 // that places all items in the bucket into free slots
211 seed_or_index d{true, prg()};
212 cvector<std::size_t, decltype(step_one)::bucket_max> bucket_slots;
213
214 while (bucket_slots.size() < bsize) {
215 auto slot = hash(key(items[bucket[bucket_slots.size()]]), static_cast<size_t>(d.value())) % M;
216
217 if (H[slot] != UNUSED || !all_different_from(bucket_slots, slot)) {
218 bucket_slots.clear();
219 d = {true, prg()};
220 continue;
221 }
222
223 bucket_slots.push_back(slot);
224 }
225
226 // Put successful seed in G, and put indices to items in their slots
227 // assert(bucket.hash == hash(key(items[bucket[0]]), step_one.seed) % M);
228 G[bucket.hash] = d;
229 for (std::size_t i = 0; i < bsize; ++i) H[bucket_slots[i]] = bucket[i];
230 }
231 }
232
233 // Any unused entries in the H table have to get changed to zero.
234 // This is because hashing should not fail or return an out-of-bounds entry.
235 // A lookup fails after we apply user-supplied KeyEqual to the query and the
236 // key found by hashing. Sending such queries to zero cannot hurt.
237 for (std::size_t i = 0; i < M; ++i)
238 if (H[i] == UNUSED) H[i] = 0;
239
240 return {step_one.seed, G, H, hash};
241 }
242
243 } // namespace bits
244
245 } // namespace frozen
246
247 #endif