]>
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.
7 * Author: J. Eric Ivancich <ivancich@redhat.com>
9 * This is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU Lesser General Public License version
11 * 2.1, as published by the Free Software Foundation. See file
30 using IndIntruHeapData
= size_t;
32 /* T is the ultimate data that's being stored in the heap, although
33 * through indirection.
35 * I is the indirect type that will actually be stored in the heap
36 * and that must allow dereferencing (via operator*) to yield a
39 * C is a functor when given two T&'s will return true if the first
40 * must precede the second.
42 * heap_info is a data member pointer as to where the heap data in T
45 * K is the branching factor of the heap, default is 2 (binary heap).
49 IndIntruHeapData
T::*heap_info
,
55 using HeapIndex
= IndIntruHeapData
;
58 std::is_same
<T
,typename
std::pointer_traits
<I
>::element_type
>::value
,
59 "class I must resolve to class T by indirection (pointer dereference)");
63 typename
std::result_of
<C(const T
&,const T
&)>::type
>::value
,
64 "class C must define operator() to take two const T& and return a bool");
66 static_assert(K
>= 2, "K (degree of branching) must be at least 2");
69 friend IndIntruHeap
<I
, T
, heap_info
, C
, K
>;
71 IndIntruHeap
<I
, T
, heap_info
, C
, K
>* heap
;
74 Iterator(IndIntruHeap
<I
, T
, heap_info
, C
, K
>& _heap
, HeapIndex _index
) :
83 Iterator(Iterator
&& other
) :
90 Iterator(const Iterator
& other
) :
97 Iterator
& operator=(Iterator
&& other
) {
98 std::swap(heap
, other
.heap
);
99 std::swap(index
, other
.index
);
103 Iterator
& operator=(const Iterator
& other
) {
108 Iterator
& operator++() {
109 if (index
<= heap
->count
) {
115 bool operator==(const Iterator
& other
) const {
116 return heap
== other
.heap
&& index
== other
.index
;
119 bool operator!=(const Iterator
& other
) const {
120 return !(*this == other
);
124 return *heap
->data
[index
];
128 return &(*heap
->data
[index
]);
132 // the item this iterator refers to
140 class ConstIterator
{
141 friend IndIntruHeap
<I
, T
, heap_info
, C
, K
>;
143 const IndIntruHeap
<I
, T
, heap_info
, C
, K
>* heap
;
146 ConstIterator(const IndIntruHeap
<I
, T
, heap_info
, C
, K
>& _heap
,
156 ConstIterator(ConstIterator
&& other
) :
163 ConstIterator(const ConstIterator
& other
) :
170 ConstIterator
& operator=(ConstIterator
&& other
) {
171 std::swap(heap
, other
.heap
);
172 std::swap(index
, other
.index
);
176 ConstIterator
& operator=(const ConstIterator
& other
) {
181 ConstIterator
& operator++() {
182 if (index
<= heap
->count
) {
188 bool operator==(const ConstIterator
& other
) const {
189 return heap
== other
.heap
&& index
== other
.index
;
192 bool operator!=(const ConstIterator
& other
) const {
193 return !(*this == other
);
196 const T
& operator*() {
197 return *heap
->data
[index
];
200 const T
* operator->() {
201 return &(*heap
->data
[index
]);
203 }; // class ConstIterator
220 IndIntruHeap(const IndIntruHeap
<I
,T
,heap_info
,C
,K
>& other
) :
223 for (HeapIndex i
= 0; i
< other
.count
; ++i
) {
224 data
.push_back(other
.data
[i
]);
228 bool empty() const { return 0 == count
; }
230 size_t size() const { return (size_t) count
; }
232 T
& top() { return *data
[0]; }
234 const T
& top() const { return *data
[0]; }
236 I
& top_ind() { return data
[0]; }
238 const I
& top_ind() const { return data
[0]; }
240 void push(I
&& item
) {
241 HeapIndex i
= count
++;
242 intru_data_of(item
) = i
;
243 data
.emplace_back(std::move(item
));
247 void push(const I
& item
) {
249 push(std::move(copy
));
253 remove(HeapIndex(0));
256 void remove(Iterator
& i
) {
261 Iterator
find(const I
& ind_item
) {
262 for (HeapIndex i
= 0; i
< count
; ++i
) {
263 if (data
[i
] == ind_item
) {
264 return Iterator(*this, i
);
270 // when passing in value we do a comparison via operator==
271 Iterator
find(const T
& item
) {
272 for (HeapIndex i
= 0; i
< count
; ++i
) {
273 if (*data
[i
] == item
) {
274 return Iterator(*this, i
);
280 // reverse find -- start looking from bottom of heap
281 Iterator
rfind(const I
& ind_item
) {
282 // HeapIndex is unsigned, so we can't allow to go negative; so
283 // we'll keep it one more than actual index
284 for (HeapIndex i
= count
; i
> 0; --i
) {
285 if (data
[i
-1] == ind_item
) {
286 return Iterator(*this, i
-1);
292 // reverse find -- start looking from bottom of heap
293 Iterator
rfind(const T
& item
) {
294 // HeapIndex is unsigned, so we can't allow to go negative; so
295 // we'll keep it one more than actual index
296 for (HeapIndex i
= count
; i
> 0; --i
) {
297 if (*data
[i
-1] == item
) {
298 return Iterator(*this, i
-1);
304 ConstIterator
find(const I
& ind_item
) const {
305 for (HeapIndex i
= 0; i
< count
; ++i
) {
306 if (data
[i
] == ind_item
) {
307 return ConstIterator(*this, i
);
313 // when passing in value we do a comparison via operator==
314 ConstIterator
find(const T
& item
) const {
315 for (HeapIndex i
= 0; i
< count
; ++i
) {
316 if (*data
[i
] == item
) {
317 return ConstIterator(*this, i
);
323 // reverse find -- start looking from bottom of heap
324 ConstIterator
rfind(const I
& ind_item
) const {
325 // HeapIndex is unsigned, so we can't allow to go negative; so
326 // we'll keep it one more than actual index
327 for (HeapIndex i
= count
; i
> 0; --i
) {
328 if (data
[i
-1] == ind_item
) {
329 return ConstIterator(*this, i
-1);
335 // reverse find -- start looking from bottom of heap
336 ConstIterator
rfind(const T
& item
) const {
337 // HeapIndex is unsigned, so we can't allow to go negative; so
338 // we'll keep it one more than actual index
339 for (HeapIndex i
= count
; i
> 0; --i
) {
340 if (*data
[i
-1] == item
) {
341 return ConstIterator(*this, i
-1);
347 Iterator
at(const I
& ind_item
) {
348 auto ind
= intru_data_of(ind_item
);
350 throw std::out_of_range(
351 std::to_string(ind
) + " >= " + std::to_string(count
));
353 assert(data
[ind
] == ind_item
);
354 return Iterator(*this, ind
);
357 void promote(T
& item
) {
358 sift_up(item
.*heap_info
);
361 void demote(T
& item
) {
362 sift_down(item
.*heap_info
);
365 void adjust(T
& item
) {
366 sift(item
.*heap_info
);
370 return Iterator(*this, 0);
374 return Iterator(*this, count
);
377 ConstIterator
cbegin() const {
378 return ConstIterator(*this, 0);
381 ConstIterator
cend() const {
382 return ConstIterator(*this, count
);
385 friend std::ostream
& operator<<(std::ostream
& out
, const IndIntruHeap
& h
) {
386 auto i
= h
.data
.cbegin();
387 if (i
!= h
.data
.cend()) {
390 while (i
!= h
.data
.cend()) {
397 // can only be called if I is copyable; copies heap into a vector
398 // and sorts it before displaying it
400 display_sorted(std::ostream
& out
,
401 std::function
<bool(const T
&)> filter
= all_filter
) const {
402 static_assert(std::is_copy_constructible
<I
>::value
,
403 "cannot call display_sorted when class I is not copy"
405 auto compare
= [this] (const I first
, const I second
) -> bool {
406 return this->comparator(*first
, *second
);
408 std::vector
<I
> copy(data
);
409 std::sort(copy
.begin(), copy
.end(), compare
);
412 for (auto c
= copy
.begin(); c
!= copy
.end(); ++c
) {
429 static IndIntruHeapData
& intru_data_of(const I
& item
) {
430 return (*item
).*heap_info
;
433 void remove(HeapIndex i
) {
434 std::swap(data
[i
], data
[--count
]);
435 intru_data_of(data
[i
]) = i
;
437 // the following needs to be sift (and not sift_down) as it can
438 // go up or down the heap; imagine the heap vector contains 0,
439 // 10, 100, 20, 30, 200, 300, 40; then 200 is removed, and 40
440 // would have to be sifted upwards
447 // default value of filter parameter to display_sorted
448 static bool all_filter(const T
& data
) { return true; }
450 // when i is negative?
451 static inline HeapIndex
parent(HeapIndex i
) {
456 // index of left child when K==2, index of left-most child when K>2
457 static inline HeapIndex
lhs(HeapIndex i
) { return K
*i
+ 1; }
459 // index of right child when K==2, index of right-most child when K>2
460 static inline HeapIndex
rhs(HeapIndex i
) { return K
*i
+ K
; }
462 void sift_up(HeapIndex i
) {
464 HeapIndex pi
= parent(i
);
465 if (!comparator(*data
[i
], *data
[pi
])) {
469 std::swap(data
[i
], data
[pi
]);
470 intru_data_of(data
[i
]) = i
;
471 intru_data_of(data
[pi
]) = pi
;
476 // use this sift_down definition when K>2; it's more general and
477 // uses a loop; EnableBool insures template uses a template
479 template<bool EnableBool
=true>
480 typename
std::enable_if
<(K
>2)&&EnableBool
,void>::type
sift_down(HeapIndex i
) {
481 if (i
>= count
) return;
483 HeapIndex li
= lhs(i
);
486 HeapIndex ri
= std::min(rhs(i
), count
- 1);
488 // find the index of min. child
489 HeapIndex min_i
= li
;
490 for (HeapIndex k
= li
+ 1; k
<= ri
; ++k
) {
491 if (comparator(*data
[k
], *data
[min_i
])) {
496 if (comparator(*data
[min_i
], *data
[i
])) {
497 std::swap(data
[i
], data
[min_i
]);
498 intru_data_of(data
[i
]) = i
;
499 intru_data_of(data
[min_i
]) = min_i
;
502 // no child is smaller
512 // use this sift_down definition when K==2; EnableBool insures
513 // template uses a template parameter
514 template<bool EnableBool
=true>
515 typename
std::enable_if
<K
==2&&EnableBool
,void>::type
sift_down(HeapIndex i
) {
516 if (i
>= count
) return;
518 const HeapIndex li
= lhs(i
);
519 const HeapIndex ri
= 1 + li
;
522 if (comparator(*data
[li
], *data
[i
])) {
523 if (ri
< count
&& comparator(*data
[ri
], *data
[li
])) {
524 std::swap(data
[i
], data
[ri
]);
525 intru_data_of(data
[i
]) = i
;
526 intru_data_of(data
[ri
]) = ri
;
529 std::swap(data
[i
], data
[li
]);
530 intru_data_of(data
[i
]) = i
;
531 intru_data_of(data
[li
]) = li
;
534 } else if (ri
< count
&& comparator(*data
[ri
], *data
[i
])) {
535 std::swap(data
[i
], data
[ri
]);
536 intru_data_of(data
[i
]) = i
;
537 intru_data_of(data
[ri
]) = ri
;
540 // no child is smaller
550 void sift(HeapIndex i
) {
552 // if we're at top, can only go down
555 HeapIndex pi
= parent(i
);
556 if (comparator(*data
[i
], *data
[pi
])) {
557 // if we can go up, we will
560 // otherwise we'll try to go down
565 }; // class IndIntruHeap
567 } // namespace crimson