include/linux/min_heap.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 #ifndef _LINUX_MIN_HEAP_H
0003 #define _LINUX_MIN_HEAP_H
0004
0005 #include <linux/bug.h>
0006 #include <linux/string.h>
0007 #include <linux/types.h>
0008
0009 /**
0010  * struct min_heap - Data structure to hold a min-heap.
0011  * @data: Start of array holding the heap elements.
0012  * @nr: Number of elements currently in the heap.
0013  * @size: Maximum number of elements that can be held in current storage.
0014  */
0015 struct min_heap {
0016     void *data;
0017     int nr;
0018     int size;
0019 };
0020
0021 /**
0022  * struct min_heap_callbacks - Data/functions to customise the min_heap.
0023  * @elem_size: The nr of each element in bytes.
0024  * @less: Partial order function for this heap.
0025  * @swp: Swap elements function.
0026  */
0027 struct min_heap_callbacks {
0028     int elem_size;
0029     bool (*less)(const void *lhs, const void *rhs);
0030     void (*swp)(void *lhs, void *rhs);
0031 };
0032
0033 /* Sift the element at pos down the heap. */
0034 static __always_inline
0035 void min_heapify(struct min_heap *heap, int pos,
0036         const struct min_heap_callbacks *func)
0037 {
0038     void *left, *right, *parent, *smallest;
0039     void *data = heap->data;
0040
0041     for (;;) {
0042         if (pos * 2 + 1 >= heap->nr)
0043             break;
0044
0045         left = data + ((pos * 2 + 1) * func->elem_size);
0046         parent = data + (pos * func->elem_size);
0047         smallest = parent;
0048         if (func->less(left, smallest))
0049             smallest = left;
0050
0051         if (pos * 2 + 2 < heap->nr) {
0052             right = data + ((pos * 2 + 2) * func->elem_size);
0053             if (func->less(right, smallest))
0054                 smallest = right;
0055         }
0056         if (smallest == parent)
0057             break;
0058         func->swp(smallest, parent);
0059         if (smallest == left)
0060             pos = (pos * 2) + 1;
0061         else
0062             pos = (pos * 2) + 2;
0063     }
0064 }
0065
0066 /* Floyd's approach to heapification that is O(nr). */
0067 static __always_inline
0068 void min_heapify_all(struct min_heap *heap,
0069         const struct min_heap_callbacks *func)
0070 {
0071     int i;
0072
0073     for (i = heap->nr / 2; i >= 0; i--)
0074         min_heapify(heap, i, func);
0075 }
0076
0077 /* Remove minimum element from the heap, O(log2(nr)). */
0078 static __always_inline
0079 void min_heap_pop(struct min_heap *heap,
0080         const struct min_heap_callbacks *func)
0081 {
0082     void *data = heap->data;
0083
0084     if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap"))
0085         return;
0086
0087     /* Place last element at the root (position 0) and then sift down. */
0088     heap->nr--;
0089     memcpy(data, data + (heap->nr * func->elem_size), func->elem_size);
0090     min_heapify(heap, 0, func);
0091 }
0092
0093 /*
0094  * Remove the minimum element and then push the given element. The
0095  * implementation performs 1 sift (O(log2(nr))) and is therefore more
0096  * efficient than a pop followed by a push that does 2.
0097  */
0098 static __always_inline
0099 void min_heap_pop_push(struct min_heap *heap,
0100         const void *element,
0101         const struct min_heap_callbacks *func)
0102 {
0103     memcpy(heap->data, element, func->elem_size);
0104     min_heapify(heap, 0, func);
0105 }
0106
0107 /* Push an element on to the heap, O(log2(nr)). */
0108 static __always_inline
0109 void min_heap_push(struct min_heap *heap, const void *element,
0110         const struct min_heap_callbacks *func)
0111 {
0112     void *data = heap->data;
0113     void *child, *parent;
0114     int pos;
0115
0116     if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap"))
0117         return;
0118
0119     /* Place at the end of data. */
0120     pos = heap->nr;
0121     memcpy(data + (pos * func->elem_size), element, func->elem_size);
0122     heap->nr++;
0123
0124     /* Sift child at pos up. */
0125     for (; pos > 0; pos = (pos - 1) / 2) {
0126         child = data + (pos * func->elem_size);
0127         parent = data + ((pos - 1) / 2) * func->elem_size;
0128         if (func->less(parent, child))
0129             break;
0130         func->swp(parent, child);
0131     }
0132 }
0133
0134 #endif /* _LINUX_MIN_HEAP_H */