dense_integer_map.h

Go to the documentation of this file.

/*******************************************************************\
 
Module: Dense integer map
 
Author: Diffblue Ltd
 
\*******************************************************************/
 
 
#ifndef CPROVER_UTIL_DENSE_INTEGER_MAP_H
#define CPROVER_UTIL_DENSE_INTEGER_MAP_H
 
#include <util/invariant.h>
 
#include <cstdint>
#include <limits>
#include <unordered_set>
#include <vector>
 
class identity_functort
{
public:
  template <typename T>
  constexpr T &&operator()(T &&t) const
  {
    return std::forward<T>(t);
  }
};
 
template <class K, class V, class KeyToDenseInteger = identity_functort>
class dense_integer_mapt
{
public:
  typedef std::vector<K> possible_keyst;
 
private:
  // Offset between keys resulting from KeyToDenseInteger{}(key) and indices
  // into map.
  int64_t offset;
 
  typedef std::vector<std::pair<K, V>> backing_storet;
 
  // Main store: contains <key, value> pairs, where entries at positions with
  // no corresponding key are default-initialized and entries with a
  // corresponding key but no value set yet have the correct key but a default-
  // initialized value. Both of these are skipped by this type's iterators.
  backing_storet map;
 
  // Indicates whether a given position in \ref map's value has been set, and
  // therefore whether our iterators should stop at a given location. We use
  // this auxiliary structure rather than `pair<K, std::optional<V>>` in
  // \ref map because this way we can more easily return a std::map-like
  // std::pair<const K, V> & from the iterator.
  std::vector<bool> value_set;
 
  // Population count (number of '1's) in value_set, i.e., number of keys whose
  // values have been set.
  std::size_t n_values_set;
 
  // "Allowed" keys passed to \ref setup_for_keys. Attempting to use keys not
  // included in this vector may result in an invariant failure, but can
  // sometimes silently succeed
  possible_keyst possible_keys_vector;
 
  // Convert a key into an index into \ref map
  std::size_t key_to_index(const K &key) const
  {
    auto key_integer = KeyToDenseInteger{}(key);
    INVARIANT(((int64_t)key_integer) >= offset, "index should be in range");
    auto ret = (std::size_t)key_integer - (std::size_t)offset;
    INVARIANT(ret < map.size(), "index should be in range");
    return ret;
  }
 
  // Note that \ref map entry at offset \ref index has been set.
  void mark_index_set(std::size_t index)
  {
    if(!value_set[index])
    {
      ++n_values_set;
      value_set[index] = true;
    }
  }
 
  // Has the \ref map entry at offset \ref index been set?
  bool index_is_set(std::size_t index) const
  {
    return value_set[index];
  }
 
  // Support class used to implement both const and non-const iterators
  // This is just a std::vector iterator pointing into \ref map, but with an
  // operator++ that skips unset values.
  template <class UnderlyingIterator, class UnderlyingValue>
  class iterator_templatet
  {
    // Type of this template instantiation
    typedef iterator_templatet<UnderlyingIterator, UnderlyingValue> self_typet;
    // Type of our containing \ref dense_integer_mapt
    typedef dense_integer_mapt<K, V, KeyToDenseInteger> map_typet;
 
  public:
    // These types are defined such that the class is compatible with being
    // treated as an STL iterator. For this to work, they must not be renamed.
    using iterator_category = std::forward_iterator_tag;
    using value_type = UnderlyingValue;
    using difference_type = std::ptrdiff_t;
    using pointer = UnderlyingValue *;
    using reference = UnderlyingValue &;
 
    iterator_templatet(UnderlyingIterator it, const map_typet &underlying_map)
      : underlying_iterator(it), underlying_map(underlying_map)
    {
      it = skip_unset_values(it);
    }
 
    operator iterator_templatet<
      typename backing_storet::const_iterator,
      const typename backing_storet::value_type>() const
    {
      return {underlying_iterator, underlying_map};
    }
 
    self_typet operator++()
    {
      self_typet i = *this;
      underlying_iterator = advance(underlying_iterator);
      return i;
    }
    self_typet operator++(int junk)
    {
      underlying_iterator = advance(underlying_iterator);
      return *this;
    }
    reference operator*() const
    {
      return *underlying_iterator;
    }
    pointer operator->() const
    {
      return &*underlying_iterator;
    }
    bool operator==(const self_typet &rhs) const
    {
      return underlying_iterator == rhs.underlying_iterator;
    }
    bool operator!=(const self_typet &rhs) const
    {
      return underlying_iterator != rhs.underlying_iterator;
    }
 
