Received-SPF: pass (google.com: domain of linux-kernel+bounces-111937-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1;
Date: Fri, 22 Mar 2024 14:23:26 -0400
From: Kent Overstreet <kent.overstreet@linux.dev>
To: Kuan-Wei Chiu <visitorckw@gmail.com>
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
Message-ID: <gx3skkrp6pfp7ch3dmludzmqrsyncsptzhlvuwqt2abdhcli5m@xsny7x4nkxv3>
References: <20240320145417.336208-1-visitorckw@gmail.com>
 <20240320145417.336208-5-visitorckw@gmail.com>
 <iz6wl3twuc72txd4ifxy73bbbfijo3ecy7izw3drsmcb2payeu@b2dusfoqobgu>
 <Zfwgu8+IeH/YqWYR@visitorckw-System-Product-Name>
 <mi3uq4gqvseubfiylslxfrnwupfzopz753md5f53v6brlgiamv@l5bxmctqnz6g>
 <Zf25pSI4p0d5pFXX@visitorckw-System-Product-Name>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <Zf25pSI4p0d5pFXX@visitorckw-System-Product-Name>

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).