CountersMap.h

Go to the documentation of this file.

#ifndef COUNTERSMAP_H
#define COUNTERSMAP_H

// interface include
#include <array>
#include <cstddef>    // std::ptrdiff_t
#include <functional> // std::less<>
#include <iterator>   // std::bidirectional_iterator_tag
#include <map>
#include <memory>      // std::allocator<>
#include <type_traits> // std::make_unsigned
#include <utility>     // std::pair<>

namespace lar {

  constexpr bool IsPowerOf2(unsigned long long int v)
  {
    return v & 1 ? v == 1 : IsPowerOf2(v >> 1);
  }

  constexpr int LowestSetBit(unsigned long long int v);

  namespace details {

    template <typename COUNTER, std::size_t NCounters>
    class CounterBlock : public std::array<COUNTER, NCounters> {
    public:
      using Counter_t = COUNTER;

      using Array_t = std::array<Counter_t, NCounters>; 
      using value_type = typename Array_t::value_type;

      CounterBlock() : Array_t() { Array_t::fill(0); }

      CounterBlock(size_t index, Counter_t value) : CounterBlock()
      {
        Array_t::operator[](index) = value;
      }

      void fill(const value_type& value) { Array_t::fill(value); }
      void fill(size_t begin, size_t n, const value_type& value)
      {
        std::fill(Array_t::data() + begin, Array_t::data() + begin + n, value);
      }

    }; // CounterBlock

    template <typename KEY, typename COUNTER, size_t SIZE>
    struct CountersMapTraits {

      using Key_t = KEY;         
      using Counter_t = COUNTER; 

      static constexpr size_t NCounters = SIZE;

      using CounterBlock_t = CounterBlock<Counter_t, NCounters>;

      using PlainBaseMap_t = std::map<Key_t, CounterBlock_t, std::less<Key_t>>;

      using DefaultAllocator_t = typename PlainBaseMap_t::allocator_type;

      template <typename Alloc>
      using BaseMap_t = std::map<Key_t, CounterBlock_t, std::less<Key_t>, Alloc>;

      using MapValue_t = typename PlainBaseMap_t::value_type;

    }; // struct CountersMapTraits

  } // namespace details

  template <typename KEY,
            typename COUNTER,
            size_t SIZE,
            typename ALLOC =
              typename details::CountersMapTraits<KEY, COUNTER, SIZE>::DefaultAllocator_t,
            unsigned int SUBCOUNTERS = 1>
  class CountersMap {
    static_assert(SUBCOUNTERS == 1, "subcounters not implemented yet");
    static_assert(IsPowerOf2(SIZE), "the size of the cluster of counters must be a power of 2");

    using Traits_t = details::CountersMapTraits<KEY, COUNTER, SIZE>;

  public:
    using Key_t = KEY;         
    using Counter_t = COUNTER; 
    using Allocator_t = ALLOC; 

    using CounterMap_t = CountersMap<KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS>;

    static constexpr size_t NCounters = Traits_t::NCounters;

    static constexpr size_t NSubcounters = NCounters * SUBCOUNTERS;

    using SubCounter_t = Counter_t;

    using CounterBlock_t = typename Traits_t::CounterBlock_t;

    using BaseMap_t = typename Traits_t::template BaseMap_t<typename std::allocator_traits<
      Allocator_t>::template rebind_alloc<typename Traits_t::MapValue_t>>;

    /*
    using const_iterator = double_fwd_const_iterator<
      typename BaseMap_t::const_iterator,
      PairSecond<typename BaseMap_t::value_type>
      >;
    */

    using mapped_type = SubCounter_t;
    using allocator_type = Allocator_t; 
    // TODO others are missing

    using value_type = std::pair<const Key_t, SubCounter_t>;

    class const_iterator;

    CountersMap() {}

    CountersMap(Allocator_t alloc) : BaseMap_t(alloc) {}

    SubCounter_t operator[](Key_t key) const { return GetSubCounter(key); }

    SubCounter_t set(Key_t key, SubCounter_t value);

