Exclusive closed ranges and classification trees.

range.cc

#include <iterator>
#include <iostream>
#include <map>
#include <unordered_map>
#include <utility>
#include <vector>

typedef unsigned long long uint64;

class ExclusiveClosedRange {
 public:
  inline ExclusiveClosedRange(uint64 first, uint64 last)
      : first_(first), last_(last) {
  }
  inline uint64 first() const { return first_; }
  inline uint64 last() const { return last_; }

  // It implements "exclusive" behavior of this class.
  // brabrabra...
  inline bool operator<(const ExclusiveClosedRange& other) const {
    return last_ < other.first_;
  }

 private:
  uint64 first_;
  uint64 last_;
};


typedef std::map<ExclusiveClosedRange, int> ClassificationTree;

class hoge {
  class fuga {
    virtual void moge() = 0;
  };
  virtual fuga& foo() = 0;
  virtual fuga* bar() = 0;
  // FAILS: virtual fuga foo() = 0;
};

class MemoryLayer {
 public:
  struct MemoryAttribute {};
  class iterator : public std::iterator<std::forward_iterator_tag, void*> {
   public:
    iterator() {}
    virtual bool operator==(const iterator& other) const { return false; }
    virtual bool operator!=(const iterator& other) const { return true; }
    virtual iterator& operator++() { return *this; }
    virtual void* operator*() { return NULL; }
  };

  virtual void change(uint64 first, uint64 last, void* attribute) = 0;
  virtual iterator begin() = 0;
  virtual iterator end() = 0;

 private:
};

class MallocMemoryLayer: public MemoryLayer {
 public:
  class iterator: public MemoryLayer::iterator {
   public:
    inline iterator(std::map<ExclusiveClosedRange, int>::iterator p): p_(p) {}
    virtual inline bool operator==(const iterator& other) const {
      std::cout << "hoge" << std::endl;
      return p_ == other.p_;
    }
    virtual inline bool operator!=(const iterator& other) const {
      return p_ != other.p_;
    }
    virtual inline iterator& operator++() { ++p_; return *this; }
    virtual inline void* operator*() { return NULL; }
   private:
    std::map<ExclusiveClosedRange, int>::iterator p_;
  };

  MallocMemoryLayer() {
  }
  virtual void change(uint64 first, uint64 last, void* attribute) {
    ;
  }
  inline virtual MemoryLayer::iterator begin() {
    return iterator(malloc_map_.begin());
  }
  inline virtual MemoryLayer::iterator end() {
    return iterator(malloc_map_.end());
  }
  std::map<ExclusiveClosedRange, int> malloc_map_;

 private:
};

class PFNMemoryLayer: public MemoryLayer {
 public:
  class iterator: public MemoryLayer::iterator {
   public:
    inline iterator(std::unordered_map<uint64, uint64>::iterator p): p_(p) {}
    virtual inline bool operator==(const iterator& other) const {
      return p_ == other.p_;
    }
    virtual inline bool operator!=(const iterator& other) const {
      return p_ != other.p_;
    }
    virtual inline iterator& operator++() { ++p_; return *this; }
    virtual inline void* operator*() { return NULL; }
   private:
    std::unordered_map<uint64, uint64>::iterator p_;
  };

  PFNMemoryLayer() {
  }
  virtual void change(uint64 first, uint64 last, void* attribute) {
    ;
  }
  inline virtual MemoryLayer::iterator begin() {
    return iterator(pfn_.begin());
  }
  inline virtual MemoryLayer::iterator end() {
    return iterator(pfn_.end());
  }

 private:
  // It assumes that addresses are appended in ascending order.
  std::vector<uint64> pfn_top_addresses_;
  std::unordered_map<uint64, uint64> pfn_;
};

class CombinedMemoryLayers {
 public:

