Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/lib/find_bit.c

  1 /* bit search implementation
  2  *
  3  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
  4  * Written by David Howells (dhowells@redhat.com)
  5  *
  6  * Copyright (C) 2008 IBM Corporation
  7  * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
  8  * (Inspired by David Howell's find_next_bit implementation)
  9  *
 10  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
 11  * size and improve performance, 2015.
 12  *
 13  * This program is free software; you can redistribute it and/or
 14  * modify it under the terms of the GNU General Public License
 15  * as published by the Free Software Foundation; either version
 16  * 2 of the License, or (at your option) any later version.
 17  */
 18 
 19 #include <linux/bitops.h>
 20 #include <linux/bitmap.h>
 21 #include <linux/export.h>
 22 #include <linux/kernel.h>
 23 
 24 #if !defined(find_next_bit) || !defined(find_next_zero_bit)
 25 
 26 /*
 27  * This is a common helper function for find_next_bit and
 28  * find_next_zero_bit.  The difference is the "invert" argument, which
 29  * is XORed with each fetched word before searching it for one bits.
 30  */
 31 static unsigned long _find_next_bit(const unsigned long *addr,
 32                 unsigned long nbits, unsigned long start, unsigned long invert)
 33 {
 34         unsigned long tmp;
 35 
 36         if (!nbits || start >= nbits)
 37                 return nbits;
 38 
 39         tmp = addr[start / BITS_PER_LONG] ^ invert;
 40 
 41         /* Handle 1st word. */
 42         tmp &= BITMAP_FIRST_WORD_MASK(start);
 43         start = round_down(start, BITS_PER_LONG);
 44 
 45         while (!tmp) {
 46                 start += BITS_PER_LONG;
 47                 if (start >= nbits)
 48                         return nbits;
 49 
 50                 tmp = addr[start / BITS_PER_LONG] ^ invert;
 51         }
 52 
 53         return min(start + __ffs(tmp), nbits);
 54 }
 55 #endif
 56 
 57 #ifndef find_next_bit
 58 /*
 59  * Find the next set bit in a memory region.
 60  */
 61 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
 62                             unsigned long offset)
 63 {
 64         return _find_next_bit(addr, size, offset, 0UL);
 65 }
 66 EXPORT_SYMBOL(find_next_bit);
 67 #endif
 68 
 69 #ifndef find_next_zero_bit
 70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
 71                                  unsigned long offset)
 72 {
 73         return _find_next_bit(addr, size, offset, ~0UL);
 74 }
 75 EXPORT_SYMBOL(find_next_zero_bit);
 76 #endif
 77 
 78 #ifndef find_first_bit
 79 /*
 80  * Find the first set bit in a memory region.
 81  */
 82 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 83 {
 84         unsigned long idx;
 85 
 86         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 87                 if (addr[idx])
 88                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
 89         }
 90 
 91         return size;
 92 }
 93 EXPORT_SYMBOL(find_first_bit);
 94 #endif
 95 
 96 #ifndef find_first_zero_bit
 97 /*
 98  * Find the first cleared bit in a memory region.
 99  */
100 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
101 {
102         unsigned long idx;
103 
104         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
105                 if (addr[idx] != ~0UL)
106                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
107         }
108 
109         return size;
110 }
111 EXPORT_SYMBOL(find_first_zero_bit);
112 #endif
113 
114 #ifndef find_last_bit
115 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
116 {
117         if (size) {
118                 unsigned long val = BITMAP_LAST_WORD_MASK(size);
119                 unsigned long idx = (size-1) / BITS_PER_LONG;
120 
121                 do {
122                         val &= addr[idx];
123                         if (val)
124                                 return idx * BITS_PER_LONG + __fls(val);
125 
126                         val = ~0ul;
127                 } while (idx--);
128         }
129         return size;
130 }
131 EXPORT_SYMBOL(find_last_bit);
132 #endif
133 
134 #ifdef __BIG_ENDIAN
135 
136 /* include/linux/byteorder does not support "unsigned long" type */
137 static inline unsigned long ext2_swab(const unsigned long y)
138 {
139 #if BITS_PER_LONG == 64
140         return (unsigned long) __swab64((u64) y);
141 #elif BITS_PER_LONG == 32
142         return (unsigned long) __swab32((u32) y);
143 #else
144 #error BITS_PER_LONG not defined
145 #endif
146 }
147 
148 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
149 static unsigned long _find_next_bit_le(const unsigned long *addr,
150                 unsigned long nbits, unsigned long start, unsigned long invert)
151 {
152         unsigned long tmp;
153 
154         if (!nbits || start >= nbits)
155                 return nbits;
156 
157         tmp = addr[start / BITS_PER_LONG] ^ invert;
158 
159         /* Handle 1st word. */
160         tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
161         start = round_down(start, BITS_PER_LONG);
162 
163         while (!tmp) {
164                 start += BITS_PER_LONG;
165                 if (start >= nbits)
166                         return nbits;
167 
168                 tmp = addr[start / BITS_PER_LONG] ^ invert;
169         }
170 
171         return min(start + __ffs(ext2_swab(tmp)), nbits);
172 }
173 #endif
174 
175 #ifndef find_next_zero_bit_le
176 unsigned long find_next_zero_bit_le(const void *addr, unsigned
177                 long size, unsigned long offset)
178 {
179         return _find_next_bit_le(addr, size, offset, ~0UL);
180 }
181 EXPORT_SYMBOL(find_next_zero_bit_le);
182 #endif
183 
184 #ifndef find_next_bit_le
185 unsigned long find_next_bit_le(const void *addr, unsigned
186                 long size, unsigned long offset)
187 {
188         return _find_next_bit_le(addr, size, offset, 0UL);
189 }
190 EXPORT_SYMBOL(find_next_bit_le);
191 #endif
192 
193 #endif /* __BIG_ENDIAN */
194 

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us