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

From: Mathieu Desnoyers
Date: Tue Aug 20 2024 - 16:45:41 EST


On 2024-08-20 19:19, Mathieu Desnoyers wrote:
On 2024-08-19 21:19, Yury Norov wrote:
[...]
+/**
+ * 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.

Actually, now that I come to think of it in terms of logic gates:

~A & ~B == ~(A | B)

So this "notandnot" is simply a "NOR" gate.

I therefore intend to name it "find_next_nor_bit" if that's OK with
you.

Thanks,

Mathieu

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