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_