short_value_optimized_storage.h

Go to the documentation of this file.

#ifndef gamgee__short_value_optimized_storage__guard
#define gamgee__short_value_optimized_storage__guard

#include "utils.h"

#include <vector>
#include <utility>
#include <cstring>
#include <stdexcept>

namespace gamgee {
namespace utils {

template<class ELEMENT_TYPE>
class ShortValueOptimizedStorage {
 public:
  ShortValueOptimizedStorage(const uint32_t capacity, const uint32_t short_value_upper_bound) :
    m_num_values { 0 },
    m_max_value_length { 0 },
    m_short_value_upper_bound { short_value_upper_bound },
    m_values(capacity),
    m_contiguous_storage(capacity * short_value_upper_bound)
  {
    if ( short_value_upper_bound == 0 ) {
      throw std::invalid_argument{"short value upper bound must be > 0"};
    }

    for ( auto i = 0u; i < m_values.size(); ++i ) {
      m_values[i].first = nullptr;
      m_values[i].second = 0u;
    }
  }

  ~ShortValueOptimizedStorage() {
    // Custom destructor because we have conditional deletion of values in the container
    clear();
  }

  // Moveable but not copyable
  ShortValueOptimizedStorage(ShortValueOptimizedStorage&& other) = default;
  ShortValueOptimizedStorage& operator=(ShortValueOptimizedStorage&& other) = default;
  ShortValueOptimizedStorage(const ShortValueOptimizedStorage& other) = delete;
  ShortValueOptimizedStorage& operator=(const ShortValueOptimizedStorage& other) = delete;

  uint32_t num_values() const { return m_num_values; }

  uint32_t capacity() const { return m_values.size(); }

  uint32_t max_value_length() const { return m_max_value_length; }

  uint32_t value_length(const uint32_t index) const {
    check_max_boundary(index, capacity());
    return m_values[index].second;
  }

  bool is_set(const uint32_t index) const {
    return index < capacity() && m_values[index].first != nullptr;
  }

  std::pair<ELEMENT_TYPE*,uint32_t> get(const uint32_t index) const {
    check_max_boundary(index, capacity());
    return m_values[index];
  }

  void set(const uint32_t index, const std::vector<ELEMENT_TYPE>& values) {
    if ( values.empty() ) return;
    set(index, &(values[0]), values.size());
  }

  void set(const uint32_t index, const ELEMENT_TYPE* values, const uint32_t num_values) {
    // Do nothing for empty values
    if ( num_values == 0 || values == nullptr ) return;

    // Make sure index is in bounds
    check_max_boundary(index, capacity());

    // If this is the first time we've used this slot, we have one more value in the container
    if ( m_values[index].first == nullptr ) { ++m_num_values; }

    // Determine how the value will be stored based on its length, and get storage ready
    prepare_memory(index, num_values);

    // Copy values into the prepared storage
    memcpy(m_values[index].first, values, num_values * sizeof(ELEMENT_TYPE));

    // Keep track of the length of the longest set of values in the container
    if ( num_values > m_max_value_length) m_max_value_length = num_values;
  }

  void clear(const uint32_t index) {
    if ( ! is_set(index) ) return;

    const auto previous_length = m_values[index].second;
    release_memory_if_necessary(index);
    --m_num_values;

    // Special case: clearing the longest item requires us to recalculate m_max_value_length
    if ( previous_length == m_max_value_length ) {
      recalculate_max_value_length();
    }
  }

  void clear() {
    for ( auto i = 0u; i < m_values.size(); ++i ) {
      release_memory_if_necessary(i);
    }
    m_num_values = 0;
    m_max_value_length = 0;
  }

 private:
  uint32_t m_num_values;                                     
  uint32_t m_max_value_length;                               
  uint32_t m_short_value_upper_bound;                        
  std::vector<std::pair<ELEMENT_TYPE*,uint32_t>> m_values;   
  std::vector<ELEMENT_TYPE> m_contiguous_storage;            

  void prepare_memory(const uint32_t index, const uint32_t num_values) {
    // Clean up previous dynamic allocation at this index if there is one
    release_memory_if_necessary(index);

    // Use contiguous pre-allocated storage for short values
    if ( num_values <= m_short_value_upper_bound ) {
      m_values[index].first = &(m_contiguous_storage[index * m_short_value_upper_bound]);
    }
    else {
      // Use dynamic allocation for values that don't fit (note: can't use smart pointers to wrap
      // this allocation since we will often be pointing into memory that must not be freed -- otherwise
      // we risk undefined behavior)
      m_values[index].first = new ELEMENT_TYPE[num_values];
    }

    // Record the length of the value as well
    m_values[index].second = num_values;
  }

  void release_memory_if_necessary(const uint32_t index) {
    // Only free pointers that don't point into the contiguous storage
    if ( m_values[index].first != nullptr &&
         m_values[index].first != &(m_contiguous_storage[index * m_short_value_upper_bound]) ) {

      // No complaining about this delete! If you're the author of a low-level container like vector,
      // or this class, delete is perfectly ok to use internally. Can't use smart pointers because we
      // have pointers into contiguous storage mixed in with pointers to individually-allocated memory
      // blocks.
      delete[] m_values[index].first;
    }

    m_values[index].first = nullptr;
    m_values[index].second = 0;
  }

  void recalculate_max_value_length() {
    m_max_value_length = 0u;

    for ( auto& value : m_values ) {
      if ( value.first != nullptr && value.second > m_max_value_length ) {
        m_max_value_length = value.second;
      }
    }
  }
};

}
}

#endif  /* gamgee__short_value_optimized_storage__guard */