src/dasynq/dasynq-daryheap.h

   1 #ifndef DASYNC_DARYHEAP_H_INCLUDED
   2 #define DASYNC_DARYHEAP_H_INCLUDED
   3
   4 #include "dasynq-svec.h"
   5 #include <type_traits>
   6 #include <functional>
   7 #include <limits>
   8
   9 namespace dasynq {
  10
  11 /**
  12  * Priority queue implementation based on a binary heap.
  13  *
  14  * Heap entry "handles" maintain an index into the heap. When the position of a node in the heap
  15  * changes, its handle must be updated.
  16  *
  17  * T : node data type
  18  * P : priority type (eg int)
  19  * Compare : functional object type to compare priorities
  20  */
  21 template <typename T, typename P, typename Compare = std::less<P>, int N = 4>
  22 class dary_heap
  23 {
  24     public:
  25     struct handle_t;
  26     using handle_t_r = handle_t &;
  27
  28     private:
  29
  30     // Actual heap node
  31     class heap_node
  32     {
  33         public:
  34         P data;
  35         handle_t * hnd_p;
  36
  37         heap_node(handle_t * hnd, const P &odata) : data(odata), hnd_p(hnd)
  38         {
  39             // nothing to do
  40         }
  41
  42         heap_node() { }
  43     };
  44
  45     svector<heap_node> hvec;
  46
  47     using hindex_t = typename decltype(hvec)::size_type;
  48
  49     hindex_t num_nodes = 0;
  50
  51     public:
  52
  53     // Handle to an element on the heap in the node buffer; also contains the data associated
  54     // with the node. (Alternative implementation would be to store the heap data in a
  55     // separate container, and have the handle be an index into that container).
  56     struct handle_t
  57     {
  58         union hd_u_t {
  59             // The data member is kept in a union so it doesn't get constructed/destructed
  60             // automatically, and we can construct it lazily.
  61             public:
  62             hd_u_t() { }
  63             ~hd_u_t() { }
  64             T hd;
  65         } hd_u;
  66
  67         hindex_t heap_index;
  68
  69         handle_t(const handle_t &) = delete;
  70         handle_t() { }
  71     };
  72
  73     // Initialise a handle (if it does not have a suitable constructor). Need not do anything
  74     // but may store a sentinel value to mark the handle as inactive. It should not be
  75     // necessary to call this, really.
  76     static void init_handle(handle_t &h) noexcept
  77     {
  78     }
  79
  80     private:
  81
  82     // Bubble a newly added timer down to the correct position
  83     bool bubble_down(hindex_t pos) noexcept
  84     {
  85         handle_t * ohndl = hvec[pos].hnd_p;
  86         P op = hvec[pos].data;
  87         return bubble_down(pos, ohndl, op);
  88     }
  89
  90     bool bubble_down(hindex_t pos, handle_t * ohndl, const P &op) noexcept
  91     {
  92         // int pos = v.size() - 1;
  93         Compare lt;
  94         while (pos > 0) {
  95             hindex_t parent = (pos - 1) / N;
  96             if (! lt(op, hvec[parent].data)) {
  97                 break;
  98             }
  99
 100             hvec[pos] = hvec[parent];
 101             hvec[pos].hnd_p->heap_index = pos;
 102             pos = parent;
 103         }
 104
 105         hvec[pos].hnd_p = ohndl;
 106         hvec[pos].data = op;
 107         ohndl->heap_index = pos;
 108
 109         return pos == 0;
 110     }
 111
 112     void bubble_up(hindex_t pos = 0) noexcept
 113     {
 114         P p = hvec[pos].data;
 115         handle_t &h = *(hvec[pos].hnd_p);
 116         bubble_up(pos, h, p);
 117     }
 118
 119     void bubble_up(hindex_t pos, handle_t &h, const P &p) noexcept
 120     {
 121         hindex_t rmax = hvec.size() - 1;
 122         if (rmax == 0) {
 123             return;
 124         }
 125
 126         Compare lt;
 127         hindex_t max = (rmax - 1) / N;
 128
 129         while (pos <= max) {
 130             hindex_t lchild = pos * N + 1;
 131             hindex_t selchild = lchild;
 132             hindex_t rchild = std::min(lchild + N, rmax);
 133             for (hindex_t i = lchild + 1; i < rchild; i++) {
 134                 if (lt(hvec[i].data, hvec[selchild].data)) {
 135                     selchild = i;
 136                 }
 137             }
 138
 139             if (! lt(hvec[selchild].data, p)) {
 140                 break;
 141             }
 142
 143             hvec[pos] = hvec[selchild];
 144             hvec[pos].hnd_p->heap_index = pos;
 145             pos = selchild;
 146         }
 147
 148         hvec[pos].hnd_p = &h;
 149         hvec[pos].data = p;
 150         h.heap_index = pos;
 151     }
 152
 153     void remove_h(hindex_t hidx) noexcept
 154     {
 155         hvec[hidx].hnd_p->heap_index = -1;
 156         if (hvec.size() != hidx + 1) {
 157             bubble_up(hidx, *(hvec.back().hnd_p), hvec.back().data);
 158             hvec.pop_back();
 159         }
 160         else {
 161             hvec.pop_back();
 162         }
 163     }
 164
 165     public:
 166
 167     T & node_data(handle_t & index) noexcept
 168     {
 169         return index.hd_u.hd;
 170     }
 171
 172     // Allocate a slot, but do not incorporate into the heap:
 173     //  u... : parameters for data constructor T::T(...)
 174     template <typename ...U> void allocate(handle_t & hnd, U... u)
 175     {
 176         new (& hnd.hd_u.hd) T(u...);
 177         hnd.heap_index = -1;
 178         constexpr hindex_t max_allowed = std::numeric_limits<hindex_t>::is_signed ?
 179                 std::numeric_limits<hindex_t>::max() : ((hindex_t) - 2);
 180
 181         if (num_nodes == max_allowed) {
 182             throw std::bad_alloc();
 183         }
 184
 185         num_nodes++;
 186
 187         if (__builtin_expect(hvec.capacity() < num_nodes, 0)) {
 188             hindex_t half_point = max_allowed / 2;
 189             try {
 190                 if (__builtin_expect(num_nodes < half_point, 1)) {
 191                     hvec.reserve(num_nodes * 2);
 192                 }
 193                 else {
 194                     hvec.reserve(max_allowed);
 195                 }
 196             }
 197             catch (std::bad_alloc &e) {
 198                 hvec.reserve(num_nodes);
 199             }
 200         }
 201     }
 202
 203     // Deallocate a slot
 204     void deallocate(handle_t & index) noexcept
 205     {
 206         num_nodes--;
 207         index.hd_u.hd.~T();
 208
 209         // shrink the capacity of hvec if num_nodes is sufficiently less than
 210         // its current capacity:
 211         if (num_nodes < hvec.capacity() / 4) {
 212             hvec.shrink_to(num_nodes * 2);
 213         }
 214     }
 215
 216     bool insert(handle_t & hnd) noexcept
 217     {
 218         P pval = P();
 219         return insert(hnd, pval);
 220     }
 221
 222     bool insert(handle_t & hnd, const P &pval) noexcept
 223     {
 224         hnd.heap_index = hvec.size();
 225         //hvec.emplace_back(&hnd, pval);
 226         hvec.emplace_back();
 227         return bubble_down(hvec.size() - 1, &hnd, pval);
 228     }
 229
 230     // Get the root node handle. (Returns a handle_t or reference to handle_t).
 231     handle_t & get_root()
 232     {
 233         return * hvec[0].hnd_p;
 234     }
 235
 236     P &get_root_priority()
 237     {
 238         return hvec[0].data;
 239     }
 240
 241     void pull_root()
 242     {
 243         remove_h(0);
 244     }
 245
 246     void remove(handle_t & hnd)
 247     {
 248         remove_h(hnd.heap_index);
 249     }
 250
 251     bool empty()
 252     {
 253         return hvec.empty();
 254     }
 255
 256     bool is_queued(handle_t & hnd)
 257     {
 258         return hnd.heap_index != (hindex_t) -1;
 259     }
 260
 261     // Set a node priority. Returns true iff the node becomes the root node (and wasn't before).
 262     bool set_priority(handle_t & hnd, const P& p)
 263     {
 264         int heap_index = hnd.heap_index;
 265
 266         Compare lt;
 267         if (lt(hvec[heap_index].data, p)) {
 268             // Increase key
 269             hvec[heap_index].data = p;
 270             bubble_up(heap_index);
 271             return false;
 272         }
 273         else {
 274             // Decrease key
 275             hvec[heap_index].data = p;
 276             return bubble_down(heap_index);
 277         }
 278     }
 279
 280     dary_heap() { }
 281
 282     dary_heap(const dary_heap &) = delete;
 283 };
 284
 285 }
 286
 287 #endif