From: Kuan-Wei Chiu <visitorckw@gmail.com>
To: Kent Overstreet <kent.overstreet@linux.dev>
Cc: colyli@suse.de, msakai@redhat.com, peterz@infradead.org,
mingo@redhat.com, acme@kernel.org, namhyung@kernel.org,
akpm@linux-foundation.org, bfoster@redhat.com,
mark.rutland@arm.com, alexander.shishkin@linux.intel.com,
jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com,
jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev,
linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org,
linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org
Subject: Re: [PATCH v2 04/15] lib min_heap: Add type safe interface
Date: Sat, 23 Mar 2024 09:53:08 +0800 [thread overview]
Message-ID: <Zf42BA7EMCRI3hik@visitorckw-System-Product-Name> (raw)
In-Reply-To: <gx3skkrp6pfp7ch3dmludzmqrsyncsptzhlvuwqt2abdhcli5m@xsny7x4nkxv3>
On Fri, Mar 22, 2024 at 02:23:26PM -0400, Kent Overstreet wrote:
> On Sat, Mar 23, 2024 at 01:02:29AM +0800, Kuan-Wei Chiu wrote:
> > On Thu, Mar 21, 2024 at 05:22:14PM -0400, Kent Overstreet wrote:
> > > On Thu, Mar 21, 2024 at 07:57:47PM +0800, Kuan-Wei Chiu wrote:
> > > > On Wed, Mar 20, 2024 at 04:56:57PM -0400, Kent Overstreet wrote:
> > > > > On Wed, Mar 20, 2024 at 10:54:06PM +0800, Kuan-Wei Chiu wrote:
> > > > > > Introduce a type-safe interface for min_heap by adding small macro
> > > > > > wrappers around functions and using a 0-size array to store type
> > > > > > information. This enables the use of __minheap_cast and
> > > > > > __minheap_obj_size macros for type casting and obtaining element size.
> > > > > > The implementation draws inspiration from generic-radix-tree.h,
> > > > > > eliminating the need to pass element size in min_heap_callbacks.
> > > > >
> > > > > let's avoid the heap->heap.nr - darray (fs/bcachefs/darray.h) has a
> > > > > trick for that. All heaps have the same memory layout, so we can just
> > > > > cast to a void pointer heap to get something the C code can use.
> > > > >
> > > > If I understand correctly, you're suggesting adding APIs similar to
> > > > darray_top(), darray_first(), and darray_last() within min_heap and
> > > > having them return a pointer. However, some users are using heap.nr in
> > > > conditional statements instead of utilizing heap.nr for memory
> > > > operations, so returning pointers may not be as convenient. What about
> > > > adding get and set functions for nr instead?
> > >
> > > No, I mean not having separate inner and outer types. Want me to sketch
> > > something out?
> >
> > Based on your suggestion, I've come up with the following code snippet:
> >
> > #define MIN_HEAP_PREALLOCATED(_type, _name, _nr) \
> > struct _name { \
> > int nr; \
> > int size; \
> > _type *data; \
> > _type preallocated[_nr]; \
> > };
> >
> > #define MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0)
> >
> > typdef MIN_HEAP(char, _) min_heap_char;
> >
> > static __always_inline
> > void min_heap_init(min_heap_char *heap, void *data, int size)
> > {
> > heap->nr = 0;
> > heap->size = size;
> > heap->data = size <= ARRAY_SIZE(heap->preallocated) ? heap->preallocated : data;
> > }
> >
> > But I'm not sure how to implement other inline functions like
> > min_heap_push or min_heap_pop if I do that, unless they are rewritten
> > using macros. Also, I'm not sure how to make the less and swp functions
> > in the min_heap_callbacks not use void * type parameters. Or perhaps I
> > misunderstood your meaning again. If you could sketch out your idea or
> > have a better approach, it would be a great help to me. Any guidance
> > would be greatly appreciated.
>
> No, you're on the right track. To call C functions on different types of
> heaps you have to cast them all to a common type, say HEAP(char), also
> pass the element size as a paremeter (which you had to do previously
> anyways).
The other question I want to ask is, I'm not sure how this relates to
avoiding the heap->heap.nr. In cases where we need to know the current
number of elements in the heap, don't we still need to use the same
method to determine the number of elements?
Regards,
Kuan-Wei
next prev parent reply other threads:[~2024-03-23 1:53 UTC|newest]
Thread overview: 35+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-20 14:54 [PATCH v2 00/15] treewide: Refactor heap related implementation Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 01/15] perf/core: Fix several typos Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 02/15] bcache: Fix typo Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 03/15] bcachefs: " Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 04/15] lib min_heap: Add type safe interface Kuan-Wei Chiu
2024-03-20 20:56 ` Kent Overstreet
2024-03-21 11:57 ` Kuan-Wei Chiu
2024-03-21 21:22 ` Kent Overstreet
2024-03-22 17:02 ` Kuan-Wei Chiu
2024-03-22 18:23 ` Kent Overstreet
2024-03-23 1:53 ` Kuan-Wei Chiu [this message]
2024-03-23 2:08 ` Kent Overstreet
2024-03-23 2:19 ` Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 05/15] lib min_heap: Add min_heap_init() Kuan-Wei Chiu
2024-03-20 17:13 ` Ian Rogers
2024-03-20 17:17 ` Ian Rogers
2024-03-20 14:54 ` [PATCH v2 06/15] lib min_heap: Add min_heap_peek() Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 07/15] lib min_heap: Add min_heap_full() Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 08/15] lib min_heap: Add min_heap_del() Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 09/15] lib min_heap: Add min_heap_sift_up() Kuan-Wei Chiu
2024-03-20 17:15 ` Ian Rogers
2024-03-21 7:00 ` Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 10/15] lib min_heap: Add args for min_heap_callbacks Kuan-Wei Chiu
2024-03-20 17:15 ` Ian Rogers
2024-03-20 14:54 ` [PATCH v2 11/15] lib min_heap: Update min_heap_push() and min_heap_pop() to return bool values Kuan-Wei Chiu
2024-03-20 14:54 ` [PATCH v2 12/15] lib min_heap: Rename min_heapify() to min_heap_sift_down() Kuan-Wei Chiu
2024-03-20 17:17 ` Ian Rogers
2024-03-20 14:54 ` [PATCH v2 13/15] lib/test_min_heap: Use min_heap_init() for initializing Kuan-Wei Chiu
2024-03-20 17:16 ` Ian Rogers
2024-03-20 14:54 ` [PATCH v2 14/15] bcache: Remove heap-related macros and switch to generic min_heap Kuan-Wei Chiu
2024-03-20 17:19 ` Ian Rogers
2024-03-20 14:54 ` [PATCH v2 15/15] bcachefs: " Kuan-Wei Chiu
2024-03-20 17:20 ` Ian Rogers
2024-03-20 19:57 ` [PATCH v2 00/15] treewide: Refactor heap related implementation Kent Overstreet
2024-03-21 7:08 ` Kuan-Wei Chiu
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Zf42BA7EMCRI3hik@visitorckw-System-Product-Name \
--to=visitorckw@gmail.com \
--cc=acme@kernel.org \
--cc=adrian.hunter@intel.com \
--cc=akpm@linux-foundation.org \
--cc=alexander.shishkin@linux.intel.com \
--cc=bfoster@redhat.com \
--cc=colyli@suse.de \
--cc=dm-devel@lists.linux.dev \
--cc=irogers@google.com \
--cc=jolsa@kernel.org \
--cc=jserv@ccns.ncku.edu.tw \
--cc=kent.overstreet@linux.dev \
--cc=linux-bcache@vger.kernel.org \
--cc=linux-bcachefs@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=mark.rutland@arm.com \
--cc=mingo@redhat.com \
--cc=msakai@redhat.com \
--cc=namhyung@kernel.org \
--cc=peterz@infradead.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).