1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
/*
* SPDX-License-Identifier: BSD-2-Clause
*
* Copyright (c) 2020 Western Digital Corporation or its affiliates.
*
* Authors:
* Anup Patel <[email protected]>
*/
#ifndef __SBI_BITMAP_H__
#define __SBI_BITMAP_H__
#include <sbi/sbi_bitops.h>
#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
#define BITMAP_LAST_WORD_MASK(nbits) \
( \
((nbits) % BITS_PER_LONG) ? \
((1UL << ((nbits) % BITS_PER_LONG)) - 1) : ~0UL \
)
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
#define DECLARE_BITMAP(name, nbits) unsigned long name[BITS_TO_LONGS(nbits)]
#define DEFINE_BITMAP(name) extern unsigned long name[]
static inline unsigned long bitmap_estimate_size(int nbits)
{
return (BITS_TO_LONGS(nbits) * sizeof(unsigned long));
}
void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits);
void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits);
void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
const unsigned long *bitmap2, int bits);
static inline void bitmap_set(unsigned long *bmap, int start, int len)
{
int bit;
for (bit = start; bit < (start + len); bit++)
bmap[BIT_WORD(bit)] |= (0x1UL << BIT_WORD_OFFSET(bit));
}
static inline void bitmap_clear(unsigned long *bmap, int start, int len)
{
int bit;
for (bit = start; bit < (start + len); bit++)
bmap[BIT_WORD(bit)] &= ~(0x1UL << BIT_WORD_OFFSET(bit));
}
static inline void bitmap_zero(unsigned long *dst, int nbits)
{
if (small_const_nbits(nbits))
*dst = 0UL;
else {
size_t i, len = BITS_TO_LONGS(nbits);
for (i = 0; i < len; i++)
dst[i] = 0;
}
}
static inline int bitmap_test(unsigned long *bmap, int bit)
{
return __test_bit(bit, bmap);
}
static inline void bitmap_zero_except(unsigned long *dst,
int exception, int nbits)
{
if (small_const_nbits(nbits))
*dst = 0UL;
else {
size_t i, len = BITS_TO_LONGS(nbits);
for (i = 0; i < len; i++)
dst[i] = 0;
}
if (exception < nbits)
__set_bit(exception, dst);
}
static inline void bitmap_fill(unsigned long *dst, int nbits)
{
size_t i, nlongs = BITS_TO_LONGS(nbits);
if (!small_const_nbits(nbits)) {
for (i = 0; i < (nlongs - 1); i++)
dst[i] = -1UL;
}
dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
}
static inline void bitmap_copy(unsigned long *dst,
const unsigned long *src, int nbits)
{
if (small_const_nbits(nbits))
*dst = *src;
else {
size_t i, len = BITS_TO_LONGS(nbits);
for (i = 0; i < len; i++)
dst[i] = src[i];
}
}
static inline void bitmap_and(unsigned long *dst, const unsigned long *src1,
const unsigned long *src2, int nbits)
{
if (small_const_nbits(nbits))
*dst = *src1 & *src2;
else
__bitmap_and(dst, src1, src2, nbits);
}
static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
const unsigned long *src2, int nbits)
{
if (small_const_nbits(nbits))
*dst = *src1 | *src2;
else
__bitmap_or(dst, src1, src2, nbits);
}
static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
const unsigned long *src2, int nbits)
{
if (small_const_nbits(nbits))
*dst = *src1 ^ *src2;
else
__bitmap_xor(dst, src1, src2, nbits);
}
static inline int bitmap_weight(const unsigned long *src, int nbits)
{
int i, res = 0;
for (i = 0; i < nbits / BITS_PER_LONG; i++)
res += sbi_popcount(src[i]);
if (nbits % BITS_PER_LONG)
res += sbi_popcount(src[i] & BITMAP_LAST_WORD_MASK(nbits));
return res;
}
static inline bool bitmap_empty(const unsigned long *src, int nbits)
{
if (nbits == 0)
return true;
if (small_const_nbits(nbits))
return !(*src & BITMAP_LAST_WORD_MASK(nbits));
else {
size_t i, len = BITS_TO_LONGS(nbits);
for (i = 0; i < len - 1; i++)
if (src[i])
return false;
return !(src[len - 1] & BITMAP_LAST_WORD_MASK(nbits));
}
}
#endif
|
