use win32 timer queues
[qemu.git] / bitmap.c
bloba62c8ba68148a62d2caf1e5cf15eeefa408cf5f7
1 /*
2 * Bitmap Module
4 * Stolen from linux/src/lib/bitmap.c
6 * Copyright (C) 2010 Corentin Chary
8 * This source code is licensed under the GNU General Public License,
9 * Version 2.
12 #include "bitops.h"
13 #include "bitmap.h"
16 * bitmaps provide an array of bits, implemented using an an
17 * array of unsigned longs. The number of valid bits in a
18 * given bitmap does _not_ need to be an exact multiple of
19 * BITS_PER_LONG.
21 * The possible unused bits in the last, partially used word
22 * of a bitmap are 'don't care'. The implementation makes
23 * no particular effort to keep them zero. It ensures that
24 * their value will not affect the results of any operation.
25 * The bitmap operations that return Boolean (bitmap_empty,
26 * for example) or scalar (bitmap_weight, for example) results
27 * carefully filter out these unused bits from impacting their
28 * results.
30 * These operations actually hold to a slightly stronger rule:
31 * if you don't input any bitmaps to these ops that have some
32 * unused bits set, then they won't output any set unused bits
33 * in output bitmaps.
35 * The byte ordering of bitmaps is more natural on little
36 * endian architectures.
39 int slow_bitmap_empty(const unsigned long *bitmap, int bits)
41 int k, lim = bits/BITS_PER_LONG;
43 for (k = 0; k < lim; ++k) {
44 if (bitmap[k]) {
45 return 0;
48 if (bits % BITS_PER_LONG) {
49 if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
50 return 0;
54 return 1;
57 int slow_bitmap_full(const unsigned long *bitmap, int bits)
59 int k, lim = bits/BITS_PER_LONG;
61 for (k = 0; k < lim; ++k) {
62 if (~bitmap[k]) {
63 return 0;
67 if (bits % BITS_PER_LONG) {
68 if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
69 return 0;
73 return 1;
76 int slow_bitmap_equal(const unsigned long *bitmap1,
77 const unsigned long *bitmap2, int bits)
79 int k, lim = bits/BITS_PER_LONG;
81 for (k = 0; k < lim; ++k) {
82 if (bitmap1[k] != bitmap2[k]) {
83 return 0;
87 if (bits % BITS_PER_LONG) {
88 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
89 return 0;
93 return 1;
96 void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
97 int bits)
99 int k, lim = bits/BITS_PER_LONG;
101 for (k = 0; k < lim; ++k) {
102 dst[k] = ~src[k];
105 if (bits % BITS_PER_LONG) {
106 dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
110 int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
111 const unsigned long *bitmap2, int bits)
113 int k;
114 int nr = BITS_TO_LONGS(bits);
115 unsigned long result = 0;
117 for (k = 0; k < nr; k++) {
118 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
120 return result != 0;
123 void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
124 const unsigned long *bitmap2, int bits)
126 int k;
127 int nr = BITS_TO_LONGS(bits);
129 for (k = 0; k < nr; k++) {
130 dst[k] = bitmap1[k] | bitmap2[k];
134 void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
135 const unsigned long *bitmap2, int bits)
137 int k;
138 int nr = BITS_TO_LONGS(bits);
140 for (k = 0; k < nr; k++) {
141 dst[k] = bitmap1[k] ^ bitmap2[k];
145 int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
146 const unsigned long *bitmap2, int bits)
148 int k;
149 int nr = BITS_TO_LONGS(bits);
150 unsigned long result = 0;
152 for (k = 0; k < nr; k++) {
153 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
155 return result != 0;
158 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
160 void bitmap_set(unsigned long *map, int start, int nr)
162 unsigned long *p = map + BIT_WORD(start);
163 const int size = start + nr;
164 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
165 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
167 while (nr - bits_to_set >= 0) {
168 *p |= mask_to_set;
169 nr -= bits_to_set;
170 bits_to_set = BITS_PER_LONG;
171 mask_to_set = ~0UL;
172 p++;
174 if (nr) {
175 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
176 *p |= mask_to_set;
180 void bitmap_clear(unsigned long *map, int start, int nr)
182 unsigned long *p = map + BIT_WORD(start);
183 const int size = start + nr;
184 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
185 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
187 while (nr - bits_to_clear >= 0) {
188 *p &= ~mask_to_clear;
189 nr -= bits_to_clear;
190 bits_to_clear = BITS_PER_LONG;
191 mask_to_clear = ~0UL;
192 p++;
194 if (nr) {
195 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
196 *p &= ~mask_to_clear;
200 #define ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
203 * bitmap_find_next_zero_area - find a contiguous aligned zero area
204 * @map: The address to base the search on
205 * @size: The bitmap size in bits
206 * @start: The bitnumber to start searching at
207 * @nr: The number of zeroed bits we're looking for
208 * @align_mask: Alignment mask for zero area
210 * The @align_mask should be one less than a power of 2; the effect is that
211 * the bit offset of all zero areas this function finds is multiples of that
212 * power of 2. A @align_mask of 0 means no alignment is required.
214 unsigned long bitmap_find_next_zero_area(unsigned long *map,
215 unsigned long size,
216 unsigned long start,
217 unsigned int nr,
218 unsigned long align_mask)
220 unsigned long index, end, i;
221 again:
222 index = find_next_zero_bit(map, size, start);
224 /* Align allocation */
225 index = ALIGN_MASK(index, align_mask);
227 end = index + nr;
228 if (end > size) {
229 return end;
231 i = find_next_bit(map, end, index);
232 if (i < end) {
233 start = i + 1;
234 goto again;
236 return index;
239 int slow_bitmap_intersects(const unsigned long *bitmap1,
240 const unsigned long *bitmap2, int bits)
242 int k, lim = bits/BITS_PER_LONG;
244 for (k = 0; k < lim; ++k) {
245 if (bitmap1[k] & bitmap2[k]) {
246 return 1;
250 if (bits % BITS_PER_LONG) {
251 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
252 return 1;
255 return 0;