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