aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--include/linux/bitops.h115
-rw-r--r--lib/find_next_bit.c22
2 files changed, 22 insertions, 115 deletions
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 8340a3aba49a..024f2b027244 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -114,8 +114,6 @@ static inline unsigned fls_long(unsigned long l)
114 114
115#ifdef __KERNEL__ 115#ifdef __KERNEL__
116#ifdef CONFIG_GENERIC_FIND_FIRST_BIT 116#ifdef CONFIG_GENERIC_FIND_FIRST_BIT
117extern unsigned long __find_first_bit(const unsigned long *addr,
118 unsigned long size);
119 117
120/** 118/**
121 * find_first_bit - find the first set bit in a memory region 119 * find_first_bit - find the first set bit in a memory region
@@ -124,28 +122,8 @@ extern unsigned long __find_first_bit(const unsigned long *addr,
124 * 122 *
125 * Returns the bit number of the first set bit. 123 * Returns the bit number of the first set bit.
126 */ 124 */
127static __always_inline unsigned long 125extern unsigned long find_first_bit(const unsigned long *addr,
128find_first_bit(const unsigned long *addr, unsigned long size) 126 unsigned long size);
129{
130 /* Avoid a function call if the bitmap size is a constant */
131 /* and not bigger than BITS_PER_LONG. */
132
133 /* insert a sentinel so that __ffs returns size if there */
134 /* are no set bits in the bitmap */
135 if (__builtin_constant_p(size) && (size < BITS_PER_LONG))
136 return __ffs((*addr) | (1ul << size));
137
138 /* the result of __ffs(0) is undefined, so it needs to be */
139 /* handled separately */
140 if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
141 return ((*addr) == 0) ? BITS_PER_LONG : __ffs(*addr);
142
143 /* size is not constant or too big */
144 return __find_first_bit(addr, size);
145}
146
147extern unsigned long __find_first_zero_bit(const unsigned long *addr,
148 unsigned long size);
149 127
150/** 128/**
151 * find_first_zero_bit - find the first cleared bit in a memory region 129 * find_first_zero_bit - find the first cleared bit in a memory region
@@ -154,31 +132,12 @@ extern unsigned long __find_first_zero_bit(const unsigned long *addr,
154 * 132 *
155 * Returns the bit number of the first cleared bit. 133 * Returns the bit number of the first cleared bit.
156 */ 134 */
157static __always_inline unsigned long 135extern unsigned long find_first_zero_bit(const unsigned long *addr,
158find_first_zero_bit(const unsigned long *addr, unsigned long size) 136 unsigned long size);
159{ 137
160 /* Avoid a function call if the bitmap size is a constant */
161 /* and not bigger than BITS_PER_LONG. */
162
163 /* insert a sentinel so that __ffs returns size if there */
164 /* are no set bits in the bitmap */
165 if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
166 return __ffs(~(*addr) | (1ul << size));
167 }
168
169 /* the result of __ffs(0) is undefined, so it needs to be */
170 /* handled separately */
171 if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
172 return (~(*addr) == 0) ? BITS_PER_LONG : __ffs(~(*addr));
173
174 /* size is not constant or too big */
175 return __find_first_zero_bit(addr, size);
176}
177#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ 138#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
178 139
179#ifdef CONFIG_GENERIC_FIND_NEXT_BIT 140#ifdef CONFIG_GENERIC_FIND_NEXT_BIT
180extern unsigned long __find_next_bit(const unsigned long *addr,
181 unsigned long size, unsigned long offset);
182 141
183/** 142/**
184 * find_next_bit - find the next set bit in a memory region 143 * find_next_bit - find the next set bit in a memory region
@@ -186,36 +145,8 @@ extern unsigned long __find_next_bit(const unsigned long *addr,
186 * @offset: The bitnumber to start searching at 145 * @offset: The bitnumber to start searching at
187 * @size: The bitmap size in bits 146 * @size: The bitmap size in bits
188 */ 147 */
189static __always_inline unsigned long 148extern unsigned long find_next_bit(const unsigned long *addr,
190find_next_bit(const unsigned long *addr, unsigned long size, 149 unsigned long size, unsigned long offset);
191 unsigned long offset)
192{
193 unsigned long value;
194
195 /* Avoid a function call if the bitmap size is a constant */
196 /* and not bigger than BITS_PER_LONG. */
197
198 /* insert a sentinel so that __ffs returns size if there */
199 /* are no set bits in the bitmap */
200 if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
201 value = (*addr) & ((~0ul) << offset);
202 value |= (1ul << size);
203 return __ffs(value);
204 }
205
206 /* the result of __ffs(0) is undefined, so it needs to be */
207 /* handled separately */
208 if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
209 value = (*addr) & ((~0ul) << offset);
210 return (value == 0) ? BITS_PER_LONG : __ffs(value);
211 }
212
213 /* size is not constant or too big */
214 return __find_next_bit(addr, size, offset);
215}
216
217extern unsigned long __find_next_zero_bit(const unsigned long *addr,
218 unsigned long size, unsigned long offset);
219 150
220/** 151/**
221 * find_next_zero_bit - find the next cleared bit in a memory region 152 * find_next_zero_bit - find the next cleared bit in a memory region
@@ -223,33 +154,11 @@ extern unsigned long __find_next_zero_bit(const unsigned long *addr,
223 * @offset: The bitnumber to start searching at 154 * @offset: The bitnumber to start searching at
224 * @size: The bitmap size in bits 155 * @size: The bitmap size in bits
225 */ 156 */
226static __always_inline unsigned long 157
227find_next_zero_bit(const unsigned long *addr, unsigned long size, 158extern unsigned long find_next_zero_bit(const unsigned long *addr,
228 unsigned long offset) 159 unsigned long size,
229{ 160 unsigned long offset);
230 unsigned long value; 161
231
232 /* Avoid a function call if the bitmap size is a constant */
233 /* and not bigger than BITS_PER_LONG. */
234
235 /* insert a sentinel so that __ffs returns size if there */
236 /* are no set bits in the bitmap */
237 if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
238 value = (~(*addr)) & ((~0ul) << offset);
239 value |= (1ul << size);
240 return __ffs(value);
241 }
242
243 /* the result of __ffs(0) is undefined, so it needs to be */
244 /* handled separately */
245 if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
246 value = (~(*addr)) & ((~0ul) << offset);
247 return (value == 0) ? BITS_PER_LONG : __ffs(value);
248 }
249
250 /* size is not constant or too big */
251 return __find_next_zero_bit(addr, size, offset);
252}
253#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */ 162#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */
254#endif /* __KERNEL__ */ 163#endif /* __KERNEL__ */
255#endif 164#endif
diff --git a/lib/find_next_bit.c b/lib/find_next_bit.c
index d3f5784807b4..24c59ded47a0 100644
--- a/lib/find_next_bit.c
+++ b/lib/find_next_bit.c
@@ -20,8 +20,8 @@
20/* 20/*
21 * Find the next set bit in a memory region. 21 * Find the next set bit in a memory region.
22 */ 22 */
23unsigned long __find_next_bit(const unsigned long *addr, 23unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
24 unsigned long size, unsigned long offset) 24 unsigned long offset)
25{ 25{
26 const unsigned long *p = addr + BITOP_WORD(offset); 26 const unsigned long *p = addr + BITOP_WORD(offset);
27 unsigned long result = offset & ~(BITS_PER_LONG-1); 27 unsigned long result = offset & ~(BITS_PER_LONG-1);
@@ -58,14 +58,14 @@ found_first:
58found_middle: 58found_middle:
59 return result + __ffs(tmp); 59 return result + __ffs(tmp);
60} 60}
61EXPORT_SYMBOL(__find_next_bit); 61EXPORT_SYMBOL(find_next_bit);
62 62
63/* 63/*
64 * This implementation of find_{first,next}_zero_bit was stolen from 64 * This implementation of find_{first,next}_zero_bit was stolen from
65 * Linus' asm-alpha/bitops.h. 65 * Linus' asm-alpha/bitops.h.
66 */ 66 */
67unsigned long __find_next_zero_bit(const unsigned long *addr, 67unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
68 unsigned long size, unsigned long offset) 68 unsigned long offset)
69{ 69{
70 const unsigned long *p = addr + BITOP_WORD(offset); 70 const unsigned long *p = addr + BITOP_WORD(offset);
71 unsigned long result = offset & ~(BITS_PER_LONG-1); 71 unsigned long result = offset & ~(BITS_PER_LONG-1);
@@ -102,15 +102,14 @@ found_first:
102found_middle: 102found_middle:
103 return result + ffz(tmp); 103 return result + ffz(tmp);
104} 104}
105EXPORT_SYMBOL(__find_next_zero_bit); 105EXPORT_SYMBOL(find_next_zero_bit);
106#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */ 106#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */
107 107
108#ifdef CONFIG_GENERIC_FIND_FIRST_BIT 108#ifdef CONFIG_GENERIC_FIND_FIRST_BIT
109/* 109/*
110 * Find the first set bit in a memory region. 110 * Find the first set bit in a memory region.
111 */ 111 */
112unsigned long __find_first_bit(const unsigned long *addr, 112unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
113 unsigned long size)
114{ 113{
115 const unsigned long *p = addr; 114 const unsigned long *p = addr;
116 unsigned long result = 0; 115 unsigned long result = 0;
@@ -131,13 +130,12 @@ unsigned long __find_first_bit(const unsigned long *addr,
131found: 130found:
132 return result + __ffs(tmp); 131 return result + __ffs(tmp);
133} 132}
134EXPORT_SYMBOL(__find_first_bit); 133EXPORT_SYMBOL(find_first_bit);
135 134
136/* 135/*
137 * Find the first cleared bit in a memory region. 136 * Find the first cleared bit in a memory region.
138 */ 137 */
139unsigned long __find_first_zero_bit(const unsigned long *addr, 138unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
140 unsigned long size)
141{ 139{
142 const unsigned long *p = addr; 140 const unsigned long *p = addr;
143 unsigned long result = 0; 141 unsigned long result = 0;
@@ -158,7 +156,7 @@ unsigned long __find_first_zero_bit(const unsigned long *addr,
158found: 156found:
159 return result + ffz(tmp); 157 return result + ffz(tmp);
160} 158}
161EXPORT_SYMBOL(__find_first_zero_bit); 159EXPORT_SYMBOL(find_first_zero_bit);
162#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ 160#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
163 161
164#ifdef __BIG_ENDIAN 162#ifdef __BIG_ENDIAN