Program Listing for File approx_hash_array.h¶
↰ Return to documentation for file (voxblox/include/voxblox/utils/approx_hash_array.h
)
#ifndef VOXBLOX_UTILS_APPROX_HASH_ARRAY_H_
#define VOXBLOX_UTILS_APPROX_HASH_ARRAY_H_
#include <atomic>
#include <limits>
#include <vector>
#include "voxblox/core/common.h"
namespace voxblox {
template <size_t unmasked_bits, typename StoredElement, typename IndexType,
typename IndexTypeHasher>
class ApproxHashArray {
public:
EIGEN_MAKE_ALIGNED_OPERATOR_NEW
StoredElement& get(const size_t& hash) {
return pseudo_map_[hash & bit_mask_];
}
StoredElement& get(const IndexType& index, size_t* hash) {
DCHECK(hash);
*hash = hasher_(index);
return get(*hash);
}
StoredElement& get(const IndexType& index) {
size_t hash = hasher_(index);
return get(hash);
}
private:
static constexpr size_t pseudo_map_size_ = (1 << unmasked_bits);
static constexpr size_t bit_mask_ = (1 << unmasked_bits) - 1;
std::array<StoredElement, pseudo_map_size_> pseudo_map_;
IndexTypeHasher hasher_;
};
template <size_t unmasked_bits, size_t full_reset_threshold, typename IndexType,
typename IndexTypeHasher>
class ApproxHashSet {
public:
EIGEN_MAKE_ALIGNED_OPERATOR_NEW
ApproxHashSet() : offset_(0), pseudo_set_(pseudo_set_size_) {
for (std::atomic<size_t>& value : pseudo_set_) {
value.store(0, std::memory_order_relaxed);
}
// The array used for storing values is initialized with zeros. However, the
// zeroth bin can actually store the 0 hash. Because of this to prevent a
// false positive on looking up a 0 hash this bin needs to initially store a
// different value.
pseudo_set_[offset_].store(std::numeric_limits<size_t>::max());
}
inline bool isHashCurrentlyPresent(const size_t& hash) {
const size_t array_index = (hash & bit_mask_) + offset_;
return (pseudo_set_[array_index].load(std::memory_order_relaxed) == hash);
}
inline bool isHashCurrentlyPresent(const IndexType& index, size_t* hash) {
DCHECK(hash);
*hash = hasher_(index);
return isHashCurrentlyPresent(*hash);
}
inline bool isHashCurrentlyPresent(const IndexType& index) {
size_t hash = hasher_(index);
return isHashCurrentlyPresent(hash);
}
inline bool replaceHash(const size_t& hash) {
const size_t array_index = (hash & bit_mask_) + offset_;
if (pseudo_set_[array_index].load(std::memory_order_relaxed) == hash) {
return false;
} else {
pseudo_set_[array_index].store(hash, std::memory_order_relaxed);
return true;
}
}
inline bool replaceHash(const IndexType& index, size_t* hash) {
DCHECK(hash);
*hash = hasher_(index);
return replaceHash(*hash);
}
inline bool replaceHash(const IndexType& index) {
const size_t hash = hasher_(index);
return replaceHash(hash);
}
void resetApproxSet() {
if (++offset_ >= full_reset_threshold) {
for (std::atomic<size_t>& value : pseudo_set_) {
value.store(0, std::memory_order_relaxed);
}
offset_ = 0;
// The array used for storing values is initialized with zeros. However,
// the zeroth bin can actually store the 0 hash. Because of this to
// prevent a false positive on looking up a 0 hash this bin needs to
// initially store a different value.
pseudo_set_[offset_].store(std::numeric_limits<size_t>::max());
}
}
private:
static constexpr size_t pseudo_set_size_ =
(1 << unmasked_bits) + full_reset_threshold;
static constexpr size_t bit_mask_ = (1 << unmasked_bits) - 1;
size_t offset_;
std::vector<std::atomic<size_t>> pseudo_set_;
IndexTypeHasher hasher_;
};
} // namespace voxblox
#endif // VOXBLOX_UTILS_APPROX_HASH_ARRAY_H_