node.hh

// This file is a part of Aurelia.
// Copyright (C) 2010  Valentin David
// Copyright (C) 2010  University of Bergen
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#ifndef __NODE_HH
# define __NODE_HH

# include <aurelia-config.hh>

# include <map>
# include <unordered_set>
# include <forward_list>
# include "../max_shared/max_shared_ptr.hh"
# include "../streams/buf_stream.hh"
# include "../memory/pool_allocator.hh"
# include "label.hh"
# include "frame.hh"
# ifndef NDEBUG
#  ifdef HAVE_CXXABI_H
#   include <cxxabi.h>
#   define DEMANGLE(X...) abi::__cxa_demangle(X,0,0,&status)
#  else
#   define DEMANGLE(X...) X
#  endif
# endif

namespace aurelia {
  namespace llstack {

struct r_t;
struct node;

  }
}

namespace std {
  template <>
  struct hash<aurelia::llstack::node> {
    unsigned operator()(const aurelia::llstack::node& a) const;
  };
}

namespace aurelia {
  namespace llstack {

struct node_core {
public:
  typedef std::forward_list<frame, pool_allocator<frame> > frame_list_t;
  typedef std::unordered_set<node, std::hash<node>, std::equal_to<node>, pool_allocator<node> > node_set_t;
  typedef std::map<stream, frame_list_t, std::less<stream>, pool_allocator<std::pair<stream, frame_list_t> > > p_t;
private:
  label L;
  frame f;
  int pos;
  p_t P;
  node_set_t parents;
  unsigned _hash;

public:
  void update_hash();
  node_core(const label& L, const frame& f, int pos): L(L), f(f), pos(pos) {
    update_hash();
  }

  node_core(const node_core& other): L(other.L), f(other.f), pos(other.pos) {
    _hash = other._hash;
  }

  node_core(node_core&& other): L(std::move(other.L)),
                                f(std::move(other.f)),
                                pos(other.pos),
                                _hash(other._hash) {
  }

  node_core& operator=(const node_core& other) {
    return *this = node_core(other);
  }

  node_core& operator=(node_core&& other) {
    std::swap(L, other.L);
    std::swap(f, other.f);
    std::swap(pos, other.pos);
    std::swap(P, other.P);
    std::swap(parents, other.parents);
    std::swap(_hash, other._hash);
    return *this;
  }

  node_core() {
    _hash = 0;
  }

  unsigned hash() const {
    return _hash;
  }

  bool operator==(const node_core& other) const;

  const node_set_t& get_parents() const {
    return parents;
  }

  node_set_t& get_parents() {
    return parents;
  }

  const p_t& get_P() const {
    return P;
  }

  p_t& get_P() {
    return P;
  }

  int get_pos() const {
    return pos;
  }

  const label& get_label() const {
    return L;
  }

  const frame& get_frame() const {
    return f;
  }

  void drop(const stream& s) {
    for (p_t::iterator i = P.begin();
         i != P.end();) {
      if ((*i).first.get_pos() <= s.get_pos()) {
        P.erase(i);
        i = P.begin();
      } else break ;
    }
  }
};

struct node: public max_shared_ptr<node_core> {
private:
  typedef max_shared_ptr<node_core> super;

  explicit node(const typename super::set_t::iterator& other): super(other) {
  }

  node(const label& l, const frame& f, int s): super(l, f, s) {
  }
  node(const label& l, frame&& f, int s): super(l, std::move(f), s) {
  }
public:
  node() = default;

  node(const node& other): super(other) {
  }

  node(node&& other): super(std::move(other)) {
  }

  const node_core::node_set_t& parents() const {
    return (*this)->get_parents();
  }

  node_core::node_set_t& parents() {
    return const_cast<node_core*>(&**this)->get_parents();
  }

  const node_core::p_t& P() const {
    return (*this)->get_P();
  }

  node_core::p_t& P() {
    return const_cast<node_core*>(&**this)->get_P();
  }

  static node create(r_t& R, const label& l, const frame& f, const node& u,
                     const stream& j);

  static node boundary(const label&, const stream& s);

  unsigned hash() const {
    return (*this)->hash();
  }

  const label& get_label() const {
    return (*this)->get_label();
  }

  int pos() const {
    return (*this)->get_pos();
  }

  node& operator=(const node& other) {
    return *this = node(other);
  }

  node& operator=(node&& other) {
    super::operator=(std::move(other));
    return *this;
  }

  static void drop(const stream& s) {
    super::set_t::iterator i = super::set().begin();
    while (i != super::set().end()) {
      super::ptr& ro = *const_cast<super::ptr*>(&*i);
      ++ro.count();
      const_cast<node_core*>(&*ro)->drop(s);
      ++i;
      if (0 == --ro.count())
        set().erase(ro);
    }
  }

  void mark(std::unordered_set<node, std::hash<node>, std::equal_to<node>, pool_allocator<node> >& marks) const {
    std::pair<std::unordered_set<node, std::hash<node>, std::equal_to<node>, pool_allocator<node> >::iterator, bool> j =
      marks.insert(*this);
    if (j.second) {
      for (node_core::node_set_t::const_iterator i =
             parents().begin();
           i != parents().end(); ++i) {
        (*i).mark(marks);
      }
    }
  }

  static int nbnode() {
    return super::set().size();
  }

# ifndef NDEBUG
  static void printnodes(std::ostream& o) {
    //int status;
    super::set_t::iterator i = super::set().begin();
    o << "digraph g {" << std::endl;
    while (i != super::set().end()) {
      super::ptr& ro = *const_cast<super::ptr*>(&*i);

      o << "n_" << (*ro).get_label().hash()
        << "_" << (*ro).get_pos() << " [label=\""
        << (*ro).get_label().hash()
        << ", " << (*ro).get_pos() << "\"];" << std::endl;

      ++i;
    }
    i = super::set().begin();
    while (i != super::set().end()) {
      super::ptr& ro = *const_cast<super::ptr*>(&*i);
      for (node_core::node_set_t::const_iterator j =
             (*ro).get_parents().begin();
           j != (*ro).get_parents().end(); ++j) {
        o << "n_" << ((*ro).get_label().hash())
          << "_" << (*ro).get_pos() << " -> " << "n_"
          << ((*j).get_label()).hash() << "_"
          << (*j).pos() << ";" << std::endl;
      }
      i++;
    }
    o << "}" << std::endl;
  }
# endif

  static void clear(std::unordered_set<node, std::hash<node>, std::equal_to<node>, pool_allocator<node> > marks
                    = std::unordered_set<node, std::hash<node>, std::equal_to<node>, pool_allocator<node> >()) {
    super::set_t::iterator i = super::set().begin();
    while (i != super::set().end()) {
      if (marks.find(node(i))
          == marks.end()) {
        super::ptr& ro = *const_cast<super::ptr*>(&*i);
        const_cast<node_core*>(&*ro)->get_P().clear();
        if (!((*ro).get_parents().empty())) {
          ++ro.count();
          const_cast<node_core*>(&*ro)->get_parents().clear();
          --ro.count();
          set().erase(ro);
          i = super::set().begin();
        }
        else {
          i++;
        }
      } else {
        i++;
      }
    }
  }

  template <typename Ret>
  void pop(r_t& queue, const Ret& ret_value, stream& j);

  void pop(r_t& queue, const void_return&, stream& j);

  template <typename Ret>
  void pop(r_t& queue, const Ret& ret_value, stream& j) const {
    node(*this).pop(queue, ret_value, j);
  }
};

  }
}

#endif