summaryrefslogtreecommitdiff
path: root/include/linux/min_heap.h
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2025-01-26 17:50:53 -0800
committerLinus Torvalds <torvalds@linux-foundation.org>2025-01-26 17:50:53 -0800
commitc159dfbdd4fc62fa08f6715d9d6c34d39cf40446 (patch)
tree42d85c4b5ccd860172ecda273765356830a9ff74 /include/linux/min_heap.h
parentbaf29cc16e18e621a05340695d333fa5d0d001ce (diff)
parentbeeba1eeec9c75d0a62335861ac175b9bdccfbd5 (diff)
Merge tag 'mm-nonmm-stable-2025-01-24-23-16' of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Pull non-MM updates from Andrew Morton: "Mainly individually changelogged singleton patches. The patch series in this pull are: - "lib min_heap: Improve min_heap safety, testing, and documentation" from Kuan-Wei Chiu provides various tightenings to the min_heap library code - "xarray: extract __xa_cmpxchg_raw" from Tamir Duberstein preforms some cleanup and Rust preparation in the xarray library code - "Update reference to include/asm-<arch>" from Geert Uytterhoeven fixes pathnames in some code comments - "Converge on using secs_to_jiffies()" from Easwar Hariharan uses the new secs_to_jiffies() in various places where that is appropriate - "ocfs2, dlmfs: convert to the new mount API" from Eric Sandeen switches two filesystems to the new mount API - "Convert ocfs2 to use folios" from Matthew Wilcox does that - "Remove get_task_comm() and print task comm directly" from Yafang Shao removes now-unneeded calls to get_task_comm() in various places - "squashfs: reduce memory usage and update docs" from Phillip Lougher implements some memory savings in squashfs and performs some maintainability work - "lib: clarify comparison function requirements" from Kuan-Wei Chiu tightens the sort code's behaviour and adds some maintenance work - "nilfs2: protect busy buffer heads from being force-cleared" from Ryusuke Konishi fixes an issues in nlifs when the fs is presented with a corrupted image - "nilfs2: fix kernel-doc comments for function return values" from Ryusuke Konishi fixes some nilfs kerneldoc - "nilfs2: fix issues with rename operations" from Ryusuke Konishi addresses some nilfs BUG_ONs which syzbot was able to trigger - "minmax.h: Cleanups and minor optimisations" from David Laight does some maintenance work on the min/max library code - "Fixes and cleanups to xarray" from Kemeng Shi does maintenance work on the xarray library code" * tag 'mm-nonmm-stable-2025-01-24-23-16' of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm: (131 commits) ocfs2: use str_yes_no() and str_no_yes() helper functions include/linux/lz4.h: add some missing macros Xarray: use xa_mark_t in xas_squash_marks() to keep code consistent Xarray: remove repeat check in xas_squash_marks() Xarray: distinguish large entries correctly in xas_split_alloc() Xarray: move forward index correctly in xas_pause() Xarray: do not return sibling entries from xas_find_marked() ipc/util.c: complete the kernel-doc function descriptions gcov: clang: use correct function param names latencytop: use correct kernel-doc format for func params minmax.h: remove some #defines that are only expanded once minmax.h: simplify the variants of clamp() minmax.h: move all the clamp() definitions after the min/max() ones minmax.h: use BUILD_BUG_ON_MSG() for the lo < hi test in clamp() minmax.h: reduce the #define expansion of min(), max() and clamp() minmax.h: update some comments minmax.h: add whitespace around operators and after commas nilfs2: do not update mtime of renamed directory that is not moved nilfs2: handle errors that nilfs_prepare_chunk() may return CREDITS: fix spelling mistake ...
Diffstat (limited to 'include/linux/min_heap.h')
-rw-r--r--include/linux/min_heap.h72
1 files changed, 46 insertions, 26 deletions
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
index 6325f6ffb895..1160bed6579e 100644
--- a/include/linux/min_heap.h
+++ b/include/linux/min_heap.h
@@ -6,6 +6,17 @@
#include <linux/string.h>
#include <linux/types.h>
+/*
+ * The Min Heap API provides utilities for managing min-heaps, a binary tree
+ * structure where each node's value is less than or equal to its children's
+ * values, ensuring the smallest element is at the root.
+ *
+ * Users should avoid directly calling functions prefixed with __min_heap_*().
+ * Instead, use the provided macro wrappers.
+ *
+ * For further details and examples, refer to Documentation/core-api/min_heap.rst.
+ */
+
/**
* Data structure to hold a min-heap.
* @nr: Number of elements currently in the heap.
@@ -218,7 +229,7 @@ void __min_heap_init_inline(min_heap_char *heap, void *data, int size)
}
#define min_heap_init_inline(_heap, _data, _size) \
- __min_heap_init_inline((min_heap_char *)_heap, _data, _size)
+ __min_heap_init_inline(container_of(&(_heap)->nr, min_heap_char, nr), _data, _size)
/* Get the minimum element from the heap. */
static __always_inline
@@ -228,7 +239,8 @@ void *__min_heap_peek_inline(struct min_heap_char *heap)
}
#define min_heap_peek_inline(_heap) \
- (__minheap_cast(_heap) __min_heap_peek_inline((min_heap_char *)_heap))
+ (__minheap_cast(_heap) \
+ __min_heap_peek_inline(container_of(&(_heap)->nr, min_heap_char, nr)))
/* Check if the heap is full. */
static __always_inline
@@ -238,7 +250,7 @@ bool __min_heap_full_inline(min_heap_char *heap)
}
#define min_heap_full_inline(_heap) \
- __min_heap_full_inline((min_heap_char *)_heap)
+ __min_heap_full_inline(container_of(&(_heap)->nr, min_heap_char, nr))
/* Sift the element at pos down the heap. */
static __always_inline
@@ -277,8 +289,8 @@ void __min_heap_sift_down_inline(min_heap_char *heap, int pos, size_t elem_size,
}
#define min_heap_sift_down_inline(_heap, _pos, _func, _args) \
- __min_heap_sift_down_inline((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), \
- _func, _args)
+ __min_heap_sift_down_inline(container_of(&(_heap)->nr, min_heap_char, nr), _pos, \
+ __minheap_obj_size(_heap), _func, _args)
/* Sift up ith element from the heap, O(log2(nr)). */
static __always_inline
@@ -304,8 +316,8 @@ void __min_heap_sift_up_inline(min_heap_char *heap, size_t elem_size, size_t idx
}
#define min_heap_sift_up_inline(_heap, _idx, _func, _args) \
- __min_heap_sift_up_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, \
- _func, _args)
+ __min_heap_sift_up_inline(container_of(&(_heap)->nr, min_heap_char, nr), \
+ __minheap_obj_size(_heap), _idx, _func, _args)
/* Floyd's approach to heapification that is O(nr). */
static __always_inline
@@ -319,7 +331,8 @@ void __min_heapify_all_inline(min_heap_char *heap, size_t elem_size,
}
#define min_heapify_all_inline(_heap, _func, _args) \
- __min_heapify_all_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
+ __min_heapify_all_inline(container_of(&(_heap)->nr, min_heap_char, nr), \
+ __minheap_obj_size(_heap), _func, _args)
/* Remove minimum element from the heap, O(log2(nr)). */
static __always_inline
@@ -340,7 +353,8 @@ bool __min_heap_pop_inline(min_heap_char *heap, size_t elem_size,
}
#define min_heap_pop_inline(_heap, _func, _args) \
- __min_heap_pop_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
+ __min_heap_pop_inline(container_of(&(_heap)->nr, min_heap_char, nr), \
+ __minheap_obj_size(_heap), _func, _args)
/*
* Remove the minimum element and then push the given element. The
@@ -356,8 +370,8 @@ void __min_heap_pop_push_inline(min_heap_char *heap, const void *element, size_t
}
#define min_heap_pop_push_inline(_heap, _element, _func, _args) \
- __min_heap_pop_push_inline((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), \
- _func, _args)
+ __min_heap_pop_push_inline(container_of(&(_heap)->nr, min_heap_char, nr), _element, \
+ __minheap_obj_size(_heap), _func, _args)
/* Push an element on to the heap, O(log2(nr)). */
static __always_inline
@@ -382,8 +396,8 @@ bool __min_heap_push_inline(min_heap_char *heap, const void *element, size_t ele
}
#define min_heap_push_inline(_heap, _element, _func, _args) \
- __min_heap_push_inline((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), \
- _func, _args)
+ __min_heap_push_inline(container_of(&(_heap)->nr, min_heap_char, nr), _element, \
+ __minheap_obj_size(_heap), _func, _args)
/* Remove ith element from the heap, O(log2(nr)). */
static __always_inline
@@ -411,8 +425,8 @@ bool __min_heap_del_inline(min_heap_char *heap, size_t elem_size, size_t idx,
}
#define min_heap_del_inline(_heap, _idx, _func, _args) \
- __min_heap_del_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, \
- _func, _args)
+ __min_heap_del_inline(container_of(&(_heap)->nr, min_heap_char, nr), \
+ __minheap_obj_size(_heap), _idx, _func, _args)
void __min_heap_init(min_heap_char *heap, void *data, int size);
void *__min_heap_peek(struct min_heap_char *heap);
@@ -433,25 +447,31 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,
const struct min_heap_callbacks *func, void *args);
#define min_heap_init(_heap, _data, _size) \
- __min_heap_init((min_heap_char *)_heap, _data, _size)
+ __min_heap_init(container_of(&(_heap)->nr, min_heap_char, nr), _data, _size)
#define min_heap_peek(_heap) \
- (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap))
+ (__minheap_cast(_heap) __min_heap_peek(container_of(&(_heap)->nr, min_heap_char, nr)))
#define min_heap_full(_heap) \
- __min_heap_full((min_heap_char *)_heap)
+ __min_heap_full(container_of(&(_heap)->nr, min_heap_char, nr))
#define min_heap_sift_down(_heap, _pos, _func, _args) \
- __min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args)
+ __min_heap_sift_down(container_of(&(_heap)->nr, min_heap_char, nr), _pos, \
+ __minheap_obj_size(_heap), _func, _args)
#define min_heap_sift_up(_heap, _idx, _func, _args) \
- __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args)
+ __min_heap_sift_up(container_of(&(_heap)->nr, min_heap_char, nr), \
+ __minheap_obj_size(_heap), _idx, _func, _args)
#define min_heapify_all(_heap, _func, _args) \
- __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
+ __min_heapify_all(container_of(&(_heap)->nr, min_heap_char, nr), \
+ __minheap_obj_size(_heap), _func, _args)
#define min_heap_pop(_heap, _func, _args) \
- __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
+ __min_heap_pop(container_of(&(_heap)->nr, min_heap_char, nr), \
+ __minheap_obj_size(_heap), _func, _args)
#define min_heap_pop_push(_heap, _element, _func, _args) \
- __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), \
- _func, _args)
+ __min_heap_pop_push(container_of(&(_heap)->nr, min_heap_char, nr), _element, \
+ __minheap_obj_size(_heap), _func, _args)
#define min_heap_push(_heap, _element, _func, _args) \
- __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args)
+ __min_heap_push(container_of(&(_heap)->nr, min_heap_char, nr), _element, \
+ __minheap_obj_size(_heap), _func, _args)
#define min_heap_del(_heap, _idx, _func, _args) \
- __min_heap_del((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args)
+ __min_heap_del(container_of(&(_heap)->nr, min_heap_char, nr), \
+ __minheap_obj_size(_heap), _idx, _func, _args)
#endif /* _LINUX_MIN_HEAP_H */