find_bit.c (0337966d121ebebf73a1c346123e8112796e684e) find_bit.c (0ade34c37012ea5c516d9aa4d19a56e9f40a55ed)
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)

--- 7 unchanged lines hidden (view full) ---

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

--- 7 unchanged lines hidden (view full) ---

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)
24#if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
25 !defined(find_next_and_bit)
25
26/*
26
27/*
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.
28 * This is a common helper function for find_next_bit, find_next_zero_bit, and
29 * find_next_and_bit. The differences are:
30 * - The "invert" argument, which is XORed with each fetched word before
31 * searching it for one bits.
32 * - The optional "addr2", which is anded with "addr1" if present.
30 */
33 */
31static unsigned long _find_next_bit(const unsigned long *addr,
32 unsigned long nbits, unsigned long start, unsigned long invert)
34static inline unsigned long _find_next_bit(const unsigned long *addr1,
35 const unsigned long *addr2, unsigned long nbits,
36 unsigned long start, unsigned long invert)
33{
34 unsigned long tmp;
35
36 if (unlikely(start >= nbits))
37 return nbits;
38
37{
38 unsigned long tmp;
39
40 if (unlikely(start >= nbits))
41 return nbits;
42
39 tmp = addr[start / BITS_PER_LONG] ^ invert;
43 tmp = addr1[start / BITS_PER_LONG];
44 if (addr2)
45 tmp &= addr2[start / BITS_PER_LONG];
46 tmp ^= 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
47
48 /* Handle 1st word. */
49 tmp &= BITMAP_FIRST_WORD_MASK(start);
50 start = round_down(start, BITS_PER_LONG);
51
52 while (!tmp) {
53 start += BITS_PER_LONG;
54 if (start >= nbits)
55 return nbits;
56
50 tmp = addr[start / BITS_PER_LONG] ^ invert;
57 tmp = addr1[start / BITS_PER_LONG];
58 if (addr2)
59 tmp &= addr2[start / BITS_PER_LONG];
60 tmp ^= 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 */
61unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
62 unsigned long offset)
63{
61 }
62
63 return min(start + __ffs(tmp), nbits);
64}
65#endif
66
67#ifndef find_next_bit
68/*
69 * Find the next set bit in a memory region.
70 */
71unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
72 unsigned long offset)
73{
64 return _find_next_bit(addr, size, offset, 0UL);
74 return _find_next_bit(addr, NULL, size, offset, 0UL);
65}
66EXPORT_SYMBOL(find_next_bit);
67#endif
68
69#ifndef find_next_zero_bit
70unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
71 unsigned long offset)
72{
75}
76EXPORT_SYMBOL(find_next_bit);
77#endif
78
79#ifndef find_next_zero_bit
80unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
81 unsigned long offset)
82{
73 return _find_next_bit(addr, size, offset, ~0UL);
83 return _find_next_bit(addr, NULL, size, offset, ~0UL);
74}
75EXPORT_SYMBOL(find_next_zero_bit);
76#endif
77
84}
85EXPORT_SYMBOL(find_next_zero_bit);
86#endif
87
88#if !defined(find_next_and_bit)
89unsigned long find_next_and_bit(const unsigned long *addr1,
90 const unsigned long *addr2, unsigned long size,
91 unsigned long offset)
92{
93 return _find_next_bit(addr1, addr2, size, offset, 0UL);
94}
95EXPORT_SYMBOL(find_next_and_bit);
96#endif
97
78#ifndef find_first_bit
79/*
80 * Find the first set bit in a memory region.
81 */
82unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
83{
84 unsigned long idx;
85

--- 55 unchanged lines hidden (view full) ---

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)
98#ifndef find_first_bit
99/*
100 * Find the first set bit in a memory region.
101 */
102unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
103{
104 unsigned long idx;
105

--- 55 unchanged lines hidden (view full) ---

161#elif BITS_PER_LONG == 32
162 return (unsigned long) __swab32((u32) y);
163#else
164#error BITS_PER_LONG not defined
165#endif
166}
167
168#if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
149static unsigned long _find_next_bit_le(const unsigned long *addr,
150 unsigned long nbits, unsigned long start, unsigned long invert)
169static inline unsigned long _find_next_bit_le(const unsigned long *addr1,
170 const unsigned long *addr2, unsigned long nbits,
171 unsigned long start, unsigned long invert)
151{
152 unsigned long tmp;
153
154 if (unlikely(start >= nbits))
155 return nbits;
156
172{
173 unsigned long tmp;
174
175 if (unlikely(start >= nbits))
176 return nbits;
177
157 tmp = addr[start / BITS_PER_LONG] ^ invert;
178 tmp = addr1[start / BITS_PER_LONG];
179 if (addr2)
180 tmp &= addr2[start / BITS_PER_LONG];
181 tmp ^= 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
182
183 /* Handle 1st word. */
184 tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
185 start = round_down(start, BITS_PER_LONG);
186
187 while (!tmp) {
188 start += BITS_PER_LONG;
189 if (start >= nbits)
190 return nbits;
191
168 tmp = addr[start / BITS_PER_LONG] ^ invert;
192 tmp = addr1[start / BITS_PER_LONG];
193 if (addr2)
194 tmp &= addr2[start / BITS_PER_LONG];
195 tmp ^= invert;
169 }
170
171 return min(start + __ffs(ext2_swab(tmp)), nbits);
172}
173#endif
174
175#ifndef find_next_zero_bit_le
176unsigned long find_next_zero_bit_le(const void *addr, unsigned
177 long size, unsigned long offset)
178{
196 }
197
198 return min(start + __ffs(ext2_swab(tmp)), nbits);
199}
200#endif
201
202#ifndef find_next_zero_bit_le
203unsigned long find_next_zero_bit_le(const void *addr, unsigned
204 long size, unsigned long offset)
205{
179 return _find_next_bit_le(addr, size, offset, ~0UL);
206 return _find_next_bit_le(addr, NULL, size, offset, ~0UL);
180}
181EXPORT_SYMBOL(find_next_zero_bit_le);
182#endif
183
184#ifndef find_next_bit_le
185unsigned long find_next_bit_le(const void *addr, unsigned
186 long size, unsigned long offset)
187{
207}
208EXPORT_SYMBOL(find_next_zero_bit_le);
209#endif
210
211#ifndef find_next_bit_le
212unsigned long find_next_bit_le(const void *addr, unsigned
213 long size, unsigned long offset)
214{
188 return _find_next_bit_le(addr, size, offset, 0UL);
215 return _find_next_bit_le(addr, NULL, size, offset, 0UL);
189}
190EXPORT_SYMBOL(find_next_bit_le);
191#endif
192
193#endif /* __BIG_ENDIAN */
216}
217EXPORT_SYMBOL(find_next_bit_le);
218#endif
219
220#endif /* __BIG_ENDIAN */