2 * Copyright (c) 2013-2017 Mellanox Technologies, Ltd.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice unmodified, this list of conditions, and the following
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 #ifndef _LINUX_BITMAP_H_
30 #define _LINUX_BITMAP_H_
32 #include <linux/bitops.h>
35 bitmap_zero(unsigned long *addr, const unsigned int size)
37 memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
41 bitmap_fill(unsigned long *addr, const unsigned int size)
43 const unsigned int tail = size & (BITS_PER_LONG - 1);
45 memset(addr, 0xff, BIT_WORD(size) * sizeof(long));
48 addr[BIT_WORD(size)] = BITMAP_LAST_WORD_MASK(tail);
52 bitmap_full(unsigned long *addr, const unsigned int size)
54 const unsigned int end = BIT_WORD(size);
55 const unsigned int tail = size & (BITS_PER_LONG - 1);
58 for (i = 0; i != end; i++) {
64 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
66 if ((addr[end] & mask) != mask)
73 bitmap_empty(unsigned long *addr, const unsigned int size)
75 const unsigned int end = BIT_WORD(size);
76 const unsigned int tail = size & (BITS_PER_LONG - 1);
79 for (i = 0; i != end; i++) {
85 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
87 if ((addr[end] & mask) != 0)
94 bitmap_set(unsigned long *map, unsigned int start, int nr)
96 const unsigned int size = start + nr;
97 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
98 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
100 map += BIT_WORD(start);
102 while (nr - bits_to_set >= 0) {
105 bits_to_set = BITS_PER_LONG;
111 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
117 bitmap_clear(unsigned long *map, unsigned int start, int nr)
119 const unsigned int size = start + nr;
120 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
121 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
123 map += BIT_WORD(start);
125 while (nr - bits_to_clear >= 0) {
126 *map &= ~mask_to_clear;
128 bits_to_clear = BITS_PER_LONG;
129 mask_to_clear = ~0UL;
134 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
135 *map &= ~mask_to_clear;
139 static inline unsigned int
140 bitmap_find_next_zero_area_off(const unsigned long *map,
141 const unsigned int size, unsigned int start,
142 unsigned int nr, unsigned int align_mask,
143 unsigned int align_offset)
150 index = find_next_zero_bit(map, size, start);
152 index = (((index + align_offset) + align_mask) & ~align_mask) - align_offset;
158 i = find_next_bit(map, end, index);
166 static inline unsigned int
167 bitmap_find_next_zero_area(const unsigned long *map,
168 const unsigned int size, unsigned int start,
169 unsigned int nr, unsigned int align_mask)
171 return (bitmap_find_next_zero_area_off(map, size,
172 start, nr, align_mask, 0));
176 bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
181 for (pos = 0; (end = pos + (1 << order)) <= bits; pos = end) {
182 if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
184 linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
191 bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
193 if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
195 linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
200 bitmap_release_region(unsigned long *bitmap, int pos, int order)
202 linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
205 static inline unsigned int
206 bitmap_weight(unsigned long *addr, const unsigned int size)
208 const unsigned int end = BIT_WORD(size);
209 const unsigned int tail = size & (BITS_PER_LONG - 1);
210 unsigned int retval = 0;
213 for (i = 0; i != end; i++)
214 retval += hweight_long(addr[i]);
217 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
219 retval += hweight_long(addr[end] & mask);
225 bitmap_equal(const unsigned long *pa,
226 const unsigned long *pb, unsigned size)
228 const unsigned int end = BIT_WORD(size);
229 const unsigned int tail = size & (BITS_PER_LONG - 1);
232 for (i = 0; i != end; i++) {
238 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
240 if ((pa[end] ^ pb[end]) & mask)
247 bitmap_complement(unsigned long *dst, const unsigned long *src,
248 const unsigned int size)
250 const unsigned int end = BITS_TO_LONGS(size);
253 for (i = 0; i != end; i++)
258 bitmap_or(unsigned long *dst, const unsigned long *src1,
259 const unsigned long *src2, const unsigned int size)
261 const unsigned int end = BITS_TO_LONGS(size);
264 for (i = 0; i != end; i++)
265 dst[i] = src1[i] | src2[i];
269 bitmap_and(unsigned long *dst, const unsigned long *src1,
270 const unsigned long *src2, const unsigned int size)
272 const unsigned int end = BITS_TO_LONGS(size);
275 for (i = 0; i != end; i++)
276 dst[i] = src1[i] & src2[i];
280 bitmap_xor(unsigned long *dst, const unsigned long *src1,
281 const unsigned long *src2, const unsigned int size)
283 const unsigned int end = BITS_TO_LONGS(size);
286 for (i = 0; i != end; i++)
287 dst[i] = src1[i] ^ src2[i];
290 #endif /* _LINUX_BITMAP_H_ */