← Back to branch summary

~ahs3/+junk/cq-qemu

« back to all changes in this revision

Viewing changes to bitmap.h

  • Committer: Al Stone
  • Date: 2012-02-09 01:17:20 UTC
  • Revision ID: albert.stone@canonical.com-20120209011720-tztl7ik3qayz80p4
first commit to bzr for qemu

Show diffs side-by-side

added added

removed removed

Lines of Context:
bitmap.h
 
1
/*
 
2
 * Bitmap Module
 
3
 *
 
4
 * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
 
5
 *
 
6
 * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
 
7
 *
 
8
 * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
 
9
 * See the COPYING.LIB file in the top-level directory.
 
10
 */
 
11
 
 
12
#ifndef BITMAP_H
 
13
#define BITMAP_H
 
14
 
 
15
#include "qemu-common.h"
 
16
#include "bitops.h"
 
17
 
 
18
/*
 
19
 * The available bitmap operations and their rough meaning in the
 
20
 * case that the bitmap is a single unsigned long are thus:
 
21
 *
 
22
 * Note that nbits should be always a compile time evaluable constant.
 
23
 * Otherwise many inlines will generate horrible code.
 
24
 *
 
25
 * bitmap_zero(dst, nbits)                      *dst = 0UL
 
26
 * bitmap_fill(dst, nbits)                      *dst = ~0UL
 
27
 * bitmap_copy(dst, src, nbits)                 *dst = *src
 
28
 * bitmap_and(dst, src1, src2, nbits)           *dst = *src1 & *src2
 
29
 * bitmap_or(dst, src1, src2, nbits)            *dst = *src1 | *src2
 
30
 * bitmap_xor(dst, src1, src2, nbits)           *dst = *src1 ^ *src2
 
31
 * bitmap_andnot(dst, src1, src2, nbits)        *dst = *src1 & ~(*src2)
 
32
 * bitmap_complement(dst, src, nbits)           *dst = ~(*src)
 
33
 * bitmap_equal(src1, src2, nbits)              Are *src1 and *src2 equal?
 
34
 * bitmap_intersects(src1, src2, nbits)         Do *src1 and *src2 overlap?
 
35
 * bitmap_empty(src, nbits)                     Are all bits zero in *src?
 
36
 * bitmap_full(src, nbits)                      Are all bits set in *src?
 
37
 * bitmap_set(dst, pos, nbits)                  Set specified bit area
 
38
 * bitmap_clear(dst, pos, nbits)                Clear specified bit area
 
39
 * bitmap_find_next_zero_area(buf, len, pos, n, mask)   Find bit free area
 
40
 */
 
41
 
 
42
/*
 
43
 * Also the following operations apply to bitmaps.
 
44
 *
 
45
 * set_bit(bit, addr)                   *addr |= bit
 
46
 * clear_bit(bit, addr)                 *addr &= ~bit
 
47
 * change_bit(bit, addr)                *addr ^= bit
 
48
 * test_bit(bit, addr)                  Is bit set in *addr?
 
49
 * test_and_set_bit(bit, addr)          Set bit and return old value
 
50
 * test_and_clear_bit(bit, addr)        Clear bit and return old value
 
51
 * test_and_change_bit(bit, addr)       Change bit and return old value
 
52
 * find_first_zero_bit(addr, nbits)     Position first zero bit in *addr
 
53
 * find_first_bit(addr, nbits)          Position first set bit in *addr
 
54
 * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit
 
55
 * find_next_bit(addr, nbits, bit)      Position next set bit in *addr >= bit
 
56
 */
 
57
 
 
58
#define BITMAP_LAST_WORD_MASK(nbits)                                    \
 
59
    (                                                                   \
 
60
        ((nbits) % BITS_PER_LONG) ?                                     \
 
61
        (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL                       \
 
62
        )
 
63
 
 
64
#define DECLARE_BITMAP(name,bits)                  \
 
65
        unsigned long name[BITS_TO_LONGS(bits)]
 
66
 
 
67
#define small_nbits(nbits)                      \
 
68
        ((nbits) <= BITS_PER_LONG)
 
69
 
 
70
int slow_bitmap_empty(const unsigned long *bitmap, int bits);
 
71
int slow_bitmap_full(const unsigned long *bitmap, int bits);
 
72
int slow_bitmap_equal(const unsigned long *bitmap1,
 
73
                   const unsigned long *bitmap2, int bits);
 
74
void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
 
75
                         int bits);
 
76
void slow_bitmap_shift_right(unsigned long *dst,
 
77
                          const unsigned long *src, int shift, int bits);
 
78
void slow_bitmap_shift_left(unsigned long *dst,
 
79
                         const unsigned long *src, int shift, int bits);
 
80
int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 
81
                 const unsigned long *bitmap2, int bits);
 
82
void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 
83
                 const unsigned long *bitmap2, int bits);
 
