hphp/util/dataflow-worklist.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #pragma once
  17
  18 #include <cstdint>
  19 #include <queue>
  20 #include <vector>
  21 #include <type_traits>
  22 #include <algorithm>
  23 #include <functional>
  24 #include <utility>
  25 #include <cassert>
  26
  27 #include <boost/dynamic_bitset.hpp>
  28
  29 namespace HPHP {
  30
  31 //////////////////////////////////////////////////////////////////////
  32
  33 /*
  34  * Encapsulates a unique priority queue of an integer type, where elements in
  35  * the queue are ids less than some universe size.
  36  *
  37  * This is useful for dataflow worklists, where we want to visit blocks with
  38  * lower (or higher) ids before blocks with higher (or lower) ids, but also
  39  * don't want to schedule something that's already scheduled.  By default this
  40  * returns lower ids first (note that this is returning things that are larger
  41  * according to its Compare function, like std::priority_queue).
  42  */
  43 template<class T, class Compare = std::greater<T>>
  44 struct dataflow_worklist {
  45   static_assert(
  46     std::is_integral<T>::value && std::is_unsigned<T>::value,
  47     "dataflow_worklist requires an unsigned integer type"
  48   );
  49
  50   explicit dataflow_worklist(T universe_size)
  51     : m_set(universe_size)
  52     , m_q(
  53         Compare{},
  54         [&] {
  55           auto r = std::vector<T>{};
  56           r.reserve(universe_size);
  57           return r;
  58         }()
  59       )
  60   {}
  61
  62   // We have to manually implement move, because boost::dynamic_bitset doesn't
  63   // support it (at the time of this writing).
  64   dataflow_worklist(dataflow_worklist&& o) noexcept
  65     : dataflow_worklist(0)
  66   {
  67     swap(o);
  68   }
  69
  70   dataflow_worklist& operator=(dataflow_worklist&& o) noexcept {
  71     dataflow_worklist tmp(std::move(o));
  72     tmp.swap(*this);
  73     return *this;
  74   }
  75
  76   void swap(dataflow_worklist& o) {
  77     using std::swap;
  78     swap(m_set, o.m_set);
  79     swap(m_q, o.m_q);
  80   }
  81
  82   bool empty() const { return m_q.empty(); }
  83   T top() { assert(!empty()); return m_q.top(); }
  84
  85   T pop() {
  86     auto const t = top();
  87     assert(m_set.test(t));
  88     m_q.pop();
  89     m_set.reset(t);
  90     return t;
  91   }
  92
  93   /*
  94    * Enqueue t. Returns true iff the item was newly inserted.
  95    */
  96   bool push(T t) {
  97     assert(t < m_set.size());
  98     if (m_set[t]) return false;
  99     m_q.push(t);
 100     m_set.set(t);
 101     return true;
 102   }
 103
 104 private:
 105   boost::dynamic_bitset<> m_set;
 106   std::priority_queue<T,std::vector<T>,Compare> m_q;
 107 };
 108
 109 //////////////////////////////////////////////////////////////////////
 110
 111 }
 112