debuggers.hg

view xen/include/xen/bitmap.h @ 0:7d21f7218375

Exact replica of unstable on 051908 + README-this
author Mukesh Rathor
date Mon May 19 15:34:57 2008 -0700 (2008-05-19)
parents
children
line source
1 #ifndef __XEN_BITMAP_H
2 #define __XEN_BITMAP_H
4 #ifndef __ASSEMBLY__
6 #include <xen/config.h>
7 #include <xen/lib.h>
8 #include <xen/types.h>
9 #include <xen/bitops.h>
11 /*
12 * bitmaps provide bit arrays that consume one or more unsigned
13 * longs. The bitmap interface and available operations are listed
14 * here, in bitmap.h
15 *
16 * Function implementations generic to all architectures are in
17 * lib/bitmap.c. Functions implementations that are architecture
18 * specific are in various include/asm-<arch>/bitops.h headers
19 * and other arch/<arch> specific files.
20 *
21 * See lib/bitmap.c for more details.
22 */
24 /*
25 * The available bitmap operations and their rough meaning in the
26 * case that the bitmap is a single unsigned long are thus:
27 *
28 * bitmap_zero(dst, nbits) *dst = 0UL
29 * bitmap_fill(dst, nbits) *dst = ~0UL
30 * bitmap_copy(dst, src, nbits) *dst = *src
31 * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2
32 * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2
33 * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2
34 * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2)
35 * bitmap_complement(dst, src, nbits) *dst = ~(*src)
36 * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal?
37 * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap?
38 * bitmap_subset(src1, src2, nbits) Is *src1 a subset of *src2?
39 * bitmap_empty(src, nbits) Are all bits zero in *src?
40 * bitmap_full(src, nbits) Are all bits set in *src?
41 * bitmap_weight(src, nbits) Hamming Weight: number set bits
42 * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n
43 * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n
44 * bitmap_scnprintf(buf, len, src, nbits) Print bitmap src to buf
45 * bitmap_scnlistprintf(buf, len, src, nbits) Print bitmap src as list to buf
46 */
48 /*
49 * Also the following operations in asm/bitops.h apply to bitmaps.
50 *
51 * set_bit(bit, addr) *addr |= bit
52 * clear_bit(bit, addr) *addr &= ~bit
53 * change_bit(bit, addr) *addr ^= bit
54 * test_bit(bit, addr) Is bit set in *addr?
55 * test_and_set_bit(bit, addr) Set bit and return old value
56 * test_and_clear_bit(bit, addr) Clear bit and return old value
57 * test_and_change_bit(bit, addr) Change bit and return old value
58 * find_first_zero_bit(addr, nbits) Position first zero bit in *addr
59 * find_first_bit(addr, nbits) Position first set bit in *addr
60 * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit
61 * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit
62 */
64 /*
65 * The DECLARE_BITMAP(name,bits) macro, in xen/types.h, can be used
66 * to declare an array named 'name' of just enough unsigned longs to
67 * contain all bit positions from 0 to 'bits' - 1.
68 */
70 /*
71 * lib/bitmap.c provides these functions:
72 */
74 extern int __bitmap_empty(const unsigned long *bitmap, int bits);
75 extern int __bitmap_full(const unsigned long *bitmap, int bits);
76 extern int __bitmap_equal(const unsigned long *bitmap1,
77 const unsigned long *bitmap2, int bits);
78 extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
79 int bits);
80 extern void __bitmap_shift_right(unsigned long *dst,
81 const unsigned long *src, int shift, int bits);
82 extern void __bitmap_shift_left(unsigned long *dst,
83 const unsigned long *src, int shift, int bits);
84 extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
85 const unsigned long *bitmap2, int bits);
86 extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
87 const unsigned long *bitmap2, int bits);
88 extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
89 const unsigned long *bitmap2, int bits);
90 extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
91 const unsigned long *bitmap2, int bits);
92 extern int __bitmap_intersects(const unsigned long *bitmap1,
93 const unsigned long *bitmap2, int bits);
94 extern int __bitmap_subset(const unsigned long *bitmap1,
95 const unsigned long *bitmap2, int bits);
96 extern int __bitmap_weight(const unsigned long *bitmap, int bits);
98 extern int bitmap_scnprintf(char *buf, unsigned int len,
99 const unsigned long *src, int nbits);
100 extern int bitmap_scnlistprintf(char *buf, unsigned int len,
101 const unsigned long *src, int nbits);
102 extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
103 extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
104 extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
106 #define BITMAP_LAST_WORD_MASK(nbits) \
107 ( \
108 ((nbits) % BITS_PER_LONG) ? \
109 (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \
110 )
112 static inline void bitmap_zero(unsigned long *dst, int nbits)
113 {
114 if (nbits <= BITS_PER_LONG)
115 *dst = 0UL;
116 else {
117 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
118 memset(dst, 0, len);
119 }
120 }
122 static inline void bitmap_fill(unsigned long *dst, int nbits)
123 {
124 size_t nlongs = BITS_TO_LONGS(nbits);
125 if (nlongs > 1) {
126 int len = (nlongs - 1) * sizeof(unsigned long);
127 memset(dst, 0xff, len);
128 }
129 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
130 }
132 static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
133 int nbits)
134 {
135 if (nbits <= BITS_PER_LONG)
136 *dst = *src;
137 else {
138 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
139 memcpy(dst, src, len);
140 }
141 }
143 static inline void bitmap_and(unsigned long *dst, const unsigned long *src1,
144 const unsigned long *src2, int nbits)
145 {
146 if (nbits <= BITS_PER_LONG)
147 *dst = *src1 & *src2;
148 else
149 __bitmap_and(dst, src1, src2, nbits);
150 }
152 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
153 const unsigned long *src2, int nbits)
154 {
155 if (nbits <= BITS_PER_LONG)
156 *dst = *src1 | *src2;
157 else
158 __bitmap_or(dst, src1, src2, nbits);
159 }
161 static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
162 const unsigned long *src2, int nbits)
163 {
164 if (nbits <= BITS_PER_LONG)
165 *dst = *src1 ^ *src2;
166 else
167 __bitmap_xor(dst, src1, src2, nbits);
168 }
170 static inline void bitmap_andnot(unsigned long *dst, const unsigned long *src1,
171 const unsigned long *src2, int nbits)
172 {
173 if (nbits <= BITS_PER_LONG)
174 *dst = *src1 & ~(*src2);
175 else
176 __bitmap_andnot(dst, src1, src2, nbits);
177 }
179 static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
180 int nbits)
181 {
182 if (nbits <= BITS_PER_LONG)
183 *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
184 else
185 __bitmap_complement(dst, src, nbits);
186 }
188 static inline int bitmap_equal(const unsigned long *src1,
189 const unsigned long *src2, int nbits)
190 {
191 if (nbits <= BITS_PER_LONG)
192 return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
193 else
194 return __bitmap_equal(src1, src2, nbits);
195 }
197 static inline int bitmap_intersects(const unsigned long *src1,
198 const unsigned long *src2, int nbits)
199 {
200 if (nbits <= BITS_PER_LONG)
201 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
202 else
203 return __bitmap_intersects(src1, src2, nbits);
204 }
206 static inline int bitmap_subset(const unsigned long *src1,
207 const unsigned long *src2, int nbits)
208 {
209 if (nbits <= BITS_PER_LONG)
210 return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
211 else
212 return __bitmap_subset(src1, src2, nbits);
213 }
215 static inline int bitmap_empty(const unsigned long *src, int nbits)
216 {
217 if (nbits <= BITS_PER_LONG)
218 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
219 else
220 return __bitmap_empty(src, nbits);
221 }
223 static inline int bitmap_full(const unsigned long *src, int nbits)
224 {
225 if (nbits <= BITS_PER_LONG)
226 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
227 else
228 return __bitmap_full(src, nbits);
229 }
231 static inline int bitmap_weight(const unsigned long *src, int nbits)
232 {
233 return __bitmap_weight(src, nbits);
234 }
236 static inline void bitmap_shift_right(unsigned long *dst,
237 const unsigned long *src, int n, int nbits)
238 {
239 if (nbits <= BITS_PER_LONG)
240 *dst = *src >> n;
241 else
242 __bitmap_shift_right(dst, src, n, nbits);
243 }
245 static inline void bitmap_shift_left(unsigned long *dst,
246 const unsigned long *src, int n, int nbits)
247 {
248 if (nbits <= BITS_PER_LONG)
249 *dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits);
250 else
251 __bitmap_shift_left(dst, src, n, nbits);
252 }
254 void bitmap_long_to_byte(uint8_t *bp, const unsigned long *lp, int nbits);
255 void bitmap_byte_to_long(unsigned long *lp, const uint8_t *bp, int nbits);
257 #endif /* __ASSEMBLY__ */
259 #endif /* __XEN_BITMAP_H */