Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
       2                 :            : /* Copyright 2016 IBM Corp. */
       3                 :            : 
       4                 :            : #include "bitmap.h"
       5                 :            : 
       6                 :         19 : static int __bitmap_find_bit(bitmap_t map, unsigned int start, unsigned int count,
       7                 :            :                              bool value)
       8                 :            : {
       9                 :            :         unsigned int el, first_bit;
      10                 :         19 :         unsigned int end = start + count;
      11                 :            :         bitmap_elem_t e, ev;
      12                 :            :         int b;
      13                 :            : 
      14                 :         19 :         ev = value ? -1ul : 0;
      15                 :         19 :         el = BITMAP_ELEM(start);
      16                 :         19 :         first_bit = BITMAP_BIT(start);
      17                 :            : 
      18                 :         21 :         while (start < end) {
      19                 :         19 :                 e = map[el] ^ ev;
      20                 :         19 :                 e |= ((1ul << first_bit) - 1);
      21                 :         19 :                 if (~e)
      22                 :         17 :                         break;
      23                 :          2 :                 start = (start + BITMAP_ELSZ) & ~(BITMAP_ELSZ - 1);
      24                 :          2 :                 first_bit = 0;
      25                 :          2 :                 el++;
      26                 :            :         }
      27                 :        214 :         for (b = first_bit; b < BITMAP_ELSZ && start < end; b++,start++) {
      28                 :        212 :                 if ((e & (1ull << b)) == 0)
      29                 :         17 :                         return start;
      30                 :            :         }
      31                 :            : 
      32                 :          2 :         return -1;
      33                 :            : }
      34                 :            : 
      35                 :         17 : int bitmap_find_zero_bit(bitmap_t map, unsigned int start, unsigned int count)
      36                 :            : {
      37                 :         17 :         return __bitmap_find_bit(map, start, count, false);
      38                 :            : }
      39                 :            : 
      40                 :          2 : int bitmap_find_one_bit(bitmap_t map, unsigned int start, unsigned int count)
      41                 :            : {
      42                 :          2 :         return __bitmap_find_bit(map, start, count, true);
      43                 :            : }
      44                 :            :