ef_sequence_view.h

Go to the documentation of this file.

 
#ifndef GRAPHSCOPE_PTHASH_UTILS_EF_SEQUENCE_VIEW_VIEW_H_
#define GRAPHSCOPE_PTHASH_UTILS_EF_SEQUENCE_VIEW_VIEW_H_
 
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
 
#include <type_traits>
 
#ifdef USE_PTHASH
#include "encoders/util.hpp"
 
namespace gs {
 
template <typename T>
struct ref_vector {
 static_assert(std::is_pod<T>::value, "T must be POD type");
 ref_vector() : buffer_(nullptr), size_(0) {}
 ~ref_vector() {}
 
 void init(const T* buffer, size_t size) {
 buffer_ = buffer;
 size_ = size;
 }
 
 const T* data() const { return buffer_; }
 const T& operator[](size_t idx) const { return buffer_[idx]; }
 
 const T* buffer_;
 size_t size_;
};
 
// This code is an adaptation from
// https://github.com/jermp/pthash/blob/master/include/encoders/bit_vector.hpp
struct bit_vector_view {
 const uint64_t* data() const { return m_bits.data(); }
 
 template <typename Visitor>
 void visit(Visitor& visitor) {
 visitor.visit(m_size);
 visitor.visit_vec(m_bits);
 }
 
 size_t m_size;
 ref_vector<uint64_t> m_bits;
};
 
// This code is an adaptation from
// https://github.com/jermp/pthash/blob/master/include/encoders/darray.hpp
struct darray1_view {
 inline uint64_t select(const bit_vector_view& bv, uint64_t idx) const {
 assert(idx < m_positions);
 uint64_t block = idx / block_size;
 int64_t block_pos = m_block_inventory[block];
 if (block_pos < 0) { // sparse super-block
 uint64_t overflow_pos = uint64_t(-block_pos - 1);
 return m_overflow_positions[overflow_pos + (idx & (block_size - 1))];
 }
 
 size_t subblock = idx / subblock_size;
 size_t start_pos = uint64_t(block_pos) + m_subblock_inventory[subblock];
 size_t reminder = idx & (subblock_size - 1);
 if (!reminder) {
 return start_pos;
 }
 
 const uint64_t* data = bv.data();
 size_t word_idx = start_pos >> 6;
 size_t word_shift = start_pos & 63;
 uint64_t word = data[word_idx] & (uint64_t(-1) << word_shift);
 
 while (true) {
 size_t popcnt = pthash::util::popcount(word);
 if (reminder < popcnt) {
 break;
 }
 reminder -= popcnt;
 word = data[++word_idx];
 }
 
 return (word_idx << 6) + pthash::util::select_in_word(word, reminder);
 }
 
 template <typename Visitor>
 void visit(Visitor& visitor) {
 visitor.visit(m_positions);
 visitor.visit_vec(m_block_inventory);
 visitor.visit_vec(m_subblock_inventory);
 visitor.visit_vec(m_overflow_positions);
 }
 
 static const size_t block_size = 1024; // 2048
 static const size_t subblock_size = 32;
 static const size_t max_in_block_distance = 1 << 16;
 
 size_t m_positions;
 ref_vector<int64_t> m_block_inventory;
 ref_vector<uint16_t> m_subblock_inventory;
 ref_vector<uint64_t> m_overflow_positions;
};
 
// This code is an adaptation from
// https://github.com/jermp/pthash/blob/master/include/encoders/compact_vector.hpp
struct compact_vector_view {
 inline uint64_t size() const { return m_size; }
 inline uint64_t width() const { return m_width; }
 inline uint64_t access(uint64_t pos) const {
 assert(pos < size());
 uint64_t i = pos * m_width;
 const char* ptr = reinterpret_cast<const char*>(m_bits.data());
 return (*(reinterpret_cast<uint64_t const*>(ptr + (i >> 3))) >> (i & 7)) &
 m_mask;
 }
 
 template <typename Visitor>
 void visit(Visitor& visitor) {
 visitor.visit(m_size);
 visitor.visit(m_width);
 visitor.visit(m_mask);
 visitor.visit_vec(m_bits);
 }
 
 uint64_t m_size;
 uint64_t m_width;
 uint64_t m_mask;
 ref_vector<uint64_t> m_bits;
};
 
// This code is an adaptation from
// https://github.com/jermp/pthash/blob/master/include/encoders/ef_sequence.hpp
struct ef_sequence_view {
 uint64_t access(uint64_t i) const {
 assert(i < m_low_bits.size());
 return ((m_high_bits_d1.select(m_high_bits, i) - i) << m_low_bits.width()) |
 m_low_bits.access(i);
 }
 
 template <typename Visitor>
 void visit(Visitor& visitor) {
 visitor.visit(m_high_bits);
 visitor.visit(m_high_bits_d1);
 visitor.visit(m_low_bits);
 }
 
 bit_vector_view m_high_bits;
 darray1_view m_high_bits_d1;
 compact_vector_view m_low_bits;
};
 
} // namespace gs
 
#endif // USE_PTHASH
 
#endif // GRAPHSCOPE_PTHASH_UTILS_EF_SEQUENCE_VIEW_VIEW_H_