]>
git.proxmox.com Git - ceph.git/blob - ceph/src/dmclock/support/src/indirect_intrusive_heap.h
1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
5 * Copyright (C) 2016 Red Hat Inc.
23 using IndIntruHeapData
= size_t;
25 /* T is the ultimate data that's being stored in the heap, although
26 * through indirection.
28 * I is the indirect type that will actually be stored in the heap
29 * and that must allow dereferencing (via operator*) to yield a
32 * C is a functor when given two T&'s will return true if the first
33 * must precede the second.
35 * heap_info is a data member pointer as to where the heap data in T
38 * K is the branching factor of the heap, default is 2 (binary heap).
42 IndIntruHeapData
T::*heap_info
,
48 using HeapIndex
= IndIntruHeapData
;
51 std::is_same
<T
,typename
std::pointer_traits
<I
>::element_type
>::value
,
52 "class I must resolve to class T by indirection (pointer dereference)");
56 typename
std::result_of
<C(const T
&,const T
&)>::type
>::value
,
57 "class C must define operator() to take two const T& and return a bool");
59 static_assert(K
>= 2, "K (degree of branching) must be at least 2");
62 friend IndIntruHeap
<I
, T
, heap_info
, C
, K
>;
64 IndIntruHeap
<I
, T
, heap_info
, C
, K
>& heap
;
67 Iterator(IndIntruHeap
<I
, T
, heap_info
, C
, K
>& _heap
, HeapIndex _index
) :
76 Iterator(Iterator
&& other
) :
83 Iterator(const Iterator
& other
) :
90 Iterator
& operator=(Iterator
&& other
) {
91 std::swap(heap
, other
.heap
);
92 std::swap(index
, other
.index
);
96 Iterator
& operator=(const Iterator
& other
) {
101 Iterator
& operator++() {
102 if (index
<= heap
.count
) {
108 bool operator==(const Iterator
& other
) const {
109 return &heap
== &other
.heap
&& index
== other
.index
;
112 bool operator!=(const Iterator
& other
) const {
113 return !(*this == other
);
117 return *heap
.data
[index
];
121 return &(*heap
.data
[index
]);
125 // the item this iterator refers to
133 class ConstIterator
{
134 friend IndIntruHeap
<I
, T
, heap_info
, C
, K
>;
136 const IndIntruHeap
<I
, T
, heap_info
, C
, K
>& heap
;
139 ConstIterator(const IndIntruHeap
<I
, T
, heap_info
, C
, K
>& _heap
,
149 ConstIterator(ConstIterator
&& other
) :
156 ConstIterator(const ConstIterator
& other
) :
163 ConstIterator
& operator=(ConstIterator
&& other
) {
164 std::swap(heap
, other
.heap
);
165 std::swap(index
, other
.index
);
169 ConstIterator
& operator=(const ConstIterator
& other
) {
174 ConstIterator
& operator++() {
175 if (index
<= heap
.count
) {
181 bool operator==(const ConstIterator
& other
) const {
182 return &heap
== &other
.heap
&& index
== other
.index
;
185 bool operator!=(const ConstIterator
& other
) const {
186 return !(*this == other
);
189 const T
& operator*() {
190 return *heap
.data
[index
];
193 const T
* operator->() {
194 return &(*heap
.data
[index
]);
196 }; // class ConstIterator
213 IndIntruHeap(const IndIntruHeap
<I
,T
,heap_info
,C
,K
>& other
) :
216 for (HeapIndex i
= 0; i
< other
.count
; ++i
) {
217 data
.push_back(other
.data
[i
]);
221 bool empty() const { return 0 == count
; }
223 size_t size() const { return (size_t) count
; }
225 T
& top() { return *data
[0]; }
227 const T
& top() const { return *data
[0]; }
229 I
& top_ind() { return data
[0]; }
231 const I
& top_ind() const { return data
[0]; }
233 void push(I
&& item
) {
234 HeapIndex i
= count
++;
235 intru_data_of(item
) = i
;
236 data
.emplace_back(std::move(item
));
240 void push(const I
& item
) {
242 push(std::move(copy
));
246 remove(HeapIndex(0));
249 void remove(Iterator
& i
) {
254 Iterator
find(const I
& ind_item
) {
255 for (HeapIndex i
= 0; i
< count
; ++i
) {
256 if (data
[i
] == ind_item
) {
257 return Iterator(*this, i
);
263 // when passing in value we do a comparison via operator==
264 Iterator
find(const T
& item
) {
265 for (HeapIndex i
= 0; i
< count
; ++i
) {
266 if (*data
[i
] == item
) {
267 return Iterator(*this, i
);
273 // reverse find -- start looking from bottom of heap
274 Iterator
rfind(const I
& ind_item
) {
275 // HeapIndex is unsigned, so we can't allow to go negative; so
276 // we'll keep it one more than actual index
277 for (HeapIndex i
= count
; i
> 0; --i
) {
278 if (data
[i
-1] == ind_item
) {
279 return Iterator(*this, i
-1);
285 // reverse find -- start looking from bottom of heap
286 Iterator
rfind(const T
& item
) {
287 // HeapIndex is unsigned, so we can't allow to go negative; so
288 // we'll keep it one more than actual index
289 for (HeapIndex i
= count
; i
> 0; --i
) {
290 if (*data
[i
-1] == item
) {
291 return Iterator(*this, i
-1);
297 ConstIterator
find(const I
& ind_item
) const {
298 for (HeapIndex i
= 0; i
< count
; ++i
) {
299 if (data
[i
] == ind_item
) {
300 return ConstIterator(*this, i
);
306 // when passing in value we do a comparison via operator==
307 ConstIterator
find(const T
& item
) const {
308 for (HeapIndex i
= 0; i
< count
; ++i
) {
309 if (*data
[i
] == item
) {
310 return ConstIterator(*this, i
);
316 // reverse find -- start looking from bottom of heap
317 ConstIterator
rfind(const I
& ind_item
) const {
318 // HeapIndex is unsigned, so we can't allow to go negative; so
319 // we'll keep it one more than actual index
320 for (HeapIndex i
= count
; i
> 0; --i
) {
321 if (data
[i
-1] == ind_item
) {
322 return ConstIterator(*this, i
-1);
328 // reverse find -- start looking from bottom of heap
329 ConstIterator
rfind(const T
& item
) const {
330 // HeapIndex is unsigned, so we can't allow to go negative; so
331 // we'll keep it one more than actual index
332 for (HeapIndex i
= count
; i
> 0; --i
) {
333 if (*data
[i
-1] == item
) {
334 return ConstIterator(*this, i
-1);
340 void promote(T
& item
) {
341 sift_up(item
.*heap_info
);
344 void demote(T
& item
) {
345 sift_down(item
.*heap_info
);
348 void adjust(T
& item
) {
349 sift(item
.*heap_info
);
353 return Iterator(*this, 0);
357 return Iterator(*this, count
);
360 ConstIterator
cbegin() const {
361 return ConstIterator(*this, 0);
364 ConstIterator
cend() const {
365 return ConstIterator(*this, count
);
368 friend std::ostream
& operator<<(std::ostream
& out
, const IndIntruHeap
& h
) {
369 auto i
= h
.data
.cbegin();
370 if (i
!= h
.data
.cend()) {
373 while (i
!= h
.data
.cend()) {
380 // can only be called if I is copyable; copies heap into a vector
381 // and sorts it before displaying it
383 display_sorted(std::ostream
& out
,
384 std::function
<bool(const T
&)> filter
= all_filter
) const {
385 static_assert(std::is_copy_constructible
<I
>::value
,
386 "cannot call display_sorted when class I is not copy"
388 auto compare
= [this] (const I first
, const I second
) -> bool {
389 return this->comparator(*first
, *second
);
391 std::vector
<I
> copy(data
);
392 std::sort(copy
.begin(), copy
.end(), compare
);
395 for (auto c
= copy
.begin(); c
!= copy
.end(); ++c
) {
412 static IndIntruHeapData
& intru_data_of(I
& item
) {
413 return (*item
).*heap_info
;
416 void remove(HeapIndex i
) {
417 std::swap(data
[i
], data
[--count
]);
418 intru_data_of(data
[i
]) = i
;
421 // the following needs to be sift (and not sift_down) as it can
422 // go up or down the heap; imagine the heap vector contains 0,
423 // 10, 100, 20, 30, 200, 300, 40; then 200 is removed, and 40
424 // would have to be sifted upwards
429 // default value of filter parameter to display_sorted
430 static bool all_filter(const T
& data
) { return true; }
432 // when i is negative?
433 static inline HeapIndex
parent(HeapIndex i
) {
438 // index of left child when K==2, index of left-most child when K>2
439 static inline HeapIndex
lhs(HeapIndex i
) { return K
*i
+ 1; }
441 // index of right child when K==2, index of right-most child when K>2
442 static inline HeapIndex
rhs(HeapIndex i
) { return K
*i
+ K
; }
444 void sift_up(HeapIndex i
) {
446 HeapIndex pi
= parent(i
);
447 if (!comparator(*data
[i
], *data
[pi
])) {
451 std::swap(data
[i
], data
[pi
]);
452 intru_data_of(data
[i
]) = i
;
453 intru_data_of(data
[pi
]) = pi
;
458 // use this sift_down definition when K>2; it's more general and
459 // uses a loop; EnableBool insures template uses a template
461 template<bool EnableBool
=true>
462 typename
std::enable_if
<(K
>2)&&EnableBool
,void>::type
sift_down(HeapIndex i
) {
463 if (i
>= count
) return;
465 HeapIndex li
= lhs(i
);
468 HeapIndex ri
= std::min(rhs(i
), count
- 1);
470 // find the index of min. child
471 HeapIndex min_i
= li
;
472 for (HeapIndex k
= li
+ 1; k
<= ri
; ++k
) {
473 if (comparator(*data
[k
], *data
[min_i
])) {
478 if (comparator(*data
[min_i
], *data
[i
])) {
479 std::swap(data
[i
], data
[min_i
]);
480 intru_data_of(data
[i
]) = i
;
481 intru_data_of(data
[min_i
]) = min_i
;
484 // no child is smaller
494 // use this sift_down definition when K==2; EnableBool insures
495 // template uses a template parameter
496 template<bool EnableBool
=true>
497 typename
std::enable_if
<K
==2&&EnableBool
,void>::type
sift_down(HeapIndex i
) {
498 if (i
>= count
) return;
500 const HeapIndex li
= lhs(i
);
501 const HeapIndex ri
= 1 + li
;
504 if (comparator(*data
[li
], *data
[i
])) {
505 if (ri
< count
&& comparator(*data
[ri
], *data
[li
])) {
506 std::swap(data
[i
], data
[ri
]);
507 intru_data_of(data
[i
]) = i
;
508 intru_data_of(data
[ri
]) = ri
;
511 std::swap(data
[i
], data
[li
]);
512 intru_data_of(data
[i
]) = i
;
513 intru_data_of(data
[li
]) = li
;
516 } else if (ri
< count
&& comparator(*data
[ri
], *data
[i
])) {
517 std::swap(data
[i
], data
[ri
]);
518 intru_data_of(data
[i
]) = i
;
519 intru_data_of(data
[ri
]) = ri
;
522 // no child is smaller
532 void sift(HeapIndex i
) {
534 // if we're at top, can only go down
537 HeapIndex pi
= parent(i
);
538 if (comparator(*data
[i
], *data
[pi
])) {
539 // if we can go up, we will
542 // otherwise we'll try to go down
547 }; // class IndIntruHeap
549 } // namespace crimson