  class iterator: public std::iterator<std::forward_iterator_tag, void*> {
   public:
    inline iterator(std::map<MemoryLayer*,
                             MemoryLayer::iterator> internal_iterators) 
        : is_end_(false) {
      for (std::map<MemoryLayer*, MemoryLayer::iterator>::iterator p =
               internal_iterators.begin();
           p != internal_iterators.end();
           ++p) {
        MemoryLayer* layer = p->first;
        MemoryLayer::iterator& internal_iterator = p->second;
        if (layer->end() == internal_iterator) {
          is_end_ = true;
        }
        internal_iterators_.insert(*p);
      }
    }
    inline const bool operator==(const iterator& other) const {
      if (is_end_ && other.is_end_) {
        return true;
      }
      return internal_iterators_ == other.internal_iterators_;
    }
    inline bool operator!=(const iterator& other) const {
      if (is_end_ && other.is_end_) {
        return false;
      }
      return internal_iterators_ != other.internal_iterators_;
    }
    inline iterator& operator++() {
      std::cout << "*" << std::endl;
      for (std::map<MemoryLayer*, MemoryLayer::iterator>::iterator p =
               internal_iterators_.begin();
           p != internal_iterators_.end();
           ++p) {
        ++(p->second);
        if (p->first->end() == p->second) {
          std::cout << "??" << std::endl;
          is_end_ = true;
        }
      }
      return *this;
    }
   private:
    bool is_end_;
    uint64 first_;
    uint64 last_;
    std::map<MemoryLayer*, MemoryLayer::iterator> internal_iterators_;
  };

  CombinedMemoryLayers(MemoryLayer* a[], int length);
  CombinedMemoryLayers(std::vector<MemoryLayer*>& v);
  iterator begin() {
    std::map<MemoryLayer*, MemoryLayer::iterator> internal_iterators;
    for (std::vector<MemoryLayer*>::iterator p = layers_.begin();
         p != layers_.end();
         ++p) {
      internal_iterators.insert(make_pair(*p, (*p)->begin()));
    }
    return iterator(internal_iterators);
  }
  iterator end() {
    std::map<MemoryLayer*, MemoryLayer::iterator> internal_iterators;
    for (std::vector<MemoryLayer*>::iterator p = layers_.begin();
         p != layers_.end();
         ++p) {
      internal_iterators.insert(make_pair(*p, (*p)->end()));
    }
    return iterator(internal_iterators);
  }
 private:
  std::vector<MemoryLayer*> layers_;
};

CombinedMemoryLayers::CombinedMemoryLayers(MemoryLayer* a[],
                                           int length) {
  for (int i = 0; i < length; ++i) {
    layers_.push_back(a[i]);
  }
}

CombinedMemoryLayers::CombinedMemoryLayers(std::vector<MemoryLayer*>& v) {
  for (std::vector<MemoryLayer*>::iterator p = v.begin(); p != v.end(); ++p) {
    layers_.push_back(*p);
  }
}

void ExampleAnalyzer() {
  MallocMemoryLayer* l = new MallocMemoryLayer();
  std::cout << (l->end() == MallocMemoryLayer::iterator(l->malloc_map_.end()))
            << std::endl;
  std::cout << (l->end() == l->end())
            << std::endl;


  MemoryLayer* layer_array[] = {
    new MallocMemoryLayer(),
    new PFNMemoryLayer(),
  };
  CombinedMemoryLayers layers(layer_array, 2);
  for (CombinedMemoryLayers::iterator p = layers.begin();
       p != layers.end();
       ++p) {
    std::cout << "!" << std::endl;
  }
}

/*
template<typename T>
T* GetLayer() {
  return reinterpret_cast<T*> @@@
}
*/

int test() {
  ExampleAnalyzer();

  ClassificationTree range_dict;
  range_dict.insert(std::make_pair(ExclusiveClosedRange(3, 4), 0));
  range_dict.insert(std::make_pair(ExclusiveClosedRange(20, 20), 0));
  range_dict.insert(std::make_pair(ExclusiveClosedRange(7, 10), 0));
  range_dict.insert(std::make_pair(ExclusiveClosedRange(14, 18), 0));
  range_dict.insert(std::make_pair(ExclusiveClosedRange(0, 2), 0));

  for (ClassificationTree::iterator p = range_dict.begin();
       p != range_dict.end();
       ++p) {
    std::cout << (p->first.first()) << "," << (p->first.last()) << std::endl;
  }

  for (int i = 0; i <= 20; ++i) {
    ClassificationTree::iterator found;
    found = range_dict.find(ExclusiveClosedRange(i, i));
    if (found == range_dict.end()) {
      std::cout << i << ":" << "not found" << std::endl;
    } else {
      std::cout << i << ":" <<
          (found->first.first()) << "," << (found->first.last()) << std::endl;
    }
  }
  
  return 0;
}

int main() {
  return test();
}