MMappedUUIDHashTable.cpp

Go to the documentation of this file.

/**
 * @file MMappedUUIDHashTable.cpp
 * @brief Open-addressing hash table over a memory-mapped file: implementation.
 *
 * Implements all methods of @c MMappedUUIDHashTable declared in
 * @c MMappedUUIDHashTable.h:
 * - @c MMappedUUIDHashTable(): open/create the backing file and map it.
 * - @c ~MMappedUUIDHashTable(): sync and unmap.
 * - @c add(): insert a UUID and assign the next sequential integer.
 * - @c operator[](): look up an integer by UUID.
 * - @c sync(): flush the backing region (@c MappedRegion::sync()).
 *
 * Internal helpers:
 * - @c grow(): double the table size and rehash.
 * - @c find(): locate the slot index for a UUID (or @c NOTHING if absent).
 * - @c set(): write a key-value pair into the table.
 */
#include "MMappedUUIDHashTable.h"
 
#include <cassert>
#include <cerrno>
#include <cstdint>
#include <cstring>
#include <new>
#include <stdexcept>
#include <string>
#include <vector>
 
#include <fcntl.h>
#include <unistd.h>
 
#include <sys/mman.h>
 
MMappedUUIDHashTable::MMappedUUIDHashTable(const char *filename, bool read_only, uint64_t magic_value)
{
  auto size = region.openFile(filename, read_only);
  bool empty = (size == 0);
 
  if(empty) {
    size = table_t::sizeForLogSize(STARTING_LOG_SIZE);
    region.resizeFile(size);
  }
 
  region.map(size);
  table = reinterpret_cast<table_t *>(region.base());
 
  if(empty) {
    table->magic     = magic_value;
    table->version   = 1;
    table->elem_size = static_cast<uint16_t>(sizeof(value_t));
    table->_reserved = 0;
    table->log_size = table_t::logSizeForSize(size);
    table->nb_elements = 0;
    table->next_value = 0;
    for(unsigned long i=0; i<table->capacity(); ++i) {
      table->t[i].value = NOTHING;
    }
  } else {
    if(table->magic != magic_value)
      throw std::runtime_error("ProvSQL mmap: wrong file type (magic mismatch)");
    if(table->version != 1)
      throw std::runtime_error("ProvSQL mmap: unsupported format version "
                               + std::to_string(table->version));
    if(table->elem_size != sizeof(value_t))
      throw std::runtime_error("ProvSQL mmap: element size mismatch (recompile required)");
  }
}
 
void MMappedUUIDHashTable::grow()
{
  std::vector<value_t> elements;
  elements.reserve(table->nb_elements);
  for(unsigned long i=0; i<table->capacity(); ++i)
    if(table->t[i].value != NOTHING)
      elements.push_back(table->t[i]);
 
  auto new_log_size = table->log_size+1;
  region.remap(table_t::sizeForLogSize(new_log_size));
  table = reinterpret_cast<table_t *>(region.base());
 
  table->log_size = new_log_size;
  for(unsigned long i=0; i<table->capacity(); ++i) {
    table->t[i].value = NOTHING;
  }
  for(const auto &u: elements)
    set(u.uuid, u.value);
}
 
MMappedUUIDHashTable::~MMappedUUIDHashTable()
{
  region.close();
}
 
unsigned long MMappedUUIDHashTable::find(pg_uuid_t u) const
{
  auto k = hash(u);
  while(table->t[k].value != NOTHING &&
        std::memcmp(&table->t[k].uuid, &u, sizeof(pg_uuid_t))) {
    k = (k+1) % table->capacity();
  }
 
  return k;
}
 
unsigned long MMappedUUIDHashTable::operator[](pg_uuid_t u) const
{
  auto k = find(u);
 
  return table->t[k].value;
}
 
std::pair<unsigned long,bool> MMappedUUIDHashTable::add(pg_uuid_t u)
{
  auto k = find(u);
 
  if(table->t[k].value == NOTHING) {
    if(table->nb_elements >= MAXIMUM_LOAD_FACTOR * table->capacity()) {
      grow();
    }
    k = find(u);
    ++table->nb_elements;
    table->t[k].uuid = u;
    return std::make_pair(table->t[k].value = table->next_value++, true);
  } else
    return std::make_pair(table->t[k].value, false);
}
 
// Only used when growing the table, so no need to check/update nb_elements
void MMappedUUIDHashTable::set(pg_uuid_t u, unsigned long i)
{
  table->t[find(u)] = {u, i};
}
 
void MMappedUUIDHashTable::sync()
{
  region.sync();
}