Accumulator.h

Go to the documentation of this file.

#ifndef GALOIS_ACCUMULATOR_H
#define GALOIS_ACCUMULATOR_H

#include "Galois/Runtime/PerThreadStorage.h"
#include "Galois/Runtime/LoopHooks.h"

#include <limits>

namespace Galois {

template<typename T, typename BinFunc>
class GReducible {
protected:
  BinFunc m_func;
  GaloisRuntime::PerThreadStorage<T> m_data;
  const T m_initial;

  explicit GReducible(const BinFunc& f, const T& initial): m_func(f), m_initial(initial) { }

public:
  explicit GReducible(const BinFunc& f = BinFunc()): m_func(f), m_initial(T()) { }

  void update(const T& rhs) {
    T& lhs = *m_data.getLocal();
    m_func(lhs, rhs);
  }

  T& reduce() {
    T& d0 = *m_data.getLocal();
    for (unsigned int i = 1; i < m_data.size(); ++i) {
      T& d = *m_data.getRemote(i);
      m_func(d0, d);
      d = m_initial;
    }
    return d0;
  }

  void reset() {
    for (unsigned int i = 0; i < m_data.size(); ++i) {
      *m_data.getRemote(i) = m_initial;
    }
  }
};


template<typename T>
struct gmax {
  const T& operator()(const T& lhs, const T& rhs) const {
    return std::max<T>(lhs, rhs);
  }
};

template<typename T>
struct gmin {
  const T& operator()(const T& lhs, const T& rhs) const {
    return std::min<T>(lhs, rhs);
  }
};

template<typename BinFunc>
struct ReduceAssignWrap {
  BinFunc fn;
  ReduceAssignWrap(const BinFunc& f = BinFunc()): fn(f) { }
  template<typename T>
  void operator()(T& lhs, const T& rhs) const {
    lhs = fn(lhs, rhs);
  }
};

template<typename BinFunc>
struct ReduceVectorWrap {
  BinFunc fn;
  ReduceVectorWrap(const BinFunc& f = BinFunc()): fn(f) { }
  template<typename T>
  void operator()(T& lhs, const T& rhs) const {
    if (lhs.size() < rhs.size())
      lhs.resize(rhs.size());
    typename T::iterator ii = lhs.begin();
    for (typename T::const_iterator jj = rhs.begin(), ej = rhs.end(); jj != ej; ++ii, ++jj) {
      fn(*ii, *jj);
    }
  }
};

template<typename BinFunc>
struct ReduceMapWrap {
  BinFunc fn;
  ReduceMapWrap(const BinFunc& f = BinFunc()): fn(f) { }
  template<typename T>
  void operator()(T& lhs, const T& rhs) const {
    for (typename T::const_iterator jj = rhs.begin(), ej = rhs.end(); jj != ej; ++jj) {
      fn(lhs[jj->first], jj->second);
    }
  }
};

template<typename CollectionTy,template<class> class AdaptorTy>
struct ReduceCollectionWrap {
  typedef typename CollectionTy::value_type value_type;

  void operator()(CollectionTy& lhs, const CollectionTy& rhs) {
    AdaptorTy<CollectionTy> adapt(lhs, lhs.begin());
    std::copy(rhs.begin(), rhs.end(), adapt);
  }

  void operator()(CollectionTy& lhs, const value_type& rhs) {
    AdaptorTy<CollectionTy> adapt(lhs, lhs.begin());
    *adapt = rhs;
  }
};

template<typename T, typename BinFunc>
class GSimpleReducible: public GReducible<T, ReduceAssignWrap<BinFunc> >  {
  typedef GReducible<T, ReduceAssignWrap<BinFunc> > base_type;
public:
  explicit GSimpleReducible(const BinFunc& func = BinFunc()): base_type(func) { }
};

template<typename T>
class GAccumulator: public GReducible<T, ReduceAssignWrap<std::plus<T> > > {
  typedef GReducible<T, ReduceAssignWrap<std::plus<T> > > base_type;

public:
  GAccumulator& operator+=(const T& rhs) {
    base_type::update(rhs);
    return *this;
  }

  GAccumulator& operator-=(const T& rhs) {
    base_type::update(-rhs);
    return *this;
 }

  T unsafeRead() const {
    T d0 = *this->m_data.getRemote(0);
    for (unsigned int i = 1; i < this->m_data.size(); ++i) {
      const T& d = *this->m_data.getRemote(i);
      this->m_func(d0, d);
    }
    return d0;
  }
};

template<typename CollectionTy,template<class> class AdaptorTy>
class GCollectionAccumulator: public GReducible<CollectionTy, ReduceCollectionWrap<CollectionTy, AdaptorTy> > {
  typedef ReduceCollectionWrap<CollectionTy, AdaptorTy> Func;
  typedef GReducible<CollectionTy, Func> base_type;
  typedef typename CollectionTy::value_type value_type;

  Func func;

public:
  void update(const value_type& rhs) {
    CollectionTy& v = *this->m_data.getLocal();
    func(v, rhs);
  }
};

template<typename SetTy>
class GSetAccumulator: public GCollectionAccumulator<SetTy, std::insert_iterator> { };

template<typename VectorTy>
class GVectorAccumulator: public GCollectionAccumulator<VectorTy, std::back_insert_iterator> { };

template<typename VectorTy>
class GVectorElementAccumulator: public GReducible<VectorTy, ReduceVectorWrap<ReduceAssignWrap<std::plus<typename VectorTy::value_type> > > > {
  typedef ReduceAssignWrap<std::plus<typename VectorTy::value_type> > ElementFunc;
  typedef GReducible<VectorTy, ReduceVectorWrap<ElementFunc> > base_type;
  typedef typename VectorTy::value_type value_type;

  ElementFunc func;

public:
  void update(size_t index, const value_type& rhs) {
    VectorTy& v = *this->m_data.getLocal();
    if (v.size() <= index)
      v.resize(index + 1);
    func(v[index], rhs);
  }
};

template<typename MapTy>
class GMapElementAccumulator: public GReducible<MapTy, ReduceMapWrap<ReduceAssignWrap<std::plus<typename MapTy::mapped_type> > > > {
  typedef ReduceAssignWrap<std::plus<typename MapTy::mapped_type> > ElementFunc;
  typedef GReducible<MapTy, ReduceMapWrap<ElementFunc> > base_type;
  typedef typename MapTy::mapped_type mapped_type;
  typedef typename MapTy::key_type key_type;

  ElementFunc func;

public:
  void update(const key_type& index, const mapped_type& rhs) {
    MapTy& v = *this->m_data.getLocal();
    func(v[index], rhs);
  }
};

template<typename T>
class GReduceMax: public GReducible<T, ReduceAssignWrap<gmax<T> > > {
  typedef GReducible<T, ReduceAssignWrap<gmax<T> > > base_type;
public:
  GReduceMax(): base_type(ReduceAssignWrap<gmax<T> >(), std::numeric_limits<T>::min()) { }
};

template<typename T>
class GReduceMin: public GReducible<T, ReduceAssignWrap<gmin<T> > > {
  typedef GReducible<T, ReduceAssignWrap<gmin<T> > > base_type;
public:
  GReduceMin(): base_type(ReduceAssignWrap<gmin<T> >(), std::numeric_limits<T>::max()) { }
};

}
#endif

---