| Message ID | 20240406164727.577914-10-visitorckw@gmail.com (mailing list archive) |
|---|---|
| State | Not Applicable, archived |
| Delegated to: | Mike Snitzer |
| Headers | show |
| Series | treewide: Refactor heap related implementation | expand |
On Sat, Apr 6, 2024 at 9:48 AM Kuan-Wei Chiu <visitorckw@gmail.com> wrote: > > Add min_heap_sift_up() to sift up the element at index 'idx' in the > heap. > > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> Reviewed-by: Ian Rogers <irogers@google.com> Thanks, Ian > --- > include/linux/min_heap.h | 20 ++++++++++++++++++++ > 1 file changed, 20 insertions(+) > > diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h > index 9391f7cc9da9..201f59cb3558 100644 > --- a/include/linux/min_heap.h > +++ b/include/linux/min_heap.h > @@ -111,6 +111,26 @@ void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, > #define min_heapify(_heap, _pos, _func, _args) \ > __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) > > +/* Sift up ith element from the heap, O(log2(nr)). */ > +static __always_inline > +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, > + const struct min_heap_callbacks *func, void *args) > +{ > + void *data = heap->data; > + size_t parent; > + > + while (idx) { > + parent = (idx - 1) / 2; > + if (func->less(data + parent * elem_size, data + idx * elem_size, args)) > + break; > + func->swp(data + parent * elem_size, data + idx * elem_size, args); > + idx = parent; > + } > +} > + > +#define min_heap_sift_up(_heap, _idx, _func, _args) \ > + __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args) > + > /* Floyd's approach to heapification that is O(nr). */ > static __always_inline > void __min_heapify_all(min_heap_char *heap, size_t elem_size, > -- > 2.34.1 >
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 9391f7cc9da9..201f59cb3558 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -111,6 +111,26 @@ void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, #define min_heapify(_heap, _pos, _func, _args) \ __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) +/* Sift up ith element from the heap, O(log2(nr)). */ +static __always_inline +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data = heap->data; + size_t parent; + + while (idx) { + parent = (idx - 1) / 2; + if (func->less(data + parent * elem_size, data + idx * elem_size, args)) + break; + func->swp(data + parent * elem_size, data + idx * elem_size, args); + idx = parent; + } +} + +#define min_heap_sift_up(_heap, _idx, _func, _args) \ + __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size,
Add min_heap_sift_up() to sift up the element at index 'idx' in the heap. Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> --- include/linux/min_heap.h | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+)