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
|
#pragma once
#include <inttypes.h>
#include <sys/types.h>
template<typename T> struct bit_size;
template<typename T, size_t count, size_t bit_sz = bit_size<T>::size>
struct packed_array {
typedef packed_array<T, count, bit_sz> packed_array_t;
typedef uint64_t word_t;
const size_t word_sz = 8 * sizeof(word_t);
uint8_t data[(count * bit_sz + 7) / 8];
/// element access
struct element {
element(word_t *base, uint shift) : base(base), shift(shift) {}
T operator= (T val) {
word_t old_val, new_val;
do {
word_t mask = ~(((((word_t) 1) << bit_sz) - 1) << shift);
old_val = *((volatile word_t*) base);
new_val = (old_val & mask) ^ (val << shift);
} while (!__sync_bool_compare_and_swap(base, old_val, new_val));
return val;
}
operator T() {
word_t mask = (((((word_t) 1) << bit_sz) - 1) << shift);
return static_cast<T>((*base & mask) >> shift);
}
T operator() () {
return (T) (*this);
}
word_t *base;
uint shift;
};
element operator[] (size_t i) {
size_t bit_addr = i * bit_sz;
return element((word_t*) (data + (bit_addr / 8)),
bit_addr % 8);
}
/// simple iteration (for for-all loops)
struct iterator {
packed_array_t &a;
size_t i;
iterator(packed_array_t &a, size_t i) : a(a), i(i) {}
iterator& operator++() { ++i; return *this; }
element operator*() { return a[i]; }
bool operator != (iterator &o) { return (i != o.i) && (&a != &(o.a)); }
};
iterator begin() { return iterator(*this, 0); }
iterator end() { return iterator(*this, count); }
};
|