    SubCounter_t increment(Key_t key);

    SubCounter_t decrement(Key_t key);

    // this stuff needs serious work to be completed

    const_iterator begin() const;

    const_iterator end() const;

    bool empty() const { return counter_map.empty(); }

    typename std::make_unsigned<Key_t>::type n_counters() const
    {
      return counter_map.size() * NSubcounters;
    }

    template <typename OALLOC>
    bool is_equal(const std::map<Key_t, SubCounter_t, std::less<Key_t>, OALLOC>& to,
                  Key_t& first_difference) const;

    template <typename OALLOC>
    bool is_equal(const std::map<Key_t, SubCounter_t, std::less<Key_t>, OALLOC>& to) const
    {
      Key_t dummy;
      return is_equal(to, dummy);
    }

  protected:
    using BlockKey_t = Key_t; 
    using CounterIndex_t = typename std::make_unsigned<Key_t>::type;

    struct CounterKey_t {
      BlockKey_t block;       
      CounterIndex_t counter; 
      // there should be a subcluster index here too

      CounterKey_t() : block(0), counter(0) {}

      CounterKey_t(BlockKey_t major, CounterIndex_t minor) : block(major), counter(minor) {}

      CounterKey_t(Key_t key)
        : //    CounterKey_t(key >> MinorKeyBits, key & MinorKeyMask) {}
        CounterKey_t(key & ~MinorKeyMask, key & MinorKeyMask)
      {}

      //  Key_t Key() const { return (block << MinorKeyBits) + counter; }
      Key_t Key() const { return block + counter; }

      operator Key_t() const { return Key(); }

      CounterKey_t& operator++()
      {
        if (++counter == MinorKeyRange) next_block();
        return *this;
      }
      CounterKey_t& operator--()
      {
        if (counter-- == 0) {
          prev_block();
          counter = MinorKeyRange - 1;
        }
        return *this;
      } // operator--()
      CounterKey_t& operator++(int)
      {
        CounterKey_t old(*this);
        this->operator++();
        return old;
      }
      CounterKey_t& operator--(int)
      {
        CounterKey_t old(*this);
        this->operator--();
        return old;
      }

      CounterKey_t& start_block()
      {
        counter = 0;
        return *this;
      }

      CounterKey_t& prev_block()
      {
        block -= MinorKeyRange;
        return start_block();
      }

      CounterKey_t& next_block()
      {
        block += MinorKeyRange;
        return start_block();
      }

      static constexpr Key_t MinorKeyRange = NSubcounters;

      static constexpr Key_t MinorKeyBits = LowestSetBit(MinorKeyRange);

      static constexpr Key_t MinorKeyMask = MinorKeyRange - 1;

      static_assert(MinorKeyBits > 0, "Wrong COUNTER value for lar::CountersMap");

    }; // struct CounterKey_t

    BaseMap_t counter_map; 

    Counter_t GetCounter(CounterKey_t key) const;

    // Since subcounters are not implemented yet, this is a no-op
    SubCounter_t GetSubCounter(CounterKey_t key) const { return GetCounter(key); }

    Counter_t& GetOrCreateCounter(CounterKey_t key);

    static CounterKey_t SplitKey(Key_t key) { return key; }

    static const_iterator make_const_iterator(typename BaseMap_t::const_iterator it, size_t ix)
    {
      return {it, ix};
    }

  private:
    SubCounter_t unchecked_set(CounterKey_t key, SubCounter_t delta);

    SubCounter_t unchecked_add(CounterKey_t key, SubCounter_t delta);

  }; // class CountersMap

} // namespace lar

//------------------------------------------------------------------------------

namespace lar {

  namespace details {
    inline constexpr int LowestSetBitScaler(unsigned long long int v, int b)
    {
      return (v & 1) ? b : LowestSetBitScaler(v >> 1, b + 1);
    }

    namespace counters_map {
      static constexpr bool bDebug = true;

    } // namespace counters_map
  }   // namespace details

