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 #ifndef incl_HPHP_DATAFLOW_WORKLIST_H_
  17 #define incl_HPHP_DATAFLOW_WORKLIST_H_
  18
  19 #include <cstdint>
  20 #include <queue>
  21 #include <vector>
  22 #include <type_traits>
  23 #include <algorithm>
  24 #include <functional>
  25 #include <utility>
  26 #include <cassert>
  27
  28 #include <boost/dynamic_bitset.hpp>
  29
  30 namespace HPHP {
  31
  32 //////////////////////////////////////////////////////////////////////
  33
  34 /*
  35  * Encapsulates a unique priority queue of an integer type, where elements in
  36  * the queue are ids less than some universe size.
  37  *
  38  * This is useful for dataflow worklists, where we want to visit blocks with
  39  * lower (or higher) ids before blocks with higher (or lower) ids, but also
  40  * don't want to schedule something that's already scheduled.  By default this
  41  * returns lower ids first (note that this is returning things that are larger
  42  * according to its Compare function, like std::priority_queue).
  43  */
  44 template<class T, class Compare = std::greater<T>>
  45 struct dataflow_worklist {
  46   static_assert(
  47     std::is_integral<T>::value && std::is_unsigned<T>::value,
  48     "dataflow_worklist requires an unsigned integer type"
  49   );
  50
  51   explicit dataflow_worklist(T universe_size)
  52     : m_set(universe_size)
  53     , m_q(
  54         Compare{},
  55         [&] {
  56           auto r = std::vector<T>{};
  57           r.reserve(universe_size);
  58           return r;
  59         }()
  60       )
  61   {}
  62
  63   // We have to manually implement move, because boost::dynamic_bitset doesn't
  64   // support it (at the time of this writing).
  65   dataflow_worklist(dataflow_worklist&& o) noexcept
  66     : dataflow_worklist(0)
  67   {
  68     swap(o);
  69   }
  70
  71   dataflow_worklist& operator=(dataflow_worklist&& o) noexcept {
  72     dataflow_worklist tmp(std::move(o));
  73     tmp.swap(*this);
  74     return *this;
  75   }
  76
  77   void swap(dataflow_worklist& o) {
  78     using std::swap;
  79     swap(m_set, o.m_set);
  80     swap(m_q, o.m_q);
  81   }
  82
  83   bool empty() const { return m_q.empty(); }
  84   T top() { assert(!empty()); return m_q.top(); }
  85
  86   T pop() {
  87     auto const t = top();
  88     assert(m_set.test(t));
  89     m_q.pop();
  90     m_set.reset(t);
  91     return t;
  92   }
  93
  94   /*
  95    * Enqueue t. Returns true iff the item was newly inserted.
  96    */
  97   bool push(T t) {
  98     assert(t < m_set.size());
  99     if (m_set[t]) return false;
 100     m_q.push(t);
 101     m_set.set(t);
 102     return true;
 103   }
 104
 105 private:
 106   boost::dynamic_bitset<> m_set;
 107   std::priority_queue<T,std::vector<T>,Compare> m_q;
 108 };
 109
 110 //////////////////////////////////////////////////////////////////////
 111
 112 }
 113
 114 #endif