indexspace.h

Go to the documentation of this file.

/*
 * Copyright 2025 Stanford University, NVIDIA Corporation
 * SPDX-License-Identifier: Apache-2.0
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
 
// index spaces for Realm
 
#ifndef REALM_INDEXSPACE_H
#define REALM_INDEXSPACE_H
 
#include "realm/event.h"
#include "realm/memory.h"
#include "realm/point.h"
#define REALM_SKIP_INLINES
#include "realm/instance.h"
#undef REALM_SKIP_INLINES
 
#include "realm/realm_c.h"
#include "realm/realm_config.h"
#include "realm/sparsity.h"
#include "realm/dynamic_templates.h"
 
#include "realm/custom_serdez.h"
 
namespace Realm {
  // NOTE: all these interfaces are templated, which means partitions.cc is going
  //  to have to somehow know which ones to instantiate - this is controlled by the
  //  following type lists, using a bunch of helper stuff from dynamic_templates.h
 
  typedef DynamicTemplates::IntList<1, REALM_MAX_DIM> DIMCOUNTS;
  typedef DynamicTemplates::TypeList<int, unsigned int, long long>::TL DIMTYPES;
  typedef DynamicTemplates::TypeList<int, bool>::TL FLDTYPES;
 
  class ProfilingRequestSet;
  class CodeDescriptor;
 
  struct CopySrcDstField {
  public:
    CopySrcDstField(void);
    CopySrcDstField(const CopySrcDstField &copy_from);
    CopySrcDstField &operator=(const CopySrcDstField &copy_from);
    ~CopySrcDstField(void);
    CopySrcDstField &set_field(RegionInstance _inst, FieldID _field_id, size_t _size,
                               size_t _subfield_offset = 0);
    CopySrcDstField &set_indirect(int _indirect_index, FieldID _field_id, size_t _size,
                                  size_t _subfield_offset = 0);
    CopySrcDstField &set_redop(ReductionOpID _redop_id, bool _is_fold,
                               bool exclusive = false);
    CopySrcDstField &set_serdez(CustomSerdezID _serdez_id);
    CopySrcDstField &set_fill(const void *_data, size_t _size);
    template <typename T>
    CopySrcDstField &set_fill(T value);
 
  public:
    RegionInstance inst;
    FieldID field_id;
    size_t size;
    ReductionOpID redop_id;
    bool red_fold;
    bool red_exclusive;
    CustomSerdezID serdez_id;
    size_t subfield_offset;
    int indirect_index;
    static const size_t MAX_DIRECT_SIZE = 8;
    union {
      char direct[8];
      void *indirect;
    } fill_data;
  };
 
  std::ostream &operator<<(std::ostream &os, const CopySrcDstField &sd);
 
  template <int N, typename T = int>
  struct IndexSpaceIterator;
  template <int N, typename T = int>
  class SparsityMap;
 
  template <typename IS, typename FT>
  struct FieldDataDescriptor {
    IS index_space;
    RegionInstance inst;
    size_t field_offset;
  };
 
  template <int N, typename T = int>
  class REALM_PUBLIC_API TranslationTransform {
  public:
    TranslationTransform(void) = default;
    TranslationTransform(const Point<N, T> &_offset);
 
    template <typename T2>
    Realm::Point<N, T> operator[](const Realm::Point<N, T2> &point) const;
 
    Point<N, T> offset;
  };
 
  template <int M, int N, typename T = int>
  class REALM_PUBLIC_API AffineTransform {
  public:
    AffineTransform(void) = default;
    AffineTransform(const Realm::Matrix<M, N, T> &_transform, const Point<M, T> &_offset);
 
    template <typename T2>
    Realm::Point<M, T> operator[](const Realm::Point<N, T2> &point) const;
 
    Realm::Matrix<M, N, T> transform;
    Point<M, T> offset;
  };
 
  template <int N, typename T, int N2, typename T2>
  class REALM_PUBLIC_API StructuredTransform {
  public:
    StructuredTransform(void) = default;
    StructuredTransform(const AffineTransform<N, N2, T2> &_transform);
    StructuredTransform(const TranslationTransform<N, T2> &_transform);
 
    enum StructuredTransformType
    {
      NONE = 0,
      AFFINE = 1,
      TRANSLATION = 2,
    };
 
    Point<N, T> operator[](const Point<N2, T> &point) const;
 
    // protected:
    Realm::Matrix<N, N2, T2> transform_matrix;
    Point<N, T2> offset;
    StructuredTransformType type = StructuredTransformType::NONE;
  };
 
  template <int N, typename T, int N2, typename T2>
  class REALM_PUBLIC_API DomainTransform {
  public:
    DomainTransform(void) = default;
    DomainTransform(const StructuredTransform<N, T, N2, T2> &_transform);
    DomainTransform(
        const std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Point<N, T>>>
            &_field_data);
    DomainTransform(const std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Rect<N, T>>>
                        &_field_data);
 
    enum DomainTransformType
    {
      NONE = 0,
      STRUCTURED = 1,
      UNSTRUCTURED_PTR = 2,
      UNSTRUCTURED_RANGE = 3,
    };
 
    // protected:
    StructuredTransform<N, T, N2, T2> structured_transform;
    std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Point<N, T>>> ptr_data;
    std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Rect<N, T>>> range_data;
    DomainTransformType type = DomainTransformType::NONE;
  };
 
  class IndirectionInfo;
 
  template <int N, typename T = int>
  class REALM_PUBLIC_API CopyIndirection {
  public:
    class Base {
    public:
      virtual ~Base(void) {}
      REALM_INTERNAL_API_EXTERNAL_LINKAGE
      virtual IndirectionInfo *create_info(const IndexSpace<N, T> &is) const = 0;
    };
 
    template <int N2, typename T2 = int>
    class Affine : public CopyIndirection<N, T>::Base {
    public:
      virtual ~Affine(void) {}
 
      // Defines the next indirection to avoid a 3-way templating.
      typename CopyIndirection<N2, T2>::Base *next_indirection;
 
      Matrix<N, N2, T2> transform;
      Point<N2, T2> offset_lo, offset_hi;
      Point<N2, T2> divisor;
      Rect<N2, T2> wrap;
      std::vector<IndexSpace<N2, T2>> spaces;
      std::vector<RegionInstance> insts;
 
      REALM_INTERNAL_API_EXTERNAL_LINKAGE
      virtual IndirectionInfo *create_info(const IndexSpace<N, T> &is) const;
    };
 
    template <int N2, typename T2 = int>
    class Unstructured : public CopyIndirection<N, T>::Base {
    public:
      Unstructured() {}
      Unstructured(RegionInstance _ind_inst,
                   const std::vector<IndexSpace<N2, T2>> &_spaces,
                   const std::vector<RegionInstance> &_insts, FieldID _field_id,
                   size_t _subfield_offset = 0, bool _is_ranges = false,
                   bool _oor_possible = false, bool _aliasing_possible = false)
        : inst(_ind_inst)
        , spaces(_spaces)
        , insts(_insts)
        , field_id(_field_id)
        , subfield_offset(_subfield_offset)
        , is_ranges(_is_ranges)
        , oor_possible(_oor_possible)
        , aliasing_possible(_aliasing_possible)
      {}
      virtual ~Unstructured(void) {}
 
      typename CopyIndirection<N2, T2>::Base *next_indirection;
 
      RegionInstance inst;
      std::vector<IndexSpace<N2, T2>> spaces;
      std::vector<RegionInstance> insts;
      FieldID field_id;
      size_t subfield_offset;
      bool is_ranges;
      bool oor_possible;      // can any pointers fall outside all the target spaces?
      bool aliasing_possible; // can multiple pointers go to the same element?
 
      REALM_INTERNAL_API_EXTERNAL_LINKAGE
      virtual IndirectionInfo *create_info(const IndexSpace<N, T> &is) const;
    };
  };
 
  template <int N, typename T>
  struct REALM_PUBLIC_API IndexSpace {
    Rect<N, T> bounds;
    SparsityMap<N, T> sparsity;
 
    REALM_CUDA_HD
    IndexSpace(void); // results in an empty index space
    REALM_CUDA_HD
    IndexSpace(const Rect<N, T> &_bounds);
    IndexSpace(const Rect<N, T> &_bounds, SparsityMap<N, T> _sparsity);
 
 
    explicit IndexSpace(const std::vector<Point<N, T>> &points, bool disjoint = false);
 
    explicit IndexSpace(const std::vector<Rect<N, T>> &rects, bool disjoint = false);
 
 
    REALM_CUDA_HD
    static IndexSpace<N, T> make_empty(void);
 
 
    void destroy(Event wait_on = Event::NO_EVENT);
 
 
    REALM_CUDA_HD
    bool empty(void) const;
 
 
    REALM_CUDA_HD
    bool dense(void) const;
 
 
    Event make_valid(bool precise = true) const;
 
    bool is_valid(bool precise = true) const;
 
 
    IndexSpace<N, T> tighten(bool precise = true) const;
 
 
    bool contains(const Point<N, T> &p) const;
    bool contains_all(const Rect<N, T> &r) const;
    bool contains_any(const Rect<N, T> &r) const;
 
    bool overlaps(const IndexSpace<N, T> &other) const;
 
 
    size_t volume(void) const;
 
 
    bool contains_approx(const Point<N, T> &p) const;
    bool contains_all_approx(const Rect<N, T> &r) const;
    bool contains_any_approx(const Rect<N, T> &r) const;
 
    bool overlaps_approx(const IndexSpace<N, T> &other) const;
 
 
    size_t volume_approx(void) const;
 
 
    REALM_PUBLIC_API
    bool compute_covering(size_t max_rects, int max_overhead,
                          std::vector<Rect<N, T>> &covering) const;
 
 
    template <typename LAMBDA>
    REALM_PUBLIC_API void foreach_subrect(LAMBDA lambda);
    template <typename LAMBDA>
    REALM_PUBLIC_API void foreach_subrect(LAMBDA lambda, const Rect<N, T> &restriction);
 
    // instance creation
#if 0
    RegionInstance create_instance(Memory memory,
                   const std::vector<size_t>& field_sizes,
                   size_t block_size,
                   const ProfilingRequestSet& reqs) const;
#endif
 
 
    REALM_PUBLIC_API
    Event fill(const std::vector<CopySrcDstField> &dsts,
               const ProfilingRequestSet &requests, const void *fill_value,
               size_t fill_value_size, Event wait_on = Event::NO_EVENT,
               int priority = 0) const;
 
 
    REALM_PUBLIC_API
    Event copy(const std::vector<CopySrcDstField> &srcs,
               const std::vector<CopySrcDstField> &dsts,
               const ProfilingRequestSet &requests, Event wait_on = Event::NO_EVENT,
               int priority = 0) const;
 
 
    REALM_PUBLIC_API
    Event copy(std::vector<CopySrcDstField> &&srcs, std::vector<CopySrcDstField> &&dsts,
               const ProfilingRequestSet &requests, Event wait_on = Event::NO_EVENT,
               int priority = 0) const;
 
 
    REALM_PUBLIC_API
    Event copy(const std::vector<CopySrcDstField> &srcs,
               const std::vector<CopySrcDstField> &dsts,
               const std::vector<const typename CopyIndirection<N, T>::Base *> &indirects,
               const ProfilingRequestSet &requests, Event wait_on = Event::NO_EVENT,
               int priority = 0) const;
 
 
    REALM_PUBLIC_API
    Event copy(std::vector<CopySrcDstField> &&srcs, std::vector<CopySrcDstField> &&dsts,
               const std::vector<const typename CopyIndirection<N, T>::Base *> &indirects,
               const ProfilingRequestSet &requests, Event wait_on = Event::NO_EVENT,
               int priority = 0) const;
 
    // Partitioning operations
 
 
    REALM_PUBLIC_API
    Event create_equal_subspace(size_t count, size_t granularity, unsigned index,
                                IndexSpace<N, T> &subspace,
                                const ProfilingRequestSet &reqs,
                                Event wait_on = Event::NO_EVENT) const;
 
    REALM_PUBLIC_API
    Event create_equal_subspaces(size_t count, size_t granularity,
                                 std::vector<IndexSpace<N, T>> &subspaces,
                                 const ProfilingRequestSet &reqs,
                                 Event wait_on = Event::NO_EVENT) const;
 
 
    REALM_PUBLIC_API
    Event create_weighted_subspaces(size_t count, size_t granularity,
                                    const std::vector<int> &weights,
                                    std::vector<IndexSpace<N, T>> &subspaces,
                                    const ProfilingRequestSet &reqs,
                                    Event wait_on = Event::NO_EVENT) const;
 
    REALM_PUBLIC_API
    Event create_weighted_subspaces(size_t count, size_t granularity,
                                    const std::vector<size_t> &weights,
                                    std::vector<IndexSpace<N, T>> &subspaces,
                                    const ProfilingRequestSet &reqs,
                                    Event wait_on = Event::NO_EVENT) const;
 
    // Field-based partitioning operations
 
    template <typename FT>
    REALM_PUBLIC_API Event create_subspace_by_field(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, FT>> &field_data,
        FT color, IndexSpace<N, T> &subspace, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
    template <typename FT>
    REALM_PUBLIC_API Event create_subspaces_by_field(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, FT>> &field_data,
        const std::vector<FT> &colors, std::vector<IndexSpace<N, T>> &subspaces,
        const ProfilingRequestSet &reqs, Event wait_on = Event::NO_EVENT) const;
 
 
    template <typename FT, typename FT2>
    REALM_PUBLIC_API Event create_subspace_by_field(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, FT>> &field_data,
        const CodeDescriptor &codedesc, FT2 color, IndexSpace<N, T> &subspace,
        const ProfilingRequestSet &reqs, Event wait_on = Event::NO_EVENT) const;
 
    template <typename FT, typename FT2>
    REALM_PUBLIC_API Event create_subspaces_by_field(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, FT>> &field_data,
        const CodeDescriptor &codedesc, const std::vector<FT2> &colors,
        std::vector<IndexSpace<N, T>> &subspaces, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
 
    template <int N2, typename T2, typename TRANSFORM>
    REALM_PUBLIC_API Event create_subspace_by_image(
        const TRANSFORM &transform, const IndexSpace<N2, T2> &source,
        const IndexSpace<N, T> &image, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2, typename TRANSFORM>
    REALM_PUBLIC_API Event create_subspaces_by_image(
        const TRANSFORM &transform, const std::vector<IndexSpace<N2, T2>> &sources,
        std::vector<IndexSpace<N, T>> &images, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspaces_by_image(
        const DomainTransform<N, T, N2, T2> &domain_transform,
        const std::vector<IndexSpace<N2, T2>> &sources,
        std::vector<IndexSpace<N, T>> &images, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspace_by_image(
        const std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Point<N, T>>>
            &field_data,
        const IndexSpace<N2, T2> &source, IndexSpace<N, T> &image,
        const ProfilingRequestSet &reqs, Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspaces_by_image(
        const std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Point<N, T>>>
            &field_data,
        const std::vector<IndexSpace<N2, T2>> &sources,
        std::vector<IndexSpace<N, T>> &images, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
    // range versions
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspace_by_image(
        const std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Rect<N, T>>>
            &field_data,
        const IndexSpace<N2, T2> &source, IndexSpace<N, T> &image,
        const ProfilingRequestSet &reqs, Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspaces_by_image(
        const std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Rect<N, T>>>
            &field_data,
        const std::vector<IndexSpace<N2, T2>> &sources,
        std::vector<IndexSpace<N, T>> &images, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspaces_by_image_with_difference(
        const std::vector<FieldDataDescriptor<IndexSpace<N2, T2>, Point<N, T>>>
            &field_data,
        const std::vector<IndexSpace<N2, T2>> &sources,
        const std::vector<IndexSpace<N, T>> &diff_rhs,
        std::vector<IndexSpace<N, T>> &images, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspaces_by_image_with_difference(
        const DomainTransform<N, T, N2, T2> &domain_transform,
        const std::vector<IndexSpace<N2, T2>> &sources,
        const std::vector<IndexSpace<N, T>> &diff_rhs,
        std::vector<IndexSpace<N, T>> &images, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
 
    template <int N2, typename T2, typename TRANSFORM>
    REALM_PUBLIC_API Event create_subspace_by_preimage(
        const TRANSFORM &transform, const IndexSpace<N2, T2> &target,
        IndexSpace<N, T> &preimage, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2, typename TRANSFORM>
    REALM_PUBLIC_API Event create_subspaces_by_preimage(
        const TRANSFORM &transform, const std::vector<IndexSpace<N2, T2>> &targets,
        std::vector<IndexSpace<N, T>> &preimages, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspaces_by_preimage(
        const DomainTransform<N2, T2, N, T> &domain_transform,
        const std::vector<IndexSpace<N2, T2>> &targets,
        std::vector<IndexSpace<N, T>> &preimages, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspace_by_preimage(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, Point<N2, T2>>>
            &field_data,
        const IndexSpace<N2, T2> &target, IndexSpace<N, T> &preimage,
        const ProfilingRequestSet &reqs, Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspaces_by_preimage(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, Point<N2, T2>>>
            &field_data,
        const std::vector<IndexSpace<N2, T2>> &targets,
        std::vector<IndexSpace<N, T>> &preimages, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
    // range versions
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspace_by_preimage(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, Rect<N2, T2>>>
            &field_data,
        const IndexSpace<N2, T2> &target, IndexSpace<N, T> &preimage,
        const ProfilingRequestSet &reqs, Event wait_on = Event::NO_EVENT) const;
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_subspaces_by_preimage(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, Rect<N2, T2>>>
            &field_data,
        const std::vector<IndexSpace<N2, T2>> &targets,
        std::vector<IndexSpace<N, T>> &preimages, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
 
    template <int N2, typename T2>
    REALM_PUBLIC_API Event create_association(
        const std::vector<FieldDataDescriptor<IndexSpace<N, T>, Point<N2, T2>>>
            &field_data,
        const IndexSpace<N2, T2> &range, const ProfilingRequestSet &reqs,
        Event wait_on = Event::NO_EVENT) const;
 
    // set operations
 
    // three basic operations (union, intersection, difference) are provided in 4 forms:
    //  IS op IS     -> result
    //  IS[] op IS[] -> result[] (zip over two inputs, which must be same length)
    //  IS op IS[]   -> result[] (first input applied to each element of second array)
    //  IS[] op IS   -> result[] (each element of first array applied to second input)
 
 
    REALM_PUBLIC_API
    static Event compute_union(const IndexSpace<N, T> &lhs, const IndexSpace<N, T> &rhs,
                               IndexSpace<N, T> &result, const ProfilingRequestSet &reqs,
                               Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_unions(const std::vector<IndexSpace<N, T>> &lhss,
                                const std::vector<IndexSpace<N, T>> &rhss,
                                std::vector<IndexSpace<N, T>> &results,
                                const ProfilingRequestSet &reqs,
                                Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_unions(const IndexSpace<N, T> &lhs,
                                const std::vector<IndexSpace<N, T>> &rhss,
                                std::vector<IndexSpace<N, T>> &results,
                                const ProfilingRequestSet &reqs,
                                Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_unions(const std::vector<IndexSpace<N, T>> &lhss,
                                const IndexSpace<N, T> &rhs,
                                std::vector<IndexSpace<N, T>> &results,
                                const ProfilingRequestSet &reqs,
                                Event wait_on = Event::NO_EVENT);
 
 
    REALM_PUBLIC_API
    static Event compute_intersection(const IndexSpace<N, T> &lhs,
                                      const IndexSpace<N, T> &rhs,
                                      IndexSpace<N, T> &result,
                                      const ProfilingRequestSet &reqs,
                                      Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_intersections(const std::vector<IndexSpace<N, T>> &lhss,
                                       const std::vector<IndexSpace<N, T>> &rhss,
                                       std::vector<IndexSpace<N, T>> &results,
                                       const ProfilingRequestSet &reqs,
                                       Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_intersections(const IndexSpace<N, T> &lhs,
                                       const std::vector<IndexSpace<N, T>> &rhss,
                                       std::vector<IndexSpace<N, T>> &results,
                                       const ProfilingRequestSet &reqs,
                                       Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_intersections(const std::vector<IndexSpace<N, T>> &lhss,
                                       const IndexSpace<N, T> &rhs,
                                       std::vector<IndexSpace<N, T>> &results,
                                       const ProfilingRequestSet &reqs,
                                       Event wait_on = Event::NO_EVENT);
 
 
    REALM_PUBLIC_API
    static Event compute_difference(const IndexSpace<N, T> &lhs,
                                    const IndexSpace<N, T> &rhs, IndexSpace<N, T> &result,
                                    const ProfilingRequestSet &reqs,
                                    Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_differences(const std::vector<IndexSpace<N, T>> &lhss,
                                     const std::vector<IndexSpace<N, T>> &rhss,
                                     std::vector<IndexSpace<N, T>> &results,
                                     const ProfilingRequestSet &reqs,
                                     Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_differences(const IndexSpace<N, T> &lhs,
                                     const std::vector<IndexSpace<N, T>> &rhss,
                                     std::vector<IndexSpace<N, T>> &results,
                                     const ProfilingRequestSet &reqs,
                                     Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_differences(const std::vector<IndexSpace<N, T>> &lhss,
                                     const IndexSpace<N, T> &rhs,
                                     std::vector<IndexSpace<N, T>> &results,
                                     const ProfilingRequestSet &reqs,
                                     Event wait_on = Event::NO_EVENT);
 
    // set reduction operations (union and intersection)
 
    REALM_PUBLIC_API
    static Event compute_union(const std::vector<IndexSpace<N, T>> &subspaces,
                               IndexSpace<N, T> &result, const ProfilingRequestSet &reqs,
                               Event wait_on = Event::NO_EVENT);
 
    REALM_PUBLIC_API
    static Event compute_intersection(const std::vector<IndexSpace<N, T>> &subspaces,
                                      IndexSpace<N, T> &result,
                                      const ProfilingRequestSet &reqs,
                                      Event wait_on = Event::NO_EVENT);
  };
 
  template <int N, typename T>
  REALM_PUBLIC_API std::ostream &operator<<(std::ostream &os, const IndexSpace<N, T> &p);
 
  class IndexSpaceGenericImpl;
 
  class REALM_PUBLIC_API IndexSpaceGeneric {
  public:
    IndexSpaceGeneric();
    IndexSpaceGeneric(const IndexSpaceGeneric &copy_from);
 
    template <int N, typename T>
    IndexSpaceGeneric(const IndexSpace<N, T> &copy_from);
    template <int N, typename T>
    IndexSpaceGeneric(const Rect<N, T> &copy_from);
 
    ~IndexSpaceGeneric();
 
    IndexSpaceGeneric &operator=(const IndexSpaceGeneric &copy_from);
 
    template <int N, typename T>
    IndexSpaceGeneric &operator=(const IndexSpace<N, T> &copy_from);
    template <int N, typename T>
    IndexSpaceGeneric &operator=(const Rect<N, T> &copy_from);
 
    void destroy(Event wait_on = Event::NO_EVENT);
 
    template <int N, typename T>
    const IndexSpace<N, T> &as_index_space() const;
 
    // only IndexSpace method exposed directly is copy
    Event copy(const std::vector<CopySrcDstField> &srcs,
               const std::vector<CopySrcDstField> &dsts,
               const ProfilingRequestSet &requests, Event wait_on = Event::NO_EVENT,
               int priority = 0) const;
 
    template <int N, typename T>
    Event copy(const std::vector<CopySrcDstField> &srcs,
               const std::vector<CopySrcDstField> &dsts,
               const std::vector<const typename CopyIndirection<N, T>::Base *> &indirects,
               const ProfilingRequestSet &requests, Event wait_on = Event::NO_EVENT,
               int priority = 0) const;
 
    // "public" but not useful to application code
    IndexSpaceGenericImpl *impl;
 
  protected:
    // would like to use sizeof(IndexSpace<REALM_MAX_DIM, size_t>) here,
    //  but that requires the specializations that are defined in the
    //  include of indexspace.inl below...
    static constexpr size_t MAX_TYPE_SIZE = DIMTYPES::MaxSize::value;
    static constexpr size_t STORAGE_BYTES = (2 * REALM_MAX_DIM + 2) * MAX_TYPE_SIZE;
    typedef char Storage_unaligned[STORAGE_BYTES];
    REALM_ALIGNED_TYPE_SAMEAS(Storage_aligned, Storage_unaligned,
                              DIMTYPES::MaxSizeType<MAX_TYPE_SIZE>::TYPE);
    Storage_aligned raw_storage;
  };
 
  template <int N, typename T>
  class LinearizedIndexSpace;
 
  class LinearizedIndexSpaceIntfc {
  protected:
    // cannot be created directly
    LinearizedIndexSpaceIntfc(int _dim, int _idxtype);
 
  public:
    virtual ~LinearizedIndexSpaceIntfc(void);
 
    virtual LinearizedIndexSpaceIntfc *clone(void) const = 0;
 
    // returns the size of the linearized space
    virtual size_t size(void) const = 0;
 
    // check and conversion routines to get a dimension-aware intermediate
    template <int N, typename T>
    bool check_dim(void) const;
    template <int N, typename T>
    LinearizedIndexSpace<N, T> &as_dim(void);
    template <int N, typename T>
    const LinearizedIndexSpace<N, T> &as_dim(void) const;
 
    int dim, idxtype;
  };
 
  template <int N, typename T>
  class LinearizedIndexSpace : public LinearizedIndexSpaceIntfc {
  protected:
    // still can't be created directly
    LinearizedIndexSpace(const IndexSpace<N, T> &_indexspace);
 
  public:
    // generic way to linearize a point
    virtual size_t linearize(const Point<N, T> &p) const = 0;
 
    IndexSpace<N, T> indexspace;
  };
 
  template <int N, typename T>
  class AffineLinearizedIndexSpace : public LinearizedIndexSpace<N, T> {
  public:
    // "fortran order" has the smallest stride in the first dimension
    explicit AffineLinearizedIndexSpace(const IndexSpace<N, T> &_indexspace,
                                        bool fortran_order = true);
 
    virtual LinearizedIndexSpaceIntfc *clone(void) const;
 
    virtual size_t size(void) const;
 
    virtual size_t linearize(const Point<N, T> &p) const;
 
    size_t volume, offset;
    Point<N, ptrdiff_t> strides;
    Rect<N, T> dbg_bounds;
  };
 
  template <int N, typename T>
  class SparsityMapPublicImpl;
 
  template <int N, typename T>
  struct REALM_PUBLIC_API IndexSpaceIterator {
    Rect<N, T> rect{Rect<N, T>::make_empty()};
    IndexSpace<N, T> space;
    Rect<N, T> restriction{Rect<N, T>::make_empty()};
    bool valid{false};
    // for iterating over SparsityMap's
    SparsityMapPublicImpl<N, T> *s_impl{nullptr};
    size_t cur_entry{0};
 
    IndexSpaceIterator(void);
    IndexSpaceIterator(const IndexSpace<N, T> &_space);
    IndexSpaceIterator(const IndexSpace<N, T> &_space, const Rect<N, T> &_restrict);
    IndexSpaceIterator(const Rect<N, T> &_boudns, const Rect<N, T> &_restrict,
                       SparsityMapPublicImpl<N, T> *_s_impl);
 
    void reset(const IndexSpace<N, T> &_space);
    void reset(const IndexSpace<N, T> &_space, const Rect<N, T> &_restrict);
    void reset(const Rect<N, T> &_bounds, const Rect<N, T> &_restrict,
               SparsityMapPublicImpl<N, T> *_s_impl);
    // steps to the next subrect, returning true if a next subrect exists
    bool step(void);
 
  private:
    void reset_sparse(SparsityMapPublicImpl<N, T> *_s_impl);
  };
 
}; // namespace Realm
 
// specializations of std::less<T> for IndexSpace<N,T> allow
//  them to be used in STL containers
namespace std {
  template <int N, typename T>
  struct less<Realm::IndexSpace<N, T>> {
    bool operator()(const Realm::IndexSpace<N, T> &is1,
                    const Realm::IndexSpace<N, T> &is2) const;
  };
}; // namespace std
 
#include "realm/indexspace.inl"
 
#endif // ifndef REALM_INDEXSPACE_H