| Message ID | 20240514084724.557100-12-visitorckw@gmail.com (mailing list archive) |
|---|---|
| State | Not Applicable, archived |
| Delegated to: | Mike Snitzer |
| Headers | show |
| Series | treewide: Refactor heap related implementation | expand |
On Tue, May 14, 2024 at 04:47:19PM +0800, Kuan-Wei Chiu wrote: > Modify the min_heap_push() and min_heap_pop() to return a boolean > value. They now return false when the operation fails and true when it > succeeds. But why ?! > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> > Reviewed-by: Ian Rogers <irogers@google.com> > --- > include/linux/min_heap.h | 12 ++++++++---- > 1 file changed, 8 insertions(+), 4 deletions(-) > > diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h > index c94f9d303205..2d080f85ad0d 100644 > --- a/include/linux/min_heap.h > +++ b/include/linux/min_heap.h > @@ -147,18 +147,20 @@ void __min_heapify_all(min_heap_char *heap, size_t elem_size, > > /* Remove minimum element from the heap, O(log2(nr)). */ > static __always_inline > -void __min_heap_pop(min_heap_char *heap, size_t elem_size, > +bool __min_heap_pop(min_heap_char *heap, size_t elem_size, > const struct min_heap_callbacks *func, void *args) > { > void *data = heap->data; > > if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap")) > - return; > + return false; > > /* Place last element at the root (position 0) and then sift down. */ > heap->nr--; > memcpy(data, data + (heap->nr * elem_size), elem_size); > __min_heapify(heap, 0, elem_size, func, args); > + > + return true; > } > > #define min_heap_pop(_heap, _func, _args) \ > @@ -184,7 +186,7 @@ void __min_heap_pop_push(min_heap_char *heap, > > /* Push an element on to the heap, O(log2(nr)). */ > static __always_inline > -void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, > +bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, > const struct min_heap_callbacks *func, void *args) > { > void *data = heap->data; > @@ -192,7 +194,7 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, > int pos; > > if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap")) > - return; > + return false; > > /* Place at the end of data. */ > pos = heap->nr; > @@ -207,6 +209,8 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, > break; > func->swp(parent, child, args); > } > + > + return true; > } > > #define min_heap_push(_heap, _element, _func, _args) \ > -- > 2.34.1 >
On Wed, May 15, 2024 at 10:37:55AM +0200, Peter Zijlstra wrote: > On Tue, May 14, 2024 at 04:47:19PM +0800, Kuan-Wei Chiu wrote: > > Modify the min_heap_push() and min_heap_pop() to return a boolean > > value. They now return false when the operation fails and true when it > > succeeds. > > But why ?! When handling failures of push/pop operations, although we could achieve the same effect by checking whether the heap is empty/full before push/pop, we have already performed such checks within the push/pop operations. Therefore, I believe directly using the result of the check as the return value will make the code written by the user more concise. This return value is used in subsequent patches for replacing the heap macro in bcache and bcachefs to determine if an error has occurred. The original heap macros in bcache and bcachefs also do the same thing. Regards, Kuan-Wei > > > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> > > Reviewed-by: Ian Rogers <irogers@google.com> > > --- > > include/linux/min_heap.h | 12 ++++++++---- > > 1 file changed, 8 insertions(+), 4 deletions(-) > > > > diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h > > index c94f9d303205..2d080f85ad0d 100644 > > --- a/include/linux/min_heap.h > > +++ b/include/linux/min_heap.h > > @@ -147,18 +147,20 @@ void __min_heapify_all(min_heap_char *heap, size_t elem_size, > > > > /* Remove minimum element from the heap, O(log2(nr)). */ > > static __always_inline > > -void __min_heap_pop(min_heap_char *heap, size_t elem_size, > > +bool __min_heap_pop(min_heap_char *heap, size_t elem_size, > > const struct min_heap_callbacks *func, void *args) > > { > > void *data = heap->data; > > > > if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap")) > > - return; > > + return false; > > > > /* Place last element at the root (position 0) and then sift down. */ > > heap->nr--; > > memcpy(data, data + (heap->nr * elem_size), elem_size); > > __min_heapify(heap, 0, elem_size, func, args); > > + > > + return true; > > } > > > > #define min_heap_pop(_heap, _func, _args) \ > > @@ -184,7 +186,7 @@ void __min_heap_pop_push(min_heap_char *heap, > > > > /* Push an element on to the heap, O(log2(nr)). */ > > static __always_inline > > -void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, > > +bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, > > const struct min_heap_callbacks *func, void *args) > > { > > void *data = heap->data; > > @@ -192,7 +194,7 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, > > int pos; > > > > if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap")) > > - return; > > + return false; > > > > /* Place at the end of data. */ > > pos = heap->nr; > > @@ -207,6 +209,8 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, > > break; > > func->swp(parent, child, args); > > } > > + > > + return true; > > } > > > > #define min_heap_push(_heap, _element, _func, _args) \ > > -- > > 2.34.1 > >
On Wed, May 15, 2024 at 10:37:55AM +0200, Peter Zijlstra wrote: > On Tue, May 14, 2024 at 04:47:19PM +0800, Kuan-Wei Chiu wrote: > > Modify the min_heap_push() and min_heap_pop() to return a boolean > > value. They now return false when the operation fails and true when it > > succeeds. > > But why ?! like Kuan said, it makes for cleaner code. It's also what the bcache/bcachefs heap (and fifo) implementations do, which we're consolidating.
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index c94f9d303205..2d080f85ad0d 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -147,18 +147,20 @@ void __min_heapify_all(min_heap_char *heap, size_t elem_size, /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void __min_heap_pop(min_heap_char *heap, size_t elem_size, +bool __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data = heap->data; if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap")) - return; + return false; /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); __min_heapify(heap, 0, elem_size, func, args); + + return true; } #define min_heap_pop(_heap, _func, _args) \ @@ -184,7 +186,7 @@ void __min_heap_pop_push(min_heap_char *heap, /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, +bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data = heap->data; @@ -192,7 +194,7 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, int pos; if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap")) - return; + return false; /* Place at the end of data. */ pos = heap->nr; @@ -207,6 +209,8 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, break; func->swp(parent, child, args); } + + return true; } #define min_heap_push(_heap, _element, _func, _args) \