find_range_of_cleared_bits.c

static bool find_clear_range(uint64_t* bitmap, size_t bitmapsize, 
                             size_t start_search, size_t size_requested, 
                             size_t* bit_pos, size_t* available_size){
   uint64_t bitset;
   uint64_t previous_set_bit = ULONG_MAX; 
   uint64_t current;

   size_t k = start_search/64;
   if(k >= bitmapsize)
      return false;

   bitset = bitmap[k];
   uint64_t mask = ~(ULONG_MAX << (start_search%64));
   bitset ^= mask;
   do {

      if (bitset == 0) {
         if(previous_set_bit == ULONG_MAX){
            previous_set_bit = k*64;
         }
         current = (k+1)*64;
         if(current > previous_set_bit + size_requested && 
            current > start_search){
            *bit_pos = previous_set_bit+1;
            *available_size = (current + 64 - previous_set_bit);
            return true;
         }
      }  

      while(bitset != 0){
         int r = __builtin_ctzl(bitset);
         current = k*64 + (uint64_t)r;
         if(current > previous_set_bit + size_requested && 
            current > start_search){
            *bit_pos = previous_set_bit+1;
            *available_size = (current - previous_set_bit -1);
            return true;
         }
         previous_set_bit = current;
         bitset ^= (bitset & -bitset);
      }
      if(++k >= bitmapsize)
         break;
      bitset = bitmap[k];
   } while(true);

   return false;
}