by Kent Overstreet

[permalink] [raw]

Subject: Re: [PATCH v2 04/15] lib min_heap: Add type safe interface

On Sat, Mar 23, 2024 at 09:53:08AM +0800, Kuan-Wei Chiu wrote:
> 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?

Yes, but this eliminates the nested types; so it's just heap->nr.

It's a pretty minor detail, cosmetic really, but I managed it in darray
so it'd be nice to have here as well :)

2024-03-23 02:19:23

by Kuan-Wei Chiu

[permalink] [raw]

Subject: Re: [PATCH v2 04/15] lib min_heap: Add type safe interface

On Fri, Mar 22, 2024 at 10:08:59PM -0400, Kent Overstreet wrote:
> On Sat, Mar 23, 2024 at 09:53:08AM +0800, Kuan-Wei Chiu wrote:
> > 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?
>
> Yes, but this eliminates the nested types; so it's just heap->nr.
>
> It's a pretty minor detail, cosmetic really, but I managed it in darray
> so it'd be nice to have here as well :)

Ah, got it. I'll make that change in v3.

Regards,
Kuan-Wei