84
void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
 
85
                  const unsigned long *bitmap2, int bits);
 
86
int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 
87
                    const unsigned long *bitmap2, int bits);
 
88
int slow_bitmap_intersects(const unsigned long *bitmap1,
 
89
                        const unsigned long *bitmap2, int bits);
 
90
 
 
91
static inline unsigned long *bitmap_new(int nbits)
 
92
{
 
93
    int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
 
94
    return g_malloc0(len);
 
95
}
 
96
 
 
97
static inline void bitmap_zero(unsigned long *dst, int nbits)
 
98
{
 
99
    if (small_nbits(nbits)) {
 
100
        *dst = 0UL;
 
101
    } else {
 
102
        int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
 
103
        memset(dst, 0, len);
 
104
    }
 
105
}
 
106
 
 
107
static inline void bitmap_fill(unsigned long *dst, int nbits)
 
108
{
 
109
    size_t nlongs = BITS_TO_LONGS(nbits);
 
110
    if (!small_nbits(nbits)) {
 
111
        int len = (nlongs - 1) * sizeof(unsigned long);
 
112
        memset(dst, 0xff,  len);
 
113
    }
 
114
    dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
 
115
}
 
116
 
 
117
static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
 
118
                               int nbits)
 
119
{
 
120
    if (small_nbits(nbits)) {
 
121
        *dst = *src;
 
122
    } else {
 
123
        int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
 
124
        memcpy(dst, src, len);
 
125
    }
 
126
}
 
127
 
 
128
static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
 
129
                             const unsigned long *src2, int nbits)
 
130
{
 
131
    if (small_nbits(nbits)) {
 
132
        return (*dst = *src1 & *src2) != 0;
 
133
    }
 
134
    return slow_bitmap_and(dst, src1, src2, nbits);
 
135
}
 
136
 
 
137
static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
 
138
                        const unsigned long *src2, int nbits)
 
139
{
 
140
    if (small_nbits(nbits)) {
 
141
        *dst = *src1 | *src2;
 
142
    } else {
 
143
        slow_bitmap_or(dst, src1, src2, nbits);
 
144
    }
 
145
}
 
146
 
 
147
static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
 
148
                        const unsigned long *src2, int nbits)
 
149
{
 
150
    if (small_nbits(nbits)) {
 
151
        *dst = *src1 ^ *src2;
 
152
    } else {
 
153
        slow_bitmap_xor(dst, src1, src2, nbits);
 
154
    }
 
155
}
 
156
 
 
157
static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
 
158
                        const unsigned long *src2, int nbits)
 
159
{
 
160
    if (small_nbits(nbits)) {
 
161
        return (*dst = *src1 & ~(*src2)) != 0;
 
162
    }
 
163
    return slow_bitmap_andnot(dst, src1, src2, nbits);
 
164
}
 
165
 
 
166
static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
 
167
                        int nbits)
 
168
{
 
169
    if (small_nbits(nbits)) {
 
170
        *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
 
171
    } else {
 
172
        slow_bitmap_complement(dst, src, nbits);
 
173
    }
 
174
}
 
175
 
 
176
static inline int bitmap_equal(const unsigned long *src1,
 
177
                        const unsigned long *src2, int nbits)
 
178
{
 
179
    if (small_nbits(nbits)) {
 
180
        return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
 
181
    } else {
 
182
        return slow_bitmap_equal(src1, src2, nbits);
 
183
    }
 
184
}
 
185
 
 
186
static inline int bitmap_empty(const unsigned long *src, int nbits)
 
187
{
 
188
    if (small_nbits(nbits)) {
 
189
        return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
 
190
    } else {
 
191
        return slow_bitmap_empty(src, nbits);
 
192
    }
 
193
}
 
194
 
 
195
static inline int bitmap_full(const unsigned long *src, int nbits)
 
196
{
 
197
    if (small_nbits(nbits)) {
 
198
        return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
 
199
    } else {
 
200
        return slow_bitmap_full(src, nbits);
 
201
    }
 
202
}
 
203
 
 
204
static inline int bitmap_intersects(const unsigned long *src1,
 
205
                        const unsigned long *src2, int nbits)
 
206
{
 
207
    if (small_nbits(nbits)) {
 
208
        return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
 
209
    } else {
 
210
        return slow_bitmap_intersects(src1, src2, nbits);
 
211
    }
 
212
}
 
213
 
 
214
void bitmap_set(unsigned long *map, int i, int len);
 
215
void bitmap_clear(unsigned long *map, int start, int nr);
 
216
unsigned long bitmap_find_next_zero_area(unsigned long *map,
 
217
                                         unsigned long size,
 
218
                                         unsigned long start,
 
219
                                         unsigned int nr,
 
220
                                         unsigned long align_mask);
 
221
 
 
222
#endif /* BITMAP_H */