]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - include/linux/min_heap.h
1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef _LINUX_MIN_HEAP_H
3 #define _LINUX_MIN_HEAP_H
6 #include <linux/string.h>
7 #include <linux/types.h>
10 * struct min_heap - Data structure to hold a min-heap.
11 * @data: Start of array holding the heap elements.
12 * @nr: Number of elements currently in the heap.
13 * @size: Maximum number of elements that can be held in current storage.
22 * struct min_heap_callbacks - Data/functions to customise the min_heap.
23 * @elem_size: The nr of each element in bytes.
24 * @less: Partial order function for this heap.
25 * @swp: Swap elements function.
27 struct min_heap_callbacks
{
29 bool (*less
)(const void *lhs
, const void *rhs
);
30 void (*swp
)(void *lhs
, void *rhs
);
33 /* Sift the element at pos down the heap. */
34 static __always_inline
35 void min_heapify(struct min_heap
*heap
, int pos
,
36 const struct min_heap_callbacks
*func
)
38 void *left
, *right
, *parent
, *smallest
;
39 void *data
= heap
->data
;
42 if (pos
* 2 + 1 >= heap
->nr
)
45 left
= data
+ ((pos
* 2 + 1) * func
->elem_size
);
46 parent
= data
+ (pos
* func
->elem_size
);
48 if (func
->less(left
, smallest
))
51 if (pos
* 2 + 2 < heap
->nr
) {
52 right
= data
+ ((pos
* 2 + 2) * func
->elem_size
);
53 if (func
->less(right
, smallest
))
56 if (smallest
== parent
)
58 func
->swp(smallest
, parent
);
66 /* Floyd's approach to heapification that is O(nr). */
67 static __always_inline
68 void min_heapify_all(struct min_heap
*heap
,
69 const struct min_heap_callbacks
*func
)
73 for (i
= heap
->nr
/ 2; i
>= 0; i
--)
74 min_heapify(heap
, i
, func
);
77 /* Remove minimum element from the heap, O(log2(nr)). */
78 static __always_inline
79 void min_heap_pop(struct min_heap
*heap
,
80 const struct min_heap_callbacks
*func
)
82 void *data
= heap
->data
;
84 if (WARN_ONCE(heap
->nr
<= 0, "Popping an empty heap"))
87 /* Place last element at the root (position 0) and then sift down. */
89 memcpy(data
, data
+ (heap
->nr
* func
->elem_size
), func
->elem_size
);
90 min_heapify(heap
, 0, func
);
94 * Remove the minimum element and then push the given element. The
95 * implementation performs 1 sift (O(log2(nr))) and is therefore more
96 * efficient than a pop followed by a push that does 2.
98 static __always_inline
99 void min_heap_pop_push(struct min_heap
*heap
,
101 const struct min_heap_callbacks
*func
)
103 memcpy(heap
->data
, element
, func
->elem_size
);
104 min_heapify(heap
, 0, func
);
107 /* Push an element on to the heap, O(log2(nr)). */
108 static __always_inline
109 void min_heap_push(struct min_heap
*heap
, const void *element
,
110 const struct min_heap_callbacks
*func
)
112 void *data
= heap
->data
;
113 void *child
, *parent
;
116 if (WARN_ONCE(heap
->nr
>= heap
->size
, "Pushing on a full heap"))
119 /* Place at the end of data. */
121 memcpy(data
+ (pos
* func
->elem_size
), element
, func
->elem_size
);
124 /* Sift child at pos up. */
125 for (; pos
> 0; pos
= (pos
- 1) / 2) {
126 child
= data
+ (pos
* func
->elem_size
);
127 parent
= data
+ ((pos
- 1) / 2) * func
->elem_size
;
128 if (func
->less(parent
, child
))
130 func
->swp(parent
, child
);
134 #endif /* _LINUX_MIN_HEAP_H */