/home/travis/build/MoarVM/MoarVM/src/core/bitmap.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* basic bitmap implementation */ |
2 | | typedef MVMuint64 MVMBitmap; |
3 | | |
4 | | /* Efficient find-first-set; on x86, using `bsf` primitive operation; something |
5 | | * else on other architectures. */ |
6 | | #ifdef __GNUC__ |
7 | | /* also works for clang and friends */ |
8 | | #define MVM_FFS(x) __builtin_ffsll(x) |
9 | | #elif defined(_MSC_VER) |
10 | | MVM_STATIC_INLINE MVMuint32 MVM_FFS(MVMBitmap x) { |
11 | | MVMuint32 i = 0; |
12 | | if (_BitScanForward64(&i, x) == 0) |
13 | | return 0; |
14 | | return i + 1; |
15 | | } |
16 | | #else |
17 | | /* fallback, note that i=0 if no bits are set */ |
18 | | MVM_STATIC_INLINE MVMuint32 MVM_FFS(MVMBitmap x) { |
19 | | MVMuint32 i = 0; |
20 | | while (x) { |
21 | | if (x & (1 << i++)) |
22 | | break; |
23 | | } |
24 | | return i; |
25 | | } |
26 | | #endif |
27 | | |
28 | | |
29 | | /* NB - make this a separate 'library', use it for register bitmap */ |
30 | | /* Witness the elegance of the bitmap for our purposes. */ |
31 | 0 | MVM_STATIC_INLINE void MVM_bitmap_set(MVMBitmap *bits, MVMint32 idx) { |
32 | 0 | bits[idx >> 6] |= (UINT64_C(1) << (idx & 0x3f)); |
33 | 0 | } |
34 | | |
35 | 0 | MVM_STATIC_INLINE MVMuint64 MVM_bitmap_get(MVMBitmap *bits, MVMint32 idx) { |
36 | 0 | return bits[idx >> 6] & (UINT64_C(1) << (idx & 0x3f)); |
37 | 0 | } |
38 | | |
39 | 0 | MVM_STATIC_INLINE MVMuint64 MVM_bitmap_get_low(MVMBitmap bits, MVMint32 idx ) { |
40 | 0 | return bits & (UINT64_C(1) << (idx & 0x3f)); |
41 | 0 | } |
42 | | |
43 | 0 | MVM_STATIC_INLINE void MVM_bitmap_delete(MVMBitmap *bits, MVMint32 idx) { |
44 | 0 | bits[idx >> 6] &= ~(UINT64_C(1) << (idx & 0x3f)); |
45 | 0 | } |
46 | | |
47 | 0 | MVM_STATIC_INLINE void MVM_bitmap_union(MVMBitmap *out, MVMBitmap *a, MVMBitmap *b, MVMint32 n) { |
48 | 0 | MVMint32 i; |
49 | 0 | for (i = 0; i < n; i++) { |
50 | 0 | out[i] = a[i] | b[i]; |
51 | 0 | } |
52 | 0 | } |
53 | | |
54 | 0 | MVM_STATIC_INLINE void MVM_bitmap_difference(MVMBitmap *out, MVMBitmap *a, MVMBitmap *b, MVMint32 n) { |
55 | 0 | MVMint32 i; |
56 | 0 | for (i = 0; i < n; i++) { |
57 | 0 | out[i] = a[i] ^ b[i]; |
58 | 0 | } |
59 | 0 | } |
60 | | |
61 | 0 | MVM_STATIC_INLINE void MVM_bitmap_intersection(MVMBitmap *out, MVMBitmap *a, MVMBitmap *b, MVMint32 n) { |
62 | 0 | MVMint32 i; |
63 | 0 | for (i = 0; i < n; i++) { |
64 | 0 | out[i] = a[i] & b[i]; |
65 | 0 | } |
66 | 0 | } |