Blame view
lib/find_bit.c
4.52 KB
2874c5fd2 treewide: Replace... |
1 |
// SPDX-License-Identifier: GPL-2.0-or-later |
8f6f19dd5 lib: move find_la... |
2 |
/* bit search implementation |
1da177e4c Linux-2.6.12-rc2 |
3 4 5 6 |
* * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. * Written by David Howells (dhowells@redhat.com) * |
8f6f19dd5 lib: move find_la... |
7 8 9 10 |
* Copyright (C) 2008 IBM Corporation * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au> * (Inspired by David Howell's find_next_bit implementation) * |
2c57a0e23 lib: find_*_bit r... |
11 12 |
* Rewritten by Yury Norov <yury.norov@gmail.com> to decrease * size and improve performance, 2015. |
1da177e4c Linux-2.6.12-rc2 |
13 14 15 |
*/ #include <linux/bitops.h> |
8f6f19dd5 lib: move find_la... |
16 |
#include <linux/bitmap.h> |
8bc3bcc93 lib: reduce the u... |
17 |
#include <linux/export.h> |
2c57a0e23 lib: find_*_bit r... |
18 |
#include <linux/kernel.h> |
b296a6d53 kernel.h: split o... |
19 |
#include <linux/minmax.h> |
1da177e4c Linux-2.6.12-rc2 |
20 |
|
b78c57135 lib/find_bit.c: j... |
21 22 23 |
#if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \ !defined(find_next_and_bit) |
64970b68d x86, generic: opt... |
24 |
/* |
0ade34c37 lib: optimize cpu... |
25 26 27 28 29 |
* This is a common helper function for find_next_bit, find_next_zero_bit, and * find_next_and_bit. The differences are: * - The "invert" argument, which is XORed with each fetched word before * searching it for one bits. * - The optional "addr2", which is anded with "addr1" if present. |
c7f612cdf [PATCH] bitops: g... |
30 |
*/ |
7dfaa98f6 lib/find_bit.c: u... |
31 |
static unsigned long _find_next_bit(const unsigned long *addr1, |
0ade34c37 lib: optimize cpu... |
32 |
const unsigned long *addr2, unsigned long nbits, |
b78c57135 lib/find_bit.c: j... |
33 |
unsigned long start, unsigned long invert, unsigned long le) |
1da177e4c Linux-2.6.12-rc2 |
34 |
{ |
b78c57135 lib/find_bit.c: j... |
35 |
unsigned long tmp, mask; |
1da177e4c Linux-2.6.12-rc2 |
36 |
|
e4afd2e55 lib/find_bit.c: m... |
37 |
if (unlikely(start >= nbits)) |
2c57a0e23 lib: find_*_bit r... |
38 |
return nbits; |
0ade34c37 lib: optimize cpu... |
39 40 41 42 |
tmp = addr1[start / BITS_PER_LONG]; if (addr2) tmp &= addr2[start / BITS_PER_LONG]; tmp ^= invert; |
2c57a0e23 lib: find_*_bit r... |
43 44 |
/* Handle 1st word. */ |
b78c57135 lib/find_bit.c: j... |
45 46 47 48 49 |
mask = BITMAP_FIRST_WORD_MASK(start); if (le) mask = swab(mask); tmp &= mask; |
2c57a0e23 lib: find_*_bit r... |
50 51 52 53 54 55 |
start = round_down(start, BITS_PER_LONG); while (!tmp) { start += BITS_PER_LONG; if (start >= nbits) return nbits; |
0ade34c37 lib: optimize cpu... |
56 57 58 59 |
tmp = addr1[start / BITS_PER_LONG]; if (addr2) tmp &= addr2[start / BITS_PER_LONG]; tmp ^= invert; |
1da177e4c Linux-2.6.12-rc2 |
60 |
} |
b78c57135 lib/find_bit.c: j... |
61 62 |
if (le) tmp = swab(tmp); |
2c57a0e23 lib: find_*_bit r... |
63 |
return min(start + __ffs(tmp), nbits); |
c7f612cdf [PATCH] bitops: g... |
64 |
} |
19de85ef5 bitops: add #ifnd... |
65 |
#endif |
1da177e4c Linux-2.6.12-rc2 |
66 |
|
2c57a0e23 lib: find_*_bit r... |
67 |
#ifndef find_next_bit |
c7f612cdf [PATCH] bitops: g... |
68 |
/* |
2c57a0e23 lib: find_*_bit r... |
69 |
* Find the next set bit in a memory region. |
c7f612cdf [PATCH] bitops: g... |
70 |
*/ |
2c57a0e23 lib: find_*_bit r... |
71 72 73 |
unsigned long find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) { |
b78c57135 lib/find_bit.c: j... |
74 |
return _find_next_bit(addr, NULL, size, offset, 0UL, 0); |
2c57a0e23 lib: find_*_bit r... |
75 76 77 78 79 |
} EXPORT_SYMBOL(find_next_bit); #endif #ifndef find_next_zero_bit |
fee4b19fb bitops: remove "o... |
80 81 |
unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, unsigned long offset) |
c7f612cdf [PATCH] bitops: g... |
82 |
{ |
b78c57135 lib/find_bit.c: j... |
83 |
return _find_next_bit(addr, NULL, size, offset, ~0UL, 0); |
1da177e4c Linux-2.6.12-rc2 |
84 |
} |
fee4b19fb bitops: remove "o... |
85 |
EXPORT_SYMBOL(find_next_zero_bit); |
19de85ef5 bitops: add #ifnd... |
86 |
#endif |
77b9bd9c4 x86: generic vers... |
87 |
|
0ade34c37 lib: optimize cpu... |
88 89 90 91 92 |
#if !defined(find_next_and_bit) unsigned long find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long offset) { |
b78c57135 lib/find_bit.c: j... |
93 |
return _find_next_bit(addr1, addr2, size, offset, 0UL, 0); |
0ade34c37 lib: optimize cpu... |
94 95 96 |
} EXPORT_SYMBOL(find_next_and_bit); #endif |
19de85ef5 bitops: add #ifnd... |
97 |
#ifndef find_first_bit |
77b9bd9c4 x86: generic vers... |
98 99 100 |
/* * Find the first set bit in a memory region. */ |
fee4b19fb bitops: remove "o... |
101 |
unsigned long find_first_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c4 x86: generic vers... |
102 |
{ |
2c57a0e23 lib: find_*_bit r... |
103 |
unsigned long idx; |
77b9bd9c4 x86: generic vers... |
104 |
|
2c57a0e23 lib: find_*_bit r... |
105 106 107 |
for (idx = 0; idx * BITS_PER_LONG < size; idx++) { if (addr[idx]) return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); |
77b9bd9c4 x86: generic vers... |
108 |
} |
77b9bd9c4 x86: generic vers... |
109 |
|
2c57a0e23 lib: find_*_bit r... |
110 |
return size; |
77b9bd9c4 x86: generic vers... |
111 |
} |
fee4b19fb bitops: remove "o... |
112 |
EXPORT_SYMBOL(find_first_bit); |
19de85ef5 bitops: add #ifnd... |
113 |
#endif |
77b9bd9c4 x86: generic vers... |
114 |
|
19de85ef5 bitops: add #ifnd... |
115 |
#ifndef find_first_zero_bit |
77b9bd9c4 x86: generic vers... |
116 117 118 |
/* * Find the first cleared bit in a memory region. */ |
fee4b19fb bitops: remove "o... |
119 |
unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c4 x86: generic vers... |
120 |
{ |
2c57a0e23 lib: find_*_bit r... |
121 |
unsigned long idx; |
77b9bd9c4 x86: generic vers... |
122 |
|
2c57a0e23 lib: find_*_bit r... |
123 124 125 |
for (idx = 0; idx * BITS_PER_LONG < size; idx++) { if (addr[idx] != ~0UL) return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); |
77b9bd9c4 x86: generic vers... |
126 |
} |
77b9bd9c4 x86: generic vers... |
127 |
|
2c57a0e23 lib: find_*_bit r... |
128 |
return size; |
77b9bd9c4 x86: generic vers... |
129 |
} |
fee4b19fb bitops: remove "o... |
130 |
EXPORT_SYMBOL(find_first_zero_bit); |
19de85ef5 bitops: add #ifnd... |
131 |
#endif |
930ae745f [PATCH] bitops: g... |
132 |
|
8f6f19dd5 lib: move find_la... |
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
#ifndef find_last_bit unsigned long find_last_bit(const unsigned long *addr, unsigned long size) { if (size) { unsigned long val = BITMAP_LAST_WORD_MASK(size); unsigned long idx = (size-1) / BITS_PER_LONG; do { val &= addr[idx]; if (val) return idx * BITS_PER_LONG + __fls(val); val = ~0ul; } while (idx--); } return size; } EXPORT_SYMBOL(find_last_bit); #endif |
930ae745f [PATCH] bitops: g... |
152 |
#ifdef __BIG_ENDIAN |
2c57a0e23 lib: find_*_bit r... |
153 154 155 156 |
#ifndef find_next_zero_bit_le unsigned long find_next_zero_bit_le(const void *addr, unsigned long size, unsigned long offset) { |
b78c57135 lib/find_bit.c: j... |
157 |
return _find_next_bit(addr, NULL, size, offset, ~0UL, 1); |
930ae745f [PATCH] bitops: g... |
158 |
} |
c4945b9ed asm-generic: rena... |
159 |
EXPORT_SYMBOL(find_next_zero_bit_le); |
19de85ef5 bitops: add #ifnd... |
160 |
#endif |
930ae745f [PATCH] bitops: g... |
161 |
|
19de85ef5 bitops: add #ifnd... |
162 |
#ifndef find_next_bit_le |
a56560b3b asm-generic: chan... |
163 |
unsigned long find_next_bit_le(const void *addr, unsigned |
aa02ad67d ext4: Add ext4_fi... |
164 165 |
long size, unsigned long offset) { |
b78c57135 lib/find_bit.c: j... |
166 |
return _find_next_bit(addr, NULL, size, offset, 0UL, 1); |
aa02ad67d ext4: Add ext4_fi... |
167 |
} |
c4945b9ed asm-generic: rena... |
168 |
EXPORT_SYMBOL(find_next_bit_le); |
19de85ef5 bitops: add #ifnd... |
169 |
#endif |
0664996b7 bitops: introduce... |
170 |
|
930ae745f [PATCH] bitops: g... |
171 |
#endif /* __BIG_ENDIAN */ |
169c474fb bitops: introduce... |
172 173 174 175 176 177 178 179 180 181 182 183 184 185 |
unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, unsigned long size, unsigned long offset) { offset = find_next_bit(addr, size, offset); if (offset == size) return size; offset = round_down(offset, 8); *clump = bitmap_get_value8(addr, offset); return offset; } EXPORT_SYMBOL(find_next_clump8); |