On 03/12/2020 02.23, Yun Levi wrote: > On Thu, Dec 3, 2020 at 7:51 AM Yun Levi <ppbuk5246@xxxxxxxxx> wrote: >> >> On Thu, Dec 3, 2020 at 6:26 AM Yury Norov <yury.norov@xxxxxxxxx> wrote: >>> >>> On Wed, Dec 2, 2020 at 10:22 AM Yun Levi <ppbuk5246@xxxxxxxxx> wrote: >>>> >>>> On Thu, Dec 3, 2020 at 2:26 AM Yury Norov <yury.norov@xxxxxxxxx> wrote: >>>> >>>>> Also look at lib/find_bit_benchmark.c >>>> Thanks. I'll see. >>>> >>>>> We need find_next_*_bit() because find_first_*_bit() can start searching only at word-aligned >>>>> bits. In the case of find_last_*_bit(), we can start at any bit. So, if my understanding is correct, >>>>> for the purpose of reverse traversing we can go with already existing find_last_bit(), >>>> >>>> Thank you. I haven't thought that way. >>>> But I think if we implement reverse traversing using find_last_bit(), >>>> we have a problem. >>>> Suppose the last bit 0, 1, 2, is set. >>>> If we start >>>> find_last_bit(bitmap, 3) ==> return 2; >>>> find_last_bit(bitmap, 2) ==> return 1; >>>> find_last_bit(bitmap, 1) ==> return 0; >>>> find_last_bit(bitmap, 0) ===> return 0? // here we couldn't Either just make the return type of all find_prev/find_last be signed int and use -1 as the sentinel to indicate "no such position exists", so the loop condition would be foo >= 0. Or, change the condition from "stop if we get the size returned" to "only continue if we get something strictly less than the size we passed in (i.e., something which can possibly be a valid bit index). In the latter case, both (unsigned)-1 aka UINT_MAX and the actual size value passed work equally well as a sentinel. If one uses UINT_MAX, a for_each_bit_reverse() macro would just be something like for (i = find_last_bit(bitmap, size); i < size; i = find_last_bit(bitmap, i)) if one wants to use the size argument as the sentinel, the caller would have to supply a scratch variable to keep track of the last i value: for (j = size, i = find_last_bit(bitmap, j); i < j; j = i, i = find_last_bit(bitmap, j)) which is probably a little less ergonomic. Rasmus