  inline constexpr int LowestSetBit(unsigned long long int v)
  {
    return (v == 0) ? -1 : details::LowestSetBitScaler(v, 0);
  }

  // providing "definitions" of the static constants;
  // these are required if the code is going to take the address of these
  // constants, which is most often due to the use of "const size_t&" in some
  // function, where "size_t" is a template argument type
  // (or else the reference would not be needed).
  // I am not providing the same for the protected and private members
  // (just because of laziness).
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  constexpr size_t CountersMap<K, C, S, A, SUB>::NCounters;

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  constexpr size_t CountersMap<K, C, S, A, SUB>::NSubcounters;

  // CountersMap<>::const_iterator does not fully implement the STL iterator
  // interface, since it does not implement operator-> () (for technical reason:
  // the value does not actually exist and it does not have an address),
  // in addition to std::swap().
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  class CountersMap<K, C, S, A, SUB>::const_iterator : public std::bidirectional_iterator_tag {
    friend CountersMap<K, C, S, A, SUB>;

  public:
    using value_type = typename CounterMap_t::value_type; 
    using difference_type = std::ptrdiff_t;
    using pointer = const value_type*;
    using reference = const value_type&;
    using iterator_category = std::bidirectional_iterator_tag;

    using iterator_type = CounterMap_t::const_iterator; 

    const_iterator() = default;

    value_type operator*() const { return {key(), iter->second[index]}; }

    iterator_type& operator++()
    {
      if (++index >= NSubcounters) {
        ++iter;
        index = 0;
      }
      return *this;
    } // operator++
    iterator_type operator++(int)
    {
      iterator_type old(*this);
      this->operator++();
      return old;
    }

    iterator_type& operator--()
    {
      if (index == 0) {
        --iter;
        index = NSubcounters - 1;
      }
      else
        --index;
      return *this;
    } // operator--()
    iterator_type operator--(int)
    {
      iterator_type old(*this);
      this->operator--();
      return old;
    }

    bool operator==(const iterator_type& as) const
    {
      return (iter == as.iter) && (index == as.index);
    }
    bool operator!=(const iterator_type& as) const
    {
      return (iter != as.iter) || (index != as.index);
    }

    CounterKey_t key() const { return {iter->first, index}; }

  protected:
    typename BaseMap_t::const_iterator iter;
    CounterIndex_t index; 

    const_iterator(typename BaseMap_t::const_iterator it, size_t ix) : iter(it), index(ix) {}

  }; // CountersMap<>::const_iterator

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::SubCounter_t CountersMap<K, C, S, A, SUB>::set(
    Key_t key,
    SubCounter_t value)
  {
    return unchecked_set(CounterKey_t(key), value);
  }

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::SubCounter_t
  CountersMap<K, C, S, A, SUB>::increment(Key_t key)
  {
    return unchecked_add(CounterKey_t(key), +1);
  }

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::SubCounter_t
  CountersMap<K, C, S, A, SUB>::decrement(Key_t key)
  {
    return unchecked_add(CounterKey_t(key), -1);
  }

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::const_iterator CountersMap<K, C, S, A, SUB>::begin()
    const
  {
    return const_iterator{counter_map.begin(), 0};
  }

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::const_iterator CountersMap<K, C, S, A, SUB>::end()
    const
  {
    return const_iterator{counter_map.end(), 0};
  }

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  template <typename OALLOC>
  bool CountersMap<K, C, S, A, SUB>::is_equal(
    const std::map<Key_t, SubCounter_t, std::less<Key_t>, OALLOC>& to,
    Key_t& first_difference) const
  {
    // this function is not optimised
    using CompMap_t = const std::map<Key_t, SubCounter_t, std::less<Key_t>, OALLOC>;
    typename CompMap_t::const_iterator to_iter = to.begin(), to_end = to.end();
    for (const typename const_iterator::value_type& p : *this) {

      if (to_iter != to_end) { // we have still counters to find
        // if counter is already beyond the next non-empty one froml STL map,
        // then we are missing some
        if (p.first > to_iter->first) {
          first_difference = to_iter->first;
          return false;
        }
        //    while (p.first > to_iter->first) {
        //      ++nMissingKeys;
        //      std::cout << "ERROR missing key " << to_iter->first << std::endl;
        //      if (++to_iter == to_end) break;
        //    } // while
        //  } // if
        //
        //  if (to_iter != to_end) { // we have still counters to find
        if (p.first == to_iter->first) {
          // if the counter is in SLT map, the two counts must match
          //  std::cout << "  " << p.first << " " << p.second << std::endl;
          if (to_iter->second != p.second) {
            //  std::cout << "ERROR wrong counter value " << p.second
            //    << ", expected " << to_iter->second << std::endl;
            //  ++nMismatchValue;
            first_difference = to_iter->first;
            return false;
          }
          ++to_iter; // done with it
        }
        else if (p.first < to_iter->first) {
          // if the counter is not in STL map, then it must be 0
          if (p.second != 0) {
            //  ++nExtraKeys;
            //  std::cout << "ERROR extra key " << p.first << " (" << p.second << ")"
            //    << std::endl;
            first_difference = p.first;
            return false;
          }
          //  else {
          //    std::cout << "  " << p.first << " " << p.second << " (not in STL)"
          //      << std::endl;
          //  }
        }
      }
      else { // if we are at the end of compared map
        // no more keys in STL map
        if (p.second != 0) {
          //  ++nExtraKeys;
          //  std::cout << "ERROR extra key " << p.first << " (" << p.second << ")"
          //    << std::endl;
          first_difference = p.first;
          return false;
        }
      }
    } // for element in map

    return true;
  } // CountersMap<>::is_equal()

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::Counter_t CountersMap<K, C, S, A, SUB>::GetCounter(
    CounterKey_t key) const
  {
    typename BaseMap_t::const_iterator iBlock = counter_map.find(key.block);
    return (iBlock == counter_map.end()) ? 0 : iBlock->second[key.counter];
  } // CountersMap<>::GetCounter() const

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::Counter_t&
  CountersMap<K, C, S, A, SUB>::GetOrCreateCounter(CounterKey_t key)
  {
    return counter_map[key.block][key.counter];
  }

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  typename CountersMap<K, C, S, A, SUB>::SubCounter_t CountersMap<K, C, S, A, SUB>::unchecked_set(
    CounterKey_t key,
    SubCounter_t value)
  {
    // take it low level here
    // first get the iterator to the block
    typename BaseMap_t::iterator iBlock = counter_map.lower_bound(key.block);
    if (iBlock != counter_map.end()) {
      if (iBlock->first == key.block) { // sweet, we have that counter already
        return iBlock->second[key.counter] = value;
      }
    }
    // no counter there yet: create one;
    // hint to insert before the block in the position we jave already found
    // (this is optimal in STL map for C++11);
    // create a block using the special constructor;
    // the temporary value created here is moved to the map
    counter_map.insert(iBlock, {key.block, {key.counter, value}});
    return value;
  } // CountersMap<>::unchecked_add() const

  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  typename CountersMap<K, C, S, A, SUB>::SubCounter_t CountersMap<K, C, S, A, SUB>::unchecked_add(
    CounterKey_t key,
    SubCounter_t delta)
  {
    // take it low level here
    // first get the iterator to the block
    typename BaseMap_t::iterator iBlock = counter_map.lower_bound(key.block);
    if (iBlock != counter_map.end()) {
      if (iBlock->first == key.block) { // sweet, we have that counter already
        return iBlock->second[key.counter] += delta;
      }
    }
    // no counter there yet: create one;
    // hint to insert before the block in the position we jave already found
    // (this is optimal in STL map for C++11);
    // create a block using the special constructor;
    // the temporary value created here is moved to the map
    counter_map.insert(iBlock, {key.block, {key.counter, delta}});
    return delta;
  } // CountersMap<>::unchecked_add() const

} // namespace lar

#endif // BULKALLOCATOR_H