  private:
    // Advance \ref it to the next map entry with an initialized value
    UnderlyingIterator advance(UnderlyingIterator it)
    {
      return skip_unset_values(std::next(it));
    }
 
    // Return the next iterator >= it with its value set
    UnderlyingIterator skip_unset_values(UnderlyingIterator it)
    {
      auto iterator_pos = (std::size_t)std::distance(
        underlying_map.map.begin(),
        (typename backing_storet::const_iterator)it);
      while((std::size_t)iterator_pos < underlying_map.map.size() &&
            !underlying_map.value_set.at(iterator_pos))
      {
        ++iterator_pos;
        ++it;
      }
      return it;
    }
 
    // Wrapped std::vector iterator
    UnderlyingIterator underlying_iterator;
    const map_typet &underlying_map;
  };
 
public:
  typedef iterator_templatet<
    typename backing_storet::iterator,
    typename backing_storet::value_type>
    iterator;
 
  typedef iterator_templatet<
    typename backing_storet::const_iterator,
    const typename backing_storet::value_type>
    const_iterator;
 
  dense_integer_mapt() : offset(0), n_values_set(0)
  {
  }
 
  template <typename Iter>
  void setup_for_keys(Iter first, Iter last)
  {
    INVARIANT(
      size() == 0,
      "setup_for_keys must only be called on a newly-constructed container");
 
    int64_t highest_key = std::numeric_limits<int64_t>::min();
    int64_t lowest_key = std::numeric_limits<int64_t>::max();
    std::unordered_set<int64_t> seen_keys;
    for(Iter it = first; it != last; ++it)
    {
      int64_t integer_key = (int64_t)KeyToDenseInteger{}(*it);
      highest_key = std::max(integer_key, highest_key);
      lowest_key = std::min(integer_key, lowest_key);
      INVARIANT(
        seen_keys.insert(integer_key).second,
        "keys for use in dense_integer_mapt must be unique");
    }
 
    if(highest_key < lowest_key)
    {
      offset = 0;
    }
    else
    {
      std::size_t map_size = (std::size_t)((highest_key - lowest_key) + 1);
      INVARIANT(
        map_size > 0, // overflowed?
        "dense_integer_mapt size should fit in std::size_t");
      INVARIANT(
        map_size <= std::numeric_limits<std::size_t>::max(),
        "dense_integer_mapt size should fit in std::size_t");
      offset = lowest_key;
      map.resize(map_size);
      for(Iter it = first; it != last; ++it)
        map.at(key_to_index(*it)).first = *it;
      value_set.resize(map_size);
    }
 
    possible_keys_vector.insert(possible_keys_vector.end(), first, last);
  }
 
  const V &at(const K &key) const
  {
    std::size_t index = key_to_index(key);
    INVARIANT(index_is_set(index), "map value should be set");
    return map.at(index).second;
  }
  V &at(const K &key)
  {
    std::size_t index = key_to_index(key);
    INVARIANT(index_is_set(index), "map value should be set");
    return map.at(index).second;
  }
 
  V &operator[](const K &key)
  {
    std::size_t index = key_to_index(key);
    mark_index_set(index);
    return map.at(index).second;
  }
 
  std::pair<iterator, bool> insert(const std::pair<const K, V> &pair)
  {
    auto index = key_to_index(pair.first);
    auto signed_index =
      static_cast<typename backing_storet::iterator::difference_type>(index);
    iterator it{std::next(map.begin(), signed_index), *this};
 
    if(index_is_set(index))
      return {it, false};
    else
    {
      mark_index_set(index);
      map.at(index).second = pair.second;
      return {it, true};
    }
  }
 
  std::size_t count(const K &key) const
  {
    return index_is_set(key_to_index(key));
  }
 
  std::size_t size() const
  {
    return n_values_set;
  }
 
  const possible_keyst &possible_keys() const
  {
    return possible_keys_vector;
  }
 
  iterator begin()
  {
    return iterator{map.begin(), *this};
  }
 
  iterator end()
  {
    return iterator{map.end(), *this};
  }
 
  const_iterator begin() const
  {
    return const_iterator{map.begin(), *this};
  }
 
  const_iterator end() const
  {
    return const_iterator{map.end(), *this};
  }
 
  const_iterator cbegin() const
  {
    return begin();
  }
 
  const_iterator cend() const
  {
    return end();
  }
};
 
#endif // CPROVER_UTIL_DENSE_INTEGER_MAP_H