LXR linux/include/linux/min

   1/* SPDX-License-Identifier: GPL-2.0 */
   2#ifndef _LINUX_MIN_HEAP_H
   3#define _LINUX_MIN_HEAP_H
   4
   5#include <linux/bug.h>
   6#include <linux/string.h>
   7#include <linux/types.h>
   8
   9/**
  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.
  14 */
  15struct min_heap {
  16        void *data;
  17        int nr;
  18        int size;
  19};
  20
  21/**
  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.
  26 */
  27struct min_heap_callbacks {
  28        int elem_size;
  29        bool (*less)(const void *lhs, const void *rhs);
  30        void (*swp)(void *lhs, void *rhs);
  31};
  32
  33/* Sift the element at pos down the heap. */
  34static __always_inline
  35void min_heapify(struct min_heap *heap, int pos,
  36                const struct min_heap_callbacks *func)
  37{
  38        void *left, *right, *parent, *smallest;
  39        void *data = heap->data;
  40
  41        for (;;) {
  42                if (pos * 2 + 1 >= heap->nr)
  43                        break;
  44
  45                left = data + ((pos * 2 + 1) * func->elem_size);
  46                parent = data + (pos * func->elem_size);
  47                smallest = parent;
  48                if (func->less(left, smallest))
  49                        smallest = left;
  50
  51                if (pos * 2 + 2 < heap->nr) {
  52                        right = data + ((pos * 2 + 2) * func->elem_size);
  53                        if (func->less(right, smallest))
  54                                smallest = right;
  55                }
  56                if (smallest == parent)
  57                        break;
  58                func->swp(smallest, parent);
  59                if (smallest == left)
  60                        pos = (pos * 2) + 1;
  61                else
  62                        pos = (pos * 2) + 2;
  63        }
  64}
  65
  66/* Floyd's approach to heapification that is O(nr). */
  67static __always_inline
  68void min_heapify_all(struct min_heap *heap,
  69                const struct min_heap_callbacks *func)
  70{
  71        int i;
  72
  73        for (i = heap->nr / 2; i >= 0; i--)
  74                min_heapify(heap, i, func);
  75}
  76
  77/* Remove minimum element from the heap, O(log2(nr)). */
  78static __always_inline
  79void min_heap_pop(struct min_heap *heap,
  80                const struct min_heap_callbacks *func)
  81{
  82        void *data = heap->data;
  83
  84        if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap"))
  85                return;
  86
  87        /* Place last element at the root (position 0) and then sift down. */
  88        heap->nr--;
  89        memcpy(data, data + (heap->nr * func->elem_size), func->elem_size);
  90        min_heapify(heap, 0, func);
  91}
  92
  93/*
  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.
  97 */
  98static __always_inline
  99void min_heap_pop_push(struct min_heap *heap,
 100                const void *element,
 101                const struct min_heap_callbacks *func)
 102{
 103        memcpy(heap->data, element, func->elem_size);
 104        min_heapify(heap, 0, func);
 105}
 106
 107/* Push an element on to the heap, O(log2(nr)). */
 108static __always_inline
 109void min_heap_push(struct min_heap *heap, const void *element,
 110                const struct min_heap_callbacks *func)
 111{
 112        void *data = heap->data;
 113        void *child, *parent;
 114        int pos;
 115
 116        if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap"))
 117                return;
 118
 119        /* Place at the end of data. */
 120        pos = heap->nr;
 121        memcpy(data + (pos * func->elem_size), element, func->elem_size);
 122        heap->nr++;
 123
 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))
 129                        break;
 130                func->swp(parent, child);
 131        }
 132}
 133
 134#endif /* _LINUX_MIN_HEAP_H */
 135