graph.h

// This file if part of the llir-opt project.
// Licensing information can be found in the LICENSE file.
// (C) 2018 Nandor Licker. All rights reserved.
 
#pragma once
 
#include <vector>
#include <memory>
 
#include "core/adt/id.h"
 
class Node;
class DerefNode;
class GraphNode;
class RootNode;
class SetNode;
 
 
 
class Graph final {
public:
  class SetIterator : public std::iterator<std::forward_iterator_tag, SetNode *> {
  public:
    bool operator==(const SetIterator &x) const { return it_ == x.it_; }
    bool operator!=(const SetIterator &x) const { return !operator==(x); }
 
    SetIterator &operator++() {
      ++it_;
      Skip();
      return *this;
    }
 
    SetIterator operator++(int) {
      auto tmp = *this;
      ++*this;
      return tmp;
    }
 
    SetNode *operator*() const { return *it_; }
 
  private:
    friend class Graph;
 
    SetIterator(
        Graph *graph,
        std::vector<SetNode *>::iterator it)
      : graph_(graph)
      , it_(it)
    {
      Skip();
    }
 
    void Skip()
    {
      while (it_ != graph_->sets_.end() && !*it_) {
        ++it_;
      }
    }
 
  private:
    Graph *graph_;
    std::vector<SetNode *>::iterator it_;
  };
 
public:
  SetNode *Set();
  DerefNode *Deref(SetNode *set);
  RootNode *Root(SetNode *set);
 
  SetNode *Get(ID<SetNode *> id) const { return sets_[id]; }
  DerefNode *Get(ID<DerefNode *> id) const { return derefs_[id]; }
 
  SetNode *Find(ID<SetNode *> id);
  DerefNode *Find(ID<DerefNode *> id) const { return derefs_[id]; }
 
  SetNode *Union(SetNode *a, SetNode *b);
 
  SetIterator begin() { return SetIterator(this, sets_.begin()); }
  SetIterator end() { return SetIterator(this, sets_.end()); }
 
private:
  void Replace(SetNode *a, SetNode *b);
  void Replace(DerefNode *a, DerefNode *b);
 
private:
  friend class SCCSolver;
 
  std::vector<SetNode *> sets_;
  std::vector<DerefNode *> derefs_;
  std::vector<RootNode *> roots_;
 
  std::vector<std::unique_ptr<Node>> nodes_;
 
  struct Entry {
    uint32_t Parent;
    uint32_t Rank;
 
    Entry(uint32_t parent, uint32_t rank) : Parent(parent), Rank(rank) {}
  };
 
  std::vector<Entry> unions_;
};