queue.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 __QUEUE_HH
# define __QUEUE_HH
# include "node.hh"
# include "label.hh"
# include "frame.hh"
# include "../memory/pool_allocator.hh"
# include <unordered_map>

namespace aurelia {
  namespace llstack {

struct rj_t {
  struct ln: public std::pair<label, node> {
  private:
    unsigned _hash;
  public:
    typedef std::pair<label, node> super;
    ln(const label& l, const node& n): super(l, n) {
      _hash = this->first.hash();
      _hash = (_hash << 11) | (_hash >> 21);
      _hash ^= this->second.hash();
    }
    unsigned hash() const {
      return _hash;
    }

    ln(const ln& other): super(other.first, other.second),
                         _hash(other._hash) {

    }

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

    ln& operator=(ln&& other) {
      std::swap(this->first, other.first);
      std::swap(this->second, other.second);
      std::swap(_hash, other._hash);
      return *this;
    }
  };

  struct hash {
    unsigned operator()(const ln& a) const {
      return a.hash();
    }
  };

  struct eq {
    unsigned operator()(const ln& a, const ln& b) const {
      return ((a.first) == (b.first)) && (a.second == b.second);
    }
  };

  typedef std::unordered_set<frame, frame::hash_op, frame::eq, pool_allocator<frame> > frame_set_t;
  typedef std::unordered_map<ln, frame_set_t, hash, eq, pool_allocator<std::pair<ln, frame_set_t> > > set_t;
  set_t done;
  set_t pending;
};

struct descriptor {
  label L;
  frame f;
  node n;
  stream s;

  descriptor(const label& L, const frame& f, const node& n, const stream& s):
    L(L), f(f), n(n), s(s) {}
  descriptor(const descriptor& other): L(other.L),
                                       f(other.f), n(other.n), s(other.s) {
  }
};

struct r_t {
  struct eof {};
  typedef std::map<stream, rj_t, std::less<stream>, pool_allocator<std::pair<stream, rj_t> > > map_t;
  map_t m;

  descriptor pop() {
    map_t::iterator i = m.begin();
    if (i == m.end()) {
      throw eof();
    }
    while ((*i).second.pending.empty()) {
      stream s = (*i).first;
      m.erase(i);
      node::drop(s);
      //collect_nodes();
      i = m.begin();
      if (i == m.end())
        throw eof();
    }
    rj_t::set_t::iterator j = (*i).second.pending.begin();
    rj_t::frame_set_t::iterator f = (*j).second.begin();
    frame fr = *f;
    rj_t::ln p = (*j).first;
    (*i).second.done[(*j).first].insert(*f);
    (*j).second.erase(*f);
    if ((*j).second.empty()) {
      (*i).second.pending.erase(j);
    }
    return descriptor(p.first, fr, p.second, (*i).first);
  }

  void collect_nodes() const {
    std::unordered_set<node, std::hash<node>, std::equal_to<node>, pool_allocator<node> > marks;
    for (map_t::const_iterator i = m.begin();
         i != m.end(); ++i) {
      for (rj_t::set_t::const_iterator j = (*i).second.pending.begin();
           j != (*i).second.pending.end(); ++j) {
        (*j).first.second.mark(marks);
      }
      for (rj_t::set_t::const_iterator j = (*i).second.done.begin();
           j != (*i).second.done.end(); ++j) {
        (*j).first.second.mark(marks);
      }
    }
    node::clear(marks);
  }

  void add(const label& L, const frame& data, const node& u, const stream& j) {
    rj_t::ln p(L, u);
    if (m[j].done[p].find(data) == m[j].done[p].end()) {
      m[j].pending[p].insert(data);
    }
  }
};

  }
}

#endif