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                 :             :