Re: [RFC PATCH 1/5] lib: Implement find_{first,next,nth}_notandnot_bit, find_first_andnot_bit

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

On 2024-08-19 21:19, Yury Norov wrote:
[...[> Can you split rewording of existing comments out to a separate patch
> please?

Will do.

> 
>>    */
>>   static inline
>>   unsigned long find_next_andnot_bit(const unsigned long *addr1,
>> @@ -131,6 +138,36 @@ unsigned long find_next_andnot_bit(const unsigned long *addr1,
>>   }
>>   #endif
>>   
>> +#ifndef find_next_notandnot_bit
> 
> Don't protect new functions. This is only for those having arch
> implementation, and it's only armv7 now.

OK

> 
>> +/**
>> + * find_next_notandnot_bit - find the next bit cleared in both *addr1 and *addr2
>> + * @addr1: The first address to base the search on
>> + * @addr2: The second address to base the search on
>> + * @size: The bitmap size in bits
>> + * @offset: The bitnumber to start searching at
>> + *
>> + * Returns the bit number for the next bit cleared in both *addr1 and *addr2.
>> + * If no such bits are found, returns @size.
>> + */
>> +static inline
>> +unsigned long find_next_notandnot_bit(const unsigned long *addr1,
>> +		const unsigned long *addr2, unsigned long size,
>> +		unsigned long offset)
>> +{
>> +	if (small_const_nbits(size)) {
>> +		unsigned long val;
>> +
>> +		if (unlikely(offset >= size))
>> +			return size;
>> +
>> +		val = (~*addr1) & (~*addr2) & GENMASK(size - 1, offset);
>> +		return val ? __ffs(val) : size;
>> +	}
>> +
>> +	return _find_next_notandnot_bit(addr1, addr2, size, offset);
>> +}
>> +#endif
>> +
> 
> It's not said explicitly, but some naming conventions exist around bitmap
> searching.
> 
> If you're looking for a clear (unset) bit in a mask, you'd use a 'zero'
> modifier. We have only 2 such functions now: find_{first,next}_zero_bit,
> both taking one bitmap. I think it's time to extend this rule for
> many bitmaps and write down the naming rules.
> 
> With the following, the find_next_notandnot_bit() should be named
> like; find_next_zero_and_bit(). It's not perfect, but still sounds
> better to me than 'notandnot' thing.
> 
> If we search for a set bit in bitmap, we use find_first or find_next
> prefixes:
>   - find_first_bit;
>   - find_next_bit.
> 
> If we'd like to pass an additional bitmap to AND, OR or XOR with the
> 1st bitmap, we provide as corresponding logical operation as
> suffix(es):
>   - find_first_and_bit(b1, b2) : b1 & b2;
>   - find _next_and_or_bit(b1, b2, b3) : b1 & b2 | b3.
> 
> If additional bitmap must be inverted, we provide a 'not' after the
> corresponding logical operation:
>   - find_first_andnot_bit(b1, b2) : b1 & ~b2;
>   - find _next_and_ornot_bit(b1, b2, b3) : b1 & b2 | ~b3.
> 
> If all bitmaps have to be inverted, or in other words, we are looking
> for an unset bit in a bitmap or a combination of bitmaps, we provide
> a 'zero' prefix in the function name:
>   - find_next_zero_bit;
>   - find_next_zero_and_bit;
>   - find_next_zero_and_or_bit;
> 
> Functions having 'zero' prefix should not negate bitmaps (should not
> have 'not' in names) because of commutative property. For example,
> find_next_zero_andnot_bit(), which is ~b1 & ~(~b2) is redundant
> because it's the same as find_next_andnot_bit() : b2 & ~b1.
> 
> Iterators over unset bits in bitmap(s) (those based on 'zero' search
> functions) should have a 'clear' prefix in the name:
>   - for_each_clear_bit;
>   - for_each_clear_bit_from;
> 
> I should probably put the above on top of the file...

I'll do this for the next round. Yes, it would be good to add
those explanations on top of the file.

Thanks for the review !

Mathieu

> 
> Thanks,
> Yury

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com