src/dasynq/dasynq-stableheap.h

   1 #ifndef DASYNQ_STABLE_HEAP_INCLUDED
   2 #define DASYNQ_STABLE_HEAP_INCLUDED 1
   3
   4 // Convert an "unstable" priority queue (which doesn't use FIFO ordering for same-priority elements)
   5 // into a "stable" queue (which does deliver same-priority elements in FIFO order). This is done by
   6 // adding a generation counter to each element added to the queue, and using it as a second-order
   7 // priority key (after the original key).
   8 //
   9 // The generation counter is a 64-bit integer and can not realistically overflow.
  10
  11 #include <functional>
  12 #include <utility>
  13 #include <cstdint>
  14
  15 namespace dasynq {
  16
  17 template <typename P>
  18 class stable_prio
  19 {
  20     public:
  21     P p;
  22     uint64_t order;
  23
  24     template <typename ...U>
  25     stable_prio(uint64_t o, U... u) : p(u...), order(o)
  26     {
  27     }
  28
  29     // zero-argument constructor should not really be needed, but some
  30     // heap implementations aren't yet perfect.
  31     stable_prio()
  32     {
  33     }
  34 };
  35
  36 template <typename P, typename C>
  37 class compare_stable_prio
  38 {
  39     public:
  40     bool operator()(const stable_prio<P> &a, const stable_prio<P> &b)
  41     {
  42         C lt;
  43         if (lt(a.p, b.p)) {
  44             return true;
  45         }
  46         if (lt(b.p, a.p)) {
  47             return false;
  48         }
  49
  50         return a.order < b.order;
  51     }
  52 };
  53
  54
  55 template <template <typename H1, typename H2, typename H3> class H, typename T, typename P, typename C = std::less<P>>
  56 class stable_heap : private H<T,stable_prio<P>,compare_stable_prio<P,C>>
  57 {
  58     using Base = H<T,stable_prio<P>,compare_stable_prio<P,C>>;
  59
  60     // using H<T,P,compare_stable_prio<P,C>>:H;  // inherit constructors
  61     using Base::Base;
  62
  63     uint64_t sequence = 0;
  64
  65     public:
  66
  67     using handle_t = typename Base::handle_t;
  68     using handle_t_r = typename Base::handle_t_r;
  69
  70     bool insert(handle_t & index, P pval = P())
  71     {
  72         auto sp = stable_prio<P>(sequence++, pval);
  73         return Base::insert(index, sp);
  74     }
  75
  76     template <typename ...U> void allocate(handle_t & hnd, U&& ...u)
  77     {
  78         Base::allocate(hnd, std::forward<U>(u)...);
  79     }
  80
  81     static void init_handle(handle_t &hndl)
  82     {
  83         Base::init_handle(hndl);
  84     }
  85
  86     T &node_data(handle_t &hndl)
  87     {
  88         return Base::node_data(hndl);
  89     }
  90
  91     bool is_queued(handle_t & hnd)
  92     {
  93         return Base::is_queued(hnd);
  94     }
  95
  96     decltype(std::declval<Base>().get_root()) get_root()
  97     {
  98         return Base::get_root();
  99     }
 100
 101     void pull_root()
 102     {
 103         Base::pull_root();
 104     }
 105
 106     void deallocate(handle_t_r index)
 107     {
 108         Base::deallocate(index);
 109     }
 110
 111     void remove(handle_t_r hnd)
 112     {
 113         Base::remove(hnd);
 114     }
 115
 116     bool empty()
 117     {
 118         return Base::empty();
 119     }
 120 };
 121
 122 } // namespace dasynq
 123
 124 #endif