| 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 |