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
  14 namespace dasynq {
  15
  16 template <typename P>
  17 class stable_prio
  18 {
  19     public:
  20     P p;
  21     uint64_t order;
  22
  23     template <typename ...U>
  24     stable_prio(uint64_t o, U... u) : p(u...), order(o)
  25     {
  26     }
  27
  28     // zero-argument constructor should not really be needed, but some
  29     // heap implementations aren't yet perfect.
  30     stable_prio()
  31     {
  32     }
  33 };
  34
  35 template <typename P, typename C>
  36 class compare_stable_prio
  37 {
  38     public:
  39     bool operator()(const stable_prio<P> &a, const stable_prio<P> &b)
  40     {
  41         C lt;
  42         if (lt(a.p, b.p)) {
  43             return true;
  44         }
  45         if (lt(b.p, a.p)) {
  46             return false;
  47         }
  48
  49         return a.order < b.order;
  50     }
  51 };
  52
  53
  54 template <template <typename H1, typename H2, typename H3> class H, typename T, typename P, typename C = std::less<P>>
  55 class stable_heap : private H<T,stable_prio<P>,compare_stable_prio<P,C>>
  56 {
  57     using Base = H<T,stable_prio<P>,compare_stable_prio<P,C>>;
  58
  59     // using H<T,P,compare_stable_prio<P,C>>:H;  // inherit constructors
  60     using Base::Base;
  61
  62     uint64_t sequence = 0;
  63
  64     public:
  65
  66     using handle_t = typename Base::handle_t;
  67     using handle_t_r = typename Base::handle_t_r;
  68
  69     bool insert(handle_t & index, P pval = P())
  70     {
  71         auto sp = stable_prio<P>(sequence++, pval);
  72         return Base::insert(index, sp);
  73     }
  74
  75     template <typename ...U> void allocate(handle_t & hnd, U&& ...u)
  76     {
  77         Base::allocate(hnd, std::forward<U>(u)...);
  78     }
  79
  80     static void init_handle(handle_t &hndl)
  81     {
  82         Base::init_handle(hndl);
  83     }
  84
  85     T &node_data(handle_t &hndl)
  86     {
  87         return Base::node_data(hndl);
  88     }
  89
  90     bool is_queued(handle_t & hnd)
  91     {
  92         return Base::is_queued(hnd);
  93     }
  94
  95     decltype(std::declval<Base>().get_root()) get_root()
  96     {
  97         return Base::get_root();
  98     }
  99
 100     void pull_root()
 101     {
 102         Base::pull_root();
 103     }
 104
 105     void deallocate(handle_t_r index)
 106     {
 107         Base::deallocate(index);
 108     }
 109
 110     void remove(handle_t_r hnd)
 111     {
 112         Base::remove(hnd);
 113     }
 114
 115     bool empty()
 116     {
 117         return Base::empty();
 118     }
 119 };
 120
 121 } // namespace dasynq
 122
 123 #endif